Instruction Combining loop

[luismarques]

Bugzilla Link	51220
Version	trunk
OS	All
CC	@asb,@topperc,@fhahn,@LebedevRI,@rotateright

Extended Description

This happens since commit 88241ff ([Passes] Move ADCE before DSE & LICM.)

$ cat test.c
float a;
double b;
void c() {
  for (int d = 0; d < 9; ++d)
    for (char e = 0; e < 24; ++e)
      for (char f = 0; f < 106; ++f) {
        for (short g = 0; g < 6; ++g)
          ;
        ++a;
      }
  a = b;
}

$ clang -O2 --target=riscv32 -c test.c
fatal error: error in backend: Instruction Combining seems stuck in an infinite loop after 100 iterations.
PLEASE submit a bug report to https://bugs.llvm.org/ and include the crash backtrace, preprocessed source, and associated run script.
Stack dump:
0.      Program arguments: /home/luismarques/llvm-project/build/debug-all/bin/clang -O2 --target=riscv32 -c test.c 
1.      <eof> parser at end of file
2.      Per-module optimization passes
3.      Running pass 'Function Pass Manager' on module 'test.c'.
4.      Running pass 'Combine redundant instructions' on function '@c'
 #0 0x00007fdb35fe0c67 llvm::sys::PrintStackTrace(llvm::raw_ostream&, int) /home/luismarques/llvm-project/llvm/lib/Support/Unix/Signals.inc:563:11
 #1 0x00007fdb35fe0e7b PrintStackTraceSignalHandler(void*) /home/luismarques/llvm-project/llvm/lib/Support/Unix/Signals.inc:630:1
 #2 0x00007fdb35fdf260 llvm::sys::RunSignalHandlers() /home/luismarques/llvm-project/llvm/lib/Support/Signals.cpp:71:5
 #3 0x00007fdb35fe041b llvm::sys::CleanupOnSignal(unsigned long) /home/luismarques/llvm-project/llvm/lib/Support/Unix/Signals.inc:0:3
 #4 0x00007fdb35e3a39e (anonymous namespace)::CrashRecoveryContextImpl::HandleCrash(int, unsigned long) /home/luismarques/llvm-project/llvm/lib/Support/CrashRecoveryContext.cpp:0:7
 #5 0x00007fdb35e3a2c8 llvm::CrashRecoveryContext::HandleExit(int) /home/luismarques/llvm-project/llvm/lib/Support/CrashRecoveryContext.cpp:442:3
 #6 0x00007fdb35fd8e0b llvm::sys::Process::Exit(int) /home/luismarques/llvm-project/llvm/lib/Support/Process.cpp:97:10
 #7 0x000055b8ed41d6a4 (/home/luismarques/llvm-project/build/debug-all/bin/clang+0x496a4)
 #8 0x00007fdb35e5f5d1 llvm::report_fatal_error(llvm::Twine const&, bool) /home/luismarques/llvm-project/llvm/lib/Support/ErrorHandling.cpp:108:5
 #9 0x00007fdb397c2daa combineInstructionsOverFunction(llvm::Function&, llvm::InstCombineWorklist&, llvm::AAResults*, llvm::AssumptionCache&, llvm::TargetLibraryInfo&, llvm::TargetTransformInfo&, llvm::DominatorTree&, llvm::OptimizationRemarkEmitter&, llvm::BlockFrequencyInfo*, llvm::ProfileSummaryInfo*, unsigned int, llvm::LoopInfo*) /home/luismarques/llvm-project/llvm/lib/Transforms/InstCombine/InstructionCombining.cpp:3879:9
