[ARM] add, or, and and xor with shl combining

[samparker]

Summary

The generic dag combiner will fold:

(shl (add x, c1), c2) -> (add (shl x, c2), c1 << c2)
(shl (or x, c1), c2) -> (or (shl x, c2), c1 << c2)

This can create constants which are too large to use as an immediate. Many ALU operations are also able of performing the shl, so we can unfold the transformation to prevent a mov imm instruction from being generated.

Other patterns, such as b + ((a << 1) | 510), can also be simplified in the same manner.

[john.brawn]

This patch does three distinct things (swap CMP operands, separate out OR->BFI conversion, unfold shl) and I think it would make more sense to therefore do three separate patches.

lib/Target/ARM/ARMISelLowering.cpp

3858–3861

This could be simplified using getShiftOpcForNode from ARMSelectionDAGInfo.h (check LHS is not no_shift, check RHS is no_shift).

3862

Not in 16-bit thumb, though it's probably harmless to swap them in that case. The comment should mention that though.

10269

Moving this comment looks a little odd.

10327

This should be called something else as there's already a PerformBFICombine and the name here violates the rule that the argument to PerformXCombine is a node of type X (here it's an OR of an AND). Probably PerformORCombineToBFI.

[samparker]

Thanks for the comments John. I'll make the changes and split the patch.

cheers,
sam

[samparker]

Updated now that BFI combine and the compare operand swapping have been extracted into their own patches.

[john.brawn]

lib/Target/ARM/ARMISelLowering.cpp

10101

'Unfold' is probably the wrong description of this as we may get these kind of instruction sequences without any folding having happened e.g.

int fn(int a, int b)
{
  return b + ((a << 1) | 510);
}

10104–10105

Could do with a comment here saying something like "no 16-bit thumb instructions with shifted operand".

10107–10108

We should be doing this for XOR and AND as well.

[samparker]

Thanks again John, I'll make the changes.

[samparker]

Added support for simplifying XOR and AND nodes and added tests for them, this meant having to modify a few tests too. Also changed and added some comments and renamed the function.

[john.brawn]

lib/Target/ARM/ARMISelLowering.cpp

10164

You're setting BinOp here then immediately setting it to something else a few lines later, you should be setting it just once.

10165–10178

It would make more sense to do this check nearer to the start of the function. Also you could check that all uses don't already have a shifted operand, as in that case doing this transform doesn't have any benefit. That should mean you don't have to adjust the load-combine tests.

[samparker]

Thanks John, I've made those changes.

[john.brawn]

LGTM.

lib/Target/ARM/ARMISelLowering.cpp

 
   // fold (add (select cc, 0, c), x) -> (select cc, x, (add, x, c))
   if (N0.getNode()->hasOneUse())
     if (SDValue Result = combineSelectAndUse(N, N0, N1, DCI))
       return Result;
   return SDValue();
 }
 
