clang: 18: Assertion `ProcessedCount[V] < 100 && "Seem to have processed the same Value a lot"' failed.

[wierton]

When compile this program with -O3 -mllvm -enable-newgvn, clang crashes:

int A[4][4][4][4];
int main(void) {
  int i, j, k, l;
  for (i = 0; i < 4; i++)
    for (j = 0; j < 4; j++)
      for (k = 0; k < 4; k++)
        for (l = 0; l < 4; l++)
          A[i][j][k][l] = i + j + k + l;
  return 0;
}

This crash can be verified at link: https://godbolt.org/z/3b8bYfj8M

Full stack dump is pasted below:

clang: /root/llvm-project/llvm/lib/Transforms/Scalar/NewGVN.cpp:3030: void {anonymous}::NewGVN::updateProcessedCount(const llvm::Value*): Assertion `ProcessedCount[V] < 100 && "Seem to have processed the same Value a lot"' failed.
PLEASE submit a bug report to https://github.com/llvm/llvm-project/issues/ and include the crash backtrace, preprocessed source, and associated run script.
Stack dump:
0.	Program arguments: /opt/compiler-explorer/clang-assertions-trunk/bin/clang -gdwarf-4 -g -o /app/output.s -mllvm --x86-asm-syntax=intel -S --gcc-toolchain=/opt/compiler-explorer/gcc-9.2.0 -fcolor-diagnostics -fno-crash-diagnostics -O3 -mllvm -enable-newgvn <source>
1.	<eof> parser at end of file
2.	Optimizer
 #0 0x000000000372f498 llvm::sys::PrintStackTrace(llvm::raw_ostream&, int) (/opt/compiler-explorer/clang-assertions-trunk/bin/clang+0x372f498)
 #1 0x000000000372d15c llvm::sys::CleanupOnSignal(unsigned long) (/opt/compiler-explorer/clang-assertions-trunk/bin/clang+0x372d15c)
 #2 0x0000000003675a78 CrashRecoverySignalHandler(int) CrashRecoveryContext.cpp:0:0
 #3 0x00007fb819dcc420 __restore_rt (/lib/x86_64-linux-gnu/libpthread.so.0+0x14420)
 #4 0x00007fb81988f00b raise (/lib/x86_64-linux-gnu/libc.so.6+0x4300b)
 #5 0x00007fb81986e859 abort (/lib/x86_64-linux-gnu/libc.so.6+0x22859)
 #6 0x00007fb81986e729 (/lib/x86_64-linux-gnu/libc.so.6+0x22729)
 #7 0x00007fb81987ffd6 (/lib/x86_64-linux-gnu/libc.so.6+0x33fd6)
 #8 0x00000000074e4245 (/opt/compiler-explorer/clang-assertions-trunk/bin/clang+0x74e4245)
 #9 0x00000000074f244e (anonymous namespace)::NewGVN::iterateTouchedInstructions() NewGVN.cpp:0:0
