[PowerPC] Fold select_cc constants when comparing zero into trivial ops

[lkail]

Summary

Fold select_cc x, 0, const0, const1, lt into sub (z, and ((sra x, sizeof(x)-1), z - y)), see https://alive2.llvm.org/ce/z/jqcf8t. On PPC, it's cheap to performance such optimization with rlwinm.

[RKSimon]

llvm/include/llvm/CodeGen/TargetLowering.h

2790 ↗

(On Diff #311484)

We need to determine whether other targets would benefit from this - otherwise I'd suggest the initial implementation was purely inside PPCISelLowering

[RKSimon]

@lkail Reverse ping - as I said earlier I'd probably suggest we make this ppc only initially

[lkail]

@RKSimon Sorry for late response. I have moved the transformation into PPCISelLowering.

[RKSimon]

I'll leave this to the PowerPC gurus now that its target specific

[lkail]

Ping.

[shchenz]

llvm/lib/Target/PowerPC/PPCISelLowering.cpp

16736

Can we handle CmpOpVT.bitsLT(VT) case by using extend operation?

16758

Is it better to check Diff.isNegative()?

llvm/test/CodeGen/PowerPC/select.ll

7

Could you please add some run lines for AIX too?

[shchenz]

llvm/lib/Target/PowerPC/PPCISelLowering.cpp

16731

Use same variable names for these comments? c0/c1 or y/z?

[lkail]

Adjust comments.

[lkail]

llvm/lib/Target/PowerPC/PPCISelLowering.cpp

16736

I don't think it's always profitable. I've updated the comment to make it clearer. The transformation involves in arithmetic shift and SIGN_EXTEND looks not zero overhead under some circumstances.

[lkail]

ping.

[lkail]

Ping.

[spatel]

I'm not familiar with current PPC micro-arch details, so someone else should also look at this patch...
But this seems more restrictive than necessary. Don't we want to handle "x > -1" in addition to "x < 0"?

Note: I added regression tests with this comment to "llvm/test/CodeGen/PowerPC/select_const.ll" long ago:

; select Cond, C1, C2 --> add (mul (zext Cond), C1-C2), C2 --> add (and (sext Cond), C1-C2), C2

Also for the signbit compare pattern, we either have:
https://alive2.llvm.org/ce/z/jqcf8t (from the description)
or:
https://alive2.llvm.org/ce/z/YZyLpm

So we can always turn a 4-instruction isel sequence of arbitrary constants:

li 4, -500
cmpdi	3, 0
li 3, -42
isellt	3, 3, 4

into something like this:

sradi 3, 3, 63
andi. 3, 3, 458
addi 3, 3, -500

So it always saves an instruction to convert to ALU ops?

[spatel]

In D93191#3001797, @spatel wrote:

So we can always turn a 4-instruction isel sequence of arbitrary constants:

That should be "arbitrary small (signed 16-bit) constants". I agree that it doesn't look profitable if we need "lis" to materialize big constants. :)

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 PPCTargetLowering::PerformDAGCombine(SDNode *N,
   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 Value = combineSelectCC(N, DCI))
+      return Value;
     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);
if (TrueOpnd.getOperand(0) == CmpOpnd1 &&
       FalseOpnd.getOperand(1) == CmpOpnd1) {
     return DAG.getNode(PPCISD::VABSD, dl, N->getOperand(1).getValueType(),
                        CmpOpnd1, CmpOpnd2,
                        DAG.getTargetConstant(0, dl, MVT::i32));
   }
 
   return SDValue();
 }
+
+SDValue PPCTargetLowering::combineSelectCC(SDNode *N,
+                                           DAGCombinerInfo &DCI) const {
+  SelectionDAG &DAG = DCI.DAG;
+  SDLoc DL(N);
+  SDValue N0 = N->getOperand(0);
+  SDValue N1 = N->getOperand(1);
+  SDValue N2 = N->getOperand(2);
+  SDValue N3 = N->getOperand(3);
+  ISD::CondCode CC = cast<CondCodeSDNode>(N->getOperand(4))->get();
+  EVT VT = N2.getValueType();
+  EVT CmpOpVT = N0.getValueType();
+  SDValue CmpOp = N0;
+  auto *N2C = dyn_cast<ConstantSDNode>(N2);
+  auto *N3C = dyn_cast<ConstantSDNode>(N3);
+
+  // Exploit sign bit to simplify select_cc x, 0, y, z, cc.
+  // Commonly we have select_cc x, 0, y, z, lt ->
+  // result = z - signbit_of_x * (z - y).
+  // On PPC, it's cheap to materialize signbit_of_x * (z - y) with rlwinm if
+  // (z - y) is a int32 ShiftedMask, which is
+  // select_cc x, 0, y, z, lt is sub (z, and ((sra x, sizeof(x)-1), z - y)).
+  if (!N2C || !N3C || !VT.isInteger() || !CmpOpVT.isInteger() ||
+      !isNullConstant(N1) || CC != ISD::SETLT || !CmpOpVT.bitsGE(VT))
+    return SDValue();
+
+  unsigned SignBitShiftAmount = CmpOpVT.getSizeInBits() - 1;
+  const APInt &TrueVal = N2C->getAPIntValue();
+  const APInt &FalseVal = N3C->getAPIntValue();
+  bool Overflow;
+  APInt Diff = FalseVal.ssub_ov(TrueVal, Overflow);
+  APInt AbsDiff = Diff.abs();
+
+  if (Overflow)
+    return SDValue();
+
+  if (AbsDiff.isNullValue())
+    // N2 == N3.
+    return N2;
+
+  // It cheap to materialize related constants with rlwinm.
+  if (!TrueVal.isSignedIntN(16) || !FalseVal.isSignedIntN(16) ||
+      !Diff.isIntN(32) || !Diff.isShiftedMask())
+    return SDValue();
+
+  unsigned LastOp = Diff.isNegative() ? ISD::ADD : ISD::SUB;
+  SDValue SignBitShifted =
+      DAG.getNode(ISD::SRA, DL, CmpOpVT, CmpOp,
+                  DAG.getConstant(SignBitShiftAmount, DL, CmpOpVT));
+  if (CmpOpVT.bitsGT(VT))
+    SignBitShifted = DAG.getNode(ISD::TRUNCATE, DL, VT, SignBitShifted);
+  SDValue Temp = DAG.getNode(ISD::AND, DL, VT, SignBitShifted,
+                             DAG.getConstant(AbsDiff, DL, VT));
+  return DAG.getNode(LastOp, DL, VT, SDValue(N3C, 0), Temp);
+}

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:    rlwinm r4, r3, 0, 24, 24
+; CHECK-32-NEXT:    subfic r4, r4, 125
 ; CHECK-32-NEXT:    blr
   %c = icmp slt i64 %x, 0
   %r = select i1 %c, i64 -3, i64 125
   ret i64 %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:    sradi r3, r3, 63
+; CHECK-LE-NEXT:    rlwinm r3, r3, 0, 23, 25
+; CHECK-LE-NEXT:    subfic r3, r3, 512
 ; 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:    addi r4, r3, 0
-; CHECK-32-NEXT:  .LBB1_2:
+; CHECK-32-NEXT:    mr r4, r3
+; CHECK-32-NEXT:    srawi r4, r4, 31
+; CHECK-32-NEXT:    rlwinm r4, r4, 0, 23, 25
 ; CHECK-32-NEXT:    li r3, 0
+; CHECK-32-NEXT:    subfic r4, r4, 512
 ; 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: