search

llvm / llvm-project

The LLVM Project is a collection of modular and reusable compiler and toolchain technologies.
http://llvm.org
Other
29.04k stars 11.98k forks source link

[PowerPC] Backend crash due to index out of bound when `lshr` / `shl` i128 vector after `sub` #59074

Closed HazyFish closed 9 months ago

HazyFish commented 1 year ago

Description

When targeting ppc64, ppc32, or ppc32le, the following code containing i128 vector shift crashes backend due to index being out of bound during PowerPC DAG->DAG Pattern Instruction Selection.

The problem occurs for lshr and shl but not for ashr. The problem occurs for sub but not for add and the result of sub must be used as the shift amount operand. The problem doesn't occur for i64 vectors. The problem doesn't occur when targeting ppc64le, aarch64, x86_64, or riscv64.

Minimal Reproduction

https://godbolt.org/z/vW4YT3Ga7

Code

define void @f(ptr %0) {
BB:
  %V1 = load <2 x i128>, <2 x i128>* %0
  %V2 = insertelement <2 x i128> %V1, i128 12, i32 0
  %V3 = sub <2 x i128> %V1, %V2
  %V4 = lshr <2 x i128> %V2, %V3
  store <2 x i128> %V4, <2 x i128>* %0
  ret void
}

Stack Trace

