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

    <tr>
        <th>Summary</th>
        <td>
            SimplifyCFG: llvm::BranchProbability::getBranchProbability: Assertion `Numerator <= Denominator && "Probability cannot be bigger than 1!"' failed.
        </td>
    </tr>

    <tr>
      <th>Labels</th>
      <td>
            new issue
      </td>
    </tr>

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

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

<pre>
    Running `opt -passes=simplifycfg` fails on this IR:
```
define void @ham(i1 %arg, i1 %arg1) {
bb:
 br i1 %arg, label %bb4, label %bb2, !prof !0

bb2: ; preds = %bb
  br i1 %arg1, label %bb4, label %bb3

bb3:                                              ; preds = %bb2
  br label %bb4

bb4: ; preds = %bb3, %bb2, %bb
  ret void
}

!0 = !{!"branch_weights", i32 -258677585, i32 -1212131848}
```
With the following message:
```
opt: llvm-project/llvm/lib/Support/BranchProbability.cpp:55: static llvm::BranchProbability llvm::BranchProbability::getBranchProbability(uint64_t, uint64_t): Assertion `Numerator <= Denominator && "Probability cannot be bigger than 1!"' failed.
PLEASE submit a bug report to https://github.com/llvm/llvm-project/issues/ and include the crash backtrace.
Stack dump:
0.      Program arguments: llvm-project/buildRA/bin/opt -passes=simplifycfg reduce/reduced-stripped.ll -S
 #0 0x0000000001e55855 llvm::sys::PrintStackTrace(llvm::raw_ostream&, int) llvm-project/llvm/lib/Support/Unix/Signals.inc:727:0
 #1 0x0000000001e534a4 llvm::sys::RunSignalHandlers() llvm-project/llvm/lib/Support/Signals.cpp:105:0
 #2 0x0000000001e53f83 SignalHandler(int) llvm-project/llvm/lib/Support/Unix/Signals.inc:403:0
 #3 0x00007f94bbc72630 __restore_rt sigaction.c:0:0
 #4 0x00007f94ba7ce387 raise (/lib64/libc.so.6+0x36387)
 #5 0x00007f94ba7cfa78 abort (/lib64/libc.so.6+0x37a78)
 #6 0x00007f94ba7c71a6 __assert_fail_base (/lib64/libc.so.6+0x2f1a6)
 #7 0x00007f94ba7c7252 (/lib64/libc.so.6+0x2f252)
 #8 0x0000000001daef65 (llvm-project/buildRA/bin/opt+0x1daef65)
 #9 0x0000000001fc54ee SimplifyCondBranchToCondBranch llvm-project/llvm/lib/Transforms/Utils/SimplifyCFG.cpp:4359:0
#10 0x0000000001fc54ee (anonymous namespace)::SimplifyCFGOpt::simplifyCondBranch(llvm::BranchInst*, llvm::IRBuilder<llvm::ConstantFolder, llvm::IRBuilderDefaultInserter>&) llvm-project/llvm/lib/Transforms/Utils/SimplifyCFG.cpp:7229:0
#11 0x0000000001fcd565 simplifyBranch llvm-project/llvm/lib/Transforms/Utils/SimplifyCFG.cpp:7066:0
#12 0x0000000001fcd565 simplifyOnce llvm-project/llvm/lib/Transforms/Utils/SimplifyCFG.cpp:7452:0
#13 0x0000000001fcd565 run llvm-project/llvm/lib/Transforms/Utils/SimplifyCFG.cpp:7483:0
#14 0x0000000001fcd565 llvm::simplifyCFG(llvm::BasicBlock*, llvm::TargetTransformInfo const&, llvm::DomTreeUpdater*, llvm::SimplifyCFGOptions const&, llvm::ArrayRef<llvm::WeakVH>) llvm-project/llvm/lib/Transforms/Utils/SimplifyCFG.cpp:7494:0
#15 0x0000000001d5a74f iterativelySimplifyCFG(llvm::Function&, llvm::TargetTransformInfo const&, llvm::DomTreeUpdater*, llvm::SimplifyCFGOptions const&) llvm-project/llvm/lib/Transforms/Scalar/SimplifyCFGPass.cpp:255:0
#16 0x0000000001d5b717 simplifyFunctionCFGImpl(llvm::Function&, llvm::TargetTransformInfo const&, llvm::DominatorTree*, llvm::SimplifyCFGOptions const&) llvm-project/llvm/lib/Transforms/Scalar/SimplifyCFGPass.cpp:276:0
#17 0x0000000001d5cf35 simplifyFunctionCFG(llvm::Function&, llvm::TargetTransformInfo const&, llvm::DominatorTree*, llvm::SimplifyCFGOptions const&) llvm-project/llvm/lib/Transforms/Scalar/SimplifyCFGPass.cpp:303:0
#18 0x0000000001d5d099 llvm::SimplifyCFGPass::run(llvm::Function&, llvm::AnalysisManager<llvm::Function>&) llvm-project/llvm/lib/Transforms/Scalar/SimplifyCFGPass.cpp:363:0
#19 0x0000000002022f4d llvm::detail::PassModel<llvm::Function, llvm::SimplifyCFGPass, llvm::PreservedAnalyses, llvm::AnalysisManager<llvm::Function>>::run(llvm::Function&, llvm::AnalysisManager<llvm::Function>&) llvm-project/llvm/include/llvm/IR/PassManagerInternal.h:90:0
#20 0x000000000197b060 llvm::PassManager<llvm::Function, llvm::AnalysisManager<llvm::Function>>::run(llvm::Function&, llvm::AnalysisManager<llvm::Function>&) llvm-project/llvm/include/llvm/IR/PassManager.h:547:0
#21 0x000000000201ceed 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>&) llvm-project/llvm/include/llvm/IR/PassManagerInternal.h:90:0
#22 0x000000000197a99a llvm::ModuleToFunctionPassAdaptor::run(llvm::Module&, llvm::AnalysisManager<llvm::Module>&) llvm-project/llvm/lib/IR/PassManager.cpp:128:0
#23 0x0000000002022d8d llvm::detail::PassModel<llvm::Module, llvm::ModuleToFunctionPassAdaptor, llvm::PreservedAnalyses, llvm::AnalysisManager<llvm::Module>>::run(llvm::Module&, llvm::AnalysisManager<llvm::Module>&) llvm-project/llvm/include/llvm/IR/PassManagerInternal.h:90:0
#24 0x0000000001979350 llvm::PassManager<llvm::Module, llvm::AnalysisManager<llvm::Module>>::run(llvm::Module&, llvm::AnalysisManager<llvm::Module>&) llvm-project/llvm/include/llvm/IR/PassManager.h:547:0
#25 0x0000000000852cc5 llvm::SmallPtrSetImplBase::~SmallPtrSetImplBase() llvm-project/llvm/include/llvm/ADT/SmallPtrSet.h:83:0
#26 0x0000000000852cc5 llvm::SmallPtrSetImpl<llvm::AnalysisKey*>::~SmallPtrSetImpl() llvm-project/llvm/include/llvm/ADT/SmallPtrSet.h:345:0
#27 0x0000000000852cc5 llvm::SmallPtrSet<llvm::AnalysisKey*, 2u>::~SmallPtrSet() llvm-project/llvm/include/llvm/ADT/SmallPtrSet.h:451:0
#28 0x0000000000852cc5 llvm::PreservedAnalyses::~PreservedAnalyses() llvm-project/llvm/include/llvm/IR/PassManager.h:172:0
#29 0x0000000000852cc5 llvm::runPassPipeline(llvm::StringRef, llvm::Module&, llvm::TargetMachine*, llvm::TargetLibraryInfoImpl*, llvm::ToolOutputFile*, llvm::ToolOutputFile*, llvm::ToolOutputFile*, llvm::StringRef, llvm::ArrayRef<llvm::PassPlugin>, llvm::opt_tool::OutputKind, llvm::opt_tool::VerifierKind, bool, bool, bool, bool, bool, bool, bool) llvm-project/llvm/tools/opt/NewPMDriver.cpp:527:0
#30 0x00000000007b51e7 std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char>>::_M_is_local() const basic_string.h:211:0
#31 0x00000000007b51e7 std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char>>::_M_dispose() basic_string.h:220:0
#32 0x00000000007b51e7 std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char>>::~basic_string() basic_string.h:647:0
#33 0x00000000007b51e7 main llvm-project/llvm/tools/opt/opt.cpp:710:0
#34 0x00007f94ba7ba555 __libc_start_main (/lib64/libc.so.6+0x22555)
#35 0x0000000000848a9e _start (llvm-project/buildRA/bin/opt+0x848a9e)
```
https://godbolt.org/z/de659P7Mn

