6 — Leaving SSA

A processor has no instruction that picks a value according to the road control came along. Before the compiler can make machine code, the φ functions have to go, and every version has to find a real home again. This last chapter shows why that is harder than it looks, and why in Mica it comes down to erasing the version numbers.

The program

Save this as Swaps.mica in the lab folder:

mkdir -p ssa-lab && cd ssa-lab

{
    Swaps - the two loops that make leaving static single assignment form hard.

    'PlayerAfter' swaps two variables on every round of its loop, and 'LastCounted' still reads, after its loop, the
    value a variable had before the last round changed it.
}
program Swaps;

imp
    WriteLn : std;

{ The player whose turn it is after a number of turns is found by letting two players alternate, player 1 first. }
function PlayerAfter(turns : int64) : int64;
var
    current, waiting, previous, turn : int64;
begin
    current := 1;
    waiting := 2;
    turn := 0;

    while turn < turns do
    begin
        previous := current;
        current := waiting;
        waiting := previous;
        turn := turn + 1;
    end;

    PlayerAfter := current;
end;

{ A counter starting at 1 runs past the limit, and the last number it reached before that is the answer. }
function LastCounted(limit : int64) : int64;
var
    x, last : int64;
begin
    x := 1;

    repeat
        last := x;
        x := x + 1;
    until x > limit;

    LastCounted := last;
end;

begin
    WriteLn("after 7 turns, player %lld moves", PlayerAfter(7));
    WriteLn("counting up to 10 ends at %lld", LastCounted(10));
end.

Run it, and export it at the debug tier and at O1:

mica Swaps.mica
mica --compile --optimize debug --platform linux,amd64,utf-8 --source Swaps.mica --build build/debug --export
mica --compile --optimize O1 --platform linux,amd64,utf-8 --source Swaps.mica --build build/O1 --export

after 7 turns, player 2 moves
counting up to 10 ends at 10
Exporting intermediate representations of source 'Swaps.mica' to 'build/debug/export'
Exporting intermediate representations of source 'Swaps.mica' to 'build/O1/export'

In PlayerAfter, v2.1 is current, v2.2 is waiting, v2.3 is previous and v2.4 is turn. In LastCounted, v3.1 is x and v3.2 is last.

The textbook way out, and its two traps

The textbook removes a φ by turning it into copies. For x3 = phi(B1: x1, B2: x2) it puts the copy x3 := x1 at the end of block B1 and x3 := x2 at the end of block B2, and drops the φ. Done naively, this breaks in two classic ways, which Briggs, Cooper, Harvey and Simpson laid out:

The lost copy. A copy at the end of a block runs on every edge that leaves the block. If the block has a second successor that still needs the old value of x3, the copy has destroyed it. An edge from a block with several successors to a block with several predecessors is called a critical edge, and the cure is to split it: put a new, empty block on the edge and the copy in that block.
The swap. The φ functions at the top of one block all pick their values at the same moment, as control enters. When a loop swaps two variables, and the optimizer has removed the temporary of the swap, the loop’s header holds a2 = phi(entry: a1, loop: b2) and b2 = phi(entry: b1, loop: a2). The copies a2 := b2 and then b2 := a2 give b2 the new a2 instead of the old one. The cure is to order the copies, and to break such a cycle with an extra temporary.

The literature then found the general rule. A form in which no two names joined by a φ are ever live at the same time is called conventional SSA: all those names can share one home, and the φ disappears without a single copy. Optimizations can break that property, and leaving SSA in general means restoring it with copies and then removing as many copies as possible again (Sreedhar and his co-authors; Boissinot and his co-authors).

How Mica leaves SSA

Mica’s φ functions only ever join versions of one variable: v2.1#1, v2.1#0 and v2.1#2, all versions of current. If no two versions of a variable are ever live at the same point, the form is conventional, and leaving it is a renaming: every v2.1#k becomes v2.1 again, every φ becomes a copy of v2.1 onto itself, and a copy onto itself is dropped. The copies the textbook would insert are already in the program: they are the stores that wrote the versions.

The form stays conventional because of how Mica builds it. A value moves from one variable to another only through a temporary, a load and then a store, and the optimizations change which temporary carries a value but never let a version of one variable stand in for a version of another. Mica does not take this on trust. Before the program leaves the form, the compiler computes which versions are live at every point and stops if two versions of one variable are ever live at once, or if a φ ever joins two different variables. Since no copy is ever placed on an edge, no critical edge needs to be split.

At the debug tier, where nothing is optimized, erasing the versions and dropping the φ functions must give back exactly the program the form was built from. Mica checks this on every export, and you can check it too: 100.out-of-ssa is the program after leaving SSA, and 040.spectra the program before it was built:

cmp build/debug/export/Swaps.040.spectra build/debug/export/Swaps.100.out-of-ssa && echo identical

identical

The swap, in Mica

PlayerAfter swaps current and waiting in every round. The loop at O1, in build/O1/export/Swaps.090.ssa:

