Please Support Arbitrary Labels and Gotos.

[oridb]

I'd like to point out that I haven't been involved in the web assembly effort,
and I'm not maintaining any large or widely used compilers (just my own
toy-ish language, minor contributions to the QBE compiler backend, and an
internship on IBM's compiler team), but I ended up getting a bit ranty, and
was encouraged to share more widely.

So, while I'm a bit uncomfortable jumping in and suggesting major changes
to a project I haven't been working on... here goes:

My Complaints:

When I'm writing a compiler, the first thing that I'd do to with the high level
structure -- loops, if statements, and so on -- is validate them for semantics,
do type checking and so on. The second thing I do with them is just throw them
out, and flatten to basic blocks, and possibly to SSA form. In some other parts
of the compiler world, a popular format is continuation passing style. I'm not
an expert on compiling with continuation passing style, but it neither seems to
be a good fit for the loops and scoped blocks that web assembly seems to have
embraced.

I'd like to argue that a flatter, goto based format would be far more useful as
a target for compiler developers, and would not significantly hinder the
writing of a usable polyfill.

Personally, also I'm not a big fan of nested complex expressions. They're a bit
clunkier to consume, especially if inner nodes can have side effects, but I
don't strongly object to them as a compiler implementer -- The web assembly
JIT can consume them, I can ignore them and generate the instructions that map
to my IR. They don't make me want to flip tables.

The bigger problem comes down to loops, blocks, and other syntactic elements
that, as an optimizing compiler writer, you try very hard to represent as a
graph with branches representing edges; The explicit control flow constructs
are a hindrance. Reconstructing them from the graph once you've actually done
the optimizations you want is certainly possible, but it's quite a bit of
complexity to work around a more complex format. And that annoys me: Both the
producer and the consumer are working around entirely invented problems
which would be avoided by simply dropping complex control flow constructs
from web assembly.

In addition, the insistence of higher level constructs leads to some
pathological cases. For example, Duff's Device ends up with horrible web
assembly output, as seen by messing around in The Wasm Explorer.
However, the inverse is not true: Everything that can be expressed
in web assembler can be trivially converted to an equivalent in some
unstructured, goto based format.

So, at the very least, I'd like to suggest that the web assembly team add
support for arbitrary labels and gotos. If they choose to keep the higher
level constructs, it would be a bit of wasteful complexity, but at least
compiler writers like me wold be able to ignore them and generate output
directly.

Polyfilling:

One of the concerns I have heard when discussing this is that the loop
and block based structure allows for easier polyfilling of web assembly.
While this isn't entirely false, I think that a simple polyfill solution
for labels and gotos is possible. Whiie it might not be quite as optimal,
I think that it's worth a little bit of ugliness in the bytecode in order
to avoid starting a new tool with built in technical debt.

If we assume an LLVM (or QBE) like syntax for web assmembly, then some code
that looks like:

int f(int x) {
    if (x == 42)
        return 123;
    else
        return 666;
}

might compile to:

 func @f(%x : i32) {
    %1 = test %x 42
jmp %1 iftrue iffalse

 L0:
    %r =i 123
jmp LRet
 L1:
    %r =i 666
jmp LRet
 Lret:
    ret %r
 }

This could be polyfilled to Javascript that looks like:

