[PowerPC, DAGCombiner] Fold a << (b % (sizeof(a) * 8)) back to a single instruction

[timshen]

Summary

This is the corresponding llvm change to D28037 to ensure no performance
regression.

[nemanjai]

llvm/lib/Target/PowerPC/PPCISelLowering.h

999

I don't think this is the case with every shift instruction. Please see the test case below.

llvm/test/CodeGen/PowerPC/shift_mask.ll

25

The results before and after when 31 < b < 64 are different. I don't think this is a safe transformation in this case. The reason being that as the ISA states:

Shift amounts from 32 to 63 give a zero result.

[timshen]

Don't mis-optimize non-vector cases.

[timshen]

Only optimize legal instructions.

I feel like needing a separate patch to add some test cases for illegal vector instructions (that get lowered to scalar instructions), and those shouldn't be combined. I need to investigate how to make those instructions illegal.

[nemanjai]

llvm/lib/Target/PowerPC/PPCISelLowering.h

1004

I think this will exclude the scalar versions as well as any that will be scalarized. However, it'll also exclude versions that will be legalized in different ways (i.e. without scalarization). Wouldn't we want something that more closely reflects what we are looking for (i.e. the type will remain a vector after legalization)? Perhaps something along the lines of:

Index: lib/Target/PowerPC/PPCISelLowering.h
===================================================================
--- lib/Target/PowerPC/PPCISelLowering.h        (revision 290968)
+++ lib/Target/PowerPC/PPCISelLowering.h        (working copy)
@@ -996,6 +996,14 @@ namespace llvm {
     SDValue
       combineElementTruncationToVectorTruncation(SDNode *N,
                                                  DAGCombinerInfo &DCI) const;
+
+    bool supportsModuloShift(ISD::NodeType Inst, EVT ReturnType,
+                             const SelectionDAG &DAG) const override {
+      assert((Inst == ISD::SHL || Inst == ISD::SRA || Inst == ISD::SRL) &&
+             "Expect a shift instruction");
+      EVT LegalizedType = getTypeToTransformTo(*DAG.getContext(), ReturnType);
+      return isOperationLegal(Inst, LegalizedType) && LegalizedType.isVector();
+    }
   };
 
   namespace PPC {

[timshen]

llvm/lib/Target/PowerPC/PPCISelLowering.h

1004

+ EVT LegalizedType = getTypeToTransformTo(*DAG.getContext(), ReturnType);
+ return isOperationLegal(Inst, LegalizedType) && LegalizedType.isVector();

Let's say isOperationLegal(Inst, LegalizedType) && LegalizedType.isVector(); is true, and we do the combine. However, later Inst turns into Inst' during the legalization, where Inst' might be any instruction that carries no modulo semantic. Won't that be a mis-combine?

[nemanjai]

llvm/lib/Target/PowerPC/PPCISelLowering.h

1004

I'm not sure I follow why the node would be transformed to something else if type legalization will legalize the type to LegalizedType and we've already determined that the operation is legal.

In any case, it seems like we might want to run this combine only after legalization. I think that in that case, we'd get the semantics we're after. And I think it makes sense for other targets too as the target may not be able to definitively say whether it supports modulo shift semantics until it knows everything about the operation and type.

[timshen]

Move the legalization check to the caller sides.

llvm/lib/Target/PowerPC/PPCISelLowering.h

1004

Agreed. I move the legalization check to the caller sides.

[timshen]

Ping?

[iteratee]

It looks fine to me.

[iteratee]

Did you ever commit this?

llvm/include/llvm/Target/TargetLowering.h

public:
   }
 
   // Return true if it is profitable to use a scalar input to a BUILD_VECTOR
   // even if the vector itself has multiple uses.
   virtual bool aggressivelyPreferBuildVectorSources(EVT VecVT) const {
     return false;
   }
 
