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

    <tr>
        <th>Summary</th>
        <td>
            Assertion `Ptr != End && "dereferencing end() iterator"' failed in ScalarEvolution::getBackedgeTakenInfo
        </td>
    </tr>

    <tr>
      <th>Labels</th>
      <td>
            bug,
            SCEV,
            crash
      </td>
    </tr>

    <tr>
      <th>Assignees</th>
      <td>
            d-makogon
      </td>
    </tr>

    <tr>
      <th>Reporter</th>
      <td>
          d-makogon
      </td>
    </tr>
</table>

<pre>
    Reproducer: https://godbolt.org/z/oqh84KvTs
`opt -passes='loop(loop-deletion),loop-mssa(loop-predication,licm<allowspeculation>,simple-loop-unswitch<nontrivial>),loop(loop-predication)'` crashes with the following backtrace:
```c++
opt: /localhome/dmakogon/llvm/llvm-project/llvm/include/llvm/ADT/DenseMap.h:1256: pointer llvm::DenseMapIterator<const llvm::Loop *, llvm::ScalarEvolution::BackedgeTakenInfo>::operator->() const [KeyT = const llvm::Loop *, ValueT = llvm::ScalarEvolution:
:BackedgeTakenInfo, KeyInfoT = llvm::DenseMapInfo<const llvm::Loop *>, Bucket = llvm::detail::DenseMapPair<const llvm::Loop *, llvm::ScalarEvolution::BackedgeTakenInfo>, IsConst = false]: Assertion `Ptr != End && "dereferencing end() iterator"' failed.
PLEASE submit a bug report to https://github.com/llvm/llvm-project/issues/ and include the crash backtrace.
Stack dump:
0.      Program arguments: /localhome/dmakogon/llvm/llvm-project/build/RA/bin/opt -passes=loop(loop-deletion),loop-mssa(loop-predication,licm<allowspeculation>,simple-loop-unswitch<nontrivial>),loop(loop-predication) renamed.ll
 #0 0x00007f0f245f92c8 llvm::sys::PrintStackTrace(llvm::raw_ostream&, int) /localhome/dmakogon/llvm/llvm-project/llvm/lib/Support/Unix/Signals.inc:602:13
 #1 0x00007f0f245f7340 llvm::sys::RunSignalHandlers() /localhome/dmakogon/llvm/llvm-project/llvm/lib/Support/Signals.cpp:105:18
 #2 0x00007f0f245f993d SignalHandler(int) /localhome/dmakogon/llvm/llvm-project/llvm/lib/Support/Unix/Signals.inc:413:1
 #3 0x00007f0f238e4630 __restore_rt sigaction.c:0:0
 #4 0x00007f0f22c8c387 raise (/lib64/libc.so.6+0x36387)
 #5 0x00007f0f22c8da78 abort (/lib64/libc.so.6+0x37a78)
 #6 0x00007f0f22c851a6 __assert_fail_base (/lib64/libc.so.6+0x2f1a6)
 #7 0x00007f0f22c85252 (/lib64/libc.so.6+0x2f252)
 #8 0x00007f0f25dcaa22 bool llvm::DenseMapBase<llvm::DenseMap<llvm::PHINode*, llvm::Constant*, llvm::DenseMapInfo<llvm::PHINode*, void>, llvm::detail::DenseMapPair<llvm::PHINode*, llvm::Constant*>>, llvm::PHINode*, llvm::Constant*, llvm::DenseMapInfo<llvm::PHINode*, void>, llvm::detail::DenseMapPair<llvm::PHINode*, llvm::Constant*>>::LookupBucketFor<llvm::PHINode*>(llvm::PHINode* const&, llvm::detail::DenseMapPair<llvm::PHINode*, llvm::Constant*> const*&) const /localhome/dmakogon/llvm/llvm-project/llvm/include/llvm/ADT/DenseMap.h:635:5
 #9 0x00007f0f25dcaa22 bool llvm::DenseMapBase<llvm::DenseMap<llvm::PHINode*, llvm::Constant*, llvm::DenseMapInfo<llvm::PHINode*, void>, llvm::detail::DenseMapPair<llvm::PHINode*, llvm::Constant*>>, llvm::PHINode*, llvm::Constant*, llvm::DenseMapInfo<llvm::PHINode*, void>, llvm::detail::DenseMapPair<llvm::PHINode*, llvm::Constant*>>::LookupBucketFor<llvm::PHINode*>(llvm::PHINode* const&, llvm::detail::DenseMapPair<llvm::PHINode*, llvm::Constant*>*&) /localhome/dmakogon/llvm/llvm-project/llvm/include/llvm/ADT/DenseMap.h:675:9
#10 0x00007f0f25dcaa22 llvm::DenseMapBase<llvm::DenseMap<llvm::PHINode*, llvm::Constant*, llvm::DenseMapInfo<llvm::PHINode*, void>, llvm::detail::DenseMapPair<llvm::PHINode*, llvm::Constant*>>, llvm::PHINode*, llvm::Constant*, llvm::DenseMapInfo<llvm::PHINode*, void>, llvm::detail::DenseMapPair<llvm::PHINode*, llvm::Constant*>>::erase(llvm::PHINode* const&) /localhome/dmakogon/llvm/llvm-project/llvm/include/llvm/ADT/DenseMap.h:317:10
#11 0x00007f0f25dcaa22 llvm::ScalarEvolution::getBackedgeTakenInfo(llvm::Loop const*) /localhome/dmakogon/llvm/llvm-project/llvm/lib/Analysis/ScalarEvolution.cpp:8419:38
#12 0x00007f0f25dc9318 llvm::SmallVectorBase<unsigned int>::size() const /localhome/dmakogon/llvm/llvm-project/llvm/include/llvm/ADT/SmallVector.h:91:32
#13 0x00007f0f25dc9318 llvm::SmallVectorTemplateCommon<llvm::ScalarEvolution::ExitNotTakenInfo, void>::end() const /localhome/dmakogon/llvm/llvm-project/llvm/include/llvm/ADT/SmallVector.h:273:49
#14 0x00007f0f25dc9318 llvm::ScalarEvolution::BackedgeTakenInfo::getExact(llvm::BasicBlock const*, llvm::ScalarEvolution*) const /localhome/dmakogon/llvm/llvm-project/llvm/lib/Analysis/ScalarEvolution.cpp:8622:24
#15 0x00007f0f25dc9318 llvm::ScalarEvolution::getExitCount(llvm::Loop const*, llvm::BasicBlock const*, llvm::ScalarEvolution::ExitCountKind) /localhome/dmakogon/llvm/llvm-project/llvm/lib/Analysis/ScalarEvolution.cpp:8309:36
#16 0x00007f0f256bf49c llvm::isa_impl_cl<llvm::SCEVCouldNotCompute, llvm::SCEV const*>::doit(llvm::SCEV const*) /localhome/dmakogon/llvm/llvm-project/llvm/include/llvm/Support/Casting.h:109:5
#17 0x00007f0f256bf49c llvm::isa_impl_wrap<llvm::SCEVCouldNotCompute, llvm::SCEV const*, llvm::SCEV const*>::doit(llvm::SCEV const* const&) /localhome/dmakogon/llvm/llvm-project/llvm/include/llvm/Support/Casting.h:137:12
#18 0x00007f0f256bf49c llvm::isa_impl_wrap<llvm::SCEVCouldNotCompute, llvm::SCEV const* const, llvm::SCEV const*>::doit(llvm::SCEV const* const&) /localhome/dmakogon/llvm/llvm-project/llvm/include/llvm/Support/Casting.h:127:12
#19 0x00007f0f256bf49c llvm::CastIsPossible<llvm::SCEVCouldNotCompute, llvm::SCEV const*, void>::isPossible(llvm::SCEV const* const&) /localhome/dmakogon/llvm/llvm-project/llvm/include/llvm/Support/Casting.h:255:12
#20 0x00007f0f256bf49c llvm::CastInfo<llvm::SCEVCouldNotCompute, llvm::SCEV const* const, void>::isPossible(llvm::SCEV const* const&) /localhome/dmakogon/llvm/llvm-project/llvm/include/llvm/Support/Casting.h:509:12
#21 0x00007f0f256bf49c bool llvm::isa<llvm::SCEVCouldNotCompute, llvm::SCEV const*>(llvm::SCEV const* const&) /localhome/dmakogon/llvm/llvm-project/llvm/include/llvm/Support/Casting.h:549:10
#22 0x00007f0f256bf49c getMinAnalyzeableBackedgeTakenCount(llvm::ScalarEvolution&, llvm::DominatorTree&, llvm::Loop*) /localhome/dmakogon/llvm/llvm-project/llvm/lib/Transforms/Scalar/LoopPredication.cpp:1096:9
#23 0x00007f0f256bf49c (anonymous namespace)::LoopPredication::predicateLoopExits(llvm::Loop*, llvm::SCEVExpander&) /localhome/dmakogon/llvm/llvm-project/llvm/lib/Transforms/Scalar/LoopPredication.cpp:1189:23
#24 0x00007f0f256bf49c (anonymous namespace)::LoopPredication::runOnLoop(llvm::Loop*) /localhome/dmakogon/llvm/llvm-project/llvm/lib/Transforms/Scalar/LoopPredication.cpp:1326:14
#25 0x00007f0f256bd57d llvm::LoopPredicationPass::run(llvm::Loop&, llvm::AnalysisManager<llvm::Loop, llvm::LoopStandardAnalysisResults&>&, llvm::LoopStandardAnalysisResults&, llvm::LPMUpdater&) /localhome/dmakogon/llvm/llvm-project/llvm/lib/Transforms/Scalar/LoopPredication.cpp:380:7
```

