[PowerPC] Combine select_cc (x, 0, t, f, lt) to avoid generating `isel`

[lkail]

Summary

We can combine select_cc (x, 0, t, f, lt) to avoid generating expensive isel instruction.

[lkail]

Confirmed with https://alive2.llvm.org/ce/z/8pnUEb

[shchenz]

Thanks for doing this. This is what we should do for PPC target.

llvm/lib/Target/PowerPC/PPCISelLowering.cpp

13624

I think it is not a win transformation for the worst case?

li
li
cmp
select

VS

srl
ext
not
shl
sub

[shchenz]

llvm/test/CodeGen/PowerPC/select.ll

56

This seems to be always profitable. Maybe we can do this transformation in void PPCDAGToDAGISel::Select(SDNode *N) {}?
We can transform it like:

select_cc (x, 0, t, f, lt)

-> subfic (rlwinm) if (f > t)
or
-> addi (rlwinm) if (f <= t)?

[lkail]

Tune codegen.

[lkail]

Add tests to cover zext/trunc.

[shchenz]

I guess this opt should also be profitable for opcode SELECT, is there any reason we don't do this?

llvm/lib/Target/PowerPC/PPCISelLowering.cpp

13599

is it possible to put some conditions in early returns and put some comments there?

13608

same as above, put some contidions in early returns and put some comments there?

13614

can getZExtOrTrunc be used here?

[lkail]

In D89084#2352644, @shchenz wrote:

I guess this opt should also be profitable for opcode SELECT, is there any reason we don't do this?

The complete form of select is select cond, true_value, false_value and cond usually comes from comparison. Most comparisons can't be transformed to shift ops easily. For current ppc backend without this ptch, such pattern is transformed into a select_cc node before pattern-matching instruction selector.

llvm/lib/Target/PowerPC/PPCISelLowering.cpp

13599

Well, it might require some refactor work if adding more select_cc related patterns.

13614

Good one.

[lkail]

Gonna to add more patterns and refine current code.

[lkail]

Functionality of this patch can be covered by https://reviews.llvm.org/D93191.

llvm/lib/Target/PowerPC/PPCISelLowering.h

private:
     SDValue combineSHL(SDNode *N, DAGCombinerInfo &DCI) const;
     SDValue combineSRA(SDNode *N, DAGCombinerInfo &DCI) const;
     SDValue combineSRL(SDNode *N, DAGCombinerInfo &DCI) const;
     SDValue combineMUL(SDNode *N, DAGCombinerInfo &DCI) const;
     SDValue combineADD(SDNode *N, DAGCombinerInfo &DCI) const;
     SDValue combineFMALike(SDNode *N, DAGCombinerInfo &DCI) const;
     SDValue combineTRUNCATE(SDNode *N, DAGCombinerInfo &DCI) const;
     SDValue combineSetCC(SDNode *N, DAGCombinerInfo &DCI) const;
+    SDValue combineSelectCC(SDNode *N, DAGCombinerInfo &DCI) const;
     SDValue combineABS(SDNode *N, DAGCombinerInfo &DCI) const;
     SDValue combineVSelect(SDNode *N, DAGCombinerInfo &DCI) const;
     SDValue combineVectorShuffle(ShuffleVectorSDNode *SVN,
                                  SelectionDAG &DAG) const;
     SDValue combineVReverseMemOP(ShuffleVectorSDNode *SVN, LSBaseSDNode *LSBase,
                                  DAGCombinerInfo &DCI) const;
 
     /// ConvertSETCCToSubtract - looks at SETCC that compares ints. It replaces

llvm/lib/Target/PowerPC/PPCISelLowering.cpp

       SDValue Add = DAG.getNode(ISD::ADD, DL, OpVT, LHS, RHS.getOperand(1));
       return DAG.getSetCC(DL, VT, Add, DAG.getConstant(0, DL, OpVT), CC);
     }
   }
 
   return DAGCombineTruncBoolExt(N, DCI);
 }
 