function f(x) {
    var __label = L0;
    var __ret;

    while (__label != LRet) {
        switch (__label) {
        case L0:
            var _v1 = (x == 42)
            if (_v1) {__lablel = L1;} else {label = L2;}
            break;
        case L1:
            __ret = 123
            __label = LRet
            break;
        case L2;
            __ret = 666
            __label = LRet
            break;
        default:
            assert(false);
            break;
    }
}

Is it ugly? Yeah. Does it matter? Hopefuly, if web assembly takes off,
not for long.

And if not:

Well, if I ever got around to targeting web assembly, I guess I'd generate code
using the approach I mentioned in the polyfill, and do my best to ignore all of
the high level constructs, hoping that the compilers would be smart enough to
catch on to this pattern.

But it would be nice if we didn't need to have both sides of the code generation
work around the format specified.

@oridb Wasm is somewhat optimized for the consumer to be able to quickly convert to SSA form, and the structure does help here for common code patterns, so the structure is not necessarily a burden for the consumer. I disagree with your assertion that 'both sides of the code generation work around the format specified'. Wasm is very much about a slim and fast consumer, and if you have some proposals to make it slimmer and faster then that might be constructive.

Blocks that can be ordered into a DAG can be expressed in the wasm blocks and branches, such as your example. The switch-loop is the style used when necessary, and perhaps consumers might do some jump threading to help here. Perhaps have a look at binaryen which might do much of the work for your compiler backend.

There have been other requests for more general CFG support, and some other approaches using loops mentioned, but perhaps the focus is elsewhere at present.

I don't think there are any plans to support 'continuation passing style' explicitly in the encoding, but there has been mention of blocks and loops popping arguments (just like a lambda) and supporting multiple values (multiple lambda arguments) and adding a pick operator to make it easier to reference definitions (the lambda arguments).

[oridb]

the structure does help here for common code patterns

I'm not seeing any common code pattern that are easier to represent in terms of branches to arbitrary labels, vs the restricted loops and blocks subset that web assembly enforces. I could see a minor benefit if there was an attempt to make the code closely resemble the input code for certain classes of langauge, but that doesn't seem to be a goal -- and the constructs are a bit bare if they were there for

Blocks that can be ordered into a DAG can be expressed in the wasm blocks and branches, such as your example.

Yes, they can be. However, I'd strongly prefer not to add extra work to determine which ones can be represented this way, versus which ones need extra work. Realistically, I'd skip doing the extra analysis, and always just generate the switch loop form.

Again, my argument isn't that loops and blocks make things impossible; It's that everything they can do is simpler and easier for a machine to write with goto, goto_if, and arbitrary, unstructured labels.

Perhaps have a look at binaryen which might do much of the work for your compiler backend.

I already have a serviceable backend that I'm fairly happy with, and plans to fully bootstrap the entire compiler in my own language. I'd rather not add in a rather large extra dependency simply to work around the enforced use of loops/blocks. If I simply use switch loops, emitting the code is pretty trivial. If I try to actually use the features present in web assembly effectively, instead of doing my damndest to pretend they don't exist, it becomes a good deal more unpleasant.

There have been other requests for more general CFG support, and some other approaches using loops mentioned, but perhaps the force is elsewhere at present.

I'm still not convinced that loops have any benefits -- anything that can be represented with a loop can be represented with a goto and label, and there are fast and well known conversions to SSA from flat instruction lists.

As afar as CPS goes, I don't think that there needs to be explicit support -- it's popular in FP circles because it's fairly easy to convert to assembly directly, and gives similar benefits to SSA in terms of reasoning (http://mlton.org/pipermail/mlton/2003-January/023054.html); Again, I'm not an expert on it, but from what I remember, the invocation continuation gets lowered to a label, a few movs, and a goto.

@oridb 'there are fast and well known conversions to SSA from flat instruction lists'

Would be interesting to know how they compare with wasm SSA decoders, that is the important question?

Wasm makes use of a values stack at present, and some of the benefits of that would gone without the structure, it would hurt decoder performance. Without the values stack the SSA decoding would have more work too, I've tried a register base code and decoding was slower (not sure how significant that is).

Would you keep the values stack, or use a register based design? If keeping the values stack then perhaps it becomes a CIL clone, and perhaps wasm performance could be compared to CIL, has anyone actually check this?

[oridb]

Would you keep the values stack, or use a register based design?

I don't actually have any strong feelings on that end. I'd imagine compactness of the encoding would be one of the biggest concerns; A register design may not fare that well there -- or it may turn out to compress fantastically over gzip. I don't actually know off the top of my head.

Performance is another concern, although I suspect that it might be less important given the ability to cache binary output, plus the fact that download time may outweigh the decoding by orders of magnitude.

Would be interesting to know how they compare with wasm SSA decoders, that is the important question?

If you're decoding to SSA, that implies that you'd also be doing a reasonable amount of optimization. I'd be curious to benchmark how significant decoding performance is in the first place. But, yes, that's definitely a good question.

[titzer]

Thanks for your questions and concerns.

It's worth noting that many of the designers and implementors of
WebAssembly have backgrounds in high performance, industrial JITs, not only
for JavaScript (V8, SpiderMonkey, Chakra, and JavaScriptCore), but also in
LLVM and other compilers. I personally have implemented two JITs for Java
bytecode and I can attest that a stack machine with unrestricted gotos
introduces quite some complexity in decoding, verifying, and constructing a
compiler IR. In fact, there are many patterns that can be expressed in Java
bytecode that will cause high-performance JITs, including both C1 and C2 in
HotSpot to simply give up and relegate the code to only running in the
interpreter. In contrast, constructing a compiler IR from something like an
AST from JavaScript or another language is something I've also done. The
extra structure of an AST makes some of this work far simpler.

The design of WebAssembly's control flow constructs simplifies consumers by
enabling fast, simple verification, easy, one pass conversion to SSA form
(even a graph IR), effective single-pass JITs, and (with postorder and the
stack machine) relatively simple in-place interpretation. Structured
control makes irreducible control flow graphs impossible, which eliminates
a whole class of nasty corner cases for decoders and compilers. It also
nicely sets the stage for exception handling in WASM bytecode, for which V8
is already developing a prototype in concert with the production
implementation.

We've had a lot of internal discussion between members about this very
topic, since, for a bytecode, it's one thing that is most different from
other machine-level targets. However, it's not any different than targeting
a source language like JavaScript (which many compilers do these days) and
requires only minor reorganization of blocks to achieve structure. There
are known algorithms to do this, and tools. We'd like to provide some
better guidance for those producers with start with an arbitrary CFG to
communicate this better. For languages targeting WASM directly from an AST
(which is actually something V8 does now for asm.js code--directly
translating a JavaScript AST to WASM bytecode), there is no restructuring
step necessary. We expect this to be the case for many language tools
across the spectrum that don't have sophisticated IRs inside.

On Thu, Sep 8, 2016 at 9:53 AM, Ori Bernstein notifications@github.com
wrote:

Would you keep the values stack, or use a register based design?

I don't actually have any strong feelings on that end. I'd imagine
compactness of the encoding would be one of the biggest concerns; As you
mentioned, performance is another.

Would be interesting to know how they compare with wasm SSA decoders, that
is the important question?

If you're decoding to SSA, that implies that you'd also be doing a
reasonable amount of optimization. I'd be curious to benchmark how
significant decoding performance is in the first place. But, yes, that's
definitely a good question.

—
You are receiving this because you are subscribed to this thread.
Reply to this email directly, view it on GitHub
#796 (comment),
or mute the thread
https://github.com/notifications/unsubscribe-auth/ALnq1Iz1nn4--NL32R9ev0JPKfEnDyvqks5qn77cgaJpZM4J3ofA
.

[qwertie]

Thanks @titzer, I was developing a suspicion that Wasm's structure had a purpose beyond just similarity to asm.js. I wonder though: Java bytecode (and CIL) don't model CFGs or the value stack directly, they have to be inferred by the JIT. But in Wasm (especially if block signatures are added) the JIT can easily figure out what's going on with the value stack and control flow, so I wonder, if CFGs (or irreducible control flow specifically) were modeled explicitly like loops and blocks are, might that avoid most of the nasty corner cases you're thinking of?

There's this neat optimization that interpreters use that relies on irreducible control flow to improve branch prediction...

[kripken]

@oridb

I'd like to argue that a flatter, goto based format would be far more useful as
a target for compiler developers

I agree that gotos are very useful for many compilers. That's why tools like Binaryen let you generate arbitrary CFGs with gotos, and they can convert that very quickly and efficiently into WebAssembly for you.

It might help to think of WebAssembly as a thing optimized for browsers to consume (as @titzer pointed out). Most compilers should probably not generate WebAssembly directly, but rather use a tool like Binaryen, so that they can emit gotos, get a bunch of optimizations for free, and don't need to think about low-level binary format details of WebAssembly (instead you emit an IR using a simple API).

Regarding polyfilling with the while-switch pattern you mention: in emscripten we started out that way before we developed the "relooper" method of recreating loops. The while-switch pattern is around 4x slower on average (but in some cases significantly less or more, e.g. small loops are more sensitive). I agree with you that in theory jump-threading optimizations could speed that up, but performance will be less predictable as some VMs will do it better than others. It is also significantly larger in terms of code size.

[oridb]

It might help to think of WebAssembly as a thing optimized for browsers to consume (as @titzer pointed out). Most compilers should probably not generate WebAssembly directly, but rather use a tool like Binaryen...

I'm still not convinced that this aspect is going to matter that much - again, I suspect the cost of fetching the bytecode would dominate the delay the user sees, with the second biggest cost being the optimizations done, and not the parsing and validation. I'm also assuming/hoping that the bytecode would be tossed out, and the compiled output is what would be cached, making the compilation effectively a one-time cost.

But if you were optimizing for web browser consumption, why not simply define web assembly as SSA, which seems to me both more in line with what I'd expect, and less effort to 'convert' to SSA?

[kripken]

You can start to parse and compile while downloading, and some VMs might not do a full compile up front (they might just use a simple baseline for example). So download and compile times can be smaller than expected, and as a result parsing and validation can end up a significant factor in the total delay the user sees.

Regarding SSA representations, they tend to have large code sizes. SSA is great for optimizing code, but not for serializing code compactly.

@oridb See the comment by @titzer 'The design of WebAssembly's control flow constructs simplifies consumers by enabling fast, simple verification, easy, one pass conversion to SSA form ...' - it can generate verified SSA in one pass. Even if wasm used SSA for the encoding it would still have the burden of verifying it, of computing the dominator structure which is easy with the wasm control flow restrictions.

Much of the encoding efficiency of wasm appears to come from being optimized for the common code pattern in which definitions have a single use that is used in stack order. I expect that an SSA encoding could do so too, so it could be of similar encoding efficiency. Operators such as if_else for diamond patterns also help a lot. But without the wasm structure it looks like all basic blocks would need to read definitions from registers and write results to registers, and that might not be so efficient. For example, I think wasm can do even better with a pick operator that could reference scoped stack values up the stack and across basic block boundaries.

I think wasm is not too far from being able to encode most code in SSA style. If definitions were passed up the scope tree as basic block outputs then it might be complete. Might the SSA encoding be orthogonal to the CFG matter. E.g. There could be an SSA encoding with the wasm CFG restrictions, there could be a register based VM with the CFG restrictions.

A goal for wasm is to move the optimization burden out the runtime consumer. There is strong resistance to adding complexity in the runtime compiler, as it increases the attack surface. So much of the design challenge is to ask what can be done to simplify the runtime compiler without hurting performance, and much debate!

[comex]

Well, it's probably too late now, but I'd like to question the idea that the relooper algorithm, or variants thereof, can produce "good enough" results in all cases. They clearly can in most cases, since most source code doesn't contain irreducible control flow to start with, optimizations don't usually make things too hairy, and if they do, e.g. as part of merging duplicate blocks, they can probably be taught not to. But what about pathological cases? For example, what if you have a coroutine which a compiler has transformed to a regular function with structure like this pseudo-C:

void transformed_coroutine(struct autogenerated_context_struct *ctx) {
	int arg1, arg2; // function args
	int var1, var2, var3, …; // all vars used by the function
	switch (ctx->current_label) { // restore state
	case 0:
		// initial state, load function args caller supplied and proceed to start
		arg1 = ctx->arg1;
		arg2 = ctx->arg2;
		break;
	case 1: 
		// restore all vars which are live at label 1, then jump there
		var2 = ctx->var2; 
		var3 = ctx->var3;
		goto resume_1;
	[more cases…]
	}
	
	[main body goes here...]
	[somewhere deep in nested control flow:]
		// originally a yield/await/etc.
		ctx->var2 = var2;
		ctx->var3 = var3;
		ctx->current_label = 1;
		return;
		resume_1:
		// continue on
}

So you have mostly normal control flow, but with some gotos pointed at the middle of it. This is roughly how LLVM coroutines work.

I don't think there's any nice way to reloop something like that, if the 'normal' control flow is complex enough. (Could be wrong.) Either you duplicate massive parts of the function, potentially needing a separate copy for every yield point, or you turn the whole thing into a giant switch, which according to @kripken is 4x slower than relooper on typical code (which itself is probably somewhat slower than not needing relooper at all).

The VM could reduce the overhead of a giant switch with jump threading optimizations, but surely it's more expensive for the VM to perform those optimizations, essentially guessing how the code reduces to gotos, than to just accept explicit gotos. As @kripken says, it's also less predictable.

Maybe doing that kind of transformation is a bad idea to start with, since afterward nothing dominates anything so SSA-based optimizations can't do much… maybe it's better done at the assembly level, maybe wasm should eventually get native coroutine support instead? But the compiler can perform most optimizations before doing the transformation, and it seems that at least the designers of LLVM coroutines didn't see an urgent need to delay the transformation until code generation. On the other hand, since there's a fair amount of variety in the exact semantics people want from coroutines (e.g. duplication of suspended coroutines, ability to inspect 'stack frames' for GC), when it comes to designing a portable bytecode (rather than a compiler), it's more flexible to properly support already-transformed code than to have the VM do the transformation.

Anyway, coroutines are just one example. Another example I can think of is implementing a VM-within-a-VM. While a more common feature of JITs is side exits, which don't require goto, there are situations that call for side entries - again, requiring goto into the middle of loops and such. Another would be optimized interpreters: not that interpreters targeting wasm can really match those targeting native code, which at minimum can improve performance with computed gotos, and can dip into assembly for more… but part of the motivation for computed gotos is to better leverage the branch predictor by giving each case its own jump instruction, so you might be able to replicate some of the effect by having a separate switch after each opcode handler, where the cases would all just be gotos. Or at least have an if or two to check for specific instructions that commonly come after the current one. There are some special cases of that pattern that might be representable with structured control flow, but not the general case. And so on…

Surely there's some way to allow arbitrary control flow without making the VM do a lot of work. Straw man idea, might be broken: you could have a scheme where jumps to child scopes are allowed, but only if the number of scopes you have to enter is less than a limit defined by the target block. The limit would default to 0 (no jumps from parent scopes), which preserves the current semantics, and a block's limit can't be greater than the parent block's limit + 1 (easy to check). And the VM would change its dominance heuristic from "X dominates Y if it is a parent of Y" to "X dominates Y if it is a parent of Y with distance greater than Y's child jump limit". (This is a conservative approximation, not guaranteed to represent the exact dominator set, but the same is true for the existing heuristic - it's possible for an inner block to dominate the bottom half of an outer one.) Since only code with irreducible control flow would need to specify a limit, it wouldn't increase code size in the common case.

Edit: Interestingly, that would basically make the block structure into a representation of the dominance tree. I guess it would be much simpler to express that directly: a tree of basic blocks, where a block is allowed to jump to a sibling, ancestor, or immediate child block, but not to a further descendant. I'm not sure how that best maps onto the existing scope structure, where a "block" can consist of multiple basic blocks with sub-loops in between.

FWIW: Wasm has a particular design, which is explained in just a few very significant words "except that the nesting restriction makes it impossible to branch into the middle of a loop from outside the loop".

If it were just a DAG then validation could just check that branches were forward, but with loops this would allow branching into the middle of the loop from outside the loop, hence the nested block design.

The CFG is only part of this design, the other being data flow, and there is a stack of values and blocks can also be organized to unwind the values stack which can very usefully communicate the live range to the consumer which saves work converting to SSA.

It is possible to extend wasm to be an SSA encoding (add pick, allow blocks to return multiple values, and have loop entries pop values), so interestingly the constraints demanded for efficient SSA decoding might not be necessary (because it could already be SSA encoded)! This leads to a functional language (which might have a stack style encoding for efficiency).

If this were extended to handle arbitrary CFG then might it look like the following. This is an SSA style encoding so values are constants. It seems to still fit the stack style to a large extent, just not certain of all the details. So within blocks branches could be made to any other labeled blocks in that set, or some other convention used to transfer control to another block. The code within the block might still usefully reference values on the values stack higher up the stack to save passing them all in.

(func f1 (arg1)
  (let ((c1 10)) ; Some values up the stack.
    (blocks ((b1 (a1 a2 a3)
                   ... (br b3)
               (br b2 (+ a1 a2 a3 arg1 c1)))
             (b2 (a1)
                 ... (br b1 ...))
             (b3 ()
                 ...))
   .. regular structured wasm ..
   (br b2 ...)
   ....
   (br b3)
    ...
   ))

But would web browsers ever handle this efficient internally?

Would someone with a stack machine background recognize the code pattern and be able to match it to a stack encoding?

There is some interesting discussion on irreducible loops here http://bboissin.appspot.com/static/upload/bboissin-thesis-2010-09-22.pdf

I did not follow it all on a quick pass, but it mentions converting irreducible loops to reducible loops by adding an entry node. For wasm it sounds like adding a defined input to loops that is specifically for dispatching within the loop, similar to the current solution but with a defined variable for this. The above mentions this is virtualized, optimized away, in processing. Perhaps something like this could be an option?

If this is on the horizon, and given that producers already need to use a similar technique but using a local variable, then might it be worth considering now so that wasm produced early has potential to run faster on more advanced runtimes? This might also create an incentive for competition between the runtimes to explore this.

This would not exactly be arbitrary labels and gotos but something that these might be transformed into that has some chance of being efficiently compiled in future.