A compiler in two dispatches

I had a two-pass GPU compiler whose second pass interpreted the first pass's output. It worked, but the result disappeared with the interpreter. I wanted the shader to leave behind a program the rest of the browser understood, so I made the second dispatch write a WebAssembly module byte by byte.

That turns compilation into a layout problem. The first dispatch reads as many as 256 UTF-8 source bytes, classifies the eight Brainfuck characters, and uses a prefix scan to compact them in source order. Comments finally matter here: they enter the GPU buffer and vanish during the scan. One lane then checks the compacted brackets and reports the opcode array's length.

Every command knows its width#

Parallel emission works because each command has one fixed binary template. The compiler deliberately skips run folding and peephole rewrites. The current WebAssembly binary format gives every template a known byte count before anything is written.

Dispatch two scans those lengths. A lane subtracts its own length from the inclusive sum to find its starting offset, then copies its template into that slot. The writes can happen together because the slots cannot overlap.

// dispatch 2: one lane per compacted commandif (lane < count) { op = ops[lane]; len = TPL_LEN[op]; }scan_values[lane] = len;workgroupBarrier();// eight synchronized scan steps produce the running byte total// lane zero writes the header and publishes code_start hereworkgroupBarrier();if (lane < count) {  let base = code_start + scan_values[lane] - len;  for (var k = 0u; k < len; k++) {    wasm_out[base + k] = TPL[TPL_OFF[op] + k];  }}

Lane zero handles the serial framing: magic bytes, types, imports, memory, exports, and the code-section lengths that depend on the scan total. This shader declares its output buffer as an array of u32, so it stores one module byte in each word and the host packs them after readback. Both compute passes share one command buffer.

The reference goes first#

The page always compiles a CPU reference before asking for a GPU. That reference catches syntax errors, renders the WAT shown in the lab, and supplies the exact bytes used to grade the shader. The host records any WebGPU error or first differing byte, then chooses the matching GPU module or the reference copy.

const reference = compileBrainfuck(source); // built first, on the CPUconst sourceBytes = new TextEncoder().encode(source);const gpu = await compileToWasmOnGpu(runtime, sourceBytes);const mismatch = byteMismatch(reference.wasm, gpu.wasm);const wasm = gpu.error === 0 && mismatch === null  ? gpu.wasm  : reference.wasm;const { instance } = await WebAssembly.instantiate(wasm, imports);instance.exports.run();

The module imports read and write. End-of-input returns the current cell, which is the convention used by the included programs, and a fuel global traps a loop that consumes its budget. The expandable WAT is CPU-rendered, omits that fuel machinery, and describes the reference module. The host checks the executable bytes directly in binary form.

The current 256-byte ceiling comes from assigning one source byte to each lane in a 256-lane workgroup. Fixed templates make the scan possible. A larger parallel version could tile the source across multiple workgroups and add another scan level, with bracket balance carried across tile boundaries. I have not built that version.

The lab reports source bytes and commands separately. Its first timer covers compilation and, on the GPU path, byte verification. The second covers instantiation and execution. The old single label timed only the last part, which looked tidy and was wrong.

Try the commented source as well as the compact samples. Browsers without the WebGPU API still use the CPU emitter and runtime boundary, so the same samples remain runnable there.

ROT13 is 190 source bytes and produces a 2,225-byte module. On the GPU path, its first timing includes the CPU reference, both dispatches, readback, and the byte comparison. The first click also includes adapter, device, and pipeline setup. The lab starts the second timing when the browser instantiates the chosen bytes and leaves both numbers visible.

The first time the comparison returned no differing offset, I checked the output buffer anyway. The first four output words held 00 61 73 6d. Lane zero had placed that magic number beside the rest of a program assembled by a graphics device.