| Issue |
242235
|
| Summary |
[InstCombine] visitAllocaInst is quadratic in alloca users; max-copied-from-constant-users does not bound the scan
|
| Labels |
new issue
|
| Assignees |
|
| Reporter |
vchuravy
|
`InstCombinerImpl::visitAllocaInst` is quadratic in the number of users of an alloca. The limit `-instcombine-max-copied-from-constant-users` (default 300) does not bound it. An alloca with N GEP users can be visited about N times, and each visit scans all N users, so a single InstCombine run takes O(N²) time.
### Reproducer
```llvm
declare void @use(ptr)
define void @f() {
%a = alloca [48000 x double], align 8
store [48000 x double] zeroinitializer, ptr %a, align 8
call void @use(ptr %a)
ret void
}
```
```
opt -passes='sroa,instcombine<max-iterations=1;no-verify-fixpoint>' -disable-output repro.ll
opt -passes='default<O2>' -disable-output repro.ll
```
SROA splits the first-class aggregate store into 48000 scalar stores, each with its own typed constant GEP (`%.fca.N.gep`). InstCombine then canonicalizes each GEP to `getelementptr i8`. Each of these changes puts the alloca back on the worklist, and each visit of the alloca scans all of its users.
### Timings
Release build, LLVM main from 2026-10-01 (c16c93955e84):
| N (`[N x double]`) | `sroa,instcombine` |
|---|---|
| 12000 | 0.46 s |
| 24000 | 1.45 s |
| 48000 | 5.26 s |
| 96000 | 22.45 s |
Doubling N makes the run about 4x slower. With `-O2`, InstCombinePass #1 accounts for 95% of the time (`-time-passes-per-run`). For `[16 x [64 x [186 x double]]]` (190k elements, 1.5 MB), `-O2` takes 334 s.
The result is the same on current main (41366ed3933c, assertions build). For N = 48000, `sroa,instcombine` takes 6.9 s, and 0.59 s with `-instcombine-max-copied-from-constant-users=0`.
The same scaling shows up in InstCombine alone, with no SROA, when the input is an alloca with N typed constant-index GEP+store users:
```python
n = 40000
print(f"declare void @use(ptr)\ndefine void @f() {{\n %a = alloca [{n} x double], align 8")
for i in range(n):
print(f" %g{i} = getelementptr inbounds [{n} x double], ptr %a, i64 0, i64 {i}")
print(f" store double 0.0, ptr %g{i}, align 8")
print(" call void @use(ptr %a)\n ret void\n}")
```
| N | `instcombine<max-iterations=1;no-verify-fixpoint>` |
|---|---|
| 10000 | 0.55 s |
| 20000 | 1.8 s |
| 40000 | 6.0 s (0.59 s with `-instcombine-max-copied-from-constant-users=0`) |
| 80000 | 27.4 s |
### Hot frames (perf)
```
70.3% llvm::InstCombinerImpl::visitAllocaInst(llvm::AllocaInst&) (isOnlyCopiedFromConstantMemory inlined)
17.0% llvm::GetElementPtrInst::hasAllZeroIndices() const
7.7% llvm::InstCombinerImpl::visitAllocSite(llvm::Instruction&)
```
### Cause
In `isOnlyCopiedFromConstantMemory` (InstCombineLoadStoreAlloca.cpp), the `MaxUsers` limit is checked only when a value is popped from the worklist (`Visited.size() > MaxUsers`). The inner `for (auto &U : Value->uses())` loop runs over all uses of the alloca and calls `hasAllZeroIndices()` on every GEP before the limit is checked. A single call is therefore O(#uses) for any `MaxUsers` greater than 0. A possible fix is to count the uses scanned (or check `Worklist.size() + Visited.size()`) inside the inner loop.
A related point: SROA (and `unpackStoreToAggregate` in InstCombine, whose `maxarray-size` limit applies to each nesting level, not to the total) splits a `store [N x T] zeroinitializer` into N scalar stores, however large N is. For a large zero store, a `memset` would be a better result.
### Where we hit this
Fortran automatic arrays in a climate model at production resolution. An AD tool (Enzyme) zeroes the shadow allocas with aggregate `zeroinitializer` stores of types such as `[20 x [86 x [186 x double]]]` (2.5 MB). `clang -O2` on the result ran for hours in `visitAllocaInst`. Before the fix, `-mllvm -instcombine-max-copied-from-constant-users=0` is a workaround.
_______________________________________________
llvm-bugs mailing list
[email protected]
https://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-bugs