+static SDValue PerformUnfoldSHL(SDNode *N,
+                                TargetLowering::DAGCombinerInfo &DCI,
+                                const ARMSubtarget *ST) {
+  if (ST->isThumb() && ST->isThumb1Only())
+    return SDValue();
+
+  if (N->getOpcode() != ISD::ADD && N->getOpcode() != ISD::OR)
+    return SDValue();
+
+  if (N->getOperand(0).getOpcode() != ISD::SHL)
+    return SDValue();
+
+  SDValue SHL = N->getOperand(0);
+
+  auto *C1ShlC2 = dyn_cast<ConstantSDNode>(N->getOperand(1));
+  auto *C2 = dyn_cast<ConstantSDNode>(SHL.getOperand(1));
+  if (!C1ShlC2 || !C2)
+    return SDValue();
+
+  DEBUG(dbgs() << "Try to unfold: "; N->dump());
+  // DAG combiner will fold:
+  // (shl (add x, c1), c2) -> (add (shl x, c2), c1 << c2)
+  // (shl (or x, c1), c2) -> (or (shl x, c2), c1 << c2)
+
+  // Many instructions can  perform the shift for free, but it requires both
+  // the operands to be registers. If c1 << c2 is too large, a mov immediate
+  // instruction will needed. So, unfold back to the original pattern if:
+  // - if c1 and c2 are small enough that they don't require mov imms.
+  // - the user(s) of the node can perform an shl
+
+  APInt C2Int = C2->getAPIntValue();
+  APInt C1Int = C1ShlC2->getAPIntValue();
+
+  // Check that C1 could have been shl'd by C2.
+  APInt Mask = APInt::getHighBitsSet(C2Int.getBitWidth(),
+                                     C2Int.getBitWidth() - C2->getZExtValue());
+  if ((C1Int & Mask) != C1Int)
+    return SDValue();
+
+  // Undo c1 << c2
+  C1Int.lshrInPlace(C2Int);
+
+  // The immediates are encoded as an 8-bit value that can be rotated.
+  unsigned Zeros = C1Int.countLeadingZeros() + C1Int.countTrailingZeros();
+  if (C1Int.getBitWidth() - Zeros > 8)
+    return SDValue();
+
+  Zeros = C2Int.countLeadingZeros() + C2Int.countTrailingZeros();
+  if (C2Int.getBitWidth() - Zeros > 8)
+    return SDValue();
+
+  // Check that all the users could perform the shl themselves.
+  SDValue BinOp = SDValue(N, 0);
+  for (auto U : N->uses()) {
+    switch(U->getOpcode()) {
+    default:
+      return SDValue();
+    case ISD::ADD:
+    case ISD::SUB:
+    case ISD::AND:
+    case ISD::OR:
+    case ISD::XOR:
+    case ISD::SETCC:
+    case ARMISD::CMP:
+      break;
+    }
+  }
+
+  SelectionDAG &DAG = DCI.DAG;
+  SDLoc dl(N);
+  SDValue X = SHL.getOperand(0);
+  BinOp = DAG.getNode(N->getOpcode(), dl, MVT::i32, X,
+                      DAG.getConstant(C1Int, dl, MVT::i32));
+  SDValue Res = DAG.getNode(ISD::SHL, dl, MVT::i32, BinOp, SHL.getOperand(1));
+
+  DEBUG(dbgs()  << "Unfolding: "; N->dump());
+  DEBUG(dbgs() << "Into shift operation:\n";
+        BinOp.dump();
+        Res.dump());
+
+  DAG.ReplaceAllUsesWith(SDValue(N, 0), Res);
+  return SDValue(N, 0);
+}
+
 /// PerformADDCombine - Target-specific dag combine xforms for ISD::ADD.
 ///
 static SDValue PerformADDCombine(SDNode *N,
                                  TargetLowering::DAGCombinerInfo &DCI,
                                  const ARMSubtarget *Subtarget) {
   SDValue N0 = N->getOperand(0);
   SDValue N1 = N->getOperand(1);
 
+  // Only works one way, because it needs an immediate operand.
+  if (SDValue Result = PerformUnfoldSHL(N, DCI, Subtarget))
+    return Result;
+
   // First try with the default operand order.
   if (SDValue Result = PerformADDCombineWithOperands(N, N0, N1, DCI, Subtarget))
     return Result;
 
   // If that didn't work, try again with the operands commuted.
   return PerformADDCombineWithOperands(N, N1, N0, DCI, Subtarget);
 }
 

   return DAG.getNode(Opcode, DL, VT,
                      DAG.getNode(ISD::MUL, DL, VT, N00, N1),
                      DAG.getNode(ISD::MUL, DL, VT, N01, N1));
 }
 
 static SDValue PerformMULCombine(SDNode *N,
                                  TargetLowering::DAGCombinerInfo &DCI,
                                  const ARMSubtarget *Subtarget) {
   SelectionDAG &DAG = DCI.DAG;
 
   if (Subtarget->isThumb1Only())
     return SDValue();
 
   if (DCI.isBeforeLegalize() || DCI.isCalledByLegalizer())
     return SDValue();
 
   EVT VT = N->getValueType(0);

   unsigned ShiftAmt = countTrailingZeros<uint64_t>(MulAmt);
 
   ShiftAmt = ShiftAmt & (32 - 1);
   SDValue V = N->getOperand(0);
   SDLoc DL(N);
 
   SDValue Res;
   MulAmt >>= ShiftAmt;
 

   if (!Subtarget->isThumb1Only()) {
     // fold (or (select cc, 0, c), x) -> (select cc, x, (or, x, c))
     if (SDValue Result = combineSelectAndUseCommutative(N, false, DCI))
       return Result;
     if (SDValue Result = PerformORCombineToSMULWBT(N, DCI, Subtarget))
       return Result;
   }
 
-  // The code below optimizes (or (and X, Y), Z).
-  // The AND operand needs to have a single user to make these optimizations
-  // profitable.
   SDValue N0 = N->getOperand(0);
-  if (N0.getOpcode() != ISD::AND || !N0.hasOneUse())
-    return SDValue();
   SDValue N1 = N->getOperand(1);
 
   // (or (and B, A), (and C, ~A)) => (VBSL A, B, C) when A is a constant.
   if (Subtarget->hasNEON() && N1.getOpcode() == ISD::AND && VT.isVector() &&
       DAG.getTargetLoweringInfo().isTypeLegal(VT)) {
+
+    // The code below optimizes (or (and X, Y), Z).
+    // The AND operand needs to have a single user to make these optimizations
+    // profitable.
+    if (N0.getOpcode() != ISD::AND || !N0.hasOneUse())
+      return SDValue();
+
     APInt SplatUndef;
     unsigned SplatBitSize;
     bool HasAnyUndefs;
 
     APInt SplatBits0, SplatBits1;
     BuildVectorSDNode *BVN0 = dyn_cast<BuildVectorSDNode>(N0->getOperand(1));
     BuildVectorSDNode *BVN1 = dyn_cast<BuildVectorSDNode>(N1->getOperand(1));
     // Ensure that the second operand of both ands are constants

 
   // Try to use the ARM/Thumb2 BFI (bitfield insert) instruction when
   // reasonable.
 
   // BFI is only available on V6T2+
   if (Subtarget->isThumb1Only() || !Subtarget->hasV6T2Ops())
     return SDValue();
 
-  if (SDValue Res = PerformORCombineToBFI(N, DCI, Subtarget))
-    return Res;
+  if (N0.getOpcode() == ISD::AND && N0.hasOneUse()) {
+    if (SDValue Res = PerformORCombineToBFI(N, DCI, Subtarget))
+      return Res;
+  }
+
+  if (SDValue Result = PerformUnfoldSHL(N, DCI, Subtarget))
+    return Result;
 
   return SDValue();
 }
 
 static SDValue PerformXORCombine(SDNode *N,
                                  TargetLowering::DAGCombinerInfo &DCI,
                                  const ARMSubtarget *Subtarget) {
   EVT VT = N->getValueType(0);

test/CodeGen/ARM/unfold-shifts.ll

+; RUN: llc -mtriple armv6t2 %s -o - | FileCheck %s
+; RUN: llc -mtriple thumbv6t2 %s -o - | FileCheck %s --check-prefix=CHECK-T2
+; RUN: llc -mtriple armv7 %s -o - | FileCheck %s
+; RUN: llc -mtriple thumbv7 %s -o - | FileCheck %s --check-prefix=CHECK-T2
+; RUN: llc -mtriple thumbv7m %s -o - | FileCheck %s --check-prefix=CHECK-T2
+; RUN: llc -mtriple thumbv8m.main %s -o - | FileCheck %s --check-prefix=CHECK-T2
+
+; CHECK-LABEL: unfold1
+; CHECK-NOT: mov
+; CHECK: orr r0, r0, #255
+; CHECK: add r0, r1, r0, lsl #1
+; CHECK-T2-NOT: mov
+; CHECK-T2: orr r0, r0, #255
+; CHECK-T2: add.w r0, r1, r0, lsl #1
+define arm_aapcscc i32 @unfold1(i32 %a, i32 %b) {
+entry:
+  %or = shl i32 %a, 1
+  %shl = or i32 %or, 510
+  %add = add nsw i32 %shl, %b
+  ret i32 %add
+}
+
+; CHECK-LABEL: unfold2
+; CHECK-NOT: mov
+; CHECK: orr r0, r0, #4080
+; CHECK: sub r0, r1, r0, lsl #2
+; CHECK-T2-NOT: mov
+; CHECK-T2: orr r0, r0, #4080
+; CHECK-T2: sub.w r0, r1, r0, lsl #2
+define arm_aapcscc i32 @unfold2(i32 %a, i32 %b) {
+entry:
+  %or = shl i32 %a, 2
+  %shl = or i32 %or, 16320
+  %sub = sub nsw i32 %b, %shl
+  ret i32 %sub
+}
+
+; CHECK-LABEL: unfold3
+; CHECK-NOT: mov
+; CHECK: orr r0, r0, #65280
+; CHECK: and r0, r1, r0, lsl #4
+; CHECK-T2-NOT: mov
+; CHECK-T2: orr r0, r0, #65280
+; CHECK-T2: and.w r0, r1, r0, lsl #4
+define arm_aapcscc i32 @unfold3(i32 %a, i32 %b) {
+entry:
+  %or = shl i32 %a, 4
+  %shl = or i32 %or, 1044480
+  %and = and i32 %shl, %b
+  ret i32 %and
+}
+
+; CHECK-LABEL: unfold4
+; CHECK-NOT: mov
+; CHECK: orr r0, r0, #1044480
+; CHECK: eor r0, r1, r0, lsl #5
+; CHECK-T2-NOT: mov
+; CHECK-T2: orr r0, r0, #1044480
+; CHECK-T2: eor.w r0, r1, r0, lsl #5
+define arm_aapcscc i32 @unfold4(i32 %a, i32 %b) {
+entry:
+  %or = shl i32 %a, 5
+  %shl = or i32 %or, 33423360
+  %xor = xor i32 %shl, %b
+  ret i32 %xor
+}
+
+; CHECK-LABEL: unfold5
+; CHECK-NOT: mov
+; CHECK: add r0, r0, #496
+; CHECK: orr r0, r1, r0, lsl #6
+; CHECK-T2: add.w r0, r0, #496
+; CHECK-T2: orr.w r0, r1, r0, lsl #6
+define arm_aapcscc i32 @unfold5(i32 %a, i32 %b) {
+entry:
+  %add = shl i32 %a, 6
+  %shl = add i32 %add, 31744
+  %or = or i32 %shl, %b
+  ret i32 %or
+}
+
+; CHECK-LABEL: unfold6
+; CHECK-NOT: mov
+; CHECK: add r0, r0, #7936
+; CHECK: and r0, r1, r0, lsl #8
+; CHECK-T2-NOT: mov
+; CHECK-T2: add.w r0, r0, #7936
+; CHECK-T2: and.w r0, r1, r0, lsl #8
+define arm_aapcscc i32 @unfold6(i32 %a, i32 %b) {
+entry:
+  %add = shl i32 %a, 8
+  %shl = add i32 %add, 2031616
+  %and = and i32 %shl, %b
+  ret i32 %and
+}
+
+; CHECK-LABEL: unfold7
+; CHECK-NOT: mov
+; CHECK: add r0, r0, #126976
+; CHECK: eor r0, r1, r0, lsl #9
+; CHECK-T2-NOT: mov
+; CHECK-T2: add.w r0, r0, #126976
+; CHECK-T2: eor.w r0, r1, r0, lsl #9
+define arm_aapcscc i32 @unfold7(i32 %a, i32 %b) {
+entry:
+  %add = shl i32 %a, 9
+  %shl = add i32 %add, 65011712
+  %xor = xor i32 %shl, %b
+  ret i32 %xor
+}
+
+; CHECK-LABEL: unfold8
+; CHECK-NOT: mov r2
+; CHECK: orr r2, r0, #4080
+; CHECK: cmp r1, r2, lsl #10
+; CHECK-T2-NOT: mov.w r2
+; CHECK-T2: orr r2, r0, #4080
+; CHECK-T2: cmp.w r1, r2, lsl #10
+define arm_aapcscc i32 @unfold8(i32 %a, i32 %b) {
+entry:
+  %or = shl i32 %a, 10
+  %shl = or i32 %or, 4177920
+  %cmp = icmp sgt i32 %shl, %b
+  %conv = zext i1 %cmp to i32
+  ret i32 %conv
+}
+
+; CHECK-LABEL: unfold9
+; CHECK-NOT: mov r2
+; CHECK: add r2, r0, #7936
+; CHECK: cmp r1, r2, lsl #11
+; CHECK-T2-NOT: mov.w r2
+; CHECK-T2: add.w r2, r0, #7936
+; CHECK-T2: cmp.w r1, r2, lsl #11
+define arm_aapcscc i32 @unfold9(i32 %a, i32 %b) {
+entry:
+  %add = shl i32 %a, 11
+  %shl = add i32 %add, 16252928
+  %cmp = icmp sgt i32 %shl, %b
+  %conv = zext i1 %cmp to i32
+  ret i32 %conv
+}
+