| Issue |
148253
|
| Summary |
[SCEV] Unbounded recursion in createSCEV leading to Stack Overflow
|
| Labels |
llvm:SCEV
|
| Assignees |
fhahn
|
| Reporter |
danilaml
|
I'm preparing a more concise reproducer currently as the original IR is ~4MB in size but the cause itself is rather simple and is already noted in the `createSCEVIter` implementation - there is a potentially unbounded recursion when dealing with the chain of PHIs that can exhaust the stack.
Phi handling was originally left out out of https://github.com/llvm/llvm-project/commit/675080a4533b91b3b62e51d3659629bc020fb940
```cpp
case Instruction::PHI:
// Keep constructing SCEVs' for phis recursively for now.
return nullptr;
```
But in the case of (pseudo ir):
```
bb1:
p1 = phi
a1 = add 1, p1
bb2:
p2 = phi [p1, bb1], ...
a2 = add 1, p2
bb3:
...
bbN:
pn = phi [pn-1, bbN-1], ...
an = add 1, pn
```
It could exhaust the stack with high enough `N` because when creating a SCEV for `an` it'll try to create addRecExpr using `StrengthenNoWrapFlags` with `pn` as one of the op for which `getSignedRange` would be called and since there is no SCEV for `pn` or `pn-1` due to bail out mentioned above it'll lead to the recursion until `bb1` is reached. With enough number of such basic block `opt` will crash with a segfault.
Was able to "fix" the crash locally with a naive patch:
```cpp
case Instruction::PHI: {
auto PHI = cast<PHINode>(U);
if (PendingPhiSCEVs.insert(PHI).second) {
llvm::append_range(Ops, PHI->incoming_values());
}
return nullptr;
}
```
plus cleanup in `createSCEVIter`:
```cpp
if (CreatedSCEV) {
insertValueToMap(CurV, CreatedSCEV);
if (auto *PHI = dyn_cast<PHINode>(CurV))
PendingPhiSCEVs.erase(PHI);
} else {
```
However, original implementation of this case before it was dropped was much more involved: https://reviews.llvm.org/D114650?id=400588
So my simple fix probably doesn't account for some corner cases (or is simply inefficient).
@fhahn do you think it'd be hard to implement this case properly? Also, even with `ulimit -s 1000` the IR size is approaching few hundred KBs, so not sure if it can be used as a lit test.
![]()
_______________________________________________
llvm-bugs mailing list
llvm-bugs@lists.llvm.org
https://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-bugs
