[SimpleCFG] Missed tail-merge/sinking of common call sequences across a subset of switch cases
- Dominant language
- LLVM
- Stars
- 40.5k
- Forks
- 18.7k
- PR merge metrics
- PR metrics pending
Description
## Summary
LLVM can miss a profitable tail-merge opportunity when several `switch` successors end in the same call sequence, but another successor to the same exit block has a different, non-mergeable call sequence.
The desired transform is to sink the common call into a shared block and use `phi` nodes for the operands that differ by predecessor.
This is the same shape as the QEMU `tcg_gen_andi_i32` pattern: multiple special cases emit the same helper call with different opcode/operand values, while other paths either skip the helper call or emit a different helper.
## Reduced Reproducer
```llvm
target triple = "x86_64-unknown-linux-gnu"
declare void @op2(i32)
declare void @op3(i32)
define void @f(i32 %x) {
entry:
switch i32 %x, label %default [
i32 0, label %case0
i32 1, label %case1
i32 2, label %case2
]
case0:
call void @op2(i32 10)
br label %exit
case1:
call void @op2(i32 20)
br label %exit
case2:
call void @op2(i32 30)
br label %exit
default:
call void @op3(i32 %x)
br label %exit
exit:
ret void
}
```
Local file: `tail-merge-subset-3case-min.ll`
## Command
```bash
opt -S -passes='default' tail-merge-subset-3case-min.ll -o -
```
Tested locally with:
```text
LLVM version 23.0.0git
```
## Actual Result
The three `@op2` calls remain duplicated:
```llvm
case0:
tail call void @op2(i32 10)
br label %exit
case1:
tail call void @op2(i32 20)
br label %exit
case2:
tail call void @op2(i32 30)
br label %exit
```
## Expected Result
LLVM could sink the common `@op2` call into a shared block and select the differing operand with a `phi`:
```llvm
case0:
br label %op2.common
case1:
br label %op2.common
case2:
br label %op2.common
op2.common:
%op = phi i32 [ 10, %case0 ], [ 20, %case1 ], [ 30, %case2 ]
call void @op2(i32 %op)
br label %exit
default:
call void @op3(i32 %x)
br label %exit
```
Local expected-shape file: `tail-merge-subset-3case-min-ideal.ll`
After this canonicalization, existing optimizations may simplify the `phi` further. For example, this particular reduced case can become a range check plus `10 * x + 10` for the `@op2` argument.
## Why This Should Be Legal
The transform preserves the dynamic call behavior:
- Each original path that called `@op2` still calls `@op2` exactly once.
- The `default` path still calls `@op3` and does not enter the shared `@op2` block.
- Only call operands that differ between merged predecessors are replaced with `phi` nodes.
- The call itself is not speculated onto paths where it was not originally executed.
In the motivating QEMU-like form, guarded paths that skip the helper call should continue to branch directly to the exit block. Only the non-skip helper-emitting edges should enter the common call block.
## Motivation
In the motivating QEMU `tcg_gen_andi_i32` case, several switch arms perform the same helper-call setup and differ mainly in opcode/source operands. Manually commoning the helper-call sequence reduced the modeled block throughput in the measured backend output from roughly:
```text
Block RThroughput: 8 -> 6
```
The dynamic number of helper calls is unchanged, but the machine CFG/codegen can improve because duplicated call setup, unconditional branches, and exit handling are reduced or laid out more effectively.
## Notes
LLVM already handles the simpler case where all switch successors share the same call shape and only operands differ. For example:
```llvm
case0:
call void @op2(i32 10)
br label %exit
case1:
call void @op2(i32 20)
br label %exit
default:
call void @op2(i32 %x)
br label %exit
```
is optimized into a single `@op2` call with a `phi` argument.
The missed opportunity here is subset tail-merging: merge the compatible `@op2` successors even when other successors to the same exit block are not compatible with that merge.
AliveProof : https://alive2.llvm.org/ce/z/P9Jxpk
Compiler-Explorer & Perf : https://compiler-explorer.com/z/zvaY4abq7
RealWorld Usage: https://github.com/dtcxzyw/llvm-opt-benchmark-nightly/pull/347/changes#diff-4d5d4501ba38b26c070e9200a0f0f0b84f6f97fb782a7e5d4d766a50c789e1e4L414
more usage: https://github.com/dtcxzyw/llvm-opt-benchmark-nightly/pull/347/changes/3f664f7d50e1b945cf2d34a4bf4be00340342719#diff-42f22a6ec28d7bc4f2463d40855f5e9652d28edadf07fc738f4a957d33d6279c
Contributor guide
Assessment
This issue has not been assessed yet.