This is an archive of the discontinued LLVM Phabricator instance.

Differential D38084

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

Authored by samparker on Sep 20 2017, 8:45 AM.

Details

Reviewers
eastig
john.brawn
Commits
rG242052c6b4bb: [ARM] and, or, xor and add with shl combine
rL317197: [ARM] and, or, xor and add with shl combine
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.

Diff Detail

Repository
rL LLVM

Event Timeline

samparker created this revision.Sep 20 2017, 8:45 AM
Herald added subscribers: kristof.beyls, javed.absar, aemerson. · View Herald TranscriptSep 20 2017, 8:45 AM
samparker added reviewers: eastig, john.brawn.Oct 16 2017, 6:22 AM
john.brawn edited edge metadata.Oct 17 2017, 4:20 AM

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 ↗(On Diff #116009)

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

3862 ↗(On Diff #116009)

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

10269 ↗(On Diff #116009)

Moving this comment looks a little odd.

10327 ↗(On Diff #116009)

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 added a comment.Oct 17 2017, 5:08 AM

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

cheers,
sam

samparker added a parent revision: D39001: [ARM] Or combine to BFI function.Oct 17 2017, 6:20 AM
samparker added a parent revision: D39004: [ARM] Swap cmp operands for automatic shifts..Oct 17 2017, 8:04 AM
samparker updated this revision to Diff 119339.Oct 17 2017, 8:53 AM
samparker edited the summary of this revision. (Show Details)

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

john.brawn added inline comments.Oct 18 2017, 5:47 AM
lib/Target/ARM/ARMISelLowering.cpp
10101 ↗(On Diff #119339)

'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 ↗(On Diff #119339)

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

10107–10108 ↗(On Diff #119339)

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

samparker added a comment.Oct 18 2017, 6:55 AM

Thanks again John, I'll make the changes.

samparker updated this revision to Diff 119572.Oct 19 2017, 5:05 AM
samparker retitled this revision from [ARM] add, or, shl combining to [ARM] add, or, and and xor with shl combining.
samparker edited the summary of this revision. (Show Details)

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 added inline comments.Oct 24 2017, 9:38 AM
lib/Target/ARM/ARMISelLowering.cpp
10164 ↗(On Diff #119572)

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 ↗(On Diff #119572)

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 updated this revision to Diff 120217.Oct 25 2017, 2:34 AM

Thanks John, I've made those changes.

john.brawn accepted this revision.Nov 1 2017, 10:50 AM

LGTM.

This revision is now accepted and ready to land.Nov 1 2017, 10:50 AM
Closed by commit rL317197: [ARM] and, or, xor and add with shl combine (authored by sam_parker). · Explain WhyNov 2 2017, 3:43 AM
This revision was automatically updated to reflect the committed changes.

Revision Contents

PathSize
llvm/
trunk/
lib/
Target/
ARM/
127 lines
test/
CodeGen/
ARM/
173 lines

Diff 121270

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

  • This file is larger than 256 KB, so syntax highlighting is disabled by default.
Show First 20 Lines • Show All 9,949 Lines • ▼ Show 20 Linesstatic SDValue PerformADDCombineWithOperands(SDNode *N, SDValue N0, SDValue N1,
// fold (add (select cc, 0, c), x) -> (select cc, x, (add, x, c)) // fold (add (select cc, 0, c), x) -> (select cc, x, (add, x, c))
if (N0.getNode()->hasOneUse()) if (N0.getNode()->hasOneUse())
if (SDValue Result = combineSelectAndUse(N, N0, N1, DCI)) if (SDValue Result = combineSelectAndUse(N, N0, N1, DCI))
return Result; return Result;
return SDValue(); return SDValue();
} }
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:
// (shl (add x, c1), c2) -> (add (shl x, c2), c1 << c2)
// (shl (or x, c1), c2) -> (or (shl x, c2), c1 << c2
// Other code patterns that can be also be modified have the following form:
// b + ((a << 1) | 510)
// b + ((a << 1) & 510)
// b + ((a << 1) ^ 510)
// b + ((a << 1) + 510)
// 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
// No shifted operands for 16-bit instructions.
if (ST->isThumb() && ST->isThumb1Only())
return SDValue();
// Check that all the users could perform the shl themselves.
for (auto U : N->uses()) {
switch(U->getOpcode()) {
default:
return SDValue();
case ISD::SUB:
case ISD::ADD:
case ISD::AND:
case ISD::OR:
case ISD::XOR:
case ISD::SETCC:
case ARMISD::CMP:
// Check that its not already using a shl.
if (U->getOperand(0).getOpcode() == ISD::SHL ||
U->getOperand(1).getOpcode() == ISD::SHL)
return SDValue();
break;
}
}
if (N->getOpcode() != ISD::ADD && N->getOpcode() != ISD::OR &&
N->getOpcode() != ISD::XOR && N->getOpcode() != ISD::AND)
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() << "Trying to simplify shl: "; N->dump());
APInt C2Int = C2->getAPIntValue();
APInt C1Int = C1ShlC2->getAPIntValue();
// Check that performing a lshr will not lose any information.
APInt Mask = APInt::getHighBitsSet(C2Int.getBitWidth(),
C2Int.getBitWidth() - C2->getZExtValue());
if ((C1Int & Mask) != C1Int)
return SDValue();
// Shift the first constant.
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();
SelectionDAG &DAG = DCI.DAG;
SDLoc dl(N);
SDValue X = SHL.getOperand(0);
SDValue BinOp = DAG.getNode(N->getOpcode(), dl, MVT::i32, X,
DAG.getConstant(C1Int, dl, MVT::i32));
// Shift left to compensate for the lshr of C1Int.
SDValue Res = DAG.getNode(ISD::SHL, dl, MVT::i32, BinOp, SHL.getOperand(1));
DAG.ReplaceAllUsesWith(SDValue(N, 0), Res);
return SDValue(N, 0);
}
/// PerformADDCombine - Target-specific dag combine xforms for ISD::ADD. /// PerformADDCombine - Target-specific dag combine xforms for ISD::ADD.
/// ///
static SDValue PerformADDCombine(SDNode *N, static SDValue PerformADDCombine(SDNode *N,
TargetLowering::DAGCombinerInfo &DCI, TargetLowering::DAGCombinerInfo &DCI,
const ARMSubtarget *Subtarget) { const ARMSubtarget *Subtarget) {
SDValue N0 = N->getOperand(0); SDValue N0 = N->getOperand(0);
SDValue N1 = N->getOperand(1); SDValue N1 = N->getOperand(1);
// Only works one way, because it needs an immediate operand.
if (SDValue Result = PerformSHLSimplify(N, DCI, Subtarget))
return Result;
// First try with the default operand order. // First try with the default operand order.
if (SDValue Result = PerformADDCombineWithOperands(N, N0, N1, DCI, Subtarget)) if (SDValue Result = PerformADDCombineWithOperands(N, N0, N1, DCI, Subtarget))
return Result; return Result;
// If that didn't work, try again with the operands commuted. // If that didn't work, try again with the operands commuted.
return PerformADDCombineWithOperands(N, N1, N0, DCI, Subtarget); return PerformADDCombineWithOperands(N, N1, N0, DCI, Subtarget);
} }
▲ Show 20 Lines • Show All 172 Lines • ▼ Show 20 Lines if (SplatBitSize <= 64) {
} }
} }
} }
if (!Subtarget->isThumb1Only()) { if (!Subtarget->isThumb1Only()) {
// fold (and (select cc, -1, c), x) -> (select cc, x, (and, x, c)) // fold (and (select cc, -1, c), x) -> (select cc, x, (and, x, c))
if (SDValue Result = combineSelectAndUseCommutative(N, true, DCI)) if (SDValue Result = combineSelectAndUseCommutative(N, true, DCI))
return Result; return Result;
if (SDValue Result = PerformSHLSimplify(N, DCI, Subtarget))
return Result;
} }
return SDValue(); return SDValue();
} }
// Try combining OR nodes to SMULWB, SMULWT. // Try combining OR nodes to SMULWB, SMULWT.
static SDValue PerformORCombineToSMULWBT(SDNode *OR, static SDValue PerformORCombineToSMULWBT(SDNode *OR,
TargetLowering::DAGCombinerInfo &DCI, TargetLowering::DAGCombinerInfo &DCI,
▲ Show 20 Lines • Show All 217 Lines • ▼ Show 20 Linesstatic SDValue PerformORCombine(SDNode *N,
if (!Subtarget->isThumb1Only()) { if (!Subtarget->isThumb1Only()) {
// fold (or (select cc, 0, c), x) -> (select cc, x, (or, x, c)) // fold (or (select cc, 0, c), x) -> (select cc, x, (or, x, c))
if (SDValue Result = combineSelectAndUseCommutative(N, false, DCI)) if (SDValue Result = combineSelectAndUseCommutative(N, false, DCI))
return Result; return Result;
if (SDValue Result = PerformORCombineToSMULWBT(N, DCI, Subtarget)) if (SDValue Result = PerformORCombineToSMULWBT(N, DCI, Subtarget))
return Result; 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); SDValue N0 = N->getOperand(0);
if (N0.getOpcode() != ISD::AND || !N0.hasOneUse())
return SDValue();
SDValue N1 = N->getOperand(1); SDValue N1 = N->getOperand(1);
// (or (and B, A), (and C, ~A)) => (VBSL A, B, C) when A is a constant. // (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() && if (Subtarget->hasNEON() && N1.getOpcode() == ISD::AND && VT.isVector() &&
DAG.getTargetLoweringInfo().isTypeLegal(VT)) { 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; APInt SplatUndef;
unsigned SplatBitSize; unsigned SplatBitSize;
bool HasAnyUndefs; bool HasAnyUndefs;
APInt SplatBits0, SplatBits1; APInt SplatBits0, SplatBits1;
BuildVectorSDNode *BVN0 = dyn_cast<BuildVectorSDNode>(N0->getOperand(1)); BuildVectorSDNode *BVN0 = dyn_cast<BuildVectorSDNode>(N0->getOperand(1));
BuildVectorSDNode *BVN1 = dyn_cast<BuildVectorSDNode>(N1->getOperand(1)); BuildVectorSDNode *BVN1 = dyn_cast<BuildVectorSDNode>(N1->getOperand(1));
// Ensure that the second operand of both ands are constants // Ensure that the second operand of both ands are constants
Show All 16 Lines if (BVN0 && BVN0->isConstantSplat(SplatBits0, SplatUndef, SplatBitSize,
return DAG.getNode(ISD::BITCAST, dl, VT, Result); return DAG.getNode(ISD::BITCAST, dl, VT, Result);
} }
} }
} }
} }
// Try to use the ARM/Thumb2 BFI (bitfield insert) instruction when // Try to use the ARM/Thumb2 BFI (bitfield insert) instruction when
// reasonable. // reasonable.
if (N0.getOpcode() == ISD::AND && N0.hasOneUse()) {
if (SDValue Res = PerformORCombineToBFI(N, DCI, Subtarget)) if (SDValue Res = PerformORCombineToBFI(N, DCI, Subtarget))
return Res; return Res;
}
if (SDValue Result = PerformSHLSimplify(N, DCI, Subtarget))
return Result;
return SDValue(); return SDValue();
} }
static SDValue PerformXORCombine(SDNode *N, static SDValue PerformXORCombine(SDNode *N,
TargetLowering::DAGCombinerInfo &DCI, TargetLowering::DAGCombinerInfo &DCI,
const ARMSubtarget *Subtarget) { const ARMSubtarget *Subtarget) {
EVT VT = N->getValueType(0); EVT VT = N->getValueType(0);
SelectionDAG &DAG = DCI.DAG; SelectionDAG &DAG = DCI.DAG;
if(!DAG.getTargetLoweringInfo().isTypeLegal(VT)) if(!DAG.getTargetLoweringInfo().isTypeLegal(VT))
return SDValue(); return SDValue();
if (!Subtarget->isThumb1Only()) { if (!Subtarget->isThumb1Only()) {
// fold (xor (select cc, 0, c), x) -> (select cc, x, (xor, x, c)) // fold (xor (select cc, 0, c), x) -> (select cc, x, (xor, x, c))
if (SDValue Result = combineSelectAndUseCommutative(N, false, DCI)) if (SDValue Result = combineSelectAndUseCommutative(N, false, DCI))
return Result; return Result;
if (SDValue Result = PerformSHLSimplify(N, DCI, Subtarget))
return Result;
} }
return SDValue(); return SDValue();
} }
// ParseBFI - given a BFI instruction in N, extract the "from" value (Rn) and return it, // ParseBFI - given a BFI instruction in N, extract the "from" value (Rn) and return it,
// and fill in FromMask and ToMask with (consecutive) bits in "from" to be extracted and // and fill in FromMask and ToMask with (consecutive) bits in "from" to be extracted and
// their position in "to" (Rd). // their position in "to" (Rd).
▲ Show 20 Lines • Show All 3,682 Lines • Show Last 20 Lines

llvm/trunk/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: and r0, r0, #256
; CHECK: add r0, r1, r0, lsl #1
; CHECK-T2-NOT: mov
; CHECK-T2: and r0, r0, #256
; CHECK-T2: add.w r0, r1, r0, lsl #1
define arm_aapcscc i32 @unfold7(i32 %a, i32 %b) {
entry:
%shl = shl i32 %a, 1
%and = and i32 %shl, 512
%add = add nsw i32 %and, %b
ret i32 %add
}
; CHECK-LABEL: unfold8
; 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 @unfold8(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: unfold9
; CHECK-NOT: mov
; CHECK: eor r0, r0, #255
; CHECK: add r0, r1, r0, lsl #1
; CHECK-T2-NOT: mov
; CHECK-T2: eor r0, r0, #255
; CHECK-T2: add.w r0, r1, r0, lsl #1
define arm_aapcscc i32 @unfold9(i32 %a, i32 %b) {
entry:
%shl = shl i32 %a, 1
%xor = xor i32 %shl, 510
%add = add nsw i32 %xor, %b
ret i32 %add
}
; CHECK-LABEL: unfold10
; 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 @unfold10(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: unfold11
; 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 @unfold11(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
}