Proposal: ability to execute a function on a different stack

[andrewrk]

Here is a snippet from the Semantics document:

Stack Overflow

Call stack space is limited by unspecified and dynamically varying constraints and is a source of nondeterminism. If program call stack usage exceeds the available call stack space at any time, the execution in the WebAssembly instance is terminated and abnormal termination is reported to the outside environment.

Implementations must have an internal maximum call stack size, and every call must take up some resources toward exhausting that size (of course, dynamic resources may be exhausted much earlier). This rule exists to avoid differences in observable behavior; if some implementations have this property and others don’t, the same program which runs successfully on some implementations may consume unbounded resources and fail on others. Also, in the future, it is expected that WebAssembly will add some form of stack-introspection functionality, in which case such optimizations would be directly observable.

Support for explicit tail calls is planned in the future 🦄, which would add an explicit tail-call operator with well-defined effects on stack introspection.

I am the creator of Zig, an LLVM-based programming language which supports WebAssembly as one of many architecture backends.

In Zig we take stack overflow very seriously. In fact, recursion is a compile error unless you use a builtin function @newStackCall in order to make the recursive call on an explicitly allocated stack. Combining this with determining stack upper bound size at compile-time, Zig eliminates the possibility of stack overflow.

For most architectures, this works with the following LLVM IR code:

  %6 = call i8* @llvm.stacksave(), !dbg !45
  call void @llvm.write_register.i64(metadata !47, i64 %5), !dbg !45
  call fastcc void @foo(), !dbg !45
  call void @llvm.stackrestore(i8* %6), !dbg !45
...
!47 = !{!"rsp\00"}

That is, it modifies the stack pointer register to point to the new stack memory, makes the function call, and then restores the stack pointer register.

This proposal is to support these semantics, in one of 2 ways:

• Allow modification of the stack pointer so that the LLVM IR above can lower to WebAssembly.
• Support a builtin function directly which performs a function call using an explicitly provided memory buffer as the stack.

[dschuff]

You could maybe almost do something like this today using LLVM's existing ABI. LLVM on wasm essentially has 2 stacks: one that is not user-visible that contains the return address and potentially any number of the (wasm) function's arguments and locals, and another allocated in the linear memory for (C/LLVM) local variables which are address-taken, variable-sized or over-aligned. The LLVM backend uses a wasm global as the stack pointer for this linear stack, and IIRC the @llvm.stacksave and @llvm.stackrestore intrinsics work with that stack pointer.

I think you could explicitly manage the allocation of the linear stack similar to how you manage the stack on other architectures. That just leaves the wasm stack. Its frame sizes are (should be?) statically bounded because the number and size of locals and arguments is statically known. But of course the "real" memory size is opaque and you can't control how much memory is available in the environment. You could get tighter control if you modified your LLVM code such that you minimized the number of wasm locals (instead putting more variables in linear memory) because instantiation of memory fails at instantiation rather than at runtime, but that would come at a cost.