WebAssembly Is Not a Stack Machine (2019)

Discussed at the time (with comments from one of the designers of WASM): <a href="https:&#x2F;&#x2F;news.ycombinator.com&#x2F;item?id=19069587" rel="nofollow">https:&#x2F;&#x2F;news.ycombinator.com&#x2F;item?id=19069587</a>

It’s misleading to say that register machines carry no liveness or that they defeat liveness. That’s a bit much. Computing liveness on a register machine with dense integer numbering of locals is not that expensive. It’s certainly cheaper than running a good backend. And a good backend will certainly modify the code in a way that requires liveness to be recomputed.<p>It’s also misleading to say that register machines defeat SSA. It’s not hard to convert from a register machine to SSA - the algorithm is almost linear. Powerful backends (like WK’s B3) recompute SSA after some transformations anyway.<p>I think that wasm combines elements of a stack machine and a register machine in a way that leads to a compact format and multiple reasonable paths to converting to the sort of IR you’d want for converting a platform agnostic form like wasm into any contemporary instruction set. I’m no wasm fanboy but as far as binary IRs for transporting code into optimizing compilers go, this one is pretty slick.

Looks like the proposal to fix this was merged into the standard in April.<p><a href="https:&#x2F;&#x2F;github.com&#x2F;WebAssembly&#x2F;multi-value" rel="nofollow">https:&#x2F;&#x2F;github.com&#x2F;WebAssembly&#x2F;multi-value</a>

The changes noted for future: loop counters as arguments, returning multiple arguments sound a bit like re-inventing the Forth VM, which does things this way. Might not hurt to review some papers in that sphere that may have walked this ground before. (?)<p><a href="https:&#x2F;&#x2F;www.researchgate.net&#x2F;publication&#x2F;2414672_A_Preliminary_Exploration_of_Optimized_Stack_Code_Generation" rel="nofollow">https:&#x2F;&#x2F;www.researchgate.net&#x2F;publication&#x2F;2414672_A_Prelimina...</a>

I&#x27;m not sure the timeline described (&quot;only at the last minute did it switch to stack-based encoding for the operators&quot;) is accurate, but it is the case that for a while we were working towards more of a register-oriented encoding instead of the stack oriented one that shipped. The representation of trees and operands was also different. I think what ultimately shipped was probably right, but the semantics described by the article for blocks are incredibly gross and if I had known about them I would&#x27;ve blocked them. The author&#x27;s conclusion that this is due to wasm&#x27;s asm.js-derived heritage is accurate (also, arguably the &#x27;lots of locals&#x27; model was unavoidable since everyone was compiling wasm using JS runtimes anyway.)<p>Incidentally this claim is false: &quot;No streaming compiler had yet been built, hell, no compiler had yet been built.&quot; Early in development we had at least two different compilers used to generate test cases - one compiler for a home-grown imperative language written by Nick Bray, and another compiler for a subset of C# that I wrote [1]. Having those two compilers generating code early on was useful given that neither emscripten or LLVM were capable of compiling real apps so we were flying blind without them. Development of LLVM integration also started <i>very</i> early, the problem is just that it took a long time until it was usable.<p>As for whether the lessons from those compilers were actually paid attention to or acted upon, well...<p>P.S. I still don&#x27;t understand the reasoning behind &quot;blocks have return values&quot;. Does any popular programming language out there do this except maybe some of the ML-derived ones? I&#x27;ve never run into it in production software. It&#x27;s certainly not something a typical compiler would generate unless the source language had it as a primitive.<p>1: <a href="https:&#x2F;&#x2F;github.com&#x2F;kg&#x2F;ilwasm&#x2F;blob&#x2F;master&#x2F;third_party&#x2F;tests&#x2F;Raytracer.cs" rel="nofollow">https:&#x2F;&#x2F;github.com&#x2F;kg&#x2F;ilwasm&#x2F;blob&#x2F;master&#x2F;third_party&#x2F;tests&#x2F;R...</a>

It seems to me that this is only a problem when you try to write wasm directly. If you compile from rust then this analysis is already done for you on a higher level. or what am i missing?

The block argument and multiple return value proposal is a very good proposal. <a href="https:&#x2F;&#x2F;github.com&#x2F;WebAssembly&#x2F;multi-value&#x2F;blob&#x2F;master&#x2F;proposals&#x2F;multi-value&#x2F;Overview.md" rel="nofollow">https:&#x2F;&#x2F;github.com&#x2F;WebAssembly&#x2F;multi-value&#x2F;blob&#x2F;master&#x2F;propo...</a><p>Any idea how likely is this to make it in to the spec?

Always write an implementation first - and make it a good one. Then derive a standard from it.<p>&quot;Oh, but the implementation details will leak through!&quot;<p>So what? This is an ivory-tower concern. When you are designing a standard, you <i>must</i> have your mind on possible implementations, which is far more difficult without having created an actual implementation. You can&#x27;t design in a total vacuum, otherwise your standard can&#x27;t be implemented properly at all.