Address comments.

@tlively kindly ping~

Minor change with comment

Also, please take care of compiler time regression.

Replace rem with bitmask operation

LGTM. Thanks!

LGTM, thanks for the fix.

@eopXD, hi, this patch make us lost +relax and -save-restore by default, would you please fix it?

LGTM with some comments.

This is general LGTM with some comments

address comment.

update testcase.

address paul's comment.

address comments. Set invalid cost for scalable vector broadcast.

In D116362#3213897, @dmgreen wrote:

This looks like it would treat the default cost of a broadcast as scalarising the first n elements from a <vscale x n x iM> vector, which doesn't sound right. Unless we are assuming that the default vscale is 1.

Yes， This patch keeps same behavior as before (release mode).

Add testcase in cost model.

In D116362#3212562, @spatel wrote:

It's fine to have a vectorizer test, but it would be better to have a more direct test of the cost model itself.

I think something like this can check for the crash (we could add variations to see if the cost is actually accurate - see /llvm/test/Analysis/CostModel/AArch64/sve-shuffle-broadcast.ll for an existing test model):

; RUN: opt -cost-model -analyze -mtriple=riscv64 -mattr=+m,+experimental-v -scalable-vectorization=on  < %s | FileCheck %s

define void @broadcast() {
  %zero = shufflevector <vscale x 16 x i8> undef, <vscale x 16 x i8> undef, <vscale x 16 x i32> zeroinitializer
  ret void
}

In D110613#3147744, @lkail wrote:

As reported in https://reviews.llvm.org/rGc93f93b2e3f28997f794265089fb8138dd5b5f13, we should implement a more general way to avoid adding quadratic edges in CFGs.

In rGc93f93b2e3f28997f794265089fb8138dd5b5f13#1040054, @lkail wrote:

Looks a more general way should be implemented in tailduplicator to avoid adding quadratic edges in CFGs.

LGTM

In D110613#3099467, @lkail wrote:

Do we have any benchmark on python, I think I can have a perf test with them before land this.

We don't have it in test-suite yet. In test-suite, we have SingleSource/Benchmarks/Misc/evalloop.c and MultiSource/Benchmarks/TSVC for computed-goto.

In D110613#3095582, @lkail wrote:

LGTM, let's land it first to unblock https://reviews.llvm.org/D106056. But one thing to notice, number of python's opcode is larger than 128. If this patch affects python's perf, I think we should seek another adequate default value.

Hi @lkail, since the value 128 can fix the ut, can we land this first, and then change this value if we have to. is it ok?

ping

In D110613#3054593, @lkail wrote:

I agree we should add limitation to such pattern of CFG. If not, quadratic number of edges are added to CFG and hurt compile-time, especially when there are 1K+ cases. The setting of tail-dup-jmptable-loop-size might be related to BTB or BTAC, of which I'm not an expert. But for now, we don't want to regress protobuf's compile-time, value of 128 need @alexfh 's confirm.

@alexfh kindly ping~

address comments.

Would it better use some parameter from GVNHoist? Also I do think maybe the default value is too large.

In D110613#3054163, @lkail wrote:

@lkail @MatzeB any suggestion with the parameter value 128?

From the perf data pasted by @alexfh in https://reviews.llvm.org/D106056, the compile time regression occurs in MachineBlockPlacement when CFG becomes complex. I think we should fix the issue there, i.e., fix the O(n^2) iteration by(There are multiple such usages, listed one)

It's not only MachineBlockPlacement pass, we saw Eliminate PHI and Control flow pass also cost much more time. with the ir file i attached above, it shows

In D110613#3029273, @junparser wrote:

In D110613#3027076, @lkail wrote:

IIUC, switching this pattern off might lose some optimization commonly seen in interpreter, e.g., https://eli.thegreenplace.net/2012/07/12/computed-goto-for-efficient-dispatch-tables. Do you have any benchmark numbers?

Hi, thanks for the reminder!
I tested the change with spec cpu2017, and there was no performance change. I also tested the case in https://eli.thegreenplace.net/2012/07/12/computed-goto-for-efficient-dispatch-tables, and I add it int tesetcase as well. This patch has no effect on most of the interpreter switch loop.

However, i test the case offered by @alexfh based on D106056 and w/o this change, it show 1x performance gains without the change. The reduced case is large_loop_switch in testcase.

The root reason is that llvm optimizer usually does not change unused default case into unreachable before D106056. The interpreter switch loop also keeps this branch when transform to jumptable, The loop form become to :

//                  
//              / <---------/ / /
//          0-> 1->  2  -> 3  / /            
//              \      \  -> 4 /              
//                \      \ -> 5             
//                  \---> default

the default bb can not tail duplicate into loop header. With D106056, the unreachable default bb is removed, then taildup can help to transform switch loop into dispatch table.

In D110613#3037724, @alexfh wrote:

In D110613#3029276, @junparser wrote:

So this change blocks optimization from D106056, @alexfh would you like to workaround with -mllvm -tail-dup-indirect-size=4？

