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

    <tr>
        <th>Summary</th>
        <td>
            [SCEV] Segfault in SCEV LoopGuards
        </td>
    </tr>

    <tr>
      <th>Labels</th>
      <td>
            llvm:crash,
            llvm:SCEV,
            crash-on-valid
      </td>
    </tr>

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

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

<pre>
    For the following IR:
```llvm
target datalayout = "e-m:e-p270:32:32-p271:32:32-p272:64:64-i64:64-i128:128-f80:128-n8:16:32:64-S128-ni:1-p2:32:8:8:32-ni:2"
target triple = "x86_64-unknown-linux-gnu"

define void @foo() {
.split.us120:
  br label %.split.us120.split.split.us.split.split.us.split.split.us.split

.split.us120.split.split.us.split.split.us.split.split.us.split: ; preds = %.noexc7.us.us.us.us.us, %.split.us120
  br label %.noexc7.us.us.us.us.us

.lr.ph.us.us.us.us407: ; No predecessors!
  switch i32 0, label %.split142.us.split.us.split.us [
 i32 0, label %.split160.us.split.us.split.us
    i32 1, label %.noexc7.us.us.us.us.us
  ]

.noexc7.us.us.us.us.us: ; preds = %.noexc7.us.us.us.us.us, %.lr.ph.us.us.us.us407, %.split.us120.split.split.us.split.split.us.split.split.us.split
  %0 = phi i32 [ %1, %.noexc7.us.us.us.us.us ], [ 0, %.lr.ph.us.us.us.us407 ], [ 0, %.split.us120.split.split.us.split.split.us.split.split.us.split ]
  %1 = add i32 %0, 1
  %.not.i3.us.us.us.us384.us = icmp slt i32 %0, 0
  br i1 %.not.i3.us.us.us.us384.us, label %.noexc7.us.us.us.us.us, label %.split.us120.split.split.us.split.split.us.split.split.us.split

.split142.us.split.us.split.us: ; preds = %.lr.ph.us.us.us.us407
  ret void

.split160.us.split.us.split.us:                   ; preds = %.lr.ph.us.us.us.us407
  ret void
}
```
`opt` crashes when run using `-passes=nary-reassociate --scalar-evolution-use-expensive-range-sharpening`

godbolt: https://godbolt.org/z/xPv4TMMo8

