[TargetLowering][DAGCombine][MSP430] Shift Amount Threshold in DAGCombine (2/2)

[joanlluch]

Summary

Continuation of D69116

Contributes to a Fix for https://bugs.llvm.org/show_bug.cgi?id=43559

Should be commited after D69099 and D69116

Using the TLI hook in DAGCombine.cpp.

[joanlluch]

Made sure the updated diff file accounts for recent trunk changes

[joanlluch]

Code style correction

[spatel]

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

50

Do we have test coverage for each code diff?
It would be good to add a code comment for each test that describes the transform that we are trying to avoid.
For example, this one could copy the formula from the corresponding source code comment:

// sext i1 (setgt iN X, -1) --> sra (not X), (N - 1)

[spatel]

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

50

Also, the IR does not correspond exactly to that comment. It's fine to include tests with 'select', but if there is an intermediate transform that turns it into 'sext' or 'zext', then we should have a test that begins with that pattern in IR too if possible. We want to make sure that we do not accidentally bypass these changes with future patches.

[joanlluch]

Updated tests to reflect each covered case in an independent way with more focused IR patterns.
Added comments to the test file that refer to the transformation we are dealing with.

[joanlluch]

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

50

I updated the test file as per your suggestion. Test cases are now focused on the individual transformations that we are trying to avoid. I also changed the IR to avoid intermediate transformations and focus on the pattern of interest.
Unfortunately, these changes implied some depart from the 'baseline' tests that were posted before, and thus the diff appears now a bit mixed, but I think it is still informative enough to see the improvements.

[joanlluch]

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

50

Ok, please forget for now about this diff. I will insert a new ‘baseline’ tests commit so that at least the test diffs here shows up hopefully cleaner.

[joanlluch]

I created a new baseline revision, D69609, that help to better reflect the effects of applying this patch. The referred revision should therefore be applied before this one for consistency reasons.

[joanlluch]

@spatel I updated this revision diff according to your suggestions. I also created a new baseline test revision to help identify the effects of this patch. I hope this is ok. Thanks in advance for your time.

[joanlluch]

@asl I identified you as the creator of the MSP430 patch that optimised 8 bit and larger shifts by combining them with bswap and extend instructions. This creates relatively cheap instruction sequences for exactly 8 bit shifts.

I am considering replacing my current implementation of getShiftAmountThreshold, by a version that passes the intended shift amount as a parameter and returns a boolean. For example, let's say that we have

bool shouldAvoidTransformToShift(EVT VT, unsigned amount) const override;

Which would return false by default.

For the MSP430 it could be implemented like this

bool MSP430TargetLowering::shouldAvoidTransformToShift(EVT VT, unsigned amount) const {
  return !(amount == 8 || amount<=2);
}

Would this make sense for the MSP430?

Thanks.

[asl]

@joanlluch Yes, having the version with amount does make sense as target may know how to efficiently lower some of the shifts with crazy tricks. And in the view of this patch it's easier to preserve the sequences rather than match and undo later. I guess for MSP430 we'd need to allow 9 as possible "special" shift value, as select is lowered to 3 instructions (test + branch + mov of some kind) and removing branch overall has some additional value like allowing more code folding / reducing register pressure.

[joanlluch]

Updated diff to account for the latest trunk changes

[joanlluch]

@asl Ok thanks, I agree that 9 bit shifts may also benefit from the version with amount.
If this is ok, I will propose the TLI function replacement on a different patch after this is reviewed, to keep things organised.

[spatel]

LGTM

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

119–137

Looks like the spelling fix was not updated here. You have to run the script again to regenerate the CHECK lines if you change the test source code.

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);
+    unsigned ShCt = VT.getSizeInBits() - 1;
+    const TargetLowering &TLI = DAG.getTargetLoweringInfo();
+    if ( ShCt <= TLI.getShiftAmountThreshold(VT)) {
       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;
+      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::visitSIGN_EXTEND(SDNode *N) {
   SDValue N0 = N->getOperand(0);
   EVT VT = N->getValueType(0);
   SDLoc DL(N);
 
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)) {
       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))
+    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());
   }
 
if (SDValue V = foldSelectCCToShiftAnd(DL, N0, N1, N2, N3, CC))
     return V;
 
   // fold (select_cc seteq (and x, y), 0, 0, A) -> (and (shr (shl x)) A)
   // where y is has a single bit set.
   // A plaintext description would be, we can turn the SELECT_CC into an AND
   // when the condition can be materialized as an all-ones register.  Any
   // single bit-test can be materialized as an all-ones register with
   // shift-left and shift-right-arith.
