'X86 DAG->DAG Instruction Selection' assertion failure

[DataCorrupted]

When fuzzing x86_64 we found a module that will trigger an assertion failure.

Seems like this is a newly introduced bug. LLVM14.0.0 compiles correctly, but crashes on latest commit cfd2c5ce580f

; ModuleID = 'x86-dag.bc'
source_filename = "M"

define void @f() {
BB:
  %A6 = alloca i64, align 8
  %A = alloca i64, align 8
  %L = load i64, i64* %A, align 4
  %B3 = sub i64 %L, %L
  %B2 = mul i64 %B3, 4294967296
  %B1 = add i64 %B2, %B2
  %B4 = udiv i64 %B2, -9223372036854775808
  %B = xor i64 %B1, %B4
  store i64 %B, i64* %A, align 4
  %B5 = sdiv i64 %B, -1
  store i64 %B5, i64* %A6, align 4
  ret void
}

llc: /home/peter/aflplusplus-isel/llvm-project/llvm/include/llvm/CodeGen/SelectionDAGNodes.h:913: const llvm::SDValue &llvm::SDNode::getOperand(unsigned int) const: Assertion `Num < NumOperands && "Invalid child # of SDNode!"' failed.
PLEASE submit a bug report to https://github.com/llvm/llvm-project/issues/ and include the crash backtrace.
Stack dump:
0.      Program arguments: /home/peter/aflplusplus-isel/llvm-project/build-debug/bin/llc x86-dag.bc
1.      Running pass 'Function Pass Manager' on module 'x86-dag.bc'.
2.      Running pass 'X86 DAG->DAG Instruction Selection' on function '@f'
 #0 0x00000000030fb20a llvm::sys::PrintStackTrace(llvm::raw_ostream&, int) /home/peter/aflplusplus-isel/llvm-project/llvm/lib/Support/Unix/Signals.inc:569:11
 #1 0x00000000030fb3bb PrintStackTraceSignalHandler(void*) /home/peter/aflplusplus-isel/llvm-project/llvm/lib/Support/Unix/Signals.inc:636:1
 #2 0x00000000030f9a06 llvm::sys::RunSignalHandlers() /home/peter/aflplusplus-isel/llvm-project/llvm/lib/Support/Signals.cpp:103:5
 #3 0x00000000030fbae5 SignalHandler(int) /home/peter/aflplusplus-isel/llvm-project/llvm/lib/Support/Unix/Signals.inc:407:1
 #4 0x00007f5c34e1d980 __restore_rt (/lib/x86_64-linux-gnu/libpthread.so.0+0x12980)
 #5 0x00007f5c33d0de87 raise /build/glibc-uZu3wS/glibc-2.27/signal/../sysdeps/unix/sysv/linux/raise.c:51:0
 #6 0x00007f5c33d0f7f1 abort /build/glibc-uZu3wS/glibc-2.27/stdlib/abort.c:81:0
 #7 0x00007f5c33cff3fa __assert_fail_base /build/glibc-uZu3wS/glibc-2.27/assert/assert.c:89:0
 #8 0x00007f5c33cff472 (/lib/x86_64-linux-gnu/libc.so.6+0x30472)
 #9 0x0000000000ebf719 llvm::SDNode::getOperand(unsigned int) const /home/peter/aflplusplus-isel/llvm-project/llvm/include/llvm/CodeGen/SelectionDAGNodes.h:0:5
#10 0x0000000000ec127e llvm::SDValue::getOperand(unsigned int) const /home/peter/aflplusplus-isel/llvm-project/llvm/include/llvm/CodeGen/SelectionDAGNodes.h:1138:3
#11 0x0000000002c94558 (anonymous namespace)::DAGCombiner::MatchRotate(llvm::SDValue, llvm::SDValue, llvm::SDLoc const&) /home/peter/aflplusplus-isel/llvm-project/llvm/lib/CodeGen/SelectionDAG/DAGCombiner.cpp:7646:25
#12 0x0000000002c338c3 (anonymous namespace)::DAGCombiner::visitOR(llvm::SDNode*) /home/peter/aflplusplus-isel/llvm-project/llvm/lib/CodeGen/SelectionDAG/DAGCombiner.cpp:7161:21
#13 0x0000000002c1b0d0 (anonymous namespace)::DAGCombiner::visit(llvm::SDNode*) /home/peter/aflplusplus-isel/llvm-project/llvm/lib/CodeGen/SelectionDAG/DAGCombiner.cpp:1721:40
#14 0x0000000002c1a788 (anonymous namespace)::DAGCombiner::combine(llvm::SDNode*) /home/peter/aflplusplus-isel/llvm-project/llvm/lib/CodeGen/SelectionDAG/DAGCombiner.cpp:1826:10
#15 0x0000000002c19d96 (anonymous namespace)::DAGCombiner::Run(llvm::CombineLevel) /home/peter/aflplusplus-isel/llvm-project/llvm/lib/CodeGen/SelectionDAG/DAGCombiner.cpp:1624:18
#16 0x0000000002c1967f llvm::SelectionDAG::Combine(llvm::CombineLevel, llvm::AAResults*, llvm::CodeGenOpt::Level) /home/peter/aflplusplus-isel/llvm-project/llvm/lib/CodeGen/SelectionDAG/DAGCombiner.cpp:25147:3
#17 0x0000000002e74baf llvm::SelectionDAGISel::CodeGenAndEmitDAG() /home/peter/aflplusplus-isel/llvm-project/llvm/lib/CodeGen/SelectionDAG/SelectionDAGISel.cpp:769:3
#18 0x0000000002e7475d llvm::SelectionDAGISel::SelectBasicBlock(llvm::ilist_iterator<llvm::ilist_detail::node_options<llvm::Instruction, true, false, void>, false, true>, llvm::ilist_iterator<llvm::ilist_detail::node_options<llvm::Instruction, true, false, void>, false, true>, bool&) /home/peter/aflplusplus-isel/llvm-project/llvm/lib/CodeGen/SelectionDAG/SelectionDAGISel.cpp:685:1
#19 0x0000000002e741fb llvm::SelectionDAGISel::SelectAllBasicBlocks(llvm::Function const&) /home/peter/aflplusplus-isel/llvm-project/llvm/lib/CodeGen/SelectionDAG/SelectionDAGISel.cpp:1591:11
#20 0x0000000002e7179d llvm::SelectionDAGISel::runOnMachineFunction(llvm::MachineFunction&) /home/peter/aflplusplus-isel/llvm-project/llvm/lib/CodeGen/SelectionDAG/SelectionDAGISel.cpp:464:3
#21 0x0000000000e8d18a (anonymous namespace)::X86DAGToDAGISel::runOnMachineFunction(llvm::MachineFunction&) /home/peter/aflplusplus-isel/llvm-project/llvm/lib/Target/X86/X86ISelDAGToDAG.cpp:191:7
#22 0x0000000001e9326d llvm::MachineFunctionPass::runOnFunction(llvm::Function&) /home/peter/aflplusplus-isel/llvm-project/llvm/lib/CodeGen/MachineFunctionPass.cpp:85:8
#23 0x00000000025a2256 llvm::FPPassManager::runOnFunction(llvm::Function&) /home/peter/aflplusplus-isel/llvm-project/llvm/lib/IR/LegacyPassManager.cpp:1430:23
#24 0x00000000025a7082 llvm::FPPassManager::runOnModule(llvm::Module&) /home/peter/aflplusplus-isel/llvm-project/llvm/lib/IR/LegacyPassManager.cpp:1476:16
#25 0x00000000025a2b29 (anonymous namespace)::MPPassManager::runOnModule(llvm::Module&) /home/peter/aflplusplus-isel/llvm-project/llvm/lib/IR/LegacyPassManager.cpp:1545:23
#26 0x00000000025a269d llvm::legacy::PassManagerImpl::run(llvm::Module&) /home/peter/aflplusplus-isel/llvm-project/llvm/lib/IR/LegacyPassManager.cpp:535:16
#27 0x00000000025a7361 llvm::legacy::PassManager::run(llvm::Module&) /home/peter/aflplusplus-isel/llvm-project/llvm/lib/IR/LegacyPassManager.cpp:1672:3
#28 0x0000000000c744b0 compileModule(char**, llvm::LLVMContext&) /home/peter/aflplusplus-isel/llvm-project/llvm/tools/llc/llc.cpp:737:41
#29 0x0000000000c72832 main /home/peter/aflplusplus-isel/llvm-project/llvm/tools/llc/llc.cpp:418:13
#30 0x00007f5c33cf0c87 __libc_start_main /build/glibc-uZu3wS/glibc-2.27/csu/../csu/libc-start.c:344:0
#31 0x0000000000c7203a _start (/home/peter/aflplusplus-isel/llvm-project/build-debug/bin/llc+0xc7203a)
Aborted

[llvmbot]

@llvm/issue-subscribers-backend-x86

[fhahn]

Godbolt: https://llvm.godbolt.org/z/T6vh17s9z

[phoebewang]

I found the problem is MatchRotate expects both are shift, but getNode returns a constant node due to optimization.
I saw @RKSimon had a comment about it. Could canonicalization solve this problem?

[RKSimon]

Its a shame that extractShiftForRotate creates node at all - as well as constant folding it can also create multiuses in a place where we have a lot of OneUse checks and its not even guaranteed they will be used....

To prevent the crash it's probably best that initially we just bail if MatchRotate doesn't find a SHL/SRL pair.

[RKSimon]

I'll leave this to brew for 24 hours then request a cherry pick for 15.x

[DataCorrupted]

Thanks for fixing it so fast! Really appreciate it!.

OneUse checks

However, I am fairly new to x86 backend, would you explain a bit more what is "OneUse checks" and how did this test case, where no shift is presented, ended up as a shifting error?