Steady On: An alternative to Tilt

[sunfishcode]

Here's one of the examples which motivated the Tilt discussion:

while (1) {
  ..
  if (...) {
    label = 1;
    break;
  }
  ..
  if (...) {
    label = 1;
    break;
  }
  ..
  if (...) {
    break;
  }
}
if (label === 1) {
  ...
}

It is possible to represent this without label variables, like this:

L1: {
  L0: while (1) {
    if (...)
      break L0;
    ..
    if (...)
      break L0;
    ..
    if (...)
      break L1;
  }
  ...
}

Furthermore, I have now worked out a constructive proof that it's possible to represent all reducible control flow using our existing structured forms without the use of label variables, by using this general technique as a fallback instead of label variables. In the worst case, it can generate deeply nested structures which may be too deep for some existing JS parsers to handle, so there are tradeoffs to consider when polyfilling to asm.js, but there are many cases where the nesting isn't deep and the technique should work well.

Consequently, I propose we hold off on Tilt for now. A hybrid Relooper implementation extended to use of this technique in situations where it would be beneficial is worth pursuing, as it would allow Emscripten to generate better asm.js code, and allow llvm-wasm to generate better wasm code which polyfills to asm.js for v1.

[kg]

Getting rid of label variables sounds really good. Is there a downside?

[sunfishcode]

The downside is that in the worst case, it can generate deeply nested structures which may be too deep for some existing JS parsers to handle.

[kg]

Ah, I see. I wasn't sure if you meant that it introduced some sort of nesting with a runtime cost.

[sunfishcode]

This technique has no runtime cost.

[kripken]

I think this is a compelling argument that we could remove a significant amount of label variables into this form. I don't think we can remove them all - even if it is possible to do so, it might lead to unpleasant "towers" that cause parsing issues, and are also less readable, as mentioned above.

But, given that label variables are rare anyhow, and this seems like a good way to get rid of yet more of them, it definitely reduces the motivation for something like tilt, at least for reducible control flow.

A remaining benefit of tilt is that it can represent irreducible control flow in a way that is very easy to optimize. So the question might be, do we care about irreducible control flow yet. I think maybe we don't, although I also don't think that tail calls are a perfect solution to irreducible control flow either, so we might consider multiple options for irreducible control flow later.

Overall this, together with @pizlonator's arguments on automatic jump threading, convince me that we can hold off on thinking about irreducible control flow for now.

[sunfishcode]

At present, there seems to be consensus on the current approach, so there's no need to hold this issue open.