The goals of this proposal are
- Keep representing control flow in a structured manner, as we already agree; the structure makes it compressible, easy to optimize on the client, and is nice for polyfilling too.
- Reduce currently-existing control flow overhead, which we know exists in practice in solutions like Emscripten, and may be impossible to avoid (even if it is typically small).
- Do so in a way that allows both (1) a super-simple VM implementation, which might not reduce that overhead, but shows this does not force undue complication on browsers, and (2) a clear optimization path to eliminating that overhead entirely.
This proposal introduces two new AST constructs, best explained with an example:
while (1) {
if (check()) {
tilt -> L1;
} else if (other()) {
tilt -> L2;
} else {
work();
}
}
multiple {
L1: { l_1(); }
L2: { l_2(); }
}
next();
What happens here is if check(), then we execute l_1(), and if other() then we execute l_2(); otherwise we do some work() and go to the top of the loop. Conceptually, Tilt doesn't actually affect control flow - it just "goes with the flow" of where things are moving anyhow, but it can "tilt" things a little one way or another (like tilting a pinball machine) at specific locations. Specifically, if control flow reaches a multiple, then the tilt has an effect in picking out where we end up inside the multiple. But otherwise, Tilt doesn't cause control flow by itself.
In more detail, the semantics are fully defined as follows:
- Define
label as a "hidden" local variable on the stack, only visible to the next 2 bullet points.
tilt -> X sets label to a numerical id that represents the label X.multiple { X1: { .. } X2: { .. } .. } checks the value of label. If it is equal to the numerical id of one of the labels X1, X2, ... then we execute the code in that label's block, set label to a null value (that is not the id of any label), and exit the multiple. Otherwise (if it is not equal to any of the ids), we just skip the multiple.
Note that Tilt does not move control flow to anywhere it couldn't actually get anyhow. Control flow still moves around using the same structured loops and ifs and breaks that we already have. Tilt only does a minor adjustment to control flow when we reach a multiple. The multiple can be seen as a "switch on labels", and the tilt picks which one we enter. But again, we could have reached any of those labels in the multiple anyhow through structured control flow (and picked which label in the multiple using a switch on the numerical id of the label).
The semantics described above also provide the "super-simple" implementation mentioned in the goals. It is trivial for a VM to implement that - just define the helper variable, set it and test it - and it would be correct; and control flow is still structured. But, it is also possible in a straightforward way to just emit a branch from the tilt to the right place. In the example above, that is perhaps too easy, so consider this more interesting example:
L1: while (1) {
if (checkA()) {
tilt -> L2;
} else {
if (checkB()) break;
while (1) {
work();
if (checkC()) {
tilt -> L3;
break L1;
}
}
never();
}
}
multiple {
L2: { print('checkA passed!') }
L3: { print('checkC passed!') }
}
It is straightforward for the VM to see that tilt -> L2 will reach L2, and tilt -> L3 will reach L3 - note how we need a break after the tilt to achieve that - so it can just emit branches directly. The helper variable overhead can be eliminated entirely.
This idea is modeled on the Relooper algorithm from 2011. There is a proof there that any control flow can be represented in a structured way, using just the available control flow constructs in JavaScript, and using a helper variable like label mentioned in the Tilt semantics, without any code duplication (other approaches split nodes, and have bad worst-case code size situations). The relooper has also been implemented in Emscripten, and over the last 4 years we have gotten a lot of practical experience with it, showing that it gives good results in practice, typically with little usage of the helper variable.
Thus, we have both a solid theoretical result that shows we can represent any control flow - even irreducible - in this way, and experience showing that that helper variable overhead tends to be minimal. In the proposal here, that helper variable is, in essence, written in an explicit manner, which allows even that overhead to be optimized out nicely by the VM.
A note on irreducible control flow: As mentioned, Tilt can represent it, e.g.,
tilt -> L2;
while (1) {
multiple {
L1: {
duffs();
tilt -> L2;
}
L2: {
device();
if (done()) break;
tilt -> L1;
}
}
}
This is not surprising as the relooper proof guarantees that it can. And we can also make that irredicuble control flow run at full speed (if the VM optimizes Tilt, instead of doing just the super-simple semantics as its implementation). Still, this is not quite as good as if we directly represented that irreducible control flow as basic blocks plus branches directly, since with Tilt we do need to analyze a little to find that underlying control flow graph. So something like proper tail calls, which can directly represent that graph, may still be useful, but it is debatable - at least a large set of cases of proper tail calls seem to be handled by Tilt (the cases of having heavily irreducible control flow), and without the limitations of proper tail calls like number of parameters. However, there is obviously a lot to debate on that.
In any case, putting aside irreducible control flow and proper tail calls, what Tilt is clearly great for is to eliminate any small amounts of helper variable usage, that occur often in practice, stemming from either small amounts of irreducible control flow (either a goto in the source, or a compiler optimization pass that complexified control flow for some reason), or reducible but complex enough control flow that the compiler didn't manage to remove all helper variable usages (it is an open question whether 100% can be removed in tractable time). Having Tilt in wasm would open the possibility for straightforward and predictable removal of that overhead.
To summarize this proposal, it can be seen as adding an "escape valve" to structured control flow, where code remains still structured, but we can express more complex patterns in a way that is at least easily optimizable without magical VM tricks.
That concludes the core of this proposal. I see two possible large open questions here:
- The above cannot optimize indirect branches. Some interpreter loops really want that. I'm not sure if we want to get into that now. But it seems that a clear path is available - an "indirect Tilt" would use a variable instead of a label, together with a way to get the numeric id of a label.
- In the proposal above, we define the semantics in a super-simple way. I like the simplicity and how it also shows how to implement the feature in a trivial way, so this should not slow down development of wasm VMs. But a downside to that is that it allows one to write nonsense like
tilt -> L1;
work();
L2: while (1) {
more();
tilt -> L2;
if (check()) break;
}
multiple {
L3: { never(); }
}
None of the tilts do anything; the multiple is ignored; just reading that makes me nauseous. But it is valid code to write, even if silly. It might be nice to get a parse-time error on such things, and it isn't hard. But to do so requires that we define what is errored on very precisely, which is a lot more detailed than the very simple (but fully defined!) semantics described above.
edit: that detailed description appears in WebAssembly/spec#33 (comment)
And that brings me to a final point here. We could in principle delay discussion of this to a later date. However, if we do want to add this later, and do want to error on such nonsense as the last example, then how easy and clean it is to define the semantics will depend on decisions that we do make now. In particular, the fewer control flow constructs we have, the easier and cleaner it will be; every construct may need to be involved in the description. Also, we might want to start out with simple constructs that make that easier (I have some ideas for those, but nothing too concrete yet).
In other words, what I am getting at is that if we design our control flow constructs as a whole, together with Tilt, then things will be much nicer than if we try to tack Tilt on later to something designed before it. For that reason, we might want to discuss it now.
Bikeshedding: Suggestions for better names are welcome. Another name I considered was slide -> X, as in "I totally meant to slide there".
React
Typescript
Django
Laravel
Facebook
Microsoft
Google
Alibaba
D3
Tencent