Infinite loop in LLVM 17 (DominatorTreeBase)

[kornelski]

Code

https://github.com/kornelski/cavif-rs/tree/a0a3652ce8a36d4aee9c5da2ab35b4e97cd20fea/ravif (kornelski/cavif-rs#78)

cargo +nightly build --release

rustc never finishes building the ravif crate (0.11.3) when building with optimizations.

Version with regression

Regression is exactly in the LLVM 17 upgrade: 443c316

Backtrace

Backtrace

194.55 Gc   96.5%	194.55 Gc	 	 llvm::DominatorTreeBase<llvm::BasicBlock, false>::updateDFSNumbers() const
194.35 Gc   96.4%	-	 	  llvm::IDFCalculatorBase<llvm::BasicBlock, false>::calculate(llvm::SmallVectorImpl<llvm::BasicBlock*>&)
194.35 Gc   96.4%	-	 	   llvm::MemorySSAUpdater::applyInsertUpdates(llvm::ArrayRef<llvm::cfg::Update<llvm::BasicBlock*>>, llvm::DominatorTree&, llvm::GraphDiff<llvm::BasicBlock*, false> const*)
194.35 Gc   96.4%	-	 	    llvm::MemorySSAUpdater::updateExitBlocksForClonedLoop(llvm::ArrayRef<llvm::BasicBlock*>, llvm::ArrayRef<std::__1::unique_ptr<llvm::ValueMap<llvm::Value const*, llvm::WeakTrackingVH, llvm::ValueMapConfig<llvm::Value const*, llvm::sys::SmartMutex<false>>>, std::__1::default_delete<llvm::ValueMap<llvm::Value const*, llvm::WeakTrackingVH, llvm::ValueMapConfig<llvm::Value const*, llvm::sys::SmartMutex<false>>>>>>, llvm::DominatorTree&)
194.35 Gc   96.4%	-	 	     unswitchNontrivialInvariants(llvm::Loop&, llvm::Instruction&, llvm::ArrayRef<llvm::Value*>, llvm::IVConditionInfo&, llvm::DominatorTree&, llvm::LoopInfo&, llvm::AssumptionCache&, llvm::function_ref<void (bool, bool, llvm::ArrayRef<llvm::Loop*>)>, llvm::ScalarEvolution*, llvm::MemorySSAUpdater*, llvm::function_ref<void (llvm::Loop&, llvm::StringRef)>, bool)
194.35 Gc   96.4%	-	 	      unswitchBestCondition(llvm::Loop&, llvm::DominatorTree&, llvm::LoopInfo&, llvm::AssumptionCache&, llvm::AAResults&, llvm::TargetTransformInfo&, llvm::function_ref<void (bool, bool, llvm::ArrayRef<llvm::Loop*>)>, llvm::ScalarEvolution*, llvm::MemorySSAUpdater*, llvm::function_ref<void (llvm::Loop&, llvm::StringRef)>)
194.35 Gc   96.4%	-	 	       unswitchLoop(llvm::Loop&, llvm::DominatorTree&, llvm::LoopInfo&, llvm::AssumptionCache&, llvm::AAResults&, llvm::TargetTransformInfo&, bool, bool, llvm::function_ref<void (bool, bool, llvm::ArrayRef<llvm::Loop*>)>, llvm::ScalarEvolution*, llvm::MemorySSAUpdater*, llvm::ProfileSummaryInfo*, llvm::BlockFrequencyInfo*, llvm::function_ref<void (llvm::Loop&, llvm::StringRef)>)
194.35 Gc   96.4%	-	 	        llvm::SimpleLoopUnswitchPass::run(llvm::Loop&, llvm::AnalysisManager<llvm::Loop, llvm::LoopStandardAnalysisResults&>&, llvm::LoopStandardAnalysisResults&, llvm::LPMUpdater&)
194.35 Gc   96.4%	-	 	         std::__1::optional<llvm::PreservedAnalyses> llvm::PassManager<llvm::Loop, llvm::AnalysisManager<llvm::Loop, llvm::LoopStandardAnalysisResults&>, llvm::LoopStandardAnalysisResults&, llvm::LPMUpdater&>::runSinglePass<llvm::Loop, std::__1::unique_ptr<llvm::detail::PassConcept<llvm::Loop, llvm::AnalysisManager<llvm::Loop, llvm::LoopStandardAnalysisResults&>, llvm::LoopStandardAnalysisResults&, llvm::LPMUpdater&>, std::__1::default_delete<llvm::detail::PassConcept<llvm::Loop, llvm::AnalysisManager<llvm::Loop, llvm::LoopStandardAnalysisResults&>, llvm::LoopStandardAnalysisResults&, llvm::LPMUpdater&>>>>(llvm::Loop&, std::__1::unique_ptr<llvm::detail::PassConcept<llvm::Loop, llvm::AnalysisManager<llvm::Loop, llvm::LoopStandardAnalysisResults&>, llvm::LoopStandardAnalysisResults&, llvm::LPMUpdater&>, std::__1::default_delete<llvm::detail::PassConcept<llvm::Loop, llvm::AnalysisManager<llvm::Loop, llvm::LoopStandardAnalysisResults&>, llvm::LoopStandardAnalysisResults&, llvm::LPMUpdater&>>>&, llvm::AnalysisManager<llvm::Loop, llvm::LoopStandardAnalysisResults&>&, llvm::LoopStandardAnalysisResults&, llvm::LPMUpdater&, llvm::PassInstrumentation&)
194.35 Gc   96.4%	-	 	          llvm::PassManager<llvm::Loop, llvm::AnalysisManager<llvm::Loop, llvm::LoopStandardAnalysisResults&>, llvm::LoopStandardAnalysisResults&, llvm::LPMUpdater&>::runWithoutLoopNestPasses(llvm::Loop&, llvm::AnalysisManager<llvm::Loop, llvm::LoopStandardAnalysisResults&>&, llvm::LoopStandardAnalysisResults&, llvm::LPMUpdater&)
194.35 Gc   96.4%	-	 	           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&)
194.35 Gc   96.4%	-	 	            llvm::FunctionToLoopPassAdaptor::run(llvm::Function&, llvm::AnalysisManager<llvm::Function>&)
194.35 Gc   96.4%	-	 	             llvm::PassManager<llvm::Function, llvm::AnalysisManager<llvm::Function>>::run(llvm::Function&, llvm::AnalysisManager<llvm::Function>&)
194.35 Gc   96.4%	-	 	              llvm::CGSCCToFunctionPassAdaptor::run(llvm::LazyCallGraph::SCC&, llvm::AnalysisManager<llvm::LazyCallGraph::SCC, llvm::LazyCallGraph&>&, llvm::LazyCallGraph&, llvm::CGSCCUpdateResult&)
194.35 Gc   96.4%	-	 	               llvm::PassManager<llvm::LazyCallGraph::SCC, llvm::AnalysisManager<llvm::LazyCallGraph::SCC, llvm::LazyCallGraph&>, llvm::LazyCallGraph&, llvm::CGSCCUpdateResult&>::run(llvm::LazyCallGraph::SCC&, llvm::AnalysisManager<llvm::LazyCallGraph::SCC, llvm::LazyCallGraph&>&, llvm::LazyCallGraph&, llvm::CGSCCUpdateResult&)
194.35 Gc   96.4%	-	 	                llvm::DevirtSCCRepeatedPass::run(llvm::LazyCallGraph::SCC&, llvm::AnalysisManager<llvm::LazyCallGraph::SCC, llvm::LazyCallGraph&>&, llvm::LazyCallGraph&, llvm::CGSCCUpdateResult&)
194.35 Gc   96.4%	-	 	                 llvm::ModuleToPostOrderCGSCCPassAdaptor::run(llvm::Module&, llvm::AnalysisManager<llvm::Module>&)
194.35 Gc   96.4%	-	 	                  llvm::PassManager<llvm::Module, llvm::AnalysisManager<llvm::Module>>::run(llvm::Module&, llvm::AnalysisManager<llvm::Module>&)
194.35 Gc   96.4%	-	 	                   llvm::ModuleInlinerWrapperPass::run(llvm::Module&, llvm::AnalysisManager<llvm::Module>&)
194.35 Gc   96.4%	-	 	                    llvm::PassManager<llvm::Module, llvm::AnalysisManager<llvm::Module>>::run(llvm::Module&, llvm::AnalysisManager<llvm::Module>&)
194.35 Gc   96.4%	-	 	                     LLVMRustOptimize
194.35 Gc   96.4%	-	 	                      _RNvNtNtCslVCRTO4GVQO_18rustc_codegen_llvm4back5write13llvm_optimize

@rustbot modify labels: +regression-from-stable-to-nightly -regression-untriaged

[apiraino]

WG-prioritization assigning priority (Zulip discussion).

@kornelski is it clear by looking at he stacktrace what kind of code is involved that causes the issue? I'm thinking if a smaller reproducible can help.

@rustbot label -I-prioritize +P-high

[apiraino]

Can reproduce also with cargo +nightly build --release --no-default-features (to skip installing the asm dependency)

[nikic]

Problematic IR: https://gist.github.com/nikic/197fd03880311129fb4bd75ef7e94d62

Based on -debug-pass-manager output, it looks like we go into an infinite loop unswitching loop.

[nikic]

Here is a test case for -passes='simple-loop-unswitch<nontrivial>': https://gist.github.com/nikic/30fa12b459f8e4a7e7219898b6336c80

[nikic]

I've filed llvm/llvm-project#66868. This appears to be related to the new invariant condition injection.