[PowerPC] Mask constant operands in bit permutation calculation

[qiucf]

Summary

This patch fixes issue 59074.

In IR or C code, left/right shift amount larger than value size is undefined behavior. But in practise, backend lowering for srl_parts/sra_parts/shl_parts produces add/sub of shift amounts, thus constant shift amounts might be negative or larger than value size. And the lowering depends on behavior in ISA.

PowerPC ISA says, the lowest 7 bits (6 bits if in 32-bit instruction) will be taken, and if the highest among them is 1, result will be zero, otherwise the low 6 bits (or 5 on 32-bit) are used as shift amount.

This patch emulates the behavior and avoids array overflow in bit permutation's value bits calculator.

[lkail]

llvm/test/CodeGen/PowerPC/pr59074.ll

1

Any idea why it doesn't crash on pwr8?

103

Any idea why it doesn't crash for scalars?

[tingwang]

llvm/lib/Target/PowerPC/PPCISelDAGToDAG.cpp

1487

If I understand correctly, ShiftAmt is unsigned so a "negative value" means very large shift amount here. Can we simply cap ShiftAmt to be no larger than NumBits, and then seems additional boundary checks are not necessary?

llvm/test/CodeGen/PowerPC/pr59074.ll

1

I think the DAGTypeLegalizer changed direction for this case on pwr8, for example:
https://github.com/llvm/llvm-project/blob/d18523c0430cee513a07b5b2a89ad1adb43c91f1/llvm/lib/Target/PowerPC/PPCISelLowering.cpp#L1059

[qiucf]

llvm/lib/Target/PowerPC/PPCISelDAGToDAG.cpp

1487

Although LLVM langref says when shift amount is larger than number bits, here the case also matches for PPCISD::SHL, which fully conforms to behavior of Power's shift instructions (sld, for example):

sld r3, r3, r4 when r4=0b110111111 or 0b0000111111 the result is the same (the instruction only cares about lowest 7 bits).

[qiucf]

llvm/test/CodeGen/PowerPC/pr59074.ll

1

Yes, -mcpu=pwr8 touches another codepath

103

We can't write shl i64 %a, 65 to reproduce it, because such simple pattern will be converted to poison value by combiner.

The crash is actually from srl_parts a, b, 0 in SDAG, which then legalizes into a group of PPCISD::SHL/SRL a, b, 0/64/-64.

Legalizer splits 2xi128 into two 1xi128, during the process some sub a, a is generated and consumed by srl_parts as shift amounts. This may expose some limitations of the combiner.

[qiucf]

Migrated to https://github.com/llvm/llvm-project/pull/67653

