78. Building SSA

SSA without a second pass

Last chapter you renamed a program into SSA by hand, looking at the whole CFG at once. A compiler that works that way needs the finished CFG first, in some non-SSA form, and then a second pass to rename everything and place phis.

VIR’s builder doesn’t do that. Like chapter 48’s single-pass compiler, it emits instructions as it walks the syntax tree, and the IR comes out in SSA form directly. There is no intermediate version with mutable variables. The trick is to treat “what is the value of x here?” as a question a block can answer, or pass on.

Each block keeps a notepad

Inside one block, SSA is just a table. Writing x records which value it now holds; reading looks it up. From builder.ts:

writeVariable(v, block, value) {
  let m = this.defs.get(block);
  if (!m) this.defs.set(block,
    (m = new Map()));
  m.set(v, value);
}
readVariable(v, block) {
  const local =
    this.defs.get(block)?.get(v);
  if (local !== undefined) return local;
  return this.readVariableRecursive(
    v, block);
}

v is any key the front end chooses for a variable, and defs maps a block to its table. An assignment never emits an instruction. It only writes into the table. That’s why x = 2 shows up in VIR as nothing more than a const 2.

Asking the predecessors

When a block has no entry for v, readVariableRecursive asks the blocks that lead to it. Simplified:

if (!this.sealed.has(block)) {
  val = incompletePhi(v, block);
} else if (b.preds.length === 1) {
  val = this.readVariable(
    v, b.preds[0]);
} else if (b.preds.length === 0) {
  val = undefinedConst();
} else {
  const phi = this.newPhi(block);
  this.writeVariable(v, block, phi.id);
  val = this.addPhiOperands(v, phi);
}
this.writeVariable(v, block, val);

• One predecessor: the answer is whatever it is there.
• No predecessors: the variable was read before any write. It’s undefined.
• Several: make a phi, record it first, then read v in every predecessor to get its operands. Recording it first matters in loops: if the search comes back round to this block, it finds the phi and stops, instead of searching forever.

The last line caches the answer, so the next read in this block is a plain look-up.

Loops: promise now, pay later

A loop header is entered from before the loop and from the end of the body. When the builder lowers the loop test, it hasn’t lowered the body yet, so the back edge doesn’t exist. The header’s list of predecessors is incomplete.

Braun and colleagues call a block sealed once all its predecessors are known^[1]. Reading a variable in an unsealed block creates an empty, incomplete phi and remembers it. Sealing the block fills in every incomplete phi:

seal(block) {
  const inc = this.incomplete.get(block);
  if (inc) {
    for (const [v, phi] of inc)
      this.addPhiOperands(v, phi);
    this.incomplete.delete(block);
  }
  this.sealed.add(block);
}

The front end decides when. For a loop, lower.ts seals the header right after it emits the back edge:

fb.br(head.id); // the back edge
fb.seal(head.id);

Step through the real sum function. A dashed block is unsealed:

function sum(n) {
  let s = 0;
  for (let i = 0; i < n; i++) {
    s = s + i;
  }
  return s;
}

Trivial phis

Look again at step 8. The header asked “what is n?” and got a phi, because it couldn’t know yet that the loop never changes n. Once sealed, the phi was %4 = φ(%0, %4). Whichever edge you take, it is %0. A phi whose operands are all one value, or the phi itself, is trivial:

let same = null;
for (const op of phi.args) {
  if (op === same || op === phi.id)
    continue;
  if (same !== null) return phi.id;
  same = op; // first other value
}
// replace every use of phi with same,
// then retry phis that used this phi

tryRemoveTrivialPhi rewires every use of the phi (including branch conditions and returns, and the definition tables) to same, and deletes the phi. Removing one phi can make another phi trivial, so it retries every phi that used it.

You can see the removals in real VIR. The ids jump: %4 is missing from sum, and here %5 is missing:

function f(c) {
  let x = 1; let y = 5;
  if (c) { x = 2; }
  return x + y;
}

  b3:  ; preds b1 b2
    %4 = phi %3, %1
    %6 = binop + %4, %2
    return %6

Reading y at the join made %5 = φ(%2, %2). Both edges agree, so it was replaced by %2. In the module’s list of values, instruction 5 is left behind as a dead entry noted removed-trivial-phi.

// Returns the one value the phi always
// means, or null if it really merges.
function trivial(id, args) {
  let same = null;
  for (const op of args) {
    if (op === same || op === id) {
      continue;
    }
    if (same !== null) return null;
    same = op;
  }
  return same;
}
const t = trivial;
console.log(t('%5', ['%2', '%2']));
console.log(t('%4', ['%0', '%4']));
console.log(t('%3', ['%2', '%10']));

The other way: dominance frontiers

The classic algorithm, from Cytron and colleagues in 1991^[4], works on a finished CFG. For a definition of x in block B, follow the dominator tree (chapter 76): the blocks where B’s dominance stops, the first ones B does not strictly dominate, are its dominance frontier. Those are exactly the joins where a path from B meets a path that avoids it, so that’s where x needs phis. Each new phi is itself a definition of x, so its block’s frontier gets phis too, until no more are added. A second walk over the dominator tree then renames every use.

LLVM’s mem2reg pass does this. It places phis “using dominator frontiers”, then rewrites loads and stores in a depth-first walk^[2]. Braun’s method needs no dominator tree and works while the IR is still being made, which suits a front end that lowers straight from a syntax tree.

Your turn

// phis: { id: [operand, ...] }
// Return { id: replacement } for
// every phi (its own id if it stays).
function removeTrivial(phis) {
  const out = {};
  for (const p in phis) out[p] = p;
  return out;
}

// preds: { block: [pred, ...] }
// defs: { block: { name: value } }
function readVar(v, b, preds, defs) {
  return defs[b][v];
}

What you learned

• On-the-fly SSA construction keeps a table of definitions per block. Assignments only write into it.
• readVariable looks locally, then asks predecessors: one predecessor passes the question on; several make a phi, recorded first so loops terminate.
• An unsealed block (a loop header, before its back edge) gets incomplete phis. seal fills them in.
• A trivial phi chooses only one value (or itself). It is replaced, and phis that used it are retried.
• The dominance-frontier algorithm places phis on a finished CFG instead; LLVM’s mem2reg uses it.

Next: what you can compute once a program is in SSA, starting with facts that flow round loops.