3 ms·

Well, more efficient to verify, because it is more restrictive Meaning some control flows are unrepresentable and certainly less compact; since they must be 'i

Well, more efficient to verify, because it is more restrictive Meaning some control flows are unrepresentable and certainly less compact; since they must be 'interpreted' I think that's probably the best decision for quick webpage loading, but given that WASM is generally used for code heavy webpages -- not quick jquery replacements, I'm not convinced it was the best decision overall -- I love a lot of wasm, I just wish it was a better target for open ended computation; which is something gotos and coroutines are better suited for That said; WASM is a clever trade off; but the trade-off is hidden within compilers (ref Go's wasm for instance)

aeldidi 3y ago
Nothing is unrepresentable, if I’m not mistaken. https://en.m.wikipedia.org/wiki/Structured_program_theorem https://en.m.wikipedia.org/wiki/Structured_program_theorem Rather, I think the trade off was more in the realm of “aggressively optimize for what the web does well”. With that being said, I do wish it was better suited for general purpose computation.
- titzer 3y ago
  Irreducible loops (loops with more than one way to enter) are not representable by structured control flow. It's possible to model with with state variables (e.g. loop over switch). Incidentally if irreducible control flow is modeled this way (set the control variable to a constant and then branch back to the loop header which immediately then switches on the variable), and the compiler performs jump threading with constant propagation (i.e. duplicate the loop header up to the switch, and fold the switch), the resulting control graph will again have irreducible control flow. In fact it will be the same as the original control flow graph. So it's possible to undo the inefficiency of the state variable with some transformations in the Wasm consumer.
titzer 3y ago
It's not just that it's more restrictive, it's that it forces the producer to do work for the verifier. Structured control flow follows a stack discipline and also pre-declares all labels, so the consumer (verifier) can use the minimum data structures necessary, immediately reusing metadata for each control structure when it is exited.
- tsegratis 3y ago
  Since you're giving great answers ;) What's the problem with multiple entry points anyway? If we're not using computed goto, or dynamically verifying it when we do, aren't all of our jump targets known, and so inherently safe? What am i missing? EDIT: is it just a question of speed of jit for register allocation / dominance frontiers?? But the verifier is providing safety right??
  - titzer 3y ago
    Sure, you can still have safe code with irreducible loops. Safety is orthogonal. There is a proposal to add "multi-loop" (https://gist.github.com/conrad-watt/6a620cb8b7d8f0191296e3eb24dffdef https://gist.github.com/conrad-watt/6a620cb8b7d8f0191296e3eb...) to Wasm, but it hasn't been a high priority. Of all the Wasm JITs I know of, none of the Web engine's optimizing compilers can handle irreducible control flow in their backends. Their register allocators and codegen algorithms would need to be modified. I worked on TurboFan, and several parts of it would choke on irreducible control flow. It's likely these engines would fall back to baseline compilation for such functions, which is a bigger perf impact than using state variables.

aeldidi 3y ago

Nothing is unrepresentable, if I’m not mistaken. https://en.m.wikipedia.org/wiki/Structured_program_theorem https://en.m.wikipedia.org/wiki/Structured_program_theorem Rather, I think the trade off was more in the realm of “aggressively optimize for what the web does well”. With that being said, I do wish it was better suited for general purpose computation.

titzer 3y ago
Irreducible loops (loops with more than one way to enter) are not representable by structured control flow. It's possible to model with with state variables (e.g. loop over switch). Incidentally if irreducible control flow is modeled this way (set the control variable to a constant and then branch back to the loop header which immediately then switches on the variable), and the compiler performs jump threading with constant propagation (i.e. duplicate the loop header up to the switch, and fold the switch), the resulting control graph will again have irreducible control flow. In fact it will be the same as the original control flow graph. So it's possible to undo the inefficiency of the state variable with some transformations in the Wasm consumer.

titzer 3y ago

It's not just that it's more restrictive, it's that it forces the producer to do work for the verifier. Structured control flow follows a stack discipline and also pre-declares all labels, so the consumer (verifier) can use the minimum data structures necessary, immediately reusing metadata for each control structure when it is exited.

tsegratis 3y ago
Since you're giving great answers ;) What's the problem with multiple entry points anyway? If we're not using computed goto, or dynamically verifying it when we do, aren't all of our jump targets known, and so inherently safe? What am i missing? EDIT: is it just a question of speed of jit for register allocation / dominance frontiers?? But the verifier is providing safety right??
- titzer 3y ago
  Sure, you can still have safe code with irreducible loops. Safety is orthogonal. There is a proposal to add "multi-loop" (https://gist.github.com/conrad-watt/6a620cb8b7d8f0191296e3eb24dffdef https://gist.github.com/conrad-watt/6a620cb8b7d8f0191296e3eb...) to Wasm, but it hasn't been a high priority. Of all the Wasm JITs I know of, none of the Web engine's optimizing compilers can handle irreducible control flow in their backends. Their register allocators and codegen algorithms would need to be modified. I worked on TurboFan, and several parts of it would choke on irreducible control flow. It's likely these engines would fall back to baseline compilation for such functions, which is a bigger perf impact than using state variables.