[NewGVN] Assertion `BeforeCC->isEquivalentTo(AfterCC) && "Value number changed after main loop completed!"' failed

[zhendongsu]

It appears to be a recent regression.

Compiler Explorer: https://godbolt.org/z/M87jMoKT1

% clangtk -v
clang version 17.0.0 (https://github.com/llvm/llvm-project.git 09d6ee765780837d5156ac81f968465bdcec73ba)
Target: x86_64-unknown-linux-gnu
Thread model: posix
InstalledDir: /local/suz-local/opfuzz/bin
Found candidate GCC installation: /usr/lib/gcc/x86_64-linux-gnu/11
Found candidate GCC installation: /usr/lib/gcc/x86_64-linux-gnu/12
Selected GCC installation: /usr/lib/gcc/x86_64-linux-gnu/12
Candidate multilib: .;@m64
Selected multilib: .;@m64
% 
% clangtk -O3 -mllvm -enable-newgvn small.c
clang-17: /local/suz-local/software/clangbuild/llvm-project/llvm/lib/Transforms/Scalar/NewGVN.cpp:3312: void {anonymous}::NewGVN::verifyIterationSettled(llvm::Function&): Assertion `BeforeCC->isEquivalentTo(AfterCC) && "Value number changed after main loop completed!"' 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: /local/home/suz/suz-local/software/local/clang-trunk/bin/clang-17 -cc1 -triple x86_64-unknown-linux-gnu -emit-obj -dumpdir a- -disable-free -clear-ast-before-backend -main-file-name small.c -mrelocation-model pic -pic-level 2 -pic-is-pie -mframe-pointer=none -fmath-errno -ffp-contract=on -fno-rounding-math -mconstructor-aliases -funwind-tables=2 -target-cpu x86-64 -tune-cpu generic -debugger-tuning=gdb -fcoverage-compilation-dir=/local/suz-local/software/emitesting/bugs/20230613-clangtk-m64-O3-mllvm-enable-newgvn-mllvm-opaque-pointers-build-202922/delta -resource-dir /local/home/suz/suz-local/software/local/clang-trunk/lib/clang/17 -I /usr/local/include -internal-isystem /local/home/suz/suz-local/software/local/clang-trunk/lib/clang/17/include -internal-isystem /usr/local/include -internal-isystem /usr/lib/gcc/x86_64-linux-gnu/12/../../../../x86_64-linux-gnu/include -internal-externc-isystem /usr/include/x86_64-linux-gnu -internal-externc-isystem /include -internal-externc-isystem /usr/include -O3 -fdebug-compilation-dir=/local/suz-local/software/emitesting/bugs/20230613-clangtk-m64-O3-mllvm-enable-newgvn-mllvm-opaque-pointers-build-202922/delta -ferror-limit 19 -fgnuc-version=4.2.1 -fcolor-diagnostics -vectorize-loops -vectorize-slp -mllvm -enable-newgvn -faddrsig -D__GCC_HAVE_DWARF2_CFI_ASM=1 -o /tmp/small-e25cb5.o -x c small.c
1.	<eof> parser at end of file
2.	Optimizer
 #0 0x0000563ca5a0a970 llvm::sys::PrintStackTrace(llvm::raw_ostream&, int) (/local/home/suz/suz-local/software/local/clang-trunk/bin/clang-17+0x3b79970)
 #1 0x0000563ca5a08244 SignalHandler(int) Signals.cpp:0:0
 #2 0x00007f65617f3520 (/lib/x86_64-linux-gnu/libc.so.6+0x42520)
 #3 0x00007f6561847a7c __pthread_kill_implementation ./nptl/pthread_kill.c:44:76
 #4 0x00007f6561847a7c __pthread_kill_internal ./nptl/pthread_kill.c:78:10
 #5 0x00007f6561847a7c pthread_kill ./nptl/pthread_kill.c:89:10
 #6 0x00007f65617f3476 gsignal ./signal/../sysdeps/posix/raise.c:27:6
 #7 0x00007f65617d97f3 abort ./stdlib/abort.c:81:7
 #8 0x00007f65617d971b _nl_load_domain ./intl/loadmsgcat.c:1177:9
 #9 0x00007f65617eae96 (/lib/x86_64-linux-gnu/libc.so.6+0x39e96)
