clang crashes on valid code at -O1 on x86_64-linux-gnu: Assertion `OldI != E && "Old is not a successor of this block"' failed

[zhendongsu]

It appears to be a recent regression as it doesn't reproduce with 18.1.0 and earlier.

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

[527] % clangtk -v
clang version 19.0.0git (https://github.com/llvm/llvm-project.git 7eae9bb856135136cddc4208a2b1546e9db44c9c)
Target: x86_64-unknown-linux-gnu
Thread model: posix
InstalledDir: /local/suz-local/software/local/clang-trunk/bin
Build config: +assertions
Found candidate GCC installation: /usr/lib/gcc/x86_64-linux-gnu/10
Found candidate GCC installation: /usr/lib/gcc/x86_64-linux-gnu/11
Found candidate GCC installation: /usr/lib/gcc/x86_64-linux-gnu/9
Selected GCC installation: /usr/lib/gcc/x86_64-linux-gnu/11
Candidate multilib: .;@m64
Selected multilib: .;@m64
[528] % 
[528] % clangtk -O1 small.c
clang-19: /local/suz-local/software/clangbuild/llvm-project/llvm/lib/CodeGen/MachineBasicBlock.cpp:879: void llvm::MachineBasicBlock::replaceSuccessor(llvm::MachineBasicBlock*, llvm::MachineBasicBlock*): Assertion `OldI != E && "Old is not a successor of this block"' 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/suz-local/software/local/clang-trunk/bin/clang-19 -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 -fdebug-compilation-dir=/local/suz-local/software/emitesting/bugs/20240710-clangtk-m64-O1-Wall-Wextra-pipe-fPIC-build-184127/delta -fcoverage-compilation-dir=/local/suz-local/software/emitesting/bugs/20240710-clangtk-m64-O1-Wall-Wextra-pipe-fPIC-build-184127/delta -resource-dir /local/suz-local/software/local/clang-trunk/lib/clang/19 -I /usr/local/include -I /local/suz-local/software/local/include -internal-isystem /local/suz-local/software/local/clang-trunk/lib/clang/19/include -internal-isystem /usr/local/include -internal-isystem /usr/lib/gcc/x86_64-linux-gnu/11/../../../../x86_64-linux-gnu/include -internal-externc-isystem /usr/include/x86_64-linux-gnu -internal-externc-isystem /include -internal-externc-isystem /usr/include -O1 -ferror-limit 19 -fgnuc-version=4.2.1 -fskip-odr-check-in-gmf -fcolor-diagnostics -faddrsig -D__GCC_HAVE_DWARF2_CFI_ASM=1 -o /tmp/small-f3a0d6.o -x c small.c
1.	<eof> parser at end of file
2.	Code generation
3.	Running pass 'Function Pass Manager' on module 'small.c'.
4.	Running pass 'Machine code sinking' on function '@main'
 #0 0x0000562a6845059f llvm::sys::PrintStackTrace(llvm::raw_ostream&, int) (/local/suz-local/software/local/clang-trunk/bin/clang-19+0x419c59f)
 #1 0x0000562a6844dae4 SignalHandler(int) Signals.cpp:0:0
 #2 0x00007fed0cef0420 __restore_rt (/lib/x86_64-linux-gnu/libpthread.so.0+0x14420)
 #3 0x00007fed0c92700b raise /build/glibc-LcI20x/glibc-2.31/signal/../sysdeps/unix/sysv/linux/raise.c:51:1
 #4 0x00007fed0c906859 abort /build/glibc-LcI20x/glibc-2.31/stdlib/abort.c:81:7
 #5 0x00007fed0c906729 get_sysdep_segment_value /build/glibc-LcI20x/glibc-2.31/intl/loadmsgcat.c:509:8
 #6 0x00007fed0c906729 _nl_load_domain /build/glibc-LcI20x/glibc-2.31/intl/loadmsgcat.c:970:34
 #7 0x00007fed0c917fd6 (/lib/x86_64-linux-gnu/libc.so.6+0x33fd6)
 #8 0x0000562a67710cb9 llvm::MachineBasicBlock::replaceSuccessor(llvm::MachineBasicBlock*, llvm::MachineBasicBlock*) (/local/suz-local/software/local/clang-trunk/bin/clang-19+0x345ccb9)
 #9 0x0000562a67717650 llvm::MachineBasicBlock::SplitCriticalEdge(llvm::MachineBasicBlock*, llvm::Pass&, std::vector<llvm::SparseBitVector<128u>, std::allocator<llvm::SparseBitVector<128u>>>*) (/local/suz-local/software/local/clang-trunk/bin/clang-19+0x3463650)
