[TargetLowering][DAGCombine][MSP430] Shift Amount Threshold in DAGCombine (4)

[joanlluch]

Summary

Replaces

unsigned getShiftAmountThreshold(EVT VT)

by

bool shouldAvoidTransformToShift(EVT VT, unsigned amount)

thus giving more flexibility for targets to decide whether particular shift amounts must be considered expensive or not.

Updates the MSP430 target with a custom implementation.

This continues D69116, D69120, D69326 and updates them, so all of them must be committed before this.

Existing tests apply, a few more have been added.

[spatel]

llvm/include/llvm/CodeGen/TargetLowering.h

2607–2610

/// Return true if creating a shift of the type by the given 
/// amount is not profitable.

2609

formatting: amount -> Amount
http://llvm.org/docs/CodingStandards.html#name-types-functions-variables-and-enumerators-properly

llvm/lib/Target/MSP430/MSP430ISelLowering.cpp

364

This changes the MSP430 output for shift by 8 or 9? If yes, there should be tests that show this difference.

[joanlluch]

llvm/lib/Target/MSP430/MSP430ISelLowering.cpp

364

I commited baseline tests to show this (D70083). I did not wait for review in this particular case, as I understand it's simple enough. (It does not modify any code) (I hope this is ok).
I will submit an updated patch for this.

[joanlluch]

llvm/lib/Target/MSP430/MSP430ISelLowering.cpp

364

After all the related previous patches, showing improvements for the special case of 8 and 9 bit shifts on the MSP430 is really borderline. But they can be found in a couple of cases. The intention of this series of patches is to provide additional hooks for targets that may benefit from them. In the particular case of the MSP430, it's possibly debatable whether 8 and 9 bit shifts should be systematically factored-in, but in the general case, I think that it is good that the TLI hook semantics provide more flexibility to targets. Please let me know how it looks now. Thanks

[spatel]

LGTM - I'm assuming less code is better on this target.
(if @asl or someone else can confirm, that would be great)

llvm/include/llvm/CodeGen/TargetLowering.h

virtual bool aggressivelyPreferBuildVectorSources(EVT VecVT) const {
     return false;
   }
 
   // Return true if CodeGenPrepare should consider splitting large offset of a
   // GEP to make the GEP fit into the addressing mode and can be sunk into the
   // same blocks of its users.
   virtual bool shouldConsiderGEPOffsetSplit() const { return false; }
 
