1 //=- AArch64ConditionOptimizer.cpp - Remove useless comparisons for AArch64 -=//
3 // The LLVM Compiler Infrastructure
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
8 //===----------------------------------------------------------------------===//
10 // This pass tries to make consecutive compares of values use same operands to
11 // allow CSE pass to remove duplicated instructions. For this it analyzes
12 // branches and adjusts comparisons with immediate values by converting:
17 // and adjusting immediate values appropriately. It basically corrects two
18 // immediate values towards each other to make them equal.
20 // Consider the following example in C:
22 // if ((a < 5 && ...) || (a > 5 && ...)) {
27 // Here both "x" and "y" expressions compare "a" with "5". When "x" evaluates
28 // to "false", "y" can just check flags set by the first comparison. As a
29 // result of the canonicalization employed by
30 // SelectionDAGBuilder::visitSwitchCase, DAGCombine, and other target-specific
31 // code, assembly ends up in the form that is not CSE friendly:
42 // Same assembly after the pass:
49 // cmp w8, #5 // <-- CSE pass removes this instruction
53 // Currently only SUBS and ADDS followed by b.?? are supported.
55 // TODO: maybe handle TBNZ/TBZ the same way as CMP when used instead for "a < 0"
56 // TODO: handle other conditional instructions (e.g. CSET)
57 // TODO: allow second branching to be anything if it doesn't require adjusting
59 //===----------------------------------------------------------------------===//
62 #include "llvm/ADT/DepthFirstIterator.h"
63 #include "llvm/ADT/SmallVector.h"
64 #include "llvm/ADT/Statistic.h"
65 #include "llvm/CodeGen/LiveIntervalAnalysis.h"
66 #include "llvm/CodeGen/MachineDominators.h"
67 #include "llvm/CodeGen/MachineFunction.h"
68 #include "llvm/CodeGen/MachineFunctionPass.h"
69 #include "llvm/CodeGen/MachineInstrBuilder.h"
70 #include "llvm/CodeGen/Passes.h"
71 #include "llvm/Support/CommandLine.h"
72 #include "llvm/Support/Debug.h"
73 #include "llvm/Support/raw_ostream.h"
74 #include "llvm/Target/TargetInstrInfo.h"
75 #include "llvm/Target/TargetSubtargetInfo.h"
81 #define DEBUG_TYPE "aarch64-condopt"
83 STATISTIC(NumConditionsAdjusted
, "Number of conditions adjusted");
86 class AArch64ConditionOptimizer
: public MachineFunctionPass
{
87 const TargetInstrInfo
*TII
;
88 MachineDominatorTree
*DomTree
;
91 // Stores immediate, compare instruction opcode and branch condition (in this
92 // order) of adjusted comparison.
93 typedef std::tuple
<int, int, AArch64CC::CondCode
> CmpInfo
;
96 AArch64ConditionOptimizer() : MachineFunctionPass(ID
) {}
97 void getAnalysisUsage(AnalysisUsage
&AU
) const override
;
98 MachineInstr
*findSuitableCompare(MachineBasicBlock
*MBB
);
99 CmpInfo
adjustCmp(MachineInstr
*CmpMI
, AArch64CC::CondCode Cmp
);
100 void modifyCmp(MachineInstr
*CmpMI
, const CmpInfo
&Info
);
101 bool adjustTo(MachineInstr
*CmpMI
, AArch64CC::CondCode Cmp
, MachineInstr
*To
,
103 bool runOnMachineFunction(MachineFunction
&MF
) override
;
104 const char *getPassName() const override
{
105 return "AArch64 Condition Optimizer";
108 } // end anonymous namespace
110 char AArch64ConditionOptimizer::ID
= 0;
113 void initializeAArch64ConditionOptimizerPass(PassRegistry
&);
116 INITIALIZE_PASS_BEGIN(AArch64ConditionOptimizer
, "aarch64-condopt",
117 "AArch64 CondOpt Pass", false, false)
118 INITIALIZE_PASS_DEPENDENCY(MachineDominatorTree
)
119 INITIALIZE_PASS_DEPENDENCY(LiveIntervals
)
120 INITIALIZE_PASS_END(AArch64ConditionOptimizer
, "aarch64-condopt",
121 "AArch64 CondOpt Pass", false, false)
123 FunctionPass
*llvm::createAArch64ConditionOptimizerPass() {
124 return new AArch64ConditionOptimizer();
127 void AArch64ConditionOptimizer::getAnalysisUsage(AnalysisUsage
&AU
) const {
128 AU
.addRequired
<MachineDominatorTree
>();
129 AU
.addPreserved
<MachineDominatorTree
>();
130 AU
.addRequired
<LiveIntervals
>();
131 AU
.addPreserved
<LiveIntervals
>();
132 MachineFunctionPass::getAnalysisUsage(AU
);
135 // Finds compare instruction that corresponds to supported types of branching.
136 // Returns the instruction or nullptr on failures or detecting unsupported
138 MachineInstr
*AArch64ConditionOptimizer::findSuitableCompare(
139 MachineBasicBlock
*MBB
) {
140 MachineBasicBlock::iterator I
= MBB
->getFirstTerminator();
144 if (I
->getOpcode() != AArch64::Bcc
)
147 // Now find the instruction controlling the terminator.
148 for (MachineBasicBlock::iterator B
= MBB
->begin(); I
!= B
;) {
150 assert(!I
->isTerminator() && "Spurious terminator");
151 switch (I
->getOpcode()) {
152 // cmp is an alias for subs with a dead destination register.
153 case AArch64::SUBSWri
:
154 case AArch64::SUBSXri
:
155 // cmn is an alias for adds with a dead destination register.
156 case AArch64::ADDSWri
:
157 case AArch64::ADDSXri
:
158 if (I
->getOperand(0).isDead())
161 DEBUG(dbgs() << "Destination of cmp is not dead, " << *I
<< '\n');
164 // Prevent false positive case like:
170 case AArch64::FCMPDri
:
171 case AArch64::FCMPSri
:
172 case AArch64::FCMPESri
:
173 case AArch64::FCMPEDri
:
175 case AArch64::SUBSWrr
:
176 case AArch64::SUBSXrr
:
177 case AArch64::ADDSWrr
:
178 case AArch64::ADDSXrr
:
179 case AArch64::FCMPSrr
:
180 case AArch64::FCMPDrr
:
181 case AArch64::FCMPESrr
:
182 case AArch64::FCMPEDrr
:
183 // Skip comparison instructions without immediate operands.
187 DEBUG(dbgs() << "Flags not defined in BB#" << MBB
->getNumber() << '\n');
191 // Changes opcode adds <-> subs considering register operand width.
192 static int getComplementOpc(int Opc
) {
194 case AArch64::ADDSWri
: return AArch64::SUBSWri
;
195 case AArch64::ADDSXri
: return AArch64::SUBSXri
;
196 case AArch64::SUBSWri
: return AArch64::ADDSWri
;
197 case AArch64::SUBSXri
: return AArch64::ADDSXri
;
199 llvm_unreachable("Unexpected opcode");
203 // Changes form of comparison inclusive <-> exclusive.
204 static AArch64CC::CondCode
getAdjustedCmp(AArch64CC::CondCode Cmp
) {
206 case AArch64CC::GT
: return AArch64CC::GE
;
207 case AArch64CC::GE
: return AArch64CC::GT
;
208 case AArch64CC::LT
: return AArch64CC::LE
;
209 case AArch64CC::LE
: return AArch64CC::LT
;
211 llvm_unreachable("Unexpected condition code");
215 // Transforms GT -> GE, GE -> GT, LT -> LE, LE -> LT by updating comparison
216 // operator and condition code.
217 AArch64ConditionOptimizer::CmpInfo
AArch64ConditionOptimizer::adjustCmp(
218 MachineInstr
*CmpMI
, AArch64CC::CondCode Cmp
) {
219 int Opc
= CmpMI
->getOpcode();
221 // CMN (compare with negative immediate) is an alias to ADDS (as
222 // "operand - negative" == "operand + positive")
223 bool Negative
= (Opc
== AArch64::ADDSWri
|| Opc
== AArch64::ADDSXri
);
225 int Correction
= (Cmp
== AArch64CC::GT
) ? 1 : -1;
226 // Negate Correction value for comparison with negative immediate (CMN).
228 Correction
= -Correction
;
231 const int OldImm
= (int)CmpMI
->getOperand(2).getImm();
232 const int NewImm
= std::abs(OldImm
+ Correction
);
234 // Handle +0 -> -1 and -0 -> +1 (CMN with 0 immediate) transitions by
235 // adjusting compare instruction opcode.
236 if (OldImm
== 0 && ((Negative
&& Correction
== 1) ||
237 (!Negative
&& Correction
== -1))) {
238 Opc
= getComplementOpc(Opc
);
241 return CmpInfo(NewImm
, Opc
, getAdjustedCmp(Cmp
));
244 // Applies changes to comparison instruction suggested by adjustCmp().
245 void AArch64ConditionOptimizer::modifyCmp(MachineInstr
*CmpMI
,
246 const CmpInfo
&Info
) {
249 AArch64CC::CondCode Cmp
;
250 std::tie(Imm
, Opc
, Cmp
) = Info
;
252 MachineBasicBlock
*const MBB
= CmpMI
->getParent();
254 // Change immediate in comparison instruction (ADDS or SUBS).
255 BuildMI(*MBB
, CmpMI
, CmpMI
->getDebugLoc(), TII
->get(Opc
))
256 .addOperand(CmpMI
->getOperand(0))
257 .addOperand(CmpMI
->getOperand(1))
259 .addOperand(CmpMI
->getOperand(3));
260 CmpMI
->eraseFromParent();
262 // The fact that this comparison was picked ensures that it's related to the
263 // first terminator instruction.
264 MachineInstr
*BrMI
= MBB
->getFirstTerminator();
266 // Change condition in branch instruction.
267 BuildMI(*MBB
, BrMI
, BrMI
->getDebugLoc(), TII
->get(AArch64::Bcc
))
269 .addOperand(BrMI
->getOperand(1));
270 BrMI
->eraseFromParent();
272 MBB
->updateTerminator();
274 ++NumConditionsAdjusted
;
277 // Parse a condition code returned by AnalyzeBranch, and compute the CondCode
278 // corresponding to TBB.
279 // Returns true if parsing was successful, otherwise false is returned.
280 static bool parseCond(ArrayRef
<MachineOperand
> Cond
, AArch64CC::CondCode
&CC
) {
281 // A normal br.cond simply has the condition code.
282 if (Cond
[0].getImm() != -1) {
283 assert(Cond
.size() == 1 && "Unknown Cond array format");
284 CC
= (AArch64CC::CondCode
)(int)Cond
[0].getImm();
290 // Adjusts one cmp instruction to another one if result of adjustment will allow
291 // CSE. Returns true if compare instruction was changed, otherwise false is
293 bool AArch64ConditionOptimizer::adjustTo(MachineInstr
*CmpMI
,
294 AArch64CC::CondCode Cmp
, MachineInstr
*To
, int ToImm
)
296 CmpInfo Info
= adjustCmp(CmpMI
, Cmp
);
297 if (std::get
<0>(Info
) == ToImm
&& std::get
<1>(Info
) == To
->getOpcode()) {
298 modifyCmp(CmpMI
, Info
);
304 bool AArch64ConditionOptimizer::runOnMachineFunction(MachineFunction
&MF
) {
305 DEBUG(dbgs() << "********** AArch64 Conditional Compares **********\n"
306 << "********** Function: " << MF
.getName() << '\n');
307 TII
= MF
.getTarget().getSubtargetImpl()->getInstrInfo();
308 DomTree
= &getAnalysis
<MachineDominatorTree
>();
310 bool Changed
= false;
312 // Visit blocks in dominator tree pre-order. The pre-order enables multiple
313 // cmp-conversions from the same head block.
314 // Note that updateDomTree() modifies the children of the DomTree node
315 // currently being visited. The df_iterator supports that; it doesn't look at
316 // child_begin() / child_end() until after a node has been visited.
317 for (MachineDomTreeNode
*I
: depth_first(DomTree
)) {
318 MachineBasicBlock
*HBB
= I
->getBlock();
320 SmallVector
<MachineOperand
, 4> HeadCond
;
321 MachineBasicBlock
*TBB
= nullptr, *FBB
= nullptr;
322 if (TII
->AnalyzeBranch(*HBB
, TBB
, FBB
, HeadCond
)) {
326 // Equivalence check is to skip loops.
327 if (!TBB
|| TBB
== HBB
) {
331 SmallVector
<MachineOperand
, 4> TrueCond
;
332 MachineBasicBlock
*TBB_TBB
= nullptr, *TBB_FBB
= nullptr;
333 if (TII
->AnalyzeBranch(*TBB
, TBB_TBB
, TBB_FBB
, TrueCond
)) {
337 MachineInstr
*HeadCmpMI
= findSuitableCompare(HBB
);
342 MachineInstr
*TrueCmpMI
= findSuitableCompare(TBB
);
347 AArch64CC::CondCode HeadCmp
;
348 if (HeadCond
.empty() || !parseCond(HeadCond
, HeadCmp
)) {
352 AArch64CC::CondCode TrueCmp
;
353 if (TrueCond
.empty() || !parseCond(TrueCond
, TrueCmp
)) {
357 const int HeadImm
= (int)HeadCmpMI
->getOperand(2).getImm();
358 const int TrueImm
= (int)TrueCmpMI
->getOperand(2).getImm();
360 DEBUG(dbgs() << "Head branch:\n");
361 DEBUG(dbgs() << "\tcondition: "
362 << AArch64CC::getCondCodeName(HeadCmp
) << '\n');
363 DEBUG(dbgs() << "\timmediate: " << HeadImm
<< '\n');
365 DEBUG(dbgs() << "True branch:\n");
366 DEBUG(dbgs() << "\tcondition: "
367 << AArch64CC::getCondCodeName(TrueCmp
) << '\n');
368 DEBUG(dbgs() << "\timmediate: " << TrueImm
<< '\n');
370 if (((HeadCmp
== AArch64CC::GT
&& TrueCmp
== AArch64CC::LT
) ||
371 (HeadCmp
== AArch64CC::LT
&& TrueCmp
== AArch64CC::GT
)) &&
372 std::abs(TrueImm
- HeadImm
) == 2) {
373 // This branch transforms machine instructions that correspond to
375 // 1) (a > {TrueImm} && ...) || (a < {HeadImm} && ...)
376 // 2) (a < {TrueImm} && ...) || (a > {HeadImm} && ...)
380 // 1) (a >= {NewImm} && ...) || (a <= {NewImm} && ...)
381 // 2) (a <= {NewImm} && ...) || (a >= {NewImm} && ...)
383 CmpInfo HeadCmpInfo
= adjustCmp(HeadCmpMI
, HeadCmp
);
384 CmpInfo TrueCmpInfo
= adjustCmp(TrueCmpMI
, TrueCmp
);
385 if (std::get
<0>(HeadCmpInfo
) == std::get
<0>(TrueCmpInfo
) &&
386 std::get
<1>(HeadCmpInfo
) == std::get
<1>(TrueCmpInfo
)) {
387 modifyCmp(HeadCmpMI
, HeadCmpInfo
);
388 modifyCmp(TrueCmpMI
, TrueCmpInfo
);
391 } else if (((HeadCmp
== AArch64CC::GT
&& TrueCmp
== AArch64CC::GT
) ||
392 (HeadCmp
== AArch64CC::LT
&& TrueCmp
== AArch64CC::LT
)) &&
393 std::abs(TrueImm
- HeadImm
) == 1) {
394 // This branch transforms machine instructions that correspond to
396 // 1) (a > {TrueImm} && ...) || (a > {HeadImm} && ...)
397 // 2) (a < {TrueImm} && ...) || (a < {HeadImm} && ...)
401 // 1) (a <= {NewImm} && ...) || (a > {NewImm} && ...)
402 // 2) (a < {NewImm} && ...) || (a >= {NewImm} && ...)
404 // GT -> GE transformation increases immediate value, so picking the
405 // smaller one; LT -> LE decreases immediate value so invert the choice.
406 bool adjustHeadCond
= (HeadImm
< TrueImm
);
407 if (HeadCmp
== AArch64CC::LT
) {
408 adjustHeadCond
= !adjustHeadCond
;
411 if (adjustHeadCond
) {
412 Changed
|= adjustTo(HeadCmpMI
, HeadCmp
, TrueCmpMI
, TrueImm
);
414 Changed
|= adjustTo(TrueCmpMI
, TrueCmp
, HeadCmpMI
, HeadImm
);
417 // Other transformation cases almost never occur due to generation of < or >
418 // comparisons instead of <= and >=.