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.