[TargetLowering][DAGCombine][MSP430] Shift Amount Threshold in DAGCombine

[joanlluch]

Summary

This is a proposal of a TLI hook to allow targets to relax the emission of shifts (Replaces D68957)

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

(please note that the diff is from Release/9.x)

Provides codegen improvements on current and future targets with no multiple shift instructions and cheap selects or branches.

For example for the MSP430, the following IR:

; Function Attrs: norecurse nounwind readnone
define dso_local i16 @test2(i16 %a) local_unnamed_addr #0 {
entry:
  %cmp = icmp slt i16 %a, 0
  %cond = select i1 %cmp, i16 2, i16 0
  ret i16 %cond
}

; Function Attrs: norecurse nounwind readnone
define dso_local i16 @test3(i16 %a) local_unnamed_addr #0 {
entry:
  %cmp = icmp slt i16 %a, 0
  %cond = select i1 %cmp, i16 3, i16 0
  ret i16 %cond
}

; Function Attrs: norecurse nounwind readnone
define dso_local i16 @test4(i16 %a, i16 %b) local_unnamed_addr #0 {
entry:
  %cmp = icmp sgt i16 %a, %b
  %cond = select i1 %cmp, i16 32, i16 0
  ret i16 %cond
}

gets translated into this before the patch:

	.globl	test2
	.p2align	1
	.type	test2,@function
test2:
	swpb	r12
	mov.b	r12, r12
	clrc
	rrc	r12
	rra	r12
	rra	r12
	rra	r12
	rra	r12
	rra	r12
	and	#2, r12
	ret
.Lfunc_end0:
	.size	test2, .Lfunc_end0-test2

	.globl	test3
	.p2align	1
	.type	test3,@function
test3:
	swpb	r12
	sxt	r12
	rra	r12
	rra	r12
	rra	r12
	rra	r12
	rra	r12
	rra	r12
	rra	r12
	and	#3, r12
	ret
.Lfunc_end1:
	.size	test3, .Lfunc_end1-test3

	.globl	test4
	.p2align	1
	.type	test4,@function
test4:
	mov	r12, r14
	mov	#1, r12
	cmp	r14, r13
	jl	.LBB2_2
	clr	r12
.LBB2_2:
	add	r12, r12
	add	r12, r12
	add	r12, r12
	add	r12, r12
	add	r12, r12
	ret
.Lfunc_end2:
	.size	test4, .Lfunc_end2-test4

After applying the patch, the above code turns into:

	.globl	test2
	.p2align	1
	.type	test2,@function
test2:
	mov	r12, r13
	mov	#1, r12
	tst	r13
	jl	.LBB0_2
	clr	r12
.LBB0_2:
	add	r12, r12
	ret
.Lfunc_end0:
	.size	test2, .Lfunc_end0-test2

	.globl	test3
	.p2align	1
	.type	test3,@function
test3:
	mov	r12, r13
	mov	#3, r12
	tst	r13
	jl	.LBB1_2
	clr	r12
.LBB1_2:
	ret
.Lfunc_end1:
	.size	test3, .Lfunc_end1-test3

	.globl	test4
	.p2align	1
	.type	test4,@function
test4:
	mov	r12, r14
	mov	#32, r12
	cmp	r14, r13
	jl	.LBB2_2
	clr	r12
.LBB2_2:
	ret
.Lfunc_end2:
	.size	test4, .Lfunc_end2-test4

[spatel]

I understand the direction, and I think there's general agreement on it (adding some more potential reviewers based on the bug report and llvm-dev thread), but:

1. Add the tests in the patch description to a file in test/CodeGen/MSP430 as an NFC commit *before* applying this patch. Generate baseline test assertions for current asm using utils/update_llc_test_checks.py.
2. Split this patch up. In the 1st step, we can add the TLI hook and 1-2 usages of that hook that show a test diff for MSP430. Ideally, we can add small tests for each proposed usage of the TLI hook.

