clang crashes on valid code at -O{2,3} on x86_64-linux-gnu: Assertion `N->getOpcode() != ISD::DELETED_NODE && "DELETED_NODE in CSEMap!"' failed

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

Note:
- fails: trunk
- works: 22.1.0 and earlier
- difficult to reduce, so the reduced code is still fairly large and messy

```
[512] % clangtk -v
clang version 23.0.0git (https://github.com/llvm/llvm-project.git a99dd8344ea9ff92d2d12b056942542d17d9895c)
Target: x86_64-unknown-linux-gnu
Thread model: posix
InstalledDir: /local/home/suz/suz-local/software/local/clang-trunk/bin
Build config: +assertions
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
Candidate multilib: 32;@m32
Candidate multilib: x32;@mx32
Selected multilib: .;@m64
Found CUDA installation: /usr/local/cuda, version 12.1
[513] %
[513] % clangtk -w -O3 small.c
clang-23: /local/suz-local/software/clangbuild/llvm-project/llvm/lib/CodeGen/SelectionDAG/SelectionDAG.cpp:1301: bool llvm::SelectionDAG::RemoveNodeFromCSEMaps(llvm::SDNode*): Assertion `N->getOpcode() != ISD::DELETED_NODE && "DELETED_NODE in CSEMap!"' 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-23 -cc1 -triple x86_64-unknown-linux-gnu -O3 -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/20260421-clangtk-m64-O3-build-120912/delta -fcoverage-compilation-dir=/local/suz-local/software/emitesting/bugs/20260421-clangtk-m64-O3-build-120912/delta -resource-dir /local/home/suz/suz-local/software/local/clang-trunk/lib/clang/23 -I /usr/local/include -I /local/suz-local/software/local/include -internal-isystem /local/home/suz/suz-local/software/local/clang-trunk/lib/clang/23/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 -w -ferror-limit 19 -fmessage-length=130 -fgnuc-version=4.2.1 -fskip-odr-check-in-gmf -fcolor-diagnostics -vectorize-loops -vectorize-slp -faddrsig -fdwarf2-cfi-asm -o /tmp/small-9ab4fd.o -x c small.c
1. parser at end of file
2. Code generation
3. Running pass 'Function Pass Manager' on module 'small.c'.
4. Running pass 'X86 DAG->DAG Instruction Selection' on function '@main'
#0 0x00005588f7095310 llvm::sys::PrintStackTrace(llvm::raw_ostream&, int) (/local/home/suz/suz-local/software/local/clang-trunk/bin/clang-23+0x4662310)
#1 0x00005588f7091edc llvm::sys::RunSignalHandlers() (/local/home/suz/suz-local/software/local/clang-trunk/bin/clang-23+0x465eedc)
#2 0x00005588f7092042 SignalHandler(int, siginfo_t*, void*) Signals.cpp:0:0
#3 0x00005588f70920fc SignalHandlerTerminate(int, siginfo_t*, void*) Signals.cpp:0:0
#4 0x00007fdc34922520 (/lib/x86_64-linux-gnu/libc.so.6+0x42520)
#5 0x00007fdc349769fc __pthread_kill_implementation ./nptl/pthread_kill.c:44:76
#6 0x00007fdc349769fc __pthread_kill_internal ./nptl/pthread_kill.c:78:10
#7 0x00007fdc349769fc pthread_kill ./nptl/pthread_kill.c:89:10
#8 0x00007fdc34922476 gsignal ./signal/../sysdeps/posix/raise.c:27:6
#9 0x00007fdc349087f3 abort ./stdlib/abort.c:81:7
#10 0x00007fdc3490871b _nl_load_domain ./intl/loadmsgcat.c:1177:9
#11 0x00007fdc34919e96 (/lib/x86_64-linux-gnu/libc.so.6+0x39e96)
#12 0x00005588f87b9c3c llvm::SelectionDAG::RemoveNodeFromCSEMaps(llvm::SDNode*) (/local/home/suz/suz-local/software/local/clang-trunk/bin/clang-23+0x5d86c3c)
#13 0x00005588f87b9e06 llvm::SelectionDAG::DeleteNode(llvm::SDNode*) (/local/home/suz/suz-local/software/local/clang-trunk/bin/clang-23+0x5d86e06)
#14 0x00005588f8673a9c (anonymous namespace)::DAGCombiner::CombineTo(llvm::SDNode*, llvm::SDValue const*, unsigned int, bool) (.constprop.1) DAGCombiner.cpp:0:0
#15 0x00005588f86b4fa9 tryToFoldExtOfLoad(llvm::SelectionDAG&, (anonymous namespace)::DAGCombiner&, llvm::TargetLowering const&, llvm::EVT, bool, llvm::SDNode*, llvm::SDValue, llvm::ISD::LoadExtType, llvm::ISD::NodeType, bool) DAGCombiner.cpp:0:0
#16 0x00005588f86b8109 (anonymous namespace)::DAGCombiner::visitZERO_EXTEND(llvm::SDNode*) DAGCombiner.cpp:0:0
#17 0x00005588f86d737b (anonymous namespace)::DAGCombiner::combine(llvm::SDNode*) DAGCombiner.cpp:0:0
#18 0x00005588f86d8ebd llvm::SelectionDAG::Combine(llvm::CombineLevel, llvm::BatchAAResults*, llvm::CodeGenOptLevel) (/local/home/suz/suz-local/software/local/clang-trunk/bin/clang-23+0x5ca5ebd)
#19 0x00005588f88339eb llvm::SelectionDAGISel::CodeGenAndEmitDAG() (/local/home/suz/suz-local/software/local/clang-trunk/bin/clang-23+0x5e009eb)
#20 0x00005588f88373f5 llvm::SelectionDAGISel::SelectAllBasicBlocks(llvm::Function const&) (/local/home/suz/suz-local/software/local/clang-trunk/bin/clang-23+0x5e043f5)
#21 0x00005588f8838d23 llvm::SelectionDAGISel::runOnMachineFunction(llvm::MachineFunction&) (/local/home/suz/suz-local/software/local/clang-trunk/bin/clang-23+0x5e05d23)
#22 0x00005588f8830959 llvm::SelectionDAGISelLegacy::runOnMachineFunction(llvm::MachineFunction&) (/local/home/suz/suz-local/software/local/clang-trunk/bin/clang-23+0x5dfd959)
#23 0x00005588f62a236b llvm::MachineFunctionPass::runOnFunction(llvm::Function&) (.part.0) MachineFunctionPass.cpp:0:0
#24 0x00005588f69417f3 llvm::FPPassManager::runOnFunction(llvm::Function&) (/local/home/suz/suz-local/software/local/clang-trunk/bin/clang-23+0x3f0e7f3)
#25 0x00005588f6941c49 llvm::FPPassManager::runOnModule(llvm::Module&) (/local/home/suz/suz-local/software/local/clang-trunk/bin/clang-23+0x3f0ec49)
#26 0x00005588f6942597 llvm::legacy::PassManagerImpl::run(llvm::Module&) (/local/home/suz/suz-local/software/local/clang-trunk/bin/clang-23+0x3f0f597)
#27 0x00005588f74d79aa clang::emitBackendOutput(clang::CompilerInstance&, clang::CodeGenOptions&, llvm::StringRef, llvm::Module*, clang::BackendAction, llvm::IntrusiveRefCntPtr, std::unique_ptr>, clang::BackendConsumer*) (/local/home/suz/suz-local/software/local/clang-trunk/bin/clang-23+0x4aa49aa)
#28 0x00005588f7bb7302 clang::BackendConsumer::HandleTranslationUnit(clang::ASTContext&) (/local/home/suz/suz-local/software/local/clang-trunk/bin/clang-23+0x5184302)
#29 0x00005588f96d473c clang::ParseAST(clang::Sema&, bool, bool) (/local/home/suz/suz-local/software/local/clang-trunk/bin/clang-23+0x6ca173c)
#30 0x00005588f7f0b629 clang::FrontendAction::Execute() (/local/home/suz/suz-local/software/local/clang-trunk/bin/clang-23+0x54d8629)
#31 0x00005588f7e85338 clang::CompilerInstance::ExecuteAction(clang::FrontendAction&) (/local/home/suz/suz-local/software/local/clang-trunk/bin/clang-23+0x5452338)
#32 0x00005588f8007b03 clang::ExecuteCompilerInvocation(clang::CompilerInstance*) (/local/home/suz/suz-local/software/local/clang-trunk/bin/clang-23+0x55d4b03)
#33 0x00005588f397ef1a cc1_main(llvm::ArrayRef, char const*, void*) (/local/home/suz/suz-local/software/local/clang-trunk/bin/clang-23+0xf4bf1a)
#34 0x00005588f397495a ExecuteCC1Tool(llvm::SmallVectorImpl&, llvm::ToolContext const&, llvm::IntrusiveRefCntPtr) driver.cpp:0:0
#35 0x00005588f3978d1e clang_main(int, char**, llvm::ToolContext const&) (/local/home/suz/suz-local/software/local/clang-trunk/bin/clang-23+0xf45d1e)
#36 0x00005588f383da61 main (/local/home/suz/suz-local/software/local/clang-trunk/bin/clang-23+0xe0aa61)
#37 0x00007fdc34909d90 __libc_start_call_main ./csu/../sysdeps/nptl/libc_start_call_main.h:58:16
#38 0x00007fdc34909e40 call_init ./csu/../csu/libc-start.c:128:20
#39 0x00007fdc34909e40 __libc_start_main ./csu/../csu/libc-start.c:379:5
#40 0x00005588f3974075 _start (/local/home/suz/suz-local/software/local/clang-trunk/bin/clang-23+0xf41075)
clangtk: error: unable to execute command: Aborted
clangtk: error: clang frontend command failed with exit code -2 (use -v to see invocation)
clang version 23.0.0git (https://github.com/llvm/llvm-project.git a99dd8344ea9ff92d2d12b056942542d17d9895c)
Target: x86_64-unknown-linux-gnu
Thread model: posix
InstalledDir: /local/home/suz/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-f055ed.c
clangtk: note: diagnostic msg: /tmp/small-f055ed.sh
clangtk: note: diagnostic msg:

********************
Aborted
```

```c
int printf(const char *, ...);
int d, a, q, u, b, i, l, aa, ab, ac, ad, ae, af;
short m, t, w, c, e, x, ag, ah, ai, aj, ak, al;
long n, o, g, am;
long long p, an, ao;
volatile short s;
volatile short r;
unsigned v, f, ap, aq, ar;
char y, h, k, as, at, au, av;
volatile short j;
volatile unsigned aw;
volatile short ax;
volatile char ay;
volatile short az;
volatile char ba;
volatile unsigned bb;
void(bc)(char b, char c) {}
void(bd)(short f) { d = 2; }
void(be)(long b) {}
void(bf)(short i) {}
void(bg)(short i, short k) {}
void(bh)(long i) {}
void bi(char x) {}
int main() {
if (!a)
return 0;
short bk, bl = an % ak / l, bm = t / v - ap,
bn = ao - h & as | au ^ v & q - ar ^ ax ^ m,
bo = ay - y & p | al | a - ag - m | az;
int bp = a | f & e, bq = al, br = ab / n, bs = ar - ao | h - q | ax - m,
bt = ag & p & m | a | y ^ al;
long bu = ac;
int bv = bl <= bb;
char bw = f / ah & b, bx = h | ao | au & as ^ q - v ^ ar;
short by = bw | av;
if (k >= 6) {
ab = v;
k = f / ah ^ ap & n | k | t / b;
t = ap | av - t - ah | ab;
ap = f - v ^ ab / ap / n / av;
bz:
ah = ah / b - t - av ^ ab ^ ap | v;
n = b & ap - f | k / v & by & av | n | t;
av = ah ^ k ^ b & v / t | f;
v = n | v | b - ap;
if (f > 4)
goto ca;
printf("g_138=%llu\n", (long long)t);
cb:
if (ab || av)
goto bz;
if (ah && f)
if (br <= n)
if (bm <= ap) {
printf("g_115=%llu\n", (long long)v);
goto cc;
}
}
af = ac;
al = ak;
bu = an;
bv = a;
d = f % l & e;
ak = f ^ an ^ l & ac >> ak | e;
an = bp / l >> an & d & ac / f;
if (d <= 4294967295)
bk = d & ak & l & a / f;
l = ak & d ^ f / al;
long cd = (p | x) * c | ag ^ t * an | v % j | w;
short ce = (p & (c ^ v) || x | t) | (aj | ag % j) ^ (w | an);
unsigned cf = j * an * ce * c | w | aj ^ t;
short cg = ag % p | v & cd & x;
short ch = an * j | cg ^ ((c || cd) | t);
short ci = an & v ^ aj || cg | w | x;
long cj = x | ag || an % p || t & c;
if (aj <= v || p || x) {
cd = an;
while (!ah)
;
ce = ag;
long ck = an | ak - s - h ^ l - aq ^ (ar | ba) & ao;
unsigned char cl =
at >> ba | -s - (ao & an ^ -h ^ -ak) & aq & ~(~l & ar & ck);
char cm =
~(-s ^ -~ba & ~ar ^ ao ^ h ^ ak & ~cl - (-aq & (at ^ ~an & ck) - l));
int cn = ~((~(ao & ck ^ s & cm << ba) & ~aq) -
((ar & h << at) - (~ak ^ an | cl)));
short co = ao - cm ^ ba, cp = l ^ ak | cn, cq = ap | ba ^ o - q ^ w;
int cr = cp & ck ^ ar & cl;
l = co;
aq = cp;
if (!aq)
goto cs;
aq = cr;
ct:
cj = p;
an = an || t * v;
ag = p;
ca:
v = (ag || t) % an * p & aj || c;
t = an & p >> c || t * aj;
x = ag ^ c | ci < p & w & v;
long cu = q ^ e ^ o & w - ap - r;
short cv = e | q ^ ap ^ w ^ o;
int cw = ba - q & ap ^ o | w | j | e;
int cx = o & cv ^ r - w ^ ap ^ q;
char cy = e > j & ae ^ ap - o - cw;
int cz = r ^ ap & e | o - q | j & w;
short z = e - ap | o & cz - q | r ^ w;
if (cy) {
z = e;
cq = ap;
o = ba ^ w ^ ap ^ e - j - cx ^ e ^ o;
aw = q & w & ap;
ae = q & o;
ba = j | ap - o & q;
q = w | ba & q;
e = w ^ o ^ ap;
ap = o | w - q & ap;
if (!(o && q))
goto cb;
if (w)
j;
if (o) {
q = ba & o | e | q - w;
goto ct;
}
if (j) {
printf("g_113=%lld\n", (long long)q);
cu = q & ap - w < e;
}
printf("g_206=%lld\n", (long long)e, ap);
}
o = cu;
d = z;
ap = cq;
w = t & ag ^ an;
c = v || an * p || t;
if (aa)
v |= t;
p = p ^ x ^ v % t % c ^ w * ag;
if (v)
printf("g_382=%llu\n", an);
cf = an | p & w ^ x % d & t;
ch = j > w | d ^ p ^ x;
printf("g_259=%lld\n", (long long)ag);
x || ~~~ag;
cc:
if (t) {
printf("g_115=%llu\n", (long long)v);
printf("g_138=%llu\n", (long long)t);
cj = cf & t;
}
if (ch || v)
printf("g_256=%llu\n", (long long)bc);
if (v && ce)
printf("g_97=%llu\n", p);
}
while (u || (ai = h && aa) && i)
an = cd;
if (w)
if (aa)
ak ^= 8;
p = cj;
d = e % an | ac % f;
if (q)
bh(a);
bg(g, a & h);
bd(h);
bc(g && ak, i);
a = e >> f & bu % a | l;
if (ak) {
printf("l_5=%lld\n", (long long)d ^ l);
bq = ak ^ d | an & f;
}
if (f <= ak)
printf("g_1087=%llu\n", (long long)d);
d = d ^ an | ak ^ ac & l;
d = an bq;
ae = ap;
printf("g_1134=%lld\n", (long long)ak);
be(am & 1);
ab = 0;
bf(am);
aa = am ^ n;
bp = l >> d | ac;
e = f ^ a % bk | bp;
an = a / d % an & ak;
if (a) {
ad = ak ^ d;
l = an < ac;
}
if (ak)
a = f | ac < d | l;
bp = d & l & ak;
short da = ax - au ^ as ^ ao | ar - v | q ^ h;
short db = aw | v - h | au & ar & q - ao;
int dc = as & m & ax & bn & ao - v ^ q ^ au;
long dd = da & m & ax | q & ao - au ^ as > aw;
char de = au & v ^ bx & dd | dc ^ db & m - as - h;
if (ao)
aw;
dd = ao;
ai = v & ai - au & q - as;
aw = m | au | as - v ^ ao;
as = ar | q ^ m ^ v - ao ^ au;
m = ai ^ v | ao | ax | as & m & q | ar;
ax = v | ar - ao & q ^ au;
ar = ao - dd - ai - au ^ ar & m;
ao = au | v - ao | m ^ as;
v = au ^ as - v & q | ai - m;
if (q)
printf("g_1060=%lld\n", (long long)ai);
ao = m | q - as & v > ai;
ax = au - v > m & ar - q & ai;
ar = bs & m > v | ai ^ q | au | as;
if (v)
if (ao <= au)
printf("g_304=%llu\n", (long long)as);
if (as)
printf("g_452=%lld\n", ao);
if (m)
printf("g_115=%llu\n", (long long)v);
v = de;
printf("g_250=%lld\n", (long long)l);
an = l / d & a % ak;
if (ah) {
printf("g_206=%lld\n", (long long)d);
al = l % bv | a ^ d > ak % an;
}
if (a && bp)
ak = al;
char df = ag ^ a & p | m & ay;
short dg = m | a - p | al | bt;
long dh = ag - bo & ay - df ^ al | p ^ a / y;
az;
if (a && ag || p && !(dh && al)) {
d = a;
dg = m;
dh = p;
cs:
ay = y / dh | p ^ ag ^ a / al;
a = m | p - a / al;
az = ag | p / d | ap & m;
printf("g_259=%lld\n", (long long)ag);
}
m = dg;
a ^= u |= v;
g = f;
ag ^= as |= w;
for (; t; t++)
ai ^= au |= am != b;
bi(al);
for (; ap;)
;
return n;
}
```

Start by reproducing the crash with clang -w -O3 small.c for x86_64-linux-gnu, using the linked Compiler Explorer case and the reported preprocessed source if needed. Read llvm/lib/CodeGen/SelectionDAG/SelectionDAG.cpp around RemoveNodeFromCSEMaps and the DAGCombiner.cpp paths tryToFoldExtOfLoad and visitZERO_EXTEND. Done means valid code no longer triggers the assertion and a regression test covers the failure.

Written by the indexing model from the issue text.