The crash happens here in ScalarEvolution::getBackedgeTakenInfo in the following piece of code:
`return BackedgeTakenCounts.find(L)->second = std::move(Result);`
So we expect here that entry for `L` exists in `BackedgeTakenCounts`. Indeed, in the begginning of the function we insert an entry if it wasn't already there. Here's how we've come to delete it from the cache.
In the example above we call `getBackedgeTakenInfo` on loop `bb9`.
After the initial insertion we call `computeBackedgeTakenCount` to get the `BackedgeTakenInfo` that is returned later. And it's all fine. The problem happens after the call to `computeBackedgeTakenCount`. We have some code that updates some statistics:
```c++
computeBackedgeTakenCount(L);
...
#if LLVM_ENABLE_STATS || !defined(NDEBUG)
  const SCEV *BEExact = Result.getExact(L, this);
  // update stats
  ...
```
And in the call to `getExact` we may call `getBackedgeTakenInfo` on another loop - `bb3`, which happens to be the parent loop for `bb9`. We compute its backedge taken info and then invalidate any SCEVs that use AddRecs of `bb3`. This is perfomed in `getBackedgeTakenInfo` and it's done to get more precise results as now we have a computed backedge count for the loop. While doing this invalidation, we erase the computed backedge count from `BackedgeTakenCounts` map for the child loop `bb9` because it happens to use the AddRec of `bb3`. Then we return from `getBackedgeTakenInfo` for the parent loop, update the stats and in `return` expect the entry for `bb9` to be in cache. Here's the stacktrace of the cache entry deletion:
```c++
#0 llvm::ScalarEvolution::forgetBackedgeTakenCounts (this=0x7b9258, L=0x7fffead56000, Predicated=false)
#1  0x00007ffff1926b1d in llvm::ScalarEvolution::forgetMemoizedResultsImpl (this=0x7b9258, S=0x7fffeacf2960)
#2  0x00007ffff1926350 in llvm::ScalarEvolution::forgetMemoizedResults (this=0x7b9258, SCEVs=...)
#3 0x00007ffff190e42c in llvm::ScalarEvolution::getBackedgeTakenInfo (this=0x7b9258, L=0x7fffead560a8) // bb3
#4  0x00007ffff190de24 in llvm::ScalarEvolution::getBackedgeTakenCount (this=0x7b9258, L=0x7fffead560a8, Kind=llvm::ScalarEvolution::ConstantMaximum)
#5 0x00007ffff0dce9f8 in llvm::ScalarEvolution::getConstantMaxBackedgeTakenCount (this=0x7b9258, L=0x7fffead560a8)
#6  0x00007ffff1906451 in llvm::ScalarEvolution::getRangeRef (this=0x7b9258, S=0x7fffeacf2730, SignHint=llvm::ScalarEvolution::HINT_RANGE_UNSIGNED, Depth=1)
#7 0x00007ffff1905bf7 in llvm::ScalarEvolution::getRangeRef (this=0x7b9258, S=0x7fffeacf2790, SignHint=llvm::ScalarEvolution::HINT_RANGE_UNSIGNED, Depth=0)
#8  0x00007fffefd4b7ae in llvm::ScalarEvolution::getUnsignedRange (this=0x7b9258, S=0x7fffeacf2790)
#9  0x00007ffff191a8d4 in llvm::ScalarEvolution::isKnownPredicateViaConstantRanges (this=0x7b9258, Pred=llvm::CmpInst::ICMP_ULE, LHS=0x7fffeacf2790, RHS=0x7fffeacf23d0)
#10 0x00007ffff191fa87 in llvm::ScalarEvolution::isKnownViaNonRecursiveReasoning (this=0x7b9258, Pred=llvm::CmpInst::ICMP_ULE, LHS=0x7fffeacf2790, RHS=0x7fffeacf23d0)
#11 0x00007ffff18fb0d1 in llvm::ScalarEvolution::getMinMaxExpr (this=0x7b9258, Kind=<incomplete type>, Ops=...)
#12 0x00007ffff18fc4e7 in llvm::ScalarEvolution::getSequentialMinMaxExpr (this=0x7b9258, Kind=<incomplete type>, Ops=...)
#13 0x00007ffff18fcaf6 in llvm::ScalarEvolution::getUMinExpr (this=0x7b9258, Ops=..., Sequential=true)
#14 0x00007ffff18fea07 in llvm::ScalarEvolution::getUMinFromMismatchedTypes (this=0x7b9258, Ops=..., Sequential=true)
#15 0x00007ffff190f2a4 in llvm::ScalarEvolution::BackedgeTakenInfo::getExact (this=0x7fffffff7430, L=0x7fffead56000, 
#16 0x00007ffff190e223 in llvm::ScalarEvolution::getBackedgeTakenInfo (this=0x7b9258, L=0x7fffead56000) // bb9
```
Notice how we initially call `getBackedgeTakenInfo` on `bb9`, during it call `getBackedgeTakenInfo` on `bb3` and end up calling `forgetBackedgeTakenCounts` on `bb9`.
</pre>
<img width="1px" height="1px" alt="" src="http://email.email.llvm.org/o/eJzsW11T2zrz_zTiRkPGkeOXXHARknDKFHgYoH0uGdlaJ_pjS34kmZd--v9ItmPHBEih9PTMnE5biC3t7m_129XqJVRrvhIARyg4RoSww4LeyZUUiBAULA5oZdZSHW0eHySSPR1dQakkq1JQyJ_htTGlRv4MkRNETlaSJTI3I6lWiJz8QORE_m8dT77e32jkLZA3Q6EnS4MPS6o1aOQvEIlyKUtEYvvjkEEOhlsLpojM3aNCa9q-LhUwntK6xTznaYH8Oc1z-aBLSKu8fuMvEZlrXpQ5HLpuldAP3KRr5M-FFEbxe05z16zVslPBFJEIhR5OFdVr0PiBmzU2a8CZtCq5WOGEpndG0RSsC1qE9d8UkWP71z2VpbHeQuQklynN17IARE7Yxt8neX5fND8OSyX_D1LTPeUizSsG3YPZ4gaRkwUIDee0HK2RPxuTILQqSsmFAYVdS3-G_Fnb7NSAokYq5M9TKbTpNTmTssSIzBCZ955epzSnankv86r2q314TNM7YCu4oXcgTkUmrR_dG1nW8g-dZ2NEprjWg4Ljr_B0g5G_wK9p_k7zCupmrxpR-3mXKWSOv8KT_XUoZuMEZ_HLDnDcwcdVegdmIIKBoTzfFndJ-Wf4k8zxqZ7XzvMXOKO5BhQs7PjOtAZlu2MUepdGYUTGts1SMIxIiEiIbSiDggwUiNSyFARrBoS3HCAEkQhnlOfARrVHL8-Ws-sl1lVScIMpTqoVVlBKZbCRw0DnZl0lo1QWL3KXa12BRuQEU8FwQ2EXPi6eutBp1F8bmt5hVhXlZoy9EXZ_LpVcKVpgqlZVAcLo98RSUvGcIXJyZSEk3DbcTkV_bh7CCgQtgI3yvHYMRsT3sPfoeZ4XZV5GJkE2JWncI5t-0vUvl4oL45x74xIVibtGij7cSm0U0MJxZ465MFbhOxNVzhNETq6r0rIGkZNvgj_aB3wlaK5HXKTIn4UesfnK76CMB1Aif-LtgnJViVrUFypYDko3rP5F1rZmpqWl4NgL7P9xZyYZenzqM7xlECLxb3DgZOxbyzrD_L5hfgyT0Pfw7a0CbaSCW2Ww5iuaWjaNrADP_dt0n_S7kzRO_TjCinIN2DnYWhVO6p_pSMtRiMix9-iHfhxZ6m4EBQNBjEYxponNIK8KimgUbwkKB4KCMQ3x7S11ue_WZq3bhL5hHsnGNNySGg2lkoC8IYIEZEtE3BcRsJRSQnAiZb5jqjmmGpA_f_5i6-Hll9MLaef2wWThsj-1ZBq8GMxkL0m6l5w1U8leU9jPWWTn_IHsfzKQdtK-q8p66j-RL4pyxc2uN3Vt0-TRTzG11TBzSjbl1ecVlaFvc2DQ8X_6L___5f_fxv-O-Z_J-chyvsn5tjjxdnH-X7r_g4G4x6DsgL1J5U_lmj-OXKXZkW38Otl2LiFXYHYshePBcrSbOz5Ync4EzZ80t0u7gTlN5RxPxlMLLu5gkQGsqT_uL1auC5rn3yE1UjVhVAm3NcXcgqQdMs1_wPbOwi8dmp4VbnSmY4uCdCj8vVHcQFHm1MBcFoUdpvkbQ7h85OZCmq2djDYSarZulvC_AzmJ7Apj0kuCkzeg77m10dB1-UitVT2KHlPN0-Ncpnc9or62eVIT-UPO2JfOIbELVjLpvBG8wxsONjdzWQnzWnT2Qf-0VzZkcmq-csuaTw9333PhHnb-2Vq_BWGSTaZpz2qu6S0vyvw2zbdDY778PpdVzi6kmcuirAwM4M6X3ztPtLHBJN_26HazX5jCu4X5nGrDxareenX4gw5-tCf8BzWoDn7SAR_2zafMcy84yXdTXS-bxr_HS-0v_yRfkaGvpq_7ynY-1ZdSa57k8EFKbc07vJP6J3iGBMG2Z4i3h2eGFed7CfQneyZwSajvmfEuzwzW6lzTD2bgPwL7ZLpdRhOyC_sKzDkXbj77ATTJYatAeT4xPys5BivbhSy4oLbaUwDP3p657fyPl9s3igqdSVV0MzAiJ1b6ZXdIsNmznoZbi1fi73IEIjEVUjwVstJY0AJ06U4Gpp3lPdn1w_ZEAuxbW2HoZ0XMzilp-VhSwUB9jAjvcMU4tnCI3_li8qt8oSrxH3HWHNf8vQPuEzvg4642JcEAJQsiNqBlT84l1XoDagecAanbYvCcCrqC7fV33WEYAteGCkYVa3tega5yS57QZY8dQfNKj-22l-ffSkbN7-eWH3vIn0WDA__mo_v_ZnPMuaZlCULjNSjAXOC9V_C28fZlg5JDClhmOJVs68KBAlMpgZ-nMz3K3BIgPkNkeoj8pYZUCuYOlbVhtfJC3tsprHazI_7xBs21xA-A4bGE1NQQzJoaDMKoJ5xJhVHonaHQw_DItdHWZhR6OwxBoTfCp4IBsPqY0WFLYLXiQlhwMqvRVsKdU1m1XGhQBlPR6OMZ5gY_UC0QiQymuQLKnmw3BSP8BRQgEmm8lg_4wf56DziVBWAjsTvPBds9U7KoT6Fpum7Pnk9rc-CRFmUOmCbyHqwFKc1zC2jnDkvoYSlw7o76Qy9JphZjLW-WGVBOJBfccJo3WBpgrdi0nmF3TEOhZ61egXFChi5t1bux4BrX4w8M5zYaRngmGLalbKSx1ZRxASNsKVkqmeRQbEhJN3Y6k4x8y6oR_i_gNb0HrK1nLRFrKyoXibp-rA01XBueavT6tZiXVdWUtVR0DUej0SbD8QyfnX0_v11ezI7PlrfXN7Oba4yiOYrmGJExA4vXkv5isTz-9ld3ftfsFrgqBZHZ8dJtQ7hgqMk_6m1NnFmamrVd93ZmYFxff2jgOqC6fdXZuJ0R3GiIoZc3qkLPUqKgT_uwjQpp6V6z7rDmnW81kTl-WPO0yzdG4qS-blFSBcLUXZqQbchqB7MZAsyNdlcyrFZsrFrMbRaiglkp9tM9zbmDTcWT86Juxl4DnjF2Bam2YbwxynKOa0vQElQmC7eb9xpA2vGWSQFtCBRSWepCyjVgVc8GmGosXKDXdKQtENahSC2THGTrBot_hP-75jlgJm3KMc66FlZ9l8OlO0V1c1PlJZk2ibyY6HBBy43adM1zNsgSOIGUWq9x0x-vqtFa-_KZK8HljibXtxa85MpWfW_wLbqGt_aN425zNwdvJpE6l7t07zJiP9E3xtfM4qLJoF3ibaQ213rajO5aNYI212peTwvudssbm1yZVEPs9QDYis7Frb_wHqNkSoLYIj-rP2dZBpQFoee5mGnndmDIX9TXrEhv1xNvaqksy8ZTEiZj5669bDuHQvIfwJr65bQo8xdsu-7ZlmZkauO5V8M_s8IPvPda8ZIFNpqRv7A5rKfa39bswYSke2jeWc7sNyy0vdBjs6zlfmvKZOAFjwGZvMMWR5KfMGaO3S6qv3hDT3vKdE4feVEVfS8Gfcs9lsI0i_ezvCf0QyA6W8KhG8NJMN7PmCsqVnAF2X4kjnwXYNd8Jb64M5y3HPjl9OLm9mp28dfy9tvF9elfF8uFFbCA0qyRvxj3UUQDEEGSRZ8CYvprQWzFddwfCsjYJIko7IfiW3M65tD8BJRO-XTAgzGN2T7hxPVXIR_EJm9-57QlqTPmpQRjO2y5b16Up0Kb-sPp_Pzy9tuZO_U9-7J7EK6Gz322hah3Tl8jymi8DykaRN85vZDiCtJKaX4PV0C1dAuTvw3PeAtPnCUe2zNSz7k4p4_Lx1K9YH2T0pA_58LWOG5xZJ5KaE7e_1PumAx6h7i1QekE9oy6a_hfBcIuhD7JNH9oGs3CPUPpnItXzOmpm-MOBvIXRlXbxcJkYANQb0_3WBtOlCzOuS6oSdfAbp7KF0PpJ0wKBnkyI3SfIH_j4Hbbrqz-E03qhL-7ztp1NNiUFIT4n1tSWAt6JcV05yLtQhqeQrN30K7a873WZJvK2CpnlbJJg5u9e_rtygcEw1Xp-rm8E3ov1rhDzaMDduSzqT-lB3A0DmMSeFEU-Afro6nvT2IW03gakphRmtEJSUOaZHQah_6YHfAj4hHfm5BwPB4HgT9KU5qxKPLidBwSLwrQxIOC8nxkR2gk1erA3ew_Cokfewc5TSDXzReIkmrlvlgwR4TYinLzwW2FNd8qUkduGy6pVhpNvJxrozvRhpscjj7hOw4_tfV2UKn86P1feHCe-f8AAAD__wVImuc">