'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?

[RKSimon]

OneUse checks - new nodes are often only created from a pattern of existing nodes if all of those nodes only occur once (i.e. inside that pattern):

or(shl(x,c),srl(x,sub(size-c)) -> rotl(x,c) only occurs if both the shl and the srl have 'oneuse' - ie are only used once each inside the or() pattern - that way we create a rotl node but we also remove a shl and srl node.

[rotateright]

how did this test case, where no shift is presented, ended up as a shifting error?

Multiply/divide by powers-of-2 are strength-reduced to shifts. This is in IR, but we do the same thing in llc (backend):
https://alive2.llvm.org/ce/z/wvkaxX

[RKSimon]

/cherry-pick e624f8a

[llvmbot]

/branch llvm/llvm-project-release-prs/issue57283

[llvmbot]

/pull-request llvm/llvm-project-release-prs#127

[DataCorrupted]

@RKSimon Thanks for the fix. I just found a case where it seems its not 100% fixed. https://llvm.godbolt.org/z/M1r9j7W1c

In your patch, I think you need to move the check for opcode up a little, up before extractShiftForRotate, like this:

  // Something has gone wrong - we've lost the shl/srl pair - bail.
  if (LHSShift.getOpcode() != ISD::SHL || RHSShift.getOpcode() != ISD::SRL)
    return SDValue();
    
  // Have LHS side of the rotate, try to extract the needed shift from the RHS.
  if (LHSShift)
    if (SDValue NewRHSShift =
            extractShiftForRotate(DAG, LHSShift, RHS, RHSMask, DL))
      RHSShift = NewRHSShift;
  // Have RHS side of the rotate, try to extract the needed shift from the LHS.
  if (RHSShift)
    if (SDValue NewLHSShift =
            extractShiftForRotate(DAG, RHSShift, LHS, LHSMask, DL))
      LHSShift = NewLHSShift;

/// The check was below here.

[RKSimon]

@DataCorrupted Did you find any other cases of this? Otherwise I'd like to start refactoring extractShiftForRotate to not create nodes at all and fix this properly, but that will make further cherry picking into 15.x very difficult.

[DataCorrupted]

@DataCorrupted Did you find any other cases of this? Otherwise I'd like to start refactoring extractShiftForRotate to not create nodes at all and fix this properly, but that will make further cherry picking into 15.x very difficult.

My fuzzing process has (unfortunately) stopped sometime ago. If you want I can fuzz the current version for a week and see the result.

But for now, I don't have any other testcases.