+SDValue PPCTargetLowering::combineSelectCC(SDNode *N,
+                                           DAGCombinerInfo &DCI) const {
+  assert(N->getOpcode() == ISD::SELECT_CC && "Expect a select_cc node");
+  SelectionDAG &DAG = DCI.DAG;
+  SDLoc DL(N);
+  SDValue LHS = N->getOperand(0);
+  SDValue RHS = N->getOperand(1);
+  SDValue TrueOp = N->getOperand(2);
+  SDValue FalseOp = N->getOperand(3);
+  ISD::CondCode CC = cast<CondCodeSDNode>(N->getOperand(4))->get();
+  EVT VT = TrueOp.getValueType();
+
+  auto *TrueC = dyn_cast<ConstantSDNode>(TrueOp);
+  auto *FalseC = dyn_cast<ConstantSDNode>(FalseOp);
+  // select_cc x, 0, y, z, lt
+  // -> sub z, (shl zext(shr x sizeof(x) - 1) log2(z - y))
+  // where (z - y) is power of 2.
+  if (VT.isInteger() && TrueC && FalseC && isTypeLegal(VT) &&
+      (isNullConstant(RHS) && CC == ISD::SETLT)) {
+    SDValue CompOp = LHS;
+    EVT CompVT = CompOp.getValueType();
+    const APInt &TrueVal = TrueC->getAPIntValue();
+    const APInt &FalseVal = FalseC->getAPIntValue();
+    bool OV;
+    APInt Diff = FalseVal.ssub_ov(TrueVal, OV);
+    APInt AbsDiff = Diff.abs();
+    if (!OV && AbsDiff.isPowerOf2() && CompVT.isInteger() &&
+        isTypeLegal(CompVT)) {
+      unsigned SignBitShiftAmount = CompVT.getSizeInBits() - 1;
+      SDValue SignBit =
+          DAG.getNode(ISD::SRL, DL, CompVT, CompOp,
+                      DAG.getConstant(SignBitShiftAmount, DL, CompVT));
+      SignBit = DAG.getZExtOrTrunc(SignBit, DL, VT);
+      unsigned LastOp = ISD::SUB;
+      if (FalseVal.slt(TrueVal))
+        LastOp = ISD::ADD;
+      unsigned Shift = AbsDiff.logBase2();
+      if (Shift == 0)
+        return DAG.getNode(LastOp, DL, VT, SDValue(FalseC, 0), SignBit);
+      SDValue Temp = DAG.getNode(ISD::SHL, DL, VT, SignBit,
+                                 DAG.getConstant(Shift, DL, VT));
+      return DAG.getNode(LastOp, DL, VT, SDValue(FalseC, 0), Temp);
+    }
+  }
+
+  return SDValue();
+}
+
 // Is this an extending load from an f32 to an f64?
 static bool isFPExtLoad(SDValue Op) {
   if (LoadSDNode *LD = dyn_cast<LoadSDNode>(Op.getNode()))
     return LD->getExtensionType() == ISD::EXTLOAD &&
       Op.getValueType() == MVT::f64;
   return false;
 }
 

   case ISD::ZERO_EXTEND:
   case ISD::ANY_EXTEND:
     return DAGCombineExtBoolTrunc(N, DCI);
   case ISD::TRUNCATE:
     return combineTRUNCATE(N, DCI);
   case ISD::SETCC:
     if (SDValue CSCC = combineSetCC(N, DCI))
       return CSCC;
-    LLVM_FALLTHROUGH;
+    return DAGCombineTruncBoolExt(N, DCI);
   case ISD::SELECT_CC:
+    if (SDValue Val = combineSelectCC(N, DCI))
+      return Val;
     return DAGCombineTruncBoolExt(N, DCI);
   case ISD::SINT_TO_FP:
   case ISD::UINT_TO_FP:
     return combineFPToIntToFP(N, DCI);
   case ISD::VECTOR_SHUFFLE:
     if (ISD::isNormalLoad(N->getOperand(0).getNode())) {
       LSBaseSDNode* LSBase = cast<LSBaseSDNode>(N->getOperand(0));
       return combineVReverseMemOP(cast<ShuffleVectorSDNode>(N), LSBase, DCI);

llvm/test/CodeGen/PowerPC/select.ll

 ; NOTE: Assertions have been autogenerated by utils/update_llc_test_checks.py
 ; RUN: llc -ppc-asm-full-reg-names -verify-machineinstrs \
 ; RUN:   -mtriple=powerpc64le-linux-gnu < %s | FileCheck \
 ; RUN:   -check-prefix=CHECK-LE %s
 ; RUN: llc -ppc-asm-full-reg-names -verify-machineinstrs \
 ; RUN:   -mtriple=powerpc-linux-gnu < %s | FileCheck \
 ; RUN:   -check-prefix=CHECK-32 %s
 
 define i64 @f0(i64 %x) {
 ; CHECK-LE-LABEL: f0:
 ; CHECK-LE:       # %bb.0:
-; CHECK-LE-NEXT:    li r4, 125
-; CHECK-LE-NEXT:    cmpdi r3, 0
-; CHECK-LE-NEXT:    li r3, -3
-; CHECK-LE-NEXT:    isellt r3, r3, r4
+; CHECK-LE-NEXT:    rotldi r3, r3, 1
+; CHECK-LE-NEXT:    rldic r3, r3, 7, 56
+; CHECK-LE-NEXT:    subfic r3, r3, 125
 ; CHECK-LE-NEXT:    blr
 ;
 ; CHECK-32-LABEL: f0:
 ; CHECK-32:       # %bb.0:
-; CHECK-32-NEXT:    li r4, 125
-; CHECK-32-NEXT:    li r5, -3
-; CHECK-32-NEXT:    cmpwi r3, 0
-; CHECK-32-NEXT:    bc 12, lt, .LBB0_1
-; CHECK-32-NEXT:    b .LBB0_2
-; CHECK-32-NEXT:  .LBB0_1:
-; CHECK-32-NEXT:    addi r4, r5, 0
-; CHECK-32-NEXT:  .LBB0_2:
-; CHECK-32-NEXT:    srawi r3, r3, 31
+; CHECK-32-NEXT:    srawi r5, r3, 31
+; CHECK-32-NEXT:    rlwinm r3, r3, 8, 24, 24
+; CHECK-32-NEXT:    subfic r4, r3, 125
+; CHECK-32-NEXT:    mr r3, r5
 ; CHECK-32-NEXT:    blr
   %c = icmp slt i64 %x, 0
   %r = select i1 %c, i64 -3, i64 125
   ret i64 %r
 }
 
+define i64 @f0_reverse(i64 %x) {
+; CHECK-LE-LABEL: f0_reverse:
+; CHECK-LE:       # %bb.0:
+; CHECK-LE-NEXT:    rotldi r3, r3, 1
+; CHECK-LE-NEXT:    rldic r3, r3, 7, 56
+; CHECK-LE-NEXT:    addi r3, r3, -3
+; CHECK-LE-NEXT:    blr
+;
+; CHECK-32-LABEL: f0_reverse:
+; CHECK-32:       # %bb.0:
+; CHECK-32-NEXT:    not r4, r3
+; CHECK-32-NEXT:    rlwinm r5, r3, 8, 24, 24
+; CHECK-32-NEXT:    srawi r3, r4, 31
+; CHECK-32-NEXT:    addi r4, r5, -3
+; CHECK-32-NEXT:    blr
+  %c = icmp slt i64 %x, 0
+  %r = select i1 %c, i64 125, i64 -3
+  ret i64 %r
+}
+
+define i32 @f0_might_ov(i32 %x) {
+; CHECK-LE-LABEL: f0_might_ov:
+; CHECK-LE:       # %bb.0:
+; CHECK-LE-NEXT:    rlwinm r3, r3, 0, 0, 0
+; CHECK-LE-NEXT:    subfic r3, r3, 1
+; CHECK-LE-NEXT:    blr
+;
+; CHECK-32-LABEL: f0_might_ov:
+; CHECK-32:       # %bb.0:
+; CHECK-32-NEXT:    lis r4, -32768
+; CHECK-32-NEXT:    cmpwi r3, 0
+; CHECK-32-NEXT:    ori r3, r4, 1
+; CHECK-32-NEXT:    li r4, 1
+; CHECK-32-NEXT:    bclr 12, lt, 0
+; CHECK-32-NEXT:  # %bb.1:
+; CHECK-32-NEXT:    ori r3, r4, 0
+; CHECK-32-NEXT:    blr
+  %c = icmp slt i32 %x, 0
+  %r = select i1 %c, i32 -2147483647, i32 1
+  ret i32 %r
+}
+
+define i32 @f0_not_ov(i32 %x) {
+; CHECK-LE-LABEL: f0_not_ov:
+; CHECK-LE:       # %bb.0:
+; CHECK-LE-NEXT:    rlwinm r3, r3, 31, 1, 1
+; CHECK-LE-NEXT:    addis r3, r3, -16384
+; CHECK-LE-NEXT:    blr
+;
+; CHECK-32-LABEL: f0_not_ov:
+; CHECK-32:       # %bb.0:
+; CHECK-32-NEXT:    rlwinm r3, r3, 31, 1, 1
+; CHECK-32-NEXT:    addis r3, r3, -16384
+; CHECK-32-NEXT:    blr
+  %c = icmp slt i32 %x, 0
+  %r = select i1 %c, i32 0, i32 -1073741824
+  ret i32 %r
+}
+
+define i64 @f0_zext(i32 %x) {
+; CHECK-LE-LABEL: f0_zext:
+; CHECK-LE:       # %bb.0:
+; CHECK-LE-NEXT:    rlwinm r3, r3, 8, 24, 24
+; CHECK-LE-NEXT:    subfic r3, r3, 131
+; CHECK-LE-NEXT:    blr
+;
+; CHECK-32-LABEL: f0_zext:
+; CHECK-32:       # %bb.0:
+; CHECK-32-NEXT:    mr r4, r3
+; CHECK-32-NEXT:    rlwinm r4, r4, 8, 24, 24
+; CHECK-32-NEXT:    li r3, 0
+; CHECK-32-NEXT:    subfic r4, r4, 131
+; CHECK-32-NEXT:    blr
+  %c = icmp slt i32 %x, 0
+  %r = select i1 %c, i64 3, i64 131
+  ret i64 %r
+}
+
+define i32 @f0_trunc(i64 %x) {
+; CHECK-LE-LABEL: f0_trunc:
+; CHECK-LE:       # %bb.0:
+; CHECK-LE-NEXT:    rotldi r3, r3, 1
+; CHECK-LE-NEXT:    rldic r3, r3, 8, 55
+; CHECK-LE-NEXT:    subfic r3, r3, 254
+; CHECK-LE-NEXT:    blr
+;
+; CHECK-32-LABEL: f0_trunc:
+; CHECK-32:       # %bb.0:
+; CHECK-32-NEXT:    rlwinm r3, r3, 9, 23, 23
+; CHECK-32-NEXT:    subfic r3, r3, 254
+; CHECK-32-NEXT:    blr
+  %c = icmp slt i64 %x, 0
+  %r = select i1 %c, i32 -2, i32 254
+  ret i32 %r
+}
+
 define i64 @f1(i64 %x) {
 ; CHECK-LE-LABEL: f1:
 ; CHECK-LE:       # %bb.0:
 ; CHECK-LE-NEXT:    li r4, 512
 ; CHECK-LE-NEXT:    cmpdi r3, 0
 ; CHECK-LE-NEXT:    li r3, 64
 ; CHECK-LE-NEXT:    isellt r3, r3, r4
 ; CHECK-LE-NEXT:    blr
 ;
 ; CHECK-32-LABEL: f1:
 ; CHECK-32:       # %bb.0:
 ; CHECK-32-NEXT:    li r4, 512
 ; CHECK-32-NEXT:    cmpwi r3, 0
 ; CHECK-32-NEXT:    li r3, 64
-; CHECK-32-NEXT:    bc 12, lt, .LBB1_1
-; CHECK-32-NEXT:    b .LBB1_2
-; CHECK-32-NEXT:  .LBB1_1:
+; CHECK-32-NEXT:    bc 12, lt, .LBB6_1
+; CHECK-32-NEXT:    b .LBB6_2
+; CHECK-32-NEXT:  .LBB6_1:
 ; CHECK-32-NEXT:    addi r4, r3, 0
-; CHECK-32-NEXT:  .LBB1_2:
+; CHECK-32-NEXT:  .LBB6_2:
 ; CHECK-32-NEXT:    li r3, 0
 ; CHECK-32-NEXT:    blr
   %c = icmp slt i64 %x, 0
   %r = select i1 %c, i64 64, i64 512
   ret i64 %r
 }
 
 define i64 @f2(i64 %x) {
 ; CHECK-LE-LABEL: f2:
 ; CHECK-LE:       # %bb.0:
 ; CHECK-LE-NEXT:    li r4, 1024
 ; CHECK-LE-NEXT:    cmpdi r3, 0
 ; CHECK-LE-NEXT:    iseleq r3, 0, r4
 ; CHECK-LE-NEXT:    blr
 ;
 ; CHECK-32-LABEL: f2:
 ; CHECK-32:       # %bb.0:
 ; CHECK-32-NEXT:    or. r3, r4, r3
 ; CHECK-32-NEXT:    li r3, 1024
-; CHECK-32-NEXT:    bc 12, eq, .LBB2_2
+; CHECK-32-NEXT:    bc 12, eq, .LBB7_2
 ; CHECK-32-NEXT:  # %bb.1:
 ; CHECK-32-NEXT:    ori r4, r3, 0
-; CHECK-32-NEXT:    b .LBB2_3
-; CHECK-32-NEXT:  .LBB2_2:
+; CHECK-32-NEXT:    b .LBB7_3
+; CHECK-32-NEXT:  .LBB7_2:
 ; CHECK-32-NEXT:    li r4, 0
-; CHECK-32-NEXT:  .LBB2_3:
+; CHECK-32-NEXT:  .LBB7_3:
 ; CHECK-32-NEXT:    li r3, 0
 ; CHECK-32-NEXT:    blr
   %c = icmp eq i64 %x, 0
   %r = select i1 %c, i64 0, i64 1024
   ret i64 %r
 }
 
 define i64 @f3(i64 %x, i64 %y) {
 ; CHECK-LE-LABEL: f3:
 ; CHECK-LE:       # %bb.0:
 ; CHECK-LE-NEXT:    cmpldi r3, 0
 ; CHECK-LE-NEXT:    iseleq r3, 0, r4
 ; CHECK-LE-NEXT:    blr
 ;
 ; CHECK-32-LABEL: f3:
 ; CHECK-32:       # %bb.0:
 ; CHECK-32-NEXT:    or. r3, r4, r3
-; CHECK-32-NEXT:    bc 12, eq, .LBB3_2
+; CHECK-32-NEXT:    bc 12, eq, .LBB8_2
 ; CHECK-32-NEXT:  # %bb.1:
 ; CHECK-32-NEXT:    ori r3, r5, 0
 ; CHECK-32-NEXT:    ori r4, r6, 0
 ; CHECK-32-NEXT:    blr
-; CHECK-32-NEXT:  .LBB3_2:
+; CHECK-32-NEXT:  .LBB8_2:
 ; CHECK-32-NEXT:    li r3, 0
 ; CHECK-32-NEXT:    li r4, 0
 ; CHECK-32-NEXT:    blr
   %c = icmp eq i64 %x, 0
   %r = select i1 %c, i64 0, i64 %y
   ret i64 %r
 }
 

 ; CHECK-32-NEXT:    cmplwi r3, 0
 ; CHECK-32-NEXT:    cmpwi cr1, r3, 0
 ; CHECK-32-NEXT:    crandc 4*cr5+lt, 4*cr1+gt, eq
 ; CHECK-32-NEXT:    cmpwi cr1, r4, 0
 ; CHECK-32-NEXT:    subfic r5, r4, 0
 ; CHECK-32-NEXT:    crandc 4*cr5+gt, eq, 4*cr1+eq
 ; CHECK-32-NEXT:    cror 4*cr5+lt, 4*cr5+gt, 4*cr5+lt
 ; CHECK-32-NEXT:    subfze r6, r3
-; CHECK-32-NEXT:    bc 12, 4*cr5+lt, .LBB4_1
+; CHECK-32-NEXT:    bc 12, 4*cr5+lt, .LBB9_1
 ; CHECK-32-NEXT:    blr
-; CHECK-32-NEXT:  .LBB4_1:
+; CHECK-32-NEXT:  .LBB9_1:
 ; CHECK-32-NEXT:    addi r3, r6, 0
 ; CHECK-32-NEXT:    addi r4, r5, 0
 ; CHECK-32-NEXT:    blr
   %c = icmp sgt i64 %x, 0
   %x.neg = sub i64 0, %x
   %r = select i1 %c, i64 %x.neg, i64 %x
   ret i64 %r
 }