1 — The question SSA answers

An optimizer spends most of its time asking one question about the program in front of it: when this instruction reads a variable, which instruction wrote the value it reads? If the answer is “the line three above, which wrote the constant 6”, the read can be replaced by the 6. If the answer is “one of two lines, depending on a decision”, it cannot. Every improvement a compiler makes to your code starts with that question answered.

This chapter asks the question of a small program twice: first the way compilers answered it before SSA, and then the way SSA answers it.

The lab

Make a folder for the series and work in it:

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

Save this as TwoWrites.mica:

{
    TwoWrites - the larger of two numbers, chosen by one decision.

    Each arm of the decision writes the variable 'larger', and the one read of it below the decision can see either
    write: the smallest program in which one use of a variable has two definitions.
}
program TwoWrites;

imp
    WriteLn : std;

{ The larger of two numbers is written into 'larger' by whichever arm of the decision runs. }
function Larger(a, b : int64) : int64;
var
    larger : int64;
begin
    if a > b then
        larger := a
    else
        larger := b;

    Larger := larger;
end;

begin
    WriteLn("the larger of 3 and 4 is %lld", Larger(3, 4));
    WriteLn("the larger of 9 and 2 is %lld", Larger(9, 2));
end.

Run it once, to see that it works:

mica TwoWrites.mica

the larger of 3 and 4 is 4
the larger of 9 and 2 is 9

Then compile it with --export, which writes every stage of the compilation into the folder export of the build directory. --optimize debug asks for the tier that does not optimize, so you see the program as it was first translated:

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

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

The folder holds one file per stage, numbered in the order the compiler works. This series reads six of them; this chapter reads three.

The intermediate code

A compiler does not optimize your source text. It first translates it into an intermediate language: a flat list of small instructions, each doing one thing, with at most two inputs and one result. That shape is called three-address code. Mica’s intermediate language is called Spectra, and the file TwoWrites.040.spectra is the program in it. The function Larger:

@TwoWrites.Larger:
    // 16: begin
    prologue @TwoWrites.Larger, 1
    // 17: if a > b then
    t2.1:int64 = loadVariable p2.1:int64 #14
    t2.2:int64 = loadVariable p2.2:int64 #15
    t2.3:bool = greater t2.1:int64, t2.2:int64 #16
    jumpNotEqual t2.3:bool, @l2.1
    // 18: larger := a
    t2.4:int64 = loadVariable p2.1:int64 #17
    storeVariable t2.4:int64, v2.1:int64 #18
    // 17: if a > b then
    jump @l2.2
@l2.1:
    // 20: larger := b;
    t2.5:int64 = loadVariable p2.2:int64 #19
    storeVariable t2.5:int64, v2.1:int64 #20
@l2.2:
    // 22: Larger := larger;
    t2.6:int64 = loadVariable v2.1:int64 #21
    storeVariable t2.6:int64, v2.2:int64 #22
@TwoWrites.Larger_leave:
    // 23: end;
    loadReturnVariable @TwoWrites.Larger, v2.2:int64 #23
    epilogue @TwoWrites.Larger

Read each line left to right. t2.4:int64 = loadVariable p2.1:int64 #17 says: read the parameter p2.1 into a new temporary t2.4, of type int64. The tokens you need:

Two things matter for the rest of the series. Every temporary is written exactly once. The variable larger, v2.1, is written twice: by the store #18 in the then arm and by the store #20 in the else arm. And the read #21, below the decision, could see either.

The question, answered without SSA

Before SSA, compilers answered the question with an analysis called reaching definitions. A definition is an instruction that writes a variable. A definition reaches a read when some path through the program goes from the definition to the read without passing another write of the same variable. The analysis computes, for every read, the set of definitions that reach it.

Mica computes this analysis when you export, and writes it to TwoWrites.080.reaching-definitions, one line per read. The line for the read of larger:

value-id=21 token=41 "t2.6:int64 = loadVariable v2.1:int64 #21" -> v2.1 = [18 20]

