4 — Renaming

The last chapter decided where the φ functions go. They are still empty: nothing says yet which version each input carries, and no read names a version. This chapter fills them in. The step is called renaming, and it is one walk over the dominator tree.

The program

Evens.mica again, as you saved it in chapter 2, exported at the debug tier:

mkdir -p ssa-lab && cd ssa-lab
mica --compile --optimize debug --platform linux,amd64,utf-8 --source Evens.mica --build build/debug --export

Exporting intermediate representations of source 'Evens.mica' to 'build/debug/export'

The walk

Renaming keeps, for every versioned variable, a stack of versions and a counter for the next version number. A parameter starts with version 0 on its stack: the value the caller passed. Then the walk visits the blocks of the dominator tree from the root, each block before its children, and in each block does four things:

Every φ of the block defines a new version of its variable: take the counter’s number, push the version.
Every instruction, in order: a read of a variable takes the version on top of its stack; a write defines a new version and pushes it.
At the end of the block, for every successor in the control-flow graph, fill the inputs of the successor’s φ functions that belong to the edge from this block, with the versions now on top of the stacks.
Visit the block’s children in the dominator tree, and on the way back pop every version this block pushed.

Why the dominator tree? A read must see the latest write on every path that reaches it. When the walk stands in a block, the blocks it has entered on the way down are exactly the blocks that dominate this one: every path to this block passes through all of them. So the versions on the stacks are the ones every path brings here, except where paths meet, and there the φ functions already stand. The pop in step 4 keeps a block from seeing what another child of the same parent wrote: block 6 is not reached through block 5, so it must not see block 5’s version.

This is the renaming of Cytron and his co-authors, and it is the one Mica runs.

The walk on `CountEven`

The dominator tree from chapter 2 gives the order: 2, 3, 4, 5, 6, 7, 8. The table below follows the walk by hand for count, k, last and the result CountEven, written count#0 for version 0 of count:

block  what it does                          pushes              fills the φ inputs of
2      count := 0, last := 0, k := 1         count#0 last#0 k#0  block 3, from 2: count#0, k#0
3      φ count, φ k; reads k#1               count#1 k#1         (blocks 7 and 4 have no φ for these)
4      reads k#1                             -                   block 6, from 4: count#1
5      reads count#1 and k#1;                count#2 last#1      block 6, from 5: count#2
       writes count and last                                     then pops count#2 and last#1
6      φ count; reads k#1, writes k          count#3 k#2         block 3, from 6: count#3, k#2
                                                                 then pops count#3 and k#2
7      reads count#1, writes CountEven       CountEven#0         -
8      reads CountEven#0                     -                   -

Versions are numbered in the order the walk meets the writes. That is why the φ at the top of the loop is count#1 although its input from the end of the round is count#3: the walk reaches that φ before any write inside the loop.

Read the result in Evens.090.ssa, the SSA form of CountEven from the top of the loop on. v2.1 is count, v2.2 is k, v2.3 is last and v2.4 is CountEven:

@l2.4:
    v2.1#1:int64 = phi 2: v2.1#0:int64, 6: v2.1#3:int64 #13
    v2.2#1:int64 = phi 2: v2.2#0:int64, 6: v2.2#2:int64 #14
    // 21: while k ≤ limit do
    t2.4:int64 = loadVariable v2.2#1:int64 #15
    t2.5:int64 = loadVariable p2.1#0:int64 #16
    t2.6:bool = lessEqual t2.4:int64, t2.5:int64 #17
    jumpNotEqual t2.6:bool, @l2.5
    // 23: if k mod 2 = 0 then
    t2.7:int64 = loadVariable v2.2#1:int64 #18
    t2.8:int64 = copyLiteral 2:int64 #19
    t2.9:int64 = modulo t2.7:int64, t2.8:int64 <@l2.8, @l2.9, @l2.10> #20
    t2.10:int64 = copyLiteral 0:int64 #21
    t2.11:bool = equal t2.9:int64, t2.10:int64 #22
    jumpNotEqual t2.11:bool, @l2.6
    // 25: count := count + 1;
    t2.12:int64 = loadVariable v2.1#1:int64 #23
    t2.13:int64 = copyLiteral 1:int64 #24
    t2.14:int64 = add t2.12:int64, t2.13:int64 <@l2.13, @l2.14, @l2.15> #25
    storeVariable t2.14:int64, v2.1#2:int64 #26
    // 26: last := k;
    t2.15:int64 = loadVariable v2.2#1:int64 #27
    storeVariable t2.15:int64, v2.3#1:int64 #28
