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