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: Select-family 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// - allow second branching to be anything if it doesn't require adjusting
59//
60// Cross-block optimizeCrossBlock() handles four head/true-successor
61// combinations:
62// Bcc (head) + Bcc (true) -- original case
63// Select (head) + Bcc (true) -- head ends with CSEL/CSET/etc.
64// Bcc (head) + Select (true) -- true-successor ends with CSEL/CSET/etc.
65// Select (head) + Select (true) -- both blocks end with a select
66//
67//===----------------------------------------------------------------------===//
68
69#include "AArch64.h"
70#include "AArch64Subtarget.h"
71#include "MCTargetDesc/AArch64AddressingModes.h"
72#include "Utils/AArch64BaseInfo.h"
73#include "llvm/ADT/ArrayRef.h"
74#include "llvm/ADT/DepthFirstIterator.h"
75#include "llvm/ADT/SmallVector.h"
76#include "llvm/ADT/Statistic.h"
77#include "llvm/CodeGen/MachineBasicBlock.h"
78#include "llvm/CodeGen/MachineDominators.h"
79#include "llvm/CodeGen/MachineFunction.h"
80#include "llvm/CodeGen/MachineFunctionPass.h"
81#include "llvm/CodeGen/MachineInstr.h"
82#include "llvm/CodeGen/MachineOperand.h"
83#include "llvm/CodeGen/MachineRegisterInfo.h"
84#include "llvm/CodeGen/TargetInstrInfo.h"
85#include "llvm/CodeGen/TargetRegisterInfo.h"
86#include "llvm/CodeGen/TargetSubtargetInfo.h"
87#include "llvm/InitializePasses.h"
88#include "llvm/Pass.h"
89#include "llvm/Support/Debug.h"
90#include "llvm/Support/ErrorHandling.h"
91#include "llvm/Support/raw_ostream.h"
92#include <cassert>
93#include <cstdlib>
94
95using namespace llvm;
96
97#define DEBUG_TYPE "aarch64-condopt"
98
99STATISTIC(NumConditionsAdjusted, "Number of conditions adjusted");
100
101namespace {
102
103/// Bundles the parameters needed to adjust a comparison instruction.
104struct CmpInfo {
105 int Imm;
106 unsigned Opc;
107 AArch64CC::CondCode CC;
108};
109
110class AArch64ConditionOptimizerImpl {
111 /// Represents a comparison instruction paired with its consuming
112 /// conditional instruction
113 struct CmpCondPair {
114 MachineInstr *CmpMI;
115 MachineInstr *CondMI;
116 AArch64CC::CondCode CC;
117
118 int getImm() const { return CmpMI->getOperand(i: 2).getImm(); }
119 unsigned getOpc() const { return CmpMI->getOpcode(); }
120 };
121
122 const AArch64InstrInfo *TII;
123 const TargetRegisterInfo *TRI;
124 MachineDominatorTree *DomTree;
125 const MachineRegisterInfo *MRI;
126
127public:
128 bool run(MachineFunction &MF, MachineDominatorTree &MDT);
129
130private:
131 bool canAdjustCmp(MachineInstr &CmpMI);
132 bool registersMatch(MachineInstr *FirstMI, MachineInstr *SecondMI);
133 bool nzcvLivesOut(MachineBasicBlock *MBB);
134 MachineInstr *getBccTerminator(MachineBasicBlock *MBB);
135 MachineInstr *findAdjustableCmp(MachineInstr *CondMI);
136 CmpInfo getAdjustedCmpInfo(MachineInstr *CmpMI, AArch64CC::CondCode Cmp);
137 void updateCmpInstr(MachineInstr *CmpMI, int NewImm, unsigned NewOpc);
138 void updateCondInstr(MachineInstr *CondMI, AArch64CC::CondCode NewCC);
139 void applyCmpAdjustment(CmpCondPair &Pair, const CmpInfo &Info);
140 bool commitPendingPair(std::optional<CmpCondPair> &PendingPair,
141 SmallDenseMap<Register, CmpCondPair> &PairsByReg);
142 bool tryOptimizePair(CmpCondPair &First, CmpCondPair &Second);
143 bool optimizeIntraBlock(MachineBasicBlock &MBB);
144 bool optimizeCrossBlock(MachineBasicBlock &HBB);
145 std::pair<MachineInstr *, AArch64CC::CondCode>
146 findCondConsumer(MachineBasicBlock *MBB);
147};
148
149class AArch64ConditionOptimizerLegacy : public MachineFunctionPass {
150public:
151 static char ID;
152 AArch64ConditionOptimizerLegacy() : MachineFunctionPass(ID) {}
153
154 void getAnalysisUsage(AnalysisUsage &AU) const override;
155 bool runOnMachineFunction(MachineFunction &MF) override;
156
157 StringRef getPassName() const override {
158 return "AArch64 Condition Optimizer";
159 }
160};
161
162} // end anonymous namespace
163
164char AArch64ConditionOptimizerLegacy::ID = 0;
165
166INITIALIZE_PASS_BEGIN(AArch64ConditionOptimizerLegacy, "aarch64-condopt",
167 "AArch64 CondOpt Pass", false, false)
168INITIALIZE_PASS_DEPENDENCY(MachineDominatorTreeWrapperPass)
169INITIALIZE_PASS_END(AArch64ConditionOptimizerLegacy, "aarch64-condopt",
170 "AArch64 CondOpt Pass", false, false)
171
172FunctionPass *llvm::createAArch64ConditionOptimizerLegacyPass() {
173 return new AArch64ConditionOptimizerLegacy();
174}
175
176void AArch64ConditionOptimizerLegacy::getAnalysisUsage(
177 AnalysisUsage &AU) const {
178 AU.addRequired<MachineDominatorTreeWrapperPass>();
179 AU.addPreserved<MachineDominatorTreeWrapperPass>();
180 MachineFunctionPass::getAnalysisUsage(AU);
181}
182
183// Verify that the MI's immediate is adjustable and it only sets flags (pure
184// cmp)
185bool AArch64ConditionOptimizerImpl::canAdjustCmp(MachineInstr &CmpMI) {
186 unsigned ShiftAmt = AArch64_AM::getShiftValue(Imm: CmpMI.getOperand(i: 3).getImm());
187 if (!CmpMI.getOperand(i: 2).isImm()) {
188 LLVM_DEBUG(dbgs() << "Immediate of cmp is symbolic, " << CmpMI << '\n');
189 return false;
190 } else if (CmpMI.getOperand(i: 2).getImm() << ShiftAmt >= 0xfff) {
191 LLVM_DEBUG(dbgs() << "Immediate of cmp may be out of range, " << CmpMI
192 << '\n');
193 return false;
194 } else if (!MRI->use_nodbg_empty(RegNo: CmpMI.getOperand(i: 0).getReg())) {
195 LLVM_DEBUG(dbgs() << "Destination of cmp is not dead, " << CmpMI << '\n');
196 return false;
197 }
198
199 return true;
200}
201
202// Ensure both compare MIs use the same register, tracing through copies.
203bool AArch64ConditionOptimizerImpl::registersMatch(MachineInstr *FirstMI,
204 MachineInstr *SecondMI) {
205 Register FirstReg = FirstMI->getOperand(i: 1).getReg();
206 Register SecondReg = SecondMI->getOperand(i: 1).getReg();
207 Register FirstCmpReg =
208 FirstReg.isVirtual() ? TRI->lookThruCopyLike(SrcReg: FirstReg, MRI) : FirstReg;
209 Register SecondCmpReg =
210 SecondReg.isVirtual() ? TRI->lookThruCopyLike(SrcReg: SecondReg, MRI) : SecondReg;
211 if (FirstCmpReg != SecondCmpReg) {
212 LLVM_DEBUG(dbgs() << "CMPs compare different registers\n");
213 return false;
214 }
215
216 return true;
217}
218
219// Check if NZCV lives out to any successor block.
220bool AArch64ConditionOptimizerImpl::nzcvLivesOut(MachineBasicBlock *MBB) {
221 for (auto *SuccBB : MBB->successors()) {
222 if (SuccBB->isLiveIn(Reg: AArch64::NZCV)) {
223 LLVM_DEBUG(dbgs() << "NZCV live into successor "
224 << printMBBReference(*SuccBB) << " from "
225 << printMBBReference(*MBB) << '\n');
226 return true;
227 }
228 }
229 return false;
230}
231
232// Returns true if the opcode is a comparison instruction (CMP/CMN).
233static bool isCmpInstruction(unsigned Opc) {
234 switch (Opc) {
235 // cmp is an alias for SUBS with a dead destination register.
236 case AArch64::SUBSWri:
237 case AArch64::SUBSXri:
238 // cmp is an alias for ADDS with a dead destination register.
239 case AArch64::ADDSWri:
240 case AArch64::ADDSXri:
241 return true;
242 default:
243 return false;
244 }
245}
246
247// Returns the Bcc terminator if present, otherwise nullptr.
248MachineInstr *
249AArch64ConditionOptimizerImpl::getBccTerminator(MachineBasicBlock *MBB) {
250 MachineBasicBlock::iterator Term = MBB->getFirstTerminator();
251 if (Term == MBB->end()) {
252 LLVM_DEBUG(dbgs() << "No terminator in " << printMBBReference(*MBB)
253 << '\n');
254 return nullptr;
255 }
256
257 if (Term->getOpcode() != AArch64::Bcc) {
258 LLVM_DEBUG(dbgs() << "Non-Bcc terminator in " << printMBBReference(*MBB)
259 << ": " << *Term);
260 return nullptr;
261 }
262
263 return &*Term;
264}
265
266// Find the CMP instruction controlling the given conditional instruction and
267// ensure it can be adjusted for CSE optimization. Searches backward from
268// CondMI, ensuring no NZCV interference. Returns nullptr if no suitable CMP
269// is found or if adjustments are not safe.
270MachineInstr *
271AArch64ConditionOptimizerImpl::findAdjustableCmp(MachineInstr *CondMI) {
272 assert(CondMI && "CondMI cannot be null");
273 MachineBasicBlock *MBB = CondMI->getParent();
274
275 // Search backward from the conditional to find the instruction controlling
276 // it.
277 for (MachineBasicBlock::iterator B = MBB->begin(),
278 It = MachineBasicBlock::iterator(CondMI);
279 It != B;) {
280 It = prev_nodbg(It, Begin: B);
281 MachineInstr &I = *It;
282 assert(!I.isTerminator() && "Spurious terminator");
283 // Ensure there is no use of NZCV between CMP and conditional.
284 if (I.readsRegister(Reg: AArch64::NZCV, /*TRI=*/nullptr))
285 return nullptr;
286
287 if (isCmpInstruction(Opc: I.getOpcode())) {
288 if (!canAdjustCmp(CmpMI&: I)) {
289 return nullptr;
290 }
291 return &I;
292 }
293
294 if (I.modifiesRegister(Reg: AArch64::NZCV, /*TRI=*/nullptr))
295 return nullptr;
296 }
297 LLVM_DEBUG(dbgs() << "Flags not defined in " << printMBBReference(*MBB)
298 << '\n');
299 return nullptr;
300}
301
302// Changes opcode adds <-> subs considering register operand width.
303static int getComplementOpc(int Opc) {
304 switch (Opc) {
305 case AArch64::ADDSWri: return AArch64::SUBSWri;
306 case AArch64::ADDSXri: return AArch64::SUBSXri;
307 case AArch64::SUBSWri: return AArch64::ADDSWri;
308 case AArch64::SUBSXri: return AArch64::ADDSXri;
309 default:
310 llvm_unreachable("Unexpected opcode");
311 }
312}
313
314// Changes form of comparison inclusive <-> exclusive.
315static AArch64CC::CondCode getAdjustedCmp(AArch64CC::CondCode Cmp) {
316 switch (Cmp) {
317 case AArch64CC::GT:
318 return AArch64CC::GE;
319 case AArch64CC::GE:
320 return AArch64CC::GT;
321 case AArch64CC::LT:
322 return AArch64CC::LE;
323 case AArch64CC::LE:
324 return AArch64CC::LT;
325 case AArch64CC::HI:
326 return AArch64CC::HS;
327 case AArch64CC::HS:
328 return AArch64CC::HI;
329 case AArch64CC::LO:
330 return AArch64CC::LS;
331 case AArch64CC::LS:
332 return AArch64CC::LO;
333 default:
334 llvm_unreachable("Unexpected condition code");
335 }
336}
337
338// Returns the adjusted immediate, opcode, and condition code for switching
339// between inclusive/exclusive forms (GT <-> GE, LT <-> LE).
340CmpInfo
341AArch64ConditionOptimizerImpl::getAdjustedCmpInfo(MachineInstr *CmpMI,
342 AArch64CC::CondCode Cmp) {
343 unsigned Opc = CmpMI->getOpcode();
344
345 bool IsSigned = Cmp == AArch64CC::GT || Cmp == AArch64CC::GE ||
346 Cmp == AArch64CC::LT || Cmp == AArch64CC::LE;
347
348 // CMN (compare with negative immediate) is an alias to ADDS (as
349 // "operand - negative" == "operand + positive")
350 bool Negative = (Opc == AArch64::ADDSWri || Opc == AArch64::ADDSXri);
351
352 int Correction = (Cmp == AArch64CC::GT || Cmp == AArch64CC::HI) ? 1 : -1;
353 // Negate Correction value for comparison with negative immediate (CMN).
354 if (Negative) {
355 Correction = -Correction;
356 }
357
358 const int OldImm = (int)CmpMI->getOperand(i: 2).getImm();
359 const int NewImm = std::abs(x: OldImm + Correction);
360
361 // Bail out on cmn 0 (ADDS with immediate 0). It is a valid instruction but
362 // doesn't set flags in a way we can safely transform, so skip optimization.
363 if (OldImm == 0 && Negative)
364 return {.Imm: OldImm, .Opc: Opc, .CC: Cmp};
365
366 if ((OldImm == 1 && Negative && Correction == -1) ||
367 (OldImm == 0 && Correction == -1)) {
368 // If we change opcodes for unsigned comparisons, this means we did an
369 // unsigned wrap (e.g., 0 wrapping to 0xFFFFFFFF), so return the old cmp.
370 // Note: For signed comparisons, opcode changes (cmn 1 ↔ cmp 0) are valid.
371 if (!IsSigned)
372 return {.Imm: OldImm, .Opc: Opc, .CC: Cmp};
373 Opc = getComplementOpc(Opc);
374 }
375
376 return {.Imm: NewImm, .Opc: Opc, .CC: getAdjustedCmp(Cmp)};
377}
378
379// Modifies a comparison instruction's immediate and opcode.
380void AArch64ConditionOptimizerImpl::updateCmpInstr(MachineInstr *CmpMI,
381 int NewImm,
382 unsigned NewOpc) {
383 CmpMI->getOperand(i: 2).setImm(NewImm);
384 CmpMI->setDesc(TII->get(Opcode: NewOpc));
385}
386
387// Modifies the condition code of a conditional instruction.
388void AArch64ConditionOptimizerImpl::updateCondInstr(MachineInstr *CondMI,
389 AArch64CC::CondCode NewCC) {
390 int CCOpIdx =
391 AArch64InstrInfo::findCondCodeUseOperandIdxForBranchOrSelect(Instr: *CondMI);
392 assert(CCOpIdx >= 0 && "Unsupported conditional instruction");
393 CondMI->getOperand(i: CCOpIdx).setImm(NewCC);
394 ++NumConditionsAdjusted;
395}
396
397// Applies a comparison adjustment to a cmp/cond instruction pair.
398void AArch64ConditionOptimizerImpl::applyCmpAdjustment(CmpCondPair &Pair,
399 const CmpInfo &Info) {
400 updateCmpInstr(CmpMI: Pair.CmpMI, NewImm: Info.Imm, NewOpc: Info.Opc);
401 updateCondInstr(CondMI: Pair.CondMI, NewCC: Info.CC);
402 Pair.CC = Info.CC;
403}
404
405// Extracts the condition code from the result of analyzeBranch.
406// Returns the CondCode or Invalid if the format is not a simple br.cond.
407static AArch64CC::CondCode parseCondCode(ArrayRef<MachineOperand> Cond) {
408 assert(!Cond.empty() && "Expected non-empty condition from analyzeBranch");
409 // A normal br.cond simply has the condition code.
410 if (Cond[0].getImm() != -1) {
411 assert(Cond.size() == 1 && "Unknown Cond array format");
412 return (AArch64CC::CondCode)(int)Cond[0].getImm();
413 }
414 return AArch64CC::CondCode::Invalid;
415}
416
417static bool isGreaterThan(AArch64CC::CondCode Cmp) {
418 return Cmp == AArch64CC::GT || Cmp == AArch64CC::HI;
419}
420
421static bool isLessThan(AArch64CC::CondCode Cmp) {
422 return Cmp == AArch64CC::LT || Cmp == AArch64CC::LO;
423}
424
425bool AArch64ConditionOptimizerImpl::tryOptimizePair(CmpCondPair &First,
426 CmpCondPair &Second) {
427 if (!((isGreaterThan(Cmp: First.CC) || isLessThan(Cmp: First.CC)) &&
428 (isGreaterThan(Cmp: Second.CC) || isLessThan(Cmp: Second.CC))))
429 return false;
430
431 int FirstImmTrueValue = First.getImm();
432 int SecondImmTrueValue = Second.getImm();
433
434 // Normalize immediate of CMN (ADDS) instructions
435 if (First.getOpc() == AArch64::ADDSWri || First.getOpc() == AArch64::ADDSXri)
436 FirstImmTrueValue = -FirstImmTrueValue;
437 if (Second.getOpc() == AArch64::ADDSWri ||
438 Second.getOpc() == AArch64::ADDSXri)
439 SecondImmTrueValue = -SecondImmTrueValue;
440
441 CmpInfo FirstAdj = getAdjustedCmpInfo(CmpMI: First.CmpMI, Cmp: First.CC);
442 CmpInfo SecondAdj = getAdjustedCmpInfo(CmpMI: Second.CmpMI, Cmp: Second.CC);
443
444 if (((isGreaterThan(Cmp: First.CC) && isLessThan(Cmp: Second.CC)) ||
445 (isLessThan(Cmp: First.CC) && isGreaterThan(Cmp: Second.CC))) &&
446 std::abs(x: SecondImmTrueValue - FirstImmTrueValue) == 2) {
447 // This branch transforms machine instructions that correspond to
448 //
449 // 1) (a > {SecondImm} && ...) || (a < {FirstImm} && ...)
450 // 2) (a < {SecondImm} && ...) || (a > {FirstImm} && ...)
451 //
452 // into
453 //
454 // 1) (a >= {NewImm} && ...) || (a <= {NewImm} && ...)
455 // 2) (a <= {NewImm} && ...) || (a >= {NewImm} && ...)
456
457 // Verify both adjustments converge to identical comparisons (same
458 // immediate and opcode). This ensures CSE can eliminate the duplicate.
459 if (FirstAdj.Imm != SecondAdj.Imm || FirstAdj.Opc != SecondAdj.Opc)
460 return false;
461
462 LLVM_DEBUG(dbgs() << "Optimized (opposite): "
463 << AArch64CC::getCondCodeName(First.CC) << " #"
464 << First.getImm() << ", "
465 << AArch64CC::getCondCodeName(Second.CC) << " #"
466 << Second.getImm() << " -> "
467 << AArch64CC::getCondCodeName(FirstAdj.CC) << " #"
468 << FirstAdj.Imm << ", "
469 << AArch64CC::getCondCodeName(SecondAdj.CC) << " #"
470 << SecondAdj.Imm << '\n');
471 applyCmpAdjustment(Pair&: First, Info: FirstAdj);
472 applyCmpAdjustment(Pair&: Second, Info: SecondAdj);
473 return true;
474
475 } else if (((isGreaterThan(Cmp: First.CC) && isGreaterThan(Cmp: Second.CC)) ||
476 (isLessThan(Cmp: First.CC) && isLessThan(Cmp: Second.CC))) &&
477 std::abs(x: SecondImmTrueValue - FirstImmTrueValue) == 1) {
478 // This branch transforms machine instructions that correspond to
479 //
480 // 1) (a > {SecondImm} && ...) || (a > {FirstImm} && ...)
481 // 2) (a < {SecondImm} && ...) || (a < {FirstImm} && ...)
482 //
483 // into
484 //
485 // 1) (a <= {NewImm} && ...) || (a > {NewImm} && ...)
486 // 2) (a < {NewImm} && ...) || (a >= {NewImm} && ...)
487
488 // GT -> GE transformation increases immediate value, so picking the
489 // smaller one; LT -> LE decreases immediate value so invert the choice.
490 bool AdjustFirst = (FirstImmTrueValue < SecondImmTrueValue);
491 if (isLessThan(Cmp: First.CC))
492 AdjustFirst = !AdjustFirst;
493
494 CmpCondPair &Target = AdjustFirst ? Second : First;
495 CmpCondPair &ToChange = AdjustFirst ? First : Second;
496 CmpInfo &Adj = AdjustFirst ? FirstAdj : SecondAdj;
497
498 // Verify the adjustment converges to the target's comparison (same
499 // immediate and opcode). This ensures CSE can eliminate the duplicate.
500 if (Adj.Imm != Target.getImm() || Adj.Opc != Target.getOpc())
501 return false;
502
503 LLVM_DEBUG(dbgs() << "Optimized (same-direction): "
504 << AArch64CC::getCondCodeName(ToChange.CC) << " #"
505 << ToChange.getImm() << " -> "
506 << AArch64CC::getCondCodeName(Adj.CC) << " #" << Adj.Imm
507 << '\n');
508 applyCmpAdjustment(Pair&: ToChange, Info: Adj);
509 return true;
510 }
511
512 // Other transformation cases almost never occur due to generation of < or >
513 // comparisons instead of <= and >=.
514 return false;
515}
516
517bool AArch64ConditionOptimizerImpl::commitPendingPair(
518 std::optional<CmpCondPair> &PendingPair,
519 SmallDenseMap<Register, CmpCondPair> &PairsByReg) {
520 if (!PendingPair)
521 return false;
522
523 Register Reg = PendingPair->CmpMI->getOperand(i: 1).getReg();
524 Register Key = Reg.isVirtual() ? TRI->lookThruCopyLike(SrcReg: Reg, MRI) : Reg;
525
526 auto MatchingPair = PairsByReg.find(Val: Key);
527 bool Changed = MatchingPair != PairsByReg.end() &&
528 tryOptimizePair(First&: MatchingPair->second, Second&: *PendingPair);
529
530 PairsByReg[Key] = *PendingPair;
531 PendingPair = std::nullopt;
532 return Changed;
533}
534
535// This function transforms cmps and their consuming conditionals (CmpCondPairs)
536// 1. Same direction: when both conditions are the same (e.g. GT/GT or LT/LT)
537// and immediates differ by 1
538// 2. Opposite direction: when both conditions are adjustable to a common middle
539// (e.g., GT/LT) and immediates differ by 2.
540// The compare instructions are made to match to enable CSE.
541// All cmp/cond pairs within a basic block are examined
542//
543// Example transformation:
544// cmp w8, #10
545// csinc w9, w0, w1, gt ; w9 = (w8 > 10) ? w0 : w1+1
546// cmp w8, #9
547// csinc w10, w0, w1, gt ; w10 = (w8 > 9) ? w0 : w1+1
548//
549// Into:
550// cmp w8, #10
551// csinc w9, w0, w1, gt ; w9 = (w8 > 10) ? w0 : w1+1
552// cmp w8, #10 ; <- CSE can remove the redundant cmp
553// csinc w10, w0, w1, ge ; w10 = (w8 >= 10) ? w0 : w1+1
554//
555bool AArch64ConditionOptimizerImpl::optimizeIntraBlock(MachineBasicBlock &MBB) {
556 SmallDenseMap<Register, CmpCondPair> PairsByReg;
557 std::optional<CmpCondPair> PendingPair;
558 MachineInstr *ActiveCmp = nullptr;
559 bool Changed = false;
560
561 for (MachineInstr &MI : MBB) {
562 if (MI.isDebugInstr())
563 continue;
564
565 if (isCmpInstruction(Opc: MI.getOpcode()) && canAdjustCmp(CmpMI&: MI)) {
566 Changed |= commitPendingPair(PendingPair, PairsByReg);
567 ActiveCmp = &MI;
568 continue;
569 }
570
571 if (MI.modifiesRegister(Reg: AArch64::NZCV, /*TRI=*/nullptr)) {
572 // Non-CMP clobber: commit any pending pair and reset all state, since
573 // unknown flag state at this point invalidates all prior pairs
574 Changed |= commitPendingPair(PendingPair, PairsByReg);
575 ActiveCmp = nullptr;
576 PairsByReg.clear();
577 continue;
578 }
579
580 if (AArch64InstrInfo::findCondCodeUseOperandIdxForBranchOrSelect(Instr: MI) >= 0 &&
581 !MI.isBranch()) {
582 if (PendingPair) {
583 // A second conditional consuming the same CMP would invalidate any
584 // optimization: modifying the CMP would silently change what both
585 // consumers compare against. Mark the CMP spent.
586 PendingPair = std::nullopt;
587 ActiveCmp = nullptr;
588 } else if (ActiveCmp) {
589 int CCOpIdx =
590 AArch64InstrInfo::findCondCodeUseOperandIdxForBranchOrSelect(Instr: MI);
591 assert(CCOpIdx >= 0 && "Unsupported conditional instruction");
592 AArch64CC::CondCode CC =
593 (AArch64CC::CondCode)(int)MI.getOperand(i: CCOpIdx).getImm();
594 PendingPair = CmpCondPair{.CmpMI: ActiveCmp, .CondMI: &MI, .CC: CC};
595 }
596 continue;
597 }
598
599 if (MI.readsRegister(Reg: AArch64::NZCV, /*TRI=*/nullptr)) {
600 ActiveCmp = nullptr;
601 PendingPair = std::nullopt;
602 continue;
603 }
604 }
605
606 // Only commit the final pending pair if NZCV doesn't live out: a cross-block
607 // consumer would be affected by any CMP adjustment we make.
608 if (!nzcvLivesOut(MBB: &MBB))
609 Changed |= commitPendingPair(PendingPair, PairsByReg);
610
611 return Changed;
612}
613
614// Finds the last valid conditional consumer in MBB and returns it together
615// with its condition code. Handles two cases:
616//
617// 1. Bcc terminator: if the block ends with a Bcc, analyzeBranch extracts
618// the condition code directly from the branch operands.
619//
620// 2. Select-family instruction (CSET/CSEL/CSINC/CSINV/CSNEG): scans
621// backward past terminators to find the sole non-branch NZCV consumer,
622// verifying there is no interfering NZCV read or write between it and
623// the CMP that produces the flags.
624//
625// Returns {nullptr, Invalid} if no suitable consumer is found or if any
626// safety check fails.
627std::pair<MachineInstr *, AArch64CC::CondCode>
628AArch64ConditionOptimizerImpl::findCondConsumer(MachineBasicBlock *MBB) {
629 // Case 1: block ends with a Bcc terminator.
630 if (MachineInstr *BrMI = getBccTerminator(MBB)) {
631 SmallVector<MachineOperand, 4> CondOperands;
632 MachineBasicBlock *TBBDest = nullptr, *FBBDest = nullptr;
633 if (TII->analyzeBranch(MBB&: *MBB, TBB&: TBBDest, FBB&: FBBDest, Cond&: CondOperands))
634 return {nullptr, AArch64CC::Invalid};
635 AArch64CC::CondCode CC = parseCondCode(Cond: CondOperands);
636 if (CC == AArch64CC::Invalid)
637 return {nullptr, AArch64CC::Invalid};
638 return {BrMI, CC};
639 }
640
641 // Case 2: no Bcc terminator — scan backward for a select-family instruction
642 // (CSET/CSEL/CSINC/CSINV/CSNEG) that is the sole NZCV consumer in the block.
643 MachineInstr *Found = nullptr;
644 AArch64CC::CondCode FoundCC = AArch64CC::Invalid;
645
646 for (MachineInstr &MI : reverse(C&: *MBB)) {
647 // Skip terminators (e.g. an unconditional branch at the end of the block)
648 // and debug instructions, which carry no real semantics.
649 if (MI.isTerminator() || MI.isDebugInstr())
650 continue;
651
652 if (!Found) {
653 // We have not yet found the select. Keep scanning backward.
654
655 // If something writes NZCV before we find a select, the flags at that
656 // point are not from the CMP we are looking for. Stop searching.
657 if (MI.modifiesRegister(Reg: AArch64::NZCV, /*TRI=*/nullptr))
658 return {nullptr, AArch64CC::Invalid};
659
660 // findCondCodeUseOperandIdxForBranchOrSelect returns the operand index
661 // of the condition code for any branch or select-family instruction, or
662 // -1 if the instruction does not use a condition code.
663 // We exclude branches because getBccTerminator already handles those;
664 // we only want non-branch conditionals: CSET, CSEL, CSINC, CSINV, CSNEG.
665 int CCOpIdx =
666 AArch64InstrInfo::findCondCodeUseOperandIdxForBranchOrSelect(Instr: MI);
667 if (CCOpIdx >= 0 && !MI.isBranch()) {
668 Found = &MI;
669 FoundCC = (AArch64CC::CondCode)(int)MI.getOperand(i: CCOpIdx).getImm();
670 continue;
671 }
672
673 // Any other instruction that reads NZCV (but is not a select) means the
674 // flags are consumed by something we do not understand. Stop searching.
675 if (MI.readsRegister(Reg: AArch64::NZCV, /*TRI=*/nullptr))
676 return {nullptr, AArch64CC::Invalid};
677
678 } else {
679 // We already found a select. Now verify there is no second NZCV reader
680 // between the found select and the CMP. If there is, the CMP feeds two
681 // consumers and cannot be safely adjusted.
682 if (MI.readsRegister(Reg: AArch64::NZCV, /*TRI=*/nullptr))
683 return {nullptr, AArch64CC::Invalid};
684
685 if (MI.modifiesRegister(Reg: AArch64::NZCV, /*TRI=*/nullptr)) {
686 // A CMP instruction is the flag producer we are looking for; stop
687 // scanning. findAdjustableCmp will locate it from CondMI.
688 if (isCmpInstruction(Opc: MI.getOpcode()))
689 break;
690 // Any other NZCV writer means the select is not reading from the CMP
691 // we would find further back.
692 return {nullptr, AArch64CC::Invalid};
693 }
694 }
695 }
696 return {Found, FoundCC};
697}
698
699// Optimizes CMP+conditional pairs across two basic blocks in the dominator
700// tree. The conditional consumer in each block may be a Bcc terminator or a
701// select-family instruction (CSEL/CSET/CSINC/CSINV/CSNEG).
702bool AArch64ConditionOptimizerImpl::optimizeCrossBlock(MachineBasicBlock &HBB) {
703 SmallVector<MachineOperand, 4> HeadCondOperands;
704 MachineBasicBlock *TBB = nullptr, *FBB = nullptr;
705 if (TII->analyzeBranch(MBB&: HBB, TBB, FBB, Cond&: HeadCondOperands)) {
706 return false;
707 }
708
709 // Equivalence check is to skip loops.
710 if (!TBB || TBB == &HBB) {
711 return false;
712 }
713
714 // Find the conditional consumer(Bcc or select-family) and its condition
715 // code in each block. findCondConsumer() handles both cases uniformly.
716 auto [HeadCondMI, HeadCondCode] = findCondConsumer(MBB: &HBB);
717 if (!HeadCondMI)
718 return false;
719
720 auto [TrueCondMI, TrueCondCode] = findCondConsumer(MBB: TBB);
721 if (!TrueCondMI)
722 return false;
723
724 // Since we may modify cmps in these blocks, make sure NZCV does not live out.
725 if (nzcvLivesOut(MBB: &HBB) || nzcvLivesOut(MBB: TBB))
726 return false;
727
728 // Find the CMPs controlling each conditional.
729 MachineInstr *HeadCmpMI = findAdjustableCmp(CondMI: HeadCondMI);
730 MachineInstr *TrueCmpMI = findAdjustableCmp(CondMI: TrueCondMI);
731 if (!HeadCmpMI || !TrueCmpMI)
732 return false;
733
734 if (!registersMatch(FirstMI: HeadCmpMI, SecondMI: TrueCmpMI))
735 return false;
736
737 LLVM_DEBUG(dbgs() << "Checking cross-block pair: "
738 << AArch64CC::getCondCodeName(HeadCondCode) << " #"
739 << HeadCmpMI->getOperand(2).getImm() << ", "
740 << AArch64CC::getCondCodeName(TrueCondCode) << " #"
741 << TrueCmpMI->getOperand(2).getImm() << '\n');
742
743 CmpCondPair Head{.CmpMI: HeadCmpMI, .CondMI: HeadCondMI, .CC: HeadCondCode};
744 CmpCondPair True{.CmpMI: TrueCmpMI, .CondMI: TrueCondMI, .CC: TrueCondCode};
745
746 return tryOptimizePair(First&: Head, Second&: True);
747}
748
749bool AArch64ConditionOptimizerLegacy::runOnMachineFunction(
750 MachineFunction &MF) {
751 if (skipFunction(F: MF.getFunction()))
752 return false;
753 MachineDominatorTree &MDT =
754 getAnalysis<MachineDominatorTreeWrapperPass>().getDomTree();
755 return AArch64ConditionOptimizerImpl().run(MF, MDT);
756}
757
758bool AArch64ConditionOptimizerImpl::run(MachineFunction &MF,
759 MachineDominatorTree &MDT) {
760 LLVM_DEBUG(dbgs() << "********** AArch64 Conditional Compares **********\n"
761 << "********** Function: " << MF.getName() << '\n');
762
763 TII = static_cast<const AArch64InstrInfo *>(MF.getSubtarget().getInstrInfo());
764 TRI = MF.getSubtarget().getRegisterInfo();
765 DomTree = &MDT;
766 MRI = &MF.getRegInfo();
767
768 bool Changed = false;
769
770 // Visit blocks in dominator tree pre-order. The pre-order enables multiple
771 // cmp-conversions from the same head block.
772 // Note that updateDomTree() modifies the children of the DomTree node
773 // currently being visited. The df_iterator supports that; it doesn't look at
774 // child_begin() / child_end() until after a node has been visited.
775 for (MachineDomTreeNode *I : depth_first(G: DomTree)) {
776 MachineBasicBlock *HBB = I->getBlock();
777 Changed |= optimizeIntraBlock(MBB&: *HBB);
778 Changed |= optimizeCrossBlock(HBB&: *HBB);
779 }
780
781 return Changed;
782}
783
784PreservedAnalyses
785AArch64ConditionOptimizerPass::run(MachineFunction &MF,
786 MachineFunctionAnalysisManager &MFAM) {
787 auto &MDT = MFAM.getResult<MachineDominatorTreeAnalysis>(IR&: MF);
788 bool Changed = AArch64ConditionOptimizerImpl().run(MF, MDT);
789 if (!Changed)
790 return PreservedAnalyses::all();
791 PreservedAnalyses PA = getMachineFunctionPassPreservedAnalyses();
792 PA.preserveSet<CFGAnalyses>();
793 return PA;
794}
795