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 "MCTargetDesc/AArch64AddressingModes.h"
63 #include "llvm/ADT/DepthFirstIterator.h"
64 #include "llvm/ADT/SmallVector.h"
65 #include "llvm/ADT/Statistic.h"
66 #include "llvm/CodeGen/LiveIntervalAnalysis.h"
67 #include "llvm/CodeGen/MachineDominators.h"
68 #include "llvm/CodeGen/MachineFunction.h"
69 #include "llvm/CodeGen/MachineFunctionPass.h"
70 #include "llvm/CodeGen/MachineInstrBuilder.h"
71 #include "llvm/CodeGen/MachineRegisterInfo.h"
72 #include "llvm/CodeGen/Passes.h"
73 #include "llvm/Support/Debug.h"
74 #include "llvm/Support/raw_ostream.h"
75 #include "llvm/Target/TargetInstrInfo.h"
76 #include "llvm/Target/TargetSubtargetInfo.h"
82 #define DEBUG_TYPE "aarch64-condopt"
84 STATISTIC(NumConditionsAdjusted, "Number of conditions adjusted");
87 class AArch64ConditionOptimizer : public MachineFunctionPass {
88 const TargetInstrInfo *TII;
89 MachineDominatorTree *DomTree;
90 const MachineRegisterInfo *MRI;
93 // Stores immediate, compare instruction opcode and branch condition (in this
94 // order) of adjusted comparison.
95 typedef std::tuple<int, unsigned, AArch64CC::CondCode> CmpInfo;
98 AArch64ConditionOptimizer() : MachineFunctionPass(ID) {
99 initializeAArch64ConditionOptimizerPass(*PassRegistry::getPassRegistry());
101 void getAnalysisUsage(AnalysisUsage &AU) const override;
102 MachineInstr *findSuitableCompare(MachineBasicBlock *MBB);
103 CmpInfo adjustCmp(MachineInstr *CmpMI, AArch64CC::CondCode Cmp);
104 void modifyCmp(MachineInstr *CmpMI, const CmpInfo &Info);
105 bool adjustTo(MachineInstr *CmpMI, AArch64CC::CondCode Cmp, MachineInstr *To,
107 bool runOnMachineFunction(MachineFunction &MF) override;
108 StringRef getPassName() const override {
109 return "AArch64 Condition Optimizer";
112 } // end anonymous namespace
114 char AArch64ConditionOptimizer::ID = 0;
116 INITIALIZE_PASS_BEGIN(AArch64ConditionOptimizer, "aarch64-condopt",
117 "AArch64 CondOpt Pass", false, false)
118 INITIALIZE_PASS_DEPENDENCY(MachineDominatorTree)
119 INITIALIZE_PASS_END(AArch64ConditionOptimizer, "aarch64-condopt",
120 "AArch64 CondOpt Pass", false, false)
122 FunctionPass *llvm::createAArch64ConditionOptimizerPass() {
123 return new AArch64ConditionOptimizer();
126 void AArch64ConditionOptimizer::getAnalysisUsage(AnalysisUsage &AU) const {
127 AU.addRequired<MachineDominatorTree>();
128 AU.addPreserved<MachineDominatorTree>();
129 MachineFunctionPass::getAnalysisUsage(AU);
132 // Finds compare instruction that corresponds to supported types of branching.
133 // Returns the instruction or nullptr on failures or detecting unsupported
135 MachineInstr *AArch64ConditionOptimizer::findSuitableCompare(
136 MachineBasicBlock *MBB) {
137 MachineBasicBlock::iterator I = MBB->getFirstTerminator();
141 if (I->getOpcode() != AArch64::Bcc)
144 // Since we may modify cmp of this MBB, make sure NZCV does not live out.
145 for (auto SuccBB : MBB->successors())
146 if (SuccBB->isLiveIn(AArch64::NZCV))
149 // Now find the instruction controlling the terminator.
150 for (MachineBasicBlock::iterator B = MBB->begin(); I != B;) {
152 assert(!I->isTerminator() && "Spurious terminator");
153 // Check if there is any use of NZCV between CMP and Bcc.
154 if (I->readsRegister(AArch64::NZCV))
156 switch (I->getOpcode()) {
157 // cmp is an alias for subs with a dead destination register.
158 case AArch64::SUBSWri:
159 case AArch64::SUBSXri:
160 // cmn is an alias for adds with a dead destination register.
161 case AArch64::ADDSWri:
162 case AArch64::ADDSXri: {
163 unsigned ShiftAmt = AArch64_AM::getShiftValue(I->getOperand(3).getImm());
164 if (!I->getOperand(2).isImm()) {
165 DEBUG(dbgs() << "Immediate of cmp is symbolic, " << *I << '\n');
167 } else if (I->getOperand(2).getImm() << ShiftAmt >= 0xfff) {
168 DEBUG(dbgs() << "Immediate of cmp may be out of range, " << *I << '\n');
170 } else if (!MRI->use_empty(I->getOperand(0).getReg())) {
171 DEBUG(dbgs() << "Destination of cmp is not dead, " << *I << '\n');
176 // Prevent false positive case like:
182 case AArch64::FCMPDri:
183 case AArch64::FCMPSri:
184 case AArch64::FCMPESri:
185 case AArch64::FCMPEDri:
187 case AArch64::SUBSWrr:
188 case AArch64::SUBSXrr:
189 case AArch64::ADDSWrr:
190 case AArch64::ADDSXrr:
191 case AArch64::FCMPSrr:
192 case AArch64::FCMPDrr:
193 case AArch64::FCMPESrr:
194 case AArch64::FCMPEDrr:
195 // Skip comparison instructions without immediate operands.
199 DEBUG(dbgs() << "Flags not defined in BB#" << MBB->getNumber() << '\n');
203 // Changes opcode adds <-> subs considering register operand width.
204 static int getComplementOpc(int Opc) {
206 case AArch64::ADDSWri: return AArch64::SUBSWri;
207 case AArch64::ADDSXri: return AArch64::SUBSXri;
208 case AArch64::SUBSWri: return AArch64::ADDSWri;
209 case AArch64::SUBSXri: return AArch64::ADDSXri;
211 llvm_unreachable("Unexpected opcode");
215 // Changes form of comparison inclusive <-> exclusive.
216 static AArch64CC::CondCode getAdjustedCmp(AArch64CC::CondCode Cmp) {
218 case AArch64CC::GT: return AArch64CC::GE;
219 case AArch64CC::GE: return AArch64CC::GT;
220 case AArch64CC::LT: return AArch64CC::LE;
221 case AArch64CC::LE: return AArch64CC::LT;
223 llvm_unreachable("Unexpected condition code");
227 // Transforms GT -> GE, GE -> GT, LT -> LE, LE -> LT by updating comparison
228 // operator and condition code.
229 AArch64ConditionOptimizer::CmpInfo AArch64ConditionOptimizer::adjustCmp(
230 MachineInstr *CmpMI, AArch64CC::CondCode Cmp) {
231 unsigned Opc = CmpMI->getOpcode();
233 // CMN (compare with negative immediate) is an alias to ADDS (as
234 // "operand - negative" == "operand + positive")
235 bool Negative = (Opc == AArch64::ADDSWri || Opc == AArch64::ADDSXri);
237 int Correction = (Cmp == AArch64CC::GT) ? 1 : -1;
238 // Negate Correction value for comparison with negative immediate (CMN).
240 Correction = -Correction;
243 const int OldImm = (int)CmpMI->getOperand(2).getImm();
244 const int NewImm = std::abs(OldImm + Correction);
246 // Handle +0 -> -1 and -0 -> +1 (CMN with 0 immediate) transitions by
247 // adjusting compare instruction opcode.
248 if (OldImm == 0 && ((Negative && Correction == 1) ||
249 (!Negative && Correction == -1))) {
250 Opc = getComplementOpc(Opc);
253 return CmpInfo(NewImm, Opc, getAdjustedCmp(Cmp));
256 // Applies changes to comparison instruction suggested by adjustCmp().
257 void AArch64ConditionOptimizer::modifyCmp(MachineInstr *CmpMI,
258 const CmpInfo &Info) {
261 AArch64CC::CondCode Cmp;
262 std::tie(Imm, Opc, Cmp) = Info;
264 MachineBasicBlock *const MBB = CmpMI->getParent();
266 // Change immediate in comparison instruction (ADDS or SUBS).
267 BuildMI(*MBB, CmpMI, CmpMI->getDebugLoc(), TII->get(Opc))
268 .addOperand(CmpMI->getOperand(0))
269 .addOperand(CmpMI->getOperand(1))
271 .addOperand(CmpMI->getOperand(3));
272 CmpMI->eraseFromParent();
274 // The fact that this comparison was picked ensures that it's related to the
275 // first terminator instruction.
276 MachineInstr &BrMI = *MBB->getFirstTerminator();
278 // Change condition in branch instruction.
279 BuildMI(*MBB, BrMI, BrMI.getDebugLoc(), TII->get(AArch64::Bcc))
281 .addOperand(BrMI.getOperand(1));
282 BrMI.eraseFromParent();
284 MBB->updateTerminator();
286 ++NumConditionsAdjusted;
289 // Parse a condition code returned by AnalyzeBranch, and compute the CondCode
290 // corresponding to TBB.
291 // Returns true if parsing was successful, otherwise false is returned.
292 static bool parseCond(ArrayRef<MachineOperand> Cond, AArch64CC::CondCode &CC) {
293 // A normal br.cond simply has the condition code.
294 if (Cond[0].getImm() != -1) {
295 assert(Cond.size() == 1 && "Unknown Cond array format");
296 CC = (AArch64CC::CondCode)(int)Cond[0].getImm();
302 // Adjusts one cmp instruction to another one if result of adjustment will allow
303 // CSE. Returns true if compare instruction was changed, otherwise false is
305 bool AArch64ConditionOptimizer::adjustTo(MachineInstr *CmpMI,
306 AArch64CC::CondCode Cmp, MachineInstr *To, int ToImm)
308 CmpInfo Info = adjustCmp(CmpMI, Cmp);
309 if (std::get<0>(Info) == ToImm && std::get<1>(Info) == To->getOpcode()) {
310 modifyCmp(CmpMI, Info);
316 bool AArch64ConditionOptimizer::runOnMachineFunction(MachineFunction &MF) {
317 DEBUG(dbgs() << "********** AArch64 Conditional Compares **********\n"
318 << "********** Function: " << MF.getName() << '\n');
319 if (skipFunction(*MF.getFunction()))
322 TII = MF.getSubtarget().getInstrInfo();
323 DomTree = &getAnalysis<MachineDominatorTree>();
324 MRI = &MF.getRegInfo();
326 bool Changed = false;
328 // Visit blocks in dominator tree pre-order. The pre-order enables multiple
329 // cmp-conversions from the same head block.
330 // Note that updateDomTree() modifies the children of the DomTree node
331 // currently being visited. The df_iterator supports that; it doesn't look at
332 // child_begin() / child_end() until after a node has been visited.
333 for (MachineDomTreeNode *I : depth_first(DomTree)) {
334 MachineBasicBlock *HBB = I->getBlock();
336 SmallVector<MachineOperand, 4> HeadCond;
337 MachineBasicBlock *TBB = nullptr, *FBB = nullptr;
338 if (TII->analyzeBranch(*HBB, TBB, FBB, HeadCond)) {
342 // Equivalence check is to skip loops.
343 if (!TBB || TBB == HBB) {
347 SmallVector<MachineOperand, 4> TrueCond;
348 MachineBasicBlock *TBB_TBB = nullptr, *TBB_FBB = nullptr;
349 if (TII->analyzeBranch(*TBB, TBB_TBB, TBB_FBB, TrueCond)) {
353 MachineInstr *HeadCmpMI = findSuitableCompare(HBB);
358 MachineInstr *TrueCmpMI = findSuitableCompare(TBB);
363 AArch64CC::CondCode HeadCmp;
364 if (HeadCond.empty() || !parseCond(HeadCond, HeadCmp)) {
368 AArch64CC::CondCode TrueCmp;
369 if (TrueCond.empty() || !parseCond(TrueCond, TrueCmp)) {
373 const int HeadImm = (int)HeadCmpMI->getOperand(2).getImm();
374 const int TrueImm = (int)TrueCmpMI->getOperand(2).getImm();
376 DEBUG(dbgs() << "Head branch:\n");
377 DEBUG(dbgs() << "\tcondition: "
378 << AArch64CC::getCondCodeName(HeadCmp) << '\n');
379 DEBUG(dbgs() << "\timmediate: " << HeadImm << '\n');
381 DEBUG(dbgs() << "True branch:\n");
382 DEBUG(dbgs() << "\tcondition: "
383 << AArch64CC::getCondCodeName(TrueCmp) << '\n');
384 DEBUG(dbgs() << "\timmediate: " << TrueImm << '\n');
386 if (((HeadCmp == AArch64CC::GT && TrueCmp == AArch64CC::LT) ||
387 (HeadCmp == AArch64CC::LT && TrueCmp == AArch64CC::GT)) &&
388 std::abs(TrueImm - HeadImm) == 2) {
389 // This branch transforms machine instructions that correspond to
391 // 1) (a > {TrueImm} && ...) || (a < {HeadImm} && ...)
392 // 2) (a < {TrueImm} && ...) || (a > {HeadImm} && ...)
396 // 1) (a >= {NewImm} && ...) || (a <= {NewImm} && ...)
397 // 2) (a <= {NewImm} && ...) || (a >= {NewImm} && ...)
399 CmpInfo HeadCmpInfo = adjustCmp(HeadCmpMI, HeadCmp);
400 CmpInfo TrueCmpInfo = adjustCmp(TrueCmpMI, TrueCmp);
401 if (std::get<0>(HeadCmpInfo) == std::get<0>(TrueCmpInfo) &&
402 std::get<1>(HeadCmpInfo) == std::get<1>(TrueCmpInfo)) {
403 modifyCmp(HeadCmpMI, HeadCmpInfo);
404 modifyCmp(TrueCmpMI, TrueCmpInfo);
407 } else if (((HeadCmp == AArch64CC::GT && TrueCmp == AArch64CC::GT) ||
408 (HeadCmp == AArch64CC::LT && TrueCmp == AArch64CC::LT)) &&
409 std::abs(TrueImm - HeadImm) == 1) {
410 // This branch transforms machine instructions that correspond to
412 // 1) (a > {TrueImm} && ...) || (a > {HeadImm} && ...)
413 // 2) (a < {TrueImm} && ...) || (a < {HeadImm} && ...)
417 // 1) (a <= {NewImm} && ...) || (a > {NewImm} && ...)
418 // 2) (a < {NewImm} && ...) || (a >= {NewImm} && ...)
420 // GT -> GE transformation increases immediate value, so picking the
421 // smaller one; LT -> LE decreases immediate value so invert the choice.
422 bool adjustHeadCond = (HeadImm < TrueImm);
423 if (HeadCmp == AArch64CC::LT) {
424 adjustHeadCond = !adjustHeadCond;
427 if (adjustHeadCond) {
428 Changed |= adjustTo(HeadCmpMI, HeadCmp, TrueCmpMI, TrueImm);
430 Changed |= adjustTo(TrueCmpMI, TrueCmp, HeadCmpMI, HeadImm);
433 // Other transformation cases almost never occur due to generation of < or >
434 // comparisons instead of <= and >=.