1//===-- AArch64ConditionalCompares.cpp --- CCMP formation 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// This file implements the AArch64ConditionalCompares pass which reduces
10// branching and code size by using the conditional compare instructions CCMP,
11// CCMN, and FCMP.
12//
13// The CFG transformations for forming conditional compares are very similar to
14// if-conversion, and this pass should run immediately before the early
15// if-conversion pass.
16//
17//===----------------------------------------------------------------------===//
18
19#include "AArch64.h"
20#include "AArch64InstrInfo.h"
21#include "AArch64Subtarget.h"
22#include "MCTargetDesc/AArch64AddressingModes.h"
23#include "llvm/ADT/DepthFirstIterator.h"
24#include "llvm/ADT/Statistic.h"
25#include "llvm/CodeGen/MachineBranchProbabilityInfo.h"
26#include "llvm/CodeGen/MachineDominators.h"
27#include "llvm/CodeGen/MachineFunction.h"
28#include "llvm/CodeGen/MachineFunctionPass.h"
29#include "llvm/CodeGen/MachineInstrBuilder.h"
30#include "llvm/CodeGen/MachineLoopInfo.h"
31#include "llvm/CodeGen/MachinePassManager.h"
32#include "llvm/CodeGen/MachineRegisterInfo.h"
33#include "llvm/CodeGen/MachineTraceMetrics.h"
34#include "llvm/CodeGen/Passes.h"
35#include "llvm/CodeGen/TargetInstrInfo.h"
36#include "llvm/CodeGen/TargetRegisterInfo.h"
37#include "llvm/CodeGen/TargetSubtargetInfo.h"
38#include "llvm/InitializePasses.h"
39#include "llvm/Support/Debug.h"
40#include "llvm/Support/raw_ostream.h"
41
42using namespace llvm;
43
44#define DEBUG_TYPE "aarch64-ccmp"
45
46STATISTIC(NumConsidered, "Number of ccmps considered");
47STATISTIC(NumPhiRejs, "Number of ccmps rejected (PHI)");
48STATISTIC(NumPhysRejs, "Number of ccmps rejected (Physregs)");
49STATISTIC(NumPhi2Rejs, "Number of ccmps rejected (PHI2)");
50STATISTIC(NumHeadBranchRejs, "Number of ccmps rejected (Head branch)");
51STATISTIC(NumCmpBranchRejs, "Number of ccmps rejected (CmpBB branch)");
52STATISTIC(NumCmpTermRejs, "Number of ccmps rejected (CmpBB is cbz...)");
53STATISTIC(NumImmRangeRejs, "Number of ccmps rejected (Imm out of range)");
54STATISTIC(NumFoldedExtRejs,
55 "Number of ccmps rejected (Folded zero- or sign-extension)");
56STATISTIC(NumLiveDstRejs, "Number of ccmps rejected (Cmp dest live)");
57STATISTIC(NumMultNZCVUses, "Number of ccmps rejected (NZCV used)");
58STATISTIC(NumUnknNZCVDefs, "Number of ccmps rejected (NZCV def unknown)");
59
60STATISTIC(NumSpeculateRejs, "Number of ccmps rejected (Can't speculate)");
61
62STATISTIC(NumConverted, "Number of ccmp instructions created");
63STATISTIC(NumCompBranches, "Number of cb/cbz/cbnz branches converted");
64
65//===----------------------------------------------------------------------===//
66// SSACCmpConv
67//===----------------------------------------------------------------------===//
68//
69// The SSACCmpConv class performs ccmp-conversion on SSA form machine code
70// after determining if it is possible. The class contains no heuristics;
71// external code should be used to determine when ccmp-conversion is a good
72// idea.
73//
74// CCmp-formation works on a CFG representing chained conditions, typically
75// from C's short-circuit || and && operators:
76//
77// From: Head To: Head
78// / | CmpBB
79// / | / |
80// | CmpBB / |
81// | / | Tail |
82// | / | | |
83// Tail | | |
84// | | | |
85// ... ... ... ...
86//
87// The Head block is terminated by a br.cond instruction, and the CmpBB block
88// contains compare + br.cond. Tail must be a successor of both.
89//
90// The cmp-conversion turns the compare instruction in CmpBB into a conditional
91// compare, and merges CmpBB into Head, speculatively executing its
92// instructions. The AArch64 conditional compare instructions have an immediate
93// operand that specifies the NZCV flag values when the condition is false and
94// the compare isn't executed. This makes it possible to chain compares with
95// different condition codes.
96//
97// Example:
98//
99// if (a == 5 || b == 17)
100// foo();
101//
102// Head:
103// cmp w0, #5
104// b.eq Tail
105// CmpBB:
106// cmp w1, #17
107// b.eq Tail
108// ...
109// Tail:
110// bl _foo
111//
112// Becomes:
113//
114// Head:
115// cmp w0, #5
116// ccmp w1, #17, 4, ne ; 4 = nZcv
117// b.eq Tail
118// ...
119// Tail:
120// bl _foo
121//
122// The ccmp condition code is the one that would cause the Head terminator to
123// branch to CmpBB.
124//
125// FIXME: It should also be possible to speculate a block on the critical edge
126// between Head and Tail, just like if-converting a diamond.
127//
128// FIXME: Handle PHIs in Tail by turning them into selects (if-conversion).
129
130namespace {
131class SSACCmpConv {
132 MachineFunction *MF;
133 const AArch64InstrInfo *TII;
134 const TargetRegisterInfo *TRI;
135 MachineRegisterInfo *MRI;
136 const MachineBranchProbabilityInfo *MBPI;
137
138public:
139 /// The first block containing a conditional branch, dominating everything
140 /// else.
141 MachineBasicBlock *Head;
142
143 /// The block containing cmp+br.cond with a successor shared with Head.
144 MachineBasicBlock *CmpBB;
145
146 /// The common successor for Head and CmpBB.
147 MachineBasicBlock *Tail;
148
149 /// The compare instruction in CmpBB that can be converted to a ccmp.
150 MachineInstr *CmpMI;
151
152private:
153 /// The branch condition in Head as determined by analyzeBranch.
154 SmallVector<MachineOperand, 4> HeadCond;
155
156 /// The condition code that makes Head branch to CmpBB.
157 AArch64CC::CondCode HeadCmpBBCC;
158
159 /// The branch condition in CmpBB.
160 SmallVector<MachineOperand, 4> CmpBBCond;
161
162 /// The condition code that makes CmpBB branch to Tail.
163 AArch64CC::CondCode CmpBBTailCC;
164
165 /// Check if the Tail PHIs are trivially convertible.
166 bool trivialTailPHIs();
167
168 /// Remove CmpBB from the Tail PHIs.
169 void updateTailPHIs();
170
171 /// Check if an operand defining DstReg is dead.
172 bool isDeadDef(unsigned DstReg);
173
174 /// Find the compare instruction in MBB that controls the conditional branch.
175 /// Return NULL if a convertible instruction can't be found.
176 MachineInstr *findConvertibleCompare(MachineBasicBlock *MBB);
177
178 /// Return true if all non-terminator instructions in MBB can be safely
179 /// speculated.
180 bool canSpeculateInstrs(MachineBasicBlock *MBB, const MachineInstr *CmpMI);
181
182public:
183 /// runOnMachineFunction - Initialize per-function data structures.
184 void runOnMachineFunction(MachineFunction &MF,
185 const MachineBranchProbabilityInfo *MBPI) {
186 this->MF = &MF;
187 this->MBPI = MBPI;
188 TII =
189 static_cast<const AArch64InstrInfo *>(MF.getSubtarget().getInstrInfo());
190 TRI = MF.getSubtarget().getRegisterInfo();
191 MRI = &MF.getRegInfo();
192 }
193
194 /// If the sub-CFG headed by MBB can be cmp-converted, initialize the
195 /// internal state, and return true.
196 bool canConvert(MachineBasicBlock *MBB);
197
198 /// Cmo-convert the last block passed to canConvertCmp(), assuming
199 /// it is possible. Add any erased blocks to RemovedBlocks.
200 void convert(SmallVectorImpl<MachineBasicBlock *> &RemovedBlocks);
201
202 /// Return the expected code size delta if the conversion into a
203 /// conditional compare is performed.
204 int expectedCodeSizeDelta() const;
205};
206} // end anonymous namespace
207
208static Register lookThroughCopies(Register Reg, MachineRegisterInfo *MRI) {
209 MachineInstr *MI;
210 while ((MI = MRI->getUniqueVRegDef(Reg)) &&
211 MI->getOpcode() == TargetOpcode::COPY) {
212 if (MI->getOperand(i: 1).getReg().isPhysical())
213 break;
214 Reg = MI->getOperand(i: 1).getReg();
215 }
216 return Reg;
217}
218
219// Check that all PHIs in Tail are selecting the same value from Head and CmpBB.
220// This means that no if-conversion is required when merging CmpBB into Head.
221bool SSACCmpConv::trivialTailPHIs() {
222 for (auto &I : *Tail) {
223 if (!I.isPHI())
224 break;
225 unsigned HeadReg = 0, CmpBBReg = 0;
226 // PHI operands come in (VReg, MBB) pairs.
227 for (unsigned oi = 1, oe = I.getNumOperands(); oi != oe; oi += 2) {
228 MachineBasicBlock *MBB = I.getOperand(i: oi + 1).getMBB();
229 Register Reg = lookThroughCopies(Reg: I.getOperand(i: oi).getReg(), MRI);
230 if (MBB == Head) {
231 assert((!HeadReg || HeadReg == Reg) && "Inconsistent PHI operands");
232 HeadReg = Reg;
233 }
234 if (MBB == CmpBB) {
235 assert((!CmpBBReg || CmpBBReg == Reg) && "Inconsistent PHI operands");
236 CmpBBReg = Reg;
237 }
238 }
239 if (HeadReg != CmpBBReg)
240 return false;
241 }
242 return true;
243}
244
245// Assuming that trivialTailPHIs() is true, update the Tail PHIs by simply
246// removing the CmpBB operands. The Head operands will be identical.
247void SSACCmpConv::updateTailPHIs() {
248 for (auto &I : *Tail) {
249 if (!I.isPHI())
250 break;
251 // I is a PHI. It can have multiple entries for CmpBB.
252 for (unsigned oi = I.getNumOperands(); oi > 2; oi -= 2) {
253 // PHI operands are (Reg, MBB) at (oi-2, oi-1).
254 if (I.getOperand(i: oi - 1).getMBB() == CmpBB) {
255 I.removeOperand(OpNo: oi - 1);
256 I.removeOperand(OpNo: oi - 2);
257 }
258 }
259 }
260}
261
262// This pass runs before the AArch64DeadRegisterDefinitions pass, so compares
263// are still writing virtual registers without any uses.
264bool SSACCmpConv::isDeadDef(unsigned DstReg) {
265 // Writes to the zero register are dead.
266 if (DstReg == AArch64::WZR || DstReg == AArch64::XZR)
267 return true;
268 if (!Register::isVirtualRegister(Reg: DstReg))
269 return false;
270 // A virtual register def without any uses will be marked dead later, and
271 // eventually replaced by the zero register.
272 return MRI->use_nodbg_empty(RegNo: DstReg);
273}
274
275// Parse a condition code returned by analyzeBranch, and compute the CondCode
276// corresponding to TBB.
277// Return
278static bool parseCond(ArrayRef<MachineOperand> Cond, AArch64CC::CondCode &CC) {
279 // A normal br.cond simply has the condition code.
280 if (Cond[0].getImm() != -1) {
281 assert(Cond.size() == 1 && "Unknown Cond array format");
282 CC = (AArch64CC::CondCode)(int)Cond[0].getImm();
283 return true;
284 }
285 // For tbz and cbz instruction, the opcode is next.
286 switch (Cond[1].getImm()) {
287 default:
288 // This includes tbz / tbnz branches which can't be converted to
289 // ccmp + br.cond.
290 return false;
291 case AArch64::CBZW:
292 case AArch64::CBZX:
293 assert(Cond.size() == 3 && "Unknown Cond array format");
294 CC = AArch64CC::EQ;
295 return true;
296 case AArch64::CBNZW:
297 case AArch64::CBNZX:
298 assert(Cond.size() == 3 && "Unknown Cond array format");
299 CC = AArch64CC::NE;
300 return true;
301
302 // For CB, cond is { -1, Opcode, CC, Op0, Op1 }
303 case AArch64::CBWPri:
304 case AArch64::CBXPri:
305 case AArch64::CBWPrr:
306 case AArch64::CBXPrr:
307 assert(Cond.size() == 5 && "Unknown Cond array format");
308 // Pseudos using standard 4bit Arm condition codes.
309 CC = static_cast<AArch64CC::CondCode>(Cond[2].getImm());
310 return true;
311
312 // For CBB and CBH, cond is { -1, Opcode, CC, Op0, Op1, Ext0, Ext1 }
313 case AArch64::CBBAssertExt:
314 case AArch64::CBHAssertExt:
315 assert(Cond.size() == 7 && "Unknown Cond array format");
316 // Pseudos using standard 4bit Arm condition codes.
317 CC = static_cast<AArch64CC::CondCode>(Cond[2].getImm());
318 return true;
319 }
320}
321
322MachineInstr *SSACCmpConv::findConvertibleCompare(MachineBasicBlock *MBB) {
323 MachineBasicBlock::iterator I = MBB->getFirstTerminator();
324 if (I == MBB->end())
325 return nullptr;
326 // The terminator must be controlled by the flags.
327 if (!I->readsRegister(Reg: AArch64::NZCV, /*TRI=*/nullptr)) {
328 switch (I->getOpcode()) {
329 // These can be converted into a ccmp against #0.
330 case AArch64::CBZW:
331 case AArch64::CBZX:
332 case AArch64::CBNZW:
333 case AArch64::CBNZX:
334 // These can be converted into a ccmp against a register.
335 case AArch64::CBWPrr:
336 case AArch64::CBXPrr:
337 return &*I;
338 // CB encodes a uimm6, ccmp wants a uimm5 so we have to check if the
339 // immediate fits.
340 case AArch64::CBWPri:
341 case AArch64::CBXPri: {
342 assert(I->getOperand(2).isImm() && "Expected immediate operand");
343 if (!isUInt<5>(x: I->getOperand(i: 2).getImm())) {
344 LLVM_DEBUG(dbgs() << "Immediate out of range for ccmp: " << *I);
345 ++NumImmRangeRejs;
346 return nullptr;
347 }
348 return &*I;
349 }
350 // Check if any of the operands would need zero- or sign-extension. If so,
351 // bail out
352 case AArch64::CBBAssertExt:
353 case AArch64::CBHAssertExt: {
354 assert(I->getOperand(4).isImm() && "Expected immediate operand");
355 assert(I->getOperand(5).isImm() && "Expected immediate operand");
356 if (I->getOperand(i: 4).getImm() != AArch64_AM::InvalidShiftExtend ||
357 I->getOperand(i: 5).getImm() != AArch64_AM::InvalidShiftExtend) {
358 LLVM_DEBUG(dbgs() << "Folded extend can't be folded into ccmp: " << *I);
359 ++NumFoldedExtRejs;
360 return nullptr;
361 }
362 return &*I;
363 }
364 }
365 ++NumCmpTermRejs;
366 LLVM_DEBUG(dbgs() << "Flags not used by terminator: " << *I);
367 return nullptr;
368 }
369
370 // Now find the instruction controlling the terminator.
371 for (MachineBasicBlock::iterator B = MBB->begin(); I != B;) {
372 I = prev_nodbg(It: I, Begin: MBB->begin());
373 assert(!I->isTerminator() && "Spurious terminator");
374 switch (I->getOpcode()) {
375 // cmp is an alias for subs with a dead destination register.
376 case AArch64::SUBSWri:
377 case AArch64::SUBSXri:
378 // cmn is an alias for adds with a dead destination register.
379 case AArch64::ADDSWri:
380 case AArch64::ADDSXri:
381 // Check that the immediate operand is within range, ccmp wants a uimm5.
382 // Rd = SUBSri Rn, imm, shift
383 if (I->getOperand(i: 3).getImm() || !isUInt<5>(x: I->getOperand(i: 2).getImm())) {
384 LLVM_DEBUG(dbgs() << "Immediate out of range for ccmp: " << *I);
385 ++NumImmRangeRejs;
386 return nullptr;
387 }
388 [[fallthrough]];
389 case AArch64::SUBSWrr:
390 case AArch64::SUBSXrr:
391 case AArch64::ADDSWrr:
392 case AArch64::ADDSXrr:
393 if (isDeadDef(DstReg: I->getOperand(i: 0).getReg()))
394 return &*I;
395 LLVM_DEBUG(dbgs() << "Can't convert compare with live destination: "
396 << *I);
397 ++NumLiveDstRejs;
398 return nullptr;
399 case AArch64::FCMPSrr:
400 case AArch64::FCMPDrr:
401 case AArch64::FCMPESrr:
402 case AArch64::FCMPEDrr:
403 return &*I;
404 }
405
406 // Check for flag reads and clobbers.
407 PhysRegInfo PRI = AnalyzePhysRegInBundle(MI: *I, Reg: AArch64::NZCV, TRI);
408
409 if (PRI.Read) {
410 // The ccmp doesn't produce exactly the same flags as the original
411 // compare, so reject the transform if there are uses of the flags
412 // besides the terminators.
413 LLVM_DEBUG(dbgs() << "Can't create ccmp with multiple uses: " << *I);
414 ++NumMultNZCVUses;
415 return nullptr;
416 }
417
418 if (PRI.Defined || PRI.Clobbered) {
419 LLVM_DEBUG(dbgs() << "Not convertible compare: " << *I);
420 ++NumUnknNZCVDefs;
421 return nullptr;
422 }
423 }
424 LLVM_DEBUG(dbgs() << "Flags not defined in " << printMBBReference(*MBB)
425 << '\n');
426 return nullptr;
427}
428
429/// Determine if all the instructions in MBB can safely
430/// be speculated. The terminators are not considered.
431///
432/// Only CmpMI is allowed to clobber the flags.
433///
434bool SSACCmpConv::canSpeculateInstrs(MachineBasicBlock *MBB,
435 const MachineInstr *CmpMI) {
436 // Reject any live-in physregs. It's probably NZCV/EFLAGS, and very hard to
437 // get right.
438 if (!MBB->livein_empty()) {
439 LLVM_DEBUG(dbgs() << printMBBReference(*MBB) << " has live-ins.\n");
440 return false;
441 }
442
443 const AArch64Options &CLOpts =
444 MF->getSubtarget<AArch64Subtarget>().getCLOpts();
445 unsigned InstrCount = 0;
446
447 // Check all instructions, except the terminators. It is assumed that
448 // terminators never have side effects or define any used register values.
449 for (auto &I : make_range(x: MBB->begin(), y: MBB->getFirstTerminator())) {
450 if (I.isDebugInstr())
451 continue;
452
453 if (++InstrCount > CLOpts.ccmp_limit && !CLOpts.stress_ccmp) {
454 LLVM_DEBUG(dbgs() << printMBBReference(*MBB) << " has more than "
455 << CLOpts.ccmp_limit << " instructions.\n");
456 return false;
457 }
458
459 // There shouldn't normally be any phis in a single-predecessor block.
460 if (I.isPHI()) {
461 LLVM_DEBUG(dbgs() << "Can't hoist: " << I);
462 return false;
463 }
464
465 // Don't speculate loads. Note that it may be possible and desirable to
466 // speculate GOT or constant pool loads that are guaranteed not to trap,
467 // but we don't support that for now.
468 if (I.mayLoad()) {
469 LLVM_DEBUG(dbgs() << "Won't speculate load: " << I);
470 return false;
471 }
472
473 // We never speculate stores, so an AA pointer isn't necessary.
474 bool DontMoveAcrossStore = true;
475 if (!I.isSafeToMove(SawStore&: DontMoveAcrossStore)) {
476 LLVM_DEBUG(dbgs() << "Can't speculate: " << I);
477 return false;
478 }
479
480 // Only CmpMI is allowed to clobber the flags.
481 if (&I != CmpMI && I.modifiesRegister(Reg: AArch64::NZCV, TRI)) {
482 LLVM_DEBUG(dbgs() << "Clobbers flags: " << I);
483 return false;
484 }
485 }
486 return true;
487}
488
489/// Analyze the sub-cfg rooted in MBB, and return true if it is a potential
490/// candidate for cmp-conversion. Fill out the internal state.
491///
492bool SSACCmpConv::canConvert(MachineBasicBlock *MBB) {
493 Head = MBB;
494 Tail = CmpBB = nullptr;
495
496 if (Head->succ_size() != 2)
497 return false;
498 MachineBasicBlock *Succ0 = Head->succ_begin()[0];
499 MachineBasicBlock *Succ1 = Head->succ_begin()[1];
500
501 // CmpBB can only have a single predecessor. Tail is allowed many.
502 if (Succ0->pred_size() != 1)
503 std::swap(a&: Succ0, b&: Succ1);
504
505 // Succ0 is our candidate for CmpBB.
506 if (Succ0->pred_size() != 1 || Succ0->succ_size() != 2)
507 return false;
508
509 CmpBB = Succ0;
510 Tail = Succ1;
511
512 if (!CmpBB->isSuccessor(MBB: Tail))
513 return false;
514
515 // The CFG topology checks out.
516 LLVM_DEBUG(dbgs() << "\nTriangle: " << printMBBReference(*Head) << " -> "
517 << printMBBReference(*CmpBB) << " -> "
518 << printMBBReference(*Tail) << '\n');
519 ++NumConsidered;
520
521 // Tail is allowed to have many predecessors, but we can't handle PHIs yet.
522 //
523 // FIXME: Real PHIs could be if-converted as long as the CmpBB values are
524 // defined before The CmpBB cmp clobbers the flags. Alternatively, it should
525 // always be safe to sink the ccmp down to immediately before the CmpBB
526 // terminators.
527 if (!trivialTailPHIs()) {
528 LLVM_DEBUG(dbgs() << "Can't handle phis in Tail.\n");
529 ++NumPhiRejs;
530 return false;
531 }
532
533 if (!Tail->livein_empty()) {
534 LLVM_DEBUG(dbgs() << "Can't handle live-in physregs in Tail.\n");
535 ++NumPhysRejs;
536 return false;
537 }
538
539 // CmpBB should never have PHIs since Head is its only predecessor.
540 // FIXME: Clean them up if it happens.
541 if (!CmpBB->empty() && CmpBB->front().isPHI()) {
542 LLVM_DEBUG(dbgs() << "Can't handle phis in CmpBB.\n");
543 ++NumPhi2Rejs;
544 return false;
545 }
546
547 if (!CmpBB->livein_empty()) {
548 LLVM_DEBUG(dbgs() << "Can't handle live-in physregs in CmpBB.\n");
549 ++NumPhysRejs;
550 return false;
551 }
552
553 // The branch we're looking to eliminate must be analyzable.
554 HeadCond.clear();
555 MachineBasicBlock *TBB = nullptr, *FBB = nullptr;
556 if (TII->analyzeBranch(MBB&: *Head, TBB, FBB, Cond&: HeadCond)) {
557 LLVM_DEBUG(dbgs() << "Head branch not analyzable.\n");
558 ++NumHeadBranchRejs;
559 return false;
560 }
561
562 // This is weird, probably some sort of degenerate CFG, or an edge to a
563 // landing pad.
564 if (!TBB || HeadCond.empty()) {
565 LLVM_DEBUG(
566 dbgs() << "analyzeBranch didn't find conditional branch in Head.\n");
567 ++NumHeadBranchRejs;
568 return false;
569 }
570
571 if (!parseCond(Cond: HeadCond, CC&: HeadCmpBBCC)) {
572 LLVM_DEBUG(dbgs() << "Unsupported branch type on Head\n");
573 ++NumHeadBranchRejs;
574 return false;
575 }
576
577 // Make sure the branch direction is right.
578 if (TBB != CmpBB) {
579 assert(TBB == Tail && "Unexpected TBB");
580 HeadCmpBBCC = AArch64CC::getInvertedCondCode(Code: HeadCmpBBCC);
581 }
582
583 CmpBBCond.clear();
584 TBB = FBB = nullptr;
585 if (TII->analyzeBranch(MBB&: *CmpBB, TBB, FBB, Cond&: CmpBBCond)) {
586 LLVM_DEBUG(dbgs() << "CmpBB branch not analyzable.\n");
587 ++NumCmpBranchRejs;
588 return false;
589 }
590
591 if (!TBB || CmpBBCond.empty()) {
592 LLVM_DEBUG(
593 dbgs() << "analyzeBranch didn't find conditional branch in CmpBB.\n");
594 ++NumCmpBranchRejs;
595 return false;
596 }
597
598 if (!parseCond(Cond: CmpBBCond, CC&: CmpBBTailCC)) {
599 LLVM_DEBUG(dbgs() << "Unsupported branch type on CmpBB\n");
600 ++NumCmpBranchRejs;
601 return false;
602 }
603
604 if (TBB != Tail)
605 CmpBBTailCC = AArch64CC::getInvertedCondCode(Code: CmpBBTailCC);
606
607 LLVM_DEBUG(dbgs() << "Head->CmpBB on "
608 << AArch64CC::getCondCodeName(HeadCmpBBCC)
609 << ", CmpBB->Tail on "
610 << AArch64CC::getCondCodeName(CmpBBTailCC) << '\n');
611
612 CmpMI = findConvertibleCompare(MBB: CmpBB);
613 if (!CmpMI)
614 return false;
615
616 if (!canSpeculateInstrs(MBB: CmpBB, CmpMI)) {
617 ++NumSpeculateRejs;
618 return false;
619 }
620 return true;
621}
622
623void SSACCmpConv::convert(SmallVectorImpl<MachineBasicBlock *> &RemovedBlocks) {
624 LLVM_DEBUG(dbgs() << "Merging " << printMBBReference(*CmpBB) << " into "
625 << printMBBReference(*Head) << ":\n"
626 << *CmpBB);
627
628 // All CmpBB instructions are moved into Head, and CmpBB is deleted.
629 // Update the CFG first.
630 updateTailPHIs();
631
632 // Save successor probabilities before removing CmpBB and Tail from their
633 // parents.
634 BranchProbability Head2CmpBB = MBPI->getEdgeProbability(Src: Head, Dst: CmpBB);
635 BranchProbability CmpBB2Tail = MBPI->getEdgeProbability(Src: CmpBB, Dst: Tail);
636
637 Head->removeSuccessor(Succ: CmpBB);
638 CmpBB->removeSuccessor(Succ: Tail);
639
640 // If Head and CmpBB had successor probabilities, update the probabilities to
641 // reflect the ccmp-conversion.
642 if (Head->hasSuccessorProbabilities() && CmpBB->hasSuccessorProbabilities()) {
643
644 // Head is allowed two successors. We've removed CmpBB, so the remaining
645 // successor is Tail. We need to increase the successor probability for
646 // Tail to account for the CmpBB path we removed.
647 //
648 // Pr(Tail|Head) += Pr(CmpBB|Head) * Pr(Tail|CmpBB).
649 assert(*Head->succ_begin() == Tail && "Head successor is not Tail");
650 BranchProbability Head2Tail = MBPI->getEdgeProbability(Src: Head, Dst: Tail);
651 Head->setSuccProbability(I: Head->succ_begin(),
652 Prob: Head2Tail + Head2CmpBB * CmpBB2Tail);
653
654 // We will transfer successors of CmpBB to Head in a moment without
655 // normalizing the successor probabilities. Set the successor probabilities
656 // before doing so.
657 //
658 // Pr(I|Head) = Pr(CmpBB|Head) * Pr(I|CmpBB).
659 for (auto I = CmpBB->succ_begin(), E = CmpBB->succ_end(); I != E; ++I) {
660 BranchProbability CmpBB2I = MBPI->getEdgeProbability(Src: CmpBB, Dst: *I);
661 CmpBB->setSuccProbability(I, Prob: Head2CmpBB * CmpBB2I);
662 }
663 }
664
665 Head->transferSuccessorsAndUpdatePHIs(FromMBB: CmpBB);
666 DebugLoc TermDL = Head->getFirstTerminator()->getDebugLoc();
667 TII->removeBranch(MBB&: *Head);
668
669 // If the Head terminator was one of the cb / cbz / tbz branches with built-in
670 // compare, we need to insert an explicit compare instruction in its place.
671 if (HeadCond[0].getImm() == -1) {
672 ++NumCompBranches;
673 TII->insertCmpForCondBr(MBB&: *Head, MI: Head->end(), DL: TermDL, Cond: HeadCond);
674 }
675
676 Head->splice(Where: Head->end(), Other: CmpBB, From: CmpBB->begin(), To: CmpBB->end());
677
678 // Now replace CmpMI with a ccmp instruction that also considers the incoming
679 // flags.
680 unsigned Opc = 0;
681 unsigned FirstOp = 1; // First CmpMI operand to copy.
682 bool isZBranch = false; // CmpMI is a cbz/cbnz instruction.
683 switch (CmpMI->getOpcode()) {
684 default:
685 llvm_unreachable("Unknown compare opcode");
686 case AArch64::SUBSWri: Opc = AArch64::CCMPWi; break;
687 case AArch64::SUBSWrr: Opc = AArch64::CCMPWr; break;
688 case AArch64::SUBSXri: Opc = AArch64::CCMPXi; break;
689 case AArch64::SUBSXrr: Opc = AArch64::CCMPXr; break;
690 case AArch64::ADDSWri: Opc = AArch64::CCMNWi; break;
691 case AArch64::ADDSWrr: Opc = AArch64::CCMNWr; break;
692 case AArch64::ADDSXri: Opc = AArch64::CCMNXi; break;
693 case AArch64::ADDSXrr: Opc = AArch64::CCMNXr; break;
694 case AArch64::FCMPSrr: Opc = AArch64::FCCMPSrr; FirstOp = 0; break;
695 case AArch64::FCMPDrr: Opc = AArch64::FCCMPDrr; FirstOp = 0; break;
696 case AArch64::FCMPESrr: Opc = AArch64::FCCMPESrr; FirstOp = 0; break;
697 case AArch64::FCMPEDrr: Opc = AArch64::FCCMPEDrr; FirstOp = 0; break;
698 case AArch64::CBZW:
699 case AArch64::CBNZW:
700 Opc = AArch64::CCMPWi;
701 FirstOp = 0;
702 isZBranch = true;
703 break;
704 case AArch64::CBZX:
705 case AArch64::CBNZX:
706 Opc = AArch64::CCMPXi;
707 FirstOp = 0;
708 isZBranch = true;
709 break;
710 case AArch64::CBWPri:
711 Opc = AArch64::CCMPWi;
712 FirstOp = 1;
713 break;
714 case AArch64::CBXPri:
715 Opc = AArch64::CCMPXi;
716 FirstOp = 1;
717 break;
718 case AArch64::CBWPrr:
719 case AArch64::CBBAssertExt:
720 case AArch64::CBHAssertExt:
721 Opc = AArch64::CCMPWr;
722 FirstOp = 1;
723 break;
724 case AArch64::CBXPrr:
725 Opc = AArch64::CCMPXr;
726 FirstOp = 1;
727 break;
728 }
729
730 // The ccmp instruction should set the flags according to the comparison when
731 // Head would have branched to CmpBB.
732 // The NZCV immediate operand should provide flags for the case where Head
733 // would have branched to Tail. These flags should cause the new Head
734 // terminator to branch to tail.
735 unsigned NZCV = AArch64CC::getNZCVToSatisfyCondCode(Code: CmpBBTailCC);
736 const MCInstrDesc &MCID = TII->get(Opcode: Opc);
737 MRI->constrainRegClass(Reg: CmpMI->getOperand(i: FirstOp).getReg(),
738 RC: TII->getRegClass(MCID, OpNum: 0));
739 if (CmpMI->getOperand(i: FirstOp + 1).isReg())
740 MRI->constrainRegClass(Reg: CmpMI->getOperand(i: FirstOp + 1).getReg(),
741 RC: TII->getRegClass(MCID, OpNum: 1));
742 MachineInstrBuilder MIB = BuildMI(BB&: *Head, I: CmpMI, MIMD: CmpMI->getDebugLoc(), MCID)
743 .add(MO: CmpMI->getOperand(i: FirstOp)); // Register Rn
744 if (isZBranch)
745 MIB.addImm(Val: 0); // cbz/cbnz Rn -> ccmp Rn, #0
746 else
747 MIB.add(MO: CmpMI->getOperand(i: FirstOp + 1)); // Register Rm / Immediate
748 MIB.addImm(Val: NZCV).addImm(Val: HeadCmpBBCC);
749
750 // If CmpMI was a terminator, we need a new conditional branch to replace it.
751 // This now becomes a Head terminator.
752 if (CmpMI->isTerminator()) {
753 AArch64CC::CondCode CC;
754 switch (CmpMI->getOpcode()) {
755 default:
756 llvm_unreachable("Unexpected CMP opcode");
757 case AArch64::CBZW:
758 case AArch64::CBZX:
759 CC = AArch64CC::EQ;
760 break;
761 case AArch64::CBNZW:
762 case AArch64::CBNZX:
763 CC = AArch64CC::NE;
764 break;
765 case AArch64::CBWPri:
766 case AArch64::CBXPri:
767 case AArch64::CBBAssertExt:
768 case AArch64::CBHAssertExt:
769 case AArch64::CBWPrr:
770 case AArch64::CBXPrr:
771 CC = static_cast<AArch64CC::CondCode>(CmpMI->getOperand(i: 0).getImm());
772 break;
773 }
774 MachineBasicBlock *BrTarget = TII->getBranchDestBlock(MI: *CmpMI);
775 BuildMI(BB&: *Head, I: CmpMI, MIMD: CmpMI->getDebugLoc(), MCID: TII->get(Opcode: AArch64::Bcc))
776 .addImm(Val: CC)
777 .addMBB(MBB: BrTarget);
778 }
779 CmpMI->eraseFromParent();
780 Head->updateTerminator(PreviousLayoutSuccessor: CmpBB->getNextNode());
781
782 RemovedBlocks.push_back(Elt: CmpBB);
783 LLVM_DEBUG(dbgs() << "Result:\n" << *Head);
784 ++NumConverted;
785}
786
787int SSACCmpConv::expectedCodeSizeDelta() const {
788 int delta = 0;
789 // If the Head terminator was one of the cb / cbz / tbz branches with built-in
790 // compare, we need to insert an explicit compare instruction in its place
791 // plus a branch instruction.
792 if (HeadCond[0].getImm() == -1) {
793 switch (HeadCond[1].getImm()) {
794 case AArch64::CBZW:
795 case AArch64::CBNZW:
796 case AArch64::CBZX:
797 case AArch64::CBNZX:
798 case AArch64::CBWPri:
799 case AArch64::CBXPri:
800 case AArch64::CBWPrr:
801 case AArch64::CBXPrr:
802 // Therefore delta += 1
803 delta = 1;
804 break;
805 // The cbb / cbh case might need a zero- or sign-extension, costing another
806 // instruction
807 case AArch64::CBBAssertExt:
808 case AArch64::CBHAssertExt:
809 assert(HeadCond[5].isImm() && "Expected immediate operand");
810 delta = (HeadCond[5].getImm() != AArch64_AM::InvalidShiftExtend ? 2 : 1);
811 break;
812 default:
813 llvm_unreachable("Cannot convert Head branch");
814 }
815 }
816 // If the Cmp terminator was one of the cb / cbz / tbz branches with
817 // built-in compare, it will be turned into a compare instruction
818 // into Head, but we do not save any instruction.
819 // Otherwise, we save the branch instruction.
820 switch (CmpMI->getOpcode()) {
821 default:
822 --delta;
823 break;
824 case AArch64::CBZW:
825 case AArch64::CBNZW:
826 case AArch64::CBZX:
827 case AArch64::CBNZX:
828 case AArch64::CBWPri:
829 case AArch64::CBXPri:
830 case AArch64::CBBAssertExt:
831 case AArch64::CBHAssertExt:
832 case AArch64::CBWPrr:
833 case AArch64::CBXPrr:
834 break;
835 }
836 return delta;
837}
838
839//===----------------------------------------------------------------------===//
840// AArch64ConditionalCompares Pass
841//===----------------------------------------------------------------------===//
842
843namespace {
844class AArch64ConditionalComparesImpl {
845 const MachineBranchProbabilityInfo *MBPI;
846 const TargetInstrInfo *TII;
847 const TargetRegisterInfo *TRI;
848 const AArch64Subtarget *STI;
849 // Does the proceeded function has Oz attribute.
850 bool MinSize;
851 MachineRegisterInfo *MRI;
852 MachineDominatorTree *DomTree;
853 MachineLoopInfo *Loops;
854 MachineTraceMetrics *Traces;
855 MachineTraceMetrics::Ensemble *MinInstr;
856 SSACCmpConv CmpConv;
857
858public:
859 AArch64ConditionalComparesImpl(const MachineBranchProbabilityInfo *MBPI,
860 MachineDominatorTree *DomTree,
861 MachineLoopInfo *Loops,
862 MachineTraceMetrics *Traces)
863 : MBPI(MBPI), DomTree(DomTree), Loops(Loops), Traces(Traces) {}
864
865 bool run(MachineFunction &MF);
866
867private:
868 bool tryConvert(MachineBasicBlock *);
869 void updateDomTree(ArrayRef<MachineBasicBlock *> Removed);
870 void updateLoops(ArrayRef<MachineBasicBlock *> Removed);
871 void invalidateTraces();
872 bool shouldConvert();
873};
874
875class AArch64ConditionalComparesLegacy : public MachineFunctionPass {
876public:
877 static char ID;
878 AArch64ConditionalComparesLegacy() : MachineFunctionPass(ID) {
879 initializeAArch64ConditionalComparesLegacyPass(
880 *PassRegistry::getPassRegistry());
881 }
882 void getAnalysisUsage(AnalysisUsage &AU) const override;
883 bool runOnMachineFunction(MachineFunction &MF) override;
884 StringRef getPassName() const override {
885 return "AArch64 Conditional Compares";
886 }
887};
888} // end anonymous namespace
889
890char AArch64ConditionalComparesLegacy::ID = 0;
891
892INITIALIZE_PASS_BEGIN(AArch64ConditionalComparesLegacy, "aarch64-ccmp",
893 "AArch64 CCMP Pass", false, false)
894INITIALIZE_PASS_DEPENDENCY(MachineBranchProbabilityInfoWrapperPass)
895INITIALIZE_PASS_DEPENDENCY(MachineDominatorTreeWrapperPass)
896INITIALIZE_PASS_DEPENDENCY(MachineTraceMetricsWrapperPass)
897INITIALIZE_PASS_END(AArch64ConditionalComparesLegacy, "aarch64-ccmp",
898 "AArch64 CCMP Pass", false, false)
899
900FunctionPass *llvm::createAArch64ConditionalCompares() {
901 return new AArch64ConditionalComparesLegacy();
902}
903
904void AArch64ConditionalComparesLegacy::getAnalysisUsage(
905 AnalysisUsage &AU) const {
906 AU.addRequired<MachineBranchProbabilityInfoWrapperPass>();
907 AU.addRequired<MachineDominatorTreeWrapperPass>();
908 AU.addPreserved<MachineDominatorTreeWrapperPass>();
909 AU.addRequired<MachineLoopInfoWrapperPass>();
910 AU.addPreserved<MachineLoopInfoWrapperPass>();
911 AU.addRequired<MachineTraceMetricsWrapperPass>();
912 AU.addPreserved<MachineTraceMetricsWrapperPass>();
913 MachineFunctionPass::getAnalysisUsage(AU);
914}
915
916/// Update the dominator tree after if-conversion erased some blocks.
917void AArch64ConditionalComparesImpl::updateDomTree(
918 ArrayRef<MachineBasicBlock *> Removed) {
919 // convert() removes CmpBB which was previously dominated by Head.
920 // CmpBB children should be transferred to Head.
921 MachineDomTreeNode *HeadNode = DomTree->getNode(BB: CmpConv.Head);
922 for (MachineBasicBlock *RemovedMBB : Removed) {
923 MachineDomTreeNode *Node = DomTree->getNode(BB: RemovedMBB);
924 assert(Node != HeadNode && "Cannot erase the head node");
925 assert(Node->getIDom() == HeadNode && "CmpBB should be dominated by Head");
926 while (!Node->isLeaf())
927 DomTree->changeImmediateDominator(N: *Node->begin(), NewIDom: HeadNode);
928 DomTree->eraseNode(BB: RemovedMBB);
929 }
930}
931
932/// Update LoopInfo after if-conversion.
933void AArch64ConditionalComparesImpl::updateLoops(
934 ArrayRef<MachineBasicBlock *> Removed) {
935 if (!Loops)
936 return;
937 for (MachineBasicBlock *RemovedMBB : Removed)
938 Loops->removeBlock(BB: RemovedMBB);
939}
940
941/// Invalidate MachineTraceMetrics before if-conversion.
942void AArch64ConditionalComparesImpl::invalidateTraces() {
943 Traces->invalidate(MBB: CmpConv.Head);
944 Traces->invalidate(MBB: CmpConv.CmpBB);
945}
946
947/// Apply cost model and heuristics to the if-conversion in IfConv.
948/// Return true if the conversion is a good idea.
949///
950bool AArch64ConditionalComparesImpl::shouldConvert() {
951 // Stress testing mode disables all cost considerations.
952 if (STI->getCLOpts().stress_ccmp)
953 return true;
954 if (!MinInstr)
955 MinInstr = Traces->getEnsemble(MachineTraceStrategy::TS_MinInstrCount);
956
957 // Head dominates CmpBB, so it is always included in its trace.
958 MachineTraceMetrics::Trace Trace = MinInstr->getTrace(MBB: CmpConv.CmpBB);
959
960 // If code size is the main concern
961 if (MinSize) {
962 int CodeSizeDelta = CmpConv.expectedCodeSizeDelta();
963 LLVM_DEBUG(dbgs() << "Code size delta: " << CodeSizeDelta << '\n');
964 // If we are minimizing the code size, do the conversion whatever
965 // the cost is.
966 if (CodeSizeDelta < 0)
967 return true;
968 if (CodeSizeDelta > 0) {
969 LLVM_DEBUG(dbgs() << "Code size is increasing, give up on this one.\n");
970 return false;
971 }
972 // CodeSizeDelta == 0, continue with the regular heuristics
973 }
974
975 // Heuristic: The compare conversion delays the execution of the branch
976 // instruction because we must wait for the inputs to the second compare as
977 // well. The branch has no dependent instructions, but delaying it increases
978 // the cost of a misprediction.
979 //
980 // Set a limit on the delay we will accept.
981 unsigned DelayLimit = STI->getMispredictionPenalty() * 3 / 4;
982
983 // Instruction depths can be computed for all trace instructions above CmpBB.
984 unsigned HeadDepth =
985 Trace.getInstrCycles(MI: *CmpConv.Head->getFirstTerminator()).Depth;
986 unsigned CmpBBDepth =
987 Trace.getInstrCycles(MI: *CmpConv.CmpBB->getFirstTerminator()).Depth;
988 LLVM_DEBUG(dbgs() << "Head depth: " << HeadDepth
989 << "\nCmpBB depth: " << CmpBBDepth << '\n');
990 if (CmpBBDepth > HeadDepth + DelayLimit) {
991 LLVM_DEBUG(dbgs() << "Branch delay would be larger than " << DelayLimit
992 << " cycles.\n");
993 return false;
994 }
995
996 // Check the resource depth at the bottom of CmpBB - these instructions will
997 // be speculated.
998 unsigned ResDepth = Trace.getResourceDepth(Bottom: true);
999 LLVM_DEBUG(dbgs() << "Resources: " << ResDepth << '\n');
1000
1001 // Heuristic: The speculatively executed instructions must all be able to
1002 // merge into the Head block. The Head critical path should dominate the
1003 // resource cost of the speculated instructions.
1004 if (ResDepth > HeadDepth) {
1005 LLVM_DEBUG(dbgs() << "Too many instructions to speculate.\n");
1006 return false;
1007 }
1008 return true;
1009}
1010
1011bool AArch64ConditionalComparesImpl::tryConvert(MachineBasicBlock *MBB) {
1012 bool Changed = false;
1013 while (CmpConv.canConvert(MBB) && shouldConvert()) {
1014 invalidateTraces();
1015 SmallVector<MachineBasicBlock *, 4> RemovedBlocks;
1016 CmpConv.convert(RemovedBlocks);
1017 Changed = true;
1018 updateDomTree(Removed: RemovedBlocks);
1019 updateLoops(Removed: RemovedBlocks);
1020 for (MachineBasicBlock *MBB : RemovedBlocks)
1021 MBB->eraseFromParent();
1022 }
1023 return Changed;
1024}
1025
1026bool AArch64ConditionalComparesImpl::run(MachineFunction &MF) {
1027 LLVM_DEBUG(dbgs() << "********** AArch64 Conditional Compares **********\n"
1028 << "********** Function: " << MF.getName() << '\n');
1029
1030 TII = MF.getSubtarget().getInstrInfo();
1031 TRI = MF.getSubtarget().getRegisterInfo();
1032 STI = &MF.getSubtarget<AArch64Subtarget>();
1033 MRI = &MF.getRegInfo();
1034 MinInstr = nullptr;
1035 MinSize = MF.getFunction().hasMinSize();
1036
1037 bool Changed = false;
1038 CmpConv.runOnMachineFunction(MF, MBPI);
1039
1040 // Visit blocks in dominator tree pre-order. The pre-order enables multiple
1041 // cmp-conversions from the same head block.
1042 // Note that updateDomTree() modifies the children of the DomTree node
1043 // currently being visited. The df_iterator supports that; it doesn't look at
1044 // child_begin() / child_end() until after a node has been visited.
1045 for (auto *I : depth_first(G: DomTree))
1046 if (tryConvert(MBB: I->getBlock()))
1047 Changed = true;
1048
1049 return Changed;
1050}
1051
1052bool AArch64ConditionalComparesLegacy::runOnMachineFunction(
1053 MachineFunction &MF) {
1054 if (skipFunction(F: MF.getFunction()))
1055 return false;
1056
1057 const MachineBranchProbabilityInfo *MBPI =
1058 &getAnalysis<MachineBranchProbabilityInfoWrapperPass>().getMBPI();
1059 MachineDominatorTree *DomTree =
1060 &getAnalysis<MachineDominatorTreeWrapperPass>().getDomTree();
1061 MachineLoopInfo *Loops = &getAnalysis<MachineLoopInfoWrapperPass>().getLI();
1062 MachineTraceMetrics *Traces =
1063 &getAnalysis<MachineTraceMetricsWrapperPass>().getMTM();
1064
1065 AArch64ConditionalComparesImpl Impl(MBPI, DomTree, Loops, Traces);
1066 return Impl.run(MF);
1067}
1068
1069PreservedAnalyses
1070AArch64ConditionalComparesPass::run(MachineFunction &MF,
1071 MachineFunctionAnalysisManager &MFAM) {
1072 const MachineBranchProbabilityInfo *MBPI =
1073 &MFAM.getResult<MachineBranchProbabilityAnalysis>(IR&: MF);
1074 MachineDominatorTree *DomTree =
1075 &MFAM.getResult<MachineDominatorTreeAnalysis>(IR&: MF);
1076 MachineLoopInfo *Loops = &MFAM.getResult<MachineLoopAnalysis>(IR&: MF);
1077 MachineTraceMetrics *Traces =
1078 &MFAM.getResult<MachineTraceMetricsAnalysis>(IR&: MF);
1079
1080 AArch64ConditionalComparesImpl Impl(MBPI, DomTree, Loops, Traces);
1081 bool Changed = Impl.run(MF);
1082 if (!Changed)
1083 return PreservedAnalyses::all();
1084
1085 PreservedAnalyses PA = getMachineFunctionPassPreservedAnalyses();
1086 PA.preserve<MachineDominatorTreeAnalysis>();
1087 PA.preserve<MachineLoopAnalysis>();
1088 PA.preserve<MachineTraceMetricsAnalysis>();
1089 return PA;
1090}
1091