Chapter 6

Structured Control Flow

WebAssembly has no jump instruction. It has three ways to group instructions, block, loop and if, and branches that can only target one of the groups that encloses them. This chapter covers each piece, then shows how the loops, breaks, continues and switches of an ordinary language compile into them.

#block and br6.1

A block groups instructions, and gives a branch somewhere to go. A branch to a block jumps to its end:

(module
  (import "env" "print_i32" (func $print (param i32)))
  (func (export "main")
    (block $done
      (call $print (i32.const 1))
      (br $done)
      (call $print (i32.const 2)))   ;; skipped
    (call $print (i32.const 3))))

1
3

br $done is an unconditional branch to the end of the block labelled $done. br_if branches only if the i32 it pops is non-zero:

(module
  (func (export "sign") (param $x i32) (result i32)
    (block $not_positive
      (br_if $not_positive (i32.le_s (local.get $x) (i32.const 0)))
      (return (i32.const 1)))
    (block $not_negative
      (br_if $not_negative (i32.ge_s (local.get $x) (i32.const 0)))
      (return (i32.const -1)))
    (i32.const 0)))

called as sign(5), sign(0) and sign(-5)

1
0
-1

Labels such as $done exist only in the text format. In the binary, a branch names its target by depth: 0 is the innermost enclosing block, 1 the one around that, and so on. wasm2wat shows what the assembler made of the names:

(module
  (func (export "main")
    (block $outer
      (block $inner
        (br $outer)
        (br $inner)))))

wasm2wat depths.wasm

(module
  (type (;0;) (func))
  (func (;0;) (type 0)
    block  ;; label = @1
      block  ;; label = @2
        br 1 (;@1;)
        br 0 (;@2;)
      end
    end)
  (export "main" (func 0)))

A compiler emitting the binary format directly has to compute these depths, which is easy: keep a stack of the blocks you are inside, and a branch's depth is how far down that stack its target is.

#loop6.2

A loop also groups instructions, but a branch to a loop jumps to its start. A loop does not repeat by itself: if control reaches the end of a loop, it carries on after it. The repetition comes from branching back:

(module
  (import "env" "print_i32" (func $print (param i32)))
  (func (export "main")
    (local $i i32)
    (loop $again
      (call $print (local.get $i))
      (local.set $i (i32.add (local.get $i) (i32.const 1)))
      (br_if $again (i32.lt_s (local.get $i) (i32.const 3))))))

0
1
2

That is the whole difference between block and loop: where a branch to it goes.

A branch to a block goes to its end; a branch to a loop goes to its start.

#if6.3

if pops an i32 and runs its then arm if it is non-zero, and its optional else arm otherwise:

(module
  (import "env" "print" (func $print (param i32 i32)))
  (memory (export "memory") 1)
  (data (i32.const 0) "evenodd")
  (func (export "parity") (param $x i32)
    (if (i32.and (local.get $x) (i32.const 1))
      (then (call $print (i32.const 4) (i32.const 3)))
      (else (call $print (i32.const 0) (i32.const 4))))))

called as parity(4) and parity(7)

even
odd

In the flat form, if pops its condition from the stack, and the arms are separated by else and closed by end:

local.get $x
i32.const 1
i32.and
if
  ;; then
else
  ;; else
end

An if is also a label, and a branch to it goes to its end, like a block.

#Blocks with results6.4

Blocks, loops and ifs can produce values. They declare what they leave on the stack with a result, just as functions do. This makes if an expression, like the ternary operator:

(module
  (func (export "max") (param $a i32) (param $b i32) (result i32)
    (if (result i32) (i32.gt_s (local.get $a) (local.get $b))
      (then (local.get $a))
      (else (local.get $b)))))

called as max(3, 8)

When a branch leaves a block that has results, it takes the values with it, from the top of the stack. So a block with a result is how you write an early exit that produces a value:

(module
  ;; the leading decimal digit of a positive number
  (func (export "first_digit") (param $n i32) (result i32)
    (block $found (result i32)
      (loop $shrink
        (br_if $found (local.get $n) (i32.lt_u (local.get $n) (i32.const 10)))
        (local.set $n (i32.div_u (local.get $n) (i32.const 10)))
        (br $shrink))
      (unreachable))))

called as first_digit(4567) and first_digit(9)

4
9

br_if $found here takes two operands: the value to carry out, and the condition. If the condition is true, the value leaves the block as its result. If it is false, the value stays on the stack, unused. That is harmless: a branch discards whatever is left on the stack inside the construct it targets, beyond the values it carries, so when br $shrink jumps back to the top of the loop, the stale value goes with it.

unreachable traps if it is ever executed. Here it marks a point control cannot reach (the loop only leaves by branching to $found), and it also satisfies the validator, as section 6.8 explains.

Blocks can also take parameters: values from the enclosing stack that the block consumes. A loop with parameters can carry values around each iteration on the stack instead of in locals. To write one, you declare its type, like a function's:

(module
  (func (export "main") (result i32)
    (local $c i32)
    ;; 10 + 9 + ... + 1, with the total and the counter carried on the stack
    (i32.const 0)                       ;; total
    (i32.const 10)                      ;; counter
    (loop $sum (param i32 i32) (result i32)
      (local.set $c)                    ;; stack: total
      (i32.add (local.get $c))          ;; stack: total+c
      (local.tee $c (i32.sub (local.get $c) (i32.const 1)))
      (br_if $sum (local.get $c))       ;; again with (total+c, c-1) if c-1 != 0
      drop)))                           ;; leave the total