+  // Return true if the instruction that performs a << b actually performs
+  // a << (b % (sizeof(a) * 8)).
+  virtual bool supportsModuloShift(ISD::NodeType Inst, EVT ReturnType) const {
+    assert((Inst == ISD::SHL || Inst == ISD::SRA || Inst == ISD::SRL) &&
+           "Expect a shift instruction");
+    return false;
+  }
+
   //===--------------------------------------------------------------------===//
   // 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

if (N1CV && N1CV->isConstant()) {
           if (SDValue C = DAG.FoldConstantArithmetic(ISD::SHL, SDLoc(N), VT,
                                                      N01CV, N1CV))
             return DAG.getNode(ISD::AND, SDLoc(N), VT, N00, C);
         }
       }
     }
   }
 
+  // If the target supports masking y in (shl, y),
+  // fold (shl x, (and y, ((1 << numbits(x)) - 1))) -> (shl x, y)
+  if (TLI.supportsModuloShift((ISD::NodeType)N->getOpcode(), VT) &&
+      N1->getOpcode() == ISD::AND) {
+    if (ConstantSDNode *Mask = isConstOrConstSplat(N1->getOperand(1))) {
+      if (Mask->getZExtValue() == OpSizeInBits - 1) {
+        return DAG.getNode(ISD::SHL, SDLoc(N), VT, N0, N1->getOperand(0));
+      }
+    }
+  }
+
   ConstantSDNode *N1C = isConstOrConstSplat(N1);
 
   // fold (shl c1, c2) -> c1<<c2
   ConstantSDNode *N0C = getAsNonOpaqueConstant(N0);
   if (N0C && N1C && !N1C->isOpaque())
     return DAG.FoldConstantArithmetic(ISD::SHL, SDLoc(N), VT, N0C, N1C);
   // fold (shl 0, x) -> 0
   if (isNullConstant(N0))

 }
 
 SDValue DAGCombiner::visitSRA(SDNode *N) {
   SDValue N0 = N->getOperand(0);
   SDValue N1 = N->getOperand(1);
   EVT VT = N0.getValueType();
   unsigned OpSizeInBits = VT.getScalarSizeInBits();
 
+  // If the target supports masking y in (sra, y),
+  // fold (sra x, (and y, ((1 << numbits(x)) - 1))) -> (sra x, y)
+  if (TLI.supportsModuloShift((ISD::NodeType)N->getOpcode(), VT) &&
+      N1->getOpcode() == ISD::AND) {
+    if (ConstantSDNode *Mask = isConstOrConstSplat(N1->getOperand(1))) {
+      if (Mask->getZExtValue() == OpSizeInBits - 1) {
+        return DAG.getNode(ISD::SRA, SDLoc(N), VT, N0, N1->getOperand(0));
+      }
+    }
+  }
+
   // Arithmetic shifting an all-sign-bit value is a no-op.
   if (DAG.ComputeNumSignBits(N0) == OpSizeInBits)
     return N0;
 
   // fold vector ops
   if (VT.isVector())
     if (SDValue FoldedVOp = SimplifyVBinOp(N))
       return FoldedVOp;

 }
 
 SDValue DAGCombiner::visitSRL(SDNode *N) {
   SDValue N0 = N->getOperand(0);
   SDValue N1 = N->getOperand(1);
   EVT VT = N0.getValueType();
   unsigned OpSizeInBits = VT.getScalarSizeInBits();
 
+  // If the target supports masking y in (srl, y),
+  // fold (srl x, (and y, ((1 << numbits(x)) - 1))) -> (srl x, y)
+  if (TLI.supportsModuloShift((ISD::NodeType)N->getOpcode(), VT) &&
+      N1->getOpcode() == ISD::AND) {
+    if (ConstantSDNode *Mask = isConstOrConstSplat(N1->getOperand(1))) {
+      if (Mask->getZExtValue() == OpSizeInBits - 1) {
+        return DAG.getNode(ISD::SRL, SDLoc(N), VT, N0, N1->getOperand(0));
+      }
+    }
+  }
+
   // fold vector ops
   if (VT.isVector())
     if (SDValue FoldedVOp = SimplifyVBinOp(N))
       return FoldedVOp;
 
   ConstantSDNode *N1C = isConstOrConstSplat(N1);
 
   // fold (srl c1, c2) -> c1 >>u c2

llvm/lib/Target/PowerPC/PPCISelLowering.h

SDValue getRecipEstimate(SDValue Operand, SelectionDAG &DAG, int Enabled,
                              int &RefinementSteps) const override;
     unsigned combineRepeatedFPDivisors() const override;
 
     CCAssignFn *useFastISelCCs(unsigned Flag) const;
 
     SDValue
       combineElementTruncationToVectorTruncation(SDNode *N,
                                                  DAGCombinerInfo &DCI) const;
+
+    bool supportsModuloShift(ISD::NodeType Inst,
+                             EVT ReturnType) const override {
+      assert((Inst == ISD::SHL || Inst == ISD::SRA || Inst == ISD::SRL) &&
+             "Expect a shift instruction");
+      return true;
+    }
   };
 
   namespace PPC {
     FastISel *createFastISel(FunctionLoweringInfo &FuncInfo,
                              const TargetLibraryInfo *LibInfo);
   }
 
   bool CC_PPC32_SVR4_Custom_Dummy(unsigned &ValNo, MVT &ValVT, MVT &LocVT,

llvm/test/CodeGen/PowerPC/shift_mask.ll

 ; NOTE: Assertions have been autogenerated by utils/update_llc_test_checks.py
 ; RUN: llc < %s | FileCheck %s
 target triple = "powerpc64le-linux-gnu"
 
 define i8 @test000(i8 %a, i8 %b) {
 ; CHECK-LABEL: test000:
 ; CHECK:       # BB#0:
-; CHECK-NEXT:    rlwinm 4, 4, 0, 29, 31
 ; CHECK-NEXT:    slw 3, 3, 4
 ; CHECK-NEXT:    blr
   %rem = and i8 %b, 7
   %shl = shl i8 %a, %rem
   ret i8 %shl
 }
 
 define i16 @test001(i16 %a, i16 %b) {
 ; CHECK-LABEL: test001:
 ; CHECK:       # BB#0:
-; CHECK-NEXT:    rlwinm 4, 4, 0, 28, 31
 ; CHECK-NEXT:    slw 3, 3, 4
 ; CHECK-NEXT:    blr
   %rem = and i16 %b, 15
   %shl = shl i16 %a, %rem
   ret i16 %shl
 }
 
 define i32 @test002(i32 %a, i32 %b) {
 ; CHECK-LABEL: test002:
 ; CHECK:       # BB#0:
-; CHECK-NEXT:    rlwinm 4, 4, 0, 27, 31
 ; CHECK-NEXT:    slw 3, 3, 4
 ; CHECK-NEXT:    blr
   %rem = and i32 %b, 31
   %shl = shl i32 %a, %rem
   ret i32 %shl
 }
 
 define i64 @test003(i64 %a, i64 %b) {
 ; CHECK-LABEL: test003:
 ; CHECK:       # BB#0:
-; CHECK-NEXT:    rlwinm 4, 4, 0, 26, 31
 ; CHECK-NEXT:    sld 3, 3, 4
 ; CHECK-NEXT:    blr
   %rem = and i64 %b, 63
   %shl = shl i64 %a, %rem
   ret i64 %shl
 }
 
 define <16 x i8> @test010(<16 x i8> %a, <16 x i8> %b) {
 ; CHECK-LABEL: test010:
 ; CHECK:       # BB#0:
-; CHECK-NEXT:    vspltisb 4, 7
-; CHECK-NEXT:    xxland 35, 35, 36
 ; CHECK-NEXT:    vslb 2, 2, 3
 ; CHECK-NEXT:    blr
   %rem = and <16 x i8> %b, <i8 7, i8 7, i8 7, i8 7, i8 7, i8 7, i8 7, i8 7, i8 7, i8 7, i8 7, i8 7, i8 7, i8 7, i8 7, i8 7>
   %shl = shl <16 x i8> %a, %rem
   ret <16 x i8> %shl
 }
 
 define <8 x i16> @test011(<8 x i16> %a, <8 x i16> %b) {
 ; CHECK-LABEL: test011:
 ; CHECK:       # BB#0:
-; CHECK-NEXT:    vspltish 4, 15
-; CHECK-NEXT:    xxland 35, 35, 36
 ; CHECK-NEXT:    vslh 2, 2, 3
 ; CHECK-NEXT:    blr
   %rem = and <8 x i16> %b, <i16 15, i16 15, i16 15, i16 15, i16 15, i16 15, i16 15, i16 15>
   %shl = shl <8 x i16> %a, %rem
   ret <8 x i16> %shl
 }
 
 define <4 x i32> @test012(<4 x i32> %a, <4 x i32> %b) {
 ; CHECK-LABEL: test012:
 ; CHECK:       # BB#0:
-; CHECK-NEXT:    vspltisw 4, -16
-; CHECK-NEXT:    vspltisw 5, 15
-; CHECK-NEXT:    vsubuwm 4, 5, 4
-; CHECK-NEXT:    xxland 35, 35, 36
 ; CHECK-NEXT:    vslw 2, 2, 3
 ; CHECK-NEXT:    blr
   %rem = and <4 x i32> %b, <i32 31, i32 31, i32 31, i32 31>
   %shl = shl <4 x i32> %a, %rem
   ret <4 x i32> %shl
 }
 
 define <2 x i64> @test013(<2 x i64> %a, <2 x i64> %b) {
 ; CHECK-LABEL: test013:
 ; CHECK:       # BB#0:
-; CHECK-NEXT:    addis 3, 2, .LCPI7_0@toc@ha
-; CHECK-NEXT:    addi 3, 3, .LCPI7_0@toc@l
-; CHECK-NEXT:    lxvd2x 0, 0, 3
-; CHECK-NEXT:    xxswapd 36, 0
-; CHECK-NEXT:    xxland 35, 35, 36
 ; CHECK-NEXT:    vsld 2, 2, 3
 ; CHECK-NEXT:    blr
   %rem = and <2 x i64> %b, <i64 63, i64 63>
   %shl = shl <2 x i64> %a, %rem
   ret <2 x i64> %shl
 }
 
 define i8 @test100(i8 %a, i8 %b) {
 ; CHECK-LABEL: test100:
 ; CHECK:       # BB#0:
 ; CHECK-NEXT:    rlwinm 3, 3, 0, 24, 31
-; CHECK-NEXT:    rlwinm 4, 4, 0, 29, 31
 ; CHECK-NEXT:    srw 3, 3, 4
 ; CHECK-NEXT:    blr
   %rem = and i8 %b, 7
   %lshr = lshr i8 %a, %rem
   ret i8 %lshr
 }
 
 define i16 @test101(i16 %a, i16 %b) {
 ; CHECK-LABEL: test101:
 ; CHECK:       # BB#0:
 ; CHECK-NEXT:    rlwinm 3, 3, 0, 16, 31
-; CHECK-NEXT:    rlwinm 4, 4, 0, 28, 31
 ; CHECK-NEXT:    srw 3, 3, 4
 ; CHECK-NEXT:    blr
   %rem = and i16 %b, 15
   %lshr = lshr i16 %a, %rem
   ret i16 %lshr
 }
 
 define i32 @test102(i32 %a, i32 %b) {
 ; CHECK-LABEL: test102:
 ; CHECK:       # BB#0:
-; CHECK-NEXT:    rlwinm 4, 4, 0, 27, 31
 ; CHECK-NEXT:    srw 3, 3, 4
 ; CHECK-NEXT:    blr
   %rem = and i32 %b, 31
   %lshr = lshr i32 %a, %rem
   ret i32 %lshr
 }
 
 define i64 @test103(i64 %a, i64 %b) {
 ; CHECK-LABEL: test103:
 ; CHECK:       # BB#0:
-; CHECK-NEXT:    rlwinm 4, 4, 0, 26, 31
 ; CHECK-NEXT:    srd 3, 3, 4
 ; CHECK-NEXT:    blr
   %rem = and i64 %b, 63
   %lshr = lshr i64 %a, %rem
   ret i64 %lshr
 }
 
 define <16 x i8> @test110(<16 x i8> %a, <16 x i8> %b) {
 ; CHECK-LABEL: test110:
 ; CHECK:       # BB#0:
-; CHECK-NEXT:    vspltisb 4, 7
-; CHECK-NEXT:    xxland 35, 35, 36
 ; CHECK-NEXT:    vsrb 2, 2, 3
 ; CHECK-NEXT:    blr
   %rem = and <16 x i8> %b, <i8 7, i8 7, i8 7, i8 7, i8 7, i8 7, i8 7, i8 7, i8 7, i8 7, i8 7, i8 7, i8 7, i8 7, i8 7, i8 7>
   %lshr = lshr <16 x i8> %a, %rem
   ret <16 x i8> %lshr
 }
 
 define <8 x i16> @test111(<8 x i16> %a, <8 x i16> %b) {
 ; CHECK-LABEL: test111:
 ; CHECK:       # BB#0:
-; CHECK-NEXT:    vspltish 4, 15
-; CHECK-NEXT:    xxland 35, 35, 36
 ; CHECK-NEXT:    vsrh 2, 2, 3
 ; CHECK-NEXT:    blr
   %rem = and <8 x i16> %b, <i16 15, i16 15, i16 15, i16 15, i16 15, i16 15, i16 15, i16 15>
   %lshr = lshr <8 x i16> %a, %rem
   ret <8 x i16> %lshr
 }
 
 define <4 x i32> @test112(<4 x i32> %a, <4 x i32> %b) {
 ; CHECK-LABEL: test112:
 ; CHECK:       # BB#0:
-; CHECK-NEXT:    vspltisw 4, -16
-; CHECK-NEXT:    vspltisw 5, 15
-; CHECK-NEXT:    vsubuwm 4, 5, 4
-; CHECK-NEXT:    xxland 35, 35, 36
 ; CHECK-NEXT:    vsrw 2, 2, 3
 ; CHECK-NEXT:    blr
   %rem = and <4 x i32> %b, <i32 31, i32 31, i32 31, i32 31>
   %lshr = lshr <4 x i32> %a, %rem
   ret <4 x i32> %lshr
 }
 
 define <2 x i64> @test113(<2 x i64> %a, <2 x i64> %b) {
 ; CHECK-LABEL: test113:
 ; CHECK:       # BB#0:
-; CHECK-NEXT:    addis 3, 2, .LCPI15_0@toc@ha
-; CHECK-NEXT:    addi 3, 3, .LCPI15_0@toc@l
-; CHECK-NEXT:    lxvd2x 0, 0, 3
-; CHECK-NEXT:    xxswapd 36, 0
-; CHECK-NEXT:    xxland 35, 35, 36
 ; CHECK-NEXT:    vsrd 2, 2, 3
 ; CHECK-NEXT:    blr
   %rem = and <2 x i64> %b, <i64 63, i64 63>
   %lshr = lshr <2 x i64> %a, %rem
   ret <2 x i64> %lshr
 }
 
 define i8 @test200(i8 %a, i8 %b) {
 ; CHECK-LABEL: test200:
 ; CHECK:       # BB#0:
 ; CHECK-NEXT:    extsb 3, 3
-; CHECK-NEXT:    rlwinm 4, 4, 0, 29, 31
 ; CHECK-NEXT:    sraw 3, 3, 4
 ; CHECK-NEXT:    blr
   %rem = and i8 %b, 7
   %ashr = ashr i8 %a, %rem
   ret i8 %ashr
 }
 
 define i16 @test201(i16 %a, i16 %b) {
 ; CHECK-LABEL: test201:
 ; CHECK:       # BB#0:
 ; CHECK-NEXT:    extsh 3, 3
-; CHECK-NEXT:    rlwinm 4, 4, 0, 28, 31
 ; CHECK-NEXT:    sraw 3, 3, 4
 ; CHECK-NEXT:    blr
   %rem = and i16 %b, 15
   %ashr = ashr i16 %a, %rem
   ret i16 %ashr
 }
 
 define i32 @test202(i32 %a, i32 %b) {
 ; CHECK-LABEL: test202:
 ; CHECK:       # BB#0:
-; CHECK-NEXT:    rlwinm 4, 4, 0, 27, 31
 ; CHECK-NEXT:    sraw 3, 3, 4
 ; CHECK-NEXT:    blr
   %rem = and i32 %b, 31
   %ashr = ashr i32 %a, %rem
   ret i32 %ashr
 }
 
 define i64 @test203(i64 %a, i64 %b) {
 ; CHECK-LABEL: test203:
 ; CHECK:       # BB#0:
-; CHECK-NEXT:    rlwinm 4, 4, 0, 26, 31
 ; CHECK-NEXT:    srad 3, 3, 4
 ; CHECK-NEXT:    blr
   %rem = and i64 %b, 63
   %ashr = ashr i64 %a, %rem
   ret i64 %ashr
 }
 
 define <16 x i8> @test210(<16 x i8> %a, <16 x i8> %b) {
 ; CHECK-LABEL: test210:
 ; CHECK:       # BB#0:
-; CHECK-NEXT:    vspltisb 4, 7
-; CHECK-NEXT:    xxland 35, 35, 36
 ; CHECK-NEXT:    vsrab 2, 2, 3
 ; CHECK-NEXT:    blr
   %rem = and <16 x i8> %b, <i8 7, i8 7, i8 7, i8 7, i8 7, i8 7, i8 7, i8 7, i8 7, i8 7, i8 7, i8 7, i8 7, i8 7, i8 7, i8 7>
   %ashr = ashr <16 x i8> %a, %rem
   ret <16 x i8> %ashr
 }
 
 define <8 x i16> @test211(<8 x i16> %a, <8 x i16> %b) {
 ; CHECK-LABEL: test211:
 ; CHECK:       # BB#0:
-; CHECK-NEXT:    vspltish 4, 15
-; CHECK-NEXT:    xxland 35, 35, 36
 ; CHECK-NEXT:    vsrah 2, 2, 3
 ; CHECK-NEXT:    blr
   %rem = and <8 x i16> %b, <i16 15, i16 15, i16 15, i16 15, i16 15, i16 15, i16 15, i16 15>
   %ashr = ashr <8 x i16> %a, %rem
   ret <8 x i16> %ashr
 }
 
 define <4 x i32> @test212(<4 x i32> %a, <4 x i32> %b) {
 ; CHECK-LABEL: test212:
 ; CHECK:       # BB#0:
-; CHECK-NEXT:    vspltisw 4, -16
-; CHECK-NEXT:    vspltisw 5, 15
-; CHECK-NEXT:    vsubuwm 4, 5, 4
-; CHECK-NEXT:    xxland 35, 35, 36
 ; CHECK-NEXT:    vsraw 2, 2, 3
 ; CHECK-NEXT:    blr
   %rem = and <4 x i32> %b, <i32 31, i32 31, i32 31, i32 31>
   %ashr = ashr <4 x i32> %a, %rem
   ret <4 x i32> %ashr
 }
 
 define <2 x i64> @test213(<2 x i64> %a, <2 x i64> %b) {
 ; CHECK-LABEL: test213:
 ; CHECK:       # BB#0:
-; CHECK-NEXT:    addis 3, 2, .LCPI23_0@toc@ha
-; CHECK-NEXT:    addi 3, 3, .LCPI23_0@toc@l
-; CHECK-NEXT:    lxvd2x 0, 0, 3
-; CHECK-NEXT:    xxswapd 36, 0
-; CHECK-NEXT:    xxland 35, 35, 36
 ; CHECK-NEXT:    vsrad 2, 2, 3
 ; CHECK-NEXT:    blr
   %rem = and <2 x i64> %b, <i64 63, i64 63>
   %ashr = ashr <2 x i64> %a, %rem
   ret <2 x i64> %ashr
 }