1//=- AArch64ConditionOptimizer.cpp - Remove useless comparisons for AArch64 -=//
2//
3// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4// See https://llvm.org/LICENSE.txt for license information.
5// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6//
7//===----------------------------------------------------------------------===//
8//
9//
10// This pass tries to make consecutive comparisons of values use the same
11// operands to allow the CSE pass to remove duplicate instructions. It adjusts
12// comparisons with immediate values by converting between inclusive and
13// exclusive forms (GE <-> GT, LE <-> LT) and correcting immediate values to
14// make them equal.
15//
16// The pass handles:
17// * Cross-block: SUBS/ADDS followed by conditional branches
18// * Intra-block: CSINC conditional instructions
19//
20//
21// Consider the following example in C:
22//
23// if ((a < 5 && ...) || (a > 5 && ...)) {
24// ~~~~~ ~~~~~
25// ^ ^
26// x y
27//
28// Here both "x" and "y" expressions compare "a" with "5". When "x" evaluates
29// to "false", "y" can just check flags set by the first comparison. As a
30// result of the canonicalization employed by
31// SelectionDAGBuilder::visitSwitchCase, DAGCombine, and other target-specific
32// code, assembly ends up in the form that is not CSE friendly:
33//
34// ...
35// cmp w8, #4
36// b.gt .LBB0_3
37// ...
38// .LBB0_3:
39// cmp w8, #6
40// b.lt .LBB0_6
41// ...
42//
43// Same assembly after the pass:
44//
45// ...
46// cmp w8, #5
47// b.ge .LBB0_3
48// ...
49// .LBB0_3:
50// cmp w8, #5 // <-- CSE pass removes this instruction
51// b.le .LBB0_6
52// ...
53//
54// See optimizeCrossBlock() and optimizeIntraBlock() for implementation details.
55//
56// TODO: maybe handle TBNZ/TBZ the same way as CMP when used instead for "a < 0"
57// TODO: For cross-block:
58// - handle other conditional instructions (e.g. CSET)
59// - allow second branching to be anything if it doesn't require adjusting
60// TODO: For intra-block:
61// - handle CINC and CSET (CSINC aliases) as their conditions are inverted
62// compared to CSINC.
63// - handle other non-CSINC conditional instructions
64//
65//===----------------------------------------------------------------------===//
66
67#include "AArch64.h"
68#include "MCTargetDesc/AArch64AddressingModes.h"
69#include "Utils/AArch64BaseInfo.h"
70#include "llvm/ADT/ArrayRef.h"
71#include "llvm/ADT/DepthFirstIterator.h"
72#include "llvm/ADT/SmallVector.h"
73#include "llvm/ADT/Statistic.h"
74#include "llvm/CodeGen/MachineBasicBlock.h"
75#include "llvm/CodeGen/MachineDominators.h"
76#include "llvm/CodeGen/MachineFunction.h"
77#include "llvm/CodeGen/MachineFunctionPass.h"
78#include "llvm/CodeGen/MachineInstr.h"
79#include "llvm/CodeGen/MachineInstrBuilder.h"
80#include "llvm/CodeGen/MachineOperand.h"
81#include "llvm/CodeGen/MachineRegisterInfo.h"
82#include "llvm/CodeGen/TargetInstrInfo.h"
83#include "llvm/CodeGen/TargetRegisterInfo.h"
84#include "llvm/CodeGen/TargetSubtargetInfo.h"
85#include "llvm/InitializePasses.h"
86#include "llvm/Pass.h"
87#include "llvm/Support/Debug.h"
88#include "llvm/Support/ErrorHandling.h"
89#include "llvm/Support/raw_ostream.h"
90#include <cassert>
91#include <cstdlib>
92#include <tuple>
93
94using namespace llvm;
95
96#define DEBUG_TYPE "aarch64-condopt"
97
98STATISTIC(NumConditionsAdjusted, "Number of conditions adjusted");
99
100namespace {
101
102class AArch64ConditionOptimizer : public MachineFunctionPass {
103 const TargetInstrInfo *TII;
104 const TargetRegisterInfo *TRI;
105 MachineDominatorTree *DomTree;
106 const MachineRegisterInfo *MRI;
107
108public:
109 // Stores immediate, compare instruction opcode and branch condition (in this
110 // order) of adjusted comparison.
111 using CmpInfo = std::tuple<int, unsigned, AArch64CC::CondCode>;
112
113 static char ID;
114
115 AArch64ConditionOptimizer() : MachineFunctionPass(ID) {}
116
117 void getAnalysisUsage(AnalysisUsage &AU) const override;
118 bool canAdjustCmp(MachineInstr &CmpMI);
119 bool registersMatch(MachineInstr *FirstMI, MachineInstr *SecondMI);
120 bool nzcvLivesOut(MachineBasicBlock *MBB);
121 MachineInstr *findSuitableCompare(MachineBasicBlock *MBB);
122 CmpInfo adjustCmp(MachineInstr *CmpMI, AArch64CC::CondCode Cmp);
123 void modifyCmp(MachineInstr *CmpMI, const CmpInfo &Info);
124 bool adjustTo(MachineInstr *CmpMI, AArch64CC::CondCode Cmp, MachineInstr *To,
125 int ToImm);
126 bool isPureCmp(MachineInstr &CmpMI);
127 bool optimizeIntraBlock(MachineBasicBlock &MBB);
128 bool optimizeCrossBlock(MachineBasicBlock &HBB);
129 bool runOnMachineFunction(MachineFunction &MF) override;
130
131 StringRef getPassName() const override {
132 return "AArch64 Condition Optimizer";
133 }
134};
135
136} // end anonymous namespace
137
138char AArch64ConditionOptimizer::ID = 0;
139
140INITIALIZE_PASS_BEGIN(AArch64ConditionOptimizer, "aarch64-condopt",
141 "AArch64 CondOpt Pass", false, false)
142INITIALIZE_PASS_DEPENDENCY(MachineDominatorTreeWrapperPass)
143INITIALIZE_PASS_END(AArch64ConditionOptimizer, "aarch64-condopt",
144 "AArch64 CondOpt Pass", false, false)
145
146FunctionPass *llvm::createAArch64ConditionOptimizerPass() {
147 return new AArch64ConditionOptimizer();
148}
149
150void AArch64ConditionOptimizer::getAnalysisUsage(AnalysisUsage &AU) const {
151 AU.addRequired<MachineDominatorTreeWrapperPass>();
152 AU.addPreserved<MachineDominatorTreeWrapperPass>();
153 MachineFunctionPass::getAnalysisUsage(AU);
154}
155
156// Verify that the MI's immediate is adjustable and it only sets flags (pure
157// cmp)
158bool AArch64ConditionOptimizer::canAdjustCmp(MachineInstr &CmpMI) {
159 unsigned ShiftAmt = AArch64_AM::getShiftValue(Imm: CmpMI.getOperand(i: 3).getImm());
160 if (!CmpMI.getOperand(i: 2).isImm()) {
161 LLVM_DEBUG(dbgs() << "Immediate of cmp is symbolic, " << CmpMI << '\n');
162 return false;
163 } else if (CmpMI.getOperand(i: 2).getImm() << ShiftAmt >= 0xfff) {
164 LLVM_DEBUG(dbgs() << "Immediate of cmp may be out of range, " << CmpMI
165 << '\n');
166 return false;
167 } else if (!MRI->use_nodbg_empty(RegNo: CmpMI.getOperand(i: 0).getReg())) {
168 LLVM_DEBUG(dbgs() << "Destination of cmp is not dead, " << CmpMI << '\n');
169 return false;
170 }
171
172 return true;
173}
174
175// Ensure both compare MIs use the same register, tracing through copies.
176bool AArch64ConditionOptimizer::registersMatch(MachineInstr *FirstMI,
177 MachineInstr *SecondMI) {
178 Register FirstReg = FirstMI->getOperand(i: 1).getReg();
179 Register SecondReg = SecondMI->getOperand(i: 1).getReg();
180 Register FirstCmpReg =
181 FirstReg.isVirtual() ? TRI->lookThruCopyLike(SrcReg: FirstReg, MRI) : FirstReg;
182 Register SecondCmpReg =
183 SecondReg.isVirtual() ? TRI->lookThruCopyLike(SrcReg: SecondReg, MRI) : SecondReg;
184 if (FirstCmpReg != SecondCmpReg) {
185 LLVM_DEBUG(dbgs() << "CMPs compare different registers\n");
186 return false;
187 }
188
189 return true;
190}
191
192// Check if NZCV lives out to any successor block.
193bool AArch64ConditionOptimizer::nzcvLivesOut(MachineBasicBlock *MBB) {
194 for (auto *SuccBB : MBB->successors()) {
195 if (SuccBB->isLiveIn(Reg: AArch64::NZCV)) {
196 LLVM_DEBUG(dbgs() << "NZCV live into successor "
197 << printMBBReference(*SuccBB) << " from "
198 << printMBBReference(*MBB) << '\n');
199 return true;
200 }
201 }
202 return false;
203}
204
205// Returns true if the opcode is a comparison instruction (CMP/CMN).
206static bool isCmpInstruction(unsigned Opc) {
207 switch (Opc) {
208 // cmp is an alias for SUBS with a dead destination register.
209 case AArch64::SUBSWri:
210 case AArch64::SUBSXri:
211 // cmp is an alias for ADDS with a dead destination register.
212 case AArch64::ADDSWri:
213 case AArch64::ADDSXri:
214 return true;
215 default:
216 return false;
217 }
218}
219
220static bool isCSINCInstruction(unsigned Opc) {
221 return Opc == AArch64::CSINCWr || Opc == AArch64::CSINCXr;
222}
223
224// Finds compare instruction that corresponds to supported types of branching.
225// Returns the instruction or nullptr on failures or detecting unsupported
226// instructions.
227MachineInstr *AArch64ConditionOptimizer::findSuitableCompare(
228 MachineBasicBlock *MBB) {
229 MachineBasicBlock::iterator Term = MBB->getFirstTerminator();
230 if (Term == MBB->end())
231 return nullptr;
232
233 if (Term->getOpcode() != AArch64::Bcc)
234 return nullptr;
235
236 // Since we may modify cmp of this MBB, make sure NZCV does not live out.
237 if (nzcvLivesOut(MBB))
238 return nullptr;
239
240 // Now find the instruction controlling the terminator.
241 for (MachineBasicBlock::iterator B = MBB->begin(), It = Term; It != B;) {
242 It = prev_nodbg(It, Begin: B);
243 MachineInstr &I = *It;
244 assert(!I.isTerminator() && "Spurious terminator");
245 // Check if there is any use of NZCV between CMP and Bcc.
246 if (I.readsRegister(Reg: AArch64::NZCV, /*TRI=*/nullptr))
247 return nullptr;
248
249 if (isCmpInstruction(Opc: I.getOpcode())) {
250 if (!canAdjustCmp(CmpMI&: I)) {
251 return nullptr;
252 }
253 return &I;
254 }
255
256 if (I.modifiesRegister(Reg: AArch64::NZCV, /*TRI=*/nullptr))
257 return nullptr;
258 }
259 LLVM_DEBUG(dbgs() << "Flags not defined in " << printMBBReference(*MBB)
260 << '\n');
261 return nullptr;
262}
263
264// Changes opcode adds <-> subs considering register operand width.
265static int getComplementOpc(int Opc) {
266 switch (Opc) {
267 case AArch64::ADDSWri: return AArch64::SUBSWri;
268 case AArch64::ADDSXri: return AArch64::SUBSXri;
269 case AArch64::SUBSWri: return AArch64::ADDSWri;
270 case AArch64::SUBSXri: return AArch64::ADDSXri;
271 default:
272 llvm_unreachable("Unexpected opcode");
273 }
274}
275
276// Changes form of comparison inclusive <-> exclusive.
277static AArch64CC::CondCode getAdjustedCmp(AArch64CC::CondCode Cmp) {
278 switch (Cmp) {
279 case AArch64CC::GT: return AArch64CC::GE;
280 case AArch64CC::GE: return AArch64CC::GT;
281 case AArch64CC::LT: return AArch64CC::LE;
282 case AArch64CC::LE: return AArch64CC::LT;
283 default:
284 llvm_unreachable("Unexpected condition code");
285 }
286}
287
288// Transforms GT -> GE, GE -> GT, LT -> LE, LE -> LT by updating comparison
289// operator and condition code.
290AArch64ConditionOptimizer::CmpInfo AArch64ConditionOptimizer::adjustCmp(
291 MachineInstr *CmpMI, AArch64CC::CondCode Cmp) {
292 unsigned Opc = CmpMI->getOpcode();
293
294 // CMN (compare with negative immediate) is an alias to ADDS (as
295 // "operand - negative" == "operand + positive")
296 bool Negative = (Opc == AArch64::ADDSWri || Opc == AArch64::ADDSXri);
297
298 int Correction = (Cmp == AArch64CC::GT) ? 1 : -1;
299 // Negate Correction value for comparison with negative immediate (CMN).
300 if (Negative) {
301 Correction = -Correction;
302 }
303
304 const int OldImm = (int)CmpMI->getOperand(i: 2).getImm();
305 const int NewImm = std::abs(x: OldImm + Correction);
306
307 // Handle +0 -> -1 and -0 -> +1 (CMN with 0 immediate) transitions by
308 // adjusting compare instruction opcode.
309 if (OldImm == 0 && ((Negative && Correction == 1) ||
310 (!Negative && Correction == -1))) {
311 Opc = getComplementOpc(Opc);
312 }
313
314 return CmpInfo(NewImm, Opc, getAdjustedCmp(Cmp));
315}
316
317// Applies changes to comparison instruction suggested by adjustCmp().
318void AArch64ConditionOptimizer::modifyCmp(MachineInstr *CmpMI,
319 const CmpInfo &Info) {
320 int Imm;
321 unsigned Opc;
322 AArch64CC::CondCode Cmp;
323 std::tie(args&: Imm, args&: Opc, args&: Cmp) = Info;
324
325 MachineBasicBlock *const MBB = CmpMI->getParent();
326
327 // Change immediate in comparison instruction (ADDS or SUBS).
328 BuildMI(BB&: *MBB, I: CmpMI, MIMD: CmpMI->getDebugLoc(), MCID: TII->get(Opcode: Opc))
329 .add(MO: CmpMI->getOperand(i: 0))
330 .add(MO: CmpMI->getOperand(i: 1))
331 .addImm(Val: Imm)
332 .add(MO: CmpMI->getOperand(i: 3));
333 CmpMI->eraseFromParent();
334
335 // The fact that this comparison was picked ensures that it's related to the
336 // first terminator instruction.
337 MachineInstr &BrMI = *MBB->getFirstTerminator();
338
339 // Change condition in branch instruction.
340 BuildMI(BB&: *MBB, I&: BrMI, MIMD: BrMI.getDebugLoc(), MCID: TII->get(Opcode: AArch64::Bcc))
341 .addImm(Val: Cmp)
342 .add(MO: BrMI.getOperand(i: 1));
343 BrMI.eraseFromParent();
344
345 ++NumConditionsAdjusted;
346}
347
348// Parse a condition code returned by analyzeBranch, and compute the CondCode
349// corresponding to TBB.
350// Returns true if parsing was successful, otherwise false is returned.
351static bool parseCond(ArrayRef<MachineOperand> Cond, AArch64CC::CondCode &CC) {
352 // A normal br.cond simply has the condition code.
353 if (Cond[0].getImm() != -1) {
354 assert(Cond.size() == 1 && "Unknown Cond array format");
355 CC = (AArch64CC::CondCode)(int)Cond[0].getImm();
356 return true;
357 }
358 return false;
359}
360
361// Adjusts one cmp instruction to another one if result of adjustment will allow
362// CSE. Returns true if compare instruction was changed, otherwise false is
363// returned.
364bool AArch64ConditionOptimizer::adjustTo(MachineInstr *CmpMI,
365 AArch64CC::CondCode Cmp, MachineInstr *To, int ToImm)
366{
367 CmpInfo Info = adjustCmp(CmpMI, Cmp);
368 if (std::get<0>(t&: Info) == ToImm && std::get<1>(t&: Info) == To->getOpcode()) {
369 modifyCmp(CmpMI, Info);
370 return true;
371 }
372 return false;
373}
374
375bool AArch64ConditionOptimizer::isPureCmp(MachineInstr &CmpMI) {
376 unsigned ShiftAmt = AArch64_AM::getShiftValue(Imm: CmpMI.getOperand(i: 3).getImm());
377 if (!CmpMI.getOperand(i: 2).isImm()) {
378 LLVM_DEBUG(dbgs() << "Immediate of cmp is symbolic, " << CmpMI << '\n');
379 return false;
380 } else if (CmpMI.getOperand(i: 2).getImm() << ShiftAmt >= 0xfff) {
381 LLVM_DEBUG(dbgs() << "Immediate of cmp may be out of range, " << CmpMI
382 << '\n');
383 return false;
384 } else if (!MRI->use_nodbg_empty(RegNo: CmpMI.getOperand(i: 0).getReg())) {
385 LLVM_DEBUG(dbgs() << "Destination of cmp is not dead, " << CmpMI << '\n');
386 return false;
387 }
388
389 return true;
390}
391
392// This function transforms two CMP+CSINC pairs within the same basic block
393// when both conditions are the same (GT/GT or LT/LT) and immediates differ
394// by 1.
395//
396// Example transformation:
397// cmp w8, #10
398// csinc w9, w0, w1, gt ; w9 = (w8 > 10) ? w0 : w1+1
399// cmp w8, #9
400// csinc w10, w0, w1, gt ; w10 = (w8 > 9) ? w0 : w1+1
401//
402// Into:
403// cmp w8, #10
404// csinc w9, w0, w1, gt ; w9 = (w8 > 10) ? w0 : w1+1
405// csinc w10, w0, w1, ge ; w10 = (w8 >= 10) ? w0 : w1+1
406//
407// The second CMP is eliminated, enabling CSE to remove the redundant
408// comparison.
409bool AArch64ConditionOptimizer::optimizeIntraBlock(MachineBasicBlock &MBB) {
410 MachineInstr *FirstCmp = nullptr;
411 MachineInstr *FirstCSINC = nullptr;
412 MachineInstr *SecondCmp = nullptr;
413 MachineInstr *SecondCSINC = nullptr;
414
415 // Find two CMP + CSINC pairs
416 for (MachineInstr &MI : MBB) {
417 if (isCmpInstruction(Opc: MI.getOpcode())) {
418 if (!FirstCmp) {
419 FirstCmp = &MI;
420 } else if (FirstCSINC && !SecondCmp) {
421 SecondCmp = &MI;
422 }
423 continue;
424 }
425
426 if (isCSINCInstruction(Opc: MI.getOpcode())) {
427 // Found a CSINC, ensure it comes after the corresponding comparison
428 if (FirstCmp && !FirstCSINC) {
429 FirstCSINC = &MI;
430 } else if (SecondCmp && !SecondCSINC) {
431 SecondCSINC = &MI;
432 }
433 }
434
435 if (SecondCSINC)
436 break;
437 }
438
439 if (!SecondCmp || !SecondCSINC) {
440 LLVM_DEBUG(dbgs() << "Didn't find two CMP+CSINC pairs\n");
441 return false;
442 }
443
444 // Since we may modify cmps in this MBB, make sure NZCV does not live out.
445 if (nzcvLivesOut(MBB: &MBB))
446 return false;
447
448 if (!registersMatch(FirstMI: FirstCmp, SecondMI: SecondCmp))
449 return false;
450
451 if (!isPureCmp(CmpMI&: *FirstCmp) || !isPureCmp(CmpMI&: *SecondCmp)) {
452 LLVM_DEBUG(dbgs() << "One or both CMPs are not pure\n");
453 return false;
454 }
455
456 // Check that nothing else modifies the flags between the first CMP and second
457 // conditional
458 for (auto It = std::next(x: MachineBasicBlock::iterator(FirstCmp));
459 It != std::next(x: MachineBasicBlock::iterator(SecondCSINC)); ++It) {
460 if (&*It != SecondCmp &&
461 It->modifiesRegister(Reg: AArch64::NZCV, /*TRI=*/nullptr)) {
462 LLVM_DEBUG(dbgs() << "Flags modified between CMPs by: " << *It << '\n');
463 return false;
464 }
465 }
466
467 // Check flags aren't read after second conditional within the same block
468 for (auto It = std::next(x: MachineBasicBlock::iterator(SecondCSINC));
469 It != MBB.end(); ++It) {
470 if (It->readsRegister(Reg: AArch64::NZCV, /*TRI=*/nullptr)) {
471 LLVM_DEBUG(dbgs() << "Flags read after second CSINC by: " << *It << '\n');
472 return false;
473 }
474 }
475
476 // Extract condition codes from both CSINCs (operand 3)
477 AArch64CC::CondCode FirstCond =
478 (AArch64CC::CondCode)(int)FirstCSINC->getOperand(i: 3).getImm();
479 AArch64CC::CondCode SecondCond =
480 (AArch64CC::CondCode)(int)SecondCSINC->getOperand(i: 3).getImm();
481
482 const int FirstImm = (int)FirstCmp->getOperand(i: 2).getImm();
483 const int SecondImm = (int)SecondCmp->getOperand(i: 2).getImm();
484
485 LLVM_DEBUG(dbgs() << "Comparing intra-block CSINCs: "
486 << AArch64CC::getCondCodeName(FirstCond) << " #" << FirstImm
487 << " and " << AArch64CC::getCondCodeName(SecondCond) << " #"
488 << SecondImm << '\n');
489
490 // Check if both conditions are the same and immediates differ by 1
491 if (((FirstCond == AArch64CC::GT && SecondCond == AArch64CC::GT) ||
492 (FirstCond == AArch64CC::LT && SecondCond == AArch64CC::LT)) &&
493 std::abs(x: SecondImm - FirstImm) == 1) {
494 // Pick which comparison to adjust to match the other
495 // For GT: adjust the one with smaller immediate
496 // For LT: adjust the one with larger immediate
497 bool adjustFirst = (FirstImm < SecondImm);
498 if (FirstCond == AArch64CC::LT) {
499 adjustFirst = !adjustFirst;
500 }
501
502 MachineInstr *CmpToAdjust = adjustFirst ? FirstCmp : SecondCmp;
503 MachineInstr *CSINCToAdjust = adjustFirst ? FirstCSINC : SecondCSINC;
504 AArch64CC::CondCode CondToAdjust = adjustFirst ? FirstCond : SecondCond;
505 int TargetImm = adjustFirst ? SecondImm : FirstImm;
506
507 CmpInfo AdjustedInfo = adjustCmp(CmpMI: CmpToAdjust, Cmp: CondToAdjust);
508
509 if (std::get<0>(t&: AdjustedInfo) == TargetImm &&
510 std::get<1>(t&: AdjustedInfo) ==
511 (adjustFirst ? SecondCmp : FirstCmp)->getOpcode()) {
512 LLVM_DEBUG(dbgs() << "Successfully optimizing intra-block CSINC pair\n");
513
514 // Modify the selected CMP and CSINC
515 CmpToAdjust->getOperand(i: 2).setImm(std::get<0>(t&: AdjustedInfo));
516 CmpToAdjust->setDesc(TII->get(Opcode: std::get<1>(t&: AdjustedInfo)));
517 CSINCToAdjust->getOperand(i: 3).setImm(std::get<2>(t&: AdjustedInfo));
518
519 return true;
520 }
521 }
522
523 return false;
524}
525
526// Optimize across blocks
527bool AArch64ConditionOptimizer::optimizeCrossBlock(MachineBasicBlock &HBB) {
528 SmallVector<MachineOperand, 4> HeadCond;
529 MachineBasicBlock *TBB = nullptr, *FBB = nullptr;
530 if (TII->analyzeBranch(MBB&: HBB, TBB, FBB, Cond&: HeadCond)) {
531 return false;
532 }
533
534 // Equivalence check is to skip loops.
535 if (!TBB || TBB == &HBB) {
536 return false;
537 }
538
539 SmallVector<MachineOperand, 4> TrueCond;
540 MachineBasicBlock *TBB_TBB = nullptr, *TBB_FBB = nullptr;
541 if (TII->analyzeBranch(MBB&: *TBB, TBB&: TBB_TBB, FBB&: TBB_FBB, Cond&: TrueCond)) {
542 return false;
543 }
544
545 MachineInstr *HeadCmpMI = findSuitableCompare(MBB: &HBB);
546 if (!HeadCmpMI) {
547 return false;
548 }
549
550 MachineInstr *TrueCmpMI = findSuitableCompare(MBB: TBB);
551 if (!TrueCmpMI) {
552 return false;
553 }
554
555 if (!registersMatch(FirstMI: HeadCmpMI, SecondMI: TrueCmpMI)) {
556 return false;
557 }
558
559 AArch64CC::CondCode HeadCmp;
560 if (HeadCond.empty() || !parseCond(Cond: HeadCond, CC&: HeadCmp)) {
561 return false;
562 }
563
564 AArch64CC::CondCode TrueCmp;
565 if (TrueCond.empty() || !parseCond(Cond: TrueCond, CC&: TrueCmp)) {
566 return false;
567 }
568
569 const int HeadImm = (int)HeadCmpMI->getOperand(i: 2).getImm();
570 const int TrueImm = (int)TrueCmpMI->getOperand(i: 2).getImm();
571
572 LLVM_DEBUG(dbgs() << "Head branch:\n");
573 LLVM_DEBUG(dbgs() << "\tcondition: " << AArch64CC::getCondCodeName(HeadCmp)
574 << '\n');
575 LLVM_DEBUG(dbgs() << "\timmediate: " << HeadImm << '\n');
576
577 LLVM_DEBUG(dbgs() << "True branch:\n");
578 LLVM_DEBUG(dbgs() << "\tcondition: " << AArch64CC::getCondCodeName(TrueCmp)
579 << '\n');
580 LLVM_DEBUG(dbgs() << "\timmediate: " << TrueImm << '\n');
581
582 if (((HeadCmp == AArch64CC::GT && TrueCmp == AArch64CC::LT) ||
583 (HeadCmp == AArch64CC::LT && TrueCmp == AArch64CC::GT)) &&
584 std::abs(x: TrueImm - HeadImm) == 2) {
585 // This branch transforms machine instructions that correspond to
586 //
587 // 1) (a > {TrueImm} && ...) || (a < {HeadImm} && ...)
588 // 2) (a < {TrueImm} && ...) || (a > {HeadImm} && ...)
589 //
590 // into
591 //
592 // 1) (a >= {NewImm} && ...) || (a <= {NewImm} && ...)
593 // 2) (a <= {NewImm} && ...) || (a >= {NewImm} && ...)
594
595 CmpInfo HeadCmpInfo = adjustCmp(CmpMI: HeadCmpMI, Cmp: HeadCmp);
596 CmpInfo TrueCmpInfo = adjustCmp(CmpMI: TrueCmpMI, Cmp: TrueCmp);
597 if (std::get<0>(t&: HeadCmpInfo) == std::get<0>(t&: TrueCmpInfo) &&
598 std::get<1>(t&: HeadCmpInfo) == std::get<1>(t&: TrueCmpInfo)) {
599 modifyCmp(CmpMI: HeadCmpMI, Info: HeadCmpInfo);
600 modifyCmp(CmpMI: TrueCmpMI, Info: TrueCmpInfo);
601 return true;
602 }
603 } else if (((HeadCmp == AArch64CC::GT && TrueCmp == AArch64CC::GT) ||
604 (HeadCmp == AArch64CC::LT && TrueCmp == AArch64CC::LT)) &&
605 std::abs(x: TrueImm - HeadImm) == 1) {
606 // This branch transforms machine instructions that correspond to
607 //
608 // 1) (a > {TrueImm} && ...) || (a > {HeadImm} && ...)
609 // 2) (a < {TrueImm} && ...) || (a < {HeadImm} && ...)
610 //
611 // into
612 //
613 // 1) (a <= {NewImm} && ...) || (a > {NewImm} && ...)
614 // 2) (a < {NewImm} && ...) || (a >= {NewImm} && ...)
615
616 // GT -> GE transformation increases immediate value, so picking the
617 // smaller one; LT -> LE decreases immediate value so invert the choice.
618 bool adjustHeadCond = (HeadImm < TrueImm);
619 if (HeadCmp == AArch64CC::LT) {
620 adjustHeadCond = !adjustHeadCond;
621 }
622
623 if (adjustHeadCond) {
624 return adjustTo(CmpMI: HeadCmpMI, Cmp: HeadCmp, To: TrueCmpMI, ToImm: TrueImm);
625 } else {
626 return adjustTo(CmpMI: TrueCmpMI, Cmp: TrueCmp, To: HeadCmpMI, ToImm: HeadImm);
627 }
628 }
629 // Other transformation cases almost never occur due to generation of < or >
630 // comparisons instead of <= and >=.
631
632 return false;
633}
634
635bool AArch64ConditionOptimizer::runOnMachineFunction(MachineFunction &MF) {
636 LLVM_DEBUG(dbgs() << "********** AArch64 Conditional Compares **********\n"
637 << "********** Function: " << MF.getName() << '\n');
638 if (skipFunction(F: MF.getFunction()))
639 return false;
640
641 TII = MF.getSubtarget().getInstrInfo();
642 TRI = MF.getSubtarget().getRegisterInfo();
643 DomTree = &getAnalysis<MachineDominatorTreeWrapperPass>().getDomTree();
644 MRI = &MF.getRegInfo();
645
646 bool Changed = false;
647
648 // Visit blocks in dominator tree pre-order. The pre-order enables multiple
649 // cmp-conversions from the same head block.
650 // Note that updateDomTree() modifies the children of the DomTree node
651 // currently being visited. The df_iterator supports that; it doesn't look at
652 // child_begin() / child_end() until after a node has been visited.
653 for (MachineDomTreeNode *I : depth_first(G: DomTree)) {
654 MachineBasicBlock *HBB = I->getBlock();
655 Changed |= optimizeIntraBlock(MBB&: *HBB);
656 Changed |= optimizeCrossBlock(HBB&: *HBB);
657 }
658
659 return Changed;
660}
661