Poor optimization of switch statement in Clang 19.1.0 compared to Clang 18.1.0

[inicula]

I was doing some tests/benchmarks regarding switch vs array look-ups and found this change in behavior from Clang 18.1.0 to Clang 19.1.0 (and current trunk):

• https://godbolt.org/z/o4TYYdr4e (original code)
• https://godbolt.org/z/1bh3KdPzY (more minimal reproduction, without the benchmark boilerplate)

Clang 18.1.0 optimizes that big switch as a constant lookup table:

        lea     rcx, [rip + .Lswitch.table.main]
.LBB0_12:
        movzx   edx, byte ptr [rbx + rax - 3]
        xor     edx, 128
        mov     rdx, qword ptr [rcx + 8*rdx]
        inc     byte ptr [rsp + rdx + 112]

On the other hand, Clang 19.1.0 generates a separate label for each switch case, and every label feeds into a main one:

.LBB0_28:
        lea     rcx, [rsp + 665] ; case 1: return 553;
        jmp     .LBB0_283
.LBB0_29:
        lea     rcx, [rsp + 653] ; case 2: return 541;
        jmp     .LBB0_283
; ..............................
.LBB0_283:
        inc     byte ptr [rcx]
        inc     rbp
        cmp     rbp, 300000000
        je      .LBB0_20
        movzx   ecx, byte ptr [rbx + rbp]
        movsxd  rdx, dword ptr [rax + 4*rcx]
        add     rdx, rax
        mov     rcx, r13
        jmp     rdx

This can tank the performance, for example if the branch predictor can't accurately predict which label you're going to access on the current iteration. In my example I'm generating random indexes and with perf stat I'm seeing almost 300 million branch misses (one for each increment() invocation).

Assuming that this change isn't an intentional trade-off made for a benefit in some other usecases, then this is a regression.

On my machine, the results of running that binary (same source code as the one in Godbolt) compiled with Clang 18 vs Clang 19 are as follows:

clang 18 = elapsed: 254ms sum: 28928
clang 19 = elapsed: 2813ms sum: 29184

So the binary generated by Clang 19 is about 11 times slower.

NOTE: The issue seems to be related to inlining, because if I add __attribute__((noinline)) to the increment() function, then Clang 19 optimizes it with a lookup table, just like Clang 18, and the result is much faster than what I get with inlining allowed:

elapsed: 548ms sum: 28928

[inicula]

I added a more minimal reproduction (without the benchmarking boilerplate) in the issue description.

[u4f3]

https://godbolt.org/z/9n4hGc1cs
[Relevant PR in SROA](aeubanks:sroa-phi2)
tradeoff between SROA and SimplifyCFG

[nikic]

Ideally we'd prevent unfolding for cases which can't be SROAd anyway, but I think the most straightforward fix for this would probably be to insert the GEPs into the phi predecessor blocks instead of the entry block. In that case we should be able to sink them down again in SimplifyCFG.

[u4f3]

I'd like to work on this but I'm not very sure where is the best place to put the sink part. And I'm not sure if transforming phi ((gep ptr, idx1), (gep ptr, idx2)) to gep ptr phi(idx1, idx2) is a universal beneficial if nothing gets SROAd. If so maybe we should not put it in SimplifyCFG. Else we should sink them somewhere near switchToLookupTable in SimplifyCFG.

[nikic]

[...] but I think the most straightforward fix for this would probably be to insert the GEPs into the phi predecessor blocks instead of the entry block. In that case we should be able to sink them down again in SimplifyCFG.

Done in #127652, but this didn't work out because LICM still ends up hoisting the GEPs, before SimplifyCFG can sink them.

I'd like to work on this but I'm not very sure where is the best place to put the sink part. And I'm not sure if transforming phi ((gep ptr, idx1), (gep ptr, idx2)) to gep ptr phi(idx1, idx2) is a universal beneficial if nothing gets SROAd. If so maybe we should not put it in SimplifyCFG. Else we should sink them somewhere near switchToLookupTable in SimplifyCFG.

SimplifyCFG already does sinking, but it expects the instructions to be in the predecessor blocks. It won't try to sink instructions from other blocks. You could try allowing that for instructions that aren't used anywhere except the phi node.

The other way to fix this is to prevent SROA from making the transform. The select/phi unfolding is something of a hack, because it's done unconditionally. SROA also has handling to speculate accesses of selects/phis (see e.g. speculatePHINodeLoads). I believe the gep/select unfolding is only ever actually useful in conjunction with those, so it would make sense to extend them to also support an intermediate gep. This would ensure we only perform the transform when it enables SROA. Doing this is probably fairly tricky though.

[sharkautarch]

