Compilers build SSA in order to optimize on it. This chapter shows four optimizations Mica runs on the form, each on a routine of three lines, and the one fact that makes every one of them simple.

The program

Save this as Folds.mica in the lab folder:

mkdir -p ssa-lab && cd ssa-lab
{
    Folds - three small routines, each a chance for one optimization that static single assignment form makes easy.

    'Area' multiplies two variables that only ever hold constants, 'SquareOfSum' computes the same sum twice, and
    'Report' tests a switch that is off on every run, so the code behind it can never run.
}
program Folds;

imp
    WriteLn : std;

{ The area of a fixed rectangle is computed through two variables. }
function Area() : int64;
var
    width, height : int64;
begin
    width := 6;
    height := 7;
    Area := width × height;
end;

{ The square of a sum is written the long way, so the sum is computed twice. }
function SquareOfSum(a, b : int64) : int64;
begin
    SquareOfSum := (a + b) × (a + b);
end;

{ A count is raised by one, and by a hundred more when a switch is on that no run ever turns on. }
function Report(count : int64) : int64;
var
    verbose : bool;
begin
    verbose := False;

    if verbose then
        count := count + 100;

    Report := count + 1;
end;

begin
    WriteLn("the rectangle covers %lld squares", Area());
    WriteLn("the square of 3 + 4 is %lld", SquareOfSum(3, 4));
    WriteLn("the report counts %lld", Report(41));
end.

Run it, then export it twice: at the debug tier, which builds the SSA form and leaves it untouched, and at O1, the release tier with the standard optimizations, which optimizes the form before it leaves it:

mica Folds.mica
mica --compile --optimize debug --platform linux,amd64,utf-8 --source Folds.mica --build build/debug --export
mica --compile --optimize O1 --platform linux,amd64,utf-8 --source Folds.mica --build build/O1 --export
the rectangle covers 42 squares
the square of 3 + 4 is 49
the report counts 42
Exporting intermediate representations of source 'Folds.mica' to 'build/debug/export'
Exporting intermediate representations of source 'Folds.mica' to 'build/O1/export'

The listings below come from build/debug/export/Folds.090.ssa, the form before the optimizations, and from build/O1/export/Folds.090.ssa, the form after them; each says which. O2, the tier with full optimizations, also copies small routines into their callers, which would hide the routines this chapter reads; O1 keeps every routine whole.

The fact behind every pass

After renaming, every versioned name has exactly one definition, and so does almost every temporary. So whatever a pass learns about a name, “it holds the constant 6” or “it is the sum of a and b”, is true wherever the name is used. Without SSA, such a fact holds only until the next write of the variable, and every pass would have to find out where that is. With SSA, the fact belongs to the name, and the name is never written again.

Forwarding

The intermediate code writes every value into its variable and loads it back at every read. Area before the optimizations:

@Folds.Area:
    // 16: begin
    prologue @Folds.Area, 1
    // 17: width := 6;
    t2.1:int64 = copyLiteral 6:int64 #17
    storeVariable t2.1:int64, v2.1#0:int64 #18
    // 18: height := 7;
    t2.2:int64 = copyLiteral 7:int64 #19
    storeVariable t2.2:int64, v2.2#0:int64 #20
    // 19: Area := width × height;
    t2.3:int64 = loadVariable v2.1#0:int64 #21
    t2.4:int64 = loadVariable v2.2#0:int64 #22
    t2.5:int64 = multiply t2.3:int64, t2.4:int64 <@l2.3, @l2.4, @l2.5> #23
    storeVariable t2.5:int64, v2.3#0:int64 #24

The load t2.3 reads v2.1#0 (width), and exactly one instruction writes v2.1#0: the store of t2.1. So t2.3 is t2.1, and every use of t2.3 can read t2.1 instead. That is store-to-load forwarding, Mica’s form of what the textbooks call copy propagation. Its sister, load-to-load forwarding, handles a version no store writes, a φ or a parameter: a second load of it reads the same value as an earlier load in a block that dominates it.

Without SSA, the compiler would have to prove that no other write of width can happen between the store and the load, on any path. With SSA, the proof is the name: a write in between would have made a new version.

Constant folding

After forwarding, the multiplication reads t2.1 and t2.2, and each of those is defined by one copyLiteral, so each holds its literal wherever it is read. A computation whose inputs are all literals can be done by the compiler: that is constant folding, and carrying the constants to the places that read them, as forwarding just did, is constant propagation. Area after the optimizations:

@Folds.Area:
    // 16: begin
    prologue @Folds.Area, 1
    // 19: Area := width × height;
    t2.5:int64 = copyLiteral 42:int64 #17
    storeVariable t2.5:int64, v2.3#0:int64 #18

The multiplication became the literal 42. Then the loads, the stores into width and height, and the literals 6 and 7 had no reader left. An instruction whose result nobody reads, and that does nothing else, is dead code, and it was removed: width and height are gone from the program. Mica does the arithmetic of a fold exactly as the program would at run time, and a computation that would overflow or fault is left in place, to do at run time exactly what it would have done.

Value numbering

