<table border="1" cellspacing="0" cellpadding="8">
    <tr>
        <th>Issue</th>
        <td>
            <a href=https://github.com/llvm/llvm-project/issues/148253>148253</a>
        </td>
    </tr>

    <tr>
        <th>Summary</th>
        <td>
            [SCEV] Unbounded recursion in createSCEV leading to Stack Overflow
        </td>
    </tr>

    <tr>
      <th>Labels</th>
      <td>
            llvm:SCEV
      </td>
    </tr>

    <tr>
      <th>Assignees</th>
      <td>
            fhahn
      </td>
    </tr>

    <tr>
      <th>Reporter</th>
      <td>
          danilaml
      </td>
    </tr>
</table>

<pre>
    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.
</pre>
<img width="1" height="1" alt="" src="http://email.email.llvm.org/o/eJyUVl1vGzsO_TXyCxFjRuPxx4MfnKZGjIubGzR728dCI3E82sqSoA-73of97QtqbDdJuwUu4CBjm6QPD3lIihj13iKuWXvPOO8HMVjGOWsfJiKnwYW1ElYbcTCTzqnzesf44gA-oBdB2z0IOLiAIJ2VOiIE9MGpLDGAzCGgTeYMIkIaEFzQe22Fgd0n0BH-O_vzHrSFqP-D0OVUbKTIEUGniKYnoyDSgAGiPniDIKyiD4UJKNQZrEuoKAR5snklA4qELx8-ft4lDGxeQXE7oE0iaWfhjiwDlhjgXUKbtDDmDNl2LluFCgLKHCIZnwa0oFAYSvOk0zACHIS24Hp4ftxRWiKBFBbw-yByHHOISchvU1ZtngcNg7BqjCDijQFzBoN9Apcvfz0MKfnImg3jW8a3e52G3E2lOzC-NeZ4_Xfng_s3ysT4VrrDQdPDfNFWy0rM2qbpVnXXdHOOba2aebua81UnK1713WpWsWpDr3k1vqT3rNqAFBFhZ2MKWRJHBKHZPD_u6KHaAACMkOAPRE91vpjaPRDTkfEF9C6AH6hcI3tHNOfyoXWn6SVKwJSDBZuN8Smw5v41mBHbfU7XahZYrgfGlz5iVg50YHw1gnrn2XX1FayvgTUPhKW8FeNboRTUjH8AXxdzfjPnV3Ng7b0vNhStfaCn6XTELvi7KLxEacYoo1XXPd2C2jdB7d0l7NPdT4Htu8D2Z052CaTLRv3cYWNPDno_AFqX9wNJ4Im6vsNRRqWDiyhGpVK9SlnYvBK26CMxvjAGUjhDcqMtEqBPKD9-9wFyJFc2r15SQLtPA9on9yUIvzViHylEQcHmlS8BqcltqVxRvC8_dxq0LDZ7TC80bdQnYfdYvEtuHRXcGFRF4VFbiT-Uat0b4OPvXJ_vanqnMhL8TmhT9ESK185SvM4d8ZamQaHIkLD9EHq2SRsKR6UnUqiPhRxQTeELZXeh1-ZDh4Fyi1kO0ImoJXTGyW_k7Hwa6TAGZBBxGJkREHHfi2zSdCzoFxFBdKYApoGrvzPOx54vXsbJMiAu3lboI4IXSQ6X5n8n4N8qGNji_qI_kZOjoVVaToqYWPPh-XH35BSy5iPjy7-Lvq7mumjvGa3Sdv886KL1qbYRQ6IvHneMr6YRpbOK8dWrHwIoA6ugEN6jVV9DKTdf_uUj9fnz4-6ONR-1le6g7f7rUZiMkfElIXgNgi0efjM9rt-_Vow3OYI0KGz2NEt-tRX-D4_XnD8Ue0UOrxIbM_9MSP_l_hSeDHP4TOm8dfiB_hqwMM_45kq-OtuvvyrAGK8wcA0A8L4CGETEWwHeUAVoIl7wvubk0Z3wiIGg3lbwu8VY9Krj2Esd9rTSdSo7SwXnParyfKC-L_te26MzR1TUY29XV8CjxlOcUhNMXdgzvn2o69m8rViz1Yo1D7OqapdLVm1eHBzO193e6-_gg-tEZ86gHEbL-CKBkNJlm4r6ozvQpREsXRciYiR2XSDBliBn0Bb7XkuNNlF7XnbFrCpnDSgHZ5cpU_ttnAll9AwilKlw4-QVFz44j8GcWbOFjYmOSMQj2tvYy0YfdIK7CHVVEeFFyrtP41lDh4b3wQk50Bzt8QRDtiqggj_uixaiozMGYiZSeyKdzokOIUcaX3SoGJ0gYUzTiVo3atWsxATX9aLlfLaq62YyrDlvF5VsVdU2bb2Qzayaq9Vi1c6qvumWQk30mle8rRZ1Xbdt3TZTybGbV7JbrVZ1PavnbFbhQWhzK9tEx5hxXc-WvG0mRnRo4uVGvMh77PdyKYZ1OU66vI9sVhkd04_6T5JOppyXxaF9gL9_cWzpy6IqOi1zmvhKDl7KqvvriKE37jTJwaz_8alUUomMby_ZHNf8fwEAAP__Yj1vQQ">