Future of Binaryen in a stack machine world? · Issue #663 · WebAssembly/binaryen (original) (raw)

The WebAssembly project recently decided to switch from being an AST to being a stack machine. This issue is to discuss the implications of that for the Binaryen project, which is AST-based.

History: Binaryen's initial design and goals were simple: WebAssembly was an AST. By building a compiler that uses that AST as its internal IR, we could stay very close to our output format, which allows

• Fast compilation to the target, since almost no lowering is needed.
• WebAssembly-to-WebAssembly optimization, as we can load it, optimize it, and write it.
• Using WebAssembly as our IR means optimizations very specific to WebAssembly are easy to express (e.g., block return optimizations), which generic compilers might find harder to do.
• ASTs are convenient as an input IR, allowing compilers to WebAssembly to use Binaryen as their backend. The asm2wasm and mir2wasm projects are examples of this.
• ASTs are a reasonable optimization IR, allowing flexible optimizations to be written in nice ways.

But the foundations for all that are now in question with WebAssembly's pivot to a stack machine.

The first practical consequence is that things in the WebAssembly MVP will not be expressible as an AST, e.g.

call gimme-i32
call gimme-i32
call no-value-returned
i32.add

This stack machine code does two calls to get i32s, then a void call. The void call is not placed on the stack, and the add adds the i32s. In an AST that order of operations is not directly expressible, although a "first" or "reverse-comma" operator can work, <x, y> where x is done, then y, and then x is returned (which is the opposite of the comma operator in C, JS, etc.). So we can write

(i32.add
  (call gimme-i32)
  (first
    (call gimme-i32)
    (call no-value-returned)
  )
)

This technically works, but is awkward. In particular, the "first" operator vanishes when actually emitting WebAssembly. This puts us in the uncomfortable position of optimizations needing to take into account that more AST nodes might mean less code size. And the obvious simple IR for such optimizations is just the linear list of stack machine instructions.

That's just the beginning: A major justification for the stack machine approach is multi-values, which are not in the MVP but will be added later. As with "first", technically one could invent some AST construct, but it's awkward. Further possible future features already showing up in discussions include pick (copy a value from up the stack) and other stack machine tricks. It's clear that WebAssembly is moving in a direction that Binaryen's initial design is just not a good fit for.

The bottom line is that Binaryen was designed based on what WebAssembly was at the time. It seemed like an elegant approach to use the WebAssembly AST as a compiler IR. That tied Binaryen's internals to the WebAssembly design, which was a risk, but it paid off - until now, as WebAssembly has pivoted. So we need to decide what to do.

Options include:

• Deprecate Binaryen: Consider a fresh start in another toolchain project, or shift efforts to an existing one.
• Keep on trucking, for now: Add "first", and add other things later, despite Binaryen getting less effective at its purpose over time. The maintenance burden will rise as the IRs get more incompatible. This delays what I suspect is the inevitable.
• Redesign Binaryen (1 IR): Switch to a stack machine IR. That would entail an almost complete rewrite, so it's not much different than the deprecate-binaryen option.
• Redesign Binaryen (2 IRs): Add a stack machine IR alongside the AST. This seems very complex and risky, especially if the IRs are meant to be bidirectionally translatable, which is necessary if we can still both consume and emit WebAssembly.
• Stop consuming WebAssembly: Keep the current AST, but it would be the "Binaryen IR" and no longer WebAssembly. This is sort of like forking the IR: WebAssembly is going in a stack machine direction, but the Binaryen IR is not following it there. Binaryen IR would be isomorphic to a subset of WebAssembly, but no more. In particular, this means we would no longer consume WebAssembly, we would only be able to emit it.

More details on the stop-consuming-WebAssembly option:

• Binaryen would be a compiler to WebAssembly and nothing more: not a WebAssembly interpreter, not a WebAssembly linker, etc. etc.
• Binaryen's IR would not be able to express all of WebAssembly directly. We would have an output layer that can translate that into WebAssembly. Since we would be a subset of WebAssembly, that should be a simple process, with little changes to our current code. In the short term we just wouldn't emit code not isomorphic to an AST (i.e. we would emit a subset of WebAssembly), but perhaps in time we could have our WebAssembly output layer emit stack machine-specific patterns as a final-layer optimization. (So we might eventually have 2 IRs, but not bidirectionally translatable ones.)
• Binaryen's AST would stay representable in text format in the current s-expression format. As that format will likely end up being changed for the stack machine, this means forking the s-expression format, into something I guess we can call "Binaryen's IR text format". We would fork the spec test suite and add it to the Binaryen test suite. wasm-shell would run those tests, and should be renamed to binaryen-shell (or byn-shell?).
• Binaryen's wasm-opt tool would be renamed binaryen-opt (or byn-opt?) as it would operate on Binaryen IR, not WebAssembly. Binaryen would stop being a wasm-to-wasm optimizer, which was a goal we thought could be useful for other projects - we would be dropping that goal.
• Binaryen's wasm-as, wasm-dis tools would likewise be renamed as they would operate on a Binaryen binary format. In other words, as with the s-expression format, this would be a fork, of the binary format. Note also that this means that Binaryen would no longer be a tool people can use to disassemble and assemble wasm files for toolchain purposes.
• Binaryen would still have an interpreter - in fact some optimization passes, like Precompute, need one - but it would be a Binaryen IR interpreter and not a WebAssembly interpreter. (Perhaps useful as an emterpreter replacement.)
• No changes to asm2wasm and mir2wasm, as Binaryen's IR and C API are not changing. There should be no downside whatsoever for those compilers, and in particular not for the entire emscripten-asm2wasm path for compiling C++ to WebAssembly, which already works now.
• s2wasm is tricky since its input is basically WebAssembly. We would need to modify or replace it, in tandem with the wasm backend. Several options here, with varying amounts of work.
• No more wasm.js or binaryen.js, which could execute WebAssembly in JS for polyfilling purposes. You might say that wasm.js fulfilled its purpose of helping the toolchain side before JS engines got proper wasm support, and at this stage, we don't need it as much. So that is probably not a big deal. For binaryen.js, it could no longer work as a (slow) client-side polyfill for WebAssembly, but other interpreters could be compiled instead.
• The bottom line is that Binaryen would be refocused from a general-purpose WebAssembly compiler and toolchain library - trying to do everything in that space - to a far more narrow niche of a specific compiler library for WebAssembly (that uses an AST designed to be isomorphic to a subset of WebAssembly).

As you can see from the amount of text, the stop-consuming-WebAssembly option is the one I've thought most about. Not because I like it necessarily, but because all the other options have downsides that worry me a lot more. But I have no definite opinion on any of this yet, hoping to hear what other people think.

Thoughts?