-  // TODO: The operation legality checks could be loosened to include "custom",
-  //       but that may cause regressions for targets that do not have shift
-  //       instructions.
   if (CC == ISD::SETEQ && N0->getOpcode() == ISD::AND &&
-      N0->getValueType(0) == VT && isNullConstant(N1) && isNullConstant(N2) &&
-      TLI.isOperationLegal(ISD::SHL, VT) &&
-      TLI.isOperationLegal(ISD::SRA, VT)) {
+      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)) {
         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.
+        // 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),
+          DAG.getConstant(ShCt, 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 &&
if ((Fold || Swap) &&
     }
 
     AddToWorklist(SCC.getNode());
     AddToWorklist(Temp.getNode());
 
     if (N2C->isOne())
       return Temp;
 
+    unsigned ShCt = N2C->getAPIntValue().logBase2();
+    if ( ShCt > TLI.getShiftAmountThreshold(VT))
+      return SDValue();
+
     // shl setcc result by log2 n2c
     return DAG.getNode(ISD::SHL, DL, N2.getValueType(), Temp,
-                       DAG.getConstant(N2C->getAPIntValue().logBase2(),
-                                       SDLoc(Temp),
+                       DAG.getConstant(ShCt, SDLoc(Temp),
                                        getShiftAmountTy(Temp.getValueType())));
   }
 
   // select_cc seteq X, 0, sizeof(X), ctlz(X) -> ctlz(X)
   // select_cc seteq X, 0, sizeof(X), ctlz_zero_undef(X) -> ctlz(X)
   // select_cc seteq X, 0, sizeof(X), cttz(X) -> cttz(X)
   // select_cc seteq X, 0, sizeof(X), cttz_zero_undef(X) -> cttz(X)
   // select_cc setne X, 0, ctlz(X), sizeof(X) -> ctlz(X)

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

 ; CHECK-NEXT:    ret
 entry:
   %and = and i16 %a, 2048
   %cmp = icmp eq i16 %and, 0
   %cond = select i1 %cmp, i16 0, i16 3
   ret i16 %cond
 }
 
 define i16 @testExtendSignBit(i16 %a) {
 ; CHECK-LABEL: testExtendSignBit:
 ; CHECK:       ; %bb.0: ; %entry
-; CHECK-NEXT:    inv r12
-; CHECK-NEXT:    swpb r12
-; CHECK-NEXT:    mov.b r12, r12
-; CHECK-NEXT:    clrc
-; CHECK-NEXT:    rrc r12
-; CHECK-NEXT:    rra r12
-; CHECK-NEXT:    rra r12
-; CHECK-NEXT:    rra r12
-; CHECK-NEXT:    rra r12
-; CHECK-NEXT:    rra r12
-; CHECK-NEXT:    rra r12
+; CHECK-NEXT:    mov r12, r13
+; CHECK-NEXT:    mov #1, r12
+; CHECK-NEXT:    tst r13
+; CHECK-NEXT:    jge .LBB3_2
+; CHECK-NEXT:  ; %bb.1: ; %entry
+; CHECK-NEXT:    clr r12
+; CHECK-NEXT:  .LBB3_2: ; %entry
 ; CHECK-NEXT:    ret
 entry:
   %cmp = icmp sgt i16 %a, -1
   %cond = select i1 %cmp, i16 1, i16 0
   ret i16 %cond
 }
 
 define i16 @testShiftAnd_0(i16 %a) {
 ; CHECK-LABEL: testShiftAnd_0:
 ; CHECK:       ; %bb.0: ; %entry
-; CHECK-NEXT:    swpb r12
-; CHECK-NEXT:    sxt r12
-; CHECK-NEXT:    rra r12
-; CHECK-NEXT:    rra r12
-; CHECK-NEXT:    rra r12
-; CHECK-NEXT:    rra r12
-; CHECK-NEXT:    rra r12
-; CHECK-NEXT:    rra r12
-; CHECK-NEXT:    rra r12
+; CHECK-NEXT:    mov r12, r13
+; CHECK-NEXT:    mov #-1, r12
+; CHECK-NEXT:    tst r13
+; CHECK-NEXT:    jl .LBB4_2
+; CHECK-NEXT:  ; %bb.1: ; %entry
+; CHECK-NEXT:    clr r12
+; CHECK-NEXT:  .LBB4_2: ; %entry
 ; CHECK-NEXT:    ret
 entry:
   %cmp = icmp slt i16 %a, 0
   %cond = select i1 %cmp, i16 -1, i16 0
   ret i16 %cond
 }
 
 define i16 @testShiftAnd_1(i16 %a) {
 ; CHECK-LABEL: testShiftAnd_1:
 ; CHECK:       ; %bb.0: ; %entry
-; CHECK-NEXT:    swpb r12
-; CHECK-NEXT:    mov.b r12, r12
-; CHECK-NEXT:    clrc
-; CHECK-NEXT:    rrc r12
-; CHECK-NEXT:    rra r12
-; CHECK-NEXT:    rra r12
-; CHECK-NEXT:    rra r12
-; CHECK-NEXT:    rra r12
-; CHECK-NEXT:    rra r12
-; CHECK-NEXT:    rra r12
+; CHECK-NEXT:    mov r12, r13
+; CHECK-NEXT:    mov #1, r12
+; CHECK-NEXT:    tst r13
+; CHECK-NEXT:    jl .LBB5_2
+; CHECK-NEXT:  ; %bb.1: ; %entry
+; CHECK-NEXT:    clr r12
+; CHECK-NEXT:  .LBB5_2: ; %entry
 ; CHECK-NEXT:    ret
 entry:
   %cmp = icmp slt i16 %a, 0
   %cond = select i1 %cmp, i16 1, i16 0
   ret i16 %cond
 }
 
 define i16 @testShiftAnd_2(i16 %a) {
 ; CHECK-LABEL: testShiftAnd_2:
 ; CHECK:       ; %bb.0: ; %entry
-; CHECK-NEXT:    swpb r12
-; CHECK-NEXT:    mov.b r12, r12
-; CHECK-NEXT:    clrc
-; CHECK-NEXT:    rrc r12
-; CHECK-NEXT:    rra r12
-; CHECK-NEXT:    rra r12
-; CHECK-NEXT:    rra r12
-; CHECK-NEXT:    rra r12
-; CHECK-NEXT:    rra r12
-; CHECK-NEXT:    and #2, r12
+; CHECK-NEXT:    mov r12, r13
+; CHECK-NEXT:    mov #1, r12
+; CHECK-NEXT:    tst r13
+; CHECK-NEXT:    jl .LBB6_2
+; CHECK-NEXT:  ; %bb.1: ; %entry
+; CHECK-NEXT:    clr r12
+; CHECK-NEXT:  .LBB6_2: ; %entry
+; CHECK-NEXT:    add r12, r12
 ; CHECK-NEXT:    ret
 entry:
   %cmp = icmp slt i16 %a, 0
   %cond = select i1 %cmp, i16 2, i16 0
   ret i16 %cond
 }
 
 define i16 @testShiftAnd_3(i16 %a) {
 ; CHECK-LABEL: testShiftAnd_3:
 ; CHECK:       ; %bb.0: ; %entry
-; CHECK-NEXT:    swpb r12
-; CHECK-NEXT:    sxt r12
-; CHECK-NEXT:    rra r12
-; CHECK-NEXT:    rra r12
-; CHECK-NEXT:    rra r12
-; CHECK-NEXT:    rra r12
-; CHECK-NEXT:    rra r12
-; CHECK-NEXT:    rra r12
-; CHECK-NEXT:    rra r12
-; CHECK-NEXT:    and #3, r12
+; CHECK-NEXT:    mov r12, r13
+; CHECK-NEXT:    mov #3, r12
+; CHECK-NEXT:    tst r13
+; CHECK-NEXT:    jl .LBB7_2
+; CHECK-NEXT:  ; %bb.1: ; %entry
+; CHECK-NEXT:    clr r12
+; CHECK-NEXT:  .LBB7_2: ; %entry
 ; CHECK-NEXT:    ret
 entry:
   %cmp = icmp slt i16 %a, 0
   %cond = select i1 %cmp, i16 3, i16 0
   ret i16 %cond
 }
 
 define i16 @testShiftAnd_4(i16 %a, i16 %b) {
 ; CHECK-LABEL: testShiftAnd_4:
 ; CHECK:       ; %bb.0: ; %entry
 ; CHECK-NEXT:    mov r12, r14
-; CHECK-NEXT:    mov #1, r12
+; CHECK-NEXT:    mov #32, r12
 ; CHECK-NEXT:    cmp r14, r13
 ; CHECK-NEXT:    jl .LBB8_2
 ; CHECK-NEXT:  ; %bb.1: ; %entry
 ; CHECK-NEXT:    clr r12
 ; CHECK-NEXT:  .LBB8_2: ; %entry
-; CHECK-NEXT:    add r12, r12
-; CHECK-NEXT:    add r12, r12
-; CHECK-NEXT:    add r12, r12
-; CHECK-NEXT:    add r12, r12
-; CHECK-NEXT:    add r12, r12
 ; CHECK-NEXT:    ret
 entry:
   %cmp = icmp sgt i16 %a, %b
   %cond = select i1 %cmp, i16 32, i16 0
   ret i16 %cond
 }