Lines Matching +full:- +full:- +full:head +full:- +full:branch
1 //===-- EarlyIfConversion.cpp - If-conversion on SSA form machine code ----===//
8 //===----------------------------------------------------------------------===//
10 // Early if-conversion is for out-of-order CPUs that don't have a lot of
14 // Instructions from both sides of the branch are executed specutatively, and a
17 //===----------------------------------------------------------------------===//
42 #define DEBUG_TYPE "early-ifcvt"
47 BlockInstrLimit("early-ifcvt-limit", cl::init(30), cl::Hidden,
50 // Stress testing mode - disable heuristics.
51 static cl::opt<bool> Stress("stress-early-ifcvt", cl::Hidden,
59 //===----------------------------------------------------------------------===//
61 //===----------------------------------------------------------------------===//
63 // The SSAIfConv class performs if-conversion on SSA form machine code after
65 // code should be used to determine when if-conversion is a good idea.
69 // Triangle: Head Diamond: Head
78 // Head block, and phis in the Tail block are converted to select instructions.
87 /// The block containing the conditional branch.
88 MachineBasicBlock *Head; member in __anonad061d3e0111::SSAIfConv
90 /// The block containing phis after the if-then-else.
99 /// isTriangle - When there is no 'else' block, either TBB or FBB will be
104 MachineBasicBlock *getTPred() const { return TBB == Tail ? Head : TBB; } in getTPred()
107 MachineBasicBlock *getFPred() const { return FBB == Tail ? Head : FBB; } in getFPred()
113 // Latencies from Cond+Branch, TReg, and FReg to DstReg.
123 /// The branch condition determined by AnalyzeBranch.
126 /// Instructions in Head that define values used by the conditional blocks.
136 /// Insertion point in Head for speculatively executed instructions form TBB
140 /// Return true if all non-terminator instructions in MBB can be safely
144 /// Find a valid insertion point in Head.
154 /// runOnMachineFunction - Initialize per-function data structures.
160 LiveRegUnits.setUniverse(TRI->getNumRegUnits()); in runOnMachineFunction()
162 ClobberedRegUnits.resize(TRI->getNumRegUnits()); in runOnMachineFunction()
165 /// canConvertIf - If the sub-CFG headed by MBB can be if-converted,
169 /// convertIf - If-convert the last block passed to canConvertIf(), assuming
176 /// canSpeculateInstrs - Returns true if all the instructions in MBB can safely
179 /// If instructions use any values that are defined in the head basic block,
185 // Reject any live-in physregs. It's probably CPSR/EFLAGS, and very hard to in canSpeculateInstrs()
187 if (!MBB->livein_empty()) { in canSpeculateInstrs()
188 DEBUG(dbgs() << "BB#" << MBB->getNumber() << " has live-ins.\n"); in canSpeculateInstrs()
196 for (MachineBasicBlock::iterator I = MBB->begin(), in canSpeculateInstrs()
197 E = MBB->getFirstTerminator(); I != E; ++I) { in canSpeculateInstrs()
198 if (I->isDebugValue()) in canSpeculateInstrs()
202 DEBUG(dbgs() << "BB#" << MBB->getNumber() << " has more than " in canSpeculateInstrs()
207 // There shouldn't normally be any phis in a single-predecessor block. in canSpeculateInstrs()
208 if (I->isPHI()) { in canSpeculateInstrs()
216 if (I->mayLoad()) { in canSpeculateInstrs()
223 if (!I->isSafeToMove(nullptr, DontMoveAcrossStore)) { in canSpeculateInstrs()
228 // Check for any dependencies on Head instructions. in canSpeculateInstrs()
229 for (const MachineOperand &MO : I->operands()) { in canSpeculateInstrs()
245 MachineInstr *DefMI = MRI->getVRegDef(Reg); in canSpeculateInstrs()
246 if (!DefMI || DefMI->getParent() != Head) in canSpeculateInstrs()
249 DEBUG(dbgs() << "BB#" << MBB->getNumber() << " depends on " << *DefMI); in canSpeculateInstrs()
250 if (DefMI->isTerminator()) { in canSpeculateInstrs()
260 /// Find an insertion point in Head for the speculated instructions. The
275 MachineBasicBlock::iterator FirstTerm = Head->getFirstTerminator(); in findInsertionPoint()
276 MachineBasicBlock::iterator I = Head->end(); in findInsertionPoint()
277 MachineBasicBlock::iterator B = Head->begin(); in findInsertionPoint()
279 --I; in findInsertionPoint()
287 for (const MachineOperand &MO : I->operands()) { in findInsertionPoint()
310 if (I != FirstTerm && I->isTerminator()) in findInsertionPoint()
337 /// canConvertIf - analyze the sub-cfg rooted in MBB, and return true if it is
338 /// a potential candidate for if-conversion. Fill out the internal state.
341 Head = MBB; in canConvertIf()
344 if (Head->succ_size() != 2) in canConvertIf()
346 MachineBasicBlock *Succ0 = Head->succ_begin()[0]; in canConvertIf()
347 MachineBasicBlock *Succ1 = Head->succ_begin()[1]; in canConvertIf()
350 if (Succ0->pred_size() != 1) in canConvertIf()
353 if (Succ0->pred_size() != 1 || Succ0->succ_size() != 1) in canConvertIf()
356 Tail = Succ0->succ_begin()[0]; in canConvertIf()
361 if (Succ1->pred_size() != 1 || Succ1->succ_size() != 1 || in canConvertIf()
362 Succ1->succ_begin()[0] != Tail) in canConvertIf()
364 DEBUG(dbgs() << "\nDiamond: BB#" << Head->getNumber() in canConvertIf()
365 << " -> BB#" << Succ0->getNumber() in canConvertIf()
366 << "/BB#" << Succ1->getNumber() in canConvertIf()
367 << " -> BB#" << Tail->getNumber() << '\n'); in canConvertIf()
369 // Live-in physregs are tricky to get right when speculating code. in canConvertIf()
370 if (!Tail->livein_empty()) { in canConvertIf()
371 DEBUG(dbgs() << "Tail has live-ins.\n"); in canConvertIf()
375 DEBUG(dbgs() << "\nTriangle: BB#" << Head->getNumber() in canConvertIf()
376 << " -> BB#" << Succ0->getNumber() in canConvertIf()
377 << " -> BB#" << Tail->getNumber() << '\n'); in canConvertIf()
382 if (Tail->empty() || !Tail->front().isPHI()) { in canConvertIf()
387 // The branch we're looking to eliminate must be analyzable. in canConvertIf()
389 if (TII->analyzeBranch(*Head, TBB, FBB, Cond)) { in canConvertIf()
390 DEBUG(dbgs() << "Branch not analyzable.\n"); in canConvertIf()
396 DEBUG(dbgs() << "AnalyzeBranch didn't find conditional branch.\n"); in canConvertIf()
400 // AnalyzeBranch doesn't set FBB on a fall-through branch. in canConvertIf()
408 for (MachineBasicBlock::iterator I = Tail->begin(), E = Tail->end(); in canConvertIf()
409 I != E && I->isPHI(); ++I) { in canConvertIf()
413 for (unsigned i = 1; i != PI.PHI->getNumOperands(); i += 2) { in canConvertIf()
414 if (PI.PHI->getOperand(i+1).getMBB() == TPred) in canConvertIf()
415 PI.TReg = PI.PHI->getOperand(i).getReg(); in canConvertIf()
416 if (PI.PHI->getOperand(i+1).getMBB() == FPred) in canConvertIf()
417 PI.FReg = PI.PHI->getOperand(i).getReg(); in canConvertIf()
423 if (!TII->canInsertSelect(*Head, Cond, PI.TReg, PI.FReg, in canConvertIf()
439 // head basic block. in canConvertIf()
450 /// replacePHIInstrs - Completely replace PHI instructions with selects.
451 /// This is possible when the only Tail predecessors are the if-converted
454 assert(Tail->pred_size() == 2 && "Cannot replace PHIs"); in replacePHIInstrs()
455 MachineBasicBlock::iterator FirstTerm = Head->getFirstTerminator(); in replacePHIInstrs()
456 assert(FirstTerm != Head->end() && "No terminators"); in replacePHIInstrs()
457 DebugLoc HeadDL = FirstTerm->getDebugLoc(); in replacePHIInstrs()
462 DEBUG(dbgs() << "If-converting " << *PI.PHI); in replacePHIInstrs()
463 unsigned DstReg = PI.PHI->getOperand(0).getReg(); in replacePHIInstrs()
464 TII->insertSelect(*Head, FirstTerm, HeadDL, DstReg, Cond, PI.TReg, PI.FReg); in replacePHIInstrs()
465 DEBUG(dbgs() << " --> " << *std::prev(FirstTerm)); in replacePHIInstrs()
466 PI.PHI->eraseFromParent(); in replacePHIInstrs()
471 /// rewritePHIOperands - When there are additional Tail predecessors, insert
472 /// select instructions in Head and rewrite PHI operands to use the selects.
475 MachineBasicBlock::iterator FirstTerm = Head->getFirstTerminator(); in rewritePHIOperands()
476 assert(FirstTerm != Head->end() && "No terminators"); in rewritePHIOperands()
477 DebugLoc HeadDL = FirstTerm->getDebugLoc(); in rewritePHIOperands()
484 DEBUG(dbgs() << "If-converting " << *PI.PHI); in rewritePHIOperands()
490 unsigned PHIDst = PI.PHI->getOperand(0).getReg(); in rewritePHIOperands()
491 DstReg = MRI->createVirtualRegister(MRI->getRegClass(PHIDst)); in rewritePHIOperands()
492 TII->insertSelect(*Head, FirstTerm, HeadDL, in rewritePHIOperands()
494 DEBUG(dbgs() << " --> " << *std::prev(FirstTerm)); in rewritePHIOperands()
497 // Rewrite PHI operands TPred -> (DstReg, Head), remove FPred. in rewritePHIOperands()
498 for (unsigned i = PI.PHI->getNumOperands(); i != 1; i -= 2) { in rewritePHIOperands()
499 MachineBasicBlock *MBB = PI.PHI->getOperand(i-1).getMBB(); in rewritePHIOperands()
501 PI.PHI->getOperand(i-1).setMBB(Head); in rewritePHIOperands()
502 PI.PHI->getOperand(i-2).setReg(DstReg); in rewritePHIOperands()
504 PI.PHI->RemoveOperand(i-1); in rewritePHIOperands()
505 PI.PHI->RemoveOperand(i-2); in rewritePHIOperands()
508 DEBUG(dbgs() << " --> " << *PI.PHI); in rewritePHIOperands()
512 /// convertIf - Execute the if conversion after canConvertIf has determined the
518 assert(Head && Tail && TBB && FBB && "Call canConvertIf first."); in convertIf()
526 // Move all instructions into Head, except for the terminators. in convertIf()
528 Head->splice(InsertionPoint, TBB, TBB->begin(), TBB->getFirstTerminator()); in convertIf()
530 Head->splice(InsertionPoint, FBB, FBB->begin(), FBB->getFirstTerminator()); in convertIf()
533 bool ExtraPreds = Tail->pred_size() != 2; in convertIf()
539 // Fix up the CFG, temporarily leave Head without any successors. in convertIf()
540 Head->removeSuccessor(TBB); in convertIf()
541 Head->removeSuccessor(FBB, true); in convertIf()
543 TBB->removeSuccessor(Tail, true); in convertIf()
545 FBB->removeSuccessor(Tail, true); in convertIf()
547 // Fix up Head's terminators. in convertIf()
548 // It should become a single branch or a fallthrough. in convertIf()
549 DebugLoc HeadDL = Head->getFirstTerminator()->getDebugLoc(); in convertIf()
550 TII->RemoveBranch(*Head); in convertIf()
552 // Erase the now empty conditional blocks. It is likely that Head can fall in convertIf()
556 TBB->eraseFromParent(); in convertIf()
560 FBB->eraseFromParent(); in convertIf()
563 assert(Head->succ_empty() && "Additional head successors?"); in convertIf()
564 if (!ExtraPreds && Head->isLayoutSuccessor(Tail)) { in convertIf()
565 // Splice Tail onto the end of Head. in convertIf()
566 DEBUG(dbgs() << "Joining tail BB#" << Tail->getNumber() in convertIf()
567 << " into head BB#" << Head->getNumber() << '\n'); in convertIf()
568 Head->splice(Head->end(), Tail, in convertIf()
569 Tail->begin(), Tail->end()); in convertIf()
570 Head->transferSuccessorsAndUpdatePHIs(Tail); in convertIf()
572 Tail->eraseFromParent(); in convertIf()
574 // We need a branch to Tail, let code placement work it out later. in convertIf()
575 DEBUG(dbgs() << "Converting to unconditional branch.\n"); in convertIf()
577 TII->InsertBranch(*Head, Tail, nullptr, EmptyCond, HeadDL); in convertIf()
578 Head->addSuccessor(Tail); in convertIf()
580 DEBUG(dbgs() << *Head); in convertIf()
584 //===----------------------------------------------------------------------===//
586 //===----------------------------------------------------------------------===//
605 const char *getPassName() const override { return "Early If-Conversion"; } in getPassName()
620 "early-ifcvt", "Early If Converter", false, false)
625 "early-ifcvt", "Early If Converter", false, false) in INITIALIZE_PASS_DEPENDENCY()
638 /// Update the dominator tree after if-conversion erased some blocks.
640 // convertIf can remove TBB, FBB, and Tail can be merged into Head. in updateDomTree()
642 // Tail children should be transferred to Head. in updateDomTree()
643 MachineDomTreeNode *HeadNode = DomTree->getNode(IfConv.Head); in updateDomTree()
645 MachineDomTreeNode *Node = DomTree->getNode(Removed[i]); in updateDomTree()
646 assert(Node != HeadNode && "Cannot erase the head node"); in updateDomTree()
647 while (Node->getNumChildren()) { in updateDomTree()
648 assert(Node->getBlock() == IfConv.Tail && "Unexpected children"); in updateDomTree()
649 DomTree->changeImmediateDominator(Node->getChildren().back(), HeadNode); in updateDomTree()
651 DomTree->eraseNode(Removed[i]); in updateDomTree()
655 /// Update LoopInfo after if-conversion.
659 // If-conversion doesn't change loop structure, and it doesn't mess with back in updateLoops()
662 Loops->removeBlock(Removed[i]); in updateLoops()
665 /// Invalidate MachineTraceMetrics before if-conversion.
667 Traces->verifyAnalysis(); in invalidateTraces()
668 Traces->invalidate(IfConv.Head); in invalidateTraces()
669 Traces->invalidate(IfConv.Tail); in invalidateTraces()
670 Traces->invalidate(IfConv.TBB); in invalidateTraces()
671 Traces->invalidate(IfConv.FBB); in invalidateTraces()
672 Traces->verifyAnalysis(); in invalidateTraces()
682 /// Apply cost model and heuristics to the if-conversion in IfConv.
691 MinInstr = Traces->getEnsemble(MachineTraceMetrics::TS_MinInstrCount); in shouldConvertIf()
693 MachineTraceMetrics::Trace TBBTrace = MinInstr->getTrace(IfConv.getTPred()); in shouldConvertIf()
694 MachineTraceMetrics::Trace FBBTrace = MinInstr->getTrace(IfConv.getFPred()); in shouldConvertIf()
702 // If-conversion only makes sense when there is unexploited ILP. Compute the in shouldConvertIf()
703 // maximum-ILP resource length of the trace after if-conversion. Compare it in shouldConvertIf()
716 // Assume that the depth of the first head terminator will also be the depth in shouldConvertIf()
719 MachineTraceMetrics::Trace HeadTrace = MinInstr->getTrace(IfConv.Head); in shouldConvertIf()
721 HeadTrace.getInstrCycles(*IfConv.Head->getFirstTerminator()).Depth; in shouldConvertIf()
722 DEBUG(dbgs() << "Branch depth: " << BranchDepth << '\n'); in shouldConvertIf()
726 MachineTraceMetrics::Trace TailTrace = MinInstr->getTrace(IfConv.Tail); in shouldConvertIf()
736 unsigned Extra = CondDepth - MaxDepth; in shouldConvertIf()
747 unsigned Extra = TDepth - MaxDepth; in shouldConvertIf()
758 unsigned Extra = FDepth - MaxDepth; in shouldConvertIf()
769 /// Attempt repeated if-conversion on MBB, return true if successful.
774 // If-convert MBB and update analyses. in tryConvertIf()
786 DEBUG(dbgs() << "********** EARLY IF-CONVERSION **********\n" in runOnMachineFunction()
808 // Visit blocks in dominator tree post-order. The post-order enables nested in runOnMachineFunction()
809 // if-conversion in a single pass. The tryConvertIf() function may erase in runOnMachineFunction()
810 // blocks, but only blocks dominated by the head block. This makes it safe to in runOnMachineFunction()
811 // update the dominator tree while the post-order iterator is still active. in runOnMachineFunction()
813 if (tryConvertIf(DomNode->getBlock())) in runOnMachineFunction()