[ARM] Complete the Thumb1 shift+and->shift+shift transforms.

[efriedma]

Summary

This saves materializing the immediate. The additional forms are less common, but they're still relevant in some situations.

I had to add a new target hook to prevent DAGCombine from reversing the transform. That isn't the only possible way to solve the conflict, but it seems straightforward enough.

[efriedma]

Remove unnecessary call to target hook from DAGCombine. (It might be necessary in the future, possibly, but it isn't useful for now.)

[t.p.northover]

I think this looks fine.

llvm/trunk/include/llvm/CodeGen/TargetLowering.h

public:
   ///
   /// @param N the shift node
   /// @param Level the current DAGCombine legalization level.
   virtual bool isDesirableToCommuteWithShift(const SDNode *N,
                                              CombineLevel Level) const {
     return true;
   }
 
+  /// Return true if it is profitable to fold a pair of shifts into a mask.
+  /// This is usually true on most targets. But some targets, like Thumb1,
+  /// have immediate shift instructions, but no immediate "and" instruction;
+  /// this makes the fold unprofitable.
+  virtual bool shouldFoldShiftPairToMask(const SDNode *N,
+                                         CombineLevel Level) const {
+    return true;
+  }
+
   // Return true if it is profitable to combine a BUILD_VECTOR with a stride-pattern
   // to a shuffle and a truncate.
   // Example of such a combine:
   // v4i32 build_vector((extract_elt V, 1),
   //                    (extract_elt V, 3),
   //                    (extract_elt V, 5),
   //                    (extract_elt V, 7))
   //  -->

llvm/trunk/lib/CodeGen/SelectionDAG/DAGCombiner.cpp

if (ConstantSDNode *N0C1 = isConstOrConstSplat(N0.getOperand(1))) {
                          DAG.getConstant(C1 - C2, DL, N1.getValueType()));
     }
   }
 
   // fold (shl (srl x, c1), c2) -> (and (shl x, (sub c2, c1), MASK) or
   //                               (and (srl x, (sub c1, c2), MASK)
   // Only fold this if the inner shift has no other uses -- if it does, folding
   // this will increase the total number of instructions.
