asm2wasm emits instructions between `return` and `end`

[sunfishcode]

When given input containing trivially unreachable code, such as this:

Module["asm"] = (function() {
    'use asm';

    // EMSCRIPTEN_START_FUNCS

    function f(i) {
        i = i | 0;
        i = i+1;
        return i|0;
        i = i+2|0;
        return i|0;
    }

    // EMSCRIPTEN_END_FUNCS

    return {f: f};
})();

asm2wasm by default emits a wasm module containing unreachable code. Adding -O1 or other options to asm2wasm does cause it to eliminate such code. However, it may be useful to make asm2wasm eliminate at least unreachable code between a br/return/br_table/unreachable and the end of the enclosing block, since the current WebAssembly spec permits a variety of behaviors in such cases (Firefox and V8 currently differ, and other variations are permitted by the spec too). Also, there's an outstanding WebAssembly design discussion on this topic happening in WebAssembly/design#894 in which one of the options is to prohibit such instructions.

I noticed this issue while investigating
https://bugzilla.mozilla.org/show_bug.cgi?id=1324032, looking for possible causes for http://files.unity3d.com/jonas/benchmarks/5.5-wasm-release containing unreachable instructions, though I don't know for sure if the example above is the cause in that case.

[kripken]

Hmm, that unity file sounds like a release build, so it should have DCE already, so enabling DCE in -O0 wouldn't fix what you see.

Something else must be causing unreachable code there. It would be useful to find a testcase we can compile from source that shows the problem, so we can investigate this, it sounds like a bug. Maybe one easy way, if you have a program that checks for such unreachable code, is to run it on the emscripten test suite (anything it finds not in -O0 is a bug).

A not-great option to paint over the bug could be to manually remove code according to the pattern you mention. But our DCE should be fixing this. Also there isn't an obviously good place to do such an optimization, not until we add a stack machine output layer type thing as discussed in the past.

[lukewagner]

It seems like a good idea to have an "absolutely remove all obviously-dead code" pass in binaryen so that, if WebAssembly/design#894 gets resolved to disallow code between unconditional branches and end/else (which it now appears 3 browsers would prefer), we can trivially turn that on whenever wasm output is enabled so that, regardless of any previous passes, we can always get valid wasm output. Maybe this could even be integrated into the AST-to-binary pass since it should be quite easy to do if you're already recursively walking over the tree.

[kripken]

Yeah, agreed. That's what the DCE pass is supposed to be, so perhaps @sunfishcode found a bug in the pass. Or perhaps AB was compiled with an older and less effective version, or maybe the extra changes done to it over time caused that change (I've seen stacky code in there, for example, which the toolchain would not emit either).

If there's a way to get a VM that errors on unreachable code, we could use fuzzing to try to find such a bug.

[sunfishcode]

There is a patch for SM which implements this in https://bugzilla.mozilla.org/show_bug.cgi?id=1324032.

[lukewagner]

@kripken Do you think you'd be able to apply this patch to SM and run the test suite? It should just throw a validation error if it encounters this case.

[kripken]

Yup, already doing that as we speak...

[kripken]

Test suite finished. I verified that

• Most tests in -O0 fail with that SM patch.
• When enabling DCE in -O0, all tests pass once more.

So I can't see any bugs in DCE. I suspect the AB issue was due to the special and nonstandard way in which it has been manipulated.

So looks like if we need to we can enable DCE in -O0. It makes the asm2wasm phase around 3% slower (tested on libc++), so not too bad if we decide to do this.

[lukewagner]

Ok, thanks for doing that! I'll reach out to see how they're building AB.

[lukewagner]

In the meantime, even if it's only temporary until WebAssembly/design#894 gets resolved; it'd be most appreciated to always run DCE in -O0 that way this isn't an issue if we make that change.

[sunfishcode]

As an aside, the proposed rule in WebAssembly/design#894 only needs to delete all code after a br/br_table/return/unreachable until the end of its containing block/then/else/loop/function. If -O0 compile time is a concern, it should be possible to create a simple pass that just does the minimum necessary, which might be faster than full DCE.

[kripken]

@lukewagner What's the benefit to running DCE in -O0 now? I'm not opposed to doing it, I just don't get what we gain from it.

@sunfishcode If there's a benefit, I lean towards running DCE instead of writing a new pass, just for simplicity, and since 3% slowdown isn't that bad. But I'd measure more carefully first I guess.

[sunfishcode]

@kripken The benefit would be that it would help the WebAssembly project find any other sources of instructions between br/etc and end/etc in the wild that would need to be fixed if WebAssembly/design#894 gets resolved in the direction that 3 browsers appear to prefer.

[kripken]

By "other sources" do you mean "bugs in binaryen's DCE"? Or something more fundamental?

And how would the bugs be noticed - would you enable your patch in Firefox too..?

[sunfishcode]

I mean llvm, wabt, SM's wasmTextToBinary, or any other wasm producers out there. We could:

• locally apply the patch to SM
• run this custom SM on a bunch of wasm content from the wild
• if anything fails to validate, figure out what tool produced it and what would be needed to fix it

[kripken]

@sunfishcode: Yeah, all that sounds great. The Binaryen part of that was done as discussed above, finding no issues, so I guess you saying it's worth doing the same for other tools? (And this is not connected to the question of enabling DCE in -O0 in Binaryen?)