8 ms·

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

144 points by tbodt 7y ago

saagarjha 7y ago
WebAssembly makes a number of strange choices that seemingly fly in the face of convention; this is one of them. It would be really nice if it someone took some time it make a FAQ on the website to answer questions like “why doesn’t WebAssembly do x like everything else”, because otherwise it just seems that they’re just doing things differently because they can…
- cwzwarich 7y ago
  A lot of those bad WebAssembly decisions are carried over from Emscripten/Asm.js and don't have any real rationale behind them beyond that. Obviously, since JS doesn't support arbitrary control flow, Emscripten/Asm.js would need to convert to some simplified form of control flow (although not necessarily fully structured). It seems that this solution was carried over to WebAssembly without much deep thought given. There does seem to be some backwards association with Java's bytecode verification complexity issues (which are the result of a bad design, not unstructured control flow). In the big GitHub Issue (https://github.com/WebAssembly/design/issues/796 https://github.com/WebAssembly/design/issues/796) on the topic, one of the core V8 developers even claims that the Java experience justifies the WebAssembly decision. However, the funclets proposal for WebAssembly (https://github.com/WebAssembly/funclets/blob/master/proposals/funclets/Overview.md https://github.com/WebAssembly/funclets/blob/master/proposal...) shows that you can support arbitrary control flow with linear time verification if you choose a different design than Java.
  - brabel 7y ago
    WASM is a typed bytecode format where the stack state must be validatable at compile-time, guaranteeing that no validated program can mess up the stack at runtime. Having unstructured control flow would make it pretty much impossible to do that, wouldn't it?
    - __s 7y ago
      Not impossible, as in the JVM there'd be a pass which verifies that the stack usage is deterministic along all program paths. It's nice not having to do that verifying step, but stack usage still has to be checked anyways, so whether it's actually a win is debatable
    - abecedarius 7y ago
      Nah. I made a low-level VM in 2001 similar to this funclets proposal cwzwarich linked to (Hi, Cameron), and verification was a fast local check. Each funclet had a signature, you collect the signatures before you start verifying the code, and then track changes to the stack as you walk through the code, using the signatures for the effects of any calls you encounter, and finally insisting that the funclet match its declared effect. Control flow within a funclet is reducible. (I didn't call them funclets, but it sounds like the same basic scheme on glancing through. One simplification: my VM could loop only through the tail calls.)
    - cwzwarich 7y ago
      To get linear time validation, you need conditions at each control flow transfer that can be checked locally but together imply that stack usage in the function is well-formed. The funclet approach (in more ordinary terminology) is to ensure that the stack difference from function invocation upon entry to a basic block is the same across entries to that basic block, and that those additional stack entries all have the same (statically specified) type in each invocation. This is very natural when generating code from an SSA optimizer. Java bytecode traditionally didn't contain any of this branch target or type information, and required the bytecode verifier to do an iterative combined control/data-flow analysis. Even now that they added some of that type information with stack maps, it's still more complicated than it needs to be due to the historical legacy of this approach.
    - int_19h 7y ago
      Completely unstructured, yes. However, there are many stack-based VMs with both gotos and verification. Generally speaking, the constraint is that for any label that is a jump target, the stack must have the same count and type of elements for all possible origins. It's not hard to verify.
  - saagarjha 7y ago
    There are other ones that can't reasonably be because of legacy, though; for example, the lack of memory permissions.
    - comex 7y ago
      By memory permissions, do you mean setting page-level permissions, like mprotect on Unix? I’d love to see WebAssembly add support for those, along with mmap-like functionality. But there at least, unlike with control flow, there are some fundamental portability issues to consider. The only performant way to implement page-level permissions is using the native MMU. But different targets have different page sizes: most Unix systems have 4kb pages, but iOS has 16kb pages; Windows has 4kb pages which can be protected individually, but separate memory mappings can only be on 64k aligned boundaries; and Linux can be configured with multiple page size options. And some little microcontrollers don’t have an MMU at all, yet there are people trying to run WebAssembly on microcontrollers for some strange reason.
      - saagarjha 7y ago
        > By memory permissions, do you mean setting page-level permissions, like mprotect on Unix? Yes, exactly. > But different targets have different page sizes: most Unix systems have 4kb pages, but iOS has 16kb pages; Windows has 4kb pages which can be protected individually, but separate memory mappings can only be on 64k aligned boundaries; and Linux can be configured with multiple page size options. I haven't looked into it much, but perhaps WASI could abstract some of this, or make this information available to applications? > And some little microcontrollers don’t have an MMU at all, yet there are people trying to run WebAssembly on microcontrollers for some strange reason. It might be a little bit overhyped ;)
  - azakai 7y ago
    > It seems that this solution was carried over to WebAssembly without much deep thought given. That's definitely not true - a lot of thought was given at the time to this. I'm not saying the optimal conclusion was arrived at (nor am I saying the opposite), but it definitely wasn't for lack of effort and consideration. I don't remember all the details, but some of the factors were: * Experience with structured control flow in compilers like Emscripten, Mandreel, and Cheerp, that showed it's pretty easy to re-structure a CFG in the toolchain, and there aren't significant downsides when the VM receives that output. * VM people concerned about the efficiency and complexity of non-structured control flow, and preferring the structural approach that has known simple ways to construct SSA etc. (see titzer's comment for more details) * Not having a proposal like funclets on the table. (The idea for that came much later.)
    - deleted 7y ago
      [deleted]
- nabla9 7y ago
  I assume that important design criteria is to enable slim and fast verification and single-pass WASM to SSA or JIT backends and native compilers. To do that you want reducible flow graph. This will become more important especially if WebAssembly is moving beyond the browser.
heretoo 7y ago
The article cites Dijkstra's "considered harmful" essay, which asserts that "goto" should be removed from "higher level" languages, not "machine language". 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.
- saagarjha 7y ago
  It’s brought up to prove the opposite. I would suggest reading it through, it’s quite good.
  - heretoo 7y ago
    Yeah, I figured that might be happening, once I started reading further. Blame the reader.
RodgerTheGreat 7y ago
Something this article doesn't appear to spell out is that the structured format WASM is constrained to means that program CFGs will never contain irreducible loops. As noted, this approach can make it harder for the AoT compilers (they have to untangle the knots to generate valid WASM bytecode), but it makes it much easier for the JIT compilers to perform analysis and transformations at runtime. In that context, it seems like a sensible engineering decision.
albertzeyer 7y ago
Interestingly I came up with a similar algorithm like Relooper when I translated C to Python code. First I translate all C code to mostly equivalent Python code but including some gotos, and then I get rid of those gotos by introducing some more loops. The current solution is simple but the resulting function could be slow. https://github.com/albertz/PyCParser/blob/080a7b0472444fd366006c44fc15e388122989bd/goto.py#L102 https://github.com/albertz/PyCParser/blob/080a7b0472444fd366...
yuri91 7y ago
The article says about the Stackifier algorithm: "no link for the latter, it’s only mentioned by this name in LLVM internal discussions". 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-control-flow-problem-once-and-for-all-5123117b1ee2 https://medium.com/leaningtech/solving-the-structured-contro...
- jeltz 7y ago
  Thanks! I used your article to successfully implement Stackifier.
  - yuri91 7y ago
    I am glad it helped somebody :)
The_rationalist 7y ago
Unpopular opinion: GraalVM is what should have been webassembly. Reasons: * True polyglotism * existing, feature complete implementation * compatibility with the existing JVM platform, and through polyglotism compatibility with almost any platform/library.
- yoklov 7y ago
  a single existing implementation is a problem, not a feature for the web platform
  - The_rationalist 7y ago
    You can always rewrite a clone if throwing money is your finality.
    - yoklov 7y ago
      Sounds like much more work than implementing a wasm vm+runtime. Besides, isn’t it owned by a company who is notoriously litigious against reimplementations?
- wmf 7y ago
  WebAssembly exists because there was an incremental path from JS to asm.js to wasm. Better solution are irrelevant unless there's a similar kind of path to them.
- sitkack 7y ago
  GraalVM has started getting wasm support, so there is still a path forward.
  - solarkraft 7y ago
    WASM support as in "you can run stuff you can run in GraalVM on WASM" or as in "you can run WASM on GraalVM"? I assume the latter, which is, frankly, relatively unimpressive. It would have been pretty amazing to be able to run everything available in Graal in the browser - but yep, Graal is not a standard, and I'm not sure it could ever be put into one (because of the insane complexity and implementation effort I suspect in there). Would still have been cool, though, one can dream. WASM will still end up being a pretty universal platform however, with it being everyone's compilation target. A lot like Java, but maybe without some of the mistakes.
int_19h 7y ago
"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."
- sieabahlpark 7y ago
  Good ol Google being the opposite of what got them where they are currently.
- est31 7y ago
  > they have multiple people on the committee in charge of WebAssembly who have veto power Note that even if Google did not have people on that committee, they'd just not implement the feature in their browser, and the feature would be dead in the water. Outside of niche cases where browser choice is controlled, no web dev would adopt features that > 70% of users can't use. So the committee only reflects power dynamics that exist in the greater browser sphere. In fact, non-Google browsers probably have more seats than they have influence by raw market share.
  - leoc 7y ago
    > So the committee only reflects power dynamics that exist in the greater browser sphere. It doesn't only reflect them, but also amplifies them. Quietly nobbling things in committee is surely a lot easier than having to field questions about why you aren't implementing Web standards (insert quotation marks as desired). There's also the danger of being embarrassed when someone writes a library which runs slowly on your browser and fast on others.
- pjmlp 7y ago
  And they already had PNaCL, which was literally vetoed by the other browser vendors, politics.
emmanueloga_ 7y ago
META: I don't understand why some authors go out of the way to obscure important pieces of information: * 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/posts/why-do-we-need-the-relooper-algorithm-again.md https://github.com/Vurich/troubles.md/blob/master/content/po...
- rkangel 7y ago
  It's a common problem with news articles too - you get linked something and you don't know whether it relates to a current event or something interesting 3 years ago.
6510 7y ago
Could someone reduce the GOTO complaints to the arguments why it is harmful. (Preferably without the considerations?)
titzer 7y ago
sigh 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.
- saagarjha 7y ago

144 points by tbodt 7y ago

WebAssembly makes a number of strange choices that seemingly fly in the face of convention; this is one of them. It would be really nice if it someone took some time it make a FAQ on the website to answer questions like “why doesn’t WebAssembly do x like everything else”, because otherwise it just seems that they’re just doing things differently because they can…

cwzwarich 7y ago
A lot of those bad WebAssembly decisions are carried over from Emscripten/Asm.js and don't have any real rationale behind them beyond that. Obviously, since JS doesn't support arbitrary control flow, Emscripten/Asm.js would need to convert to some simplified form of control flow (although not necessarily fully structured). It seems that this solution was carried over to WebAssembly without much deep thought given. There does seem to be some backwards association with Java's bytecode verification complexity issues (which are the result of a bad design, not unstructured control flow). In the big GitHub Issue (https://github.com/WebAssembly/design/issues/796 https://github.com/WebAssembly/design/issues/796) on the topic, one of the core V8 developers even claims that the Java experience justifies the WebAssembly decision. However, the funclets proposal for WebAssembly (https://github.com/WebAssembly/funclets/blob/master/proposals/funclets/Overview.md https://github.com/WebAssembly/funclets/blob/master/proposal...) shows that you can support arbitrary control flow with linear time verification if you choose a different design than Java.
- brabel 7y ago
  WASM is a typed bytecode format where the stack state must be validatable at compile-time, guaranteeing that no validated program can mess up the stack at runtime. Having unstructured control flow would make it pretty much impossible to do that, wouldn't it?
  - __s 7y ago
    Not impossible, as in the JVM there'd be a pass which verifies that the stack usage is deterministic along all program paths. It's nice not having to do that verifying step, but stack usage still has to be checked anyways, so whether it's actually a win is debatable
  - abecedarius 7y ago
    Nah. I made a low-level VM in 2001 similar to this funclets proposal cwzwarich linked to (Hi, Cameron), and verification was a fast local check. Each funclet had a signature, you collect the signatures before you start verifying the code, and then track changes to the stack as you walk through the code, using the signatures for the effects of any calls you encounter, and finally insisting that the funclet match its declared effect. Control flow within a funclet is reducible. (I didn't call them funclets, but it sounds like the same basic scheme on glancing through. One simplification: my VM could loop only through the tail calls.)
  - cwzwarich 7y ago
    To get linear time validation, you need conditions at each control flow transfer that can be checked locally but together imply that stack usage in the function is well-formed. The funclet approach (in more ordinary terminology) is to ensure that the stack difference from function invocation upon entry to a basic block is the same across entries to that basic block, and that those additional stack entries all have the same (statically specified) type in each invocation. This is very natural when generating code from an SSA optimizer. Java bytecode traditionally didn't contain any of this branch target or type information, and required the bytecode verifier to do an iterative combined control/data-flow analysis. Even now that they added some of that type information with stack maps, it's still more complicated than it needs to be due to the historical legacy of this approach.
  - int_19h 7y ago
    Completely unstructured, yes. However, there are many stack-based VMs with both gotos and verification. Generally speaking, the constraint is that for any label that is a jump target, the stack must have the same count and type of elements for all possible origins. It's not hard to verify.
- saagarjha 7y ago
  There are other ones that can't reasonably be because of legacy, though; for example, the lack of memory permissions.
  - comex 7y ago
    By memory permissions, do you mean setting page-level permissions, like mprotect on Unix? I’d love to see WebAssembly add support for those, along with mmap-like functionality. But there at least, unlike with control flow, there are some fundamental portability issues to consider. The only performant way to implement page-level permissions is using the native MMU. But different targets have different page sizes: most Unix systems have 4kb pages, but iOS has 16kb pages; Windows has 4kb pages which can be protected individually, but separate memory mappings can only be on 64k aligned boundaries; and Linux can be configured with multiple page size options. And some little microcontrollers don’t have an MMU at all, yet there are people trying to run WebAssembly on microcontrollers for some strange reason.
    - saagarjha 7y ago
      > By memory permissions, do you mean setting page-level permissions, like mprotect on Unix? Yes, exactly. > But different targets have different page sizes: most Unix systems have 4kb pages, but iOS has 16kb pages; Windows has 4kb pages which can be protected individually, but separate memory mappings can only be on 64k aligned boundaries; and Linux can be configured with multiple page size options. I haven't looked into it much, but perhaps WASI could abstract some of this, or make this information available to applications? > And some little microcontrollers don’t have an MMU at all, yet there are people trying to run WebAssembly on microcontrollers for some strange reason. It might be a little bit overhyped ;)
- azakai 7y ago
  > It seems that this solution was carried over to WebAssembly without much deep thought given. That's definitely not true - a lot of thought was given at the time to this. I'm not saying the optimal conclusion was arrived at (nor am I saying the opposite), but it definitely wasn't for lack of effort and consideration. I don't remember all the details, but some of the factors were: * Experience with structured control flow in compilers like Emscripten, Mandreel, and Cheerp, that showed it's pretty easy to re-structure a CFG in the toolchain, and there aren't significant downsides when the VM receives that output. * VM people concerned about the efficiency and complexity of non-structured control flow, and preferring the structural approach that has known simple ways to construct SSA etc. (see titzer's comment for more details) * Not having a proposal like funclets on the table. (The idea for that came much later.)
  - deleted 7y ago
    [deleted]
nabla9 7y ago
I assume that important design criteria is to enable slim and fast verification and single-pass WASM to SSA or JIT backends and native compilers. To do that you want reducible flow graph. This will become more important especially if WebAssembly is moving beyond the browser.

heretoo 7y ago

The article cites Dijkstra's "considered harmful" essay, which asserts that "goto" should be removed from "higher level" languages, not "machine language". 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.

saagarjha 7y ago
It’s brought up to prove the opposite. I would suggest reading it through, it’s quite good.
- heretoo 7y ago
  Yeah, I figured that might be happening, once I started reading further. Blame the reader.

RodgerTheGreat 7y ago

Something this article doesn't appear to spell out is that the structured format WASM is constrained to means that program CFGs will never contain irreducible loops. As noted, this approach can make it harder for the AoT compilers (they have to untangle the knots to generate valid WASM bytecode), but it makes it much easier for the JIT compilers to perform analysis and transformations at runtime. In that context, it seems like a sensible engineering decision.

albertzeyer 7y ago

Interestingly I came up with a similar algorithm like Relooper when I translated C to Python code. First I translate all C code to mostly equivalent Python code but including some gotos, and then I get rid of those gotos by introducing some more loops. The current solution is simple but the resulting function could be slow. https://github.com/albertz/PyCParser/blob/080a7b0472444fd366006c44fc15e388122989bd/goto.py#L102 https://github.com/albertz/PyCParser/blob/080a7b0472444fd366...

yuri91 7y ago

The article says about the Stackifier algorithm: "no link for the latter, it’s only mentioned by this name in LLVM internal discussions". 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-control-flow-problem-once-and-for-all-5123117b1ee2 https://medium.com/leaningtech/solving-the-structured-contro...

jeltz 7y ago
Thanks! I used your article to successfully implement Stackifier.
- yuri91 7y ago
  I am glad it helped somebody :)

The_rationalist 7y ago

Unpopular opinion: GraalVM is what should have been webassembly. Reasons: * True polyglotism * existing, feature complete implementation * compatibility with the existing JVM platform, and through polyglotism compatibility with almost any platform/library.

yoklov 7y ago
a single existing implementation is a problem, not a feature for the web platform
- The_rationalist 7y ago
  You can always rewrite a clone if throwing money is your finality.
  - yoklov 7y ago
    Sounds like much more work than implementing a wasm vm+runtime. Besides, isn’t it owned by a company who is notoriously litigious against reimplementations?
wmf 7y ago
WebAssembly exists because there was an incremental path from JS to asm.js to wasm. Better solution are irrelevant unless there's a similar kind of path to them.
sitkack 7y ago
GraalVM has started getting wasm support, so there is still a path forward.
- solarkraft 7y ago
  WASM support as in "you can run stuff you can run in GraalVM on WASM" or as in "you can run WASM on GraalVM"? I assume the latter, which is, frankly, relatively unimpressive. It would have been pretty amazing to be able to run everything available in Graal in the browser - but yep, Graal is not a standard, and I'm not sure it could ever be put into one (because of the insane complexity and implementation effort I suspect in there). Would still have been cool, though, one can dream. WASM will still end up being a pretty universal platform however, with it being everyone's compilation target. A lot like Java, but maybe without some of the mistakes.

int_19h 7y ago

"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."

sieabahlpark 7y ago
Good ol Google being the opposite of what got them where they are currently.
est31 7y ago
> they have multiple people on the committee in charge of WebAssembly who have veto power Note that even if Google did not have people on that committee, they'd just not implement the feature in their browser, and the feature would be dead in the water. Outside of niche cases where browser choice is controlled, no web dev would adopt features that > 70% of users can't use. So the committee only reflects power dynamics that exist in the greater browser sphere. In fact, non-Google browsers probably have more seats than they have influence by raw market share.
- leoc 7y ago
  > So the committee only reflects power dynamics that exist in the greater browser sphere. It doesn't only reflect them, but also amplifies them. Quietly nobbling things in committee is surely a lot easier than having to field questions about why you aren't implementing Web standards (insert quotation marks as desired). There's also the danger of being embarrassed when someone writes a library which runs slowly on your browser and fast on others.
pjmlp 7y ago
And they already had PNaCL, which was literally vetoed by the other browser vendors, politics.

emmanueloga_ 7y ago

META: I don't understand why some authors go out of the way to obscure important pieces of information: * 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/posts/why-do-we-need-the-relooper-algorithm-again.md https://github.com/Vurich/troubles.md/blob/master/content/po...

rkangel 7y ago
It's a common problem with news articles too - you get linked something and you don't know whether it relates to a current event or something interesting 3 years ago.

6510 7y ago

Could someone reduce the GOTO complaints to the arguments why it is harmful. (Preferably without the considerations?)

titzer 7y ago

sigh 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.

saagarjha 7y ago