-  // Return the shift amount threshold for profitable transforms into shifts.
-  // Transforms creating shifts above the returned value will be avoided.
-  virtual unsigned getShiftAmountThreshold(EVT VT) const {
-    return VT.getScalarSizeInBits();
+  /// Return true if creating a shift of the type by the given
+  /// amount is not profitable.
+  virtual bool shouldAvoidTransformToShift(EVT VT, unsigned Amount) const {
+    return false;
   }
 
   //===--------------------------------------------------------------------===//
   // Runtime Library hooks
   //
 
   /// Rename the default libcall routine name for the specified libcall.
   void setLibcallName(RTLIB::Libcall Call, const char *Name) {

llvm/lib/CodeGen/SelectionDAG/DAGCombiner.cpp

static SDValue foldExtendedSignBitTest(SDNode *N, SelectionDAG &DAG,
   // not require the 'not' op.
   if (CC == ISD::SETGT && isAllOnesConstant(Ones) && VT == XVT) {
     // Invert and smear/shift the sign bit:
     // sext i1 (setgt iN X, -1) --> sra (not X), (N - 1)
     // zext i1 (setgt iN X, -1) --> srl (not X), (N - 1)
     SDLoc DL(N);
     unsigned ShCt = VT.getSizeInBits() - 1;
     const TargetLowering &TLI = DAG.getTargetLoweringInfo();
-    if (ShCt <= TLI.getShiftAmountThreshold(VT)) {
+    if (!TLI.shouldAvoidTransformToShift(VT, ShCt)) {
       SDValue NotX = DAG.getNOT(DL, X, VT);
       SDValue ShiftAmount = DAG.getConstant(ShCt, DL, VT);
       auto ShiftOpcode =
         N->getOpcode() == ISD::SIGN_EXTEND ? ISD::SRA : ISD::SRL;
       return DAG.getNode(ShiftOpcode, DL, VT, NotX, ShiftAmount);
     }
   }
   return SDValue();
SDValue DAGCombiner::foldSelectCCToShiftAnd(const SDLoc &DL, SDValue N0,
   }
 
   // and (sra X, size(X)-1), A -> "and (srl X, C2), A" iff A is a single-bit
   // constant.
   EVT ShiftAmtTy = getShiftAmountTy(N0.getValueType());
   auto *N2C = dyn_cast<ConstantSDNode>(N2.getNode());
   if (N2C && ((N2C->getAPIntValue() & (N2C->getAPIntValue() - 1)) == 0)) {
     unsigned ShCt = XType.getSizeInBits() - N2C->getAPIntValue().logBase2() - 1;
-    if (ShCt <= TLI.getShiftAmountThreshold(XType)) {
+    if (!TLI.shouldAvoidTransformToShift(XType, ShCt)) {
       SDValue ShiftAmt = DAG.getConstant(ShCt, DL, ShiftAmtTy);
       SDValue Shift = DAG.getNode(ISD::SRL, DL, XType, N0, ShiftAmt);
       AddToWorklist(Shift.getNode());
 
       if (XType.bitsGT(AType)) {
         Shift = DAG.getNode(ISD::TRUNCATE, DL, AType, Shift);
         AddToWorklist(Shift.getNode());
       }
 
       if (CC == ISD::SETGT)
         Shift = DAG.getNOT(DL, Shift, AType);
 
       return DAG.getNode(ISD::AND, DL, AType, Shift, N2);
     }
   }
 
   unsigned ShCt = XType.getSizeInBits() - 1;
-  if (ShCt > TLI.getShiftAmountThreshold(XType))
+  if (TLI.shouldAvoidTransformToShift(XType, ShCt))
     return SDValue();
 
   SDValue ShiftAmt = DAG.getConstant(ShCt, DL, ShiftAmtTy);
   SDValue Shift = DAG.getNode(ISD::SRA, DL, XType, N0, ShiftAmt);
   AddToWorklist(Shift.getNode());
 
   if (XType.bitsGT(AType)) {
     Shift = DAG.getNode(ISD::TRUNCATE, DL, AType, Shift);
SDValue DAGCombiner::SimplifySelectCC(const SDLoc &DL, SDValue N0, SDValue N1,
   if (CC == ISD::SETEQ && N0->getOpcode() == ISD::AND &&
       N0->getValueType(0) == VT && isNullConstant(N1) && isNullConstant(N2)) {
     SDValue AndLHS = N0->getOperand(0);
     auto *ConstAndRHS = dyn_cast<ConstantSDNode>(N0->getOperand(1));
     if (ConstAndRHS && ConstAndRHS->getAPIntValue().countPopulation() == 1) {
       // Shift the tested bit over the sign bit.
       const APInt &AndMask = ConstAndRHS->getAPIntValue();
       unsigned ShCt = AndMask.getBitWidth() - 1;
-      if (ShCt <= TLI.getShiftAmountThreshold(VT)) {
+      if (!TLI.shouldAvoidTransformToShift(VT, ShCt)) {
         SDValue ShlAmt =
           DAG.getConstant(AndMask.countLeadingZeros(), SDLoc(AndLHS),
                           getShiftAmountTy(AndLHS.getValueType()));
         SDValue Shl = DAG.getNode(ISD::SHL, SDLoc(N0), VT, AndLHS, ShlAmt);
 
         // Now arithmetic right shift it all the way over, so the result is
         // either all-ones, or zero.
         SDValue ShrAmt =
if ((Fold || Swap) &&
 
     AddToWorklist(SCC.getNode());
     AddToWorklist(Temp.getNode());
 
     if (N2C->isOne())
       return Temp;
 
     unsigned ShCt = N2C->getAPIntValue().logBase2();
-    if (ShCt > TLI.getShiftAmountThreshold(VT))
+    if (TLI.shouldAvoidTransformToShift(VT, ShCt))
       return SDValue();
 
     // shl setcc result by log2 n2c
     return DAG.getNode(ISD::SHL, DL, N2.getValueType(), Temp,
                        DAG.getConstant(ShCt, SDLoc(Temp),
                                        getShiftAmountTy(Temp.getValueType())));
   }
 

llvm/lib/CodeGen/SelectionDAG/TargetLowering.cpp

if ((Cond == ISD::SETEQ || Cond == ISD::SETNE) &&
         N0.getOpcode() == ISD::AND) {
       if (auto *AndRHS = dyn_cast<ConstantSDNode>(N0.getOperand(1))) {
         EVT ShiftTy =
             getShiftAmountTy(ShValTy, Layout, !DCI.isBeforeLegalize());
         if (Cond == ISD::SETNE && C1 == 0) {// (X & 8) != 0  -->  (X & 8) >> 3
           // Perform the xform if the AND RHS is a single bit.
           unsigned ShCt = AndRHS->getAPIntValue().logBase2();
           if (AndRHS->getAPIntValue().isPowerOf2() &&
-              ShCt <= TLI.getShiftAmountThreshold(ShValTy)) {
+              !TLI.shouldAvoidTransformToShift(ShValTy, ShCt)) {
             return DAG.getNode(ISD::TRUNCATE, dl, VT,
                                DAG.getNode(ISD::SRL, dl, ShValTy, N0,
                                            DAG.getConstant(ShCt, dl, ShiftTy)));
           }
         } else if (Cond == ISD::SETEQ && C1 == AndRHS->getAPIntValue()) {
           // (X & 8) == 8  -->  (X & 8) >> 3
           // Perform the xform if C1 is a single bit.
           unsigned ShCt = C1.logBase2();
           if (C1.isPowerOf2() &&
-              ShCt <= TLI.getShiftAmountThreshold(ShValTy)) {
+              !TLI.shouldAvoidTransformToShift(ShValTy, ShCt)) {
             return DAG.getNode(ISD::TRUNCATE, dl, VT,
                                DAG.getNode(ISD::SRL, dl, ShValTy, N0,
                                            DAG.getConstant(ShCt, dl, ShiftTy)));
           }
         }
       }
     }
 
     if (C1.getMinSignedBits() <= 64 &&
         !isLegalICmpImmediate(C1.getSExtValue())) {
       EVT ShiftTy = getShiftAmountTy(ShValTy, Layout, !DCI.isBeforeLegalize());
       // (X & -256) == 256 -> (X >> 8) == 1
       if ((Cond == ISD::SETEQ || Cond == ISD::SETNE) &&
           N0.getOpcode() == ISD::AND && N0.hasOneUse()) {
         if (auto *AndRHS = dyn_cast<ConstantSDNode>(N0.getOperand(1))) {
           const APInt &AndRHSC = AndRHS->getAPIntValue();
           if ((-AndRHSC).isPowerOf2() && (AndRHSC & C1) == C1) {
             unsigned ShiftBits = AndRHSC.countTrailingZeros();
-            if (ShiftBits <= TLI.getShiftAmountThreshold(ShValTy)) {
+            if (!TLI.shouldAvoidTransformToShift(ShValTy, ShiftBits)) {
               SDValue Shift =
                 DAG.getNode(ISD::SRL, dl, ShValTy, N0.getOperand(0),
                             DAG.getConstant(ShiftBits, dl, ShiftTy));
               SDValue CmpRHS = DAG.getConstant(C1.lshr(ShiftBits), dl, ShValTy);
               return DAG.getSetCC(dl, VT, Shift, CmpRHS, Cond);
             }
           }
         }
if (C1.getMinSignedBits() <= 64 &&
           NewC = NewC + 1;
           NewCond = (Cond == ISD::SETULE) ? ISD::SETULT : ISD::SETUGE;
         } else {
           ShiftBits = C1.countTrailingZeros();
         }
         NewC.lshrInPlace(ShiftBits);
         if (ShiftBits && NewC.getMinSignedBits() <= 64 &&
             isLegalICmpImmediate(NewC.getSExtValue()) &&
-            ShiftBits <= TLI.getShiftAmountThreshold(ShValTy)) {
+            !TLI.shouldAvoidTransformToShift(ShValTy, ShiftBits)) {
           SDValue Shift = DAG.getNode(ISD::SRL, dl, ShValTy, N0,
                                       DAG.getConstant(ShiftBits, dl, ShiftTy));
           SDValue CmpRHS = DAG.getConstant(NewC, dl, ShValTy);
           return DAG.getSetCC(dl, VT, Shift, CmpRHS, NewCond);
         }
       }
     }
   }

llvm/lib/Target/MSP430/MSP430ISelLowering.h

public:
     /// necessarily apply to truncate instructions. e.g. on msp430, all
     /// instructions that define 8-bit values implicit zero-extend the result
     /// out to 16 bits.
     bool isZExtFree(Type *Ty1, Type *Ty2) const override;
     bool isZExtFree(EVT VT1, EVT VT2) const override;
     bool isZExtFree(SDValue Val, EVT VT2) const override;
 
     bool isLegalICmpImmediate(int64_t) const override;
-    unsigned getShiftAmountThreshold(EVT VT) const override;
+    bool shouldAvoidTransformToShift(EVT VT, unsigned Amount) const override;
 
     MachineBasicBlock *
     EmitInstrWithCustomInserter(MachineInstr &MI,
                                 MachineBasicBlock *BB) const override;
     MachineBasicBlock *EmitShiftInstr(MachineInstr &MI,
                                       MachineBasicBlock *BB) const;
 
   private:

llvm/lib/Target/MSP430/MSP430ISelLowering.cpp

SDValue MSP430TargetLowering::LowerOperation(SDValue Op,
   case ISD::FRAMEADDR:        return LowerFRAMEADDR(Op, DAG);
   case ISD::VASTART:          return LowerVASTART(Op, DAG);
   case ISD::JumpTable:        return LowerJumpTable(Op, DAG);
   default:
     llvm_unreachable("unimplemented operand");
   }
 }
 
-// Set transforms into shift amounts above 2 as not profitable
-unsigned MSP430TargetLowering::getShiftAmountThreshold(EVT VT) const {
-  return 2;
+// Define non profitable transforms into shifts
+bool MSP430TargetLowering::shouldAvoidTransformToShift(EVT VT,
+                                                       unsigned Amount) const {
+  return !(Amount == 8 || Amount == 9 || Amount<=2);
 }
 
 // Implemented to verify test case assertions in
 // tests/codegen/msp430/shift-amount-threshold-b.ll
 bool MSP430TargetLowering::isLegalICmpImmediate(int64_t Immed) const {
   if (MSP430NoLegalImmediate)
     return Immed >= -32 && Immed < 32;
   return TargetLowering::isLegalICmpImmediate(Immed);

llvm/test/CodeGen/MSP430/shift-amount-threshold.ll

entry:
   ret i16 %cond
 }
 
 ; Check the following conversion in TargetLowering::SimplifySetCC
 ; (X & 8) != 0  -->  (X & 8) >> 3
 define i16 @testSimplifySetCC_0_sh8(i16 %x) {
 ; CHECK-LABEL: testSimplifySetCC_0_sh8:
 ; CHECK:       ; %bb.0: ; %entry
-; CHECK-NEXT:    bit #256, r12
-; CHECK-NEXT:    mov r2, r12
-; CHECK-NEXT:    and #1, r12
+; CHECK-NEXT:    and #256, r12
+; CHECK-NEXT:    swpb r12
 ; CHECK-NEXT:    ret
 entry:
   %and = and i16 %x, 256
   %cmp = icmp ne i16 %and, 0
   %conv = zext i1 %cmp to i16
   ret i16 %conv
 }
 
 ; Check the following conversion in TargetLowering::SimplifySetCC
 ; (X & 8) == 8  -->  (X & 8) >> 3
 define i16 @testSimplifySetCC_1_sh8(i16 %x) {
 ; CHECK-LABEL: testSimplifySetCC_1_sh8:
 ; CHECK:       ; %bb.0: ; %entry
-; CHECK-NEXT:    bit #256, r12
-; CHECK-NEXT:    mov r2, r12
-; CHECK-NEXT:    and #1, r12
+; CHECK-NEXT:    and #256, r12
+; CHECK-NEXT:    swpb r12
 ; CHECK-NEXT:    ret
 entry:
   %and = and i16 %x, 256
   %cmp = icmp eq i16 %and, 256
   %conv = zext i1 %cmp to i16
   ret i16 %conv
 }
 
 ; Check the following conversion in DAGCombiner::foldSelectCCToShiftAnd
 ; select_cc setlt X, 0, A, 0 -> "and (srl X, C2), A" iff A is a single-bit
 define i16 @testShiftAnd_1_sh8(i16 %x) {
 ; CHECK-LABEL: testShiftAnd_1_sh8:
 ; CHECK:       ; %bb.0: ; %entry
-; CHECK-NEXT:    mov r12, r13
-; CHECK-NEXT:    mov #128, r12
-; CHECK-NEXT:    tst r13
-; CHECK-NEXT:    jl .LBB10_2
-; CHECK-NEXT:  ; %bb.1: ; %entry
-; CHECK-NEXT:    clr r12
-; CHECK-NEXT:  .LBB10_2: ; %entry
+; CHECK-NEXT:    swpb r12
+; CHECK-NEXT:    and #128, r12
 ; CHECK-NEXT:    ret
 entry:
   %cmp = icmp slt i16 %x, 0
   %cond = select i1 %cmp, i16 128, i16 0
   ret i16 %cond
 }
 
 ; Check the following conversion in DAGCombiner::foldSelectCCToShiftAnd
 ; select_cc setlt X, 0, A, 0 -> "and (srl X, C2), A" iff A is a single-bit
 define i16 @testShiftAnd_1_sh9(i16 %x) {
 ; CHECK-LABEL: testShiftAnd_1_sh9:
 ; CHECK:       ; %bb.0: ; %entry
-; CHECK-NEXT:    mov r12, r13
-; CHECK-NEXT:    mov #64, r12
-; CHECK-NEXT:    tst r13
-; CHECK-NEXT:    jl .LBB11_2
-; CHECK-NEXT:  ; %bb.1: ; %entry
-; CHECK-NEXT:    clr r12
-; CHECK-NEXT:  .LBB11_2: ; %entry
+; CHECK-NEXT:    swpb r12
+; CHECK-NEXT:    mov.b r12, r12
+; CHECK-NEXT:    clrc
+; CHECK-NEXT:    rrc r12
+; CHECK-NEXT:    and #64, r12
 ; CHECK-NEXT:    ret
 entry:
   %cmp = icmp slt i16 %x, 0
   %cond = select i1 %cmp, i16 64, i16 0
   ret i16 %cond
 }