76. Dominators

Has this already happened?

Look again at the Collatz loop’s graph from chapter 75. Suppose b2 computes something, say n % 2, and b7 wants to reuse it. Is that safe? Only if b2 has certainly run by the time b7 runs. Or the other way round: b5 computes 3 * n. Can b7 use that? No: on the path through b6, b5 never ran.

The difference between b2 and b5 is not where they sit in the listing, or which runs first on some path. It’s whether you can get to b7 without them. That idea, the blocks you can’t avoid, turns out to be one of the most useful facts a compiler can have.

Checkpoints

For the Collatz graph: b2 dominates b7, because both ways into b7 come from b2’s branches. b5 doesn’t dominate b7, since the path through b6 avoids it. And b2 does not dominate b4, the exit, even though b2 can run before it: when n starts at 1, the loop test fails at once and b4 runs with no visit to b2 at all.

Computing it: shrink until nothing changes

There is a neat equation hidden in the definition. To reach B you must come from one of its predecessors. So a block dominates B exactly if it is B itself, or it dominates every predecessor of B:

Dom(entry) = { entry }
Dom(B) = { B } ∪ ⋂ Dom(P), P a pred of B

Loops make this circular: b1’s set depends on b3’s, which depends on b1’s. The way out is to start every set as large as possible, “all blocks”, and apply the equation again and again. Sets only shrink, and when a whole pass changes nothing, you have the answer. Step through it:

The order matters for speed, not for the answer. Viscosity visits blocks in reverse postorder: do a depth-first search from the entry, write each block down once all its successors are finished, then reverse the list. From packages/core/src/cfg.ts:

function reversePostorder(f: Func) {
  const seen = new Set<BlockId>();
  const order: BlockId[] = [];
  const visit = (b: BlockId) => {
    seen.add(b);
    for (const s of successors(f, b))
      if (!seen.has(s)) visit(s);
    order.push(b);
  };
  visit(f.entry);
  return order.reverse();
}

In that order every block comes after its predecessors, except the ones that reach it by a back edge. So most of the information is already there when a block is visited. For the Collatz graph the order is 0 1 4 2 6 5 7 3. One pass does the work, and a second confirms it.

// Collatz CFG from chapter 75
const preds = [[], [0, 3], [1], [7],
  [1], [2], [2], [5, 6]];
const rpo = [0, 1, 4, 2, 6, 5, 7, 3];
const at = new Map(
  rpo.map((b, i) => [b, i]));
const idom = new Map([[0, 0]]);
const meet = (a, b) => {
  while (a !== b) {
    while (at.get(a) > at.get(b))
      a = idom.get(a);
    while (at.get(b) > at.get(a))
      b = idom.get(b);
  }
  return a;
};
let changed = true, passes = 0;
while (changed) {
  changed = false;
  passes++;
  for (const b of rpo.slice(1)) {
    const ps = preds[b]
      .filter((p) => idom.has(p));
    let d = ps[0];
    for (const p of ps.slice(1))
      d = meet(p, d);
    if (idom.get(b) !== d) {
      idom.set(b, d);
      changed = true;
    }
  }
}
for (const [b, d] of idom)
  console.log(`idom(b${b}) = b${d}`);
console.log('passes:', passes);

The dominator tree

Look at the final sets: Dom(b3) = {0,1,2,3,7}. They nest. Every dominator of b3 also dominates b3’s closest dominator, b7. So you never need to store whole sets. For each block, keep just its nearest strict dominator, and the rest follow by walking upwards.

Viscosity’s version stores only the tree

dominators in cfg.ts computes the immediate dominators directly, as a Map from each block to its idom, without ever building a set. Trimmed:

const intersect = (a, b) => {
  while (a !== b) {
    while (index.get(a) > index.get(b))
      a = idom.get(a);
    while (index.get(b) > index.get(a))
      b = idom.get(b);
  }
  return a;
};
// then, until nothing changes, for each
// block b in reverse postorder (not entry):
let d = preds[0];
for (const p of preds.slice(1))
  d = intersect(p, d);
if (idom.get(b) !== d) {
  idom.set(b, d); changed = true;
}

intersect is the set intersection, done on the tree. index is a block’s position in reverse postorder, and a block’s idom always comes earlier in that order than the block itself. Put a finger on each block and move whichever finger is further down up to its idom, until the fingers meet. Where they meet is the nearest block that dominates both. Only predecessors that already have an idom are used, which also means unreachable blocks never get one.

Asking “does A dominate B?” is then a walk up the tree from B:

function dominates(idom, a, b) {
  if (!idom.has(b)) return false;
  for (let x = b; ; x = idom.get(x)) {
    if (x === a) return true;
    if (idom.get(x) === x) return false;
  }
}

The entry is its own idom, which is how the walk knows it reached the root.

Your turn

function dominators(succ) {
  const preds = succ.map(() => []);
  succ.forEach((ss, b) => {
    for (const s of ss)
      preds[s].push(b);
  });
  // dom[b]: b's dominators, sorted
  const dom = succ.map((_, b) => [b]);
  return dom;
}

function idoms(dom) {
  return dom.map(() => 0);
}

What you learned

• A dominates B if every path from the entry to B goes through A. Every block dominates itself; the entry dominates everything reachable.
• Dominator sets satisfy Dom(B) = {B} ∪ the intersection of its predecessors’ sets. Start from “all”, repeat until nothing changes; sets only shrink. Reverse postorder makes it quick.
• The immediate dominator is the closest strict dominator. Joining each block to its idom gives the dominator tree; a block’s dominators are its ancestors.
• Viscosity stores only idom, intersecting by walking two fingers up the tree. dominates walks up from B; naturalLoops uses it to find back edges.

Next: SSA form, where every value has exactly one definition, and the dominator tree tells you where that definition can be seen.