75. Basic blocks and control-flow graphs

A list with holes in it

Here is a classic loop: halve n if it’s even, otherwise triple it and add one, until it reaches 1.

function g(n) {
  while (n > 1) {
    if (n % 2) n = 3 * n + 1;
    else n = n / 2;
  }
  return n;
}

Written as flat three-address code with jumps, the way chapter 55’s compiler wrote bytecode, it’s ten lines:

0  t1 = n > 1
1  ifnot t1 goto 9
2  t2 = n % 2
3  ifnot t2 goto 7
4  t3 = 3 * n
5  n = t3 + 1
6  goto 0
7  n = n / 2
8  goto 0
9  return n

Now a simple question: when line 7 runs, which line ran just before it? You can’t tell by looking at line 6. You have to search the whole list for jumps to 7. Every question about order, “is this value computed before that use?”, has the same problem. A compiler needs a better map.

Basic blocks

The roads are runs of instructions with no jump into their middle and no jump out of their middle. To find them, first mark the leaders, the instructions where a run must start. Step through it:

Three rules find every leader: the first instruction, every jump target, and every instruction straight after a jump. Each block then runs from one leader up to, but not including, the next.

The control-flow graph

The blocks are the nodes of a graph. An edge from block A to block B means “control can go straight from the end of A to the start of B”, by a jump or by falling through.

Inside a block, order is trivial: top to bottom. Between blocks, it is whatever the arrows allow. So a compiler can study each block on its own, cheaply, and then combine the results along the edges. Nearly every analysis in the rest of Part VI works that way.

Blocks in VIR

Viscosity never has to look for leaders, because its lowering builds blocks directly. An if makes a block for each branch and one for the code after; a while makes a header, a body, a “continue” block (where the update of a for goes) and an exit. The types from packages/core/src/vir.ts make “one exit” impossible to get wrong:

interface Block {
  id: BlockId;
  insts: Inst[];
  term: Terminator;
  preds: BlockId[];
}

type Terminator =
  | { kind: 'br'; target: BlockId }
  | { kind: 'condbr'; cond: ValueId;
      then: BlockId; else: BlockId }
  | { kind: 'return';
      value: ValueId | null }
  | { kind: 'throw'; value: ValueId }
  | { kind: 'unreachable' };

Ordinary instructions can’t jump: only the terminator can, and every block has exactly one, at the end. Reading off a block’s successors is then one line, from packages/core/src/cfg.ts:

function successors(f: Func, b: BlockId) {
  const t = f.blocks[b].term;
  return t.kind === 'br' ? [t.target]
    : t.kind === 'condbr' ? [t.then, t.else]
    : [];
}

Predecessors are kept on each block, filled in as edges are made. When the builder sets a block’s terminator, it adds the block to each successor’s preds.

Here is the graph Viscosity builds for g:

b0:
  br b1
b1:  ; preds b0 b3
  ...n > 1
  condbr %3, b2, b4
b2:  ; preds b1
  ...n % 2
  condbr %5, b5, b6
b3:  ; preds b7
  br b1
b4:  ; preds b1
  return %1
b5:  ; preds b2
  ...3 * n + 1
  br b7
b6:  ; preds b2
  ...n / 2
  br b7
b7:  ; preds b5 b6
  br b3

(Trimmed: ... stands for the instructions that compute the value.)

That is eight blocks where the hand-written list had five. The lowering is mechanical: it gives the if a join block (b7) and the loop a “continue” block (b3), even when they hold nothing but a jump. A block with a single br is cheap and keeps the lowering simple. Notice the predecessors, too: b1 has two, the entry and the back edge, and b7 has two, the two branches. Blocks with several predecessors are where values from different paths meet, which is what chapter 77’s phis are for.

// successors of b0..b7, from VIR
const succ = [[1], [2, 4], [5, 6],
  [1], [], [7], [7], [3]];
const preds = succ.map(() => []);
succ.forEach((ss, b) => {
  for (const s of ss) preds[s].push(b);
});
preds.forEach((ps, b) => {
  console.log('b' + b, 'preds', ps);
});

Unreachable blocks

What does the lowering do with code after a return?

func f(%0):            // return x; x = 2;
  b0:
    %0 = param
    return %0
  b1:
    %1 = const 2
    return

It keeps going, in a fresh block, b1. No terminator anywhere points at b1, so it has no predecessors and no path from the entry reaches it. In a CFG that is a fact you can see, and a compiler can drop such blocks without asking anything else. Viscosity’s dominator code simply leaves them out, as you’ll see next chapter.

Your turn

function leaders(code) {
  const ls = new Set([0]);
  for (const ins of code) {
    if (ins.op === 'goto') {
      ls.add(ins.to);
    }
  }
  return [...ls];
}

function preds(succ) {
  return succ;
}

What you learned

• A basic block is straight-line code with one entry and one exit: if its first instruction runs, all of it does.
• Leaders start blocks: the first instruction, every jump target, and every instruction after a jump.
• A CFG has a node per block and an edge where control can pass directly. Successors come from the terminator; predecessors are the reverse edges. A cycle is a loop.
• In VIR, only a block’s single terminator can jump. The lowering builds blocks directly and records preds as it links them.
• A block (other than the entry) with no predecessors is unreachable.

Next: which blocks must run before which, whatever path is taken.