WebAssembly

Larva compiles a program to WebAssembly in two ways, chosen with --target:

Both produce the same three files and import the same JavaScript runtime, larva_rt.js. The own back end compiles in milliseconds and needs no tools; the LLVM path optimizes and is the one to use for speed. Today only the LLVM path is dependable: see Known gaps.

$ larva build --timings --target wasm -o sum.js sum.ant
sum.wasm, sum.js, sum.html (Larva back end, entry sum::Sums.$Module.Main)
timings: System.Core (compiled library) 50 ms, frontend 389 ms, HIR link 37 ms, lowering 344 ms, IR checks 133 ms, IR link 90 ms, native (wasm) 44 ms; total 1088 ms
$ node sum.js
4950
$ larva build --timings --target wasm-llvm -o suml.js sum.ant
suml.wasm, suml.js, suml.html (LLVM back end, O3, entry suml::Sums.$Module.Main)
timings: System.Core (compiled library) 11 ms, frontend 201 ms, HIR link 16 ms, lowering 260 ms, IR checks 192 ms, IR link 95 ms, native (wasm-llvm) 1293 ms; total 2068 ms
$ node suml.js
4950

sum.ant is the array-sum program of The LLVM back end. Its own-back-end module is 11,473 bytes; LLVM's is 1,184 bytes (LLVM inlined and folded nearly everything).

The driver: WasmBuilder

larva build lowers and links the program as for any target (see Projects and builds), then hands the linked IR to Larva.Driver.WasmBuilder.Build:

 linked IR program
        |
        +-- --target wasm -------> WasmBackend.Compile          (Larva.Wasm)
        |                             AddWrappers, Monomorphizer, WasmCodegen x2
        |                             WasmProgram.Write  -> NAME.wasm, NAME.js, NAME.html
        |
        +-- --target wasm-llvm --> ExecutableEntry.AddWrappers
                                   LlvmBackend.Compile (Triple = wasm64-unknown-unknown)
                                   EmitObject -> program.o (temporary folder)
                                   wasm-ld ... -o NAME.wasm program.o
                                   WasmBackend.Glue(abi "c64") -> NAME.js
                                   WasmBackend.Page            -> NAME.html

The -o you give names the JavaScript file; the .wasm and .html take the same name next to it. A project whose BUILD says target: wasm builds with the LLVM path, or with the own back end when its backend: is x64 (the "fast to compile" choice); its output gets the .js extension.

The three files

