Assertion `CurLoop->contains(PredBB) && "Expect all predecessors are in the loop"' failed

[mikaelholmen]

llvm commit: ef5be2b

Reproduce with:
opt -passes='function(loop-mssa(licm,loop-rotate,loop-deletion,lnicm))' -o /dev/null bbi-63573.ll
Result:
opt: ../lib/Transforms/Scalar/LICM.cpp:1604: void splitPredecessorsOfLoopExit(llvm::PHINode *, llvm::DominatorTree *, llvm::LoopInfo *, const llvm::Loop *, llvm::LoopSafetyInfo *, llvm::MemorySSAUpdater *): AssertionCurLoop->contains(PredBB) && "Expect all predecessors are in the loop"' failed.
PLEASE submit a bug report to https://bugs.llvm.org/ and include the crash backtrace.
Stack dump:
0. Program arguments: build-all/bin/opt -passes=function(loop-mssa(licm,loop-rotate,loop-deletion,lnicm)) -o /dev/null bbi-63573.ll
#0 0x0000000002c50733 llvm::sys::PrintStackTrace(llvm::raw_ostream&, int) (build-all/bin/opt+0x2c50733)
#1 0x0000000002c4e3ae llvm::sys::RunSignalHandlers() (build-all/bin/opt+0x2c4e3ae)
#2 0x0000000002c50ab6 SignalHandler(int) Signals.cpp:0:0
#3 0x00007fc9517c5630 __restore_rt sigaction.c:0:0
#4 0x00007fc94eef8387 raise (/lib64/libc.so.6+0x36387)
#5 0x00007fc94eef9a78 abort (/lib64/libc.so.6+0x37a78)
#6 0x00007fc94eef11a6 __assert_fail_base (/lib64/libc.so.6+0x2f1a6)
#7 0x00007fc94eef1252 (/lib64/libc.so.6+0x2f252)
#8 0x000000000299cadc llvm::sinkRegion(llvm::DomTreeNodeBasellvm::BasicBlock, llvm::AAResults, llvm::LoopInfo*, llvm::DominatorTree*, llvm::BlockFrequencyInfo*, llvm::TargetLibraryInfo*, llvm::TargetTransformInfo*, llvm::Loop*, llvm::MemorySSAUpdater*, llvm::ICFLoopSafetyInfo*, llvm::SinkAndHoistLICMFlags&, llvm::OptimizationRemarkEmitter*, llvm::Loop*) (build-all/bin/opt+0x299cadc)
#9 0x000000000299e6c2 llvm::sinkRegionForLoopNest(llvm::DomTreeNodeBasellvm::BasicBlock, llvm::AAResults, llvm::LoopInfo*, llvm::DominatorTree*, llvm::BlockFrequencyInfo*, llvm::TargetLibraryInfo*, llvm::TargetTransformInfo*, llvm::Loop*, llvm::MemorySSAUpdater*, llvm::ICFLoopSafetyInfo*, llvm::SinkAndHoistLICMFlags&, llvm::OptimizationRemarkEmitter*) (build-all/bin/opt+0x299e6c2)
#10 0x00000000029991b5 (anonymous namespace)::LoopInvariantCodeMotion::runOnLoop(llvm::Loop*, llvm::AAResults*, llvm::LoopInfo*, llvm::DominatorTree*, llvm::BlockFrequencyInfo*, llvm::TargetLibraryInfo*, llvm::TargetTransformInfo*, llvm::ScalarEvolution*, llvm::MemorySSA*, llvm::OptimizationRemarkEmitter*, bool) LICM.cpp:0:0
#11 0x000000000299960b llvm::LNICMPass::run(llvm::LoopNest&, llvm::AnalysisManager<llvm::Loop, llvm::LoopStandardAnalysisResults&>&, llvm::LoopStandardAnalysisResults&, llvm::LPMUpdater&) (build-all/bin/opt+0x299960b)
#12 0x0000000002f76bed llvm::detail::PassModel<llvm::LoopNest, llvm::LNICMPass, llvm::PreservedAnalyses, llvm::AnalysisManager<llvm::Loop, llvm::LoopStandardAnalysisResults&>, llvm::LoopStandardAnalysisResults&, llvm::LPMUpdater&>::run(llvm::LoopNest&, llvm::AnalysisManager<llvm::Loop, llvm::LoopStandardAnalysisResults&>&, llvm::LoopStandardAnalysisResults&, llvm::LPMUpdater&) crtstuff.c:0:0
#13 0x00000000034af44c llvm::Optionalllvm::PreservedAnalyses llvm::PassManager<llvm::Loop, llvm::AnalysisManager<llvm::Loop, llvm::LoopStandardAnalysisResults&>, llvm::LoopStandardAnalysisResults&, llvm::LPMUpdater&>::runSinglePass<llvm::LoopNest, std::unique_ptr<llvm::detail::PassConcept<llvm::LoopNest, llvm::AnalysisManager<llvm::Loop, llvm::LoopStandardAnalysisResults&>, llvm::LoopStandardAnalysisResults&, llvm::LPMUpdater&>, std::default_delete<llvm::detail::PassConcept<llvm::LoopNest, llvm::AnalysisManager<llvm::Loop, llvm::LoopStandardAnalysisResults&>, llvm::LoopStandardAnalysisResults&, llvm::LPMUpdater&> > > >(llvm::LoopNest&, std::unique_ptr<llvm::detail::PassConcept<llvm::LoopNest, llvm::AnalysisManager<llvm::Loop, llvm::LoopStandardAnalysisResults&>, llvm::LoopStandardAnalysisResults&, llvm::LPMUpdater&>, std::default_delete<llvm::detail::PassConcept<llvm::LoopNest, llvm::AnalysisManager<llvm::Loop, llvm::LoopStandardAnalysisResults&>, llvm::LoopStandardAnalysisResults&, llvm::LPMUpdater&> > >&, llvm::AnalysisManager<llvm::Loop, llvm::LoopStandardAnalysisResults&>&, llvm::LoopStandardAnalysisResults&, llvm::LPMUpdater&, llvm::PassInstrumentation&) (build-all/bin/opt+0x34af44c)
#14 0x00000000034ae7d3 llvm::PassManager<llvm::Loop, llvm::AnalysisManager<llvm::Loop, llvm::LoopStandardAnalysisResults&>, llvm::LoopStandardAnalysisResults&, llvm::LPMUpdater&>::runWithLoopNestPasses(llvm::Loop&, llvm::AnalysisManager<llvm::Loop, llvm::LoopStandardAnalysisResults&>&, llvm::LoopStandardAnalysisResults&, llvm::LPMUpdater&) (build-all/bin/opt+0x34ae7d3)
#15 0x00000000034ae3b1 llvm::PassManager<llvm::Loop, llvm::AnalysisManager<llvm::Loop, llvm::LoopStandardAnalysisResults&>, llvm::LoopStandardAnalysisResults&, llvm::LPMUpdater&>::run(llvm::Loop&, llvm::AnalysisManager<llvm::Loop, llvm::LoopStandardAnalysisResults&>&, llvm::LoopStandardAnalysisResults&, llvm::LPMUpdater&) (build-all/bin/opt+0x34ae3b1)
#16 0x0000000002f490cd llvm::detail::PassModel<llvm::Loop, llvm::PassManager<llvm::Loop, llvm::AnalysisManager<llvm::Loop, llvm::LoopStandardAnalysisResults&>, llvm::LoopStandardAnalysisResults&, llvm::LPMUpdater&>, llvm::PreservedAnalyses, llvm::AnalysisManager<llvm::Loop, llvm::LoopStandardAnalysisResults&>, llvm::LoopStandardAnalysisResults&, llvm::LPMUpdater&>::run(llvm::Loop&, llvm::AnalysisManager<llvm::Loop, llvm::LoopStandardAnalysisResults&>&, llvm::LoopStandardAnalysisResults&, llvm::LPMUpdater&) crtstuff.c:0:0
#17 0x00000000034b036b llvm::FunctionToLoopPassAdaptor::run(llvm::Function&, llvm::AnalysisManagerllvm::Function&) (build-all/bin/opt+0x34b036b)
#18 0x0000000002f64cdd llvm::detail::PassModel<llvm::Function, llvm::FunctionToLoopPassAdaptor, llvm::PreservedAnalyses, llvm::AnalysisManagerllvm::Function >::run(llvm::Function&, llvm::AnalysisManagerllvm::Function&) crtstuff.c:0:0
#19 0x00000000023d0b25 llvm::PassManager<llvm::Function, llvm::AnalysisManagerllvm::Function >::run(llvm::Function&, llvm::AnalysisManagerllvm::Function&) (build-all/bin/opt+0x23d0b25)
#20 0x0000000000b001ed llvm::detail::PassModel<llvm::Function, llvm::PassManager<llvm::Function, llvm::AnalysisManagerllvm::Function >, llvm::PreservedAnalyses, llvm::AnalysisManagerllvm::Function >::run(llvm::Function&, llvm::AnalysisManagerllvm::Function&) crtstuff.c:0:0
#21 0x00000000023d4f4a llvm::ModuleToFunctionPassAdaptor::run(llvm::Module&, llvm::AnalysisManagerllvm::Module&) (build-all/bin/opt+0x23d4f4a)
#22 0x000000000079d8dd llvm::detail::PassModel<llvm::Module, llvm::ModuleToFunctionPassAdaptor, llvm::PreservedAnalyses, llvm::AnalysisManagerllvm::Module >::run(llvm::Module&, llvm::AnalysisManagerllvm::Module&) crtstuff.c:0:0
#23 0x00000000023cfc68 llvm::PassManager<llvm::Module, llvm::AnalysisManagerllvm::Module >::run(llvm::Module&, llvm::AnalysisManagerllvm::Module&) (build-all/bin/opt+0x23cfc68)
#24 0x0000000000795652 llvm::runPassPipeline(llvm::StringRef, llvm::Module&, llvm::TargetMachine*, llvm::TargetLibraryInfoImpl*, llvm::ToolOutputFile*, llvm::ToolOutputFile*, llvm::ToolOutputFile*, llvm::StringRef, llvm::ArrayRefllvm::StringRef, llvm::opt_tool::OutputKind, llvm::opt_tool::VerifierKind, bool, bool, bool, bool, bool) (build-all/bin/opt+0x795652)
#25 0x00000000007a81dd main (build-all/bin/opt+0x7a81dd)
#26 0x00007fc94eee4555 __libc_start_main (/lib64/libc.so.6+0x22555)
#27 0x0000000000790a9c _start (build-all/bin/opt+0x790a9c)
Abort
The crash starts happening with commit c7b25e43599
[LoopDeletion] Use max trip count to break backedge in addition to exact one

We'd added support a while back from breaking the backedge if SCEV can prove the trip count is zero. However, we used the exact trip count which requires *all* exits be analyzeable. I noticed while writing test cases for another patch that this disallows cases where one exit is provably taken paired with another which is unknown. This patch adds the upper bound case.

We could use a symbolic max trip count here instead, but we use an isKnownNonZero filter (presumably for compile time?) for the first-iteration reasoning. I decided this was a more obvious incremental step, and we could go back and untangle the schemes separately.

Differential Revision: https://reviews.llvm.org/D108833

`
I made a comment about it in Phabricator here:
https://reviews.llvm.org/D108833#3158617

bbi-63573.ll.gz

[fhahn]

https://reviews.llvm.org/D107219 added sinkRegionForLoopNest which may be the actual culprit.

[mikaelholmen]

Since https://reviews.llvm.org/D149136 the bbi-63573.ll reproducer doesn't crash anymore.
I've no idea if that is by luck or if the problem is actually fixed.

[fhahn]

From a glance at the patch it seems like this would just hide the issue.