#10 0x0000563ca9101794 (anonymous namespace)::NewGVN::verifyIterationSettled(llvm::Function&) (.constprop.0) NewGVN.cpp:0:0
#11 0x0000563ca9103232 (anonymous namespace)::NewGVN::runGVN() NewGVN.cpp:0:0
#12 0x0000563ca9105146 llvm::NewGVNPass::run(llvm::Function&, llvm::AnalysisManager<llvm::Function>&) (/local/home/suz/suz-local/software/local/clang-trunk/bin/clang-17+0x7274146)
#13 0x0000563ca6cbf3a6 llvm::detail::PassModel<llvm::Function, llvm::NewGVNPass, llvm::PreservedAnalyses, llvm::AnalysisManager<llvm::Function>>::run(llvm::Function&, llvm::AnalysisManager<llvm::Function>&) (/local/home/suz/suz-local/software/local/clang-trunk/bin/clang-17+0x4e2e3a6)
#14 0x0000563ca322115a 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>&) (/local/home/suz/suz-local/software/local/clang-trunk/bin/clang-17+0x139015a)
#15 0x0000563ca4922d1c llvm::CGSCCToFunctionPassAdaptor::run(llvm::LazyCallGraph::SCC&, llvm::AnalysisManager<llvm::LazyCallGraph::SCC, llvm::LazyCallGraph&>&, llvm::LazyCallGraph&, llvm::CGSCCUpdateResult&) (/local/home/suz/suz-local/software/local/clang-trunk/bin/clang-17+0x2a91d1c)
#16 0x0000563ca3205fd6 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&) (/local/home/suz/suz-local/software/local/clang-trunk/bin/clang-17+0x1374fd6)
#17 0x0000563ca491ca1d 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&) (/local/home/suz/suz-local/software/local/clang-trunk/bin/clang-17+0x2a8ba1d)
#18 0x0000563ca6cbdb46 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&) (/local/home/suz/suz-local/software/local/clang-trunk/bin/clang-17+0x4e2cb46)
#19 0x0000563ca4923ace llvm::DevirtSCCRepeatedPass::run(llvm::LazyCallGraph::SCC&, llvm::AnalysisManager<llvm::LazyCallGraph::SCC, llvm::LazyCallGraph&>&, llvm::LazyCallGraph&, llvm::CGSCCUpdateResult&) (/local/home/suz/suz-local/software/local/clang-trunk/bin/clang-17+0x2a92ace)
#20 0x0000563ca6cbdb96 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&) (/local/home/suz/suz-local/software/local/clang-trunk/bin/clang-17+0x4e2cb96)
#21 0x0000563ca491ea5d llvm::ModuleToPostOrderCGSCCPassAdaptor::run(llvm::Module&, llvm::AnalysisManager<llvm::Module>&) (/local/home/suz/suz-local/software/local/clang-trunk/bin/clang-17+0x2a8da5d)
#22 0x0000563ca6e8ec94 llvm::ModuleInlinerWrapperPass::run(llvm::Module&, llvm::AnalysisManager<llvm::Module>&) (/local/home/suz/suz-local/software/local/clang-trunk/bin/clang-17+0x4ffdc94)
#23 0x0000563ca6cbd2d6 llvm::detail::PassModel<llvm::Module, llvm::ModuleInlinerWrapperPass, llvm::PreservedAnalyses, llvm::AnalysisManager<llvm::Module>>::run(llvm::Module&, llvm::AnalysisManager<llvm::Module>&) (/local/home/suz/suz-local/software/local/clang-trunk/bin/clang-17+0x4e2c2d6)
#24 0x0000563ca53b29a1 llvm::PassManager<llvm::Module, llvm::AnalysisManager<llvm::Module>>::run(llvm::Module&, llvm::AnalysisManager<llvm::Module>&) (/local/home/suz/suz-local/software/local/clang-trunk/bin/clang-17+0x35219a1)
#25 0x0000563ca5c71a10 (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
#26 0x0000563ca5c7509a 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>>) (/local/home/suz/suz-local/software/local/clang-trunk/bin/clang-17+0x3de409a)
#27 0x0000563ca6c569d5 clang::BackendConsumer::HandleTranslationUnit(clang::ASTContext&) (/local/home/suz/suz-local/software/local/clang-trunk/bin/clang-17+0x4dc59d5)
#28 0x0000563ca7bd1db9 clang::ParseAST(clang::Sema&, bool, bool) (/local/home/suz/suz-local/software/local/clang-trunk/bin/clang-17+0x5d40db9)
#29 0x0000563ca64ac309 clang::FrontendAction::Execute() (/local/home/suz/suz-local/software/local/clang-trunk/bin/clang-17+0x461b309)
#30 0x0000563ca642f7fe clang::CompilerInstance::ExecuteAction(clang::FrontendAction&) (/local/home/suz/suz-local/software/local/clang-trunk/bin/clang-17+0x459e7fe)
#31 0x0000563ca6579d2f clang::ExecuteCompilerInvocation(clang::CompilerInstance*) (/local/home/suz/suz-local/software/local/clang-trunk/bin/clang-17+0x46e8d2f)
#32 0x0000563ca2e71f03 cc1_main(llvm::ArrayRef<char const*>, char const*, void*) (/local/home/suz/suz-local/software/local/clang-trunk/bin/clang-17+0xfe0f03)
#33 0x0000563ca2e6dcd3 ExecuteCC1Tool(llvm::SmallVectorImpl<char const*>&, llvm::ToolContext const&) driver.cpp:0:0
#34 0x0000563ca2e6f36c clang_main(int, char**, llvm::ToolContext const&) (/local/home/suz/suz-local/software/local/clang-trunk/bin/clang-17+0xfde36c)
#35 0x0000563ca2d827b3 main (/local/home/suz/suz-local/software/local/clang-trunk/bin/clang-17+0xef17b3)
#36 0x00007f65617dad90 __libc_start_call_main ./csu/../sysdeps/nptl/libc_start_call_main.h:58:16
#37 0x00007f65617dae40 call_init ./csu/../csu/libc-start.c:128:20
#38 0x00007f65617dae40 __libc_start_main ./csu/../csu/libc-start.c:379:5
#39 0x0000563ca2e68545 _start (/local/home/suz/suz-local/software/local/clang-trunk/bin/clang-17+0xfd7545)
clangtk: error: unable to execute command: Aborted
clangtk: error: clang frontend command failed due to signal (use -v to see invocation)
clang version 17.0.0 (https://github.com/llvm/llvm-project.git 09d6ee765780837d5156ac81f968465bdcec73ba)
Target: x86_64-unknown-linux-gnu
Thread model: posix
InstalledDir: /local/suz-local/opfuzz/bin
clangtk: note: diagnostic msg: 
********************

PLEASE ATTACH THE FOLLOWING FILES TO THE BUG REPORT:
Preprocessed source(s) and associated run script(s) are located at:
clangtk: note: diagnostic msg: /tmp/small-8a9f40.c
clangtk: note: diagnostic msg: /tmp/small-8a9f40.sh
clangtk: note: diagnostic msg: 

********************
% 
% cat small.c
extern void e();
int a, b, c, d;
int main() {
  int g = 1;
  while (a) {
    int h = 1, i;
    if (g)
    L:;
      i = c;
    d = c % h;
    while (1) {
      e();
      break;
    }
    h = 0;
    if (b) {
      g = 0;
      if (a)
        goto L;
    }
    c = g / ~i;
  }
  return 0;
}

[vfdff]

related to https://reviews.llvm.org/D130910, simplified case: https://gcc.godbolt.org/z/hdT1d18zY

[ManuelJBrito]

This crash is due to the caching for OpIsSafeForPhiOfOps being unsound. It uses information thats valid for a given block but may not be true for blocks processed after.

Detailed analysis for the reduced test case:

While processing instructions

• %phi1 symbolizes to 0 (ignores unreachable edge)
• %rem symbolizes to poison - no attempt at making a phiofops.
• Attempt a phiofops for %div, in the process %val is marked as safe. (dominates %div)
• %phi1 symbolizes to itself (reachability changes)
• %rem symbolizes to itself, so we try to make a phiofops - val is deemed safe because of the cached result and the phiofops succeeds.

When verifying if a maximal fixpoint was reached:

• the cache is cleared
• we try to make a phiofops for %rem and fail because %val is deemed unsafe.
• %rem changes classes which causes the assert to fail !!

Here is another example to show that this is not specific to safety of memory accesses https://gcc.godbolt.org/z/Kvxr6oWba.

I'm thinking we can either refine the caching to have the phi block as part of it or drop it completely.

CC @nunoplopes, @alinas, @kmitropoulou