@nikic What if you just changed the currently-unconditional select/phi unfolding SROA code to prevent it from unfolding gep of phis that have more than some arbitrarily chosen number of (unique) incoming values originating from the (same) switch instruction. That, or prevent the code from unfolding gep of phis with more than a certain number of incoming values entirely.
This might not be the best long term solution, but maybe (short of reverting Pr #83494 entirely) it'll be the easiest (or most straightforward) short-term solution?

[u4f3]

My understanding towards sinkCommonCodeFromPredecessors:

1. (I don't know if this point is right) SimplifyCFG use LockstepReverseIterator to traverse all the unconditional incoming predecessors, but

   llvm-project/llvm/lib/Transforms/Utils/SimplifyCFG.cpp

   Line 2190 in 8ff4d27

   for (const Use &U : I0->uses()) {

   
   Does that mean actually the common code we sink must be a phi node's incoming value? If so, maybe we could traverse directly the phi node's incoming values to seek for candidates to be sunk later.

2. Maybe we could try to combine canSinkInstructions and ProfitableToSinkInstruction together.

Directly about the issue, I'm trying to allow SimplifyCFG to sink code from other blocks

The result compile with O2

Simply sink code from other blocks will not solve the problem directly since there's an use of arr directly as incoming value of the specific phi node.

[sharkautarch]

My understanding towards sinkCommonCodeFromPredecessors:

1. (I don't know if this point is right) SimplifyCFG use `LockstepReverseIterator` to traverse all the unconditional incoming predecessors, but 
     
       
         [llvm-project/llvm/lib/Transforms/Utils/SimplifyCFG.cpp](https://github.com/llvm/llvm-project/blob/8ff4d27fe6b32ea1a127758c121cc2a980439833/llvm/lib/Transforms/Utils/SimplifyCFG.cpp#L2190)
       
       
            Line 2190
         in
         [8ff4d27](/llvm/llvm-project/commit/8ff4d27fe6b32ea1a127758c121cc2a980439833)
       
     
     
       
   
           
             
              for (const Use &U : I0->uses()) { 
           
       
     
   
   
   Does that mean actually the common code we sink must be a phi node's incoming value? If so, maybe we could traverse directly the phi node's incoming values to seek for candidates to be sunk later.

2. Maybe we could try to combine `canSinkInstructions` and `ProfitableToSinkInstruction` together.

Directly about the issue, I'm trying to allow SimplifyCFG to sink code from other blocks.

The result compile with O2

Simply sink code from other blocks will not solve the problem directly since there's an use of arr directly as incoming value of the specific phi node.

Did you check what the IR output right after simplifyCFG finishes (for llvm built w/ your draft PR)?
In case you don't know how, you can use
-mllvm --print-after=<string> to print the IR after a pass
and -mllvm --print-before=<string> to print the IR after a pass

and to print the IR that's changed there's:

 --print-changed=<value>                                                    - Print changed IRs
    =quiet                                                                   -   Run in quiet mode
    =diff                                                                    -   Display patch-like changes
    =diff-quiet                                                              -   Display patch-like changes in quiet mode
    =cdiff                                                                   -   Display patch-like changes with color
    =cdiff-quiet                                                             -   Display patch-like changes in quiet mode with color
    =dot-cfg                                                                 -   Create a website with graphical changes
    =dot-cfg-quiet                                                           -   Create a website with graphical changes in quiet mode

EDIT: Here's a gist link that shows the diff for the last run of SimplifyCFG (w/ llvm built w/ your PR):
https://gist.github.com/sharkautarch/872e68926b96639eaa1c027f1ea0d7cf

Also, looking at the assembly output for llvm built w/ your PR, it looks more like the clang18 assembly from the godbolt link now
The getelementptr inbounds nuw i8, ptr %arrs in vector.body I think may be due to automatic vectorization and/or unrolling, so unrelated to the regression
And wrt there still being one getelementptr inbounds nuw [256 x i64], ptr @switch.table in for.body.prol, but the rest being in for.body, I think that matches clang 18 behavior
Why? Because if you look at the 2nd godbolt link that was included in the OP of this Issue, for the compiler output for clang 18, there was actually still two separate lea rdx, [rip + .Lswitch.table.foo(std::vector<unsigned char, std::allocator<unsigned char>> const&)] that were emitted, one of each in a different bb, and that's the same behavior for the assembly output for llvm built w/ your PR

Note that I had built llvm with both your PR, and some other PRs that haven't been merged into upstream yet, so my output may be a bit different than yours.
@u4f3 So I would conclude that it seems to me that your PR already fixes the regression (in perf of clang 19+ compared to clang 18), at least for the godbolt example
Yes, there seems to be a redundant table lookup, but seems like that actually matches clang 18 behavior, so...

EDIT 2:
Btw, I just realized that the extra lea rdx, [rip + .Lswitch.table.foo(std::vector<unsigned char, std::allocator<unsigned char>> const&)] goes away if you add the compiler option -fno-unroll-loops...

[u4f3]

Thanks for your reply @sharkautarch. I will update the code in my draft pr to avoid some misunderstanding. Actually I don't notice if there are redundant getelementptr or leas. Sorry for any inconvenience.

I actually means arr is directly used in the phi node prevents sinking code directly. All other incoming geps are of the same structure. (1)So I have added another piece of heuristic code to try to transform the alloca into a gep with zero offset to make sunk happen. I wonder if this is right or if it will only introduce more bugs.

%retval.0.i.i.sroa.phi = phi ptr [ %retval.0.i.i.sroa.gep, %sw.bb255.i.i ], [ %retval.0.i.i.sroa.gep13, %sw.bb254.i.i ], [ %arr, %sw.bb161.i.i ], ...

The idea is based on previous sinkCommonCodeFromPredecessors. And I find it a little bit difficult for me to understand some part of it (and it seems that it is linked with other issues):

(2) IF we are only trying to sink instructions from phi's incoming, maybe we could use phi's incoming values directly as candidates we would like to sink later instead of using LockstepReverseIterator.

(3) Maybe we could try to combine canSinkInstructions and ProfitableToSinkInstruction together.

My questions are (1) (2) (3). @nikic