SimplifyCFG: llvm::BranchProbability::getBranchProbability: Assertion `Numerator <= Denominator && "Probability cannot be bigger than 1!"' failed.

[DaniilSuchkov]

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: f054947
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
}

My LLVM build is on c425db2

[vpykhtin]

Hi @DaniilSuchkov thank you for reporting this, my bad, there is a uint32 overflow. As a quick fix can you try this?

SimplifyCFG.cpp:4356:

BranchProbability CommonDestProb = BranchProbability::getBranchProbability(
PredWeights[PBIOp], (uint64_t)PredWeights[0] + (uint64_t)PredWeights[1]);

[DaniilSuchkov]

Hi @DaniilSuchkov thank you for reporting this, my bad, there is a uint32 overflow. As a quick fix can you try this?

SimplifyCFG.cpp:4356:

BranchProbability CommonDestProb = BranchProbability::getBranchProbability( PredWeights[PBIOp], (uint64_t)PredWeights[0] + (uint64_t)PredWeights[1]);

Yep, that worked.

[vpykhtin]

I'm going to fix this, thanks!