@l2.6:
    v2.1#3:int64 = phi 4: v2.1#1:int64, 5: v2.1#2:int64 #29
    // 29: k := k + 1;
    t2.16:int64 = loadVariable v2.2#1:int64 #30
    t2.17:int64 = copyLiteral 1:int64 #31
    t2.18:int64 = add t2.16:int64, t2.17:int64 <@l2.17, @l2.18, @l2.19> #32
    storeVariable t2.18:int64, v2.2#2:int64 #33
    // 21: while k ≤ limit do
    jump @l2.4
@l2.5:
    // 32: CountEven := count;
    t2.19:int64 = loadVariable v2.1#1:int64 #34
    storeVariable t2.19:int64, v2.4#0:int64 #35

Every line of the table is there. Three details are worth a second look:

limit is read as p2.1#0 in every round: the loop never writes it, so its entry version stays on top of its stack all the way down.
After the loop, CountEven := count reads v2.1#1, the count of the top of the round whose test ended the loop, not count#3: block 7 hangs under block 3 in the dominator tree, and count#3 was popped when the walk left block 6.
last is written as v2.3#0 and v2.3#1 and has no φ: renaming versions every write of it all the same, and the versions are simply never read. Chapter 5 shows what the optimizer does with writes like these.

Versions and value ids

Each line now carries two kinds of number, and they answer two different questions. The version, #1 right after v2.1, names a value where it is used. The value id, #13 at the end of the line, numbers the instruction that defines a value, counted through the whole unit. In SSA they finally agree one to one: v2.1#1 is defined by exactly one instruction, the φ with the value id 13, and by nothing else. The SSA form counts its value ids afresh, since its φ functions are new instructions, so #13 here is not the #13 of 040.spectra.

The compiler checks the result

The renamed form is checked before anything uses it. Mica verifies that every version has exactly one definition, that the definition of every version dominates each of its uses (a φ input counts as a use at the end of the predecessor it belongs to), that every φ has one input for each predecessor of its block, and that no block reads a version before it is defined. A violation stops the compiler and names what failed: a wrong SSA form is never handed on.

Try it

Make the loop count by twos: write k := k + 1; a second time, right under the first. Export again and follow k, v2.2, through the form:

    storeVariable t2.3:int64, v2.2#0:int64 #12
    v2.2#1:int64 = phi 2: v2.2#0:int64, 6: v2.2#3:int64 #14
    t2.4:int64 = loadVariable v2.2#1:int64 #15
    t2.7:int64 = loadVariable v2.2#1:int64 #18
    t2.15:int64 = loadVariable v2.2#1:int64 #27
    t2.16:int64 = loadVariable v2.2#1:int64 #30
    storeVariable t2.18:int64, v2.2#2:int64 #33
    t2.19:int64 = loadVariable v2.2#2:int64 #34
    storeVariable t2.21:int64, v2.2#3:int64 #37

Block 6 now writes k twice. The first write pushes k#2, the second addition reads it, and the second write pushes k#3, which is on top when the block ends: the φ at the top of the loop now takes v2.2#3 from block 6. The number of φ functions did not change, because no new block writes k. Undo the edit before you go on.

Next: What SSA makes easy.

The program#

The walk#

The walk on CountEven#

Versions and value ids#

The compiler checks the result#

Try it#