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

    <tr>
        <th>Summary</th>
        <td>
            [SCEV] Assertion `isAvailableAtLoopEntry(OrigRHS, L) && "Must be!"' failed.
        </td>
    </tr>

    <tr>
      <th>Labels</th>
      <td>
      </td>
    </tr>

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

    <tr>
      <th>Reporter</th>
      <td>
          max-quazan
      </td>
    </tr>
</table>

<pre>
    https://godbolt.org/z/5Y9df9YsY

Run `opt -passes=irce -S` on the following test:
```
define void @test() {
bb:
  %tmp = icmp ult i32 0, undef
  br i1 %tmp, label %bb1, label %bb31

bb1:                                              ; preds = %bb
  br label %bb5

bb2:                                              ; preds = %bb20
  %tmp3 = phi i32 [ %tmp21, %bb20 ]
  %tmp4 = add nuw nsw i32 %tmp3, 100
  br label %bb5

bb5:                                              ; preds = %bb2, %bb1
  %tmp6 = phi i32 [ 102, %bb1 ], [ %tmp4, %bb2 ]
  %tmp7 = phi i32 [ 2, %bb1 ], [ %tmp3, %bb2 ]
  br label %bb12

bb8:                                              ; preds = %bb12
  %tmp9 = phi i32 [ %tmp14, %bb12 ]
  %tmp10 = add nsw i32 %tmp9, -1
  %tmp11 = icmp ult i32 %tmp10, undef
  br i1 %tmp11, label %bb12, label %bb32

bb12:                                             ; preds = %bb8, %bb5
  %tmp13 = phi i32 [ 1, %bb5 ], [ %tmp9, %bb8 ]
  %tmp14 = add nuw nsw i32 %tmp13, 1
  %tmp15 = load atomic i32, i32 addrspace(1)* undef unordered, align 8
  %tmp16 = icmp ult i32 %tmp14, %tmp6
  br i1 %tmp16, label %bb8, label %bb17

bb17:                                             ; preds = %bb12
  %tmp18 = phi i32 [ %tmp15, %bb12 ]
  %tmp19 = icmp ult i32 %tmp7, %tmp18
  br i1 %tmp19, label %bb20, label %bb33

bb20:                                             ; preds = %bb17
  %tmp21 = add nuw nsw i32 %tmp7, 2
  br i1 undef, label %bb22, label %bb2

bb22:                                             ; preds = %bb20
  %tmp23 = phi i32 [ %tmp18, %bb20 ]
  br label %bb24

bb24:                                             ; preds = %bb30, %bb22
  %tmp25 = phi i32 [ 3, %bb22 ], [ %tmp26, %bb30 ]
  %tmp26 = add i32 %tmp25, 1
  %tmp27 = icmp ult i32 %tmp26, %tmp23
  %tmp28 = and i1 undef, %tmp27
  br i1 %tmp28, label %bb30, label %bb29

bb29:                                             ; preds = %bb24
  ret void

bb30:                                             ; preds = %bb24
  br label %bb24

bb31:                                             ; preds = %bb
  ret void

bb32:                                             ; preds = %bb8
  unreachable

bb33:                                             ; preds = %bb17
  ret void
}

