1 //===-- ARM64ConditionalCompares.cpp --- CCMP formation for ARM64 ---------===//
3 // The LLVM Compiler Infrastructure
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
8 //===----------------------------------------------------------------------===//
10 // This file implements the ARM64ConditionalCompares pass which reduces
11 // branching and code size by using the conditional compare instructions CCMP,
14 // The CFG transformations for forming conditional compares are very similar to
15 // if-conversion, and this pass should run immediately before the early
16 // if-conversion pass.
18 //===----------------------------------------------------------------------===//
20 #define DEBUG_TYPE "arm64-ccmp"
22 #include "llvm/ADT/BitVector.h"
23 #include "llvm/ADT/DepthFirstIterator.h"
24 #include "llvm/ADT/SetVector.h"
25 #include "llvm/ADT/SmallPtrSet.h"
26 #include "llvm/ADT/SparseSet.h"
27 #include "llvm/ADT/Statistic.h"
28 #include "llvm/CodeGen/MachineBranchProbabilityInfo.h"
29 #include "llvm/CodeGen/MachineDominators.h"
30 #include "llvm/CodeGen/MachineFunction.h"
31 #include "llvm/CodeGen/MachineFunctionPass.h"
32 #include "llvm/CodeGen/MachineInstrBuilder.h"
33 #include "llvm/CodeGen/MachineLoopInfo.h"
34 #include "llvm/CodeGen/MachineRegisterInfo.h"
35 #include "llvm/CodeGen/MachineTraceMetrics.h"
36 #include "llvm/CodeGen/Passes.h"
37 #include "llvm/Support/CommandLine.h"
38 #include "llvm/Support/Debug.h"
39 #include "llvm/Support/raw_ostream.h"
40 #include "llvm/Target/TargetInstrInfo.h"
41 #include "llvm/Target/TargetRegisterInfo.h"
42 #include "llvm/Target/TargetSubtargetInfo.h"
46 // Absolute maximum number of instructions allowed per speculated block.
47 // This bypasses all other heuristics, so it should be set fairly high.
48 static cl::opt<unsigned> BlockInstrLimit(
49 "arm64-ccmp-limit", cl::init(30), cl::Hidden,
50 cl::desc("Maximum number of instructions per speculated block."));
52 // Stress testing mode - disable heuristics.
53 static cl::opt<bool> Stress("arm64-stress-ccmp", cl::Hidden,
54 cl::desc("Turn all knobs to 11"));
56 STATISTIC(NumConsidered, "Number of ccmps considered");
57 STATISTIC(NumPhiRejs, "Number of ccmps rejected (PHI)");
58 STATISTIC(NumPhysRejs, "Number of ccmps rejected (Physregs)");
59 STATISTIC(NumPhi2Rejs, "Number of ccmps rejected (PHI2)");
60 STATISTIC(NumHeadBranchRejs, "Number of ccmps rejected (Head branch)");
61 STATISTIC(NumCmpBranchRejs, "Number of ccmps rejected (CmpBB branch)");
62 STATISTIC(NumCmpTermRejs, "Number of ccmps rejected (CmpBB is cbz...)");
63 STATISTIC(NumImmRangeRejs, "Number of ccmps rejected (Imm out of range)");
64 STATISTIC(NumLiveDstRejs, "Number of ccmps rejected (Cmp dest live)");
65 STATISTIC(NumMultCPSRUses, "Number of ccmps rejected (CPSR used)");
66 STATISTIC(NumUnknCPSRDefs, "Number of ccmps rejected (CPSR def unknown)");
68 STATISTIC(NumSpeculateRejs, "Number of ccmps rejected (Can't speculate)");
70 STATISTIC(NumConverted, "Number of ccmp instructions created");
71 STATISTIC(NumCompBranches, "Number of cbz/cbnz branches converted");
73 //===----------------------------------------------------------------------===//
75 //===----------------------------------------------------------------------===//
77 // The SSACCmpConv class performs ccmp-conversion on SSA form machine code
78 // after determining if it is possible. The class contains no heuristics;
79 // external code should be used to determine when ccmp-conversion is a good
82 // CCmp-formation works on a CFG representing chained conditions, typically
83 // from C's short-circuit || and && operators:
85 // From: Head To: Head
95 // The Head block is terminated by a br.cond instruction, and the CmpBB block
96 // contains compare + br.cond. Tail must be a successor of both.
98 // The cmp-conversion turns the compare instruction in CmpBB into a conditional
99 // compare, and merges CmpBB into Head, speculatively executing its
100 // instructions. The ARM64 conditional compare instructions have an immediate
101 // operand that specifies the NZCV flag values when the condition is false and
102 // the compare isn't executed. This makes it possible to chain compares with
103 // different condition codes.
107 // if (a == 5 || b == 17)
124 // ccmp w1, #17, 4, ne ; 4 = nZcv
130 // The ccmp condition code is the one that would cause the Head terminator to
133 // FIXME: It should also be possible to speculate a block on the critical edge
134 // between Head and Tail, just like if-converting a diamond.
136 // FIXME: Handle PHIs in Tail by turning them into selects (if-conversion).
141 const TargetInstrInfo *TII;
142 const TargetRegisterInfo *TRI;
143 MachineRegisterInfo *MRI;
146 /// The first block containing a conditional branch, dominating everything
148 MachineBasicBlock *Head;
150 /// The block containing cmp+br.cond with a successor shared with Head.
151 MachineBasicBlock *CmpBB;
153 /// The common successor for Head and CmpBB.
154 MachineBasicBlock *Tail;
156 /// The compare instruction in CmpBB that can be converted to a ccmp.
160 /// The branch condition in Head as determined by AnalyzeBranch.
161 SmallVector<MachineOperand, 4> HeadCond;
163 /// The condition code that makes Head branch to CmpBB.
164 ARM64CC::CondCode HeadCmpBBCC;
166 /// The branch condition in CmpBB.
167 SmallVector<MachineOperand, 4> CmpBBCond;
169 /// The condition code that makes CmpBB branch to Tail.
170 ARM64CC::CondCode CmpBBTailCC;
172 /// Check if the Tail PHIs are trivially convertible.
173 bool trivialTailPHIs();
175 /// Remove CmpBB from the Tail PHIs.
176 void updateTailPHIs();
178 /// Check if an operand defining DstReg is dead.
179 bool isDeadDef(unsigned DstReg);
181 /// Find the compare instruction in MBB that controls the conditional branch.
182 /// Return NULL if a convertible instruction can't be found.
183 MachineInstr *findConvertibleCompare(MachineBasicBlock *MBB);
185 /// Return true if all non-terminator instructions in MBB can be safely
187 bool canSpeculateInstrs(MachineBasicBlock *MBB, const MachineInstr *CmpMI);
190 /// runOnMachineFunction - Initialize per-function data structures.
191 void runOnMachineFunction(MachineFunction &MF) {
193 TII = MF.getTarget().getInstrInfo();
194 TRI = MF.getTarget().getRegisterInfo();
195 MRI = &MF.getRegInfo();
198 /// If the sub-CFG headed by MBB can be cmp-converted, initialize the
199 /// internal state, and return true.
200 bool canConvert(MachineBasicBlock *MBB);
202 /// Cmo-convert the last block passed to canConvertCmp(), assuming
203 /// it is possible. Add any erased blocks to RemovedBlocks.
204 void convert(SmallVectorImpl<MachineBasicBlock *> &RemovedBlocks);
206 /// Return the expected code size delta if the conversion into a
207 /// conditional compare is performed.
208 int expectedCodeSizeDelta() const;
210 } // end anonymous namespace
212 // Check that all PHIs in Tail are selecting the same value from Head and CmpBB.
213 // This means that no if-conversion is required when merging CmpBB into Head.
214 bool SSACCmpConv::trivialTailPHIs() {
215 for (auto &I : *Tail) {
218 unsigned HeadReg = 0, CmpBBReg = 0;
219 // PHI operands come in (VReg, MBB) pairs.
220 for (unsigned oi = 1, oe = I.getNumOperands(); oi != oe; oi += 2) {
221 MachineBasicBlock *MBB = I.getOperand(oi + 1).getMBB();
222 unsigned Reg = I.getOperand(oi).getReg();
224 assert((!HeadReg || HeadReg == Reg) && "Inconsistent PHI operands");
228 assert((!CmpBBReg || CmpBBReg == Reg) && "Inconsistent PHI operands");
232 if (HeadReg != CmpBBReg)
238 // Assuming that trivialTailPHIs() is true, update the Tail PHIs by simply
239 // removing the CmpBB operands. The Head operands will be identical.
240 void SSACCmpConv::updateTailPHIs() {
241 for (auto &I : *Tail) {
244 // I is a PHI. It can have multiple entries for CmpBB.
245 for (unsigned oi = I.getNumOperands(); oi > 2; oi -= 2) {
246 // PHI operands are (Reg, MBB) at (oi-2, oi-1).
247 if (I.getOperand(oi - 1).getMBB() == CmpBB) {
248 I.RemoveOperand(oi - 1);
249 I.RemoveOperand(oi - 2);
255 // This pass runs before the ARM64DeadRegisterDefinitions pass, so compares are
256 // still writing virtual registers without any uses.
257 bool SSACCmpConv::isDeadDef(unsigned DstReg) {
258 // Writes to the zero register are dead.
259 if (DstReg == ARM64::WZR || DstReg == ARM64::XZR)
261 if (!TargetRegisterInfo::isVirtualRegister(DstReg))
263 // A virtual register def without any uses will be marked dead later, and
264 // eventually replaced by the zero register.
265 return MRI->use_nodbg_empty(DstReg);
268 // Parse a condition code returned by AnalyzeBranch, and compute the CondCode
269 // corresponding to TBB.
271 static bool parseCond(ArrayRef<MachineOperand> Cond, ARM64CC::CondCode &CC) {
272 // A normal br.cond simply has the condition code.
273 if (Cond[0].getImm() != -1) {
274 assert(Cond.size() == 1 && "Unknown Cond array format");
275 CC = (ARM64CC::CondCode)(int)Cond[0].getImm();
278 // For tbz and cbz instruction, the opcode is next.
279 switch (Cond[1].getImm()) {
281 // This includes tbz / tbnz branches which can't be converted to
286 assert(Cond.size() == 3 && "Unknown Cond array format");
291 assert(Cond.size() == 3 && "Unknown Cond array format");
297 MachineInstr *SSACCmpConv::findConvertibleCompare(MachineBasicBlock *MBB) {
298 MachineBasicBlock::iterator I = MBB->getFirstTerminator();
301 // The terminator must be controlled by the flags.
302 if (!I->readsRegister(ARM64::CPSR)) {
303 switch (I->getOpcode()) {
308 // These can be converted into a ccmp against #0.
312 DEBUG(dbgs() << "Flags not used by terminator: " << *I);
316 // Now find the instruction controlling the terminator.
317 for (MachineBasicBlock::iterator B = MBB->begin(); I != B;) {
319 assert(!I->isTerminator() && "Spurious terminator");
320 switch (I->getOpcode()) {
321 // cmp is an alias for subs with a dead destination register.
324 // cmn is an alias for adds with a dead destination register.
327 // Check that the immediate operand is within range, ccmp wants a uimm5.
328 // Rd = SUBSri Rn, imm, shift
329 if (I->getOperand(3).getImm() || !isUInt<5>(I->getOperand(2).getImm())) {
330 DEBUG(dbgs() << "Immediate out of range for ccmp: " << *I);
339 if (isDeadDef(I->getOperand(0).getReg()))
341 DEBUG(dbgs() << "Can't convert compare with live destination: " << *I);
346 case ARM64::FCMPESrr:
347 case ARM64::FCMPEDrr:
351 // Check for flag reads and clobbers.
352 MIOperands::PhysRegInfo PRI =
353 MIOperands(I).analyzePhysReg(ARM64::CPSR, TRI);
356 // The ccmp doesn't produce exactly the same flags as the original
357 // compare, so reject the transform if there are uses of the flags
358 // besides the terminators.
359 DEBUG(dbgs() << "Can't create ccmp with multiple uses: " << *I);
365 DEBUG(dbgs() << "Not convertible compare: " << *I);
370 DEBUG(dbgs() << "Flags not defined in BB#" << MBB->getNumber() << '\n');
374 /// Determine if all the instructions in MBB can safely
375 /// be speculated. The terminators are not considered.
377 /// Only CmpMI is allowed to clobber the flags.
379 bool SSACCmpConv::canSpeculateInstrs(MachineBasicBlock *MBB,
380 const MachineInstr *CmpMI) {
381 // Reject any live-in physregs. It's probably CPSR/EFLAGS, and very hard to
383 if (!MBB->livein_empty()) {
384 DEBUG(dbgs() << "BB#" << MBB->getNumber() << " has live-ins.\n");
388 unsigned InstrCount = 0;
390 // Check all instructions, except the terminators. It is assumed that
391 // terminators never have side effects or define any used register values.
392 for (auto &I : make_range(MBB->begin(), MBB->getFirstTerminator())) {
393 if (I.isDebugValue())
396 if (++InstrCount > BlockInstrLimit && !Stress) {
397 DEBUG(dbgs() << "BB#" << MBB->getNumber() << " has more than "
398 << BlockInstrLimit << " instructions.\n");
402 // There shouldn't normally be any phis in a single-predecessor block.
404 DEBUG(dbgs() << "Can't hoist: " << I);
408 // Don't speculate loads. Note that it may be possible and desirable to
409 // speculate GOT or constant pool loads that are guaranteed not to trap,
410 // but we don't support that for now.
412 DEBUG(dbgs() << "Won't speculate load: " << I);
416 // We never speculate stores, so an AA pointer isn't necessary.
417 bool DontMoveAcrossStore = true;
418 if (!I.isSafeToMove(TII, 0, DontMoveAcrossStore)) {
419 DEBUG(dbgs() << "Can't speculate: " << I);
423 // Only CmpMI is allowed to clobber the flags.
424 if (&I != CmpMI && I.modifiesRegister(ARM64::CPSR, TRI)) {
425 DEBUG(dbgs() << "Clobbers flags: " << I);
432 /// Analyze the sub-cfg rooted in MBB, and return true if it is a potential
433 /// candidate for cmp-conversion. Fill out the internal state.
435 bool SSACCmpConv::canConvert(MachineBasicBlock *MBB) {
439 if (Head->succ_size() != 2)
441 MachineBasicBlock *Succ0 = Head->succ_begin()[0];
442 MachineBasicBlock *Succ1 = Head->succ_begin()[1];
444 // CmpBB can only have a single predecessor. Tail is allowed many.
445 if (Succ0->pred_size() != 1)
446 std::swap(Succ0, Succ1);
448 // Succ0 is our candidate for CmpBB.
449 if (Succ0->pred_size() != 1 || Succ0->succ_size() != 2)
455 if (!CmpBB->isSuccessor(Tail))
458 // The CFG topology checks out.
459 DEBUG(dbgs() << "\nTriangle: BB#" << Head->getNumber() << " -> BB#"
460 << CmpBB->getNumber() << " -> BB#" << Tail->getNumber() << '\n');
463 // Tail is allowed to have many predecessors, but we can't handle PHIs yet.
465 // FIXME: Real PHIs could be if-converted as long as the CmpBB values are
466 // defined before The CmpBB cmp clobbers the flags. Alternatively, it should
467 // always be safe to sink the ccmp down to immediately before the CmpBB
469 if (!trivialTailPHIs()) {
470 DEBUG(dbgs() << "Can't handle phis in Tail.\n");
475 if (!Tail->livein_empty()) {
476 DEBUG(dbgs() << "Can't handle live-in physregs in Tail.\n");
481 // CmpBB should never have PHIs since Head is its only predecessor.
482 // FIXME: Clean them up if it happens.
483 if (!CmpBB->empty() && CmpBB->front().isPHI()) {
484 DEBUG(dbgs() << "Can't handle phis in CmpBB.\n");
489 if (!CmpBB->livein_empty()) {
490 DEBUG(dbgs() << "Can't handle live-in physregs in CmpBB.\n");
495 // The branch we're looking to eliminate must be analyzable.
497 MachineBasicBlock *TBB = 0, *FBB = 0;
498 if (TII->AnalyzeBranch(*Head, TBB, FBB, HeadCond)) {
499 DEBUG(dbgs() << "Head branch not analyzable.\n");
504 // This is weird, probably some sort of degenerate CFG, or an edge to a
506 if (!TBB || HeadCond.empty()) {
507 DEBUG(dbgs() << "AnalyzeBranch didn't find conditional branch in Head.\n");
512 if (!parseCond(HeadCond, HeadCmpBBCC)) {
513 DEBUG(dbgs() << "Unsupported branch type on Head\n");
518 // Make sure the branch direction is right.
520 assert(TBB == Tail && "Unexpected TBB");
521 HeadCmpBBCC = ARM64CC::getInvertedCondCode(HeadCmpBBCC);
526 if (TII->AnalyzeBranch(*CmpBB, TBB, FBB, CmpBBCond)) {
527 DEBUG(dbgs() << "CmpBB branch not analyzable.\n");
532 if (!TBB || CmpBBCond.empty()) {
533 DEBUG(dbgs() << "AnalyzeBranch didn't find conditional branch in CmpBB.\n");
538 if (!parseCond(CmpBBCond, CmpBBTailCC)) {
539 DEBUG(dbgs() << "Unsupported branch type on CmpBB\n");
545 CmpBBTailCC = ARM64CC::getInvertedCondCode(CmpBBTailCC);
547 DEBUG(dbgs() << "Head->CmpBB on " << ARM64CC::getCondCodeName(HeadCmpBBCC)
548 << ", CmpBB->Tail on " << ARM64CC::getCondCodeName(CmpBBTailCC)
551 CmpMI = findConvertibleCompare(CmpBB);
555 if (!canSpeculateInstrs(CmpBB, CmpMI)) {
562 void SSACCmpConv::convert(SmallVectorImpl<MachineBasicBlock *> &RemovedBlocks) {
563 DEBUG(dbgs() << "Merging BB#" << CmpBB->getNumber() << " into BB#"
564 << Head->getNumber() << ":\n" << *CmpBB);
566 // All CmpBB instructions are moved into Head, and CmpBB is deleted.
567 // Update the CFG first.
569 Head->removeSuccessor(CmpBB);
570 CmpBB->removeSuccessor(Tail);
571 Head->transferSuccessorsAndUpdatePHIs(CmpBB);
572 DebugLoc TermDL = Head->getFirstTerminator()->getDebugLoc();
573 TII->RemoveBranch(*Head);
575 // If the Head terminator was one of the cbz / tbz branches with built-in
576 // compare, we need to insert an explicit compare instruction in its place.
577 if (HeadCond[0].getImm() == -1) {
580 switch (HeadCond[1].getImm()) {
583 Opc = ARM64::SUBSWri;
587 Opc = ARM64::SUBSXri;
590 llvm_unreachable("Cannot convert Head branch");
592 const MCInstrDesc &MCID = TII->get(Opc);
593 // Create a dummy virtual register for the SUBS def.
595 MRI->createVirtualRegister(TII->getRegClass(MCID, 0, TRI, *MF));
596 // Insert a SUBS Rn, #0 instruction instead of the cbz / cbnz.
597 BuildMI(*Head, Head->end(), TermDL, MCID)
598 .addReg(DestReg, RegState::Define | RegState::Dead)
599 .addOperand(HeadCond[2])
602 // SUBS uses the GPR*sp register classes.
603 MRI->constrainRegClass(HeadCond[2].getReg(),
604 TII->getRegClass(MCID, 1, TRI, *MF));
607 Head->splice(Head->end(), CmpBB, CmpBB->begin(), CmpBB->end());
609 // Now replace CmpMI with a ccmp instruction that also considers the incoming
612 unsigned FirstOp = 1; // First CmpMI operand to copy.
613 bool isZBranch = false; // CmpMI is a cbz/cbnz instruction.
614 switch (CmpMI->getOpcode()) {
616 llvm_unreachable("Unknown compare opcode");
617 case ARM64::SUBSWri: Opc = ARM64::CCMPWi; break;
618 case ARM64::SUBSWrr: Opc = ARM64::CCMPWr; break;
619 case ARM64::SUBSXri: Opc = ARM64::CCMPXi; break;
620 case ARM64::SUBSXrr: Opc = ARM64::CCMPXr; break;
621 case ARM64::ADDSWri: Opc = ARM64::CCMNWi; break;
622 case ARM64::ADDSWrr: Opc = ARM64::CCMNWr; break;
623 case ARM64::ADDSXri: Opc = ARM64::CCMNXi; break;
624 case ARM64::ADDSXrr: Opc = ARM64::CCMNXr; break;
625 case ARM64::FCMPSrr: Opc = ARM64::FCCMPSrr; FirstOp = 0; break;
626 case ARM64::FCMPDrr: Opc = ARM64::FCCMPDrr; FirstOp = 0; break;
627 case ARM64::FCMPESrr: Opc = ARM64::FCCMPESrr; FirstOp = 0; break;
628 case ARM64::FCMPEDrr: Opc = ARM64::FCCMPEDrr; FirstOp = 0; break;
643 // The ccmp instruction should set the flags according to the comparison when
644 // Head would have branched to CmpBB.
645 // The NZCV immediate operand should provide flags for the case where Head
646 // would have branched to Tail. These flags should cause the new Head
647 // terminator to branch to tail.
648 unsigned NZCV = ARM64CC::getNZCVToSatisfyCondCode(CmpBBTailCC);
649 const MCInstrDesc &MCID = TII->get(Opc);
650 MRI->constrainRegClass(CmpMI->getOperand(FirstOp).getReg(),
651 TII->getRegClass(MCID, 0, TRI, *MF));
652 if (CmpMI->getOperand(FirstOp + 1).isReg())
653 MRI->constrainRegClass(CmpMI->getOperand(FirstOp + 1).getReg(),
654 TII->getRegClass(MCID, 1, TRI, *MF));
655 MachineInstrBuilder MIB =
656 BuildMI(*Head, CmpMI, CmpMI->getDebugLoc(), MCID)
657 .addOperand(CmpMI->getOperand(FirstOp)); // Register Rn
659 MIB.addImm(0); // cbz/cbnz Rn -> ccmp Rn, #0
661 MIB.addOperand(CmpMI->getOperand(FirstOp + 1)); // Register Rm / Immediate
662 MIB.addImm(NZCV).addImm(HeadCmpBBCC);
664 // If CmpMI was a terminator, we need a new conditional branch to replace it.
665 // This now becomes a Head terminator.
667 bool isNZ = CmpMI->getOpcode() == ARM64::CBNZW ||
668 CmpMI->getOpcode() == ARM64::CBNZX;
669 BuildMI(*Head, CmpMI, CmpMI->getDebugLoc(), TII->get(ARM64::Bcc))
670 .addImm(isNZ ? ARM64CC::NE : ARM64CC::EQ)
671 .addOperand(CmpMI->getOperand(1)); // Branch target.
673 CmpMI->eraseFromParent();
674 Head->updateTerminator();
676 RemovedBlocks.push_back(CmpBB);
677 CmpBB->eraseFromParent();
678 DEBUG(dbgs() << "Result:\n" << *Head);
682 int SSACCmpConv::expectedCodeSizeDelta() const {
684 // If the Head terminator was one of the cbz / tbz branches with built-in
685 // compare, we need to insert an explicit compare instruction in its place
686 // plus a branch instruction.
687 if (HeadCond[0].getImm() == -1) {
688 switch (HeadCond[1].getImm()) {
693 // Therefore delta += 1
697 llvm_unreachable("Cannot convert Head branch");
700 // If the Cmp terminator was one of the cbz / tbz branches with
701 // built-in compare, it will be turned into a compare instruction
702 // into Head, but we do not save any instruction.
703 // Otherwise, we save the branch instruction.
704 switch (CmpMI->getOpcode()) {
717 //===----------------------------------------------------------------------===//
718 // ARM64ConditionalCompares Pass
719 //===----------------------------------------------------------------------===//
722 class ARM64ConditionalCompares : public MachineFunctionPass {
723 const TargetInstrInfo *TII;
724 const TargetRegisterInfo *TRI;
725 const MCSchedModel *SchedModel;
726 // Does the proceeded function has Oz attribute.
728 MachineRegisterInfo *MRI;
729 MachineDominatorTree *DomTree;
730 MachineLoopInfo *Loops;
731 MachineTraceMetrics *Traces;
732 MachineTraceMetrics::Ensemble *MinInstr;
737 ARM64ConditionalCompares() : MachineFunctionPass(ID) {}
738 void getAnalysisUsage(AnalysisUsage &AU) const;
739 bool runOnMachineFunction(MachineFunction &MF);
740 const char *getPassName() const { return "ARM64 Conditional Compares"; }
743 bool tryConvert(MachineBasicBlock *);
744 void updateDomTree(ArrayRef<MachineBasicBlock *> Removed);
745 void updateLoops(ArrayRef<MachineBasicBlock *> Removed);
746 void invalidateTraces();
747 bool shouldConvert();
749 } // end anonymous namespace
751 char ARM64ConditionalCompares::ID = 0;
754 void initializeARM64ConditionalComparesPass(PassRegistry &);
757 INITIALIZE_PASS_BEGIN(ARM64ConditionalCompares, "arm64-ccmp", "ARM64 CCMP Pass",
759 INITIALIZE_PASS_DEPENDENCY(MachineBranchProbabilityInfo)
760 INITIALIZE_PASS_DEPENDENCY(MachineDominatorTree)
761 INITIALIZE_PASS_DEPENDENCY(MachineTraceMetrics)
762 INITIALIZE_PASS_END(ARM64ConditionalCompares, "arm64-ccmp", "ARM64 CCMP Pass",
765 FunctionPass *llvm::createARM64ConditionalCompares() {
766 return new ARM64ConditionalCompares();
769 void ARM64ConditionalCompares::getAnalysisUsage(AnalysisUsage &AU) const {
770 AU.addRequired<MachineBranchProbabilityInfo>();
771 AU.addRequired<MachineDominatorTree>();
772 AU.addPreserved<MachineDominatorTree>();
773 AU.addRequired<MachineLoopInfo>();
774 AU.addPreserved<MachineLoopInfo>();
775 AU.addRequired<MachineTraceMetrics>();
776 AU.addPreserved<MachineTraceMetrics>();
777 MachineFunctionPass::getAnalysisUsage(AU);
780 /// Update the dominator tree after if-conversion erased some blocks.
782 ARM64ConditionalCompares::updateDomTree(ArrayRef<MachineBasicBlock *> Removed) {
783 // convert() removes CmpBB which was previously dominated by Head.
784 // CmpBB children should be transferred to Head.
785 MachineDomTreeNode *HeadNode = DomTree->getNode(CmpConv.Head);
786 for (unsigned i = 0, e = Removed.size(); i != e; ++i) {
787 MachineDomTreeNode *Node = DomTree->getNode(Removed[i]);
788 assert(Node != HeadNode && "Cannot erase the head node");
789 assert(Node->getIDom() == HeadNode && "CmpBB should be dominated by Head");
790 while (Node->getNumChildren())
791 DomTree->changeImmediateDominator(Node->getChildren().back(), HeadNode);
792 DomTree->eraseNode(Removed[i]);
796 /// Update LoopInfo after if-conversion.
798 ARM64ConditionalCompares::updateLoops(ArrayRef<MachineBasicBlock *> Removed) {
801 for (unsigned i = 0, e = Removed.size(); i != e; ++i)
802 Loops->removeBlock(Removed[i]);
805 /// Invalidate MachineTraceMetrics before if-conversion.
806 void ARM64ConditionalCompares::invalidateTraces() {
807 Traces->invalidate(CmpConv.Head);
808 Traces->invalidate(CmpConv.CmpBB);
811 /// Apply cost model and heuristics to the if-conversion in IfConv.
812 /// Return true if the conversion is a good idea.
814 bool ARM64ConditionalCompares::shouldConvert() {
815 // Stress testing mode disables all cost considerations.
819 MinInstr = Traces->getEnsemble(MachineTraceMetrics::TS_MinInstrCount);
821 // Head dominates CmpBB, so it is always included in its trace.
822 MachineTraceMetrics::Trace Trace = MinInstr->getTrace(CmpConv.CmpBB);
824 // If code size is the main concern
826 int CodeSizeDelta = CmpConv.expectedCodeSizeDelta();
827 DEBUG(dbgs() << "Code size delta: " << CodeSizeDelta << '\n');
828 // If we are minimizing the code size, do the conversion whatever
830 if (CodeSizeDelta < 0)
832 if (CodeSizeDelta > 0) {
833 DEBUG(dbgs() << "Code size is increasing, give up on this one.\n");
836 // CodeSizeDelta == 0, continue with the regular heuristics
839 // Heuristic: The compare conversion delays the execution of the branch
840 // instruction because we must wait for the inputs to the second compare as
841 // well. The branch has no dependent instructions, but delaying it increases
842 // the cost of a misprediction.
844 // Set a limit on the delay we will accept.
845 unsigned DelayLimit = SchedModel->MispredictPenalty * 3 / 4;
847 // Instruction depths can be computed for all trace instructions above CmpBB.
849 Trace.getInstrCycles(CmpConv.Head->getFirstTerminator()).Depth;
850 unsigned CmpBBDepth =
851 Trace.getInstrCycles(CmpConv.CmpBB->getFirstTerminator()).Depth;
852 DEBUG(dbgs() << "Head depth: " << HeadDepth
853 << "\nCmpBB depth: " << CmpBBDepth << '\n');
854 if (CmpBBDepth > HeadDepth + DelayLimit) {
855 DEBUG(dbgs() << "Branch delay would be larger than " << DelayLimit
860 // Check the resource depth at the bottom of CmpBB - these instructions will
862 unsigned ResDepth = Trace.getResourceDepth(true);
863 DEBUG(dbgs() << "Resources: " << ResDepth << '\n');
865 // Heuristic: The speculatively executed instructions must all be able to
866 // merge into the Head block. The Head critical path should dominate the
867 // resource cost of the speculated instructions.
868 if (ResDepth > HeadDepth) {
869 DEBUG(dbgs() << "Too many instructions to speculate.\n");
875 bool ARM64ConditionalCompares::tryConvert(MachineBasicBlock *MBB) {
876 bool Changed = false;
877 while (CmpConv.canConvert(MBB) && shouldConvert()) {
879 SmallVector<MachineBasicBlock *, 4> RemovedBlocks;
880 CmpConv.convert(RemovedBlocks);
882 updateDomTree(RemovedBlocks);
883 updateLoops(RemovedBlocks);
888 bool ARM64ConditionalCompares::runOnMachineFunction(MachineFunction &MF) {
889 DEBUG(dbgs() << "********** ARM64 Conditional Compares **********\n"
890 << "********** Function: " << MF.getName() << '\n');
891 TII = MF.getTarget().getInstrInfo();
892 TRI = MF.getTarget().getRegisterInfo();
894 MF.getTarget().getSubtarget<TargetSubtargetInfo>().getSchedModel();
895 MRI = &MF.getRegInfo();
896 DomTree = &getAnalysis<MachineDominatorTree>();
897 Loops = getAnalysisIfAvailable<MachineLoopInfo>();
898 Traces = &getAnalysis<MachineTraceMetrics>();
900 MinSize = MF.getFunction()->getAttributes().hasAttribute(
901 AttributeSet::FunctionIndex, Attribute::MinSize);
903 bool Changed = false;
904 CmpConv.runOnMachineFunction(MF);
906 // Visit blocks in dominator tree pre-order. The pre-order enables multiple
907 // cmp-conversions from the same head block.
908 // Note that updateDomTree() modifies the children of the DomTree node
909 // currently being visited. The df_iterator supports that; it doesn't look at
910 // child_begin() / child_end() until after a node has been visited.
911 for (auto *I : depth_first(DomTree))
912 if (tryConvert(I->getBlock()))