#10 0x00000000074f4c76 (anonymous namespace)::NewGVN::runGVN() NewGVN.cpp:0:0
#11 0x00000000074f707d llvm::NewGVNPass::run(llvm::Function&, llvm::AnalysisManager<llvm::Function>&) (/opt/compiler-explorer/clang-assertions-trunk/bin/clang+0x74f707d)
#12 0x0000000004b6e14e llvm::detail::PassModel<llvm::Function, llvm::NewGVNPass, llvm::PreservedAnalyses, llvm::AnalysisManager<llvm::Function>>::run(llvm::Function&, llvm::AnalysisManager<llvm::Function>&) (/opt/compiler-explorer/clang-assertions-trunk/bin/clang+0x4b6e14e)
#13 0x0000000000fbe8cd 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/clang+0xfbe8cd)
#14 0x00000000026a55cf llvm::CGSCCToFunctionPassAdaptor::run(llvm::LazyCallGraph::SCC&, llvm::AnalysisManager<llvm::LazyCallGraph::SCC, llvm::LazyCallGraph&>&, llvm::LazyCallGraph&, llvm::CGSCCUpdateResult&) (/opt/compiler-explorer/clang-assertions-trunk/bin/clang+0x26a55cf)
#15 0x0000000000fa2d2e llvm::detail::PassModel<llvm::LazyCallGraph::SCC, llvm::CGSCCToFunctionPassAdaptor, llvm::PreservedAnalyses, 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&) (/opt/compiler-explorer/clang-assertions-trunk/bin/clang+0xfa2d2e)
#16 0x000000000269da7b 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&) (/opt/compiler-explorer/clang-assertions-trunk/bin/clang+0x269da7b)
#17 0x0000000004b6d7ee llvm::detail::PassModel<llvm::LazyCallGraph::SCC, llvm::PassManager<llvm::LazyCallGraph::SCC, llvm::AnalysisManager<llvm::LazyCallGraph::SCC, llvm::LazyCallGraph&>, llvm::LazyCallGraph&, llvm::CGSCCUpdateResult&>, llvm::PreservedAnalyses, 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&) (/opt/compiler-explorer/clang-assertions-trunk/bin/clang+0x4b6d7ee)
#18 0x00000000026a1c85 llvm::DevirtSCCRepeatedPass::run(llvm::LazyCallGraph::SCC&, llvm::AnalysisManager<llvm::LazyCallGraph::SCC, llvm::LazyCallGraph&>&, llvm::LazyCallGraph&, llvm::CGSCCUpdateResult&) (/opt/compiler-explorer/clang-assertions-trunk/bin/clang+0x26a1c85)
#19 0x0000000004b6d80e llvm::detail::PassModel<llvm::LazyCallGraph::SCC, llvm::DevirtSCCRepeatedPass, llvm::PreservedAnalyses, 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&) (/opt/compiler-explorer/clang-assertions-trunk/bin/clang+0x4b6d80e)
#20 0x000000000269fe29 llvm::ModuleToPostOrderCGSCCPassAdaptor::run(llvm::Module&, llvm::AnalysisManager<llvm::Module>&) (/opt/compiler-explorer/clang-assertions-trunk/bin/clang+0x269fe29)
#21 0x0000000004d29c0f llvm::ModuleInlinerWrapperPass::run(llvm::Module&, llvm::AnalysisManager<llvm::Module>&) (/opt/compiler-explorer/clang-assertions-trunk/bin/clang+0x4d29c0f)
#22 0x0000000004a1333e llvm::detail::PassModel<llvm::Module, llvm::ModuleInlinerWrapperPass, llvm::PreservedAnalyses, llvm::AnalysisManager<llvm::Module>>::run(llvm::Module&, llvm::AnalysisManager<llvm::Module>&) (/opt/compiler-explorer/clang-assertions-trunk/bin/clang+0x4a1333e)
#23 0x00000000030f70cc llvm::PassManager<llvm::Module, llvm::AnalysisManager<llvm::Module>>::run(llvm::Module&, llvm::AnalysisManager<llvm::Module>&) (/opt/compiler-explorer/clang-assertions-trunk/bin/clang+0x30f70cc)
#24 0x00000000039a06b0 (anonymous namespace)::EmitAssemblyHelper::RunOptimizationPipeline(clang::BackendAction, std::unique_ptr<llvm::raw_pwrite_stream, std::default_delete<llvm::raw_pwrite_stream>>&, std::unique_ptr<llvm::ToolOutputFile, std::default_delete<llvm::ToolOutputFile>>&) BackendUtil.cpp:0:0
#25 0x00000000039a3a96 (anonymous namespace)::EmitAssemblyHelper::EmitAssembly(clang::BackendAction, std::unique_ptr<llvm::raw_pwrite_stream, std::default_delete<llvm::raw_pwrite_stream>>) BackendUtil.cpp:0:0
#26 0x00000000039a40a9 clang::EmitBackendOutput(clang::DiagnosticsEngine&, clang::HeaderSearchOptions const&, clang::CodeGenOptions const&, clang::TargetOptions const&, clang::LangOptions const&, llvm::StringRef, llvm::Module*, clang::BackendAction, llvm::IntrusiveRefCntPtr<llvm::vfs::FileSystem>, std::unique_ptr<llvm::raw_pwrite_stream, std::default_delete<llvm::raw_pwrite_stream>>) (/opt/compiler-explorer/clang-assertions-trunk/bin/clang+0x39a40a9)
#27 0x000000000499c34f clang::BackendConsumer::HandleTranslationUnit(clang::ASTContext&) (/opt/compiler-explorer/clang-assertions-trunk/bin/clang+0x499c34f)
#28 0x0000000005ea1529 clang::ParseAST(clang::Sema&, bool, bool) (/opt/compiler-explorer/clang-assertions-trunk/bin/clang+0x5ea1529)
#29 0x000000000499b538 clang::CodeGenAction::ExecuteAction() (/opt/compiler-explorer/clang-assertions-trunk/bin/clang+0x499b538)
#30 0x00000000041fefa9 clang::FrontendAction::Execute() (/opt/compiler-explorer/clang-assertions-trunk/bin/clang+0x41fefa9)
#31 0x000000000418044e clang::CompilerInstance::ExecuteAction(clang::FrontendAction&) (/opt/compiler-explorer/clang-assertions-trunk/bin/clang+0x418044e)
#32 0x00000000042de12e clang::ExecuteCompilerInvocation(clang::CompilerInstance*) (/opt/compiler-explorer/clang-assertions-trunk/bin/clang+0x42de12e)
#33 0x0000000000befa56 cc1_main(llvm::ArrayRef<char const*>, char const*, void*) (/opt/compiler-explorer/clang-assertions-trunk/bin/clang+0xbefa56)
#34 0x0000000000be731a ExecuteCC1Tool(llvm::SmallVectorImpl<char const*>&, llvm::ToolContext const&) driver.cpp:0:0
#35 0x0000000003fdc649 void llvm::function_ref<void ()>::callback_fn<clang::driver::CC1Command::Execute(llvm::ArrayRef<std::optional<llvm::StringRef>>, std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char>>*, bool*) const::'lambda'()>(long) Job.cpp:0:0
#36 0x0000000003675f24 llvm::CrashRecoveryContext::RunSafely(llvm::function_ref<void ()>) (/opt/compiler-explorer/clang-assertions-trunk/bin/clang+0x3675f24)
#37 0x0000000003fdcc3f clang::driver::CC1Command::Execute(llvm::ArrayRef<std::optional<llvm::StringRef>>, std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char>>*, bool*) const (.part.0) Job.cpp:0:0
#38 0x0000000003fa4e05 clang::driver::Compilation::ExecuteCommand(clang::driver::Command const&, clang::driver::Command const*&, bool) const (/opt/compiler-explorer/clang-assertions-trunk/bin/clang+0x3fa4e05)
#39 0x0000000003fa586d clang::driver::Compilation::ExecuteJobs(clang::driver::JobList const&, llvm::SmallVectorImpl<std::pair<int, clang::driver::Command const*>>&, bool) const (/opt/compiler-explorer/clang-assertions-trunk/bin/clang+0x3fa586d)
#40 0x0000000003fad795 clang::driver::Driver::ExecuteCompilation(clang::driver::Compilation&, llvm::SmallVectorImpl<std::pair<int, clang::driver::Command const*>>&) (/opt/compiler-explorer/clang-assertions-trunk/bin/clang+0x3fad795)
#41 0x0000000000becefc clang_main(int, char**, llvm::ToolContext const&) (/opt/compiler-explorer/clang-assertions-trunk/bin/clang+0xbecefc)
#42 0x0000000000ae7091 main (/opt/compiler-explorer/clang-assertions-trunk/bin/clang+0xae7091)
#43 0x00007fb819870083 __libc_start_main (/lib/x86_64-linux-gnu/libc.so.6+0x24083)
#44 0x0000000000be6dfe _start (/opt/compiler-explorer/clang-assertions-trunk/bin/clang+0xbe6dfe)
clang: error: clang frontend command failed with exit code 134 (use -v to see invocation)

