LTO error: Instruction does not dominate all uses

[googlebleh]

clang crashes while linking

clang: error: unable to execute command: Aborted (core dumped)
clang: error: linker command failed due to signal (use -v to see invocation)

I followed the instructions here and narrowed it down to an LTO bug. File to reproduce is attached. a.out.0.2.internalize-reduced.bc.tar.gz

$ opt "-passes=lto<O3>" a.out.0.2.internalize-reduced.bc
WARNING: You're attempting to print out a bitcode file.
This is inadvisable as it may cause display problems. If
you REALLY want to taste LLVM bitcode first-hand, you
can force output with the `-f' option.

Instruction does not dominate all uses!
  %.lcssa16 = phi i64 [ %12, %9 ]
  %27 = add i64 %.lcssa16, 2
LLVM ERROR: Broken module found, compilation aborted!
PLEASE submit a bug report to https://github.com/llvm/llvm-project/issues/ and include the crash backtrace.
Stack dump:
0.      Program arguments: opt -passes=lto<O3> reduced-redacted.bc                                                                                                                             #0 0x00007e899efc4d90 llvm::sys::PrintStackTrace(llvm::raw_ostream&, int) /usr/src/debug/llvm/llvm-18.1.8.src/lib/Support/Unix/Signals.inc:723:22
 #1 0x00007e899efc1d4d llvm::sys::RunSignalHandlers() /usr/src/debug/llvm/llvm-18.1.8.src/lib/Support/Signals.cpp:105:20
 #2 0x00007e899efc1d4d SignalHandler /usr/src/debug/llvm/llvm-18.1.8.src/lib/Support/Unix/Signals.inc:403:31
 #3 0x00007e899e24c1d0 (/usr/lib/libc.so.6+0x3d1d0)
 #4 0x00007e899e2a53f4 __pthread_kill_implementation /usr/src/debug/glibc/glibc/nptl/pthread_kill.c:44:76
 #5 0x00007e899e24c120 raise /usr/src/debug/glibc/glibc/signal/../sysdeps/posix/raise.c:27:6
 #6 0x00007e899e2334c3 abort /usr/src/debug/glibc/glibc/stdlib/abort.c:81:7
 #7 0x00007e899ecaba1b std::mutex::lock() /usr/include/c++/14.1.1/bits/std_mutex.h:117:22
 #8 0x00007e899ecaba1b std::lock_guard<std::mutex>::lock_guard(std::mutex&) /usr/include/c++/14.1.1/bits/std_mutex.h:250:23
 #9 0x00007e899ecaba1b llvm::install_bad_alloc_error_handler(void (*)(void*, char const*, bool), void*) /usr/src/debug/llvm/llvm-18.1.8.src/lib/Support/ErrorHandling.cpp:131:61
#10 0x00007e899eec070e (/usr/lib/libLLVM.so.18.1+0x6c070e)
#11 0x00007e899f21aa1b (/usr/lib/libLLVM.so.18.1+0xa1aa1b)
#12 0x000055a86e4acf57 llvm::detail::PassModel<llvm::Module, llvm::VerifierPass, llvm::PreservedAnalyses, llvm::AnalysisManager<llvm::Module>>::run(llvm::Module&, llvm::AnalysisManager<llvm:
:Module>&) /usr/src/debug/llvm/llvm-18.1.8.src/include/llvm/IR/PassManagerInternal.h:90:3
#13 0x00007e899f1d767e llvm::PassManager<llvm::Module, llvm::AnalysisManager<llvm::Module>>::run(llvm::Module&, llvm::AnalysisManager<llvm::Module>&) /usr/src/debug/llvm/llvm-18.1.8.src/incl
ude/llvm/IR/PassManager.h:547:20
#14 0x000055a86e4b7052 llvm::SmallPtrSetImplBase::isSmall() const /usr/src/debug/llvm/llvm-18.1.8.src/include/llvm/ADT/SmallPtrSet.h:195:33
#15 0x000055a86e4b7052 llvm::SmallPtrSetImplBase::~SmallPtrSetImplBase() /usr/src/debug/llvm/llvm-18.1.8.src/include/llvm/ADT/SmallPtrSet.h:83:17
#16 0x000055a86e4b7052 llvm::SmallPtrSetImpl<llvm::AnalysisKey*>::~SmallPtrSetImpl() /usr/src/debug/llvm/llvm-18.1.8.src/include/llvm/ADT/SmallPtrSet.h:345:7
#17 0x000055a86e4b7052 llvm::SmallPtrSet<llvm::AnalysisKey*, 2u>::~SmallPtrSet() /usr/src/debug/llvm/llvm-18.1.8.src/include/llvm/ADT/SmallPtrSet.h:451:7
#18 0x000055a86e4b7052 llvm::PreservedAnalyses::~PreservedAnalyses() /usr/src/debug/llvm/llvm-18.1.8.src/include/llvm/IR/PassManager.h:172:7
#19 0x000055a86e4b7052 llvm::runPassPipeline(llvm::StringRef, llvm::Module&, llvm::TargetMachine*, llvm::TargetLibraryInfoImpl*, llvm::ToolOutputFile*, llvm::ToolOutputFile*, llvm::ToolOutpu
tFile*, llvm::StringRef, llvm::ArrayRef<llvm::PassPlugin>, llvm::opt_tool::OutputKind, llvm::opt_tool::VerifierKind, bool, bool, bool, bool, bool, bool, bool) /usr/src/debug/llvm/llvm-18.1.8
.src/tools/opt/NewPMDriver.cpp:527:10
#20 0x000055a86e4ab1ed std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char>>::~basic_string() /usr/include/c++/14.1.1/bits/basic_string.h:809:19
#21 0x000055a86e4ab1ed main /usr/src/debug/llvm/llvm-18.1.8.src/tools/opt/opt.cpp:747:3
#22 0x00007e899e234e08 __libc_start_call_main /usr/src/debug/glibc/glibc/csu/../sysdeps/nptl/libc_start_call_main.h:74:3
#23 0x00007e899e234ecc call_init /usr/src/debug/glibc/glibc/csu/../csu/libc-start.c:128:20
#24 0x00007e899e234ecc __libc_start_main /usr/src/debug/glibc/glibc/csu/../csu/libc-start.c:347:5
#25 0x000055a86e4abfd5 _start (/usr/bin/opt+0x1cfd5)
Aborted (core dumped)

This happened after adding -fsplit-lto-unit to some parts of my code base.

[googlebleh]

While bisecting using this reduced test case, I was able to reproduce this crash on several versions of LLVM between 15 and 18.1.8. I was also able to reproduce on the tip of main (e439fdf). However, this crash did not reproduce on 15.0.7. The commit on 15.0.7 that "fixed" the issue is

commit f3c5289e78462fb96015f79c954d95a0d527ba55                                                                        
Author: Martin Storsjö <martin@martin.st>                                                                              
Date:   Wed Oct 5 14:44:21 2022 +0300                                                                                  
                                                                                                                       
    Revert "Recommit "[SCEV] Look through single value PHIs." (take 3)"                                                
                                                                                                                       
    This reverts commit 20d798bd47ec5191de1b2a8a031da06a04e612e1.                                                      
                                                                                                                       
    This commit caused crashes in some cases, see github issue #58152.                                                 
    This is fixed on main, but backporting it requires multiple                                                                                                                                                                               
    nontrivial cherrypicks.                                                                                            
                                                                                                                       
    Updating llvm/test/Transforms/LoopVectorize/create-induction-resume.ll                                             
    with update_test_checks.py, so this isn't an exact automatic revert,                                               
    as that test case was added after the reverted commit.                                                             
                                                                                                                       
    This fixes #58152 for the release branch.                                                                          
                                                                                                                       
 llvm/lib/Analysis/ScalarEvolution.cpp              |  7 ++-
 llvm/test/Analysis/DependenceAnalysis/lcssa.ll     |  2 +-                                                            
 llvm/test/Analysis/ScalarEvolution/cycled_phis.ll  |  4 +-                                                            
 .../ScalarEvolution/incorrect-exit-count.ll        |  2 +-                                                                                                                                                                                   
 .../Analysis/ScalarEvolution/solve-quadratic-i1.ll |  4 +-                                                            
 .../ScalarEvolution/solve-quadratic-overflow.ll    |  6 +--                                                                                                                                                                                  
 llvm/test/Analysis/ScalarEvolution/trivial-phis.ll |  2 +-                                                            
 llvm/test/Transforms/LoopStrengthReduce/funclet.ll | 40 +++++++++-------
 .../LoopVectorize/create-induction-resume.ll       | 24 ++++------
 llvm/test/Transforms/LoopVectorize/pr45259.ll      | 55 +++++++++++-----------
 10 files changed, 75 insertions(+), 71 deletions(-)

specifically, this (almost) 1-line diff

diff --git a/llvm/lib/Analysis/ScalarEvolution.cpp b/llvm/lib/Analysis/ScalarEvolution.cpp
index 4b2db80bc1ec..3b73f9511eca 100644
--- a/llvm/lib/Analysis/ScalarEvolution.cpp
+++ b/llvm/lib/Analysis/ScalarEvolution.cpp
@@ -6023,8 +6023,13 @@ const SCEV *ScalarEvolution::createNodeForPHI(PHINode *PN) {
   if (const SCEV *S = createAddRecFromPHI(PN))
     return S;
 
+  // If the PHI has a single incoming value, follow that value, unless the
+  // PHI's incoming blocks are in a different loop, in which case doing so
+  // risks breaking LCSSA form. Instcombine would normally zap these, but
+  // it doesn't have DominatorTree information, so it may miss cases.
   if (Value *V = simplifyInstruction(PN, {getDataLayout(), &TLI, &DT, &AC}))
-    return getSCEV(V);
+    if (LI.replacementPreservesLCSSAForm(PN, V))
+      return getSCEV(V);
 
   if (const SCEV *S = createNodeFromSelectLikePHI(PN))
     return S;

[nikic]

Reduced:

; RUN: opt -passes="print<scalar-evolution>,loop-unroll" -unroll-runtime
define void @test(i1 %c, ptr %p) {
entry:
  br label %loop

loop:
  %phi = phi ptr [ null, %entry ], [ %p, %loop ]
  %load = load i64, ptr %p, align 8
  %add = add i64 %load, 1
  br i1 %c, label %bb2, label %loop

bb2:
  %add.lcssa = phi i64 [ %add, %loop ]
  %gep = getelementptr i64, ptr %p, i64 %add.lcssa
  br label %loop2

loop2:
  %iv = phi ptr [ %p, %bb2 ], [ %iv.next, %loop2 ]
  %iv.next = getelementptr i8, ptr %iv, i64 8
  %icmp = icmp eq ptr %iv, %gep
  br i1 %icmp, label %exit, label %loop2

exit:
  ret void
}

[nikic]

From a cursory look, the problem here is that the BECount of loop2 depends on %load, and after peeling it should instead depend on a phi node, but instead still depends on %load. As the BECount does not dominate the loop, SCEV is invalid.

This issue sounds very familiar, we've fixed variants of this in the past.