#10 0x00007fdb397c3358 llvm::InstructionCombiningPass::runOnFunction(llvm::Function&) /home/luismarques/llvm-project/llvm/lib/Transforms/InstCombine/InstructionCombining.cpp:3978:3
#11 0x00007fdb369f144d llvm::FPPassManager::runOnFunction(llvm::Function&) /home/luismarques/llvm-project/llvm/lib/IR/LegacyPassManager.cpp:1519:23
#12 0x00007fdb369f694f llvm::FPPassManager::runOnModule(llvm::Module&) /home/luismarques/llvm-project/llvm/lib/IR/LegacyPassManager.cpp:1565:16
#13 0x00007fdb369f1dfa (anonymous namespace)::MPPassManager::runOnModule(llvm::Module&) /home/luismarques/llvm-project/llvm/lib/IR/LegacyPassManager.cpp:1634:23
#14 0x00007fdb369f190d llvm::legacy::PassManagerImpl::run(llvm::Module&) /home/luismarques/llvm-project/llvm/lib/IR/LegacyPassManager.cpp:615:16
#15 0x00007fdb369f6c51 llvm::legacy::PassManager::run(llvm::Module&) /home/luismarques/llvm-project/llvm/lib/IR/LegacyPassManager.cpp:1761:3
#16 0x00007fdb3c73c4a2 (anonymous namespace)::EmitAssemblyHelper::EmitAssembly(clang::BackendAction, std::unique_ptr<llvm::raw_pwrite_stream, std::default_delete<llvm::raw_pwrite_stream> >) /home/luismarques/llvm-project/clang/lib/CodeGen/BackendUtil.cpp:981:3
#17 0x00007fdb3c738b49 clang::EmitBackendOutput(clang::DiagnosticsEngine&, clang::HeaderSearchOptions const&, clang::CodeGenOptions const&, clang::TargetOptions const&, clang::LangOptions const&, llvm::DataLayout const&, llvm::Module*, clang::BackendAction, std::unique_ptr<llvm::raw_pwrite_stream, std::default_delete<llvm::raw_pwrite_stream> >) /home/luismarques/llvm-project/clang/lib/CodeGen/BackendUtil.cpp:1670:5
#18 0x00007fdb3cda0a5f clang::BackendConsumer::HandleTranslationUnit(clang::ASTContext&) /home/luismarques/llvm-project/clang/lib/CodeGen/CodeGenAction.cpp:341:7
#19 0x00007fdb308535df clang::ParseAST(clang::Sema&, bool, bool) /home/luismarques/llvm-project/clang/lib/Parse/ParseAST.cpp:178:12
#20 0x00007fdb3956eb0c clang::ASTFrontendAction::ExecuteAction() /home/luismarques/llvm-project/clang/lib/Frontend/FrontendAction.cpp:1058:1
#21 0x00007fdb3cd9acc7 clang::CodeGenAction::ExecuteAction() /home/luismarques/llvm-project/clang/lib/CodeGen/CodeGenAction.cpp:0:28
#22 0x00007fdb3956e439 clang::FrontendAction::Execute() /home/luismarques/llvm-project/clang/lib/Frontend/FrontendAction.cpp:953:7
#23 0x00007fdb394d8827 clang::CompilerInstance::ExecuteAction(clang::FrontendAction&) /home/luismarques/llvm-project/clang/lib/Frontend/CompilerInstance.cpp:989:23
#24 0x00007fdb3dd54e6e clang::ExecuteCompilerInvocation(clang::CompilerInstance*) /home/luismarques/llvm-project/clang/lib/FrontendTool/ExecuteCompilerInvocation.cpp:278:8
#25 0x000055b8ed41d075 cc1_main(llvm::ArrayRef<char const*>, char const*, void*) /home/luismarques/llvm-project/clang/tools/driver/cc1_main.cpp:240:13
#26 0x000055b8ed40ff9f ExecuteCC1Tool(llvm::SmallVectorImpl<char const*>&) /home/luismarques/llvm-project/clang/tools/driver/driver.cpp:330:5
#27 0x00007fdb38f46115 clang::driver::CC1Command::Execute(llvm::ArrayRef<llvm::Optional<llvm::StringRef> >, std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char> >*, bool*) const::$_1::operator()() const /home/luismarques/llvm-project/clang/lib/Driver/Job.cpp:404:34
#28 0x00007fdb38f460e5 void llvm::function_ref<void ()>::callback_fn<clang::driver::CC1Command::Execute(llvm::ArrayRef<llvm::Optional<llvm::StringRef> >, std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char> >*, bool*) const::$_1>(long) /home/luismarques/llvm-project/llvm/include/llvm/ADT/STLExtras.h:185:5
#29 0x00007fdb35e27a99 llvm::function_ref<void ()>::operator()() const /home/luismarques/llvm-project/llvm/include/llvm/ADT/STLExtras.h:209:5
#30 0x00007fdb35e3a187 llvm::CrashRecoveryContext::RunSafely(llvm::function_ref<void ()>) /home/luismarques/llvm-project/llvm/lib/Support/CrashRecoveryContext.cpp:425:3
#31 0x00007fdb38f45354 clang::driver::CC1Command::Execute(llvm::ArrayRef<llvm::Optional<llvm::StringRef> >, std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char> >*, bool*) const /home/luismarques/llvm-project/clang/lib/Driver/Job.cpp:404:7
#32 0x00007fdb38edb25c clang::driver::Compilation::ExecuteCommand(clang::driver::Command const&, clang::driver::Command const*&) const /home/luismarques/llvm-project/clang/lib/Driver/Compilation.cpp:195:7
#33 0x00007fdb38edb455 clang::driver::Compilation::ExecuteJobs(clang::driver::JobList const&, llvm::SmallVectorImpl<std::pair<int, clang::driver::Command const*> >&) const /home/luismarques/llvm-project/clang/lib/Driver/Compilation.cpp:246:13
#34 0x00007fdb38efb8dc clang::driver::Driver::ExecuteCompilation(clang::driver::Compilation&, llvm::SmallVectorImpl<std::pair<int, clang::driver::Command const*> >&) /home/luismarques/llvm-project/clang/lib/Driver/Driver.cpp:1513:7
#35 0x000055b8ed40f8e9 main /home/luismarques/llvm-project/clang/tools/driver/driver.cpp:502:9
#36 0x00007fdb356a8b25 __libc_start_main (/usr/lib/libc.so.6+0x27b25)
#37 0x000055b8ed40e8ce _start (/home/luismarques/llvm-project/build/debug-all/bin/clang+0x3a8ce)
clang-12: error: clang frontend command failed with exit code 70 (use -v to see invocation)
clang version 12.0.0
Target: riscv32
Thread model: posix
InstalledDir: /home/luismarques/llvm-project/build/debug-all/bin

