Why does WebAssembly need the relooper algorithm, instead of gotos? (2019)

* Who wrote this article?

* When was this written?

Was lucky to find this pieces of information in Github [1].

1: https://github.com/Vurich/troubles.md/blob/master/content/po...

Since the release of this article, I wrote a blog post explaining how Stackifier works, for those who are interested:

https://medium.com/leaningtech/solving-the-structured-contro...

I am partly responsible for why WebAssembly is this way. You can thank/blame me for the if-else bytecodes. They are indeed, a form of compression, as they don't add expressive power. I measured carefully and they make a big difference in code size. That's why they're there!

The structured control flow requirement is to benefit all consumers. It is only a burden on producers that come from CFGs, not from ASTs and other tree-like IRs. If you have a dominator tree, then you can generate structured control flow in linear time. LLVM does this a particular way, but there are straightforward algorithms.

No, this wasn't Google throwing around its veto power or something like that. There is a good reason why control flow is structured, as hinted in comments here.

1. Structured control flow rules out irreducible loops. Irreducible loops cause problems for all JIT compilers in all browser engines, not just V8, and even in JVMs. Things get really complicated, particularly in register allocation. [1]

2. Structured control flow guarantees a stack discipline for the use of labels, mirroring the stack discipline for values. This is not only a nice symmetry, it means that a consumer that needs to allocate space per label can reuse that space as soon as a control construct is closed. That is essentially optimal for use of consumer space resources.

[1] No kidding. If you have an irreducible loop in Java bytecode, which is possible, you will never be JITed and will get stuck running 100x slower in the interpreter. We thought this through very carefully in V8. If you allow irreducible loops in Wasm, you force all engines to either stick to their lowest execution tier and run 2-100x slower, do relooping themselves, or handle the general case of irreducible loops spending multiple person-years complicating their optimizing tiers' backends for a case that is incredibly rare (and probably introducing lots of bugs). In V8 we would have probably gone for the relooper option because the other two options are bad. So that's a lose, because now the engine is more complicated, doing a rewrite of the code that could as well be done better and more efficiently offline by a producer. And there is no benefit because the engine's code would be no better than what the producer would have come up with. So we'd choose the lesser of the complexity options, but get no performance benefit, in order to avoid the absurdly bad performance hit of not being able to use the optimizing tier. Bad tradeoff now matter how you slice it, IMHO.

I am fully convinced we made the right choice here.

We should have communicated better and the relooper algorithm and tools should textbook, off-the-shelf stuff.

https://github.com/albertz/PyCParser/blob/080a7b0472444fd366...

Without reading the remainder of the article, this would seem to undermine any further assertions.

UPDATE: after reading the article, it seems the opposite is being shown. my bad.

Reasons: * True polyglotism * existing, feature complete implementation * compatibility with the existing JVM platform, and through polyglotism compatibility with almost any platform/library.