[XChy]

A reduced IR:

; RUN: opt -S -passes=newgvn < %s
define i32 @main() {
entry:
  br label %for.body9

for.body9:                                        ; preds = %for.body9, %entry
  %indvars.iv = phi i64 [ 0, %entry ], [ %indvars.iv.next, %for.body9 ]
  %0 = add i64 1, %indvars.iv
  %1 = add i64 %0, 1
  %2 = trunc i64 %1 to i32
  %indvars.iv.next = add i64 %indvars.iv, 1
  br label %for.body9
}

It seems that NewGVN doesn't handle infinite loops correctly. If possible, I'll post a PR to fix it.

[XChy]

It seems that NewGVN doesn't handle infinite loops correctly. If possible, I'll post a PR to fix it.

I'm wrong here. It's also a problem for finite loops:

; RUN: opt -S -passes=newgvn < %s
declare void @dummy(i64)

define i32 @foo() {
entry:
  br label %for.body

for.body:                                        ; preds = %for.body, %entry
  %indvars.iv = phi i64 [ 0, %entry ], [ %indvars.iv.next, %for.body ]
  %0 = add i64 %indvars.iv, 1
  %1 = add i64 %0, 1
  call void @dummy(i64 %1)

  %indvars.iv.next = add i64 %indvars.iv, 1
  %tobool = icmp slt i64 %indvars.iv.next, 1000
  br i1 %tobool, label %for.body, label %end

end:
  ret i32 0
}

[alinas]

@alinas @ManuelJBrito @kmitropoulou @nunoplopes