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 MachineInstr *findSuitableCompare(MachineBasicBlock *MBB);
119 CmpInfo adjustCmp(MachineInstr *CmpMI, AArch64CC::CondCode Cmp);
120 void modifyCmp(MachineInstr *CmpMI, const CmpInfo &Info);
121 bool adjustTo(MachineInstr *CmpMI, AArch64CC::CondCode Cmp, MachineInstr *To,
122 int ToImm);
123 bool isPureCmp(MachineInstr &CmpMI);
124 bool optimizeIntraBlock(MachineBasicBlock &MBB);
125 bool optimizeCrossBlock(MachineBasicBlock &HBB);
126 bool runOnMachineFunction(MachineFunction &MF) override;
127
128 StringRef getPassName() const override {
129 return "AArch64 Condition Optimizer";
130 }
131};
132
133} // end anonymous namespace
134
135char AArch64ConditionOptimizer::ID = 0;
136
137INITIALIZE_PASS_BEGIN(AArch64ConditionOptimizer, "aarch64-condopt",
138 "AArch64 CondOpt Pass", false, false)
139INITIALIZE_PASS_DEPENDENCY(MachineDominatorTreeWrapperPass)
140INITIALIZE_PASS_END(AArch64ConditionOptimizer, "aarch64-condopt",
141 "AArch64 CondOpt Pass", false, false)
142
143FunctionPass *llvm::createAArch64ConditionOptimizerPass() {
144 return new AArch64ConditionOptimizer();
145}
146
147void AArch64ConditionOptimizer::getAnalysisUsage(AnalysisUsage &AU) const {
148 AU.addRequired<MachineDominatorTreeWrapperPass>();
149 AU.addPreserved<MachineDominatorTreeWrapperPass>();
150 MachineFunctionPass::getAnalysisUsage(AU);
151}
152
153// Finds compare instruction that corresponds to supported types of branching.
154// Returns the instruction or nullptr on failures or detecting unsupported
155// instructions.
156MachineInstr *AArch64ConditionOptimizer::findSuitableCompare(
157 MachineBasicBlock *MBB) {
158 MachineBasicBlock::iterator Term = MBB->getFirstTerminator();
159 if (Term == MBB->end())
160 return nullptr;
161
162 if (Term->getOpcode() != AArch64::Bcc)
163 return nullptr;
164
165 // Since we may modify cmp of this MBB, make sure NZCV does not live out.
166 for (auto *SuccBB : MBB->successors())
167 if (SuccBB->isLiveIn(Reg: AArch64::NZCV))
168 return nullptr;
169
170 // Now find the instruction controlling the terminator.
171 for (MachineBasicBlock::iterator B = MBB->begin(), It = Term; It != B;) {
172 It = prev_nodbg(It, Begin: B);
173 MachineInstr &I = *It;
174 assert(!I.isTerminator() && "Spurious terminator");
175 // Check if there is any use of NZCV between CMP and Bcc.
176 if (I.readsRegister(Reg: AArch64::NZCV, /*TRI=*/nullptr))
177 return nullptr;
178 switch (I.getOpcode()) {
179 // cmp is an alias for subs with a dead destination register.
180 case AArch64::SUBSWri:
181 case AArch64::SUBSXri:
182 // cmn is an alias for adds with a dead destination register.
183 case AArch64::ADDSWri:
184 case AArch64::ADDSXri: {
185 unsigned ShiftAmt = AArch64_AM::getShiftValue(Imm: I.getOperand(i: 3).getImm());
186 if (!I.getOperand(i: 2).isImm()) {
187 LLVM_DEBUG(dbgs() << "Immediate of cmp is symbolic, " << I << '\n');
188 return nullptr;
189 } else if (I.getOperand(i: 2).getImm() << ShiftAmt >= 0xfff) {
190 LLVM_DEBUG(dbgs() << "Immediate of cmp may be out of range, " << I
191 << '\n');
192 return nullptr;
193 } else if (!MRI->use_nodbg_empty(RegNo: I.getOperand(i: 0).getReg())) {
194 LLVM_DEBUG(dbgs() << "Destination of cmp is not dead, " << I << '\n');
195 return nullptr;
196 }
197 return &I;
198 }
199 }
200 if (I.modifiesRegister(Reg: AArch64::NZCV, /*TRI=*/nullptr))
201 return nullptr;
202 }
203 LLVM_DEBUG(dbgs() << "Flags not defined in " << printMBBReference(*MBB)
204 << '\n');
205 return nullptr;
206}
207
208// Changes opcode adds <-> subs considering register operand width.
209static int getComplementOpc(int Opc) {
210 switch (Opc) {
211 case AArch64::ADDSWri: return AArch64::SUBSWri;
212 case AArch64::ADDSXri: return AArch64::SUBSXri;
213 case AArch64::SUBSWri: return AArch64::ADDSWri;
214 case AArch64::SUBSXri: return AArch64::ADDSXri;
215 default:
216 llvm_unreachable("Unexpected opcode");
217 }
218}
219
220// Changes form of comparison inclusive <-> exclusive.
221static AArch64CC::CondCode getAdjustedCmp(AArch64CC::CondCode Cmp) {
222 switch (Cmp) {
223 case AArch64CC::GT: return AArch64CC::GE;
224 case AArch64CC::GE: return AArch64CC::GT;
225 case AArch64CC::LT: return AArch64CC::LE;
226 case AArch64CC::LE: return AArch64CC::LT;
227 default:
228 llvm_unreachable("Unexpected condition code");
229 }
230}
231
232// Transforms GT -> GE, GE -> GT, LT -> LE, LE -> LT by updating comparison
233// operator and condition code.
234AArch64ConditionOptimizer::CmpInfo AArch64ConditionOptimizer::adjustCmp(
235 MachineInstr *CmpMI, AArch64CC::CondCode Cmp) {
236 unsigned Opc = CmpMI->getOpcode();
237
238 // CMN (compare with negative immediate) is an alias to ADDS (as
239 // "operand - negative" == "operand + positive")
240 bool Negative = (Opc == AArch64::ADDSWri || Opc == AArch64::ADDSXri);
241
242 int Correction = (Cmp == AArch64CC::GT) ? 1 : -1;
243 // Negate Correction value for comparison with negative immediate (CMN).
244 if (Negative) {
245 Correction = -Correction;
246 }
247
248 const int OldImm = (int)CmpMI->getOperand(i: 2).getImm();
249 const int NewImm = std::abs(x: OldImm + Correction);
250
251 // Handle +0 -> -1 and -0 -> +1 (CMN with 0 immediate) transitions by
252 // adjusting compare instruction opcode.
253 if (OldImm == 0 && ((Negative && Correction == 1) ||
254 (!Negative && Correction == -1))) {
255 Opc = getComplementOpc(Opc);
256 }
257
258 return CmpInfo(NewImm, Opc, getAdjustedCmp(Cmp));
259}
260
261// Applies changes to comparison instruction suggested by adjustCmp().
262void AArch64ConditionOptimizer::modifyCmp(MachineInstr *CmpMI,
263 const CmpInfo &Info) {
264 int Imm;
265 unsigned Opc;
266 AArch64CC::CondCode Cmp;
267 std::tie(args&: Imm, args&: Opc, args&: Cmp) = Info;
268
269 MachineBasicBlock *const MBB = CmpMI->getParent();
270
271 // Change immediate in comparison instruction (ADDS or SUBS).
272 BuildMI(BB&: *MBB, I: CmpMI, MIMD: CmpMI->getDebugLoc(), MCID: TII->get(Opcode: Opc))
273 .add(MO: CmpMI->getOperand(i: 0))
274 .add(MO: CmpMI->getOperand(i: 1))
275 .addImm(Val: Imm)
276 .add(MO: CmpMI->getOperand(i: 3));
277 CmpMI->eraseFromParent();
278
279 // The fact that this comparison was picked ensures that it's related to the
280 // first terminator instruction.
281 MachineInstr &BrMI = *MBB->getFirstTerminator();
282
283 // Change condition in branch instruction.
284 BuildMI(BB&: *MBB, I&: BrMI, MIMD: BrMI.getDebugLoc(), MCID: TII->get(Opcode: AArch64::Bcc))
285 .addImm(Val: Cmp)
286 .add(MO: BrMI.getOperand(i: 1));
287 BrMI.eraseFromParent();
288
289 ++NumConditionsAdjusted;
290}
291
292// Parse a condition code returned by analyzeBranch, and compute the CondCode
293// corresponding to TBB.
294// Returns true if parsing was successful, otherwise false is returned.
295static bool parseCond(ArrayRef<MachineOperand> Cond, AArch64CC::CondCode &CC) {
296 // A normal br.cond simply has the condition code.
297 if (Cond[0].getImm() != -1) {
298 assert(Cond.size() == 1 && "Unknown Cond array format");
299 CC = (AArch64CC::CondCode)(int)Cond[0].getImm();
300 return true;
301 }
302 return false;
303}
304
305// Adjusts one cmp instruction to another one if result of adjustment will allow
306// CSE. Returns true if compare instruction was changed, otherwise false is
307// returned.
308bool AArch64ConditionOptimizer::adjustTo(MachineInstr *CmpMI,
309 AArch64CC::CondCode Cmp, MachineInstr *To, int ToImm)
310{
311 CmpInfo Info = adjustCmp(CmpMI, Cmp);
312 if (std::get<0>(t&: Info) == ToImm && std::get<1>(t&: Info) == To->getOpcode()) {
313 modifyCmp(CmpMI, Info);
314 return true;
315 }
316 return false;
317}
318
319bool AArch64ConditionOptimizer::isPureCmp(MachineInstr &CmpMI) {
320 unsigned ShiftAmt = AArch64_AM::getShiftValue(Imm: CmpMI.getOperand(i: 3).getImm());
321 if (!CmpMI.getOperand(i: 2).isImm()) {
322 LLVM_DEBUG(dbgs() << "Immediate of cmp is symbolic, " << CmpMI << '\n');
323 return false;
324 } else if (CmpMI.getOperand(i: 2).getImm() << ShiftAmt >= 0xfff) {
325 LLVM_DEBUG(dbgs() << "Immediate of cmp may be out of range, " << CmpMI
326 << '\n');
327 return false;
328 } else if (!MRI->use_nodbg_empty(RegNo: CmpMI.getOperand(i: 0).getReg())) {
329 LLVM_DEBUG(dbgs() << "Destination of cmp is not dead, " << CmpMI << '\n');
330 return false;
331 }
332
333 return true;
334}
335
336// This function transforms two CMP+CSINC pairs within the same basic block
337// when both conditions are the same (GT/GT or LT/LT) and immediates differ
338// by 1.
339//
340// Example transformation:
341// cmp w8, #10
342// csinc w9, w0, w1, gt ; w9 = (w8 > 10) ? w0 : w1+1
343// cmp w8, #9
344// csinc w10, w0, w1, gt ; w10 = (w8 > 9) ? w0 : w1+1
345//
346// Into:
347// cmp w8, #10
348// csinc w9, w0, w1, gt ; w9 = (w8 > 10) ? w0 : w1+1
349// csinc w10, w0, w1, ge ; w10 = (w8 >= 10) ? w0 : w1+1
350//
351// The second CMP is eliminated, enabling CSE to remove the redundant
352// comparison.
353bool AArch64ConditionOptimizer::optimizeIntraBlock(MachineBasicBlock &MBB) {
354 MachineInstr *FirstCmp = nullptr;
355 MachineInstr *FirstCSINC = nullptr;
356 MachineInstr *SecondCmp = nullptr;
357 MachineInstr *SecondCSINC = nullptr;
358
359 // Find two CMP + CSINC pairs
360 for (MachineInstr &MI : MBB) {
361 switch (MI.getOpcode()) {
362 // cmp is an alias for subs with a dead destination register.
363 case AArch64::SUBSWri:
364 case AArch64::SUBSXri:
365 // cmn is an alias for adds with a dead destination register.
366 case AArch64::ADDSWri:
367 case AArch64::ADDSXri: {
368 if (!FirstCmp) {
369 FirstCmp = &MI;
370 } else if (FirstCSINC && !SecondCmp) {
371 SecondCmp = &MI;
372 }
373 break;
374 }
375
376 case AArch64::CSINCWr:
377 case AArch64::CSINCXr: {
378 // Found a CSINC, ensure it comes after the corresponding comparison
379 if (FirstCmp && !FirstCSINC) {
380 FirstCSINC = &MI;
381 } else if (SecondCmp && !SecondCSINC) {
382 SecondCSINC = &MI;
383 }
384 break;
385 }
386 }
387
388 if (SecondCSINC)
389 break;
390 }
391
392 if (!SecondCmp || !SecondCSINC) {
393 LLVM_DEBUG(dbgs() << "Didn't find two CMP+CSINC pairs\n");
394 return false;
395 }
396
397 if (FirstCmp->getOperand(i: 1).getReg() != SecondCmp->getOperand(i: 1).getReg()) {
398 LLVM_DEBUG(dbgs() << "CMPs compare different registers\n");
399 return false;
400 }
401
402 if (!isPureCmp(CmpMI&: *FirstCmp) || !isPureCmp(CmpMI&: *SecondCmp)) {
403 LLVM_DEBUG(dbgs() << "One or both CMPs are not pure\n");
404 return false;
405 }
406
407 // Check that nothing else modifies the flags between the first CMP and second
408 // conditional
409 for (auto It = std::next(x: MachineBasicBlock::iterator(FirstCmp));
410 It != std::next(x: MachineBasicBlock::iterator(SecondCSINC)); ++It) {
411 if (&*It != SecondCmp &&
412 It->modifiesRegister(Reg: AArch64::NZCV, /*TRI=*/nullptr)) {
413 LLVM_DEBUG(dbgs() << "Flags modified between CMPs by: " << *It << '\n');
414 return false;
415 }
416 }
417
418 // Check flags aren't read after second conditional within the same block
419 for (auto It = std::next(x: MachineBasicBlock::iterator(SecondCSINC));
420 It != MBB.end(); ++It) {
421 if (It->readsRegister(Reg: AArch64::NZCV, /*TRI=*/nullptr)) {
422 LLVM_DEBUG(dbgs() << "Flags read after second CSINC by: " << *It << '\n');
423 return false;
424 }
425 }
426
427 // Since we may modify a cmp in this MBB, make sure NZCV does not live out.
428 for (auto *SuccBB : MBB.successors())
429 if (SuccBB->isLiveIn(Reg: AArch64::NZCV))
430 return false;
431
432 // Extract condition codes from both CSINCs (operand 3)
433 AArch64CC::CondCode FirstCond =
434 (AArch64CC::CondCode)(int)FirstCSINC->getOperand(i: 3).getImm();
435 AArch64CC::CondCode SecondCond =
436 (AArch64CC::CondCode)(int)SecondCSINC->getOperand(i: 3).getImm();
437
438 const int FirstImm = (int)FirstCmp->getOperand(i: 2).getImm();
439 const int SecondImm = (int)SecondCmp->getOperand(i: 2).getImm();
440
441 LLVM_DEBUG(dbgs() << "Comparing intra-block CSINCs: "
442 << AArch64CC::getCondCodeName(FirstCond) << " #" << FirstImm
443 << " and " << AArch64CC::getCondCodeName(SecondCond) << " #"
444 << SecondImm << '\n');
445
446 // Check if both conditions are the same and immediates differ by 1
447 if (((FirstCond == AArch64CC::GT && SecondCond == AArch64CC::GT) ||
448 (FirstCond == AArch64CC::LT && SecondCond == AArch64CC::LT)) &&
449 std::abs(x: SecondImm - FirstImm) == 1) {
450 // Pick which comparison to adjust to match the other
451 // For GT: adjust the one with smaller immediate
452 // For LT: adjust the one with larger immediate
453 bool adjustFirst = (FirstImm < SecondImm);
454 if (FirstCond == AArch64CC::LT) {
455 adjustFirst = !adjustFirst;
456 }
457
458 MachineInstr *CmpToAdjust = adjustFirst ? FirstCmp : SecondCmp;
459 MachineInstr *CSINCToAdjust = adjustFirst ? FirstCSINC : SecondCSINC;
460 AArch64CC::CondCode CondToAdjust = adjustFirst ? FirstCond : SecondCond;
461 int TargetImm = adjustFirst ? SecondImm : FirstImm;
462
463 CmpInfo AdjustedInfo = adjustCmp(CmpMI: CmpToAdjust, Cmp: CondToAdjust);
464
465 if (std::get<0>(t&: AdjustedInfo) == TargetImm &&
466 std::get<1>(t&: AdjustedInfo) ==
467 (adjustFirst ? SecondCmp : FirstCmp)->getOpcode()) {
468 LLVM_DEBUG(dbgs() << "Successfully optimizing intra-block CSINC pair\n");
469
470 // Modify the selected CMP and CSINC
471 CmpToAdjust->getOperand(i: 2).setImm(std::get<0>(t&: AdjustedInfo));
472 CmpToAdjust->setDesc(TII->get(Opcode: std::get<1>(t&: AdjustedInfo)));
473 CSINCToAdjust->getOperand(i: 3).setImm(std::get<2>(t&: AdjustedInfo));
474
475 return true;
476 }
477 }
478
479 return false;
480}
481
482// Optimize across blocks
483bool AArch64ConditionOptimizer::optimizeCrossBlock(MachineBasicBlock &HBB) {
484 SmallVector<MachineOperand, 4> HeadCond;
485 MachineBasicBlock *TBB = nullptr, *FBB = nullptr;
486 if (TII->analyzeBranch(MBB&: HBB, TBB, FBB, Cond&: HeadCond)) {
487 return false;
488 }
489
490 // Equivalence check is to skip loops.
491 if (!TBB || TBB == &HBB) {
492 return false;
493 }
494
495 SmallVector<MachineOperand, 4> TrueCond;
496 MachineBasicBlock *TBB_TBB = nullptr, *TBB_FBB = nullptr;
497 if (TII->analyzeBranch(MBB&: *TBB, TBB&: TBB_TBB, FBB&: TBB_FBB, Cond&: TrueCond)) {
498 return false;
499 }
500
501 MachineInstr *HeadCmpMI = findSuitableCompare(MBB: &HBB);
502 if (!HeadCmpMI) {
503 return false;
504 }
505
506 MachineInstr *TrueCmpMI = findSuitableCompare(MBB: TBB);
507 if (!TrueCmpMI) {
508 return false;
509 }
510
511 // Ensure both compares use the same register, tracing through copies.
512 Register HeadReg = HeadCmpMI->getOperand(i: 1).getReg();
513 Register TrueReg = TrueCmpMI->getOperand(i: 1).getReg();
514 Register HeadCmpReg =
515 HeadReg.isVirtual() ? TRI->lookThruCopyLike(SrcReg: HeadReg, MRI) : HeadReg;
516 Register TrueCmpReg =
517 TrueReg.isVirtual() ? TRI->lookThruCopyLike(SrcReg: TrueReg, MRI) : TrueReg;
518 if (HeadCmpReg != TrueCmpReg) {
519 LLVM_DEBUG(dbgs() << "CMPs compare different registers\n");
520 return false;
521 }
522
523 AArch64CC::CondCode HeadCmp;
524 if (HeadCond.empty() || !parseCond(Cond: HeadCond, CC&: HeadCmp)) {
525 return false;
526 }
527
528 AArch64CC::CondCode TrueCmp;
529 if (TrueCond.empty() || !parseCond(Cond: TrueCond, CC&: TrueCmp)) {
530 return false;
531 }
532
533 const int HeadImm = (int)HeadCmpMI->getOperand(i: 2).getImm();
534 const int TrueImm = (int)TrueCmpMI->getOperand(i: 2).getImm();
535
536 LLVM_DEBUG(dbgs() << "Head branch:\n");
537 LLVM_DEBUG(dbgs() << "\tcondition: " << AArch64CC::getCondCodeName(HeadCmp)
538 << '\n');
539 LLVM_DEBUG(dbgs() << "\timmediate: " << HeadImm << '\n');
540
541 LLVM_DEBUG(dbgs() << "True branch:\n");
542 LLVM_DEBUG(dbgs() << "\tcondition: " << AArch64CC::getCondCodeName(TrueCmp)
543 << '\n');
544 LLVM_DEBUG(dbgs() << "\timmediate: " << TrueImm << '\n');
545
546 if (((HeadCmp == AArch64CC::GT && TrueCmp == AArch64CC::LT) ||
547 (HeadCmp == AArch64CC::LT && TrueCmp == AArch64CC::GT)) &&
548 std::abs(x: TrueImm - HeadImm) == 2) {
549 // This branch transforms machine instructions that correspond to
550 //
551 // 1) (a > {TrueImm} && ...) || (a < {HeadImm} && ...)
552 // 2) (a < {TrueImm} && ...) || (a > {HeadImm} && ...)
553 //
554 // into
555 //
556 // 1) (a >= {NewImm} && ...) || (a <= {NewImm} && ...)
557 // 2) (a <= {NewImm} && ...) || (a >= {NewImm} && ...)
558
559 CmpInfo HeadCmpInfo = adjustCmp(CmpMI: HeadCmpMI, Cmp: HeadCmp);
560 CmpInfo TrueCmpInfo = adjustCmp(CmpMI: TrueCmpMI, Cmp: TrueCmp);
561 if (std::get<0>(t&: HeadCmpInfo) == std::get<0>(t&: TrueCmpInfo) &&
562 std::get<1>(t&: HeadCmpInfo) == std::get<1>(t&: TrueCmpInfo)) {
563 modifyCmp(CmpMI: HeadCmpMI, Info: HeadCmpInfo);
564 modifyCmp(CmpMI: TrueCmpMI, Info: TrueCmpInfo);
565 return true;
566 }
567 } else if (((HeadCmp == AArch64CC::GT && TrueCmp == AArch64CC::GT) ||
568 (HeadCmp == AArch64CC::LT && TrueCmp == AArch64CC::LT)) &&
569 std::abs(x: TrueImm - HeadImm) == 1) {
570 // This branch transforms machine instructions that correspond to
571 //
572 // 1) (a > {TrueImm} && ...) || (a > {HeadImm} && ...)
573 // 2) (a < {TrueImm} && ...) || (a < {HeadImm} && ...)
574 //
575 // into
576 //
577 // 1) (a <= {NewImm} && ...) || (a > {NewImm} && ...)
578 // 2) (a < {NewImm} && ...) || (a >= {NewImm} && ...)
579
580 // GT -> GE transformation increases immediate value, so picking the
581 // smaller one; LT -> LE decreases immediate value so invert the choice.
582 bool adjustHeadCond = (HeadImm < TrueImm);
583 if (HeadCmp == AArch64CC::LT) {
584 adjustHeadCond = !adjustHeadCond;
585 }
586
587 if (adjustHeadCond) {
588 return adjustTo(CmpMI: HeadCmpMI, Cmp: HeadCmp, To: TrueCmpMI, ToImm: TrueImm);
589 } else {
590 return adjustTo(CmpMI: TrueCmpMI, Cmp: TrueCmp, To: HeadCmpMI, ToImm: HeadImm);
591 }
592 }
593 // Other transformation cases almost never occur due to generation of < or >
594 // comparisons instead of <= and >=.
595
596 return false;
597}
598
599bool AArch64ConditionOptimizer::runOnMachineFunction(MachineFunction &MF) {
600 LLVM_DEBUG(dbgs() << "********** AArch64 Conditional Compares **********\n"
601 << "********** Function: " << MF.getName() << '\n');
602 if (skipFunction(F: MF.getFunction()))
603 return false;
604
605 TII = MF.getSubtarget().getInstrInfo();
606 TRI = MF.getSubtarget().getRegisterInfo();
607 DomTree = &getAnalysis<MachineDominatorTreeWrapperPass>().getDomTree();
608 MRI = &MF.getRegInfo();
609
610 bool Changed = false;
611
612 // Visit blocks in dominator tree pre-order. The pre-order enables multiple
613 // cmp-conversions from the same head block.
614 // Note that updateDomTree() modifies the children of the DomTree node
615 // currently being visited. The df_iterator supports that; it doesn't look at
616 // child_begin() / child_end() until after a node has been visited.
617 for (MachineDomTreeNode *I : depth_first(G: DomTree)) {
618 MachineBasicBlock *HBB = I->getBlock();
619 Changed |= optimizeIntraBlock(MBB&: *HBB);
620 Changed |= optimizeCrossBlock(HBB&: *HBB);
621 }
622
623 return Changed;
624}
625