This somehow caused a regression in the wasm targets, which I bisected to here. Certain files when compiled with -O1 appear to hang for a very long time (maybe forever). This happened on the Bullet physics engine codebase in the Emscripten test suite, but affects all wasm targets (wasm32-unknown-unknown, -wasi, and -emscripten).

Seems reasonable to me, this restriction doesn't worry me, and great to have a clear error.

In D105510#2870173, @efriedma wrote:

Crash should be fixed by rG6144085c29b3

In D105510#2870147, @efriedma wrote:

In D105510#2870088, @kripken wrote:

This caused assertions to be hit on some tests as well as real-world code that we run.

Do all the failures you're seeing involve WidenIV::getWideRecurrence()?

This caused assertions to be hit on some tests as well as real-world code that we run. Here is a testcase:

I believe we have all agreed that this is the right path forward, and so this can land?

In D104808#2836942, @sunfish wrote:

Do we still intend to unify Emscripten's ABI with wasm32-unknown-unknown or wasm32-wasi eventually? This is talking a step away from that.

I'm not very familiar with this code, but it looks right, and sgtm to add a warning here.

Nice find!

I think this broke the LLVM roll on Emscripten CI. I don't have time to bisect atm, but this is the only wasm-related commit in the range, and the compiler crash is on a file and function modified in this patch:

In D95125#2522915, @SjoerdMeijer wrote:

In D95125#2522699, @kripken wrote:

As mentioned earlier VMs are working on this, and the benefit of them doing it is that code size matters quite a bit on wasm, and doing it there would be better.

Like I said, I am not from this field, but I don't see according to which criteria this is better:

• In terms of implementation, I guess letting the LLVM based producer do the loop-unrolling is better as loop-unrolling is a non-trivial optimisation (to do this properly) to (re)implement, this is leveraging the existing LLVM infrastructure, and enabling this is a few lines of code which much beat reimplementing loop-unrolling in a consumer.

In D95125#2522493, @SjoerdMeijer wrote:

Webassembly and runtimes is not my field, just saying so you can take my remarks with a bit (or a lot) of salt, but I do have a few opinions on loop-unrolling. :-)
I look at this problem slightly differently:

What concerns me is that some existing users will definitely be harmed by this, if the default for -O2 changes.

I.e., the way I look at this is that we deliver on of its promises:

WebAssembly aims to execute at native speed by taking advantage of common hardware capabilities available on a wide range of platforms.

If this is the goal, if we want parity with native execution, that means we would have to apply the same tricks as ahead of time compiled code, otherwise we would never achieve this. Loop-unrolling is known to greatly improve performance, and also to be an enabler for other optimisations. Thus, without loop-unrolling I don't think near native execution speeds will be feasible.

In D95125#2519248, @samparker wrote:

The unrolling would be disabled at -Os and -Oz, see

AFAIK, loop unrolling is disabled at -O1 for all targets. I don't think there's currently a backend mechanism to make a decision on the opt level, but the loop unroller uses them to adjust thresholds to be more aggressive in some situations.

In D95125#2516677, @tlively wrote:

I'm inclined to merge this and leave it to users for whom the code size increase is unacceptable to use -Os/-Oz/-fno-unroll-loops to disable it.

Very interesting perf data!

I don't know enough to tell if these changes are sufficient, but they make sense to me.

I'm not an expert on the LLVM details here, but, the logic looks correct and that it properly corresponds to the original idea of this optimization (that this will replace).

I don't understand the LLVM side enough to review, but running this locally it fixes all the issues we had earlier!

