Future of Binaryen in a stack machine world?

[kripken]

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?

Can you give an example of stack-machine code that can not be expressed (with only encoding loss) in a structured AST? There might not be any such examples, given that dropping stack elements is currently constrained to block boundaries.

An explicit block1 was considered some time ago see WebAssembly/design#650 As you note if it is explicit then it does not solve the problem as using it changes the code. While the text format might use it just for presentation, what if people use it in excess and this still need to be encoded. Also this is still limited to structured uses in the scope of the block.

But this can not express multiple uses of the function results, and does not work for functions returning multiple values in general. A general solution is needed, and I appeal to people to solve the general case first then optimize it for high frequency cases.

The example could also be presented as the following:

(letc (($c0 (gimme-i32))
       ($c1 (gimme-i32)))
  (no-value-returned)
  (i32.add $c0 $c1))

And when people code references to these local constants that do not fit the stack usage pattern they would simply be encoded with get_value aka pick/pick_and_void. We could also move the function arguments onto the stack. Why not consider this proposal, it was communicated some time ago yet seems to have been ignored and there has been no rationale given?

The other option is the 'Stop consuming WebAssembly' option but I would look at it from a different perspective and view it as conceding that the wasm binary code is just a compressed encoding of the language that developers will actually work with and that the language that binaryen consumed would be the wasm text format and debugging would step through that code not the stack code which would be a throwaway intermediate encoding, just as debuggers do not step through compressed encodings. This would focus on the SSA decoded format, which is really what this is all about, and it might be better for analysis and transforms, but distant from the stack machine code. This would be a last-resort strategy, working around the product of the wasm group, but why should the group be in such a position, it is our group.

[dschuff]

In the past we've kicked around the idea of defining a flavor of wasm (an IR, if you like) which is not exactly wasm but more natural for many compilers to produce (aka a producer-oriented/subwasm/flat wasm). What you are describing as Binaryen's new non-isomorphic IR sounds a lot like that in some respects. As you have observed, Binaryen would then be a one-way tool (at least the compiler part would be; obviously from the user perspective Binaryen has always been a loosely-related collection of tools; e.g. we could still have wasm-as and wasm-dis if we wanted to, they would just not use the same IR).