run(options) accepts args (strings), write(text) for output, error(text) for errors, readLine() for input (Node reads standard input, a page asks with prompt()), and module (the module's bytes, instead of fetching it). It returns { exitCode, error? }.

Run under Node, NAME.js passes its own command line, maps the result to the process exit code, and honours two environment variables: LARVA_GC_STRESS=1 (collect at every allocation) and LARVA_GC_THRESHOLD=n (collect every n allocations).

The entry follows the same rules as a native executable: up to four integer, bool or float arguments, and a result that is printed:

$ node num.js 12
144
$ node num.js
usage: program <arguments> (1 integer argument)
$ node oob.js
larva panic: index 5 out of bounds for length 3

A panic ends with exit code 101, an uncaught exception with 1 (larva: unhandled exception (type id N)), a wrong argument count with 2.

larva_rt.js: the runtime

Larva.Wasm/Runtime/larva_rt.js (about 800 lines, embedded in larva) is the WebAssembly counterpart of the C runtime larva_rt.c: it provides every larva_* function a module imports. One file serves both back ends; the two "code shapes" differ only in how addresses travel:

What it provides:

The heap and the collector

The heap lives in the module's memory above the static data (from __heap_base for LLVM, from stack_top for the own back end). It is made of 16-byte blocks taken from a bump pointer and reused by size. What the runtime knows about each block (its kind, size, reference count, region) is kept in typed arrays indexed by address / 16, and finalizers in a map.

Collection is a non-moving mark-sweep. Roots are found conservatively: any aligned word in the stack range, the globals or a live heap cell that holds the address of a live gc object marks it, and marked objects are scanned the same way. A collection is due once as many bytes of gc objects were allocated as survived the last one (at least 4 MB), or every LARVA_GC_THRESHOLD allocations. Reference counting and arena regions are also implemented, so every gc: mode that works natively works here (except custom, which works nowhere yet).

Because a WebAssembly program runs on one thread and the runtime collects only inside an allocation, there are no safepoints in WebAssembly code at all: LLVM's code generator is told not to emit polls, and the own back end never did.

Allocation without leaving WebAssembly

Calling into JavaScript for every allocation was the main cost of early LLVM builds. Now Larva.Llvm/Runtime/wasm_heap.ll (150 lines of LLVM IR, embedded in larva) is linked into the program before optimization whenever it allocates gc objects, so its fast path is inlined where the program allocates. It owns a global, larva_wasm_heap, that both sides read:

larva_wasm_heap (all i64): 0 cursor, 8 limit (the bump region), 16 since (bytes since the last collection),
24 budget (since >= budget: JavaScript decides; 0 sends every allocation there), 32 count (entries in log),
40 free[256] (heads by size in 16-byte units; a free block's first word is the next one), 2088 log[4096 x 2].

An allocation takes a block from the free list of its size, or from the bump region, and appends the new object's address and size to log. JavaScript reads the log before it looks at the heap (and clears it, since it lies in the globals the collector scans). Only the slow cases go to JavaScript (larva_js_gc_alloc, larva_js_gc_array, larva_js_array_new): a collection due, a full log, a large object, an empty region, or an open arena region. LARVA_WASM_HEAP=0 turns the inline heap off.

Soft floats and wide integers

The LLVM path compiles f16, f128, f256, i128 and i256, and the linked module imports the helpers it needs from env: larva_rt.js provides them. The float routines are a bit-for-bit port of Larva's soft-float code on BigInt: the five formats (16, 32, 64, 128 and 256 bits), rounding to nearest with ties to even, subnormals, overflow to infinity and a canonical quiet NaN. Wide values travel as 64-bit limbs in memory, lowest first. 128-bit multiplication and division (__multi3, __udivti3, …) take each operand as a (low, high) pair and write the result to memory. i256 needs no helper: LLVM expands it into 64-bit instructions.

import System;

into namespace Wide
{
	Main()
	{
		u256 big = 1u256 << 200;
		Console.WriteLine(big);
	}
}

$ larva build --target wasm-llvm -o widel.js wide.ant
widel.wasm, widel.js, widel.html (LLVM back end, O3, entry widel::Wide.$Module.Main)
$ node widel.js
1606938044258990275541962092341162602522202993782792835301376

These routines came late (the design notes' "Restoration 32"). wasm-ld leaves every helper LLVM calls as an import from env, and before the port a module that used f16, f128/f256 or 128-bit division failed when it was instantiated, because the runtime had only __multi3. The one remaining difference with native code: a NaN loses its payload when it goes through f16 (the canonical NaN is returned, as in the VM; compiler-rt keeps it).

The own back end: Larva.Wasm

Larva.Wasm writes the binary format directly, without LLVM, in the spirit of the direct x86-64 back end: a baseline compiler that is fast and simple.

Two passes

WasmBackend.Generate runs the code generator twice. The first pass records which runtime functions the code calls; the second builds the module importing only those. A program that prints numbers imports four functions:

0 env larva_array_new ('7e7f7f7f', '7f')
1 env larva_print_i64 ('7e', '')
2 env larva_print_line ('', '')
3 env larva_panic ('7f7e7e', '')

(7e is i64, 7f is i32.)

Design

• Frames in linear memory. Every IR local has a slot in a shadow stack that grows down from the global $sp. Every value has an address, so the collector finds every root by scanning the stack, conservatively, and nothing needs a stack map.
• One calling convention. Every Larva function has the type (args: i32, ret: i32) -> (): the caller lays the arguments out in its own frame and passes where they are and where the result goes. An indirect call (a function value, a finalizer) is then always a call_indirect of that one type through the exported table.
• A dispatch loop per function. Each function is a loop around a br_table on a state local, one state per basic block. This takes any IR control-flow graph as it is, with no need to rebuild structured control flow.
• Exceptions as globals. throw stores the payload cell and its type id in the globals $exception and $exception_type and goes to the site's handlers; after every call a pending exception does the same, or the frame cleans up and returns with it.
• Pointers are 32-bit in 8-byte slots (zero-extended), so struct layouts are exactly the native ones from Layouts.
• Scalars are canonical. Once loaded, an integer of up to 64 bits is held as an i64, extended according to its signedness; i128 and u128 are two 64-bit halves.

The memory layout:

 0        16           48     64                                       +1 MiB
 | null   | entry args | result | static data | globals | <- stack ... | heap (larva_rt.js) ->
                                             ^globals_start  ^globals_end = stack_limit
                                                             stack_top = sp at start ^

The module exports memory, table, the globals sp, exception, exception_type, stack_limit, stack_top, globals_start, globals_end, and every function whose name starts with larva_ (the entry wrappers). It uses the bulk-memory instructions (memory.copy, so it writes the data-count section) and the non-trapping float conversions.

The LLVM path: --target wasm-llvm

The LLVM back end compiles the program for wasm64-unknown-unknown: 64-bit memory, so pointers keep the 8 bytes Larva's layouts give them and the same IR works unchanged. What differs from native code:

The target features are +bulk-memory,+sign-ext,+nontrapping-fptoint,+mutable-globals, which every current browser and Node have. LARVA_WASM_FEATURES replaces the list. SIMD was tried and left out: its two-lane i64 loops ran slower in V8 than unrolled scalar code (a static-field benchmark 445 ms against 294 ms, a matrix one 381 ms against 310 ms).

LLVM writes an object file, and wasm-ld links it:

wasm-ld -mwasm64 --no-entry --allow-undefined --export-table --stack-first -z stack-size=1048576
        --gc-sections --strip-all -O2
        --export=larva_entry --export=larva_entry_f64 --export=larva_entry_info
        --export=larva_exception --export=larva_exception_type
        --export=__stack_pointer --export=__stack_high --export=__data_end --export=__heap_base
        --export-if-defined=larva_wasm_heap
        -o NAME.wasm program.o

--allow-undefined turns every runtime function into an import from env; --stack-first puts the 1 MiB stack below the data, so a stack overflow traps instead of corrupting globals.

wasm-ld is not shipped with Larva. WasmBuilder.FindLinker looks for it in this order: LARVA_WASM_LD (a path; if it does not exist, no other place is tried), wasm-ld on PATH, then C:\Program Files\LLVM\bin\wasm-ld.exe, /usr/bin/wasm-ld, /usr/local/bin/wasm-ld and /opt/homebrew/opt/llvm/bin/wasm-ld. Without it the build stops with no wasm-ld: install LLVM (it comes with it), or set LARVA_WASM_LD to its path.

Speed

From the design notes (Node 24, the same machine for every measurement):

• LLVM-compiled WebAssembly runs 3 to 12 times slower than the native LLVM executable. The causes found: V8 checks bounds on every memory64 access, roots live in memory rather than registers, and non-gc cells (larva_raw_alloc, larva_free) still go through JavaScript.
• The own back end runs 10 to 40 times slower than native: its convention passes every argument and result through memory, and every value lives in a frame slot.
• Compiling a program that exercises all of System.Core (after the 1.4 s that the frontend, lowering and IR checks take): the own back end in 0.9 to 1.0 s for 1,778 KB of WebAssembly; LLVM in 8.6 to 9.2 s for 839 KB (682 KB before the allocation fast path was inlined).

So --target wasm is for fast turnaround and --target wasm-llvm is for anything that runs.

Known gaps

The own back end emits invalid modules for many programs. Its code generator passes a raw pointer (*mut u8) argument of a runtime intrinsic as an i64, where the import expects an i32 address: it narrows only reference-typed arguments. System.Core copies string contents with mem.copy, so programs that build or print text, Hello World included, produce a module that Node refuses to compile:

$ larva build --target wasm -o hello.js hello.ant
hello.wasm, hello.js, hello.html (Larva back end, entry hello::Hello.$Module.Main)
$ node hello.js
[CompileError: WebAssembly.instantiate(): Compiling function #15 failed: call[0] expected type i32, found i64.load of type i64 @+3231]

Programs that only compute and print numbers or bools (the sum.ant above, the out-of-bounds panic) work. The same programs work with --target wasm-llvm.

Wide numbers in the own back end. It rejects some types and operations at compile time, with the function's name:

$ larva build --target wasm -o wide.js wide.ant
larva: `wide::Wide.$Module.Main`: `u256` is not supported by the WebAssembly back end

f128 and f256 could reuse the JavaScript soft-float routines the LLVM path already uses; the design notes list that as the next step.

One GC domain. larva_gc_domain always returns 0 in larva_rt.js: the own back end handles a single GC per program, and mixing GC domains is not supported on WebAssembly.

Threads, sockets and streams are stubs: a program runs on one thread, and network and stream functions fail with -1. Files work under Node only.

Environment variables