Tail Calls

A call is a tail call when it is the last thing a function does: the caller will return whatever the callee returns, and has nothing else to do. A tail call does not need its own stack frame, since the caller's frame is finished with. Native compilers turn tail calls into jumps when they can. A WebAssembly compiler cannot, because there are no jumps between functions, so WebAssembly 3.0 added instructions that make a tail call explicitly. This chapter covers them and what they make possible.

#return_call21.1

return_call $f is call $f followed by return, except that the caller's frame is removed before the call rather than after. A recursive function written with it runs in constant stack space, however deep the recursion:

(module
  (func $count (export "count") (param $n i32) (result i32)
    (if (result i32) (i32.eqz (local.get $n))
      (then (i32.const 0))
      (else (return_call $count (i32.sub (local.get $n) (i32.const 1)))))))

0

The same function with an ordinary call runs out of stack long before a million levels:

(module
  (func $count (export "count") (param $n i32) (result i32)
    (if (result i32) (i32.eqz (local.get $n))
      (then (i32.const 0))
      (else (call $count (i32.sub (local.get $n) (i32.const 1)))))))

RangeError: Maximum call stack size exceeded

Tail calls are not limited to recursion. Any call in tail position can use return_call, including calls between different functions:

(module
  (func $is_even (export "is_even") (param $n i32) (result i32)
    (if (result i32) (i32.eqz (local.get $n))
      (then (i32.const 1))
      (else (return_call $is_odd (i32.sub (local.get $n) (i32.const 1))))))
  (func $is_odd (param $n i32) (result i32)
    (if (result i32) (i32.eqz (local.get $n))
      (then (i32.const 0))
      (else (return_call $is_even (i32.sub (local.get $n) (i32.const 1)))))))

0
1

Mutual recursion like this cannot be turned into a loop by a compiler working one function at a time, which is why the instruction is needed.

#The rules21.2

A tail call replaces the caller's return, so the callee's results must be what the caller returns: its result types must match the caller's, or be subtypes of them. The parameters can be anything:

(module
  (func $f (result i64) (i64.const 1))
  (func (result i32)
    (return_call $f)))

CompileError: WebAssembly.Module(): Compiling function #1 failed: return_call: tail call type error @+34

There are three instructions, one for each kind of call:

Like return, a tail call ends the block it is in, and the code after it is unreachable.

#What tail calls make possible21.3

Functional languages. Scheme requires that tail calls run in constant space, and ML, Haskell, Elixir and similar languages assume it. Without tail calls, compilers for these languages used trampolines: functions return a description of the next call to a loop that makes it. That works, but every call goes through the loop, which is slow and hard for engines to optimise.

Interpreters. A fast way to write an interpreter is to give each opcode its own handler function, and have each handler tail-call the next opcode's handler through a table. There is no central dispatch loop, so each handler's indirect jump is predicted separately by the hardware. This is the technique behind several fast interpreters, and it needs tail calls:

(module
  (import "env" "print_i32" (func $print (param i32)))
  (memory 1)
  ;; an accumulator machine. 1 n: acc += n; 2 n: acc *= n; 3: print acc; 0: halt
  (data (i32.const 0) "\01\05" "\02\07" "\01\03" "\03" "\00")
  (type $handler (func (param i32 i32)))         ;; pc, acc
  (table 4 funcref)
  (elem (i32.const 0) $halt $add $mul $out)

  ;; fetch the opcode at pc and tail-call its handler
  (func $next (param $pc i32) (param $acc i32)
    (return_call_indirect (type $handler)
      (local.get $pc) (local.get $acc)
      (i32.load8_u (local.get $pc))))

  (func $halt (param $pc i32) (param $acc i32))
  (func $add (param $pc i32) (param $acc i32)
    (return_call $next
      (i32.add (local.get $pc) (i32.const 2))
      (i32.add (local.get $acc) (i32.load8_u offset=1 (local.get $pc)))))
  (func $mul (param $pc i32) (param $acc i32)
    (return_call $next
      (i32.add (local.get $pc) (i32.const 2))
      (i32.mul (local.get $acc) (i32.load8_u offset=1 (local.get $pc)))))
  (func $out (param $pc i32) (param $acc i32)
    (call $print (local.get $acc))
    (return_call $next (i32.add (local.get $pc) (i32.const 1)) (local.get $acc)))

  (func (export "main")
    (call $next (i32.const 0) (i32.const 0))))

The program computes (0 + 5) × 7 + 3:

38

Every handler ends by tail-calling $next, which tail-calls the next handler, so however long the program runs, the stack never grows. A real interpreter would inline $next into each handler, so that every handler ends with its own return_call_indirect, giving the hardware's branch predictor a separate history for each.

State machines and continuations. A state machine can make each state a function, with transitions as tail calls, which is often clearer than a dispatch loop. A compiler using continuation-passing style, where every function takes the function to call next as a parameter, needs tail calls for every call.

#What you have seen21.4

return_call, return_call_indirect and return_call_ref call a function in place of the caller, so a chain of tail calls runs in constant stack space. The callee must return what the caller returns. Tail calls let functional languages compile calls directly instead of through trampolines, and enable fast interpreter designs and state machines written as functions.

The next chapter covers the biggest addition to WebAssembly since its first version: garbage collection.