llvm/lib/Target/PowerPC/PPCISelDAGToDAG.cpp

     bool &Interesting = ValueEntry->first;
     SmallVector<ValueBit, 64> &Bits = ValueEntry->second;
     Bits.resize(NumBits);
 
     switch (V.getOpcode()) {
     default: break;
     case ISD::ROTL:
       if (isa<ConstantSDNode>(V.getOperand(1))) {
-        unsigned RotAmt = V.getConstantOperandVal(1);
+        unsigned RotAmt = V.getConstantOperandVal(1) & (NumBits - 1);
 
         const auto &LHSBits = *getValueBits(V.getOperand(0), NumBits).second;
 
         for (unsigned i = 0; i < NumBits; ++i)
           Bits[i] = LHSBits[i < RotAmt ? i + (NumBits - RotAmt) : i - RotAmt];
 
         return std::make_pair(Interesting = true, &Bits);
       }
       break;
     case ISD::SHL:
     case PPCISD::SHL:
       if (isa<ConstantSDNode>(V.getOperand(1))) {
-        unsigned ShiftAmt = V.getConstantOperandVal(1);
+        // sld takes 7 bits, slw takes 6.
+        unsigned ShiftAmt = V.getConstantOperandVal(1) & ((NumBits << 1) - 1);
 
         const auto &LHSBits = *getValueBits(V.getOperand(0), NumBits).second;
 
-        for (unsigned i = ShiftAmt; i < NumBits; ++i)
-          Bits[i] = LHSBits[i - ShiftAmt];
-
-        for (unsigned i = 0; i < ShiftAmt; ++i)
-          Bits[i] = ValueBit(ValueBit::ConstZero);
+        if (ShiftAmt >= NumBits) {
+          for (unsigned i = 0; i < NumBits; ++i)
+            Bits[i] = ValueBit(ValueBit::ConstZero);
+        } else {
+          for (unsigned i = ShiftAmt; i < NumBits; ++i)
+            Bits[i] = LHSBits[i - ShiftAmt];
+          for (unsigned i = 0; i < ShiftAmt; ++i)
+            Bits[i] = ValueBit(ValueBit::ConstZero);
+        }
 
         return std::make_pair(Interesting = true, &Bits);
       }
       break;
     case ISD::SRL:
     case PPCISD::SRL:
       if (isa<ConstantSDNode>(V.getOperand(1))) {
-        unsigned ShiftAmt = V.getConstantOperandVal(1);
+        // srd takes lowest 7 bits, srw takes 6.
+        unsigned ShiftAmt = V.getConstantOperandVal(1) & ((NumBits << 1) - 1);
 
         const auto &LHSBits = *getValueBits(V.getOperand(0), NumBits).second;
 
-        for (unsigned i = 0; i < NumBits - ShiftAmt; ++i)
-          Bits[i] = LHSBits[i + ShiftAmt];
-
-        for (unsigned i = NumBits - ShiftAmt; i < NumBits; ++i)
-          Bits[i] = ValueBit(ValueBit::ConstZero);
+        if (ShiftAmt >= NumBits) {
+          for (unsigned i = 0; i < NumBits; ++i)
+            Bits[i] = ValueBit(ValueBit::ConstZero);
+        } else {
+          for (unsigned i = 0; i < NumBits - ShiftAmt; ++i)
+            Bits[i] = LHSBits[i + ShiftAmt];
+          for (unsigned i = NumBits - ShiftAmt; i < NumBits; ++i)
+            Bits[i] = ValueBit(ValueBit::ConstZero);
+        }
 
         return std::make_pair(Interesting = true, &Bits);
       }
       break;
     case ISD::AND:
       if (isa<ConstantSDNode>(V.getOperand(1))) {
         uint64_t Mask = V.getConstantOperandVal(1);
 

llvm/test/CodeGen/PowerPC/pr59074.ll

+; NOTE: Assertions have been autogenerated by utils/update_llc_test_checks.py
+; RUN: llc -mtriple=powerpc64le-unknown-linux-gnu -mcpu=pwr7 < %s | FileCheck %s --check-prefix=LE64
+; RUN: llc -mtriple=powerpcle-unknown-linux-gnu -mcpu=pwr7 < %s | FileCheck %s --check-prefix=LE32
+; RUN: llc -mtriple=powerpc64-ibm-aix -mcpu=pwr7 < %s | FileCheck %s --check-prefix=BE64
+; RUN: llc -mtriple=powerpc-ibm-aix -mcpu=pwr7 < %s | FileCheck %s --check-prefix=BE32
+
+; To verify this doesn't crash due to array out of bound.
+define void @pr59074(ptr %0) {
+; LE64-LABEL: pr59074:
+; LE64:       # %bb.0: # %entry
+; LE64-NEXT:    lwz 5, 0(3)
+; LE64-NEXT:    li 4, 12
+; LE64-NEXT:    ld 6, 16(3)
+; LE64-NEXT:    li 7, 0
+; LE64-NEXT:    std 7, 8(3)
+; LE64-NEXT:    addi 5, 5, -12
+; LE64-NEXT:    std 6, 16(3)
+; LE64-NEXT:    srd 4, 4, 5
+; LE64-NEXT:    ld 5, 24(3)
+; LE64-NEXT:    std 4, 0(3)
+; LE64-NEXT:    std 5, 24(3)
+; LE64-NEXT:    blr
+;
+; LE32-LABEL: pr59074:
+; LE32:       # %bb.0: # %entry
+; LE32-NEXT:    lwz 5, 0(3)
+; LE32-NEXT:    li 4, 12
+; LE32-NEXT:    lwz 6, 4(3)
+; LE32-NEXT:    li 7, 0
+; LE32-NEXT:    lwz 8, 8(3)
+; LE32-NEXT:    lwz 9, 12(3)
+; LE32-NEXT:    subc 5, 5, 4
+; LE32-NEXT:    stw 7, 8(3)
+; LE32-NEXT:    subfe. 6, 7, 6
+; LE32-NEXT:    cmplwi 1, 5, 64
+; LE32-NEXT:    subfe 8, 7, 8
+; LE32-NEXT:    crand 20, 2, 4
+; LE32-NEXT:    stw 7, 12(3)
+; LE32-NEXT:    subfe 9, 7, 9
+; LE32-NEXT:    stw 7, 4(3)
+; LE32-NEXT:    or. 10, 8, 9
+; LE32-NEXT:    or 8, 5, 8
+; LE32-NEXT:    or 6, 6, 9
+; LE32-NEXT:    lwz 9, 24(3)
+; LE32-NEXT:    crnand 20, 2, 20
+; LE32-NEXT:    srw 5, 4, 5
+; LE32-NEXT:    or. 6, 8, 6
+; LE32-NEXT:    lwz 6, 28(3)
+; LE32-NEXT:    stw 9, 24(3)
+; LE32-NEXT:    isel 5, 0, 5, 20
+; LE32-NEXT:    stw 6, 28(3)
+; LE32-NEXT:    iseleq 4, 4, 5
+; LE32-NEXT:    stw 4, 0(3)
+; LE32-NEXT:    blr
+;
+; BE64-LABEL: pr59074:
+; BE64:       # %bb.0: # %entry
+; BE64-NEXT:    lwz 5, 12(3)
+; BE64-NEXT:    li 4, 12
+; BE64-NEXT:    ld 6, 24(3)
+; BE64-NEXT:    li 7, 0
+; BE64-NEXT:    std 7, 0(3)
+; BE64-NEXT:    addi 5, 5, -12
+; BE64-NEXT:    std 6, 24(3)
+; BE64-NEXT:    srd 4, 4, 5
+; BE64-NEXT:    ld 5, 16(3)
+; BE64-NEXT:    std 4, 8(3)
+; BE64-NEXT:    std 5, 16(3)
+; BE64-NEXT:    blr
+;
+; BE32-LABEL: pr59074:
+; BE32:       # %bb.0: # %entry
+; BE32-NEXT:    lwz 5, 12(3)
+; BE32-NEXT:    li 4, 12
+; BE32-NEXT:    lwz 6, 8(3)
+; BE32-NEXT:    li 7, 0
+; BE32-NEXT:    lwz 8, 4(3)
+; BE32-NEXT:    lwz 9, 0(3)
+; BE32-NEXT:    subc 5, 5, 4
+; BE32-NEXT:    stw 7, 8(3)
+; BE32-NEXT:    subfe. 6, 7, 6
+; BE32-NEXT:    cmplwi 1, 5, 64
+; BE32-NEXT:    subfe 8, 7, 8
+; BE32-NEXT:    crand 20, 2, 4
+; BE32-NEXT:    stw 7, 0(3)
+; BE32-NEXT:    subfe 9, 7, 9
+; BE32-NEXT:    stw 7, 4(3)
+; BE32-NEXT:    or. 10, 8, 9
+; BE32-NEXT:    or 8, 5, 8
+; BE32-NEXT:    or 6, 6, 9
+; BE32-NEXT:    lwz 9, 20(3)
+; BE32-NEXT:    crnand 20, 2, 20
+; BE32-NEXT:    srw 5, 4, 5
+; BE32-NEXT:    or. 6, 8, 6
+; BE32-NEXT:    lwz 6, 16(3)
+; BE32-NEXT:    stw 9, 20(3)
+; BE32-NEXT:    isel 5, 0, 5, 20
+; BE32-NEXT:    stw 6, 16(3)
+; BE32-NEXT:    iseleq 4, 4, 5
+; BE32-NEXT:    stw 4, 12(3)
+; BE32-NEXT:    blr
+entry:
+  %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
+}