SquareOfSum computes a + b twice. Before the optimizations:

    // 25: SquareOfSum := (a + b) × (a + b);
    t3.1:int64 = loadVariable p3.1#0:int64 #26
    t3.2:int64 = loadVariable p3.2#0:int64 #27
    t3.3:int64 = add t3.1:int64, t3.2:int64 <@l3.1, @l3.2, @l3.3> #28
    t3.4:int64 = loadVariable p3.1#0:int64 #29
    t3.5:int64 = loadVariable p3.2#0:int64 #30
    t3.6:int64 = add t3.4:int64, t3.5:int64 <@l3.4, @l3.5, @l3.6> #31
    t3.7:int64 = multiply t3.3:int64, t3.6:int64 <@l3.7, @l3.8, @l3.9> #32

After them:

    // 25: SquareOfSum := (a + b) × (a + b);
    t3.1:int64 = loadVariable p3.1#0:int64 #20
    t3.2:int64 = loadVariable p3.2#0:int64 #21
    t3.3:int64 = add t3.1:int64, t3.2:int64 <@l3.1, @l3.2, @l3.3> #22
    t3.7:int64 = multiply t3.3:int64, t3.3:int64 <@l3.7, @l3.8, @l3.9> #23

Two passes worked here. Load-to-load forwarding made the second pair of loads read t3.1 and t3.2, so the second add had exactly the inputs of the first. Value numbering then gave every computation a key, its operation and its input names, and found the second add with the key of an earlier one in a block that dominates it. The second reads the first’s result instead, and the multiplication squares t3.3.

In SSA, “the same inputs” is a comparison of names, because a name has one value. Without SSA, two reads of a could see two different writes of it, and equal names would prove nothing.

Dead code behind a constant branch

Report tests a variable that is False on every run. After the optimizations:

@Folds.Report:
    // 32: begin
    prologue @Folds.Report, 1
    // 35: if verbose then
    jump @l4.2
    // 36: count := count + 100;
    t4.3:int64 = loadVariable p4.1#0:int64 #26
    t4.4:int64 = copyLiteral 100:int64 #27
    t4.5:int64 = add t4.3:int64, t4.4:int64 <@l4.4, @l4.5, @l4.6> #28
    storeVariable t4.5:int64, p4.1#1:int64 #29
@l4.2:
    p4.1#2:int64 = phi 6: p4.1#0:int64, 7: p4.1#1:int64 #30

Forwarding turned the test into a test of a literal, and folding knows its answer. Branch resolution replaced the conditional jump by the one jump that can happen, so the block that adds 100 can no longer be reached. The form keeps that block until it is left, together with its input to the φ; the next chapter’s file, 100.out-of-ssa, no longer has it. A block nothing reaches is dead code too.

The ledger

Every export writes 130.optimization, in which each pass counts what it did. The part about the SSA form, in build/O1/export/Folds.130.optimization:

Static-single-assignment optimization statistics for source 'Folds.mica'
  Store-to-load forwards: 3
  Load-to-load forwards: 2
  Dead loads eliminated: 5
  Dead stores eliminated: 3
  Constants folded: 1
  Arithmetic constants folded: 1
  Dead literals eliminated: 3
  Constant branches resolved: 1
  Dead blocks eliminated: 1
  Redundant jumps eliminated: 1
  Redundant computations numbered: 1

The counts cover the whole program, its body included. Redundant jumps eliminated belongs to a small clean-up that runs after the form is left: it removes a jump to the very next block, here the jump branch resolution left in Report.

The passes Mica runs

The four optimizations of this chapter are the first of a longer row. Among the passes Mica runs on the form at O1 and O2, in their order, are forwarding, constant folding, the scalar replacement of small local arrays whose every access has a constant index, value numbering, the removal of a bounds check or a nil check that a dominating check already made, branch resolution, the value ranges, which give every value the interval it provably lies in and drop the guards those intervals make needless, the use of a constant array index as a literal, and the removal of code behind an instruction that always fails. O2 adds two loop passes: moving what is the same in every round in front of the loop, and strength reduction, which turns a multiplication by the loop’s counter into an addition per round. After the passes, the form is verified again, as the last chapter described.

The textbooks often combine constant propagation and branch resolution in one analysis, sparse conditional constant propagation, which also carries constants through φ functions. Mica keeps them apart: it folds first, over the temporaries with one definition, and resolves branches in a pass of its own after that.

Try it

Value numbering compares the inputs of +, × and = in a fixed order, so that a + b and b + a get the same key. Write the second sum the other way round, (a + b) × (b + a), export at O1 again, and look at SquareOfSum:

build/try/export/Folds.090.ssa:    t3.1:int64 = loadVariable p3.1#0:int64 #20
build/try/export/Folds.090.ssa:    t3.2:int64 = loadVariable p3.2#0:int64 #21
build/try/export/Folds.090.ssa:    t3.3:int64 = add t3.1:int64, t3.2:int64 <@l3.1, @l3.2, @l3.3> #22
build/try/export/Folds.090.ssa:    t3.7:int64 = multiply t3.3:int64, t3.3:int64 <@l3.7, @l3.8, @l3.9> #23
build/try/export/Folds.130.optimization:  Redundant computations numbered: 1

The sum is still computed once. Then change verbose := False; to verbose := True; and export again: the branch is resolved the other way. This time the test and its jump disappear, and the addition stays, with nothing left to go around it. Undo both edits when you are done.

Next: Leaving SSA.