[LebedevRI]

Can you post a reduced IR that only involves -instcombine?

[luismarques]

instcombine issue
$ opt -S --instcombine bug-instcombine.ll
LLVM ERROR: Instruction Combining seems stuck in an infinite loop after 100 iterations.
(...)

[asb]

Confirming this is still an issue in current HEAD.

[lukel97]

The resulting CFG is pretty pathological case, increasing -instcombine-infinite-loop-threshold to 200 seems to fix it. On release builds it may be fine because the default threshold is bumped from 100 to 1000.

[lukel97]

I don't think InstCombine is necessarily doing anything wrong here. After unrolling it receives a function with about 100 or so basic blocks in this chain:

It traverses through all the instructions and eventually realises at the very last BB it can delete the phi:

llvm-project/llvm/lib/Transforms/InstCombine/InstCombinePHI.cpp

Lines 1433 to 1443 in ab06a74

	// If this phi has a single use, and if that use just computes a value for
	// the next iteration of a loop, delete the phi. This occurs with unused
	// induction variables, e.g. "for (int j = 0; ; ++j);". Detecting this
	// common case here is good because the only other things that catch this
	// are induction variable analysis (sometimes) and ADCE, which is only run
	// late.
	if (PHIUser->hasOneUse() &&
	(isa<BinaryOperator>(PHIUser) || isa<GetElementPtrInst>(PHIUser)) &&
	PHIUser->user_back() == &PN) {
	return replaceInstUsesWith(PN, PoisonValue::get(PN.getType()));
	}

It then ends up as:

for.cond12.preheader.4.3:                         ; preds = %for.cond12.preheader.4.3, %for.cond12.preheader.4.2
  %inc18.4.3 = fadd float poison, 0.000000e+00
  br label %for.cond12.preheader.4.3

And then the induction instruction gets erased too:

for.cond12.preheader.4.3:                         ; preds = %for.cond12.preheader.4.3, %for.cond12.preheader.4.2
  br label %for.cond12.preheader.4.3

This then unlocks the same optimisation for the basic block above it, which then unlocks it for the block above it and so on and so forth. So it quickly reaches the maximum number of iterations.

When an instruction is removed, any operands it used are added back to the worklist because their use count changes.
However in this case, the operand added back to the worklist is not the phi node, it's one of the phi node's uses. And so the phi node isn't visited again, and the elimination doesn't occur within the same iteration

[nikic]

Candidate patch: https://reviews.llvm.org/D142293

[lukel97]

Second candidate patch: https://reviews.llvm.org/D142551

[nikic]

No longer reproduces, fixed as part of the single-iteration InstCombine work (presumably revisitation of newly one-use instructions).