SSA gives every write of a variable its own version, and a φ function picks a version where paths with different versions meet. This chapter answers the first half of the construction: which blocks get a φ, and for which variables. The next chapter fills in the versions.

The program

This chapter reads Evens.mica from chapter 2, as you saved it there. Export it again at the debug tier, so the files match the program:

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 routine, to keep in view:

function CountEven(limit : int64) : int64;
var
    count, k, last : int64;
begin
    count := 0;
    last := 0;
    k := 1;

    while k ≤ limit do
    begin
        if k mod 2 = 0 then
        begin
            count := count + 1;
            last := k;
        end;

        k := k + 1;
    end;

    CountEven := count;
end;

And its blocks, from the last chapter: block 2 is the entry, block 3 the loop’s test, block 4 the decision, block 5 the then arm, block 6 the merge that raises k, and block 7 the code after the loop.

Where two versions can meet

Take one variable and a block that writes it. Every block that this block dominates is reached only through it, so the version it wrote is the one that arrives there, until the next write of the same variable. A different version can come in only where that dominance ends: in the block’s dominance frontier. That is the whole argument, and it is the discovery of Cytron, Ferrante, Rosen, Wegman and Zadeck, who first built SSA this way: a variable needs a φ in the dominance frontier of every block that writes it.

A φ is itself a write of the variable: it makes a new version. So the blocks that received a φ have frontiers of their own where that new version can meet another one, and they need a φ too. The placement repeats until no new block joins. The result is called the iterated dominance frontier of the blocks that write the variable.

Placing them by hand

The frontiers, from Evens.060.dominance:

  block 2 idom=- rpo=0 children=[3] df=[]
  block 3 idom=2 rpo=1 children=[4 7] df=[3]
  block 4 idom=3 rpo=2 children=[5 6] df=[3]
  block 5 idom=4 rpo=3 children=[] df=[6]
  block 6 idom=4 rpo=4 children=[] df=[3]

Work through the variables of CountEven:

  • count is written in block 2 (count := 0) and block 5 (count := count + 1). The frontier of block 2 is empty, the frontier of block 5 is block 6: a φ for count goes into block 6. That φ is a new write in block 6, whose frontier is block 3: a φ goes into block 3. Block 3’s frontier is block 3 itself, which already has one. Done: blocks 6 and 3.
  • k is written in block 2 and block 6 (k := k + 1). Block 6’s frontier is block 3, and block 3 adds nothing new. Done: block 3.
  • last is written in block 2 and block 5, exactly like count. By the same steps it needs φ functions in blocks 6 and 3.
  • CountEven, the result, is written only in block 7, whose frontier is empty. No φ.

Now look at what the compiler placed. Every φ stands right after the label of its block:

grep -e phi build/debug/export/Evens.090.ssa
    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
    v2.1#3:int64 = phi 4: v2.1#1:int64, 5: v2.1#2:int64 #29

count (v2.1) has two φ functions, one at the loop’s test, whose inputs come from blocks 2 and 6, and one at the merge, whose inputs come from blocks 4 and 5. k (v2.2) has one, at the loop’s test. Each input of a φ is tagged with the predecessor it belongs to, and a φ has one input for each predecessor of its block.

And last (v2.3) has none.

A φ only where the variable is live

Nothing ever reads last. A φ for it would pick a version that no instruction will ever look at, so the compiler leaves it out. The rule that decides is liveness: a variable is live at a point of the program when some path from that point reads it before writing it again. A φ is kept only in a block where its variable is live on entry. SSA built this way is called pruned SSA; Choi, Cytron and Ferrante proposed it, and it is the form Mica builds.

The export holds the liveness too. The last lines of Evens.070.liveness list, for every block, the names live at its end:

live_out[2]: [p2.1 v2.1 v2.2]
live_out[3]: [p2.1 v2.1 v2.2]
live_out[4]: [p2.1 v2.1 v2.2]
live_out[5]: [p2.1 v2.1 v2.2]
live_out[6]: [p2.1 v2.1 v2.2]
live_out[7]: [v2.4]

limit (p2.1), count and k are live all through the loop. last (v2.3) is live nowhere, so neither of its frontier blocks keeps a φ.

Which names get versions

Mica gives versions to the local variables and parameters of a routine that the routine writes only as a whole, by a plain store, whose address is never taken, and that no other routine reaches. Everything else keeps its plain name in the SSA listing: an array written element by element, a variable another routine nested inside this one also uses, and every temporary, which the compiler already writes exactly once. A self-check proves the choice before any name is versioned.

Try it

Make the function answer with the last even number instead of the count: change its last line to CountEven := last;. Now last is read after the loop, so it is live wherever its value can still travel there. Export again and look for the φ functions:

    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
    v2.3#1:int64 = phi 2: v2.3#0:int64, 6: v2.3#3:int64 #15
    v2.1#3:int64 = phi 4: v2.1#1:int64, 5: v2.1#2:int64 #30
    v2.3#3:int64 = phi 4: v2.3#1:int64, 5: v2.3#2:int64 #31

last received exactly the φ functions you placed by hand for it, in blocks 3 and 6. count kept both of its own: it is still read inside the loop, by count := count + 1. Undo the edit before you go on.

Next: Renaming.