This is an archive of the discontinued LLVM Phabricator instance.

Differential D73924

[AArch64][GlobalISel] Fold G_SHL into TB(N)Z bit calculation
ClosedPublic

Authored by paquette on Feb 3 2020, 1:47 PM.

Details

Reviewers
aemerson
Commits
rG37910fd0e1fd: [AArch64][GlobalISel] Fold G_SHL into TB(N)Z bit calculation
Summary

This implements the following optimization:

(tbz (shl x, c), b) -> (tbz x, b-c)

Which appears in getTestBitOperand in AArch64ISelLowering.cpp.

If we test bit b of shl x, c, we can fold away the shl by looking c bits to the right of b in x when this fits in the type. So, we can just test the b-cth bit.

Diff Detail

Event Timeline

paquette created this revision.Feb 3 2020, 1:47 PM
Herald added a project: Restricted Project. · View Herald TranscriptFeb 3 2020, 1:47 PM
Herald added subscribers: Petar.Avramovic, hiraditya, kristof.beyls, rovka. · View Herald Transcript
paquette updated this revision to Diff 242177.Feb 3 2020, 1:49 PM

fix typo

aemerson accepted this revision.Feb 3 2020, 2:21 PM
aemerson added inline comments.
llvm/lib/Target/AArch64/AArch64InstructionSelector.cpp
1063

I guess the case where b-c is negative isn't hit in real code. If it does come from real world code then the entire condbr can be folded away as always/never taken tbz/tbnz.

This revision is now accepted and ready to land.Feb 3 2020, 2:21 PM
Closed by commit rG37910fd0e1fd: [AArch64][GlobalISel] Fold G_SHL into TB(N)Z bit calculation (authored by paquette). · Explain WhyFeb 3 2020, 2:33 PM
This revision was automatically updated to reflect the committed changes.

Revision Contents

PathSize
llvm/
lib/
Target/
AArch64/
19 lines
test/
CodeGen/
AArch64/
GlobalISel/
114 lines

Diff 242177

llvm/lib/Target/AArch64/AArch64InstructionSelector.cpp

