[SelectionDAG][DAGCombiner] Compile time blows up in TokenFactor inlining for a basic block with a few thousand strided stores
- Dominant language
- LLVM
- Stars
- 40.5k
- Forks
- 18.7k
- PR merge metrics
- PR metrics pending
Description
```c
extern unsigned arr[5000][5000];
void test(void) {
#pragma clang loop unroll(enable)
#pragma clang loop interleave(enable)
for (unsigned i = 0; i < 5000; i += 1)
arr[i][i] = 0;
}
```
```
$ clang -O3 -w -c reduced.c
# appears to hang
```
This reproduces also with `extern unsigned arr[1][1]`, if you don't mind the UB (write out of bounds).
A single basic block containing ~2000 strided stores makes the SelectionDAG DAGCombiner take effectively unbounded time. Mid-end finishes in ~0s and produces seemingly regular IR; all the time is spent in `llc`/ISel.
The time explodes with `-combiner-tokenfactor-inline-limit`, measurements below. At the default 2048 I stopped the compile after 30min.
This isn't a miscompile - the generated code is correct when the compile is allowed to finish (checked for values < 2048).
## Middle end not involved:
```
$ time clang -O3 -w -S -emit-llvm reduced.c -o reduced.ll
real 0m0.0s
$ grep -c ' store ' reduced.ll
2000
```
`reduced.ll` has 2 basic blocks and 2000 `store` instructions. Feeding it
straight to `llc` reproduces:
```
$ llc -O3 reduced.ll -o /dev/null # hangs
$ llc -O3 -combiner-disabled reduced.ll -o /dev/null
real 0m2s
```
`-O2` and `-O3` emit byte-identical IR here, so the problem is not tied to a single optimisation level.
## Localisation: TokenFactor inlining
Disabling DAGCombine entirely fixes it, so I bisected the combiner's `cl::opt` knobs. Only `-combiner-tokenfactor-inline-limit` matters:
| knob | result |
| --- | --- |
| `-combiner-disabled` | 2 s |
| `-combiner-tokenfactor-inline-limit=32` | 25 s |
| `-combiner-store-merging=false` | hangs |
| `-combiner-store-merge-dependence-limit=2` |hangs |
| `-combiner-use-tbaa=false` | hangs |
Scaling the limit on `reduced.ll`:
| `-combiner-tokenfactor-inline-limit` | time |
| --- | --- |
| 32 | 25 s |
| 64 | 31 s |
| 128 | 57 s |
| 256 | 173 s |
| 512 | 758 s |
| 2048 (default) | > 30 min, not finished |
Extrapolating suggests the default would take several hours.
This points at `DAGCombiner::visitTokenFactor` / `SelectionDAG::getTokenFactor` in `llvm/lib/CodeGen/SelectionDAG/DAGCombiner.cpp`. With 2000 chained stores the combiner repeatedly flattens large TokenFactor operand lists, and the work done per flattening scales with the limit while the number of flattenings also scales with the chain length.
## Not memory exhaustion:
A 30-minute run on the original test case held RSS flat at 124 MB for the whole duration while burning 1800 s of CPU. It is spinning, not allocating.
## Sensitivities
Removing any of these makes the problem disappear:
- **Both pragmas.** `unroll(enable)` alone or `interleave(enable)` alone is fine; only the pair triggers it.
- **Trip count.** 4000 compiles in 1 s; 6000 and up hang.
- **Two-dimensional subscript.** A flat `arr[i*13] = 0` is fine.
- **Array element count must not be a power of two.** `[12][12]`, `[6][6]` and `[3][3]` hang; `[4][4]`, `[8][8]` and `[2][2]` do not. Presumably the power-of-two strides let an earlier combine collapse the address arithmetic before the store chain gets long.
Not sensitive to: `-fno-vectorize`, `-fno-slp-vectorize`, `-fno-unroll-loops`, `extern` vs. a definition, or C vs. C++.
This appears to be a regression between clang 20 and 21.
Found by my [my yarpgen fork](https://github.com/OfekShilon/yarpgen_wsl), seed 2386185415.
Contributor guide
Research direction
Start with the reduced.c reproducer and reduced.ll, running clang -O3 and llc -O3 with and without DAGCombine to confirm the time difference. Read DAGCombiner::visitTokenFactor in llvm/lib/CodeGen/SelectionDAG/DAGCombiner.cpp and SelectionDAG::getTokenFactor, focusing on the token-factor inline limit and long chained stores. Done means the reproducer no longer exhibits effectively unbounded compile time while retaining correct generated code.
Written by the indexing model from the issue text.
Assessment
- Tech stack
- c
- Domain
- compilers
- Issue type
- Bug
- Difficulty
- 4/5
- Estimated time
- 3-5 days
- Activity status
- Active
- Clarity
- Mostly clear
- Newbie friendliness
- 45/100