llvm/lib/CodeGen/SelectionDAG/DAGCombiner.cpp

9496

Formatting: extra space after parenthesis here.
Several places below have the same problem.

[spatel]

Also, I have no knowledge of MSP430, and I don't see a code owner for this target. cc @asl @krisb based on D54623.

[asl]

The MSP430 changes / overall direction looks extremely useful to me. We just need to ensure everything is done properly. This is exactly what @spatel proposed.

I will be happy to review all MSP430 stuff :)

[joanlluch]

Hi @spatel
Thank you for your support. I'll try to do what you suggest regarding generating of baseline tests and splitting the patch.

My primary interest is proposing LLVM improvements that will benefit targets of the MSP430 kind, but -just to clarify- I only know what I learned online about that particular target. In fact, I have little practical interest on it, except that it allows me to show the validity of my proposed patches. The same can be said about the 'experimental' AVR target. The AVR is even more benefited from this patch, but I am not even showing it. It would be REALLY nice to get some involvement (or just feedback) from people who implemented or worked on these targets in the past, because I am not able to work on them.

So, given the above, I want to ask whether there would be a generic (or target independent) way to show the effects of this patch. Ideally, given some IR input, demonstrate that the output will minimise the generation of expensive shifts, which some targets will benefit of. It's understandable that showing this in the context of a particular trunk target makes it easier to get approval, but as I am relatively new to LLVM development, I still wonder if there's a target independent way to show the same. Any help would be appreciated.

Thanks.

[asl]

@joanlluch There are two things here. We understand that there might be some out-of-tree targets that would benefit from changes in the mainline. However, it is still important to add tests that utilize mainline targets as this ensures that the proposed changes won't e.g. break during some refactoring, etc. So, using MSP430 (probably the smallest) / AVR is perfectly fine for tests, etc.!

[joanlluch]

In D68982#1710529, @asl wrote:

The MSP430 changes / overall direction looks extremely useful to me. We just need to ensure everything is done properly. This is exactly what @spatel proposed.

I will be happy to review all MSP430 stuff :)

Hi,
Sorry, I somehow missed your post before I posted my last one. Thanks for that.

[joanlluch]

In D68982#1710606, @asl wrote:

@joanlluch There are two things here. We understand that there might be some out-of-tree targets that would benefit from changes in the mainline. However, it is still important to add tests that utilize mainline targets as this ensures that the proposed changes won't e.g. break during some refactoring, etc. So, using MSP430 (probably the smallest) / AVR is perfectly fine for tests, etc.!

I fully understand and agree on that, and I will adhere to it. Still, I found some few cases of LLVM improvements regarding the direction of this patch, that will not fully show on MSP430 because of reversals implemented in the target itself, but I will try to make mentions of them in due term. Thanks again for your support.

[asl]

If they are not necessary, then it would make sense to undo them. At least partially.

[joanlluch]

I know this is possibly not the right place to ask this particular question, but I thought that I would get a more focused reply by asking here:

I am stuck now on how to create test files. I created a file shift-amount-threshold.ll with the IR code to test, that compiles fine with llc. Tried to run update_llc_test_checks.py on that file, like this:

/Users/joan/LLVM-9/llvm-project/llvm/utils/update_llc_test_checks.py --llc-binary /Users/joan/LLVM-9/llvm-project/build/Debug/bin/llc /Users/joan/Documents-Local/Relay/RelayNouTest/shift-amount-threshold.ll

but I get the following error:

Traceback (most recent call last):
  File "/Users/joan/LLVM-9/llvm-project/llvm/utils/update_llc_test_checks.py", line 187, in <module>
    main()
  File "/Users/joan/LLVM-9/llvm-project/llvm/utils/update_llc_test_checks.py", line 128, in main
    triple, prefixes, func_dict)
  File "/Users/joan/LLVM-9/llvm-project/llvm/utils/UpdateTestChecks/asm.py", line 335, in build_function_body_dictionary_for_triple
    raise KeyError('Triple %r is not supported' % (triple))
