{"action":"created","issue":{"url":"https://api.github.com/repos/WebAssembly/binaryen/issues/663","repository_url":"https://api.github.com/repos/WebAssembly/binaryen","labels_url":"https://api.github.com/repos/WebAssembly/binaryen/issues/663/labels{/name}","comments_url":"https://api.github.com/repos/WebAssembly/binaryen/issues/663/comments","events_url":"https://api.github.com/repos/WebAssembly/binaryen/issues/663/events","html_url":"https://github.com/WebAssembly/binaryen/issues/663","id":169489052,"number":663,"title":"Future of Binaryen in a stack machine world?","user":{"login":"kripken","id":173661,"avatar_url":"https://avatars.githubusercontent.com/u/173661?v=3","gravatar_id":"","url":"https://api.github.com/users/kripken","html_url":"https://github.com/kripken","followers_url":"https://api.github.com/users/kripken/followers","following_url":"https://api.github.com/users/kripken/following{/other_user}","gists_url":"https://api.github.com/users/kripken/gists{/gist_id}","starred_url":"https://api.github.com/users/kripken/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/kripken/subscriptions","organizations_url":"https://api.github.com/users/kripken/orgs","repos_url":"https://api.github.com/users/kripken/repos","events_url":"https://api.github.com/users/kripken/events{/privacy}","received_events_url":"https://api.github.com/users/kripken/received_events","type":"User","site_admin":false},"labels":[],"state":"open","locked":false,"assignee":null,"assignees":[],"milestone":null,"comments":19,"created_at":"2016-08-04T22:34:42Z","updated_at":"2016-08-10T23:42:37Z","closed_at":null,"body":"The WebAssembly project recently decided to switch from being an AST to being a [stack machine](https://docs.google.com/presentation/d/1dRsN5lKY60d3IOILi4bttJXOX4ge-2tA1PaEX-d5So0/edit#slide=id.g156cf85f39_1_274). This issue is to discuss the implications of that for the Binaryen project, which is AST-based.\r\n\r\n**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\r\n\r\n * Fast compilation to the target, since almost no lowering is needed.\r\n * WebAssembly-to-WebAssembly optimization, as we can load it, optimize it, and write it.\r\n * 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.\r\n * 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.\r\n * ASTs are a reasonable optimization IR, allowing flexible optimizations to be written in nice ways.\r\n\r\nBut the foundations for all that are now in question with WebAssembly's pivot to a stack machine.\r\n\r\n**The first practical consequence** is that things in the WebAssembly MVP will not be expressible as an AST, e.g.\r\n\r\n````\r\ncall gimme-i32\r\ncall gimme-i32\r\ncall no-value-returned\r\ni32.add\r\n````\r\n\r\nThis 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](https://github.com/WebAssembly/design/issues/736#issuecomment-237402407) 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\r\n\r\n````\r\n(i32.add\r\n  (call gimme-i32)\r\n  (first\r\n    (call gimme-i32)\r\n    (call no-value-returned)\r\n  )\r\n)\r\n````\r\n\r\nThis 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.\r\n\r\n**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.\r\n\r\nThe 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.\r\n\r\n**Options** include:\r\n\r\n * **Deprecate Binaryen**: Consider a fresh start in another toolchain project, or shift efforts to an existing one.\r\n * **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.\r\n * **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.\r\n * **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.\r\n * **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.\r\n\r\nMore details on the stop-consuming-WebAssembly option:\r\n\r\n * Binaryen would be a compiler to WebAssembly and nothing more: not a WebAssembly interpreter, not a WebAssembly linker, etc. etc.\r\n * 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.)\r\n * 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`?).\r\n * 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.\r\n * 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.\r\n * 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](https://github.com/kripken/emscripten/wiki/Emterpreter) replacement.)\r\n * 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.\r\n * `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.\r\n * 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.\r\n * 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).\r\n\r\nAs 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.\r\n\r\nThoughts?\r\n"},"comment":{"url":"https://api.github.com/repos/WebAssembly/binaryen/issues/comments/239037786","html_url":"https://github.com/WebAssembly/binaryen/issues/663#issuecomment-239037786","issue_url":"https://api.github.com/repos/WebAssembly/binaryen/issues/663","id":239037786,"user":{"login":"JSStats","id":11826073,"avatar_url":"https://avatars.githubusercontent.com/u/11826073?v=3","gravatar_id":"","url":"https://api.github.com/users/JSStats","html_url":"https://github.com/JSStats","followers_url":"https://api.github.com/users/JSStats/followers","following_url":"https://api.github.com/users/JSStats/following{/other_user}","gists_url":"https://api.github.com/users/JSStats/gists{/gist_id}","starred_url":"https://api.github.com/users/JSStats/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/JSStats/subscriptions","organizations_url":"https://api.github.com/users/JSStats/orgs","repos_url":"https://api.github.com/users/JSStats/repos","events_url":"https://api.github.com/users/JSStats/events{/privacy}","received_events_url":"https://api.github.com/users/JSStats/received_events","type":"User","site_admin":false},"created_at":"2016-08-10T23:42:36Z","updated_at":"2016-08-10T23:42:36Z","body":"@kripken A fundamental problem with this plan is that it still does not address multiple values. Development needs to more forward, develop a counter proposal that addresses the issues, rather than just resisting development and shuffling the chairs. People care about wasm because it is a deployment platform.\r\n\r\nI think the general point you are making about the disconnect between the language that producers want to easily emit and the twisted stack machine constraints is a key point. The same was seen with the x87, a numerical stack machine, where compilers just wanted to connect inputs and output but had to work around frustrating stack machine constraints, and to optimize for these constraints, and and to be able to annotate where values were for debugging. The `pick` operator helps a little as it can access values in general up the stack, but if the requirement that a block stack be empty except for the out values stands then this will require really frustrating `swap` and `drop` sequences to clean up the stack.\r\n\r\nIf wasm is just a target, and not optimized for code size, then the expressionless register based code is much simpler for producers."}}
{"actor":{"display_login":"JSStats"}}