1 //===-- AArch64ConditionalCompares.cpp --- CCMP formation for AArch64 -----===//
5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
7 //===----------------------------------------------------------------------===//
14 // if-conversion, and this pass should run immediately before the early
15 // if-conversion pass.
17 //===----------------------------------------------------------------------===//
41 #define DEBUG_TYPE "aarch64-ccmp"
46     "aarch64-ccmp-limit", cl::init(30), cl::Hidden,
49 // Stress testing mode - disable heuristics.
50 static cl::opt<bool> Stress("aarch64-stress-ccmp", cl::Hidden,
57 STATISTIC(NumHeadBranchRejs, "Number of ccmps rejected (Head branch)");
65 STATISTIC(NumSpeculateRejs, "Number of ccmps rejected (Can't speculate)");
70 //===----------------------------------------------------------------------===//
72 //===----------------------------------------------------------------------===//
74 // The SSACCmpConv class performs ccmp-conversion on SSA form machine code
76 // external code should be used to determine when ccmp-conversion is a good
79 // CCmp-formation works on a CFG representing chained conditions, typically
80 // from C's short-circuit || and && operators:
82 //   From:         Head            To:         Head
92 // The Head block is terminated by a br.cond instruction, and the CmpBB block
95 // The cmp-conversion turns the compare instruction in CmpBB into a conditional
96 // compare, and merges CmpBB into Head, speculatively executing its
99 // the compare isn't executed. This makes it possible to chain compares with
107 //    Head:
119 //    Head:
127 // The ccmp condition code is the one that would cause the Head terminator to
131 // between Head and Tail, just like if-converting a diamond.
133 // FIXME: Handle PHIs in Tail by turning them into selects (if-conversion).
146   MachineBasicBlock *Head;  member in __anon79d718350111::SSACCmpConv
148   /// The block containing cmp+br.cond with a successor shared with Head.
151   /// The common successor for Head and CmpBB.
158   /// The branch condition in Head as determined by analyzeBranch.
161   /// The condition code that makes Head branch to CmpBB.
180   /// Return NULL if a convertible instruction can't be found.
183   /// Return true if all non-terminator instructions in MBB can be safely
188   /// runOnMachineFunction - Initialize per-function data structures.
191     this->MF = &MF;  in runOnMachineFunction()
192     this->MBPI = MBPI;  in runOnMachineFunction()
198   /// If the sub-CFG headed by MBB can be cmp-converted, initialize the
202   /// Cmo-convert the last block passed to canConvertCmp(), assuming
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.
223       if (MBB == Head) {  in trivialTailPHIs()
239 // removing the CmpBB operands. The Head operands will be identical.
245     for (unsigned oi = I.getNumOperands(); oi > 2; oi -= 2) {  in updateTailPHIs()
246       // PHI operands are (Reg, MBB) at (oi-2, oi-1).  in updateTailPHIs()
247       if (I.getOperand(oi - 1).getMBB() == CmpBB) {  in updateTailPHIs()
248         I.removeOperand(oi - 1);  in updateTailPHIs()
249         I.removeOperand(oi - 2);  in updateTailPHIs()
265   return MRI->use_nodbg_empty(DstReg);  in isDeadDef()
273   if (Cond[0].getImm() != -1) {  in parseCond()
281     // This includes tbz / tbnz branches which can't be converted to  in parseCond()
298   MachineBasicBlock::iterator I = MBB->getFirstTerminator();  in findConvertibleCompare()
299   if (I == MBB->end())  in findConvertibleCompare()
302   if (!I->readsRegister(AArch64::NZCV, /*TRI=*/nullptr)) {  in findConvertibleCompare()
303     switch (I->getOpcode()) {  in findConvertibleCompare()
317   for (MachineBasicBlock::iterator B = MBB->begin(); I != B;) {  in findConvertibleCompare()
318     I = prev_nodbg(I, MBB->begin());  in findConvertibleCompare()
319     assert(!I->isTerminator() && "Spurious terminator");  in findConvertibleCompare()
320     switch (I->getOpcode()) {  in findConvertibleCompare()
329       if (I->getOperand(3).getImm() || !isUInt<5>(I->getOperand(2).getImm())) {  in findConvertibleCompare()
339       if (isDeadDef(I->getOperand(0).getReg()))  in findConvertibleCompare()
341       LLVM_DEBUG(dbgs() << "Can't convert compare with live destination: "  in findConvertibleCompare()
356       // The ccmp doesn't produce exactly the same flags as the original  in findConvertibleCompare()
359       LLVM_DEBUG(dbgs() << "Can't create ccmp with multiple uses: " << *I);  in findConvertibleCompare()
382   // Reject any live-in physregs. It's probably NZCV/EFLAGS, and very hard to  in canSpeculateInstrs()
384   if (!MBB->livein_empty()) {  in canSpeculateInstrs()
385     LLVM_DEBUG(dbgs() << printMBBReference(*MBB) << " has live-ins.\n");  in canSpeculateInstrs()
393   for (auto &I : make_range(MBB->begin(), MBB->getFirstTerminator())) {  in canSpeculateInstrs()
403     // There shouldn't normally be any phis in a single-predecessor block.  in canSpeculateInstrs()
405       LLVM_DEBUG(dbgs() << "Can't hoist: " << I);  in canSpeculateInstrs()
409     // Don't speculate loads. Note that it may be possible and desirable to  in canSpeculateInstrs()
411     // but we don't support that for now.  in canSpeculateInstrs()
413       LLVM_DEBUG(dbgs() << "Won't speculate load: " << I);  in canSpeculateInstrs()
417     // We never speculate stores, so an AA pointer isn't necessary.  in canSpeculateInstrs()
420       LLVM_DEBUG(dbgs() << "Can't speculate: " << I);  in canSpeculateInstrs()
433 /// Analyze the sub-cfg rooted in MBB, and return true if it is a potential
434 /// candidate for cmp-conversion. Fill out the internal state.
437   Head = MBB;  in canConvert()
440   if (Head->succ_size() != 2)  in canConvert()
442   MachineBasicBlock *Succ0 = Head->succ_begin()[0];  in canConvert()
443   MachineBasicBlock *Succ1 = Head->succ_begin()[1];  in canConvert()
446   if (Succ0->pred_size() != 1)  in canConvert()
450   if (Succ0->pred_size() != 1 || Succ0->succ_size() != 2)  in canConvert()
456   if (!CmpBB->isSuccessor(Tail))  in canConvert()
460   LLVM_DEBUG(dbgs() << "\nTriangle: " << printMBBReference(*Head) << " -> "  in canConvert()
461                     << printMBBReference(*CmpBB) << " -> "  in canConvert()
465   // Tail is allowed to have many predecessors, but we can't handle PHIs yet.  in canConvert()
467   // FIXME: Real PHIs could be if-converted as long as the CmpBB values are  in canConvert()
472     LLVM_DEBUG(dbgs() << "Can't handle phis in Tail.\n");  in canConvert()
477   if (!Tail->livein_empty()) {  in canConvert()
478     LLVM_DEBUG(dbgs() << "Can't handle live-in physregs in Tail.\n");  in canConvert()
483   // CmpBB should never have PHIs since Head is its only predecessor.  in canConvert()
485   if (!CmpBB->empty() && CmpBB->front().isPHI()) {  in canConvert()
486     LLVM_DEBUG(dbgs() << "Can't handle phis in CmpBB.\n");  in canConvert()
491   if (!CmpBB->livein_empty()) {  in canConvert()
492     LLVM_DEBUG(dbgs() << "Can't handle live-in physregs in CmpBB.\n");  in canConvert()
500   if (TII->analyzeBranch(*Head, TBB, FBB, HeadCond)) {  in canConvert()
501     LLVM_DEBUG(dbgs() << "Head branch not analyzable.\n");  in canConvert()
510         dbgs() << "analyzeBranch didn't find conditional branch in Head.\n");  in canConvert()
516     LLVM_DEBUG(dbgs() << "Unsupported branch type on Head\n");  in canConvert()
529   if (TII->analyzeBranch(*CmpBB, TBB, FBB, CmpBBCond)) {  in canConvert()
537         dbgs() << "analyzeBranch didn't find conditional branch in CmpBB.\n");  in canConvert()
551   LLVM_DEBUG(dbgs() << "Head->CmpBB on "  in canConvert()
553                     << ", CmpBB->Tail on "  in canConvert()
569                     << printMBBReference(*Head) << ":\n"  in convert()
572   // All CmpBB instructions are moved into Head, and CmpBB is deleted.  in convert()
578   BranchProbability Head2CmpBB = MBPI->getEdgeProbability(Head, CmpBB);  in convert()
579   BranchProbability CmpBB2Tail = MBPI->getEdgeProbability(CmpBB, Tail);  in convert()
581   Head->removeSuccessor(CmpBB);  in convert()
582   CmpBB->removeSuccessor(Tail);  in convert()
584   // If Head and CmpBB had successor probabilties, udpate the probabilities to  in convert()
585   // reflect the ccmp-conversion.  in convert()
586   if (Head->hasSuccessorProbabilities() && CmpBB->hasSuccessorProbabilities()) {  in convert()
588     // Head is allowed two successors. We've removed CmpBB, so the remaining  in convert()
592     // Pr(Tail|Head) += Pr(CmpBB|Head) * Pr(Tail|CmpBB).  in convert()
593     assert(*Head->succ_begin() == Tail && "Head successor is not Tail");  in convert()
594     BranchProbability Head2Tail = MBPI->getEdgeProbability(Head, Tail);  in convert()
595     Head->setSuccProbability(Head->succ_begin(),  in convert()
598     // We will transfer successors of CmpBB to Head in a moment without  in convert()
602     // Pr(I|Head) = Pr(CmpBB|Head) * Pr(I|CmpBB).  in convert()
603     for (auto I = CmpBB->succ_begin(), E = CmpBB->succ_end(); I != E; ++I) {  in convert()
604       BranchProbability CmpBB2I = MBPI->getEdgeProbability(CmpBB, *I);  in convert()
605       CmpBB->setSuccProbability(I, Head2CmpBB * CmpBB2I);  in convert()
609   Head->transferSuccessorsAndUpdatePHIs(CmpBB);  in convert()
610   DebugLoc TermDL = Head->getFirstTerminator()->getDebugLoc();  in convert()
611   TII->removeBranch(*Head);  in convert()
613   // If the Head terminator was one of the cbz / tbz branches with built-in  in convert()
615   if (HeadCond[0].getImm() == -1) {  in convert()
628       llvm_unreachable("Cannot convert Head branch");  in convert()
630     const MCInstrDesc &MCID = TII->get(Opc);  in convert()
633         MRI->createVirtualRegister(TII->getRegClass(MCID, 0, TRI, *MF));  in convert()
635     BuildMI(*Head, Head->end(), TermDL, MCID)  in convert()
641     MRI->constrainRegClass(HeadCond[2].getReg(),  in convert()
642                            TII->getRegClass(MCID, 1, TRI, *MF));  in convert()
645   Head->splice(Head->end(), CmpBB, CmpBB->begin(), CmpBB->end());  in convert()
652   switch (CmpMI->getOpcode()) {  in convert()
682   // Head would have branched to CmpBB.  in convert()
683   // The NZCV immediate operand should provide flags for the case where Head  in convert()
684   // would have branched to Tail. These flags should cause the new Head  in convert()
687   const MCInstrDesc &MCID = TII->get(Opc);  in convert()
688   MRI->constrainRegClass(CmpMI->getOperand(FirstOp).getReg(),  in convert()
689                          TII->getRegClass(MCID, 0, TRI, *MF));  in convert()
690   if (CmpMI->getOperand(FirstOp + 1).isReg())  in convert()
691     MRI->constrainRegClass(CmpMI->getOperand(FirstOp + 1).getReg(),  in convert()
692                            TII->getRegClass(MCID, 1, TRI, *MF));  in convert()
693   MachineInstrBuilder MIB = BuildMI(*Head, CmpMI, CmpMI->getDebugLoc(), MCID)  in convert()
694                                 .add(CmpMI->getOperand(FirstOp)); // Register Rn  in convert()
696     MIB.addImm(0); // cbz/cbnz Rn -> ccmp Rn, #0  in convert()
698     MIB.add(CmpMI->getOperand(FirstOp + 1)); // Register Rm / Immediate  in convert()
702   // This now becomes a Head terminator.  in convert()
704     bool isNZ = CmpMI->getOpcode() == AArch64::CBNZW ||  in convert()
705                 CmpMI->getOpcode() == AArch64::CBNZX;  in convert()
706     BuildMI(*Head, CmpMI, CmpMI->getDebugLoc(), TII->get(AArch64::Bcc))  in convert()
708         .add(CmpMI->getOperand(1)); // Branch target.  in convert()
710   CmpMI->eraseFromParent();  in convert()
711   Head->updateTerminator(CmpBB->getNextNode());  in convert()
714   CmpBB->eraseFromParent();  in convert()
715   LLVM_DEBUG(dbgs() << "Result:\n" << *Head);  in convert()
721   // If the Head terminator was one of the cbz / tbz branches with built-in  in expectedCodeSizeDelta()
724   if (HeadCond[0].getImm() == -1) {  in expectedCodeSizeDelta()
734       llvm_unreachable("Cannot convert Head branch");  in expectedCodeSizeDelta()
738   // built-in compare, it will be turned into a compare instruction  in expectedCodeSizeDelta()
739   // into Head, but we do not save any instruction.  in expectedCodeSizeDelta()
741   switch (CmpMI->getOpcode()) {  in expectedCodeSizeDelta()
743     --delta;  in expectedCodeSizeDelta()
754 //===----------------------------------------------------------------------===//
756 //===----------------------------------------------------------------------===//
795 INITIALIZE_PASS_BEGIN(AArch64ConditionalCompares, "aarch64-ccmp",
800 INITIALIZE_PASS_END(AArch64ConditionalCompares, "aarch64-ccmp",  in INITIALIZE_PASS_DEPENDENCY()
818 /// Update the dominator tree after if-conversion erased some blocks.
821   // convert() removes CmpBB which was previously dominated by Head.  in updateDomTree()
822   // CmpBB children should be transferred to Head.  in updateDomTree()
823   MachineDomTreeNode *HeadNode = DomTree->getNode(CmpConv.Head);  in updateDomTree()
825     MachineDomTreeNode *Node = DomTree->getNode(RemovedMBB);  in updateDomTree()
826     assert(Node != HeadNode && "Cannot erase the head node");  in updateDomTree()
827     assert(Node->getIDom() == HeadNode && "CmpBB should be dominated by Head");  in updateDomTree()
828     while (Node->getNumChildren())  in updateDomTree()
829       DomTree->changeImmediateDominator(Node->back(), HeadNode);  in updateDomTree()
830     DomTree->eraseNode(RemovedMBB);  in updateDomTree()
834 /// Update LoopInfo after if-conversion.
840     Loops->removeBlock(RemovedMBB);  in updateLoops()
843 /// Invalidate MachineTraceMetrics before if-conversion.
845   Traces->invalidate(CmpConv.Head);  in invalidateTraces()
846   Traces->invalidate(CmpConv.CmpBB);  in invalidateTraces()
849 /// Apply cost model and heuristics to the if-conversion in IfConv.
857     MinInstr = Traces->getEnsemble(MachineTraceStrategy::TS_MinInstrCount);  in shouldConvert()
859   // Head dominates CmpBB, so it is always included in its trace.  in shouldConvert()
860   MachineTraceMetrics::Trace Trace = MinInstr->getTrace(CmpConv.CmpBB);  in shouldConvert()
887       Trace.getInstrCycles(*CmpConv.Head->getFirstTerminator()).Depth;  in shouldConvert()
889       Trace.getInstrCycles(*CmpConv.CmpBB->getFirstTerminator()).Depth;  in shouldConvert()
890   LLVM_DEBUG(dbgs() << "Head depth:  " << HeadDepth  in shouldConvert()
898   // Check the resource depth at the bottom of CmpBB - these instructions will  in shouldConvert()
904   // merge into the Head block. The Head critical path should dominate the  in shouldConvert()
946   // Visit blocks in dominator tree pre-order. The pre-order enables multiple  in runOnMachineFunction()
947   // cmp-conversions from the same head block.  in runOnMachineFunction()
949   // currently being visited. The df_iterator supports that; it doesn't look at  in runOnMachineFunction()
952     if (tryConvert(I->getBlock()))  in runOnMachineFunction()