The read #21 of v2.1 may see the value written by #18 or the value written by #20. That is the honest answer: which one depends on a > b, which the compiler cannot know.

The temporaries have one definition each, so their lines are short. The store into larger in the then arm reads t2.4, and only one instruction ever writes t2.4:

value-id=18 token=31 "storeVariable t2.4:int64, v2.1:int64 #18" -> t2.4 = [17]

The reads of the parameters a and b have no line at all: their values were written by the caller, by no instruction of this program, so there is no value id to list.

This is how the question is answered without SSA: a set per read, computed over the whole routine, where every new write of a variable kills the facts about the writes before it. It works, but every optimization has to carry these sets around, and every change to the program can invalidate them.

The question, answered by SSA

Static single assignment form rewrites the program so that the question disappears. Every write of a variable creates a new version of it, with a name of its own. Every read names the one version it sees. Where two paths that carry different versions meet, a new kind of instruction, the φ function (written phi in the listings), picks the version that belongs to the path control actually came along.

The same export holds the SSA form of the program, TwoWrites.090.ssa. The part below the if:

    // 18: larger := a
    t2.4:int64 = loadVariable p2.1#0:int64 #17
    storeVariable t2.4:int64, v2.1#0:int64 #18
    // 17: if a > b then
    jump @l2.2
@l2.1:
    // 20: larger := b;
    t2.5:int64 = loadVariable p2.2#0:int64 #19
    storeVariable t2.5:int64, v2.1#1:int64 #20
@l2.2:
    v2.1#2:int64 = phi 3: v2.1#0:int64, 4: v2.1#1:int64 #21
    // 22: Larger := larger;
    t2.6:int64 = loadVariable v2.1#2:int64 #22

A # written right after a name, with no space, is a version: v2.1#0 is version 0 of larger. The # after a space at the end of a line is still the value id. Read it like this:

• The then arm writes version 0 of larger, v2.1#0.
• The else arm writes version 1, v2.1#1.
• Where the arms meet, at @l2.2, the φ function defines version 2: v2.1#2 is v2.1#0 when control came from block 3, and v2.1#1 when it came from block 4. Blocks 3 and 4 are the two arms; the next chapter shows where those numbers come from.
• The read below the decision reads v2.1#2, and nothing else.
• The parameters are read as p2.1#0 and p2.2#0: version 0 of a parameter is the value the caller passed.

Now ask the question again. Which write does the read of v2.1#2 see? The one that defines v2.1#2. There is exactly one, because every version is written in exactly one place: that is the “single assignment”. It is “static” because it holds in the program text; a version inside a loop is still written many times while the program runs.

The set of the reaching-definitions file became a name. An optimization that wants to know where a value came from no longer runs an analysis: it looks the name up.

Try it

Give larger a starting value before the decision. Add the line larger := 0; in front of the if:

begin
    larger := 0;

    if a > b then
        larger := a
    else
        larger := b;

    Larger := larger;
end;

Export again, and look for the read of larger in the reaching definitions and for the versions of larger in the SSA form:

value-id=23 token=45 "t2.7:int64 = loadVariable v2.1:int64 #23" -> v2.1 = [20 22]
    storeVariable t2.1:int64, v2.1#0:int64 #15
    storeVariable t2.5:int64, v2.1#1:int64 #20
    storeVariable t2.6:int64, v2.1#2:int64 #22
    v2.1#3:int64 = phi 3: v2.1#1:int64, 4: v2.1#2:int64 #23
    t2.7:int64 = loadVariable v2.1#3:int64 #24

The read still sees two definitions, not three: both arms write larger, so the 0 can never reach the read, and the analysis says so by leaving it out. In the SSA form the 0 became version 0, the arms versions 1 and 2, and the φ still joins only the two versions that arrive at the merge.

Now the question is how the compiler decides where a φ goes and which version each read names. Both answers stand on one structure, the dominator tree, which the next chapter builds.

Next: The graph and its dominators.