Chapter 7

Control Flow Graphs

The last chapter compiled loops and switches straight from source-level constructs. That works when your compiler goes from a syntax tree to WebAssembly in one step. Many compilers do not. They lower functions to a control flow graph first, a set of basic blocks joined by jumps, because that is where optimisations are easiest to write. Turning a control flow graph back into nested blocks is the problem this chapter solves.

#Why there is no goto7.1

WebAssembly could have had a goto. It does not because structured control flow makes two things cheap that a goto makes expensive.

The first is validation. With nested blocks, the validator knows at every point exactly which branch targets are in scope and what type each one expects, and it can check a function in one pass with a simple stack. With arbitrary jumps, it would have to find every path to each instruction and check they agree on the stack's types, which is a dataflow analysis.

The second is compilation. A baseline compiler like V8's Liftoff reads a function once, front to back, and emits machine code as it goes. Nested blocks tell it, at each branch, where the target is and what is live there. With arbitrary jumps it would need to build a graph first.

So the burden moves to the producer: your compiler. In return, you get fast startup on every engine.

#You may not need a graph7.2

If your compiler emits code from a syntax tree, and your language has only structured control flow (if, while, for, break, continue, return, switch, labelled breaks), you never have a graph to turn back into structure. The last chapter's patterns are enough. This is the simplest design, and a good one for a new compiler: engines do the low-level optimisations, so a WebAssembly backend gains less from its own graph-level optimisation than a native backend would.

The rest of this chapter is for compilers that do build a graph, or whose language has goto.

#Reducible graphs7.3

A control flow graph is reducible if every loop in it has a single entry: one block, the loop header, through which every path into the loop passes. Graphs built from structured code are always reducible. So are nearly all graphs that come out of optimising them, since the standard optimisations preserve reducibility. Graphs can become irreducible through goto, through some kinds of jump threading, or through lowering things like coroutines and generators.

Every reducible graph can be turned into nested blocks and loops without duplicating any code and without adding any variables. Irreducible graphs cannot, and need one of the techniques in section 7.6.

#From a graph to blocks7.4

The algorithm most compilers use today is the one in Norman Ramsey's paper Beyond Relooper (2022), which LLVM's WebAssembly backend arrived at in its own form, called CFGStackify. It goes like this:

  1. Put the basic blocks in an order where every block comes after all of its forward predecessors: a reverse postorder. In this order, every edge either goes forward, or goes backward to a loop header.
  2. For each loop header, open a loop just before it. A backward edge to the header becomes a br to that loop. The loop ends after the last block in the loop.
  3. For each forward edge that does not go to the very next block, there must be a block that ends just before its target, so the edge can be a br to that block. Open each such block as late as possible while still enclosing every branch to it, which is at the start of the target's immediate dominator.
  4. Edges to the very next block are fall-through: no branch at all.

The blocks nest properly because of how dominators work: if block X dominates block Y, everything between X and Y in the order is dominated by X too, so the block constructs opened in step 3 can always be nested.

Here is a small graph, a diamond:

B0:  if (c) goto B2; else goto B1
B1:  x = 10; goto B3
B2:  x = 20; goto B3
B3:  return x + 1

In the order B0, B1, B2, B3: the edge B0→B1 falls through. B0→B2 skips over B1, so it needs a block ending before B2. B1→B3 skips over B2, so it needs a block ending before B3. B2→B3 falls through. Both blocks are opened at B0, which dominates everything, with the one that ends later on the outside:

(module
  (func (export "diamond") (param $c i32) (result i32)
    (local $x i32)
    (block $B3
      (block $B2
        ;; B0
        (br_if $B2 (local.get $c))
        ;; B1
        (local.set $x (i32.const 10))
        (br $B3))
      ;; B2
      (local.set $x (i32.const 20)))
    ;; B3
    (i32.add (local.get $x) (i32.const 1))))
called as diamond(0) and diamond(1)
11
21

That is more nesting than a person would write; a person would use an if. But it is mechanical, it is always correct, and engines compile it to the same machine code as the if. LLVM additionally recognises diamonds and emits if–else for them, which makes the output smaller.

