In a course that introduced x86 machine code we compiled basic C code snippets and looked at the output in text format. I think that is a great way to get to know a low-level language. Of course it is tedious, but we can gain a lot of insight into compilation and language semantics this way. I am currently studying WebAssembly and had some struggles understanding control flow, things like conditionals and loops. This is because in contrast to most other low-level languages, WebAssembly has structured control flow1:

It [WebAssembly] does not offer simple jumps but instead provides structured control flow constructs more akin to a programming language. This ensures by construction that control flow cannot form irreducible loops, contain branches to blocks with misaligned stack heights, or branch into the middle of a multi-byte instruction.

Sounds great! This is a very similar motivation as to why goto is considered a bad thing and should be avoided. It prevents several attacks using arbitrary jumps in assembly code by design and is therefore highly relevant to the security aspect of WebAssembly too. So how does structured control flow look like? Reading the specification is great to understand some things like type systems, but has not helped me much with structured control flow. Instead I started to take the same approach as with x86 and look at compiled C control flow in WebAssembly.

Todays code snippet is a single function with a for loop and break statements and you can play with it directly in the browser via webassembly.studio. Simply start an empty C project and include this function (make sure you add the WASM_EXPORT just like with main).

/**
 * Returns 1 if x is prime and its smallest proper divisor otherwise
 */
int isPrime(unsigned int x) {
  unsigned int divisor = 1;
  for(unsigned int i = 2; i < x; ++i) {
    if(x % i == 0) {
      divisor = i;
      break;
    }
  }
  return divisor;
}

This is not a post about primes,the correctness or edge cases of this function. I just use this example because I feel like it presents an intuitive use case of break. The coolest feature of webassembly.studio is that it automatically pretty-prints an editable text representation of the compiled wasm binary and we can directly look at it:

(func $isPrime (export "isPrime") (type $t2) (param $p0 i32) (result i32)
  (local $l0 i32) (local $l1 i32)
  i32.const 1
  set_local $l0
  block $B0
    block $B1
      get_local $p0
      i32.const 3
      i32.lt_u
      br_if $B1
      i32.const 2
      set_local $l1
      loop $L2
        get_local $p0
        get_local $l1
        i32.rem_u
        i32.eqz
        br_if $B0
        i32.const 1
        set_local $l0
        get_local $l1
        i32.const 1
        i32.add
        tee_local $l1
        get_local $p0
        i32.lt_u
        br_if $L2
      end
    end
    get_local $l0
    return
  end
  get_local $l1
)

Like most low-level code this is not easy on the eye and almost impossible to read and understand from top to bottom in one go. It takes some time to figure out code like this and the difficulty can range from easy to nearly impossible. Remember that a compiler can essentially output any sequence of instructions that behaves as defined by our source program. But even without understanding the code in detail, we can see the main aspect of structured control flow here:

Jump instructions (br, br_if) target control constructs (block, loop) directly by name.

That is the key point behind the quote I highlighted at the beginning of the post. The text format actually hides the “structured” part of control flow a bit, because it seems like you can still write jumps to weird places by using other label names. This is not the case, since label names are just syntactic sugar for numerical indices 0, 1, 2 and so on. The number indicates how many of the currently nested structures to break out of. So br 0 targets the immediately surrounding block, br 1 the block one level above and so on. If the branch index is higher than the current nesting level, the code is not valid and cannot be run.

Now just for the fun of it, I still want to figure out the code above though. I guess the best way to do this is by writing pseudocode for it. Here is what I think the code above is doing:

func(p0) { 
  let l0 = 1
  let l1 = 0

  if(p0 < 3) {
    return l0
  }

  l1 = 2

  while(l1 < p0) {
    if(p0 % l1 == 0) {
      return l1
    }
    l0 = 1
    ++l1
  }

  return l0
}

Going through this, you can see how it should behave the same way like our source program in C. However, it is also visible that compiler output does not always make sense. Consider at the local variable l0 for example: It is initialized to 1 and then assigned 1 in each loop iteration, only to be possibly returned as 1 in the end. I cannot think of a reason against just deleting l0 altogether and saying return 1 instead. Do not be tricked into thinking the compiler is stupid because it did not see this though!

My view is this: I as a human might be able to “optimize” one short program by manual inspection. A compiler as an algorithm is (ideally) able to produce reasonable code for any valid, arbitrary large source program. Put things into perspective.

That being said, if you have a correction or rationale for about the pseudocode above, please let me know!