-  if (N1C && N0.getOpcode() == ISD::SRL && N0.hasOneUse()) {
+  if (N1C && N0.getOpcode() == ISD::SRL && N0.hasOneUse() &&
+      TLI.shouldFoldShiftPairToMask(N, Level)) {
     if (ConstantSDNode *N0C1 = isConstOrConstSplat(N0.getOperand(1))) {
       uint64_t c1 = N0C1->getZExtValue();
       if (c1 < OpSizeInBits) {
         uint64_t c2 = N1C->getZExtValue();
         APInt Mask = APInt::getHighBitsSet(OpSizeInBits, OpSizeInBits - c1);
         SDValue Shift;
         if (c2 > c1) {
           Mask <<= c2 - c1;

llvm/trunk/lib/Target/ARM/ARMISelLowering.h

public:
 
     /// Return the correct alignment for the current calling convention.
     unsigned getABIAlignmentForCallingConv(Type *ArgTy,
                                            DataLayout DL) const override;
 
     bool isDesirableToCommuteWithShift(const SDNode *N,
                                        CombineLevel Level) const override;
 
+    bool shouldFoldShiftPairToMask(const SDNode *N,
+                                   CombineLevel Level) const override;
   protected:
     std::pair<const TargetRegisterClass *, uint8_t>
     findRepresentativeClass(const TargetRegisterInfo *TRI,
                             MVT VT) const override;
 
   private:
     /// Subtarget - Keep a pointer to the ARMSubtarget around so that we can
     /// make the right decision when generating code for different targets.

llvm/trunk/lib/Target/ARM/ARMISelLowering.cpp

ARMTargetLowering::isDesirableToCommuteWithShift(const SDNode *N,
 
   // Turn off commute-with-shift transform after legalization, so it doesn't
   // conflict with PerformSHLSimplify.  (We could try to detect when
   // PerformSHLSimplify would trigger more precisely, but it isn't
   // really necessary.)
   return false;
 }
 
+bool
+ARMTargetLowering::shouldFoldShiftPairToMask(const SDNode *N,
+                                             CombineLevel Level) const {
+  if (!Subtarget->isThumb1Only())
+    return true;
+
+  if (Level == BeforeLegalizeTypes)
+    return true;
+
+  return false;
+}
+
 static SDValue PerformSHLSimplify(SDNode *N,
                                 TargetLowering::DAGCombinerInfo &DCI,
                                 const ARMSubtarget *ST) {
   // Allow the generic combiner to identify potential bswaps.
   if (DCI.isBeforeLegalize())
     return SDValue();
 
   // DAG combiner will fold:
static SDValue CombineANDShift(SDNode *N,
   ConstantSDNode *N01C = dyn_cast<ConstantSDNode>(N0->getOperand(1));
   if (!N01C)
     return SDValue();
 
   uint32_t C2 = (uint32_t)N01C->getZExtValue();
   if (!C2 || C2 >= 32)
     return SDValue();
 
+  // Clear irrelevant bits in the mask.
+  if (LeftShift)
+    C1 &= (-1U << C2);
+  else
+    C1 &= (-1U >> C2);
+
   SelectionDAG &DAG = DCI.DAG;
   SDLoc DL(N);
 
   // We have a pattern of the form "(and (shl x, c2) c1)" or
   // "(and (srl x, c2) c1)", where c1 is a shifted mask. Try to
   // transform to a pair of shifts, to save materializing c1.
 
-  // First pattern: right shift, and c1+1 is a power of two.
-  // FIXME: Also check reversed pattern (left shift, and ~c1+1 is a power
-  // of two).
+  // First pattern: right shift, then mask off leading bits.
   // FIXME: Use demanded bits?
   if (!LeftShift && isMask_32(C1)) {
     uint32_t C3 = countLeadingZeros(C1);
     if (C2 < C3) {
       SDValue SHL = DAG.getNode(ISD::SHL, DL, MVT::i32, N0->getOperand(0),
                                 DAG.getConstant(C3 - C2, DL, MVT::i32));
       return DAG.getNode(ISD::SRL, DL, MVT::i32, SHL,
                          DAG.getConstant(C3, DL, MVT::i32));
     }
   }
 
-  // Second pattern: left shift, and (c1>>c2)+1 is a power of two.
-  // FIXME: Also check reversed pattern (right shift, and ~(c1<<c2)+1
-  // is a power of two).
+  // First pattern, reversed: left shift, then mask off trailing bits.
+  if (LeftShift && isMask_32(~C1)) {
+    uint32_t C3 = countTrailingZeros(C1);
+    if (C2 < C3) {
+      SDValue SHL = DAG.getNode(ISD::SRL, DL, MVT::i32, N0->getOperand(0),
+                                DAG.getConstant(C3 - C2, DL, MVT::i32));
+      return DAG.getNode(ISD::SHL, DL, MVT::i32, SHL,
+                         DAG.getConstant(C3, DL, MVT::i32));
+    }
+  }
+
+  // Second pattern: left shift, then mask off leading bits.
   // FIXME: Use demanded bits?
   if (LeftShift && isShiftedMask_32(C1)) {
+    uint32_t Trailing = countTrailingZeros(C1);
     uint32_t C3 = countLeadingZeros(C1);
-    if (C2 + C3 < 32 && C1 == ((-1U << (C2 + C3)) >> C3)) {
+    if (Trailing == C2 && C2 + C3 < 32) {
       SDValue SHL = DAG.getNode(ISD::SHL, DL, MVT::i32, N0->getOperand(0),
                                 DAG.getConstant(C2 + C3, DL, MVT::i32));
       return DAG.getNode(ISD::SRL, DL, MVT::i32, SHL,
                         DAG.getConstant(C3, DL, MVT::i32));
     }
   }
 
+  // Second pattern, reversed: right shift, then mask off trailing bits.
+  // FIXME: Handle other patterns of known/demanded bits.
+  if (!LeftShift && isShiftedMask_32(C1)) {
+    uint32_t Leading = countLeadingZeros(C1);
+    uint32_t C3 = countTrailingZeros(C1);
+    if (Leading == C2 && C2 + C3 < 32) {
+      SDValue SHL = DAG.getNode(ISD::SRL, DL, MVT::i32, N0->getOperand(0),
+                                DAG.getConstant(C2 + C3, DL, MVT::i32));
+      return DAG.getNode(ISD::SHL, DL, MVT::i32, SHL,
+                         DAG.getConstant(C3, DL, MVT::i32));
+    }
+  }
+
   // FIXME: Transform "(and (shl x, c2) c1)" ->
   // "(shl (and x, c1>>c2), c2)" if "c1 >> c2" is a cheaper immediate than
   // c1.
   return SDValue();
 }
 
 static SDValue PerformANDCombine(SDNode *N,
                                  TargetLowering::DAGCombinerInfo &DCI,

llvm/trunk/test/CodeGen/Thumb/shift-and.ll

entry:
   %0 = lshr i32 %x, 2
   %shr = and i32 %0, 255
   ret i32 %shr
 }
 
 define i32 @test4(i32 %x) {
 ; CHECK-LABEL: test4:
 ; CHECK:       @ %bb.0: @ %entry
-; CHECK-NEXT:    lsls r0, r0, #4
-; CHECK-NEXT:    movs r1, #112
-; CHECK-NEXT:    bics r0, r1
+; CHECK-NEXT:    lsrs r0, r0, #3
+; CHECK-NEXT:    lsls r0, r0, #7
 ; CHECK-NEXT:    bx lr
 entry:
   %0 = shl i32 %x, 4
   %shr = and i32 %0, -128
   ret i32 %shr
 }
 
 define i32 @test5(i32 %x) {
entry:
   %0 = shl i32 %x, 29
   %shr = and i32 %0, 2684354560
   ret i32 %shr
 }
 
 define i32 @test7(i32 %x) {
 ; CHECK-LABEL: test7:
 ; CHECK:       @ %bb.0: @ %entry
-; CHECK-NEXT:    lsrs r1, r0, #29
-; CHECK-NEXT:    movs r0, #4
-; CHECK-NEXT:    ands r0, r1
+; CHECK-NEXT:    lsrs r0, r0, #31
+; CHECK-NEXT:    lsls r0, r0, #2
 ; CHECK-NEXT:    bx lr
 entry:
   %0 = lshr i32 %x, 29
   %shr = and i32 %0, 4
   ret i32 %shr
 }
 
 define i32 @test8(i32 %x) {
 ; CHECK-LABEL: test8:
 ; CHECK:       @ %bb.0: @ %entry
 ; CHECK-NEXT:    lsrs r1, r0, #29
 ; CHECK-NEXT:    movs r0, #5
 ; CHECK-NEXT:    ands r0, r1
 ; CHECK-NEXT:    bx lr
 entry:
   %0 = lshr i32 %x, 29
   %shr = and i32 %0, 5
   ret i32 %shr
 }
 
 define i32 @test9(i32 %x) {
 ; CHECK-LABEL: test9:
 ; CHECK:       @ %bb.0: @ %entry
-; CHECK-NEXT:    lsrs r0, r0, #2
-; CHECK-NEXT:    movs r1, #1
-; CHECK-NEXT:    bics r0, r1
+; CHECK-NEXT:    lsrs r0, r0, #3
+; CHECK-NEXT:    lsls r0, r0, #1
 ; CHECK-NEXT:    bx lr
 entry:
   %and = lshr i32 %x, 2
   %shr = and i32 %and, 1073741822
   ret i32 %shr
 }
 
 define i32 @test10(i32 %x) {
 ; CHECK-LABEL: test10:
 ; CHECK:       @ %bb.0: @ %entry
 ; CHECK-NEXT:    lsls r0, r0, #2
 ; CHECK-NEXT:    uxtb r0, r0
 ; CHECK-NEXT:    bx lr
 entry:
   %0 = shl i32 %x, 2
   %shr = and i32 %0, 255
   ret i32 %shr
 }
+
+define i32 @test11(i32 %x) {
+; CHECK-LABEL: test11:
+; CHECK:       @ %bb.0: @ %entry
+; CHECK-NEXT:    lsrs r0, r0, #24
+; CHECK-NEXT:    lsls r0, r0, #2
+; CHECK-NEXT:    bx lr
+entry:
+  %shl = lshr i32 %x, 22
+  %and = and i32 %shl, 1020
+  ret i32 %and
+}
+
+define i32 @test12(i32 %x) {
+; CHECK-LABEL: test12:
+; CHECK:       @ %bb.0: @ %entry
+; CHECK-NEXT:    lsrs r0, r0, #3
+; CHECK-NEXT:    lsls r0, r0, #4
+; CHECK-NEXT:    bx lr
+entry:
+  %0 = shl i32 %x, 1
+  %shr = and i32 %0, -16
+  ret i32 %shr
+}
+
+define i32 @test13(i32 %x) {
+; CHECK-LABEL: test13:
+; CHECK:       @ %bb.0: @ %entry
+; CHECK-NEXT:    lsrs r0, r0, #3
+; CHECK-NEXT:    lsls r0, r0, #4
+; CHECK-NEXT:    bx lr
+entry:
+  %shr = lshr i32 %x, 3
+  %shl = shl i32 %shr, 4
+  ret i32 %shl
+}
+
+define i32 @test14(i32 %x) {
+; CHECK-LABEL: test14:
+; CHECK:       @ %bb.0: @ %entry
+; CHECK-NEXT:    lsrs r0, r0, #6
+; CHECK-NEXT:    lsls r0, r0, #10
+; CHECK-NEXT:    bx lr
+entry:
+  %shl = shl i32 %x, 4
+  %and = and i32 %shl, -1024
+  ret i32 %and
+}
+
+define i32 @test15(i32 %x) {
+; CHECK-LABEL: test15:
+; CHECK:       @ %bb.0: @ %entry
+; CHECK-NEXT:    lsrs r0, r0, #4
+; CHECK-NEXT:    lsls r0, r0, #3
+; CHECK-NEXT:    bx lr
+entry:
+  %shr = lshr i32 %x, 4
+  %shl = shl i32 %shr, 3
+  ret i32 %shl
+}