Reverting this commit helps: https://github.com/llvm/llvm-project/commit/f054947c0da99ec8b3c4bb043e5225672420a313
After the revert, I get the following IR from this test:
```
define void @ham(i1 %arg, i1 %arg1) {
bb:
  %brmerge = select i1 %arg, i1 true, i1 %arg1
  ret void
}
```

The probability in the initial IR indeed exceeds 1: -258677585/-1212131848 => 4,036,289,711/3,082,835,448 ~ 1.3
Though, I'm not sure if it's OK for SimplifyCFG to crash due to that. The verifier doesn't mind that, and I haven't found anything in LangRef that would indicate that such IR is invalid.
Moreover, it was SimplifyCFG who introduced those weights in the first place.
Running it (`opt -passes=simplifycfg`) on this IR:
```
define void @blam(i1 %arg) {
bb:
  br label %bb1

bb1: ; preds = %bb9, %bb7, %bb5, %bb3, %bb2, %bb1, %bb
  br i1 %arg, label %bb1, label %bb2, !prof !0

bb2: ; preds = %bb1
  %icmp = icmp sgt i32 0, 0
  br i1 %icmp, label %bb1, label %bb3, !prof !1

bb3: ; preds = %bb2
  %icmp4 = icmp sgt i32 0, 0
  br i1 %icmp4, label %bb1, label %bb5, !prof !2

bb5: ; preds = %bb3
  %icmp6 = icmp sgt i32 0, 0
  br i1 %icmp6, label %bb1, label %bb7, !prof !3

bb7: ; preds = %bb5
  %icmp8 = icmp ult i32 0, 0
  br i1 %icmp8, label %bb1, label %bb9, !prof !4

bb9: ; preds = %bb7
  %mul = mul i32 0, 0
  br label %bb1
}

!0 = !{!"branch_weights", i32 188098938, i32 254254470}
!1 = !{!"branch_weights", i32 127, i32 388}
!2 = !{!"branch_weights", i32 127, i32 261}
!3 = !{!"branch_weights", i32 127, i32 134}
!4 = !{!"branch_weights", i32 127, i32 127}
```
Results in the following IR:
```
define void @blam(i1 %arg) {
  br label %bb1

bb1: ; preds = %bb9, %bb1, %bb
  %icmp = icmp sgt i32 0, 0
  %or.cond = or i1 %arg, %icmp
  %icmp4 = icmp sgt i32 0, 0
  %or.cond1 = or i1 %or.cond, %icmp4
  %icmp6 = icmp sgt i32 0, 0
  %or.cond2 = or i1 %or.cond1, %icmp6
  %icmp8 = icmp ult i32 0, 0
  %or.cond3 = or i1 %or.cond2, %icmp8
  br i1 %or.cond3, label %bb1, label %bb9, !prof !0

bb9:                                              ; preds = %bb1
  %mul = mul i32 0, 0
  br label %bb1
}

!0 = !{!"branch_weights", i32 -1770328737, i32 204041957}
```
Before SimplifyCFG all probabilities were less than 1, while after it the only probability that's left is 2,524,638,559/204,041,957.