llc: /home/henry/aflplusplus-isel/llvm-project/llvm/include/llvm/ADT/SmallVector.h:298: llvm::SmallVectorTemplateCommon::const_reference llvm::SmallVectorTemplateCommon<(anonymous namespace)::BitPermutationSelector::ValueBit>::operator[](llvm::SmallVectorTemplateCommon::size_type) const [T = (anonymous namespace)::BitPermutationSelector::ValueBit]: Assertion `idx < size()' failed.
PLEASE submit a bug report to https://github.com/llvm/llvm-project/issues/ and include the crash backtrace.
Stack dump:
0.  Program arguments: ./llvm-project/build-debug/bin/llc -mtriple=ppc64 ./crash-reports/dagisel-ppc64/1.ll
1.  Running pass 'Function Pass Manager' on module './crash-reports/dagisel-ppc64/1.ll'.
2.  Running pass 'PowerPC DAG->DAG Pattern Instruction Selection' on function '@f'
 #0 0x00000000047db7da llvm::sys::PrintStackTrace(llvm::raw_ostream&, int) /home/henry/aflplusplus-isel/llvm-project/llvm/lib/Support/Unix/Signals.inc:569:11
 #1 0x00000000047db98b PrintStackTraceSignalHandler(void*) /home/henry/aflplusplus-isel/llvm-project/llvm/lib/Support/Unix/Signals.inc:636:1
 #2 0x00000000047d9fc6 llvm::sys::RunSignalHandlers() /home/henry/aflplusplus-isel/llvm-project/llvm/lib/Support/Signals.cpp:104:5
 #3 0x00000000047dc0b5 SignalHandler(int) /home/henry/aflplusplus-isel/llvm-project/llvm/lib/Support/Unix/Signals.inc:407:1
 #4 0x00007f3802601980 __restore_rt (/lib/x86_64-linux-gnu/libpthread.so.0+0x12980)
 #5 0x00007f38014f1e87 raise /build/glibc-CVJwZb/glibc-2.27/signal/../sysdeps/unix/sysv/linux/raise.c:51:0
 #6 0x00007f38014f37f1 abort /build/glibc-CVJwZb/glibc-2.27/stdlib/abort.c:81:0
 #7 0x00007f38014e33fa __assert_fail_base /build/glibc-CVJwZb/glibc-2.27/assert/assert.c:89:0
 #8 0x00007f38014e3472 (/lib/x86_64-linux-gnu/libc.so.6+0x30472)
 #9 0x000000000217ced9 llvm::SmallVectorTemplateCommon<(anonymous namespace)::BitPermutationSelector::ValueBit, void>::operator[](unsigned long) const /home/henry/aflplusplus-isel/llvm-project/llvm/include/llvm/ADT/SmallVector.h:0:5
#10 0x000000000217b0ba (anonymous namespace)::BitPermutationSelector::getValueBits(llvm::SDValue, unsigned int) /home/henry/aflplusplus-isel/llvm-project/llvm/lib/Target/PowerPC/PPCISelDAGToDAG.cpp:1507:21
#11 0x000000000217b469 (anonymous namespace)::BitPermutationSelector::getValueBits(llvm::SDValue, unsigned int) /home/henry/aflplusplus-isel/llvm-project/llvm/lib/Target/PowerPC/PPCISelDAGToDAG.cpp:1543:30
#12 0x0000000002179acc (anonymous namespace)::BitPermutationSelector::Select(llvm::SDNode*) /home/henry/aflplusplus-isel/llvm-project/llvm/lib/Target/PowerPC/PPCISelDAGToDAG.cpp:2674:9
#13 0x0000000002170d66 (anonymous namespace)::PPCDAGToDAGISel::tryBitPermutation(llvm::SDNode*) /home/henry/aflplusplus-isel/llvm-project/llvm/lib/Target/PowerPC/PPCISelDAGToDAG.cpp:3938:17
#14 0x000000000215b184 (anonymous namespace)::PPCDAGToDAGISel::Select(llvm::SDNode*) /home/henry/aflplusplus-isel/llvm-project/llvm/lib/Target/PowerPC/PPCISelDAGToDAG.cpp:5037:7
#15 0x000000000453dac9 llvm::SelectionDAGISel::DoInstructionSelection() /home/henry/aflplusplus-isel/llvm-project/llvm/lib/CodeGen/SelectionDAG/SelectionDAGISel.cpp:1165:5
#16 0x000000000453cb1a llvm::SelectionDAGISel::CodeGenAndEmitDAG() /home/henry/aflplusplus-isel/llvm-project/llvm/lib/CodeGen/SelectionDAG/SelectionDAGISel.cpp:936:3
#17 0x000000000453b4ed 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/henry/aflplusplus-isel/llvm-project/llvm/lib/CodeGen/SelectionDAG/SelectionDAGISel.cpp:688:1
#18 0x000000000453af8b llvm::SelectionDAGISel::SelectAllBasicBlocks(llvm::Function const&) /home/henry/aflplusplus-isel/llvm-project/llvm/lib/CodeGen/SelectionDAG/SelectionDAGISel.cpp:1603:11
#19 0x0000000004538536 llvm::SelectionDAGISel::runOnMachineFunction(llvm::MachineFunction&) /home/henry/aflplusplus-isel/llvm-project/llvm/lib/CodeGen/SelectionDAG/SelectionDAGISel.cpp:467:3
#20 0x000000000215ad79 (anonymous namespace)::PPCDAGToDAGISel::runOnMachineFunction(llvm::MachineFunction&) /home/henry/aflplusplus-isel/llvm-project/llvm/lib/Target/PowerPC/PPCISelDAGToDAG.cpp:167:7
#21 0x0000000003597c35 llvm::MachineFunctionPass::runOnFunction(llvm::Function&) /home/henry/aflplusplus-isel/llvm-project/llvm/lib/CodeGen/MachineFunctionPass.cpp:91:8
#22 0x0000000003c7f5e6 llvm::FPPassManager::runOnFunction(llvm::Function&) /home/henry/aflplusplus-isel/llvm-project/llvm/lib/IR/LegacyPassManager.cpp:1430:23
#23 0x0000000003c84412 llvm::FPPassManager::runOnModule(llvm::Module&) /home/henry/aflplusplus-isel/llvm-project/llvm/lib/IR/LegacyPassManager.cpp:1476:16
#24 0x0000000003c7feb9 (anonymous namespace)::MPPassManager::runOnModule(llvm::Module&) /home/henry/aflplusplus-isel/llvm-project/llvm/lib/IR/LegacyPassManager.cpp:1545:23
#25 0x0000000003c7fa2d llvm::legacy::PassManagerImpl::run(llvm::Module&) /home/henry/aflplusplus-isel/llvm-project/llvm/lib/IR/LegacyPassManager.cpp:535:16
#26 0x0000000003c846f1 llvm::legacy::PassManager::run(llvm::Module&) /home/henry/aflplusplus-isel/llvm-project/llvm/lib/IR/LegacyPassManager.cpp:1672:3
#27 0x0000000000d2566c compileModule(char**, llvm::LLVMContext&) /home/henry/aflplusplus-isel/llvm-project/llvm/tools/llc/llc.cpp:737:41
#28 0x0000000000d23a12 main /home/henry/aflplusplus-isel/llvm-project/llvm/tools/llc/llc.cpp:418:13
#29 0x00007f38014d4c87 __libc_start_main /build/glibc-CVJwZb/glibc-2.27/csu/../csu/libc-start.c:344:0
#30 0x0000000000d2321a _start (./llvm-project/build-debug/bin/llc+0xd2321a)

Cause

The following line returns the shift amount 4294967232 (-64 represented in unsigned) which is wrong and caused out-of-bound access to vector in the following code.

https://github.com/llvm/llvm-project/blob/af029d383a24ee454e1124f64f3427d5b79e5f7e/llvm/lib/Target/PowerPC/PPCISelDAGToDAG.cpp#L1502

HazyFish commented 1 year ago

cc @DataCorrupted

llvmbot commented 1 year ago

@llvm/issue-subscribers-backend-powerpc

RKSimon commented 1 year ago

It looks like BitPermutationSelector.getValueBits doesn't account for PPCISD shift opcodes handling of out of bounds shift amounts (or ISD::ROTL by the looks of it).

SelectionDAG has 34 nodes:
  t0: ch,glue = EntryToken
  t2: i64,ch = CopyFromReg t0, Register:i64 %0
  t89: i64 = add t2, Constant:i64<24>
  t16: i64 = add nuw t2, Constant:i64<16>
  t30: i64,ch = load<(load (s64) from %ir.0 + 24, basealign 32)> t0, t89, undef:i64
    t84: i64 = add t2, Constant:i64<12>
  t83: i32,ch = load<(load (s32) from %ir.0 + 12)> t0, t84, undef:i64
  t27: i64,ch = load<(load (s64) from %ir.0 + 16, align 16, basealign 32)> t0, t16, undef:i64
          t80: i32 = add t83, Constant:i32<-12>
        t92: i64 = PPCISD::SRL Constant:i64<12>, t80
        t41: i64 = add t2, Constant:i64<8>
      t60: ch = store<(store (s64) into %ir.0 + 8, basealign 32)> t83:1, t92, t41, undef:i64
      t63: ch = store<(store (s64) into %ir.0, align 32)> t0, Constant:i64<0>, t2, undef:i64
            t101: i64 = PPCISD::SRL t30, Constant:i32<0>
            t102: i64 = PPCISD::SHL t27, Constant:i32<64>
          t103: i64 = or t101, t102
          t104: i64 = PPCISD::SRL t27, Constant:i32<-64>
        t105: i64 = or t103, t104
      t66: ch = store<(store (s64) into %ir.0 + 24, basealign 32)> t30:1, t105, t89, undef:i64
        t106: i64 = PPCISD::SRL t27, Constant:i32<0>
      t69: ch = store<(store (s64) into %ir.0 + 16, align 16, basealign 32)> t27:1, t106, t16, undef:i64
    t73: ch = TokenFactor t60, t63, t66, t69
  t12: ch = PPCISD::RET_FLAG t73
ecnelises commented 1 year ago

I posted https://reviews.llvm.org/D138551 for review.