Show First 20 Lines • Show All 985 Lines • ▼ Show 20 Lines case CmpInst::FCMP_ULE:
break; break;
case CmpInst::FCMP_UNE: case CmpInst::FCMP_UNE:
CondCode = AArch64CC::NE; CondCode = AArch64CC::NE;
break; break;
} }
} }
/// Return a register which can be used as a bit to test in a TB(N)Z. /// Return a register which can be used as a bit to test in a TB(N)Z.
static Register getTestBitReg(Register Reg, uint64_t Bit, static Register getTestBitReg(Register Reg, uint64_t &Bit,
MachineRegisterInfo &MRI) { MachineRegisterInfo &MRI) {
assert(Reg.isValid() && "Expected valid register!"); assert(Reg.isValid() && "Expected valid register!");
while (MachineInstr *MI = getDefIgnoringCopies(Reg, MRI)) { while (MachineInstr *MI = getDefIgnoringCopies(Reg, MRI)) {
unsigned Opc = MI->getOpcode(); unsigned Opc = MI->getOpcode();
// (tbz (any_ext x), b) -> (tbz x, b) if we don't use the extended bits. // (tbz (any_ext x), b) -> (tbz x, b) if we don't use the extended bits.
// //
// (tbz (trunc x), b) -> (tbz x, b) is always safe, because the bit number // (tbz (trunc x), b) -> (tbz x, b) is always safe, because the bit number
// on the truncated x is the same as the bit number on x. // on the truncated x is the same as the bit number on x.
Show All 23 Lines case TargetOpcode::G_AND: {
// AND commutes, check the other side for a constant. // AND commutes, check the other side for a constant.
// FIXME: Can we canonicalize the constant so that it's always on the // FIXME: Can we canonicalize the constant so that it's always on the
// same side at some point earlier? // same side at some point earlier?
std::swap(ConstantReg, TestReg); std::swap(ConstantReg, TestReg);
VRegAndVal = getConstantVRegValWithLookThrough(ConstantReg, MRI); VRegAndVal = getConstantVRegValWithLookThrough(ConstantReg, MRI);
} }
if (VRegAndVal) if (VRegAndVal)
C = VRegAndVal->Value; C = VRegAndVal->Value;
break;
}
case TargetOpcode::G_SHL: {
TestReg = MI->getOperand(1).getReg();
auto VRegAndVal =
getConstantVRegValWithLookThrough(MI->getOperand(2).getReg(), MRI);
if (VRegAndVal)
C = VRegAndVal->Value;
break;
} }
} }
// Didn't find a constant. Bail out of the loop. // Didn't find a constant. Bail out of the loop.
if (!C) if (!C)
break; break;
// We found a suitable instruction with a constant. Check to see if we can // We found a suitable instruction with a constant. Check to see if we can
// walk through the instruction. // walk through the instruction.
Register NextReg; Register NextReg;
switch (Opc) { switch (Opc) {
default: default:
break; break;
case TargetOpcode::G_AND: case TargetOpcode::G_AND:
// (tbz (and x, m), b) -> (tbz x, b) when the b-th bit of m is set. // (tbz (and x, m), b) -> (tbz x, b) when the b-th bit of m is set.
if ((*C >> Bit) & 1) if ((*C >> Bit) & 1)
NextReg = TestReg; NextReg = TestReg;
break; break;
case TargetOpcode::G_SHL:
// (tbz (shl x, c), b) -> (tbz x, b-c) when b-c is positive and fits in
// the type of the register.
aemersonUnsubmitted
Not Done
ReplyInline Actions

I guess the case where b-c is negative isn't hit in real code. If it does come from real world code then the entire condbr can be folded away as always/never taken tbz/tbnz.

aemerson: I guess the case where b-c is negative isn't hit in real code. If it does come from real world…
if (*C <= Bit && (Bit - *C) < MRI.getType(TestReg).getSizeInBits()) {
NextReg = TestReg;
Bit = Bit - *C;
}
break;
} }
// Check if we found anything worth folding. // Check if we found anything worth folding.
if (!NextReg.isValid() || !MRI.hasOneUse(NextReg)) if (!NextReg.isValid() || !MRI.hasOneUse(NextReg))
break; break;
Reg = NextReg; Reg = NextReg;
} }
▲ Show 20 Lines • Show All 4,125 Lines • Show Last 20 Lines

llvm/test/CodeGen/AArch64/GlobalISel/opt-fold-shift-tbz-tbnz.mir

  • This file was added.