My LLVM build is on https://github.com/llvm/llvm-project/commit/c425db2eb558c26377edc04e062c0c1f999b2770
</pre>
<img width="1px" height="1px" alt="" src="http://email.email.llvm.org/o/eJzsWl9z2yj3_jTkhqlHAqE_F7lwkno3s802k2R3Lz1IQja_YvAASprfxX72d0D-IxTZidt0O_vO28nUkhDPeXg4HEAcagxfSMbOAbkACD2un78sLZcAIUCuzmhrl0qfX1HJubhvq-UX9XhWqvr5_K6VkssFBGmk1hZ-WFNjmAH4yvDVWvDmuWoWII1gQ7kwUElol9zA6zuApyC6AtEUpNHmz9_WrOGSwUfFawiSaElXAOU8hgARqhcAXcLdTQxQAUF20VUsyx0kLDUMqghaMuHuyzIZ3CN3D1C81qpxvxsaW0wE8BQCfAHXmtUGAnzVVdsYCizFr5jCITR20Cf9G-GBekQC04Gp5EArcNf4vQy9lmlmfS9skLKrPqQTagMTux5AMUCo1FRWy_kT44ulNc5zXG9hBD8gkqdZRnKyexKjGMU4zpN8jxw6wl_cLqFdMtgoIdST87EVM4Yu2CHXUWvr2inE4-rDWqv_Y5UFaOZu3Q8vAZrdt-u10u7xhSd7q1VJSy64fZ5U6zXAU0IchrHU8spDOWt4-uL1Y2Xd4wWzL0tQ3nJp02RunRT768JZnRrDtOVKutH0e7timlqlIcCXTuorJtWKy-4RSgFKIUCoT6miUioLSwZLvlgwDe2SShh3vQNQ5gchqyedXLefPk7vP0LTlituIYVlu4CaOXmgVXBp7dq4hqAZQLMFt8u2nFRq1VM01Jkb0zID0AxSWUMuK9HWzHdgpalZwpJWX6ymFduYv7e0-gLrdrXe9Wc06fz8VquFpitI9aJdMWnNSLeWLRf1naNXuig1Oxh8oGZ1WzGAZt1F_cFYzddrVk-EgB_uN_4OEI5g9DXa_osZITkhvW42z6a7uNVcWk__wbUHoHz_kqZPc2WsZi5upd7dpeveN3rlH5J_dQ_4QlJhJlxWAE8zlAE8jfZE4wFRnNBkjOhdKzukX6msBdMGoPztXLYkunERRyQkgYYkmhzDwJwL3N_d-CTCoV28sZs1RVKWVYZSHMH5XDNjlWZzbaHhC1q5YTSpfNWgetKvTrOK4TyDmnLDoFfHsUqT7reaGDVJAbqIvuIU55kbpjsgMgBqaJZDWrrhcxQoo1keAKUDoCymKZzPqQ8Gczdk5yV9hR5qYpoGqNkQFRH0CgQiKIDIgx6uKWtSAjfefnwkesBNjQCyCCCbiiSMwfvNYL1Usu4i5oPaXx91ngdNpWmUXrnA84flwngH2uDNftk4b4JJsXcDN4KiMSIA5VQq-bxSrYGSrphZ-_FddMOph_vZTzVurL3gHoSD7tG1NBagqV8O7Iqu7y6ccEwDfLl_eqmksVTamfJF4zWuWENbYa-l8xAH8NHHmuPj7I1SZQgNpIoHUtUkJXDb7vfroyxK09AwOmb4s6zYu5hNCArN4jGzupXvYy3HobVkzFovlu8hQseihlcXQlVfXjjWA9ULZneErmWjYKW8C6bhm1dq9aAZ-2NdU-dGQ6DQ37mS5gDOVGv6fMeawJP_YvTLn79633wfx0yKJJSOhPGJ0CxpILdu1cQfmXi-P6DdrJV-enjRjn9GuRPUuK-ooDqU45aa7ZyMCAkVSQeKlFmc7UbMttmXs1-uV2vxAyTpFqdOmJ-mSDaIIdlAkarBZEyR_0o1cDQINoMZndRRUYzTciibFW0r3ybOVFLxbLi5oZIuBtPartLpU9VrbUwHbQyWGChCqEnqHsuaWcrFZiFPjblRNRPjXA91mdcmKLzVzDD9yOpOA2a-TRn3949Lvtmp7R9c3wE089J0qNfSMi2pmCwBnhZRoDYK11FFVkZp1BdmD_MGjf_dOnl9SJKFAsWhO8YVY-_hjj9M2P_5te82NPBrWhS0R_BG1a1gD2pLxsFOa7q2So83tatwUkM3Vd4UMV_44mbTjvKwWXgYHOv8NG_ctuPyjWK8lzvtxTjkTD9M4e9zpGTgSAUmbwmQYzr_W_UZD4zB6j3KCaqq_sbnfkWFuLX6nlm3Wr2ghnUFf4-VHPuu9YLf9OrBLSf2MJ7gYGOG0pP4BbptNf2NPbul37ZHhszfgzVOwi0Ayt5M-xhldAlRO0r8PUgnJA5J58dJv4wbHa2ReHIKuVE_jbPwcwAqjnPTrY93t3zNBJfhx-B7q7lcuI3xSLw8sLm4odXS44zu6j_xUlP97DYenQcN31JKfG7turUzLkZAvqv4QHNGd_9eE9EuuHyxqFBrO7dKbaaZzt5vXNbH3vqTad5wprfvla7k5N9DnuHsmO2Xy9nv7On25krzx900SlAYu8KTgigrScwyaGzdkZ3Pq69f47i7Kanh1dx46QC-rJbUT4q7l92DudWUW7Mt7gTbvUGFUBX1K4td-XZkzm_m3Mxd-Taa-H0k7Fv1bo3icMiFZwg_uQk1N2u1i-IvuaNwTg2PHn4m978D-AP008HMh_EY_RXlh74whu6p1nb7RSwe6DI42ygpIQTO54KXjhDVdu6tHD0FQITsP9k70ME8neS0YLCDO-EwoKu3Bw5PbgeHjaoulbATpRcAzf4foFnNUlLcZjeyfwZ9xx6ZtlwuupSCSq1W3MIlEx7q9APMDgCgWRORpEiyKqppUbAqL3GVlGWUYEYQImmGEhRRHG-O86eN9SetDGpPyDnPNVwwOzi8vr6DjVarjqxlxh8g_LAMCH-Wr1dML5g_pzdMsMrCIYzVLRsgvnL8H3Lt_n9YMrjunUNz6dvOJbecCtdyLmu372Vf3fbXQDc4g6yAWS8hwPEF-CNMALqMsJskUV4AdJnFMUAz7J7mCKDLHBOALpMkh3_DeIK3VFS7WPo-AChbQaksNK1mkDfQdW5m4OffYKM07H3QgVZtDqnrlrkbu6R2Al2zHjcTD6wVMxKgzMIVl7V_w1mhsobXcEkfWVfYqFbWkMpnu3SdziX8RP2c6WvAJ9WK2qnBK2pZ98y01dJrZCCXj1Tw7QH9jdJMPXanQNzCJ2oC0k9LBbm0WvlTbWiXyjC4Sb7YdkHDtbFwLfbH7tt8Hd4dUx7P2nHudXLKTimGHnvIR8OclTjMWYkP5KwUu0yVbHdFdldjGS3xi9yWI_lBwySeb8wPinvjkFertS_xF2ZhfQpM5ICjF4zcO69QwgNK8Uhe0bFUoY2V5CROw2SmISkyIIVCUuRgBlJIKj2JVPoKqWxAapCBlR0gRQak8j2pVrxKKn-FVDEgNcjVKg6QynqkVq3wBe53lM3IsPqeBK44z6MiL3C-fYBIgkiSZNEeFsXxCYAo217iPO-DoG8CQWncB8HfBBLjpA-SfBsIyg5NlnfMtKIXm3tLg_cIrd8dT1_GyTcGL4CI0pNKydq_qQbRdRvVTgw_e9Q4hN087UEnp0aRPQoaxY574Omp0WAPg0fBUQ88fxFCtlVPjCLRSBT53uTS-CeGnA9xlkUY5RneD_IoiZK4IAcH2AVrlGbBIokK0VuacmbgE9MMCmbMLjvyEj4tuWCQ-pU87xbuSornYFHbrfgyAwVrrFusOaoEuXkx9YGRkAKgGYr8ujVxuAXJJn0Fbp7hp09_3kC_SXIQSn7HNqVKEKlLxEpC8gqlOMtYXUUJi1JURVXcFEVRoiyLzupzXBe4oGfsPM7cJg6nGTpbnqOozusmrxKSUBoRjKMEozIvYlJGtMrTM36OIoTjOE4QjhOMJhjXFcvLKCJ5w4qYgCRiK8rFxHF0-7UznwV6niGM8Jn3CLNJKJfsCfrCTUa5PvftKtuFAUkkuLFmj2K5Fey8n7-xSQAFvayqtyXc_oNptWetFuffnjfrRftPAAAA__9UnAEv">