Congrats! @nikic

Thanks for the patch.

Hi Sjoerd and JinGu, I remember from your comments on the initial DFAJumpThreading patch, that you guys are interested in the opportunities in SPEC2017 perlbench. I wanted to let you know that this patch introduces a limit on the number of threaded paths per switch. The limit is 200 paths, that means that if a switch has 1,000 potential path candidates, only 200 of them will get threaded, the rest of them will circle back to the switch instruction the usual way. The thing is that perlbench has several switches optimized by DFAJumpThreading, and a couple of them have the number of paths above the limit (in the thousands). Due to the limit, these switches are threaded partially, which might lead to performance regressions.

No noticeable compile time impact.

Compare the number of switches threaded before and after this patch.

Limit the number of paths explored to contain compile time.

I'm getting compile time numbers, will submit them soon. We're also planning on adding more test cases before the patch is merged.

Code size increase is very small.

In D122122#3397403, @xbolva00 wrote:

Also it would be interesting to have here some status/future plans/ideas to explore for new passes like CE by @fhahn, SLP with memory versioning, LoopFlatten, FuncSpecialization, DFA pass, etc..

@SjoerdMeijer
@aeubanks
@alexey.zhikhar

In D118590#3286616, @ollef wrote:

There are some seemingly unrelated failures in the Debian build. How do we handle that?

Thank you @ollef this LGTM

@niravd Hi Nirav, my team and I discovered a compile time regression due to this patch. I submitted a bug report for it, we would really appreciate if you could take a look at it:

I attach a picture of the CFG illustrating the problem in one of the llvm-test-suite tests that was failing on X86.

Thanks everybody.

Compile time statistics gathered on CTMark (no change, basically):

Thanks guys

Rebase on top of the latest main

In D99205#2899231, @SjoerdMeijer wrote:

Thanks, looking good. But one last request, sorry, can you add tests for the optimisation remarks too?

• Add a test for the minsize attribute
• Test MaxPathDepth with a test case where only a subset of paths is threaded
• Reduce the test case for the cost model by passing the threshold through CLI
• Fix a bug in how the NumTransforms statistic is incremented
• Expand the cost model to include the case for jump tables

• Add optimization remark emitter
• Test for min code size
• Test with blocks that cannot be cloned
• Test with some unsupported instructions
• Test unpredictable switch
• Replace all mentions of FSM with DFA
• Always use the term "Threading Path", instead of interchanging "threading" with "threadable"

In D99205#2873336, @SjoerdMeijer wrote:

Thanks for the updates.
If I am not mistaken, I still think tests are missing for cases when jump threading should *not* trigger:

I think some tests are missing, mostly negative tests:

• test for min code size,
• test with blocks that cannot be cloned,
• test with some unsupported instructions

Addressed the inline comments, added a co-author.

@efriedma ping.

@efriedma Eli, I believe all your comments have been addressed, please take another look when you get a chance, thanks.

Fix a clang-format warning

Fixed the bug submitted by @dnsampaio, test case added

In D99205#2792215, @alanphipps wrote:

Thanks for all of the effort! On our downstream Cortex-R5 compiler, I'm seeing a 20.4% speedup on Coremark with this patch, which is good, however, the older patch (https://reviews.llvm.org/D88307) gave me a 21.6% speedup. Any idea what could account for the difference there?

Addressed the rest of Florian's comments.

Addressed part of Florian's comments.

CFG before the patch, LCSSA broken:

In D68515#1872588, @jeroen.dobbelaere wrote:

Is the bitcast introduced by 'clang' (frontend), or was it introduced by one of the optimization passes ? In the latter case, which pass is this? We should probably handle it and
treat it as a 'gep with all-0 indices'... And make sure that the pointer-type for the llvm.noalias is somewhat usable.

If it is based on 'a pointer to int' conversion in the c-language, then it should be ok to just ignore it.

Jeroen, we discovered an assertion in introduceNoAliasWhenCopyGuardIndicesAreCompatible() for the case described below; we would appreciate your input.

@hiraditya Thank you very much for the code, I'm very interested in it. I'm trying to compile this and the 2/n revision together but I'm getting compilation failures, e.g.:

In D49994#1191386, @efriedma wrote:

I'd like an explanation for why the generated code is changing for AArch64... generating extra copies clearly seems like a downside. And there isn't any obvious reason for this change to impact register allocation: on AArch64, all i32 register classes contain exactly the same set of allocatable registers.

For some of the failing ARM/AArch64 tests, I see additional mov-s being performed; for example, in CodeGen/AArch64/and-sink.ll: if you take a look at the assembly after applying the patch, you will see an addtional mov for the trace when %c (w1) equals to zero. I'm not sure how important it is, so I would appreciate some feedback from ARM/AArch64 backend people. Please note that for performance-critical atomic compare-and-swap operations, performance is unchanged.

Differential is updated with:

All the test failures are mismatches between expected assembly and assembly produced. One exception is CodeGen/AMDGPU/early-if-convert.ll, where the backend fails with an assertion:

In D49994#1184441, @uweigand wrote:

The new code for f2 in cond-move-03.ll is in fact better, since it now actually uses the conditional move instruction instead of a branch ...

@jonpa Jonas, I see a different assembly in one of SystemZ unit tests; my memory of Z is pretty fuzzy, so could you please make sense of the change to see whether it is reasonable?

In D49994#1182189, @alexey.zhikhar wrote:

This patch fails 14 tests; however, it seems that the problem is not in the patch but in flaky test cases. I took a quick look at CodeGen/PowerPC/vsx.ll: the test case fails after not finding copy instructions, which were redundant and expectedly removed by this patch.

This patch fails 14 tests; however, it seems that the problem is not in the patch but in flaky test cases. I took a quick look at CodeGen/PowerPC/vsx.ll: the test case fails after not finding copy instructions, which were redundant and expectedly removed by this patch.

In D49994#1181808, @jonpa wrote:

Is this making sense, and what are your thoughts? What happens if you run your out-of-tree test cases with the SystemZ (-mcpu=z13) backend? Do you see any improvement? In that case, it seems like we have a test of real worth...

In D49994#1180443, @lebedev.ri wrote:

Probably needs tests. (Not that i know how to write one here)