Samrat Man Singh

Email: mail@samrat.me

Hi! I’m Samrat, a programmer from Nepal.

Summary of recent reading(July-September 2020)

2020-10-01

Summary of recent reading(April-June 2020)

2020-07-04

Summary of recent reading(January-March 2020)

2020-03-31

WebAssembly branching instructions, by example

2020-03-29

I have been familiarizing myself with WebAssembly by writing small WAT files and looking at the WASM output for some simple C functions. WebAssembly Studio is a great tool for doing this kind of exploration.

Branching in WebAssembly takes some getting used to– for one thing, the target of your branch instructions are relative to the current scope. That is, the target of the br 1 refers to the scope one level up from the current scope and the same target will be referred to as different indices depending on where the branch is being called from.

(block ;; <- this is the target block for the br below
  (block ;; <- if you wanted to refer to this, you would use `0`.
    ...
    br 1
    ))

The other thing is that the branching behaviour is a bit different depending on whether the target is a block or a loop. If the target is a block, control exits from the block. While if the target is a loop, the loop continues.

I thought I’d jot down some notes on my understanding of how branching works in WASM along with some examples.

Blocks

The branch instructions take an index– this index specifies the number of levels outward to go from the current scope:

(block
    local.get 0 ;; get 0th local, and put into stack
    i32.eqz ;; pop stack and check if it is zero, put result(boolean) into stack
    br_if 0 ;; branch out of 0th `block` if top item in stack is true
    i32.const 42
    local.set 1)

As mentioned in the comment in the code block, if the 0th local is zero, control reaches the instruction after the block.

Let’s look at a function involving nested blocks. Suppose we want to encode the following logic in WASM:

if (x == 0)
  return 42;
else if (x == 1)
  return 99;
else
  return 7;

One way to achieve this would be with the following function:

(func $foo (param i32) (result i32)
       (local i32)
       (block
           (block
               (block
                   ;; x == 0
                   local.get 0
                   i32.eqz
                   br_if 0

                   ;; x == 1
                   local.get 0
                   i32.const 1
                   i32.eq
                   br_if 1

                   ;; the `else` case
                   i32.const 7
                   local.set 1
                   br 2)
             i32.const 42
             local.set 1
             br 1)
         i32.const 99
         local.set 1)
       local.get 1)

If you actually compile the C or Rust equivalent of the code above, this is not the WASM you’ll get but this serves nicely for our purposes.

Let’s start with the “else” case first. We set the local to 7 and branch out of the block two levels up. This is the outermost block, which makes the next instruction the local.get 1. So we get the local we just set and return.

In the x == 0 case, we branch out from the innermost block, and the next three instructions are:

i32.const 42
local.set 1
br 1

Again we set the local to 42. And the index we pass to br is 1. Remember though that we branched out from a block, so branching out with index 1 means we are branching out of the outermost block again.

Loops

A branch instruction referring to a loop behaves a bit differently– if the index passed to a branch instruction is a loop, control passes to the beginning of the loop instead of exiting as happens in a block.

Here is an example showing the iterative factorial algorithm:

;; int result = 1;
;; while (i > 0) {
;;   result = result * i;
;;   i = i - 1;
;; }
(func $iterFact (param i64) (result i64)
       (local i64)
       i64.const 1
       local.set 1
       (block
           local.get 0
           i64.eqz
           br_if 0
           (loop
            local.get 1
            local.get 0
            i64.mul
            local.set 1
            local.get 0
            i64.const -1
            i64.add
            local.tee 0
            i64.eqz
            br_if 1
            br 0))
       local.get 1)

Let’s focus on just the branching statements.

The first br_if, outside the loop exits the block if the argument passed is 0.

The br_if inside the loop also exits the block(and hence also the loop), although note that this time the same block is referred to as index 1 instead of 0.

The final br 0(the penultimate line in the code block above) branches to the beginning of the loop, thus continuing the loop.

Summary of recent reading(October-December 2019)

2019-12-31