3 ms·

Real question. Most of the wasm instructions are very low level (eg, the test and branch are different, similar to assembly). But then when you get to the con

Real question. Most of the wasm instructions are very low level (eg, the test and branch are different, similar to assembly). But then when you get to the control flow constructs they went in the this weird direction. There is no goto, some of the instructions (br) are context dependent, and if the wasm JIT tries to inline anything it has to muck with the br operand (not even the worst of it). The looping constructs are just odd too. When I last checked you couldn't even do basic blocks with a control flow graph like most other compilers (so that also means no jump threading optimizations, and without goto you would have a hard time optimizing at the wasm generation level). It just seems like this part of the instruction set was developed by somebody who wanted some weird higher-level asm, but others wanted an asm close to the instruction set. Just seems like a really bad decitions. Is there a reason for this or has this been cleaned up at all?

naikrovek 7y ago
No "goto" means no JUMP instruction, right? I mean I guess that's still Turing-complete, but it seems like that would make things a lot more difficult than necessary. I would love to know the answer to your question
- jnordwick 7y ago
  also no conditional jumps (equivalent to jnz, jeq, etc...) instead of uses this weird br_if that can only go to places on the control flow stack.
Rusky 7y ago
That was done entirely on purpose, to make validation simpler. It does make things harder for compilers that want to support irreducible control flow, but the workaround is a single "relooper" algorithm that doesn't really fundamentally change how those compilers work. It is possible that in the future this will be relaxed (without giving up on the benefits for validation) via something like this: https://github.com/WebAssembly/funclets https://github.com/WebAssembly/funclets
- deleted 7y ago
  [deleted]
- FullyFunctional 7y ago
  It's not just validation. A lot of things compilers have to do becomes dramatically simpler with structured control flow and simpler means faster. When you operate on an unstructured CFG you first have to analyze the entire graph to find the dominators, loops etc and then you have to propagate the dataflow information in that order. All these complications go away. There's been a few other works that realized this, among them the CORTL IR, suggested by Carl McConnell in his Thesis proposal "Tree Based Optimizations" and the IR used in the Oberon compiler by Michael Franz.
  - jnordwick 7y ago
    1. You can have both. Jumps (conditional or unconditional allow for more complex control flow and different control flow than was immediately thought of. 2 only having structured control flow makes it a difficult target for HLL, which is what was is supposed to be. 3. A few years ago I was working on an array language and was trying to use tree based optimization and code generation, but I put it on hold until i understood more - can you recommend and links or papers? 4. Wasm is an IR, both target and source. Why not add a goto and structured primitive. There are clearly some things that cannot be compiled anywhere remotely performant.
int_19h 7y ago
http://troubles.md/posts/why-do-we-need-the-relooper-algorithm-again/ http://troubles.md/posts/why-do-we-need-the-relooper-algorit... "There is one thing that may have been a major factor to the decision not to adopt arbitrary CFGs for WebAssembly control flow. I believe that V8 is an exception to most compilers in that it doesn’t represent code as a CFG at all - it maintains roughly JS-compatible control flow all the way from front-end to codegen. In order to support this V8 would have to be converted to use CFGs, they’d have to implement something like Relooper internally, or they’d have to write a new WebAssembly runtime from scratch. Google was and is a major roadblock to getting this implemented as they have multiple people on the committee in charge of WebAssembly who have veto power."

naikrovek 7y ago

No "goto" means no JUMP instruction, right? I mean I guess that's still Turing-complete, but it seems like that would make things a lot more difficult than necessary. I would love to know the answer to your question

jnordwick 7y ago
also no conditional jumps (equivalent to jnz, jeq, etc...) instead of uses this weird br_if that can only go to places on the control flow stack.

Rusky 7y ago

That was done entirely on purpose, to make validation simpler. It does make things harder for compilers that want to support irreducible control flow, but the workaround is a single "relooper" algorithm that doesn't really fundamentally change how those compilers work. It is possible that in the future this will be relaxed (without giving up on the benefits for validation) via something like this: https://github.com/WebAssembly/funclets https://github.com/WebAssembly/funclets

deleted 7y ago
[deleted]
FullyFunctional 7y ago
It's not just validation. A lot of things compilers have to do becomes dramatically simpler with structured control flow and simpler means faster. When you operate on an unstructured CFG you first have to analyze the entire graph to find the dominators, loops etc and then you have to propagate the dataflow information in that order. All these complications go away. There's been a few other works that realized this, among them the CORTL IR, suggested by Carl McConnell in his Thesis proposal "Tree Based Optimizations" and the IR used in the Oberon compiler by Michael Franz.
- jnordwick 7y ago
  1. You can have both. Jumps (conditional or unconditional allow for more complex control flow and different control flow than was immediately thought of. 2 only having structured control flow makes it a difficult target for HLL, which is what was is supposed to be. 3. A few years ago I was working on an array language and was trying to use tree based optimization and code generation, but I put it on hold until i understood more - can you recommend and links or papers? 4. Wasm is an IR, both target and source. Why not add a goto and structured primitive. There are clearly some things that cannot be compiled anywhere remotely performant.

int_19h 7y ago

http://troubles.md/posts/why-do-we-need-the-relooper-algorithm-again/ http://troubles.md/posts/why-do-we-need-the-relooper-algorit... "There is one thing that may have been a major factor to the decision not to adopt arbitrary CFGs for WebAssembly control flow. I believe that V8 is an exception to most compilers in that it doesn’t represent code as a CFG at all - it maintains roughly JS-compatible control flow all the way from front-end to codegen. In order to support this V8 would have to be converted to use CFGs, they’d have to implement something like Relooper internally, or they’d have to write a new WebAssembly runtime from scratch. Google was and is a major roadblock to getting this implemented as they have multiple people on the committee in charge of WebAssembly who have veto power."