Shift Amount Threshold in DAGCombine

[joanlluch]

Summary

This is a proposal of a TLI hook to allow targets to relax the emission of shifts.
Contributes to a Fix for https://bugs.llvm.org/show_bug.cgi?id=43559
(please note that the diff is from Release/9.x)

[joanlluch]

I abandoned this, created D68982 instead

llvm/include/llvm/CodeGen/TargetLowering.h

public:
   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
+  // that will result in shifts above the returned value will be discarded.
+  virtual unsigned getShiftAmountThreshold(EVT VT) const {
+    return VT.getSizeInBits();
+  }
+
   //===--------------------------------------------------------------------===//
   // Runtime Library hooks
   //
 
   /// Rename the default libcall routine name for the specified libcall.
   void setLibcallName(RTLIB::Libcall Call, const char *Name) {
     LibcallRoutineNames[Call] = Name;
   }

llvm/lib/CodeGen/SelectionDAG/DAGCombiner.cpp

static SDValue foldExtendedSignBitTest(SDNode *N, SelectionDAG &DAG,
   // setge X, C is canonicalized to setgt, so we do not need to match that
   // pattern. The setlt sibling is folded in SimplifySelectCC() because it does
   // 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);
+    // FIX ME: should we perform TLI.getShiftAmountThreshold checks for
+    // shift amounts of VT.getSizeInBits()-1 ?
     SDValue NotX = DAG.getNOT(DL, X, VT);
     SDValue ShiftAmount = DAG.getConstant(VT.getSizeInBits() - 1, 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(ShiftAmtTy)) {
       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(ShiftAmtTy))
+    return SDValue();
 
-  SDValue ShiftAmt = DAG.getConstant(XType.getSizeInBits() - 1, DL, ShiftAmtTy);
+  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);
     AddToWorklist(Shift.getNode());
   }
 
SDValue DAGCombiner::SimplifySelectCC(const SDLoc &DL, SDValue N0, SDValue N1,
   // shift-left and shift-right-arith.
   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();
+      if (AndMask.getBitWidth() - 1 <= TLI.getShiftAmountThreshold(VT)) {
         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 =
           DAG.getConstant(AndMask.getBitWidth() - 1, SDLoc(Shl),
                           getShiftAmountTy(Shl.getValueType()));
         SDValue Shr = DAG.getNode(ISD::SRA, SDLoc(N0), VT, Shl, ShrAmt);
 
         return DAG.getNode(ISD::AND, DL, VT, Shr, N3);
       }
     }
+  }
 
   // fold select C, 16, 0 -> shl C, 4
   bool Fold = N2C && isNullConstant(N3) && N2C->getAPIntValue().isPowerOf2();
   bool Swap = N3C && isNullConstant(N2) && N3C->getAPIntValue().isPowerOf2();
 
   if ((Fold || Swap) &&
       TLI.getBooleanContents(CmpOpVT) ==
           TargetLowering::ZeroOrOneBooleanContent &&
-      (!LegalOperations || TLI.isOperationLegal(ISD::SETCC, CmpOpVT))) {
+      (!LegalOperations || TLI.isOperationLegal(ISD::SETCC, CmpOpVT)) &&
+      TLI.isOperationLegal(ISD::SHL, N2.getValueType())) {
 
     if (Swap) {
       CC = ISD::getSetCCInverse(CC, CmpOpVT.isInteger());
       std::swap(N2C, N3C);
     }
 
     // If the caller doesn't want us to simplify this into a zext of a compare,
     // don't do it.

llvm/lib/CodeGen/SelectionDAG/TargetLowering.cpp

if (!VT.isVector() || DCI.isBeforeLegalizeOps()) {
         return DAG.getSetCC(dl, VT, N0, ConstMinusOne, ISD::SETGT);
       }
     }
   }
 
   // Back to non-vector simplifications.
   // TODO: Can we do these for vector splats?
   if (auto *N1C = dyn_cast<ConstantSDNode>(N1.getNode())) {
+    const TargetLowering &TLI = DAG.getTargetLoweringInfo();
     const APInt &C1 = N1C->getAPIntValue();
 
     // Fold bit comparisons when we can.
     if ((Cond == ISD::SETEQ || Cond == ISD::SETNE) &&
         (VT == N0.getValueType() ||
          (isTypeLegal(VT) && VT.bitsLE(N0.getValueType()))) &&
         N0.getOpcode() == ISD::AND) {
       auto &DL = DAG.getDataLayout();
       if (auto *AndRHS = dyn_cast<ConstantSDNode>(N0.getOperand(1))) {
         EVT ShiftTy = getShiftAmountTy(N0.getValueType(), DL,
                                        !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.
-          if (AndRHS->getAPIntValue().isPowerOf2()) {
+          if (AndRHS->getAPIntValue().isPowerOf2() &&
+                AndRHS->getAPIntValue().logBase2() <= TLI.getShiftAmountThreshold(ShiftTy)) {
             return DAG.getNode(ISD::TRUNCATE, dl, VT,
                               DAG.getNode(ISD::SRL, dl, N0.getValueType(), N0,
                    DAG.getConstant(AndRHS->getAPIntValue().logBase2(), 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.
-          if (C1.isPowerOf2()) {
+          if (C1.isPowerOf2() && C1.logBase2() <= TLI.getShiftAmountThreshold(ShiftTy)) {
             return DAG.getNode(ISD::TRUNCATE, dl, VT,
                                DAG.getNode(ISD::SRL, dl, N0.getValueType(), N0,
                                       DAG.getConstant(C1.logBase2(), dl,
                                                       ShiftTy)));
           }
         }
       }
     }