I found a single huge protobuf generated source that was pushed over the time limit. However, there are likely many others that will just take more time to compile wasting resources and potentially increasing build latency. Having to hunt down all of them and to sprinkle -mllvm -tail-dup-indirect-size=4 all around the build configuration files would be unfortunate.

Or let add one more parameter such as -tail-dup-jmptable-size with default value maybe 100?
any suggest？

Would that stop this particular transformation for large switch cases? Should this always be done?

Add one parameter. @alexfh could you have a try with this patch?

So this change blocks optimization from D106056, @alexfh would you like to workaround with -mllvm -tail-dup-indirect-size=4？

In D110613#3027076, @lkail wrote:

IIUC, switching this pattern off might lose some optimization commonly seen in interpreter, e.g., https://eli.thegreenplace.net/2012/07/12/computed-goto-for-efficient-dispatch-tables. Do you have any benchmark numbers?

Add testcase diff between this change.

reduced bc file.

@alexfh Turns out it was caused by EarlyTailDuplicatePass, would you try with -mllvm -disable-early-taildup=true?

In D106056#3024102, @alexfh wrote:

In D106056#3024018, @junparser wrote:

In D106056#3023813, @junparser wrote:

In D106056#3023777, @xbolva00 wrote:

In D106056#3023709, @alexfh wrote:

We'd appreciate a prompt fix or a workaround. If neither is possible, please revert the commit while working on a proper solution.

Well, it is not "common" code, switch 1000 cases. But easy fix is probably to introduce some reasonable limit when to bail out.

switch 1000 cases is not the issue, use loop induction variable as condition is. It cause LVI recursive call SolveBlockValue.

@xbolva00 I was wrong. The compiler time regression is caused by CodeGen Passes rather than CVP or LVI.

This conclusion corresponds with the profile in my earlier comment (e.g. this line: 80.96% (anonymous namespace)::MachineBlockPlacement::buildLoopChains).

In D106056#3023813, @junparser wrote:

In D106056#3023777, @xbolva00 wrote:

In D106056#3023709, @alexfh wrote:

We'd appreciate a prompt fix or a workaround. If neither is possible, please revert the commit while working on a proper solution.

Well, it is not "common" code, switch 1000 cases. But easy fix is probably to introduce some reasonable limit when to bail out.

In D106056#3023777, @xbolva00 wrote:

In D106056#3023709, @alexfh wrote:

We'd appreciate a prompt fix or a workaround. If neither is possible, please revert the commit while working on a proper solution.

Well, it is not "common" code, switch 1000 cases. But easy fix is probably to introduce some reasonable limit when to bail out.

switch 1000 cases is not the issue, use loop induction variable as condition is. It cause LVI recursive call SolveBlockValue.

I've hit this issue in Jumpthreading pass. Maybe we should add one parameter for LVI::solve

In D106056#3023777, @xbolva00 wrote:

In D106056#3023709, @alexfh wrote:

We'd appreciate a prompt fix or a workaround. If neither is possible, please revert the commit while working on a proper solution.

Well, it is not "common" code, switch 1000 cases. But easy fix is probably to introduce some reasonable limit when to bail out.

In D106056#3023709, @alexfh wrote:

We'd appreciate a prompt fix or a workaround. If neither is possible, please revert the commit while working on a proper solution.

In D106056#3021866, @xbolva00 wrote:

In D106056#3021783, @alexfh wrote:

FYI, we see a ~5x increase in compile time on some of our code (mainly on some large protobuf-generated files) after rG8ba2adcf9e54b34ba8efa73ac0d81a1192e4f614. We're working on an isolated test case.

With switches with the huge number of cases?

In D109760#3001467, @chill wrote:

In D109760#3000216, @xbolva00 wrote:

I believe the latest issues with gvnhoist were regressions, what about to take a look at this pass again and possibly enable (some “obviously” profitable) parts of gvnhoist again?

Did you run spec benchmarks with trunk+gvnhoist?

I did and indeed I got even better speedup, but with -O2 -mllvm -enable-gvnhoist. With -O3 there was no improvement (and maybe a regression) (due to unrolling, see thread on the mailing list).

As for mcf, I guess it may casued by large register pressure due to hoist some expression from some huge successor. So simple cost model is necessary.

In D109760#3000216, @xbolva00 wrote:

I believe the latest issues with gvnhoist were regressions, what about to take a look at this pass again and possibly enable (some “obviously” profitable) parts of gvnhoist again?

Did you run spec benchmarks with trunk+gvnhoist?

Thanks for your patch！

@spatel ok for relanding?

In D106056#2972517, @nickdesaulniers wrote:

Hi @junparser , thank you kindly for helping us look into this; even building and booting kernels locally! Right now, we're chasing multiple regressions (https://github.com/ClangBuiltLinux/linux/issues/1438, https://github.com/ClangBuiltLinux/linux/issues/325#issuecomment-885197956, and this) with the first currently marked a clang-13 release blocker. Unless this patch fixes a regression marked as blocking the clang-13 release, can you please extend your generosity and patience so that we have another week to sort those out and revisit this?

@nathanchance @nickdesaulniers, any update?