#10 0x0000562a6787317c (anonymous namespace)::MachineSinking::runOnMachineFunction(llvm::MachineFunction&) (.part.0) MachineSink.cpp:0:0
#11 0x0000562a677996e5 llvm::MachineFunctionPass::runOnFunction(llvm::Function&) (.part.0) MachineFunctionPass.cpp:0:0
#12 0x0000562a67da68fb llvm::FPPassManager::runOnFunction(llvm::Function&) (/local/suz-local/software/local/clang-trunk/bin/clang-19+0x3af28fb)
#13 0x0000562a67da6b49 llvm::FPPassManager::runOnModule(llvm::Module&) (/local/suz-local/software/local/clang-trunk/bin/clang-19+0x3af2b49)
#14 0x0000562a67da73f5 llvm::legacy::PassManagerImpl::run(llvm::Module&) (/local/suz-local/software/local/clang-trunk/bin/clang-19+0x3af33f5)
#15 0x0000562a687088f8 (anonymous namespace)::EmitAssemblyHelper::EmitAssembly(clang::BackendAction, std::unique_ptr<llvm::raw_pwrite_stream, std::default_delete<llvm::raw_pwrite_stream>>, clang::BackendConsumer*) BackendUtil.cpp:0:0
#16 0x0000562a68708e26 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>>, clang::BackendConsumer*) (/local/suz-local/software/local/clang-trunk/bin/clang-19+0x4454e26)
#17 0x0000562a68d7d66c clang::BackendConsumer::HandleTranslationUnit(clang::ASTContext&) (/local/suz-local/software/local/clang-trunk/bin/clang-19+0x4ac966c)
#18 0x0000562a6ab708ec clang::ParseAST(clang::Sema&, bool, bool) (/local/suz-local/software/local/clang-trunk/bin/clang-19+0x68bc8ec)
#19 0x0000562a68d7da78 clang::CodeGenAction::ExecuteAction() (/local/suz-local/software/local/clang-trunk/bin/clang-19+0x4ac9a78)
#20 0x0000562a69012da9 clang::FrontendAction::Execute() (/local/suz-local/software/local/clang-trunk/bin/clang-19+0x4d5eda9)
#21 0x0000562a68f9554e clang::CompilerInstance::ExecuteAction(clang::FrontendAction&) (/local/suz-local/software/local/clang-trunk/bin/clang-19+0x4ce154e)
#22 0x0000562a690fec46 clang::ExecuteCompilerInvocation(clang::CompilerInstance*) (/local/suz-local/software/local/clang-trunk/bin/clang-19+0x4e4ac46)
#23 0x0000562a655a6ef5 cc1_main(llvm::ArrayRef<char const*>, char const*, void*) (/local/suz-local/software/local/clang-trunk/bin/clang-19+0x12f2ef5)
#24 0x0000562a6559ff0a ExecuteCC1Tool(llvm::SmallVectorImpl<char const*>&, llvm::ToolContext const&) driver.cpp:0:0
#25 0x0000562a655a38de clang_main(int, char**, llvm::ToolContext const&) (/local/suz-local/software/local/clang-trunk/bin/clang-19+0x12ef8de)
#26 0x0000562a65496dfb main (/local/suz-local/software/local/clang-trunk/bin/clang-19+0x11e2dfb)
#27 0x00007fed0c908083 __libc_start_main /build/glibc-LcI20x/glibc-2.31/csu/../csu/libc-start.c:342:3
#28 0x0000562a6559f99e _start (/local/suz-local/software/local/clang-trunk/bin/clang-19+0x12eb99e)
clangtk: error: unable to execute command: Aborted
clangtk: error: clang frontend command failed due to signal (use -v to see invocation)
clang version 19.0.0git (https://github.com/llvm/llvm-project.git 7eae9bb856135136cddc4208a2b1546e9db44c9c)
Target: x86_64-unknown-linux-gnu
Thread model: posix
InstalledDir: /local/suz-local/software/local/clang-trunk/bin
Build config: +assertions
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-8058d2.c
clangtk: note: diagnostic msg: /tmp/small-8058d2.sh
clangtk: note: diagnostic msg: 

********************
[529] % 
[529] % cat small.c
int a, b, c, d, e, f;
volatile int g;
int main() {
  int h = 1, i, k;
  if (a) {
    i = 0;
  j:
    i = f;
    f = ~(-1 % (g % 3 / 2));
    k = g / h;
    if (c || b <= c) {
      b = h = ~(-1 % k);
      if (d)
        goto j;
    }
    while (h)
      b = ~f / i;
  }
  if (e)
    goto j;
  return 0;
}

[dtcxzyw]

Reproducer:

; bin/llc test.ll
target datalayout = "e-m:e-p270:32:32-p271:32:32-p272:64:64-i64:64-i128:128-f80:128-n8:16:32:64-S128"
target triple = "x86_64-unknown-linux-gnu"

define i32 @main(i1 %tobool.not, i32 %0) {
entry:
  br i1 %tobool.not, label %if.end13, label %j.preheader

j.preheader:                                      ; preds = %if.end13, %entry
  %h.0.ph = phi i32 [ 1, %entry ], [ 0, %if.end13 ]
  br label %j

j:                                                ; preds = %if.then4, %j.preheader
  %1 = phi i32 [ %div2, %if.then4 ], [ 0, %j.preheader ]
  %rem1 = srem i32 1, %0
  %cmp = icmp slt i32 %1, 0
  %or.cond = select i1 false, i1 true, i1 %cmp
  br i1 %or.cond, label %if.then4, label %if.end9

if.then4:                                         ; preds = %j
  %div2 = sdiv i32 1, 0
  %rem5 = srem i32 1, %h.0.ph
  br i1 %tobool.not, label %if.end9, label %j

if.end9:                                          ; preds = %if.then4, %j
  %2 = phi i32 [ 0, %j ], [ %rem5, %if.then4 ]
  %tobool10.not = icmp eq i32 %2, 0
  br i1 %tobool10.not, label %if.end13, label %while.body.lr.ph

while.body.lr.ph:                                 ; preds = %if.end9
  ret i32 %rem1

if.end13:                                         ; preds = %if.end9, %entry
  br label %j.preheader
}

Reverting 7e2f961 fixes this issue.
cc @mshockwave @wangpc-pp