I think you are basically correct about the consequenses of moving Binaryen to this style of IR. Presumably it would evolve a bit (since it doesn't have to precisely track the current flavor of wasm we could rethink pain points that exist or as we find them), and libbinaryen (C API, optimizers, etc) would track this evolution.
For s2wasm it would depend on what we wanted to do with LLVM; we could make LLVM target the "flatwasm" IR if we wanted to. Moving the compiler part of LLVM fully to a non-wasm IR might have interesting consequences for linking formats and the other parts of LLVM, but that's a decision we can make independently of what we want Binaryen to be.

Practically speaking, we may choose over some near-term period to keep on trucking and paper over the differences while we work out what we want the end product to be.

[kripken]

@JSStats: what you're suggesting sounds more like for the WebAssembly design than for Binaryen? This issue is just for Binaryen responding to a WebAssembly change.

@dschuff: I agree that trucking on for a while sounds reasonable, but it's not quite that easy. I've been working towards that in the (increasingly misnamed ;) since it's all about stack now) land-drop branch, and it's been quite a lot of work so far. In addition, it looks like we'd need to rewrite our s-expression parser from scratch. If it's indeed the case that this is a significant amount of work, it seems unwise to do it only to likely get rid of it later - so it makes sense to focus on the change in direction now.

[dschuff]

That makes sense; If we do want to just go toward a new IR, we do have sexpr-wasm-prototype which can take the role of binary encoding, decoding, and standalone interpretation. Then the IR can be designed for ease of production from whatever class of compilers we care about, and for wasm-specific optimizations.

[kripken]

Yeah, sexpr-wasm-prototype is perfect for that, it has a proper stack-based interpreter in fact. And I think I saw @binji already has a web port so it could be used as a clientside polyfill (if not I'd be happy to help with that).

I think in the forked-IR path, if we go that route, binaryen might still end up with some wasm import facilities, but they might not be lossless. For example a "wasm2byn" could handle patterns that can't work in an AST by introducing new locals (sort of like the project whose name escapes me that translates wasm into LLVM IR in the sense that it's also not meant to be lossless). And of course we can emit wasm, so optimizing wasm to wasm in binaryen might still be useful, although that's an open question.

[kripken]

I am leaning more in the forked-IR direction. I considered in more detail the option of rewriting binaryen to use a single stack-based IR, but I just don't think it makes sense. The original design principles still relevant are

• A single main IR has major simplicity and efficiency benefits.
• That single main IR should be transformable so we can run optimization passes on it. (Without this requirement, the single main IR could just be the wasm binary format.)

But doing those with a stack machine IR seems very hard. On the one hand it's true that some optimizations are easy to write (e.g. removing dead code) while others become possible (stack-machine specific things). But on the other, consider a simple pass that reduces eqz(gt(x, y)) into lte(x, y) (i.e. !(x > y) into x <= y, which is true on integers). Right now in our AST an eqz node has a pointer to the child node. In a stack machine, options are

• No child pointer. The child is then defined by the location in the array, and might be right before the parent, but also might not be (and even trickier with more than one child).
  • Optimization passes would therefore need to maintain an expression stack, and every optimization pass would need to consult that data structure for child operations. This might not be so bad when traversing in the natural direction, but anything else (other orders, random access, etc.) become tricky.
  • Code receiving a pointer to a node must also receive a "context" pointer to the array, as the node by itself is no longer enough (in our AST right now, we've intentionally made it so a node pointer is always enough; in fact expressions stand on their own even without knowing the module, which makes function parallelism trivial).
  • On the other hand, not having a child pointer would make each node smaller, which is a significant upside. But nodes would still need a "next" pointer (forming a linked list) if we want it to be efficient to move nodes around, insert them, etc., which seems like a strong requirement. So this would only help when the number of child nodes is >1. Still significant, but less.
• Have a child pointer. This means
  • Node sizes strictly increase compared to our current AST, given the "next" pointer.
  • Each modification of the code needs to be updated in two places, the linked list and the child pointers, which adds overhead compared to now and also introduces bug risk.

[qwertie]

@kripken Do you know what the decision-making process is for WebAssembly? I'm increasingly getting the feeling that major decisions are made in private discussions behind closed doors, or other unknown places, with little important discussion happening in the design repo. Did the change to a stack machine catch you by surprise as well?

Based on what I know so far (which is no doubt less than what you know), "Keep on trucking, for now" looks like the best option (for now), because

• I don't know if the stack machine is a final, irreversible decision.
• It looks like there are AST equivalents for the new stack machine semantics (have you discovered anything in the stack machine that can't be expressed in AST form with a new operator like 'first'?)
• By maintaining an AST form for Wasm code, you maintain knowledge about the two-way isomorphism between AST and stack machine. I think that's just useful knowledge from an academic perspective. It could be useful to other engineers in the future and useful to the computer science field.
• Converting stack-based wasm to an AST is a potentially useful feature to many people. By keeping this ability, you reduce the need for people to migrate to other tools, making your tool more popular and by implication, you yourself ;)
• It is probably easier to adapt gradually to the changes in Wasm as they happen. We're predicting certain things in the future like a pick operator and multi-values, but we don't know that these will actually happen in the form currently being considered. I think before ripping out functionality or engaging in a major rewrite, you should be certain it is necessary.
• (edit) As you mentioned, ASTs seem easier to work with for some common optimizations.

This puts us in the uncomfortable position of optimizations needing to take into account that more AST nodes might mean less code size

Are "virtual" nodes really uncomfortable in terms of code complexity, or it is mainly uncomfortable psychologically? If it's the latter, I think you'll get used to it after awhile.

[qwertie]

I am leaning more in the forked-IR direction.

If "forked-IR" means "an AST-based IR that is very similar to, and easily convertible to, the Wasm stack machine, such that arbitrary Wasm stack-machine code can be converted easily to the IR," it sounds like a good plan to me. It's even better if Wasm-to-IR-to-Wasm and/or IR-to-Wasm-to-IR are (guaranteed to be) lossless roundtrips.

[kripken]

@qwertie: Yes, I was taken by surprise by the stack machine change. And from what I've seen online and off I was the only browser-vendor person that opposed it. And you can see work going on for it (e.g. in the spec repo). So for better or for worse, I think it's safe to assume it's happening, even if nothing is truly final until it lands, is specced, and ships.

there are AST equivalents for the new stack machine semantics (have you discovered anything in the stack machine that can't be expressed in AST form with a new operator like 'first'?)

Yes, a "first" can solve the current issues, with some awkwardness, but as discussed above multi-values are almost certain to happen, and "pick" and others seem very possible. It's clear the awkwardness for an AST will increase.

By maintaining an AST form for Wasm code, you maintain knowledge about the two-way isomorphism between AST and stack machine. I think that's just useful knowledge from an academic perspective. It could be useful to other engineers in the future and useful to the computer science field.

I agree and those are some of the reasons I opposed WebAssembly moving to a stack machine. (My main reason is the negative implications for the text format.)

Converting stack-based wasm to an AST is a potentially useful feature to many people.

I agree, and I think we might still support a form of that, but it wouldn't be lossless. For example, a wasm2binaryen tool might use additional locals for stack machine code we can't directly represent.

Are "virtual" nodes really uncomfortable in terms of code complexity, or it is mainly uncomfortable psychologically? If it's the latter, I think you'll get used to it after awhile.

I think there is a fundamental issue here. The optimizer currently has some useful principles like

• AST nodes ~ work. That makes it easier to write optimization passes. In particular, it is obviously the "right thing" in most cases to replace some AST nodes with a smaller number of AST nodes.
• Removing AST nodes is good. And not just individually as implied by the previous point: if optimization passes decrease the number of nodes, we have a good guarantee of repeated optimization reaching a fixed point (sort of like a loss function in gradient descent or a Lyapunov function in differential equations; i.e., we have a monotonically decreasing function in the number of nodes, and it can't decrease forever, so we must halt).
• The same points also apply when replacing "work" with "code size", i.e., when optimizing for size over speed.

Now, there are exceptions to those principles. For example, a block does no work by itself, e.g. (block (block ..) x) is the same as (block .. x). So we lose the "AST nodes ~ work" property. But we do still have the principle that decreasing AST nodes is good (for AST size and code size). Another example is that some math operation might be faster with more nodes, like say turning an integer divide by a constant into a sequence of shifts and adds. That violates the first two principles, so the optimizer has to be careful about it. In this case, we can just not do the reverse of that operation, but it does mean we need to keep that in mind when writing additional integer math optimizations. At least, though, the third principle remains in that more AST nodes means more code size, so we clearly know not to do it when optimizing for size.

The problem with "first" is even trickier in that all three of those principles are no longer true: adding such nodes can reduce output code size and work, but the opposite is true in other cases. So we can't just not do the inverse, and it isn't trivial what to do when optimizing for size, and so all optimization passes that remove or create "first"s must be coordinated. Now, of course this isn't an insurmountable problem. But it (and multi-values, and pick, etc.) add complexity and awkwardness to our optimization IR, and not just in a few places. An AST is just not a good 1-to-1 IR for such stack machine code.

If "forked-IR" means "an AST-based IR that is very similar to, and easily convertible to, the Wasm stack machine, such that arbitrary Wasm stack-machine code can be converted easily to the IR,"

No, sorry, the name might be confusing. Forking here means that we diverge from WebAssembly by not adopting the stack machine elements that are awkward in our AST. A better name might be "only output wasm", as it implies wasm is only our output format, while the forked IR is our input format, internal IR, binary and text format, etc. But the direction of Binaryen IR => WebAssembly would remain a very easy and fast operation, of course (since we would be pretty much a subset of WebAssembly).

[qwertie]

OIC - "~" means "varies proportionally with". Aka x α y...

It seems to me you can model most of this with a per-node weight - say, most operations have weight 1, multiplications have weight 2-ish, divisions have weight 10-ish... and you can define three weights, one for "optimize for speed", one for "optimize for size" and one for "balanced". If an algorithm needs positive weights, that's okay: it might be better to give first a weight of 0.001 rather than 0 since w; x; y + z has the (small) virtue of being easier to understand than w; first (y, x) + z. On the other hand, another optimizer might have chosen w; first (y, x) + z intentionally, let's say because w might modify memory read by x... anyway, I've never written optimizers so I'm probably not helping :)

I see that multi-values are likely to happen as currently envisioned because they seem easy for the back-end to support. But local variables do everything we would use pick for, so I think it'll be awhile before they consider that - unless they eliminate local variables entirely (a slightly horrifying thought).

FWIW I support your opposition to the stack machine, or at least I think there should be a closely-related AST variant of Wasm for the text format and for binaryen. I recognize the (small) value of the stack machine in the final back-end, but still wonder if there's some way to achieve a similar benefit in the AST paradigm (I'm cursing myself for not having found the time to learn Wasm better, otherwise I'd love to investigate this.)

It sounds like you weren't really consulted about this decision, but do you know what the decision-making process is?

@kripken A sketch of a single pass stack-machine to text format algorithm is at WebAssembly/design#753 This does not use a first operator, rather lexical constants, which would seem to work with the current proposal in the stack-machine to text direction, but be fragile in the other direction without the pick operator. Perhaps you can work it into something concrete, or if you find any show stoppers or loss then please report it so it can be understood and pondered. You could explore the utility of the pick operator, which would probably eliminate a lot of local variables.

[kripken]

OIC - "~" means "varies proportionally with". Aka x α y...

Yeah, sorry, I should have been more clear.

It seems to me you can model most of this with a per-node weight [..]

Yes, but the issue is that "first" would need to have a negative weight in the context of code size. That's already troubling, but in addition, even that isn't true as the weight depends on the surrounding code, it shouldn't be negative in other cases, so it doesn't even have an intrinsically definable weight.

But local variables do everything we would use pick for, so I think it'll be awhile before they consider that

It might be a while, but I hope it'll happen at least for the text format: with pick you can avoid oddities like a let variable that can only be used once and in certain places.

do you know what the decision-making process is?

I don't know that there is anything formal written up. For the informal stuff I'm not sure since I'm not very good at politics ;)