Here is a graph with a loop, the for loop from the last chapter:

B0:  i = 0; sum = 0
B1:  if (i >= 10) goto B5          ;; loop header
B2:  if (i % 2 == 0) goto B4
B3:  sum = sum + i
B4:  i = i + 1; goto B1            ;; back edge
B5:  return sum

B1 is a loop header, so a loop opens before it, and the loop holds B1 to B4. The edge B1→B5 skips forward out of the loop, so a block ending before B5 is opened at B1's dominator, B0, outside the loop. The edge B2→B4 skips B3, so a block ending before B4 is opened at B2:

(module
  (func (export "main") (result i32)
    (local $i i32)
    (local $sum i32)
    ;; B0 (locals start at zero)
    (block $B5
      (loop $B1
        (br_if $B5 (i32.ge_s (local.get $i) (i32.const 10)))
        ;; B2
        (block $B4
          (br_if $B4 (i32.eqz (i32.rem_s (local.get $i) (i32.const 2))))
          ;; B3
          (local.set $sum (i32.add (local.get $sum) (local.get $i))))
        ;; B4
        (local.set $i (i32.add (local.get $i) (i32.const 1)))
        (br $B1)))
    ;; B5
    (local.get $sum)))

25

It is exactly the shape the last chapter built by hand from the for loop, which is no coincidence.

#The Relooper7.5

Before structured-control-flow algorithms based on dominators became standard, Emscripten used an algorithm called the Relooper (Alon Zakai, 2011), first to turn C into JavaScript and then into WebAssembly. Binaryen still provides it as a library, so a compiler can hand Binaryen a graph of basic blocks and get structured WebAssembly back. If you already use Binaryen to build your output, its Relooper is the quickest way to get started. It handles irreducible graphs too, using the technique in the next section.

#Irreducible control flow7.6

An irreducible graph has a loop with more than one entry. The smallest example is a goto into the middle of a loop:

    if (skip) goto middle;
top:
    print(1);
middle:
    print(2);
    if (--k > 0) goto top;

The loop top→middle→top can be entered at top (by falling into it) or at middle (by the goto). No placement of a single loop works, since a loop has one entry, its start.

The general fix is a dispatch loop: a loop around a br_table that switches on a local variable saying which block to run next. Each block sets the variable and branches back to the dispatcher:

(module
  (import "env" "print_i32" (func $print (param i32)))
  (func (export "f") (param $skip i32) (param $k i32)
    (local $next i32)                 ;; 0: top, 1: middle, 2: exit
    (local.set $next (local.get $skip))
    (loop $dispatch
      (block $exit
        (block $middle
          (block $top
            (br_table $top $middle $exit (local.get $next)))
          ;; top
          (call $print (i32.const 1)))
        ;; middle (top falls into it)
        (call $print (i32.const 2))
        (local.set $k (i32.sub (local.get $k) (i32.const 1)))
        (local.set $next (select (i32.const 0) (i32.const 2)
                                 (i32.gt_s (local.get $k) (i32.const 0))))
        (br $dispatch)))
    ;; exit
    ))

The first call falls into top and goes round twice. The second skips straight to middle the first time round:

called as f(0, 2) and f(1, 2)
1
2
1
2
2
1
2

Only the blocks involved in the irreducible loop need to go through the dispatcher. The rest of the function can be structured normally. The cost is an indirect jump per transfer, and an engine cannot optimise the loop as well as a natural one, so this is for the rare case, not the common one.

The other fix is node splitting: duplicate the blocks of the loop that are reachable from the second entry, so each copy has a single entry. It produces faster code at the cost of size, and in the worst case the size grows exponentially, so compilers use it only for small regions.

#What you have seen7.7

WebAssembly's structured control flow puts the work of structuring on the producer, to make validation and compilation single-pass. A compiler that works from a syntax tree can emit structure directly. One that builds a control flow graph can restore structure from any reducible graph with an algorithm based on dominators, placing a loop at each header and a block before each forward-branch target. Irreducible graphs need a dispatch loop or node splitting.

The next chapter looks at modules as a whole.