Backtrace (truncated due to length limits):
````
PLEASE submit a bug report to https://github.com/llvm/llvm-project/issues/ and include the crash backtrace.
Stack dump:
0.      Program arguments: /opt/compiler-explorer/clang-assertions-trunk/bin/opt -o /app/output.s -S -passes=nary-reassociate --scalar-evolution-use-expensive-range-sharpening <source>
1.      Running pass "function(nary-reassociate)" on module "<source>"
2.      Running pass "nary-reassociate" on function "foo"
  #0 0x0000000005257198 llvm::sys::PrintStackTrace(llvm::raw_ostream&, int) (/opt/compiler-explorer/clang-assertions-trunk/bin/opt+0x5257198)
  #1 0x0000000005254b9c SignalHandler(int) Signals.cpp:0:0
  #2 0x00007f9ab9c42520 (/lib/x86_64-linux-gnu/libc.so.6+0x42520)
  #3 0x00000000051640cb llvm::hash_value(llvm::APInt const&) (/opt/compiler-explorer/clang-assertions-trunk/bin/opt+0x51640cb)
  #4 0x00000000051641a9 llvm::DenseMapInfo<llvm::APInt, void>::getHashValue(llvm::APInt const&) (/opt/compiler-explorer/clang-assertions-trunk/bin/opt+0x51641a9)
  #5 0x0000000004ed726b bool llvm::DenseMapBase<llvm::DenseMap<llvm::APInt, std::unique_ptr<llvm::ConstantInt, std::default_delete<llvm::ConstantInt>>, llvm::DenseMapInfo<llvm::APInt, void>, llvm::detail::DenseMapPair<llvm::APInt, std::unique_ptr<llvm::ConstantInt, std::default_delete<llvm::ConstantInt>>>>, llvm::APInt, std::unique_ptr<llvm::ConstantInt, std::default_delete<llvm::ConstantInt>>, llvm::DenseMapInfo<llvm::APInt, void>, llvm::detail::DenseMapPair<llvm::APInt, std::unique_ptr<llvm::ConstantInt, std::default_delete<llvm::ConstantInt>>>>::LookupBucketFor<llvm::APInt>(llvm::APInt const&, llvm::detail::DenseMapPair<llvm::APInt, std::unique_ptr<llvm::ConstantInt, std::default_delete<llvm::ConstantInt>>>*&) (/opt/compiler-explorer/clang-assertions-trunk/bin/opt+0x4ed726b)
  #6 0x0000000004edb996 llvm::ConstantInt::get(llvm::LLVMContext&, llvm::APInt const&) (/opt/compiler-explorer/clang-assertions-trunk/bin/opt+0x4edb996)
 #7 0x0000000004eeba30 llvm::ConstantInt::get(llvm::Type*, llvm::APInt const&) (/opt/compiler-explorer/clang-assertions-trunk/bin/opt+0x4eeba30)
  #8 0x0000000004eb6172 llvm::ConstantFoldBinaryInstruction(unsigned int, llvm::Constant*, llvm::Constant*) (/opt/compiler-explorer/clang-assertions-trunk/bin/opt+0x4eb6172)
  #9 0x0000000004ee9f2e llvm::ConstantExpr::get(unsigned int, llvm::Constant*, llvm::Constant*, unsigned int, llvm::Type*) (/opt/compiler-explorer/clang-assertions-trunk/bin/opt+0x4ee9f2e)
 #10 0x00000000049427fb llvm::ScalarEvolution::getNegativeSCEV(llvm::SCEV const*, llvm::SCEV::NoWrapFlags) (/opt/compiler-explorer/clang-assertions-trunk/bin/opt+0x49427fb)
 #11 0x00000000049429c4 llvm::ScalarEvolution::getMinusSCEV(llvm::SCEV const*, llvm::SCEV const*, llvm::SCEV::NoWrapFlags, unsigned int) (/opt/compiler-explorer/clang-assertions-trunk/bin/opt+0x49429c4)
 #12 0x0000000004950e7a llvm::ScalarEvolution::LoopGuards::collectFromBlock(llvm::ScalarEvolution&, llvm::ScalarEvolution::LoopGuards&, llvm::BasicBlock const*, llvm::BasicBlock const*, llvm::SmallPtrSetImpl<llvm::BasicBlock const*>&, unsigned int) (/opt/compiler-explorer/clang-assertions-trunk/bin/opt+0x4950e7a)
 #13 0x00000000049524c2 llvm::ScalarEvolution::LoopGuards::collectFromPHI(llvm::ScalarEvolution&, llvm::ScalarEvolution::LoopGuards&, llvm::PHINode const&, llvm::SmallPtrSetImpl<llvm::BasicBlock const*>&, llvm::SmallDenseMap<llvm::BasicBlock const*, llvm::ScalarEvolution::LoopGuards, 4u, llvm::DenseMapInfo<llvm::BasicBlock const*, void>, llvm::detail::DenseMapPair<llvm::BasicBlock const*, llvm::ScalarEvolution::LoopGuards>>&, unsigned int)::'lambda'(unsigned int)::operator()(unsigned int) const ScalarEvolution.cpp:0:0
 #14 0x0000000004952702 llvm::ScalarEvolution::LoopGuards::collectFromPHI(llvm::ScalarEvolution&, llvm::ScalarEvolution::LoopGuards&, llvm::PHINode const&, llvm::SmallPtrSetImpl<llvm::BasicBlock const*>&, llvm::SmallDenseMap<llvm::BasicBlock const*, llvm::ScalarEvolution::LoopGuards, 4u, llvm::DenseMapInfo<llvm::BasicBlock const*, void>, llvm::detail::DenseMapPair<llvm::BasicBlock const*, llvm::ScalarEvolution::LoopGuards>>&, unsigned int) (/opt/compiler-explorer/clang-assertions-trunk/bin/opt+0x4952702)
 #15 0x0000000004951839 llvm::ScalarEvolution::LoopGuards::collectFromBlock(llvm::ScalarEvolution&, llvm::ScalarEvolution::LoopGuards&, llvm::BasicBlock const*, llvm::BasicBlock const*, llvm::SmallPtrSetImpl<llvm::BasicBlock const*>&, unsigned int) (/opt/compiler-explorer/clang-assertions-trunk/bin/opt+0x4951839)
 #16 0x0000000004952c7d llvm::ScalarEvolution::applyLoopGuards(llvm::SCEV const*, llvm::Loop const*) (/opt/compiler-explorer/clang-assertions-trunk/bin/opt+0x4952c7d)
 #17 0x0000000004952fb0 llvm::ScalarEvolution::getRangeForAffineNoSelfWrappingAR(llvm::SCEVAddRecExpr const*, llvm::SCEV const*, unsigned int, llvm::ScalarEvolution::RangeSignHint) (/opt/compiler-explorer/clang-assertions-trunk/bin/opt+0x4952fb0)
 #18 0x000000000492888d llvm::ScalarEvolution::getRangeRef(llvm::SCEV const*, llvm::ScalarEvolution::RangeSignHint, unsigned int) (/opt/compiler-explorer/clang-assertions-trunk/bin/opt+0x492888d)
 #19 0x0000000004942b52 llvm::ScalarEvolution::isKnownPredicateViaConstantRanges(llvm::CmpInst::Predicate, llvm::SCEV const*, llvm::SCEV const*) (/opt/compiler-explorer/clang-assertions-trunk/bin/opt+0x4942b52)
 #20 0x0000000004942e18 llvm::ScalarEvolution::isKnownViaNonRecursiveReasoning(llvm::CmpInst::Predicate, llvm::SCEV const*, llvm::SCEV const*) (/opt/compiler-explorer/clang-assertions-trunk/bin/opt+0x4942e18)
 #21 0x0000000004943799 llvm::ScalarEvolution::getMinMaxExpr(llvm::SCEVTypes, llvm::SmallVectorImpl<llvm::SCEV const*>&) (/opt/compiler-explorer/clang-assertions-trunk/bin/opt+0x4943799)
 #22 0x0000000004943f1a llvm::ScalarEvolution::getSMinExpr(llvm::SCEV const*, llvm::SCEV const*) (/opt/compiler-explorer/clang-assertions-trunk/bin/opt+0x4943f1a)
 #23 0x0000000004951128 llvm::ScalarEvolution::LoopGuards::collectFromBlock(llvm::ScalarEvolution&, llvm::ScalarEvolution::LoopGuards&, llvm::BasicBlock const*, llvm::BasicBlock const*, llvm::SmallPtrSetImpl<llvm::BasicBlock const*>&, unsigned int) (/opt/compiler-explorer/clang-assertions-trunk/bin/opt+0x4951128)
