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

[joanlluch]

Summary

This is a continuation of D68982, following community recommendations

Provides a TLI hook to allow targets to relax the emission of shifts, thus enabling codegen improvements on targets with no multiple shift instructions and cheap selects or branches.

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

Should be commited after D69099

This is part 1, defining the TLI hook, incorporating it in the MSP430 target, and using it in TagetLogwering.cpp.

[spatel]

llvm/include/llvm/CodeGen/TargetLowering.h

2614

It may not be used with vector types currently, but it would be safer to use:

VT.getScalarSizeInBits()

llvm/lib/CodeGen/SelectionDAG/TargetLowering.cpp

3621

This is probably not working as you expected because the shift type may not be the same as the value type.
I added an x86 test to demonstrate:
rL375158

3632–3634

Here and above the indentation looks non-standard. Use "clang-format" to correct.

[joanlluch]

llvm/include/llvm/CodeGen/TargetLowering.h

2614

okey

llvm/lib/CodeGen/SelectionDAG/TargetLowering.cpp

3621

Would passing the shift value (not the constant amount type) to getShiftAmountThreshold work in all cases?

3632–3634

I didn't know about clang-format. I see what you mean now. I will correct that.

[joanlluch]

llvm/lib/CodeGen/SelectionDAG/TargetLowering.cpp

3621

I mean passing the shift value type, not the shift value, of course., so in the case above would be TLI.getShiftAmountThreshold(N0.getValueType())
Would that look good?

[joanlluch]

Updated with latest suggestions

[spatel]

LGTM - see inline for a minor improvement.

Do you have commit access?

llvm/lib/CodeGen/SelectionDAG/TargetLowering.cpp

3611–3612

Within this block alone, we call N0.getValueType() at least 6 times. Better to make that a local variable like:

EVT N0VT = N0.getValueType();

[joanlluch]

llvm/lib/CodeGen/SelectionDAG/TargetLowering.cpp

3611–3612

Totally agree!, but I was a bit shy of touching code made by others.
Will do

[joanlluch]

In D69116#1715005, @spatel wrote:

LGTM - see inline for a minor improvement.

Do you have commit access?

Thanks for accepting this.
I don't have commit access. I would appreciate that you push it for me after I apply your last suggested improvement.

[joanlluch]

Move repeated calls to N0.getValueType() into a variable

[asl]

LGTM, thanks!

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();
+  }
+
   //===--------------------------------------------------------------------===//
   // 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/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();
+    EVT ShValTy = N0.getValueType();
 
     // Fold bit comparisons when we can.
     if ((Cond == ISD::SETEQ || Cond == ISD::SETNE) &&
-        (VT == N0.getValueType() ||
-         (isTypeLegal(VT) && VT.bitsLE(N0.getValueType()))) &&
+        (VT == ShValTy || (isTypeLegal(VT) && VT.bitsLE(ShValTy))) &&
         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());
+        EVT ShiftTy = getShiftAmountTy(ShValTy, 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(ShValTy)) {
             return DAG.getNode(ISD::TRUNCATE, dl, VT,
-                              DAG.getNode(ISD::SRL, dl, N0.getValueType(), N0,
-                   DAG.getConstant(AndRHS->getAPIntValue().logBase2(), dl,
-                                   ShiftTy)));
+                               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.
-          if (C1.isPowerOf2()) {
+          unsigned ShCt = C1.logBase2();
+          if (C1.isPowerOf2() &&
+              ShCt <= TLI.getShiftAmountThreshold(ShValTy)) {
             return DAG.getNode(ISD::TRUNCATE, dl, VT,
-                               DAG.getNode(ISD::SRL, dl, N0.getValueType(), N0,
-                                      DAG.getConstant(C1.logBase2(), dl,
-                                                      ShiftTy)));
+                               DAG.getNode(ISD::SRL, dl, ShValTy, N0,
+                                           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 {

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

 ; NOTE: Assertions have been autogenerated by utils/update_llc_test_checks.py
 ; RUN: llc -mtriple=msp430-- < %s | FileCheck %s
 
 define i16 @testSimplifySetCC_0(i16 %a) {
 ; CHECK-LABEL: testSimplifySetCC_0:
 ; CHECK:       ; %bb.0: ; %entry
-; CHECK-NEXT:    and #32, 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:    bit #32, r12
+; CHECK-NEXT:    mov r2, r12
+; CHECK-NEXT:    and #1, r12
 ; CHECK-NEXT:    ret
 entry:
   %and = and i16 %a, 32
   %cmp = icmp ne i16 %and, 0
   %conv = zext i1 %cmp to i16
   ret i16 %conv
 }
 
 define i16 @testSimplifySetCC_1(i16 %a) {
 ; CHECK-LABEL: testSimplifySetCC_1:
 ; CHECK:       ; %bb.0: ; %entry
-; CHECK-NEXT:    and #32, 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:    bit #32, r12
+; CHECK-NEXT:    mov r2, r12
+; CHECK-NEXT:    and #1, r12
 ; CHECK-NEXT:    ret
 entry:
   %and = and i16 %a, 32
   %cmp = icmp eq i16 %and, 32
   %conv = zext i1 %cmp to i16
   ret i16 %conv
 }