@l2.4:
    v2.1#1:int64 = phi 2: v2.1#0:int64, 4: v2.1#2:int64 #18
    v2.2#1:int64 = phi 2: v2.2#0:int64, 4: v2.2#2:int64 #19
    v2.4#1:int64 = phi 2: v2.4#0:int64, 4: v2.4#2:int64 #20
    // 21: while turn < turns do
    t2.4:int64 = loadVariable v2.4#1:int64 #21
    t2.5:int64 = loadVariable p2.1#0:int64 #22
    t2.6:bool = less t2.4:int64, t2.5:int64 #23
    jumpNotEqual t2.6:bool, @l2.5
    // 23: previous := current;
    t2.7:int64 = loadVariable v2.1#1:int64 #24
    // 24: current := waiting;
    t2.8:int64 = loadVariable v2.2#1:int64 #25
    storeVariable t2.8:int64, v2.1#2:int64 #26
    // 25: waiting := previous;
    storeVariable t2.7:int64, v2.2#2:int64 #27

Forwarding has removed previous altogether: waiting := previous stores t2.7, the load of the old current. This is exactly the shape in which the textbook’s naive copies swap wrongly. In Mica nothing can go wrong: the φ for current still joins only versions of current, the φ for waiting only versions of waiting, and both old values sit in the temporaries t2.7 and t2.8 before either store happens. The same lines after leaving SSA, in build/O1/export/Swaps.100.out-of-ssa:

@l2.4:
    // 21: while turn < turns do
    t2.4:int64 = loadVariable v2.4:int64 #18
    t2.5:int64 = loadVariable p2.1:int64 #19
    t2.6:bool = less t2.4:int64, t2.5:int64 #20
    jumpNotEqual t2.6:bool, @l2.5
    // 23: previous := current;
    t2.7:int64 = loadVariable v2.1:int64 #21
    // 24: current := waiting;
    t2.8:int64 = loadVariable v2.2:int64 #22
    storeVariable t2.8:int64, v2.1:int64 #23
    // 25: waiting := previous;
    storeVariable t2.7:int64, v2.2:int64 #24

The φ lines are gone, the versions are gone, and nothing else changed. The value ids count afresh, because the program after leaving SSA is a new unit of its own.

The lost copy, in Mica

LastCounted reads, after its loop, the value x had before the last round raised it. At O1, in build/O1/export/Swaps.090.ssa:

@l3.2:
    v3.1#1:int64 = phi 7: v3.1#0:int64, 9: v3.1#2:int64 #36
    // 40: last := x;
    t3.2:int64 = loadVariable v3.1#1:int64 #37
    // 41: x := x + 1;
    t3.4:int64 = copyLiteral 1:int64 #38
    t3.5:int64 = add t3.2:int64, t3.4:int64 <@l3.6, @l3.7, @l3.8> #39
    storeVariable t3.5:int64, v3.1#2:int64 #40
@l3.3:
    // 42: until x > limit;
    t3.7:int64 = loadVariable p3.1#0:int64 #41
    t3.8:bool = greater t3.5:int64, t3.7:int64 #42
    jumpNotEqual t3.8:bool, @l3.2
@l3.4:
    // 44: LastCounted := last;
    storeVariable t3.2:int64, v3.3#0:int64 #43

last is gone too: its store was forwarded, and then nothing read it. The old value of x lives in the temporary t3.2, from the load at the top of the round to the store after the loop. The versions of x never overlap: v3.1#1 is read for the last time by that load, and v3.1#2 is written after it. So x keeps one home, and the value the textbook’s copy could lose was never in that home: it sits in t3.2.

After SSA

The program that leaves the form is plain Spectra again, read by the rest of the compiler exactly as the debug tier reads the generator’s program. The next stage, placement, gives every variable and temporary that remains a register or a stack slot; Mica allocates its registers on the program after leaving SSA. Two small passes also run on it, where no φ function is left to disturb them: at O1 and O2 the jumps to the very next block are removed, and at O2 every loop whose test stands at the top is rotated so that the test stands at the bottom, and a round ends with one conditional jump back instead of a jump up to the test.

Try it

Export the program at O2, the tier with full optimizations, and look for the rotated loops in the program after leaving SSA:

@l4.9.rotated:
    jumpEqual t4.12:bool, @l4.9.rotated

@l4.9.rotated: is a label made for the top of the loop’s body, and the jumpEqual at the bottom jumps back to it while the test holds. The names changed: at O2 both routines are copied into the program body, each copy under a block number of its own, so this loop is PlayerAfter’s, numbered 4. LastCounted’s repeat loop has its test at the bottom already, so it has nothing to rotate. Open build/O2/export/Swaps.090.ssa beside it: the form has no rotated label, because the rotation happened after the form was left.

What you have seen

Six files told the whole story. 040.spectra is the program as first translated, and 080.reaching-definitions the question every optimization asks of it. 055.cfg-before-ssa and 060.dominance are the graph and the dominator tree the form is built on. 090.ssa is the form itself, with its φ functions at the iterated dominance frontiers and its versions from one walk over the dominator tree, and, at O1 and O2, after the optimizations that one definition per name makes simple. 100.out-of-ssa is the program back in plain form, by renaming alone. Export any program of your own the same way, and every one of these files is there to read.

The program#

The textbook way out, and its two traps#

How Mica leaves SSA#

The swap, in Mica#

The lost copy, in Mica#

After SSA#

Try it#

What you have seen#

Further reading#