DECEMBER 2018 | VOL. 61 | NO. 12 | COMMUNICATIONS OF THE ACM 109 with explicit branches. Every control construct is annotated with a function type ft = t 1 * → t 2 * describing its effect on the stack, popping values typed t 1 * and pushing t 2 *.

Branches. Branches can be unconditional (br), conditional (br_if), or indexed (br_table). They have “label” immediates that do not denote positions in the instruction stream but reference outer control constructs by relative nesting depth. Hence, labels are effectively scoped: branches can only reference constructs in which they are nested. Taking a branch “breaks from” that construct’s block;c the exact effect depends on the target construct: in case of a block or if it is a forward jump to its end (like a break statement); with a loop it is a backward jump to its beginning (like a continue statement). Branching unwinds the operand stack by implicitly popping all unused operands, similar to returning from a function call. This liberates producers from having to track stack height across sub-expressions and adding explicit drops to make them match.

Expressiveness. Structured control flow may seem like a severe limitation, but most high-level control constructs are readily expressible with the suitable nesting of blocks. For example, a C-style switch statement with fall-through,

switch (x) { block block block block case 0: … A… br_table 0 1 2 case 1: …B… break; becomes end … A… default: …C… end …B… br 1

} end …C… Slightly more finesse is required for fall-through between unordered cases. Various forms of loops can likewise be expressed with combinations of loop, block, br and br_if.

It is the responsibility of producers to transform unstructured and irreducible control flow into structured form. This is the established approach to compiling for the Web, where JavaScript is also restricted to structured control. In our experience building an LLVM backend for WebAssembly, irreducible control flow is rare, and a simple restructuring algorithm18 is sufficient to translate any Control Flow Graph (CFG) to WebAssembly. The benefit of the restriction is that many algorithms in engines are much simpler and faster.

2. 4. Function calls and tables

A function body is a block. Execution can complete by either reaching the end of the block with the function’s result values on the stack, or by a branch exiting the function block, with the branch operands as the result values; the return instruction is simply shorthand for the latter.

Calls. Functions can be invoked directly using the call instruction which takes an immediate identifying the function to call. Function pointers can be emulated with the call_

indirect instruction which takes a runtime index into a table
of functions defined by the module. The functions in this
table are not required to have the same type. Instead, the
type of the function is checked dynamically against an
form of configurability, for example, for linking. Like all enti-
ties in WebAssembly, variables are referenced by integer
indices.

So far so boring. In the following sections we turn our attention to more unusual features of WebAssembly’s design.

2. 2. Memory

The main storage of a WebAssembly program is a large array of raw bytes, the linear memory or simply memory. Memory is accessed with load and store instructions, where addresses are simply unsigned integer operands.

Creation and growing. Each module can define at most one memory, which may be shared with other instances via import/export. Memory is created with an initial size but may be dynamically grown. The unit of growth is a page, which is defined to be 64KiB, a choice that allows reusing virtual memory hardware for bounds checks on modern hardware (Section 5). Page size is fixed instead of being sys-tem-specific to prevent portability hazards.

Endianness. Programs that load and store to aliased locations with different types can observe byte order. Since most contemporary hardware has converged on little endian, or at least can handle it equally well, we chose to define WebAssembly memory to have little endian byte order. Thus the semantics of memory access is completely deterministic and portable across all engines and platforms.

Security. All memory access is dynamically checked against the memory size; out of bounds access results in a trap. Linear memory is disjoint from code space, the execution stack, and the engine’s data structures; therefore compiled programs cannot corrupt their execution environment, jump to arbitrary locations, or perform other undefined behavior. At worst, a buggy or malicious WebAssembly program can make a mess of the data in its own memory. Consequently, even untrusted modules can be safely executed in the same address space as other code. Achieving fast in-process isolation is necessary for interacting with untrusted JavaScript and the various Web Application Programming Interfaces (APIs) in a high-performance way. It also allows a WebAssembly engine to be safely embedded into other managed language runtimes.

2. 3. Control flow

WebAssembly represents control flow differently from most stack machines. It does not offer arbitrary 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. These properties allow WebAssembly code to be validated in a single pass, compiled in a single pass, and even transformed to an SSA-form intermediate representation in the same single pass.

Control constructs. As required by the grammar in Figure 1, the block, loop and if constructs must be terminated by an end opcode and be properly nested to be considered well-formed. The inner instruction sequences e* in these constructs form a block. Note that loop does not automatically iterate its block but allows constructing a loop manually c The name br can also be read as “break” wrt. a block.