[SCEV] Unbounded recursion in createSCEV leading to Stack Overflow

[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 675080a

  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:

  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:

    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.

[danilaml]

@fhahn apologies for the delay, llvm-reduce is still running (initial IR was quite big), but here is the intermediary result:
https://gist.github.com/danilaml/75f1117c8a4ab2928750db8699b1356b

On my machine it crashes with stack overflow if I set ulimit -s 880 and run opt -passes=loop-unroll -S reduced.ll. This is for opt built with assertions enabled. Release build might need slightly different stack limit. Original test case was crashing with the default stack size, but you can see that this one can be easily extended to exhaust any stack size just by adding new BBs of the form discussed above.

[danilaml]

@fhahn Was your implementation for Phi case in https://reviews.llvm.org/D114650?id=400588 complex to avoid unnecessary computations or was it a correctness issue? My naive "fix" seems to work but a few lit tests fail but so far the ones I've examined are optimization issues not miscompiles (i.e. exitcount previously resolved to 0 became -1 + (1 umax undef) with my changes which we don't fold for some reason).

[danilaml]

ping