I can do a roll if needed, sure. (Is one needed? Let's see on the bots I guess...)

Just to be sure, is it ok to do this even when atomics are not enabled?

Thanks!

It looks like this pattern-matches on the switch's input. Does that mean that if we see a valid wrap there, we would also optimize this less?

In D77908#1977039, @sbc100 wrote:

As a less controversial version of this change I could instead create a new CPU called current and leave generic as is (basically leave it at mvp) until we can agree that a features is widespread enough to warrant being part of generic?

Is the general plan for LLVM documented somewhere?

Remove unneeded & in lambda capture.

In D74999#1887675, @aheejin wrote:

There seem to be multiple places that call Graph.getLoopEntries(). I guess we should sort all of them..? How about sort LoopEntries at the end of calculate() once and for all?

Nice, thanks! Will help with debug info coverage too.

Makes sense to me, nice. Also verified no crashes on wasm0 and wasm3 on the emscripten test suite.

lgtm module the error message, let's find the best phrasing there.

Nothing looks wrong to me here, but I don't know enough to fully understand it, sorry - like what the various indexes are, what a virtual address means here, etc.

To make sure I understand, is the issue that in the presence of a setjmp we turn those calls into invokes, which means in wasm we end up with an indirect call - and then in binaryen we don't see the emscripten_asm_const_int etc., and instead just the indirect call? (Or does the backend do more processing here?)

I'm not an expert on this but it looks right to me.

This looks right to me, but I'm not an expert on this stuff.

This may have broken CI, as it shows as one of the commits in the first broken roll here:

I bisected the failure on emscripten's wasm0.test_dylink_rtti (and two others, also failing on the waterfall) which hits

I'm in favor of this. There are a bunch of tradeoffs that VMs can make, and this lets them make their own choices, by emitting the higher-level construct, which is also smaller in size in the wasm.

Not an expert on this code but it looks right to me.

As mentioned on the issue, I'd prefer if we got imports for such globals, but if that's not possible then definitely an error instead of just silently emitting a 0 is better, lgtm.

Fair enough. Slightly worries me since it's not obvious from the name or the docs, and so perhaps it might change one day, but that's overly paranoid perhaps.

This broke wasm2.test_openjpeg on CI, reproducible locally. Errors on error: undefined symbol: __memory_base

Nice!

Thanks for the explanation! I think I understand.

Nice idea, and overall looks good to me. I didn't quite understand the TII part though.

I'm not that familiar with the BuildMI parts though.

Great, and thanks for the comments!

• Thanks, indeed one of the tests removed before (func_2) was still irreducible at -O0, restored it into the main irreducible file test, which is now at -O0. The other (tre_parse) was actually not irreducible, so we mis-identified it, and I left it out.
  • Fixed extra newline at the end of a test.
  • Renamed the title to have [WebAssembly]

Various changes from the feedback:

Review feedback changes, in particular:

What changes fixed the previous bug?

Code change lgtm, thanks!

This broke binaryen2.test_exceptions_white_list_2

From the point of view of FixIrreducibleControlFlow this sounds good.

Use SmallPtrSet for our sets, and return to using a vector for SortedEntries which we sort, avoiding SetVector.

• Use SetVector for determinism
• Simplify names in exceptions testcase
• Improve comments about canonicalization

Thanks for the comments, uploading an updated patch now.

Thanks, submitting a fixed patch now.

In D55467#1330455, @sunfish wrote:

In D55467#1326244, @kripken wrote:

In D55467#1326177, @sunfish wrote:

Do we know what part of the optimizer or codegen is introducing the irreducible control flow in malloc?

Some other musl libc elements with irreducible control flow that show up in a hello world are actually irreducible in the source (!), I verified.

Do you by chance remember which functions this was?

In D55467#1330401, @aheejin wrote:

Is it possible to reduce test cases more while they exhibit the same behavior? We usually try to avoid big generated test cases to our LLVM regression tests, so..

Thanks for the comments @aheejin!

In D55467#1326244, @kripken wrote:

In D55467#1326177, @sunfish wrote:

Do we know what part of the optimizer or codegen is introducing the irreducible control flow in malloc?

Not for malloc - I think @jgravelle-google may have been looking into that though?

Use llvm::sort following @mgrang's feedback. Thanks!

In D55467#1326177, @sunfish wrote:

Do we know what part of the optimizer or codegen is introducing the irreducible control flow in malloc?

No, I think I don't. I think someone else landed the few patches I had a few years ago.

Thanks aheejin!

In D11691#587616, @hughperkins wrote:

Hi, I have a project to rewrite llvm code as OpenCL https://github.com/hughperkins/cuda-on-cl It currently outputs lots of conditional branches, is labels and gotos, in the output .I want to 'reloop' this into fors/whiles/ etc. To what extent can I use the code in this PR to achieve this? What are the preferred option(s) for me to use this code from my own code? (eg drop the sourcecod into my repo? build as a shared object somehow? some other approach?)