[LoopFuse] No dominance relationship between these fusion candidates!

[nrinskaya]

This bug was found by Azul FuzzGen IR test generator.

https://godbolt.org/z/aqMMhr7Mo

Run opt with -passes=loop-simplify,newgvn,loop-fusion

; ModuleID = 'bugpoint-reduced-simplified.bc'
source_filename = "gen_1771"
target triple = "x86_64-unknown-linux-gnu"

define void @function_0() {
entry_1:
  br i1 false, label %bb_2, label %bb_3

bb_2:                                             ; preds = %bb_7, %bb_5, %bb_2, %entry_1
  br i1 false, label %bb_2, label %bb_5

bb_3:                                             ; preds = %bb_3, %entry_1
  br i1 false, label %bb_3, label %bb_4

bb_4:                                             ; preds = %bb_3
  br label %bb_6

bb_5:                                             ; preds = %bb_2
  br i1 undef, label %bb_2, label %bb_7

bb_6:                                             ; preds = %bb_7, %bb_6, %bb_4
  br i1 undef, label %bb_7, label %bb_6

bb_7:                                             ; preds = %bb_6, %bb_5
  br i1 undef, label %bb_2, label %bb_6
}

Stacktrace:

No dominance relationship between these fusion candidates!
UNREACHABLE executed at /root/llvm-project/llvm/lib/Transforms/Scalar/LoopFuse.cpp:420!
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=loop-simplify,newgvn,loop-fusion <source>
 #0 0x00005640e2778c2f PrintStackTraceSignalHandler(void*) Signals.cpp:0:0
 #1 0x00005640e277665c SignalHandler(int) Signals.cpp:0:0
 #2 0x00007f5bc82563c0 __restore_rt (/lib/x86_64-linux-gnu/libpthread.so.0+0x143c0)
 #3 0x00007f5bc7d2303b raise (/lib/x86_64-linux-gnu/libc.so.6+0x4303b)
 #4 0x00007f5bc7d02859 abort (/lib/x86_64-linux-gnu/libc.so.6+0x22859)
 #5 0x00005640e26bb63a (/opt/compiler-explorer/clang-assertions-trunk/bin/opt+0x34bb63a)
 #6 0x00005640e2648214 std::pair<std::_Rb_tree_iterator<(anonymous namespace)::FusionCandidate>, bool> std::_Rb_tree<(anonymous namespace)::FusionCandidate, (anonymous namespace)::FusionCandidate, std::_Identity<(anonymous namespace)::FusionCandidate>, (anonymous namespace)::FusionCandidateCompare, std::allocator<(anonymous namespace)::FusionCandidate>>::_M_insert_unique<(anonymous namespace)::FusionCandidate const&>((anonymous namespace)::FusionCandidate const&) LoopFuse.cpp:0:0
 #7 0x00005640e264868a (anonymous namespace)::LoopFuser::collectFusionCandidates(llvm::SmallVector<llvm::Loop*, 4u> const&) LoopFuse.cpp:0:0
 #8 0x00005640e2650bab (anonymous namespace)::LoopFuser::fuseLoops(llvm::Function&) LoopFuse.cpp:0:0
 #9 0x00005640e2651d31 llvm::LoopFusePass::run(llvm::Function&, llvm::AnalysisManager<llvm::Function>&) (/opt/compiler-explorer/clang-assertions-trunk/bin/opt+0x3451d31)
#10 0x00005640e2aa3b01 llvm::detail::PassModel<llvm::Function, llvm::LoopFusePass, llvm::PreservedAnalyses, llvm::AnalysisManager<llvm::Function>>::run(llvm::Function&, llvm::AnalysisManager<llvm::Function>&) (/opt/compiler-explorer/clang-assertions-trunk/bin/opt+0x38a3b01)
#11 0x00005640e1ef45ca llvm::PassManager<llvm::Function, llvm::AnalysisManager<llvm::Function>>::run(llvm::Function&, llvm::AnalysisManager<llvm::Function>&) (/opt/compiler-explorer/clang-assertions-trunk/bin/opt+0x2cf45ca)
#12 0x00005640e0275971 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+0x1075971)
#13 0x00005640e1ef3fda llvm::ModuleToFunctionPassAdaptor::run(llvm::Module&, llvm::AnalysisManager<llvm::Module>&) (/opt/compiler-explorer/clang-assertions-trunk/bin/opt+0x2cf3fda)
#14 0x00005640e02762d1 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+0x10762d1)
#15 0x00005640e1ef2904 llvm::PassManager<llvm::Module, llvm::AnalysisManager<llvm::Module>>::run(llvm::Module&, llvm::AnalysisManager<llvm::Module>&) (/opt/compiler-explorer/clang-assertions-trunk/bin/opt+0x2cf2904)
#16 0x00005640dfeb1d0a 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) (/opt/compiler-explorer/clang-assertions-trunk/bin/opt+0xcb1d0a)
#17 0x00005640dfdef0b3 main (/opt/compiler-explorer/clang-assertions-trunk/bin/opt+0xbef0b3)
#18 0x00007f5bc7d040b3 __libc_start_main (/lib/x86_64-linux-gnu/libc.so.6+0x240b3)
#19 0x00005640dfea542a _start (/opt/compiler-explorer/clang-assertions-trunk/bin/opt+0xca542a)
Compiler returned: 139

[mikaelholmen]

Another opt reproducer crashing on llvm commit 6663f34:
opt -passes="loop-fusion" bbi-75968.ll -o /dev/null
bbi-75968.ll.gz

[xgupta]

Both reproducer stopped crashing on trunk - https://godbolt.org/z/5Yz9Knnnf and https://godbolt.org/z/r4WE3b6Ko.