# NOTE: Assertions have been autogenerated by utils/update_mir_test_checks.py
# RUN: llc -mtriple aarch64-unknown-unknown -run-pass=instruction-select -verify-machineinstrs %s -o - | FileCheck %s
#
# Check folding a G_SHL into a G_BRCOND which has been matched as a TB(N)Z.
...
---
name: fold_shl
alignment: 4
legalized: true
regBankSelected: true
body: |
; CHECK-LABEL: name: fold_shl
; CHECK: bb.0:
; CHECK: successors: %bb.0(0x40000000), %bb.1(0x40000000)
; CHECK: %copy:gpr64all = COPY $x0
; CHECK: [[COPY:%[0-9]+]]:gpr32all = COPY %copy.sub_32
; CHECK: [[COPY1:%[0-9]+]]:gpr32 = COPY [[COPY]]
; CHECK: TBNZW [[COPY1]], 2, %bb.1
; CHECK: B %bb.0
; CHECK: bb.1:
; CHECK: RET_ReallyLR
bb.0:
successors: %bb.0, %bb.1
liveins: $x0
%copy:gpr(s64) = COPY $x0
%bit:gpr(s64) = G_CONSTANT i64 8
%zero:gpr(s64) = G_CONSTANT i64 0
; tbnz (shl x, 1), 3 == tbnz x, 2
%fold_cst:gpr(s64) = G_CONSTANT i64 1
%fold_me:gpr(s64) = G_SHL %copy, %fold_cst
%and:gpr(s64) = G_AND %fold_me, %bit
%cmp:gpr(s32) = G_ICMP intpred(ne), %and(s64), %zero
%cmp_trunc:gpr(s1) = G_TRUNC %cmp(s32)
G_BRCOND %cmp_trunc(s1), %bb.1
G_BR %bb.0
bb.1:
RET_ReallyLR
...
---
name: dont_fold_shl_1
alignment: 4
legalized: true
regBankSelected: true
body: |
; CHECK-LABEL: name: dont_fold_shl_1
; CHECK: bb.0:
; CHECK: successors: %bb.0(0x40000000), %bb.1(0x40000000)
; CHECK: %copy:gpr64 = COPY $x0
; CHECK: %fold_me:gpr64 = UBFMXri %copy, 59, 58
; CHECK: [[COPY:%[0-9]+]]:gpr64all = COPY %fold_me
; CHECK: [[COPY1:%[0-9]+]]:gpr32all = COPY [[COPY]].sub_32
; CHECK: [[COPY2:%[0-9]+]]:gpr32 = COPY [[COPY1]]
; CHECK: TBNZW [[COPY2]], 3, %bb.1
; CHECK: B %bb.0
; CHECK: bb.1:
; CHECK: RET_ReallyLR
bb.0:
successors: %bb.0, %bb.1
liveins: $x0
%copy:gpr(s64) = COPY $x0
%bit:gpr(s64) = G_CONSTANT i64 8
%zero:gpr(s64) = G_CONSTANT i64 0
; 5 > 3, so we cannot do the transformation as above.
%fold_cst:gpr(s64) = G_CONSTANT i64 5
%fold_me:gpr(s64) = G_SHL %copy, %fold_cst
%and:gpr(s64) = G_AND %fold_me, %bit
%cmp:gpr(s32) = G_ICMP intpred(ne), %and(s64), %zero
%cmp_trunc:gpr(s1) = G_TRUNC %cmp(s32)
G_BRCOND %cmp_trunc(s1), %bb.1
G_BR %bb.0
bb.1:
RET_ReallyLR
...
---
name: dont_fold_shl_2
alignment: 4
legalized: true
regBankSelected: true
body: |
; CHECK-LABEL: name: dont_fold_shl_2
; CHECK: bb.0:
; CHECK: successors: %bb.0(0x40000000), %bb.1(0x40000000)
; CHECK: %copy:gpr64 = COPY $x0
; CHECK: %fold_cst:gpr64 = MOVi64imm -5
; CHECK: %fold_me:gpr64 = LSLVXr %copy, %fold_cst
; CHECK: [[COPY:%[0-9]+]]:gpr64all = COPY %fold_me
; CHECK: [[COPY1:%[0-9]+]]:gpr32all = COPY [[COPY]].sub_32
; CHECK: [[COPY2:%[0-9]+]]:gpr32 = COPY [[COPY1]]
; CHECK: TBNZW [[COPY2]], 3, %bb.1
; CHECK: B %bb.0
; CHECK: bb.1:
; CHECK: RET_ReallyLR
bb.0:
successors: %bb.0, %bb.1
liveins: $x0
%copy:gpr(s64) = COPY $x0
%bit:gpr(s64) = G_CONSTANT i64 8
%zero:gpr(s64) = G_CONSTANT i64 0
; Same case as above, except we wrap around.
%fold_cst:gpr(s64) = G_CONSTANT i64 -5
%fold_me:gpr(s64) = G_SHL %copy, %fold_cst
%and:gpr(s64) = G_AND %fold_me, %bit
%cmp:gpr(s32) = G_ICMP intpred(ne), %and(s64), %zero
%cmp_trunc:gpr(s1) = G_TRUNC %cmp(s32)
G_BRCOND %cmp_trunc(s1), %bb.1
G_BR %bb.0
bb.1:
RET_ReallyLR