79. Dataflow analysis

A question that depends on itself

Part VII’s compiler wants to store a field like x in a Float64Array column (chapter 23’s SoA). That is only safe if every value ever written to x is a number. So Viscosity has to answer, for every SSA value: is this always a number?

For most instructions the answer is easy. const 0 is a number. const "!" isn’t. But look at a loop’s running total, in the VIR from chapter 77:

  b1:  ; preds b0 b3
    %6 = phi %1, %7
  ...
  b2:  ; preds b1
    %7 = binop + %6, %3

%6 is a number if %1 and %7 are. %7 is a number if %6 and %3 are. Each answer waits on the other. You can’t compute them in order, because there is no order: the loop is a cycle.

Facts, rules and merges

An analysis like this has three parts:

• a fact about each value (here: number, or maybe not);
• a rule for each kind of instruction, computing its fact from its operands’ facts. From Viscosity’s analysis.ts:

case 'const':
  return typeof i.value === 'number';
case 'binop':
  return ARITH.has(i.operator) &&
    n(i.args[0]) && n(i.args[1]);
case 'phi':
  return i.args.every(n);

• a merge where paths meet. In SSA, the merge is the phi rule: a phi is a number only if every incoming value is.

A ladder of facts

The facts need an order, so that merging always has an answer. Here there are just two, with “number” above “maybe-not”. Merging two facts gives the lower one: if either side might not be a number, the result might not be either.

Real analyses use taller ladders. Next chapter’s constant analysis has three levels: “no information yet”, “the constant 4”, and “varies”.

Guess, check, repeat

To break the cycle, start with a guess and correct it. Which guess? Try starting everything at “maybe-not” (pessimistic):

// s = 0; loop: s = s + i (i: number)
// v2 = φ(v1, v3), v3 = v2 + i
function solve(start) {
  let v2 = start;
  let v3 = start;
  for (let r = 0; r < 5; r++) {
    v2 = true && v3; // φ(v1, v3)
    v3 = v2 && true; // v2 + i
  }
  return v2;
}
console.log('optimistic', solve(true));
console.log('pessimistic',
  solve(false));

Pessimistic gets stuck. %6 is maybe-not because %7 is; %7 is maybe-not because %6 is. That answer is consistent, but it’s useless. Starting optimistic, at “number”, the loop also stays consistent, and this time the answer is the useful one. Both are fixpoints: states where applying every rule again changes nothing. Optimism finds the best one, as long as you keep checking until the guesses stop being contradicted.

A worklist

Rerunning every rule until nothing changes is wasteful: most values didn’t change since the last round. Instead, keep a queue of values that might need updating. When a value’s fact changes, put its users on the queue.

The real thing in Viscosity

Viscosity’s numeric inference is exactly this optimistic analysis, over SSA values plus the bindings and collection fields that values flow through. It skips the worklist: each round, it reruns every rule, and it repeats rounds until a whole round changes nothing (with a cap of 1000 rounds, after which it gives up every guess: it fails closed). Simplified from analysis.ts:

for (const v of m.values)
  num.set(v.id, optimistic(v)
    ? true : compute(v));
for (let changed = true, rounds = 0;
     changed && rounds < 100;
     rounds++) {
  changed = false;
  for (const v of m.values) {
    const nv = compute(v);
    if (num.get(v.id) !== nv) {
      num.set(v.id, nv);
      changed = true;
    }
  }
  // ...then bindings and fields
}

optimistic(v) is true for phis, binding loads, field reads and parameters, the values that can sit on a cycle. On the sum loop the real analysis reports %3 (i), %6 (s) and %7 as numbers. The parameter %0 comes out maybe-not: nothing in the program calls sum, so nothing is known about n. Add a call sum(3) and %0 becomes a number too: sum is only ever called directly, so the param rule can check the argument at every call site. Replace the loop body with something that can add a string, and the doubt travels round the back edge, just as in the diagram.

Your turn

// insts: { id: { op, args } }
// op: 'num' | 'str' | 'add' | 'phi'
// Return { id: true if a number }.
function numeric(insts) {
  const fact = {};
  for (const id in insts) {
    fact[id] = insts[id].op === 'num';
  }
  return fact;
}

// blocks: { b: { preds: [...],
//   defs: [[name, defId], ...] } }
// Return { b: sorted defIds that
//   reach the start of b }.
function reaching(blocks) {
  const inn = {};
  for (const b in blocks) inn[b] = [];
  return inn;
}

What you learned

• A dataflow analysis has a fact per value or point, a rule per instruction, and a merge where paths meet. In SSA, the phi’s rule is the merge.
• A lattice orders the facts. Merging takes the highest fact below both. Finite height plus one-way movement means the analysis ends.
• A fixpoint is where no rule changes anything. Starting optimistic finds the most precise one; starting pessimistic can get stuck on loops.
• A worklist only revisits values whose inputs changed.
• Viscosity’s numeric inference is an optimistic fixpoint, run in rounds over values, bindings and fields.

Next: the most famous analysis of all, and the transformation it enables.