KeyError: "Triple 'msp430' is not supported"

Looked at llvm/utils/UpdateTestChecks/asm.py line 335, and found that "msp430" is not listed there (?).

It's the first time for me at this. What am doing wrong?.
Thanks in advance for any help.

[lebedev.ri]

You need to work on svn trunk.

[spatel]

In D68982#1711031, @lebedev.ri wrote:

You need to work on svn trunk.

That would be best/easiest. See here for preliminary steps/example commits:
https://bugs.llvm.org/show_bug.cgi?id=43542#c3

[joanlluch]

Follow ups in D69099 , D69116 and D69120

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 creating shifts above the returned value will be avoided.
+  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);
+    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(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();
+      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 (LegalTypes) {
       Temp = DAG.getNode(ISD::ZERO_EXTEND, SDLoc(N2), VT, SCC);
     }
 
     AddToWorklist(SCC.getNode());
     AddToWorklist(Temp.getNode());
 
     if (N2C->isOne())
       return Temp;
     
+    unsigned ShCt = N2C->getAPIntValue().logBase2();
+    EVT ShiftAmtTy = Temp.getValueType();
+    if ( ShCt > TLI.getShiftAmountThreshold(ShiftAmtTy))
+      return SDValue();
+
     // shl setcc result by log2 n2c
     return DAG.getNode(ISD::SHL, DL, N2.getValueType(), Temp,
-                       DAG.getConstant(N2C->getAPIntValue().logBase2(),
+                       DAG.getConstant(ShCt,
                                        SDLoc(Temp),
-                                       getShiftAmountTy(Temp.getValueType())));
+                                       getShiftAmountTy(ShiftAmtTy)));
+    
   }
 
   // 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)
   // select_cc setne X, 0, ctlz_zero_undef(X), sizeof(X) -> ctlz(X)

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()) {
+          unsigned ShCt = AndRHS->getAPIntValue().logBase2();
+          if (AndRHS->getAPIntValue().isPowerOf2() &&
+                ShCt <= 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)));
+                              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.
-          if (C1.isPowerOf2()) {
+          unsigned ShCt = C1.logBase2();
+          if (C1.isPowerOf2() && ShCt <= TLI.getShiftAmountThreshold(ShiftTy)) {
             return DAG.getNode(ISD::TRUNCATE, dl, VT,
                                DAG.getNode(ISD::SRL, dl, N0.getValueType(), N0,
-                                      DAG.getConstant(C1.logBase2(), dl,
-                                                      ShiftTy)));
+                                      DAG.getConstant(ShCt, dl, ShiftTy)));
           }
         }
       }
     }
 
     if (C1.getMinSignedBits() <= 64 &&
         !isLegalICmpImmediate(C1.getSExtValue())) {
       // (X & -256) == 256 -> (X >> 8) == 1

llvm/lib/Target/MSP430/MSP430ISelLowering.h

public:
     /// registers. Also, if isTruncateFree(Ty2, Ty1) is true, this does not
     /// 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;
 
+
+    unsigned getShiftAmountThreshold(EVT VT) const override;
+    
     MachineBasicBlock *
     EmitInstrWithCustomInserter(MachineInstr &MI,
                                 MachineBasicBlock *BB) const override;
     MachineBasicBlock *EmitShiftInstr(MachineInstr &MI,
                                       MachineBasicBlock *BB) const;
 
   private:
     SDValue LowerCCCCallTo(SDValue Chain, SDValue Callee,

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");
   }
 }
 
+unsigned MSP430TargetLowering::getShiftAmountThreshold(EVT VT) const {
+  return 2;
+}
+
 //===----------------------------------------------------------------------===//
 //                       MSP430 Inline Assembly Support
 //===----------------------------------------------------------------------===//
 
 /// getConstraintType - Given a constraint letter, return the type of
 /// constraint it is for this target.
 TargetLowering::ConstraintType
 MSP430TargetLowering::getConstraintType(StringRef Constraint) const {