The folded (i32.add (local.get $c)) has only one operand written inside it; the other is already on the stack. The folded form allows that, since it only decides the order instructions are written in.

Loops with parameters are awkward to write by hand: there is no instruction to duplicate a value, so anything used twice goes through a local anyway. They are mostly useful to compilers that want to avoid creating locals. The point to take away is the typing rule. A branch to a loop carries the loop's parameters, since it goes to the start, where those are expected. A branch to a block or if carries its results, since it goes to the end.

#br_table6.5

br_table is the multi-way branch. It pops an i32 index and branches to the label at that position in its list, or to the last label, the default, if the index is out of range:

(module
  (func (export "classify") (param $x i32) (result i32)
    (block $default
      (block $two
        (block $one
          (block $zero
            (br_table $zero $one $two $default (local.get $x)))
          ;; case 0
          (return (i32.const 100)))
        ;; case 1
        (return (i32.const 101)))
      ;; case 2
      (return (i32.const 102)))
    ;; default
    (i32.const -1)))

called as classify(0), classify(1), classify(2) and classify(99)

This is how a switch compiles: one block per case, nested so that the innermost block's end is where the first case's code starts. A branch to $zero lands just after $zero's end, which is case 0's code; a branch to $one lands after $one's end, which is case 1's code. Each case ends by leaving the whole construct, here with return, in general with a br to an outer block. If a case should fall through to the next, as in C, it simply does not branch out.

#Compiling loops6.6

Here are the usual shapes. A while loop tests its condition first, so it needs a block to leave and a loop to repeat:

;; while (cond) { body }
(block $break
  (loop $continue
    (br_if $break (i32.eqz cond))
    body
    (br $continue)))

break is br $break, and continue is br $continue. A do–while tests at the bottom, so the loop alone is enough:

;; do { body } while (cond)
(loop $top
  body
  (br_if $top cond))

But a continue inside a do–while must go to the test, not the top. So does a continue inside a for loop, which must run the increment. Those need one more block, wrapping the body, so that continue can branch to its end:

;; for (init; cond; step) { body }
init
(block $break
  (loop $top
    (br_if $break (i32.eqz cond))
    (block $continue
      body)                ;; continue is (br $continue)
    step
    (br $top)))

Here is that shape, summing the odd numbers below 10 with a continue for the even ones:

(module
  (func (export "main") (result i32)
    (local $i i32)
    (local $sum i32)
    ;; for (i = 0; i < 10; i++) { if (i % 2 == 0) continue; sum += i; }
    (block $break
      (loop $top
        (br_if $break (i32.ge_s (local.get $i) (i32.const 10)))
        (block $continue
          (br_if $continue (i32.eqz (i32.rem_s (local.get $i) (i32.const 2))))
          (local.set $sum (i32.add (local.get $sum) (local.get $i))))
        (local.set $i (i32.add (local.get $i) (i32.const 1)))
        (br $top)))
    (local.get $sum)))

Labelled break and continue, which leave or restart an outer loop, are no harder: they branch to that loop's $break block or $continue label, at a greater depth.

#Short-circuit operators6.7

&& and || must not evaluate their right operand unless they need to, so they are an if with a result:

;; a && b
(if (result i32) a
  (then b)
  (else (i32.const 0)))

;; a || b
(if (result i32) a
  (then (i32.const 1))
  (else b))

When the right operand is cheap and has no side effects, such as a local or a comparison of locals, select or a plain i32.and of two normalised booleans is shorter and avoids a branch.

#How validation handles control flow6.8

Each block, loop and if is validated as if it were a little function:

Inside a block, the stack starts with only the block's parameters. The instructions inside cannot pop values that were on the stack before the block began. They are not lost, just out of reach until the block ends.
At the end of a block, the stack must hold exactly the block's results.
A branch must have the values its target expects on top of the stack.

The interesting case is code after an unconditional branch:

(module
  (func (export "main") (result i32)
    (block $b (result i32)
      (br $b (i32.const 7))
      i32.add)))       ;; never runs, and has no operands

That validates, even though the i32.add has nothing to pop. After br, return, br_table and unreachable, control cannot continue, so the rest of the block is dead code, and the validator treats the stack there as polymorphic: it can supply values of any type, as many as needed. This saves a compiler from having to make dead code type-check, which matters most at the end of a function whose last statement is a return:

(module
  (func (export "f") (param i32) (result i32)
    (return (local.get 0))))

called as f(3)

Without the polymorphic rule, that function would need the i32 the body promised to be on the stack after the return too.

When the validator does object, V8's messages name the problem directly:

(module
  (func (export "main") (result i32)
    (block $b (result i32)
      (br $b))))

expected 1 elements on the stack for branch, found 0

#What you have seen6.9

block, loop and if nest. A branch names an enclosing one by depth, and goes to the end of a block or if, or the start of a loop, carrying values with it. br_if branches conditionally and br_table by index. Loops, break, continue, switch and short-circuit operators all compile into these shapes.

What does not compile into them so directly is a goto, or any control flow graph that is not already nested. That is the next chapter.