80. Constant folding and propagation

Work you could do in advance

const DAY = 60 * 60 * 24;
let k = 4;
let n = k * 2;
if (n > 5) { /* ... */ }

Every time this runs, the machine multiplies 60 by 60 by 24 and gets 86400. It multiplies 4 by 2 and gets 8, then checks whether 8 is more than 5. The answers never change. A compiler can work them out once, while compiling, and write the answers into the program instead.

Folding

In SSA it is one rule: if every operand of an instruction is a known constant, and the operation has no side effects and can’t throw, compute it now and replace the instruction with a const.

%1 = const 60
%2 = binop * %1, %1   →  %2 = const 3600

The catch: the compiler must get exactly the answer the program would have got at run time. In JavaScript that includes all of these:

console.log('1' + 2);
console.log(1 / 0);
console.log(0.1 + 0.2);
console.log(Object.is(0 * -1, -0));
console.log(2 ** 53 + 1);

'1' + 2 is a string. Dividing by zero is not an error. 0.1 + 0.2 has the rounding of a 64-bit float (chapter 22). -0 is a real value, and 2 ** 53 + 1 can’t be represented. A folder written in JavaScript gets these right for free by doing the same operation. A folder written in another language must copy JavaScript’s rules exactly, or it changes the program.

Propagation

Folding needs operands that are constants. After %2 = const 3600, any instruction using %2 now has a constant operand. In SSA that needs no checking at all: %2 is defined once, so every use of it is 3600. Replace each use with the constant, and fold whatever that makes foldable. Each fold can enable more folds further down.

%3 = const 24
%4 = binop * %2, %3   →  %4 = const 86400

Without SSA you’d need chapter 79’s reaching definitions first, to be sure no other assignment to the variable could reach the use.

Constants meet at phis

What about %6 = φ(%4, %5)? If both operands are 2, %6 is 2. If one is 2 and the other 3, %6 is not a constant. And inside a loop, an operand may not have been worked out yet. That gives a lattice with three levels:

• ⊤ (“top”): no information yet;
• a constant: 2, or 'hi', or true;
• ⊥ (“bottom”): varies, not a constant.

Merging ⊤ with anything gives the other thing. Merging two equal constants gives that constant. Anything else gives ⊥. Start every value at ⊤ and you have chapter 79’s optimistic analysis again. It is what finds x constant in a loop like this one, which never changes it:

b1:  ; loop header
  %5 = phi %1, %5   ; %1 = const 7

Optimistically, %5 starts at ⊤, so merging gives 7, and 7 is consistent. It is the trivial phi of chapter 78, seen by an analysis. A loop counter φ(0, i + 1) goes to ⊥: 0 merged with 1 varies.

Using the branches too

Plain propagation treats every block as reachable. But if a branch condition folds to true, the else side can never run, and its values should not count. Sparse conditional constant propagation (SCCP) tracks this with a second kind of fact: which CFG edges are executable. It starts optimistic about both. Every value is ⊤ and every block is unreachable until proven otherwise:

let x = 1;
let y;
if (x > 0) { y = 2; } else { y = 3; }
let z = y * 10;

SCCP keeps two worklists: SSA values whose lattice value changed (to revisit their users), and CFG edges that just became executable (to visit the block they lead to). A phi only merges operands arriving on executable edges. A branch on a constant marks only one edge. Plain propagation would merge 2 with 3 at the phi and say “varies”. SCCP proves z is 20, and that b2 is dead.

LLVM’s sccp pass is this algorithm. Its documentation sums it up as: assume values are constant and blocks dead unless proven otherwise, replace values proven constant, and turn branches proven to go one way into unconditional ones. It also notes that the pass leaves dead code behind for a later DCE pass^[1].

Your turn

// insts: [{ id, op, args, value }]
// op: 'const' | 'param' | 'add'
//   | 'sub' | 'mul'; args are ids
//   of earlier instructions.
const OPS = {
  add: (a, b) => a + b,
  sub: (a, b) => a - b,
  mul: (a, b) => a * b,
};
function fold(insts) {
  return insts;
}

const TOP = 'top';
const BOT = 'varies';
// a, b: TOP, BOT, or a constant.
function meet(a, b) {
  return a;
}

What you learned

• Constant folding computes an operation on constants at compile time. It must match run-time semantics exactly, quirks included, and must not fold anything with side effects or that can throw.
• Constant propagation replaces uses of a constant value with the constant. In SSA every use of a constant value is that constant. Folding and propagation feed each other until a fixpoint.
• At phis, constants merge in a three-level lattice: ⊤, a constant, ⊥. Starting at ⊤ is what lets loops keep their constants.
• SCCP is also optimistic about edges. Branches on constants make only one edge executable, and phis ignore the rest.

Next: deleting the code these passes just made useless.