llvm / llvm/llvm-project

[SelectionDAG][DAGCombiner] Compile time blows up in TokenFactor inlining for a basic block with a few thousand strided stores

Open
#221,433 0 comments 0 reactions 0 assignees View on GitHub
hang llvm:SelectionDAG regression:21 slow-compile
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

Open the contributing 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

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.