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

Reply via email to