...
#255 0x00000000049524c2 llvm::ScalarEvolution::LoopGuards::collectFromPHI(llvm::ScalarEvolution&, llvm::ScalarEvolution::LoopGuards&, llvm::PHINode const&, llvm::SmallPtrSetImpl<llvm::BasicBlock const*>&, llvm::SmallDenseMap<llvm::BasicBlock const*, llvm::ScalarEvolution::LoopGuards, 4u, llvm::DenseMapInfo<llvm::BasicBlock const*, void>, llvm::detail::DenseMapPair<llvm::BasicBlock const*, llvm::ScalarEvolution::LoopGuards>>&, unsigned int)::'lambda'(unsigned int)::operator()(unsigned int) const ScalarEvolution.cpp:0:0
Program terminated with signal: SIGSEGV
Compiler returned: 139
```

Stack exhaustion via some recursion error maybe?
</pre>
<img width="1" height="1" alt="" src="http://email.email.llvm.org/o/eJzsWl1vozwW_jXujUVkDAlw0QuSNjPVTkdVM-pejgw4xFtjs7bpx_76lQ2ZAiVvvzKz70qt2pT483mec-xznJhozUpB6SmYL8H87IQ0ZifVaUEE46TiJ5ksHk_XUkGzo3ArOZf3TJTw4hoEKUApWKD2l_O7CqDUEFVSAwtiCCePsjEQBGcQYEy9CgQp9WocIRCkAXYv9q0_fGufFqF78divBx_HIEh9HHvbGHVPwhUt9t0XobdxxcwWezXeV8TdX4DbOgwwfoJqFKs53cN8iBc_F6HXiFsh74XHmWgevFI0bReA0oJumaDwTrICghBtpQQ4BjiBIFoClM50zZmZNdrHqFUIwkxBTjLKIcDzfn33vC95zdsWw0cHCVIIgiWsFS10R3w-E5I-5JFt1PsFeDVG_ZzSdM8WKVezetcvD1G0n_-7dBBoTrWWSgPsu7H1PTP5DrIAQ2TnH2nnh_iJWO8BWgdG6eF-CzTZz80JXTd_2O0QLwjB_KzjN93m7QJP6vRc_Pe5DLTDIAek3jFHFcyXttDfzzEJzvG0DebLVtJDSCcbfgx2p7GD7jvopCha6Hju5vD31TMhzYwFfUxBHDr8wRlkeVVDzc2g7y8vZv5fjvAah3juakdZ3of8fNq5Jv3HclTUuM1qMPShpRC4pTD6eedk0Vk_PLTPsjZggWCuiN5RDe93VEDVCNhoG1PAAnk10ZpqEJwJoh49RYnWMmfEUOh5OiecKI_eSd4YJoXXaOrRh5oKze6op4goqad3RNVUMFF2s6K0lEUmudv2dsbUlibAa4DXXcVMqhLg9X8AXj9c3YU_Li9l3PZckvzWKJJTCHBsVCNyYmgBi4ZCIyGnojQ7yFnFjAY4GUXEdv6rb-fp5hzqJquYgQRmTQkVraUydogRHmZ2TTbLZQXw2gXU9p9XK_kvmhuA10zrhmqA15CIAjKR86agLjY7UWG2RzwDKN0Ykt_CoqnqFhqaAZRcKVkqUkGiyqaiwrQOhdfWNnidy6pmnCqrK5eKKlvGiSg9axhlZdeeVeIW4HXGRNsRetIOQeravm9M3ZiZht4GHtOeEAQrLRuVUxCcA5T6ls11I1ydncfG720jcjsWwPF4RmshjKEUsJJFY0M-xoMhXYjHU6M-H8qNs5_MTWwTAdxtSQGC6AHtf-Z4HvlJDJ1FgxQEqX7U7cOVYsI4M_2wRgM4fmqkyP1PqY2ipAJ4YbcZJozLNGzC8SF7AbxEDx0sK0uH2h-hDrMkhxtWCsK_ElFwO3rcgWiL9SyvrXMh99cNg7thom1CsiQP8RyjDjRnmV1lbZLVS65sRT7TcrZw0FyXHrBgAMxfhCjPenLuiN79vCO8GQqYXl0IA3MptHECHk-5FkEPYDgG6JOkB_CMCk0vSX0hthIEqxFEa1q3awbnbWlJzVeidzd_lpFPkh6jeZ9RSIsILzKYScknaC2JpgNa-4pprtoUbUkj2L8b-rM2atBwZfkRYcbNC7olDTc_C8qpoQe7WBXPXVR-h_6DbgU1hPHhEFeEqf8hrQlyn7oeTVdX-U3K26ZeNvktNWs5Bcry-YtV-fenitPjbh_d_tDbPhaj7SNLkgU8gKrb8gaafvt2c7mSwtCH55r-tl2ww9nRADiIhixoRgL0FhY_HmvqxP5D8B3AnhXiIf5s4Ud4Av9a8mLJbJJzIbRRzT6DaoT7bKhoE4_VRM9n5AYVR2TmoPeYJSPLJFtMJ2CcP9Sqb5qPMlrBwyP8MvYxDWp5PfmjP8grwyTE0bafCG1cRn2-T6h_Mf9OS2LYHd2szm8GDmoL9q444u3auqfv8p-K1GtOSn1Mci36Hjl_TC7Jw1eQu2Si0W9l9jbSY7MfVYQkD3si4KEIc0Qj8pII36SsvzREFd2pIpec09yslayWXOa3Q2FGI4x315dmGLdfEs1yN80BTV9ssKkI51dGbai5qGo-CF9TnW0AW_xWozjVe0YJRkbBYY4_YJSrrxe_1SRXXy--y4IeSEneLfdoiMkk_2Vjv8RlBcPmlVnmgcnen3N-GH2XXk15Z9sW4IiTKisIwNGzeNS1kTVVxEjVfrHwvFWLDY6wjE_i1m_Dsd9G6NNvP_32TX57xF3Vul9vV52PvNOPg-Qz1P3pUGdV7xllMd4y8qh4STJS1_yxr9vr8jDbo1d1VE_Lo6JHKhqT2mboFZnlNRElXUuVbrdM0O9yQ_nWZoU1E2V6_YxmWhTXNLdHjtcmnocPE5OQHJ4NK8XX4y_NbYZ6gg0PjgmO4_hFL9gLdk23r87EX8HyN_q-o9VjnYwPINn8xXDJ9D-EvBdXihYsJ4beMLI_MToiw9Wwqmp7xO7C3b7Pm44nv2fFOK5PUuBnB03qx6-U4oaR71Jc07xRmt3Ra0q0dN_H_Z8IQf24J8T4UBpEyYtBqj2UXpIH9_HDeC38eKypnggLNzQ3Uj0LC0OqXUA4JmHLqEcYjwlv_RcPoCU1m0smJun-eQtaxD1C48Ob7-MXXfkzzTh6muHjblnNZjOAUmuZ-TgD_DxXf55P_ubn6v31CUNVxYS7DnLPzA5q9304CFK4ufiyOf9yA1C66lYMVNQ0StDCVvtBMr4Ys7-pQR92pNHuRsEdI1DLikLVxlEpIFVKKliRx4yCYH1SnAZFEiTkhJ76URAuApvnnuxOE4yiIEswyjLkR0kUbhHKsoJEc-RviyI8YacY4dDHfuLHfhxEswQTEgTzLSooQdk8BiGiFWF8Zu0zk6o8cbdOTn2MFv78xF120u6-KMadCd3lE4AxwKunwvYz2a7MtfCk8O4IZ4Utnp-dqFPb1MuaUoMQcaaNfprUMMPdtVQ3zvwMbmjpvuaCTEAXPp4c5KRR_PT9l2k6Znen-L8BAAD__8Mia6w">