Line data Source code
1 : //=- AArch64ConditionOptimizer.cpp - Remove useless comparisons for AArch64 -=//
2 : //
3 : // The LLVM Compiler Infrastructure
4 : //
5 : // This file is distributed under the University of Illinois Open Source
6 : // License. See LICENSE.TXT for details.
7 : //
8 : //===----------------------------------------------------------------------===//
9 : //
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:
13 : // * GE -> GT
14 : // * GT -> GE
15 : // * LT -> LE
16 : // * LE -> LT
17 : // and adjusting immediate values appropriately. It basically corrects two
18 : // immediate values towards each other to make them equal.
19 : //
20 : // Consider the following example in C:
21 : //
22 : // if ((a < 5 && ...) || (a > 5 && ...)) {
23 : // ~~~~~ ~~~~~
24 : // ^ ^
25 : // x y
26 : //
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:
32 : //
33 : // ...
34 : // cmp w8, #4
35 : // b.gt .LBB0_3
36 : // ...
37 : // .LBB0_3:
38 : // cmp w8, #6
39 : // b.lt .LBB0_6
40 : // ...
41 : //
42 : // Same assembly after the pass:
43 : //
44 : // ...
45 : // cmp w8, #5
46 : // b.ge .LBB0_3
47 : // ...
48 : // .LBB0_3:
49 : // cmp w8, #5 // <-- CSE pass removes this instruction
50 : // b.le .LBB0_6
51 : // ...
52 : //
53 : // Currently only SUBS and ADDS followed by b.?? are supported.
54 : //
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
58 : //
59 : //===----------------------------------------------------------------------===//
60 :
61 : #include "AArch64.h"
62 : #include "MCTargetDesc/AArch64AddressingModes.h"
63 : #include "Utils/AArch64BaseInfo.h"
64 : #include "llvm/ADT/ArrayRef.h"
65 : #include "llvm/ADT/DepthFirstIterator.h"
66 : #include "llvm/ADT/SmallVector.h"
67 : #include "llvm/ADT/Statistic.h"
68 : #include "llvm/CodeGen/MachineBasicBlock.h"
69 : #include "llvm/CodeGen/MachineDominators.h"
70 : #include "llvm/CodeGen/MachineFunction.h"
71 : #include "llvm/CodeGen/MachineFunctionPass.h"
72 : #include "llvm/CodeGen/MachineInstr.h"
73 : #include "llvm/CodeGen/MachineInstrBuilder.h"
74 : #include "llvm/CodeGen/MachineOperand.h"
75 : #include "llvm/CodeGen/MachineRegisterInfo.h"
76 : #include "llvm/CodeGen/TargetInstrInfo.h"
77 : #include "llvm/CodeGen/TargetSubtargetInfo.h"
78 : #include "llvm/Pass.h"
79 : #include "llvm/Support/Debug.h"
80 : #include "llvm/Support/ErrorHandling.h"
81 : #include "llvm/Support/raw_ostream.h"
82 : #include <cassert>
83 : #include <cstdlib>
84 : #include <tuple>
85 :
86 : using namespace llvm;
87 :
88 : #define DEBUG_TYPE "aarch64-condopt"
89 :
90 : STATISTIC(NumConditionsAdjusted, "Number of conditions adjusted");
91 :
92 : namespace {
93 :
94 : class AArch64ConditionOptimizer : public MachineFunctionPass {
95 : const TargetInstrInfo *TII;
96 : MachineDominatorTree *DomTree;
97 : const MachineRegisterInfo *MRI;
98 :
99 : public:
100 : // Stores immediate, compare instruction opcode and branch condition (in this
101 : // order) of adjusted comparison.
102 : using CmpInfo = std::tuple<int, unsigned, AArch64CC::CondCode>;
103 :
104 : static char ID;
105 :
106 1120 : AArch64ConditionOptimizer() : MachineFunctionPass(ID) {
107 1120 : initializeAArch64ConditionOptimizerPass(*PassRegistry::getPassRegistry());
108 1120 : }
109 :
110 : void getAnalysisUsage(AnalysisUsage &AU) const override;
111 : MachineInstr *findSuitableCompare(MachineBasicBlock *MBB);
112 : CmpInfo adjustCmp(MachineInstr *CmpMI, AArch64CC::CondCode Cmp);
113 : void modifyCmp(MachineInstr *CmpMI, const CmpInfo &Info);
114 : bool adjustTo(MachineInstr *CmpMI, AArch64CC::CondCode Cmp, MachineInstr *To,
115 : int ToImm);
116 : bool runOnMachineFunction(MachineFunction &MF) override;
117 :
118 1114 : StringRef getPassName() const override {
119 1114 : return "AArch64 Condition Optimizer";
120 : }
121 : };
122 :
123 : } // end anonymous namespace
124 :
125 : char AArch64ConditionOptimizer::ID = 0;
126 :
127 85109 : INITIALIZE_PASS_BEGIN(AArch64ConditionOptimizer, "aarch64-condopt",
128 : "AArch64 CondOpt Pass", false, false)
129 85109 : INITIALIZE_PASS_DEPENDENCY(MachineDominatorTree)
130 200152 : INITIALIZE_PASS_END(AArch64ConditionOptimizer, "aarch64-condopt",
131 : "AArch64 CondOpt Pass", false, false)
132 :
133 1120 : FunctionPass *llvm::createAArch64ConditionOptimizerPass() {
134 1120 : return new AArch64ConditionOptimizer();
135 : }
136 :
137 1107 : void AArch64ConditionOptimizer::getAnalysisUsage(AnalysisUsage &AU) const {
138 : AU.addRequired<MachineDominatorTree>();
139 : AU.addPreserved<MachineDominatorTree>();
140 1107 : MachineFunctionPass::getAnalysisUsage(AU);
141 1107 : }
142 :
143 : // Finds compare instruction that corresponds to supported types of branching.
144 : // Returns the instruction or nullptr on failures or detecting unsupported
145 : // instructions.
146 0 : MachineInstr *AArch64ConditionOptimizer::findSuitableCompare(
147 : MachineBasicBlock *MBB) {
148 0 : MachineBasicBlock::iterator I = MBB->getFirstTerminator();
149 0 : if (I == MBB->end())
150 0 : return nullptr;
151 :
152 0 : if (I->getOpcode() != AArch64::Bcc)
153 0 : return nullptr;
154 :
155 : // Since we may modify cmp of this MBB, make sure NZCV does not live out.
156 0 : for (auto SuccBB : MBB->successors())
157 0 : if (SuccBB->isLiveIn(AArch64::NZCV))
158 0 : return nullptr;
159 :
160 : // Now find the instruction controlling the terminator.
161 0 : for (MachineBasicBlock::iterator B = MBB->begin(); I != B;) {
162 : --I;
163 : assert(!I->isTerminator() && "Spurious terminator");
164 : // Check if there is any use of NZCV between CMP and Bcc.
165 0 : if (I->readsRegister(AArch64::NZCV))
166 0 : return nullptr;
167 0 : switch (I->getOpcode()) {
168 : // cmp is an alias for subs with a dead destination register.
169 : case AArch64::SUBSWri:
170 : case AArch64::SUBSXri:
171 : // cmn is an alias for adds with a dead destination register.
172 : case AArch64::ADDSWri:
173 : case AArch64::ADDSXri: {
174 0 : unsigned ShiftAmt = AArch64_AM::getShiftValue(I->getOperand(3).getImm());
175 0 : if (!I->getOperand(2).isImm()) {
176 : LLVM_DEBUG(dbgs() << "Immediate of cmp is symbolic, " << *I << '\n');
177 0 : return nullptr;
178 0 : } else if (I->getOperand(2).getImm() << ShiftAmt >= 0xfff) {
179 : LLVM_DEBUG(dbgs() << "Immediate of cmp may be out of range, " << *I
180 : << '\n');
181 0 : return nullptr;
182 0 : } else if (!MRI->use_empty(I->getOperand(0).getReg())) {
183 : LLVM_DEBUG(dbgs() << "Destination of cmp is not dead, " << *I << '\n');
184 0 : return nullptr;
185 : }
186 0 : return &*I;
187 : }
188 : // Prevent false positive case like:
189 : // cmp w19, #0
190 : // cinc w0, w19, gt
191 : // ...
192 : // fcmp d8, #0.0
193 : // b.gt .LBB0_5
194 : case AArch64::FCMPDri:
195 : case AArch64::FCMPSri:
196 : case AArch64::FCMPESri:
197 : case AArch64::FCMPEDri:
198 :
199 : case AArch64::SUBSWrr:
200 : case AArch64::SUBSXrr:
201 : case AArch64::ADDSWrr:
202 : case AArch64::ADDSXrr:
203 : case AArch64::FCMPSrr:
204 : case AArch64::FCMPDrr:
205 : case AArch64::FCMPESrr:
206 : case AArch64::FCMPEDrr:
207 : // Skip comparison instructions without immediate operands.
208 : return nullptr;
209 : }
210 : }
211 : LLVM_DEBUG(dbgs() << "Flags not defined in " << printMBBReference(*MBB)
212 : << '\n');
213 : return nullptr;
214 : }
215 :
216 : // Changes opcode adds <-> subs considering register operand width.
217 : static int getComplementOpc(int Opc) {
218 0 : switch (Opc) {
219 : case AArch64::ADDSWri: return AArch64::SUBSWri;
220 0 : case AArch64::ADDSXri: return AArch64::SUBSXri;
221 0 : case AArch64::SUBSWri: return AArch64::ADDSWri;
222 0 : case AArch64::SUBSXri: return AArch64::ADDSXri;
223 0 : default:
224 0 : llvm_unreachable("Unexpected opcode");
225 : }
226 : }
227 :
228 : // Changes form of comparison inclusive <-> exclusive.
229 : static AArch64CC::CondCode getAdjustedCmp(AArch64CC::CondCode Cmp) {
230 : switch (Cmp) {
231 : case AArch64CC::GT: return AArch64CC::GE;
232 : case AArch64CC::GE: return AArch64CC::GT;
233 : case AArch64CC::LT: return AArch64CC::LE;
234 : case AArch64CC::LE: return AArch64CC::LT;
235 0 : default:
236 0 : llvm_unreachable("Unexpected condition code");
237 : }
238 : }
239 :
240 : // Transforms GT -> GE, GE -> GT, LT -> LE, LE -> LT by updating comparison
241 : // operator and condition code.
242 0 : AArch64ConditionOptimizer::CmpInfo AArch64ConditionOptimizer::adjustCmp(
243 : MachineInstr *CmpMI, AArch64CC::CondCode Cmp) {
244 0 : unsigned Opc = CmpMI->getOpcode();
245 :
246 : // CMN (compare with negative immediate) is an alias to ADDS (as
247 : // "operand - negative" == "operand + positive")
248 0 : bool Negative = (Opc == AArch64::ADDSWri || Opc == AArch64::ADDSXri);
249 :
250 0 : int Correction = (Cmp == AArch64CC::GT) ? 1 : -1;
251 : // Negate Correction value for comparison with negative immediate (CMN).
252 0 : if (Negative) {
253 0 : Correction = -Correction;
254 : }
255 :
256 0 : const int OldImm = (int)CmpMI->getOperand(2).getImm();
257 0 : const int NewImm = std::abs(OldImm + Correction);
258 :
259 : // Handle +0 -> -1 and -0 -> +1 (CMN with 0 immediate) transitions by
260 : // adjusting compare instruction opcode.
261 0 : if (OldImm == 0 && ((Negative && Correction == 1) ||
262 0 : (!Negative && Correction == -1))) {
263 0 : Opc = getComplementOpc(Opc);
264 : }
265 :
266 0 : return CmpInfo(NewImm, Opc, getAdjustedCmp(Cmp));
267 : }
268 :
269 : // Applies changes to comparison instruction suggested by adjustCmp().
270 0 : void AArch64ConditionOptimizer::modifyCmp(MachineInstr *CmpMI,
271 : const CmpInfo &Info) {
272 : int Imm;
273 : unsigned Opc;
274 : AArch64CC::CondCode Cmp;
275 0 : std::tie(Imm, Opc, Cmp) = Info;
276 :
277 0 : MachineBasicBlock *const MBB = CmpMI->getParent();
278 :
279 : // Change immediate in comparison instruction (ADDS or SUBS).
280 0 : BuildMI(*MBB, CmpMI, CmpMI->getDebugLoc(), TII->get(Opc))
281 0 : .add(CmpMI->getOperand(0))
282 0 : .add(CmpMI->getOperand(1))
283 0 : .addImm(Imm)
284 0 : .add(CmpMI->getOperand(3));
285 0 : CmpMI->eraseFromParent();
286 :
287 : // The fact that this comparison was picked ensures that it's related to the
288 : // first terminator instruction.
289 0 : MachineInstr &BrMI = *MBB->getFirstTerminator();
290 :
291 : // Change condition in branch instruction.
292 0 : BuildMI(*MBB, BrMI, BrMI.getDebugLoc(), TII->get(AArch64::Bcc))
293 0 : .addImm(Cmp)
294 0 : .add(BrMI.getOperand(1));
295 0 : BrMI.eraseFromParent();
296 :
297 0 : MBB->updateTerminator();
298 :
299 : ++NumConditionsAdjusted;
300 0 : }
301 :
302 : // Parse a condition code returned by AnalyzeBranch, and compute the CondCode
303 : // corresponding to TBB.
304 : // Returns true if parsing was successful, otherwise false is returned.
305 0 : static bool parseCond(ArrayRef<MachineOperand> Cond, AArch64CC::CondCode &CC) {
306 : // A normal br.cond simply has the condition code.
307 50 : if (Cond[0].getImm() != -1) {
308 : assert(Cond.size() == 1 && "Unknown Cond array format");
309 50 : CC = (AArch64CC::CondCode)(int)Cond[0].getImm();
310 0 : return true;
311 : }
312 : return false;
313 : }
314 :
315 : // Adjusts one cmp instruction to another one if result of adjustment will allow
316 : // CSE. Returns true if compare instruction was changed, otherwise false is
317 : // returned.
318 3 : bool AArch64ConditionOptimizer::adjustTo(MachineInstr *CmpMI,
319 : AArch64CC::CondCode Cmp, MachineInstr *To, int ToImm)
320 : {
321 3 : CmpInfo Info = adjustCmp(CmpMI, Cmp);
322 3 : if (std::get<0>(Info) == ToImm && std::get<1>(Info) == To->getOpcode()) {
323 2 : modifyCmp(CmpMI, Info);
324 2 : return true;
325 : }
326 : return false;
327 : }
328 :
329 14089 : bool AArch64ConditionOptimizer::runOnMachineFunction(MachineFunction &MF) {
330 : LLVM_DEBUG(dbgs() << "********** AArch64 Conditional Compares **********\n"
331 : << "********** Function: " << MF.getName() << '\n');
332 14089 : if (skipFunction(MF.getFunction()))
333 : return false;
334 :
335 14083 : TII = MF.getSubtarget().getInstrInfo();
336 14083 : DomTree = &getAnalysis<MachineDominatorTree>();
337 14083 : MRI = &MF.getRegInfo();
338 :
339 : bool Changed = false;
340 :
341 : // Visit blocks in dominator tree pre-order. The pre-order enables multiple
342 : // cmp-conversions from the same head block.
343 : // Note that updateDomTree() modifies the children of the DomTree node
344 : // currently being visited. The df_iterator supports that; it doesn't look at
345 : // child_begin() / child_end() until after a node has been visited.
346 44491 : for (MachineDomTreeNode *I : depth_first(DomTree)) {
347 16325 : MachineBasicBlock *HBB = I->getBlock();
348 :
349 : SmallVector<MachineOperand, 4> HeadCond;
350 16325 : MachineBasicBlock *TBB = nullptr, *FBB = nullptr;
351 16325 : if (TII->analyzeBranch(*HBB, TBB, FBB, HeadCond)) {
352 : continue;
353 : }
354 :
355 : // Equivalence check is to skip loops.
356 1957 : if (!TBB || TBB == HBB) {
357 : continue;
358 : }
359 :
360 : SmallVector<MachineOperand, 4> TrueCond;
361 1051 : MachineBasicBlock *TBB_TBB = nullptr, *TBB_FBB = nullptr;
362 1051 : if (TII->analyzeBranch(*TBB, TBB_TBB, TBB_FBB, TrueCond)) {
363 : continue;
364 : }
365 :
366 320 : MachineInstr *HeadCmpMI = findSuitableCompare(HBB);
367 320 : if (!HeadCmpMI) {
368 : continue;
369 : }
370 :
371 80 : MachineInstr *TrueCmpMI = findSuitableCompare(TBB);
372 80 : if (!TrueCmpMI) {
373 : continue;
374 : }
375 :
376 : AArch64CC::CondCode HeadCmp;
377 50 : if (HeadCond.empty() || !parseCond(HeadCond, HeadCmp)) {
378 0 : continue;
379 : }
380 :
381 : AArch64CC::CondCode TrueCmp;
382 50 : if (TrueCond.empty() || !parseCond(TrueCond, TrueCmp)) {
383 0 : continue;
384 : }
385 :
386 25 : const int HeadImm = (int)HeadCmpMI->getOperand(2).getImm();
387 25 : const int TrueImm = (int)TrueCmpMI->getOperand(2).getImm();
388 :
389 : LLVM_DEBUG(dbgs() << "Head branch:\n");
390 : LLVM_DEBUG(dbgs() << "\tcondition: " << AArch64CC::getCondCodeName(HeadCmp)
391 : << '\n');
392 : LLVM_DEBUG(dbgs() << "\timmediate: " << HeadImm << '\n');
393 :
394 : LLVM_DEBUG(dbgs() << "True branch:\n");
395 : LLVM_DEBUG(dbgs() << "\tcondition: " << AArch64CC::getCondCodeName(TrueCmp)
396 : << '\n');
397 : LLVM_DEBUG(dbgs() << "\timmediate: " << TrueImm << '\n');
398 :
399 25 : if (((HeadCmp == AArch64CC::GT && TrueCmp == AArch64CC::LT) ||
400 3 : (HeadCmp == AArch64CC::LT && TrueCmp == AArch64CC::GT)) &&
401 5 : std::abs(TrueImm - HeadImm) == 2) {
402 : // This branch transforms machine instructions that correspond to
403 : //
404 : // 1) (a > {TrueImm} && ...) || (a < {HeadImm} && ...)
405 : // 2) (a < {TrueImm} && ...) || (a > {HeadImm} && ...)
406 : //
407 : // into
408 : //
409 : // 1) (a >= {NewImm} && ...) || (a <= {NewImm} && ...)
410 : // 2) (a <= {NewImm} && ...) || (a >= {NewImm} && ...)
411 :
412 5 : CmpInfo HeadCmpInfo = adjustCmp(HeadCmpMI, HeadCmp);
413 5 : CmpInfo TrueCmpInfo = adjustCmp(TrueCmpMI, TrueCmp);
414 5 : if (std::get<0>(HeadCmpInfo) == std::get<0>(TrueCmpInfo) &&
415 4 : std::get<1>(HeadCmpInfo) == std::get<1>(TrueCmpInfo)) {
416 4 : modifyCmp(HeadCmpMI, HeadCmpInfo);
417 4 : modifyCmp(TrueCmpMI, TrueCmpInfo);
418 : Changed = true;
419 5 : }
420 20 : } else if (((HeadCmp == AArch64CC::GT && TrueCmp == AArch64CC::GT) ||
421 1 : (HeadCmp == AArch64CC::LT && TrueCmp == AArch64CC::LT)) &&
422 3 : std::abs(TrueImm - HeadImm) == 1) {
423 : // This branch transforms machine instructions that correspond to
424 : //
425 : // 1) (a > {TrueImm} && ...) || (a > {HeadImm} && ...)
426 : // 2) (a < {TrueImm} && ...) || (a < {HeadImm} && ...)
427 : //
428 : // into
429 : //
430 : // 1) (a <= {NewImm} && ...) || (a > {NewImm} && ...)
431 : // 2) (a < {NewImm} && ...) || (a >= {NewImm} && ...)
432 :
433 : // GT -> GE transformation increases immediate value, so picking the
434 : // smaller one; LT -> LE decreases immediate value so invert the choice.
435 3 : bool adjustHeadCond = (HeadImm < TrueImm);
436 3 : if (HeadCmp == AArch64CC::LT) {
437 1 : adjustHeadCond = !adjustHeadCond;
438 : }
439 :
440 3 : if (adjustHeadCond) {
441 2 : Changed |= adjustTo(HeadCmpMI, HeadCmp, TrueCmpMI, TrueImm);
442 : } else {
443 1 : Changed |= adjustTo(TrueCmpMI, TrueCmp, HeadCmpMI, HeadImm);
444 : }
445 : }
446 : // Other transformation cases almost never occur due to generation of < or >
447 : // comparisons instead of <= and >=.
448 : }
449 :
450 14083 : return Changed;
451 : }
|