```

Failure:
```
opt: /root/llvm-project/llvm/lib/Analysis/ScalarEvolution.cpp:12706: llvm::ScalarEvolution::ExitLimit llvm::ScalarEvolution::howManyLessThans(const llvm::SCEV*, const llvm::SCEV*, const llvm::Loop*, bool, bool, bool): Assertion `isAvailableAtLoopEntry(OrigRHS, L) && "Must be!"' failed.
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=irce <source>
 #0 0x000055f8639273a4 PrintStackTraceSignalHandler(void*) Signals.cpp:0:0
 #1 0x000055f863924b64 SignalHandler(int) Signals.cpp:0:0
 #2 0x00007f384064a420 __restore_rt (/lib/x86_64-linux-gnu/libpthread.so.0+0x14420)
 #3 0x00007f384011700b raise (/lib/x86_64-linux-gnu/libc.so.6+0x4300b)
 #4 0x00007f38400f6859 abort (/lib/x86_64-linux-gnu/libc.so.6+0x22859)
 #5 0x00007f38400f6729 (/lib/x86_64-linux-gnu/libc.so.6+0x22729)
 #6 0x00007f3840107fd6 (/lib/x86_64-linux-gnu/libc.so.6+0x33fd6)
 #7 0x000055f8627b5031 llvm::ScalarEvolution::howManyLessThans(llvm::SCEV const*, llvm::SCEV const*, llvm::Loop const*, bool, bool, bool) (/opt/compiler-explorer/clang-assertions-trunk/bin/opt+0x268e031)
 #8 0x000055f8627b53f3 llvm::ScalarEvolution::computeExitLimitFromICmp(llvm::Loop const*, llvm::CmpInst::Predicate, llvm::SCEV const*, llvm::SCEV const*, bool, bool) (/opt/compiler-explorer/clang-assertions-trunk/bin/opt+0x268e3f3)
 #9 0x000055f8627b59e8 llvm::ScalarEvolution::computeExitLimitFromICmp(llvm::Loop const*, llvm::ICmpInst*, bool, bool, bool) (/opt/compiler-explorer/clang-assertions-trunk/bin/opt+0x268e9e8)
#10 0x000055f8627b5dd2 llvm::ScalarEvolution::computeExitLimitFromCondImpl(llvm::ScalarEvolution::ExitLimitCache&, llvm::Loop const*, llvm::Value*, bool, bool, bool) (/opt/compiler-explorer/clang-assertions-trunk/bin/opt+0x268edd2)
#11 0x000055f8627b62b3 llvm::ScalarEvolution::computeExitLimitFromCondCached(llvm::ScalarEvolution::ExitLimitCache&, llvm::Loop const*, llvm::Value*, bool, bool, bool) (/opt/compiler-explorer/clang-assertions-trunk/bin/opt+0x268f2b3)
#12 0x000055f8627b6662 llvm::ScalarEvolution::computeExitLimitFromCondFromBinOp(llvm::ScalarEvolution::ExitLimitCache&, llvm::Loop const*, llvm::Value*, bool, bool, bool) (/opt/compiler-explorer/clang-assertions-trunk/bin/opt+0x268f662)
#13 0x000055f8627b5b71 llvm::ScalarEvolution::computeExitLimitFromCondImpl(llvm::ScalarEvolution::ExitLimitCache&, llvm::Loop const*, llvm::Value*, bool, bool, bool) (/opt/compiler-explorer/clang-assertions-trunk/bin/opt+0x268eb71)
#14 0x000055f8627b62b3 llvm::ScalarEvolution::computeExitLimitFromCondCached(llvm::ScalarEvolution::ExitLimitCache&, llvm::Loop const*, llvm::Value*, bool, bool, bool) (/opt/compiler-explorer/clang-assertions-trunk/bin/opt+0x268f2b3)
#15 0x000055f8627b63ed llvm::ScalarEvolution::computeExitLimitFromCond(llvm::Loop const*, llvm::Value*, bool, bool, bool) (/opt/compiler-explorer/clang-assertions-trunk/bin/opt+0x268f3ed)
#16 0x000055f862783888 llvm::ScalarEvolution::computeExitLimit(llvm::Loop const*, llvm::BasicBlock*, bool) (/opt/compiler-explorer/clang-assertions-trunk/bin/opt+0x265c888)
#17 0x000055f862783f01 llvm::ScalarEvolution::computeBackedgeTakenCount(llvm::Loop const*, bool) (/opt/compiler-explorer/clang-assertions-trunk/bin/opt+0x265cf01)
#18 0x000055f862784aa8 llvm::ScalarEvolution::getBackedgeTakenInfo(llvm::Loop const*) (/opt/compiler-explorer/clang-assertions-trunk/bin/opt+0x265daa8)
#19 0x000055f862785329 llvm::ScalarEvolution::getBackedgeTakenCount(llvm::Loop const*, llvm::ScalarEvolution::ExitCountKind) (.constprop.0) ScalarEvolution.cpp:0:0
#20 0x000055f86278792f llvm::ScalarEvolution::getRangeRef(llvm::SCEV const*, llvm::ScalarEvolution::RangeSignHint) (/opt/compiler-explorer/clang-assertions-trunk/bin/opt+0x266092f)
#21 0x000055f8627887c7 StrengthenNoWrapFlags(llvm::ScalarEvolution*, llvm::SCEVTypes, llvm::ArrayRef<llvm::SCEV const*>, llvm::SCEV::NoWrapFlags) ScalarEvolution.cpp:0:0
#22 0x000055f862795757 llvm::ScalarEvolution::getAddExpr(llvm::SmallVectorImpl<llvm::SCEV const*>&, llvm::SCEV::NoWrapFlags, unsigned int) (/opt/compiler-explorer/clang-assertions-trunk/bin/opt+0x266e757)
#23 0x000055f86278ee60 llvm::ScalarEvolution::createSCEV(llvm::Value*) (.part.0) ScalarEvolution.cpp:0:0
#24 0x000055f86278f8a9 llvm::ScalarEvolution::createSCEVIter(llvm::Value*) (/opt/compiler-explorer/clang-assertions-trunk/bin/opt+0x26688a9)
#25 0x000055f8635baa39 (anonymous namespace)::InductiveRangeCheck::extractRangeChecksFromCond(llvm::Loop*, llvm::ScalarEvolution&, llvm::Use&, llvm::SmallVectorImpl<(anonymous namespace)::InductiveRangeCheck>&, llvm::SmallPtrSetImpl<llvm::Value*>&) InductiveRangeCheckElimination.cpp:0:0
#26 0x000055f8635bacbf (anonymous namespace)::InductiveRangeCheck::extractRangeChecksFromCond(llvm::Loop*, llvm::ScalarEvolution&, llvm::Use&, llvm::SmallVectorImpl<(anonymous namespace)::InductiveRangeCheck>&, llvm::SmallPtrSetImpl<llvm::Value*>&) InductiveRangeCheckElimination.cpp:0:0
#27 0x000055f8635be609 (anonymous namespace)::InductiveRangeCheckElimination::run(llvm::Loop*, llvm::function_ref<void (llvm::Loop*, bool)>) InductiveRangeCheckElimination.cpp:0:0
#28 0x000055f8635c2637 llvm::IRCEPass::run(llvm::Function&, llvm::AnalysisManager<llvm::Function>&) (/opt/compiler-explorer/clang-assertions-trunk/bin/opt+0x349b637)
#29 0x000055f863c91ce6 llvm::detail::PassModel<llvm::Function, llvm::IRCEPass, llvm::PreservedAnalyses, llvm::AnalysisManager<llvm::Function>>::run(llvm::Function&, llvm::AnalysisManager<llvm::Function>&) (/opt/compiler-explorer/clang-assertions-trunk/bin/opt+0x3b6ace6)
#30 0x000055f86303a93a llvm::PassManager<llvm::Function, llvm::AnalysisManager<llvm::Function>>::run(llvm::Function&, llvm::AnalysisManager<llvm::Function>&) (/opt/compiler-explorer/clang-assertions-trunk/bin/opt+0x2f1393a)
#31 0x000055f86118e096 llvm::detail::PassModel<llvm::Function, llvm::PassManager<llvm::Function, llvm::AnalysisManager<llvm::Function>>, llvm::PreservedAnalyses, llvm::AnalysisManager<llvm::Function>>::run(llvm::Function&, llvm::AnalysisManager<llvm::Function>&) (/opt/compiler-explorer/clang-assertions-trunk/bin/opt+0x1067096)
#32 0x000055f8630394a6 llvm::ModuleToFunctionPassAdaptor::run(llvm::Module&, llvm::AnalysisManager<llvm::Module>&) (/opt/compiler-explorer/clang-assertions-trunk/bin/opt+0x2f124a6)
#33 0x000055f86118ea96 llvm::detail::PassModel<llvm::Module, llvm::ModuleToFunctionPassAdaptor, llvm::PreservedAnalyses, llvm::AnalysisManager<llvm::Module>>::run(llvm::Module&, llvm::AnalysisManager<llvm::Module>&) (/opt/compiler-explorer/clang-assertions-trunk/bin/opt+0x1067a96)
#34 0x000055f86303754e llvm::PassManager<llvm::Module, llvm::AnalysisManager<llvm::Module>>::run(llvm::Module&, llvm::AnalysisManager<llvm::Module>&) (/opt/compiler-explorer/clang-assertions-trunk/bin/opt+0x2f1054e)
#35 0x000055f860d69ce8 llvm::runPassPipeline(llvm::StringRef, llvm::Module&, llvm::TargetMachine*, llvm::TargetLibraryInfoImpl*, llvm::ToolOutputFile*, llvm::ToolOutputFile*, llvm::ToolOutputFile*, llvm::StringRef, llvm::ArrayRef<llvm::StringRef>, llvm::ArrayRef<llvm::PassPlugin>, llvm::opt_tool::OutputKind, llvm::opt_tool::VerifierKind, bool, bool, bool, bool, bool, bool) (/opt/compiler-explorer/clang-assertions-trunk/bin/opt+0xc42ce8)
#36 0x000055f860c8ecca main (/opt/compiler-explorer/clang-assertions-trunk/bin/opt+0xb67cca)
#37 0x00007f38400f8083 __libc_start_main (/lib/x86_64-linux-gnu/libc.so.6+0x24083)
#38 0x000055f860d5c69e _start (/opt/compiler-explorer/clang-assertions-trunk/bin/opt+0xc3569e)
Compiler returned: 139
```
</pre>
<img width="1px" height="1px" alt="" src="http://email.email.llvm.org/o/eJztW1tT4zgW_jXhRQVlS77IDzyEdKimlt6hgO2tfqJkW0m87UheWaZhfv0c2blJcULChK7dnqEgiS3p6HzfuehIManMXy9nWlf1gAwH-Bp-pzJPZakvpJrC1e_wF35L8knyrf428D4NvGH3et8INIg8WWl0XrG65iDhU6Eyjs4f4D6SAukZRxNZlvJHIaZI81qbSToZkbf4bS9zPikER8-yyNEg8NqumA5wggbxVdclTVeDERrgUM8rBDOiIoMPTalRQTDyBniEGgHilj1ThQp_0d80lizlpblOU9-5Jv4mPtNOQMAxPwNyhSrF87rVrBW6ocfGVKE9Ez7FTNiz2SFtUzUrWmYG4dXiPm5xL4bA_U_2sKAdxvIcieYHEvWPbngn0oz0Pe8gUOFJQK109W01oy10vrfRucVlrlawgzXqbdDxlrS9ski_LJsOH9t80FPwsRS6VDzZYWR_Ddfvwet7aytbFk7MsHOHa9_fjrSlnL0B57sh5mM35hyS_KNDoYckusIeOkC2Y2IdDOG2nZNVI-3hcF-k-F2oOCPCdkQpWY6YlvMiMyNMRzMQBKm6YhmHzAdawdzDjll4lSrngNF0ZWUxFYg6kqOdFlo6gomZXhtFjkmoa7PYMVF8AhO5fuzTXY4c7nfkZBfweI3bp73AEwco9lznJE6a9k6BPLYRYH-PG7UgsK19F22O6m5cOWGFTxFW7gKDd60wPt2xwtgJEgeOksEJlCTeem7Hx3C4pe9GIsfb4Y-jVTPpWSlxtLLc2mI47Al8HO_y0tUULZ_OqC4mmMgtsy9F9vk0doOXuD4NecUmPTmFZwRLZRTXbRVnT0JOETjrSfa7ETm6bttTtu3Ac5pVajFHIxRn2YylJXemISfNNw6W-NPmbE5B3r1es6JsFN9VtUPtbxSEHYKSEgr267J8np9XSv6HZ8tL81ak8DoUrHytixo-PmSsZGr8LMtGF1JcZFUFcnwce5GR1w6DKcnQ6djdHL8U-raYF_qtjjP54wsTr7e8rh9nTMDMNJOitsaNxl9hnTUxckTTrZTVoimVstx-b2NqCHsiZbQx26SiHj4DmcbGQ23Gj4VWr6DRb6qY3n9-MGNv2_2OyQiQWDD-0sCkKVQDUAxAeo_RBATw_KLj_u52PHwYo7pJDRMMpc0UDFxJpZGWyNnRFXrWpBeZnG8YxTZVUdcNN7bp0o3Iyibn7QYuU6yeoZRl37WC4mQx_YOGGyhv5tXKOTxoSu6UnCo2R0xNmzkXul44iHEVfA0aVIBBnfOXqpSKK3OvZGJ6zpZk1edaNeI7NKSF6Aaic2lEMPASuG501eiLGnaZ7r5zQEa1bODTgIwXPj_AkLi9Fw9-wnBCI5LgmLAA3alC6BbDowH1ACUVKz8D9NLoRNsoMQZOUNdUL3zUa_9Wsn1HdpBGAXKFwUxvCsILQfGE0MCLAhbAwvn0pGAfDDQ9gVHb7fAilF5o9BQF52UhmpfzqWi6hkrPII_kF7W8gKR_5b34QWBKmmQ9DbGm8f3Y81KkWFHzA-RnRnLUSg4IDLQkB5ZkbxLRMEEslQdpviEZYxhoSQ5dyXEbJUfJjLEtM7J5gPc8Ok4mITDEkhlv-gKO09AD9zg-Q9kJqEs9i1xzUJPJLVbTjgy1gPtn4rIjN6IckFpUUJcKMiFvUWFUaDRfJXdYUuY3I3NmQ_eAWzdB1xvRHTCR4R0sgUXGND-Ytq2mD6QL2LDoSly6Ek4_mq6bJV8_zUkA1Aq1SZ2eizrP8XtQj6TIb-ZVacfO3sJhBNUWH3Sl90FsfWVlw38eVcCERZXvUBXh9F3xZKhqsee_DlkT4MIiC7tkRdG7_cq8XxXit-oX4gvosPgibhym8Zvr1l8kDoEJi6rg7zg8PA5DlyzC8_eSdeiq9pMhE2PADciRDZkSSo9eyA-FesXqIrsqZfbdwntCfGEG6lv4YhffxDs0VVzBVovnU_7IvnMxko14A-gHoAFlLTROlUoDxt601pRrC8mNmMh9QE4JIAf9LABO3UhDAvMdCeAAUxyQoFop_yhMoLaIL9rxlZKV2YrC3rf3wGdjD2y2wE5BSOMETw6Acw_88XtzNHrg3qlPTivE7NA_L3brJzNb5AGMTbNhp5qjNM5i9KAVF1M94-Kf8t-KVdclm9Z7V4e-Hczja2UOcTZvD5Vir4YeMtpFDxlvS-o-WbocaEan_krCOIwPMOMwz8cvlbIhz1lZfuWZlqqtLPZDiA5CYb6trMHQ3JxyndjUHKBapnZqK8p55L2ZMBWHjWt3-kj7lrYuwiqm9BHB5ZQudELZm7lircmN5mqfNifij4JSFn9WDUHClDHSzseEFK9z2dRIsDlffGmadKrdiLzJdPHM25gezTiskG0DfzEHmHp9u95ZXryZNFxn-1e9XZpte-97NO9xbCP3TqsHrreiYmWXxbgE9Qgdl1BoCLbbWSKX9iyd_E37h9MeO7RDsniPt2_M0_WBcHub6kkjMjPkSbVrRfck1o5Rqy85xu-FSm2oGY7I5iJxcz8a30HG6Nf_eqHqlomWXzF9YYJNIfdsmmg1aGWiE-UtEiSwt7HzvlWZkSzxMx5t6JlzzYqy-2xgfpE5L_u1tQ_tlrRYd-8UBxWfed7B3yoADiTF_P4fsJ1G4P7RJtvONzweYQlhm_wYhvfp-AvThSc-ATYsuqz60_cp95JTOOeH0fzXdXbfi2IwjmU97Dh7ErBN64G1mpI_yqVOxirDnFWwGvYj7gYchXcx5AN8FQMYCy1xfZUd6atLeKMDOTqVs6052uVq_zvEGzdjjpsFjpvFYcAPCPY-un8VmsA_PWDBosnaoHh5lGTWV3cgxzB1V1S8LAS3N7daFWJ6v3iU7y28j0zBJvkLy2atnGFf622RKqZezZlUdxDv9oKy7bf28YnrouwR8qead8DpP35Y9XXTe2_3lsKymRZiqz_Y5kmbarS96tTrzqF29_rKVTEpuFr26z8o_vAD5CzAmf2VKLH2XV5GeZYxNGeFONWcaRSDSGvO2Hm8gnqUoKcn87TDU62Z0k8bChz6wEUAQqxZqB0nYRYlHHXyT8YnCUHoatbRQpJ56q1RgudgeQTFkPMg2xm_9KPIJ4EXUnqWX5I8IQk704Uu-eUgvGrPYcJPH_Yw11mjSvf_b454WiuMIQedzS5jnvAE09TPaBbloTm6j3DqT3I-oQnn3ln7vGRtEAGas-ISexh7FAe-j5OAXjCaRMTnUZjSGCc0GQQeB7uXF2Zi859AZ-qy1SFtpjU0lkWt63UjGMccqfGlfNbomVSXc_Zy_t-G_c7EWavxZavuH9fAY34">