77. SSA form

Which x is this?

Here are four lines of three-address code:

x = a + 1;
x = x * 2;
y = x + 3;
x = 0;

Suppose an optimizer wants to know something about the x in line 3. Is it a number? Is it a constant? Is it still needed later? Before it can answer, it has to work out which assignment to x it is looking at. Here it is line 2, but finding that out meant scanning backwards and noticing that line 2 overwrote line 1. With branches and loops, the scan turns into a search over the whole CFG, and every analysis would have to repeat it.

The trouble is that one name, x, stands for three different values over time. So stop doing that.

One name per value

Give every assignment a fresh version of the name, and make every use refer to the latest version:

x1 = a0 + 1;
x2 = x1 * 2;
y1 = x2 + 3;
x3 = 0;

Now line 3 says x2, and x2 has exactly one definition. No scanning. a0 is version 0: a value that came in from outside, such as a parameter.

Where paths meet

Straight-line code is easy, because there is always exactly one latest version. Branches break that:

x = a + 1;
if (x > 5) {
  x = x * 2;
} else {
  x = 0;
}
y = x + 3;

Rename both branches and you get x2 on the left and x3 on the right. The block after the if has two predecessors, and they disagree. No single name can go in y = ? + 3, because the right answer depends on which way the program went.

SSA’s answer is a new kind of instruction at the start of the join block: x4 = φ(x2, x3). Step through the renaming:

All the phis at the top of a block take their values at the same moment, as control crosses the edge. None of them sees another one’s new value. The extra exercise shows why that matters.

function f(a0) {
  const x1 = a0 + 1;
  let x2, x3, from;
  if (x1 > 5) {
    x2 = x1 * 2;
    from = 'B1';
  } else {
    x3 = 0;
    from = 'B2';
  }
  // x4 = φ(x2, x3): pick by edge
  const x4 = from === 'B1' ? x2 : x3;
  return x4 + 3;
}
console.log(f(9), f(1));

Phis in real VIR

Viscosity’s IR, VIR, is in SSA form. Here is the if program written as a function, lowered by the real front end and printed with printFunc:

function f(c) {
  let x;
  if (c) { x = 1; } else { x = 2; }
  return x * 10;
}

func f(%0):
  b0:
    %0 = param
    %1 = const undefined
    condbr %0, b1, b2
  b1:  ; preds b0
    %2 = const 1
    br b3
  b2:  ; preds b0
    %3 = const 2
    br b3
  b3:  ; preds b1 b2
    %4 = phi %2, %3
    %5 = const 10
    %6 = binop * %4, %5
    return %6

There are no variable names in it at all. In VIR an SSA value is the instruction that defines it: %4 means “the result of instruction 4”. Because an instruction is written once, the value is assigned once. %4 = phi %2, %3 lists its operands in the order of the preds comment: %2 if control came from b1, %3 if from b2.

Loops need phis too, at the loop header, where the entry edge and the back edge meet. Here is the header of function sum(n), whose body is let s = 0; for (let i = 0; i < n; i++) s = s + i; return s;:

  b1:  ; preds b0 b3
    %6 = phi %1, %7
    %3 = phi %2, %10
    %5 = binop < %3, %0
    condbr %5, b2, b4

%3 is i: %2 (the 0) on the first entry from b0, and %10 (i + 1) each time round the back edge from b3. The operand %10 is defined later in the listing. That is fine: it is only read when control arrives from b3, and by then b3 has run.

What SSA buys

With one definition per value, the questions from the start become look-ups:

• Where is this value defined? It is the instruction itself.
• Is it a constant? If %1 = const 0, every use of %1 is 0. No later assignment can change it, because there are none.
• Where is it defined, relative to its uses? The definition dominates every ordinary use (chapter 76). A phi operand only has to be available at the end of the matching predecessor.

Not everything fits. A local that a closure captures can be changed by another function, at a moment the CFG cannot see (chapters 41 and 57). VIR keeps those as bindings, read and written with load and store. So do locals assigned inside a try, and arrays, which the layout analyses of Part VII track by binding. Every other simple local becomes SSA values.

Your turn

// code: [[dst, op, a, b], ...]
// a and b are names or numbers.
function toSSA(code) {
  // your code here
}

// phis: [[dst, [op0, op1, ...]], ...]
// env: name -> value. k: the edge.
function enter(phis, env, k) {
  return env;
}

What you learned

• In SSA form every variable is assigned in exactly one place in the text, so every use points at exactly one definition.
• Renaming straight-line code: each assignment makes a new version; each use takes the latest version, read before the assignment on the same line.
• A phi node at the start of a join block picks one operand per incoming edge. All of a block’s phis take their values at once.
• In VIR, a value is its defining instruction (%4). Loop headers have phis whose second operand arrives on the back edge.
• Captured variables stay out of SSA, as bindings with load and store.

Next: how VIR’s builder creates all of this while it lowers, in one pass.