Lines Matching +full:end +full:- +full:of +full:- +full:conversion
1 //===-- EarlyIfConversion.cpp - If-conversion on SSA form machine code ----===//
3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
7 //===----------------------------------------------------------------------===//
9 // Early if-conversion is for out-of-order CPUs that don't have a lot of
13 // Instructions from both sides of the branch are executed specutatively, and a
16 //===----------------------------------------------------------------------===//
43 #define DEBUG_TYPE "early-ifcvt"
45 // Absolute maximum number of instructions allowed per speculated block.
48 BlockInstrLimit("early-ifcvt-limit", cl::init(30), cl::Hidden,
49 cl::desc("Maximum number of instructions per speculated block."));
51 // Stress testing mode - disable heuristics.
52 static cl::opt<bool> Stress("stress-early-ifcvt", cl::Hidden,
55 STATISTIC(NumDiamondsSeen, "Number of diamonds");
56 STATISTIC(NumDiamondsConv, "Number of diamonds converted");
57 STATISTIC(NumTrianglesSeen, "Number of triangles");
58 STATISTIC(NumTrianglesConv, "Number of triangles converted");
60 //===----------------------------------------------------------------------===//
62 //===----------------------------------------------------------------------===//
64 // The SSAIfConv class performs if-conversion on SSA form machine code after
66 // code should be used to determine when if-conversion is a good idea.
91 /// The block containing phis after the if-then-else.
100 /// isTriangle - When there is no 'else' block, either TBB or FBB will be
140 /// Return true if all non-terminator instructions in MBB can be safely
144 /// Return true if all non-terminator instructions in MBB can be safely
149 /// Return false if any dependency is incompatible with if conversion.
152 /// Predicate all instructions of the basic block with current condition
166 /// runOnMachineFunction - Initialize per-function data structures.
172 LiveRegUnits.setUniverse(TRI->getNumRegUnits()); in runOnMachineFunction()
174 ClobberedRegUnits.resize(TRI->getNumRegUnits()); in runOnMachineFunction()
177 /// canConvertIf - If the sub-CFG headed by MBB can be if-converted,
183 /// convertIf - If-convert the last block passed to canConvertIf(), assuming
188 } // end anonymous namespace
191 /// canSpeculateInstrs - Returns true if all the instructions in MBB can safely
200 // Reject any live-in physregs. It's probably CPSR/EFLAGS, and very hard to in canSpeculateInstrs()
202 if (!MBB->livein_empty()) { in canSpeculateInstrs()
203 LLVM_DEBUG(dbgs() << printMBBReference(*MBB) << " has live-ins.\n"); in canSpeculateInstrs()
212 llvm::make_range(MBB->begin(), MBB->getFirstTerminator())) { in canSpeculateInstrs()
222 // There shouldn't normally be any phis in a single-predecessor block. in canSpeculateInstrs()
250 /// Check that there is no dependencies preventing if conversion.
255 for (const MachineOperand &MO : I->operands()) { in InstrDependenciesAllowIfConv()
266 for (MCRegUnit Unit : TRI->regunits(Reg.asMCReg())) in InstrDependenciesAllowIfConv()
271 MachineInstr *DefMI = MRI->getVRegDef(Reg); in InstrDependenciesAllowIfConv()
272 if (!DefMI || DefMI->getParent() != Head) in InstrDependenciesAllowIfConv()
275 LLVM_DEBUG(dbgs() << printMBBReference(*I->getParent()) << " depends on " in InstrDependenciesAllowIfConv()
277 if (DefMI->isTerminator()) { in InstrDependenciesAllowIfConv()
285 /// canPredicateInstrs - Returns true if all the instructions in MBB can safely
294 // Reject any live-in physregs. It's probably CPSR/EFLAGS, and very hard to in canPredicateInstrs()
296 if (!MBB->livein_empty()) { in canPredicateInstrs()
297 LLVM_DEBUG(dbgs() << printMBBReference(*MBB) << " has live-ins.\n"); in canPredicateInstrs()
305 for (MachineBasicBlock::iterator I = MBB->begin(), in canPredicateInstrs()
306 E = MBB->getFirstTerminator(); in canPredicateInstrs()
308 if (I->isDebugInstr()) in canPredicateInstrs()
317 // There shouldn't normally be any phis in a single-predecessor block. in canPredicateInstrs()
318 if (I->isPHI()) { in canPredicateInstrs()
324 if (!TII->isPredicable(*I)) { in canPredicateInstrs()
330 if (TII->isPredicated(*I) && !TII->canPredicatePredicatedInstr(*I)) { in canPredicateInstrs()
346 bool CanRevCond = !TII->reverseBranchCondition(Condition); in PredicateBlock()
351 for (MachineBasicBlock::iterator I = MBB->begin(), in PredicateBlock()
352 E = MBB->getFirstTerminator(); in PredicateBlock()
354 if (I->isDebugInstr()) in PredicateBlock()
356 TII->PredicateInstruction(*I, Condition); in PredicateBlock()
371 // Keep track of live regunits before the current position. in findInsertionPoint()
375 MachineBasicBlock::iterator FirstTerm = Head->getFirstTerminator(); in findInsertionPoint()
376 MachineBasicBlock::iterator I = Head->end(); in findInsertionPoint()
377 MachineBasicBlock::iterator B = Head->begin(); in findInsertionPoint()
379 --I; in findInsertionPoint()
380 // Some of the conditional code depends in I. in findInsertionPoint()
387 for (const MachineOperand &MO : I->operands()) { in findInsertionPoint()
396 for (MCRegUnit Unit : TRI->regunits(Reg.asMCReg())) in findInsertionPoint()
404 for (MCRegUnit Unit : TRI->regunits(Reads.pop_back_val())) in findInsertionPoint()
409 if (I != FirstTerm && I->isTerminator()) in findInsertionPoint()
412 // Some of the clobbered registers are live before I, not a valid insertion in findInsertionPoint()
435 /// canConvertIf - analyze the sub-cfg rooted in MBB, and return true if it is
436 /// a potential candidate for if-conversion. Fill out the internal state.
442 if (Head->succ_size() != 2) in canConvertIf()
444 MachineBasicBlock *Succ0 = Head->succ_begin()[0]; in canConvertIf()
445 MachineBasicBlock *Succ1 = Head->succ_begin()[1]; in canConvertIf()
448 if (Succ0->pred_size() != 1) in canConvertIf()
451 if (Succ0->pred_size() != 1 || Succ0->succ_size() != 1) in canConvertIf()
454 Tail = Succ0->succ_begin()[0]; in canConvertIf()
459 if (Succ1->pred_size() != 1 || Succ1->succ_size() != 1 || in canConvertIf()
460 Succ1->succ_begin()[0] != Tail) in canConvertIf()
462 LLVM_DEBUG(dbgs() << "\nDiamond: " << printMBBReference(*Head) << " -> " in canConvertIf()
464 << printMBBReference(*Succ1) << " -> " in canConvertIf()
467 // Live-in physregs are tricky to get right when speculating code. in canConvertIf()
468 if (!Tail->livein_empty()) { in canConvertIf()
469 LLVM_DEBUG(dbgs() << "Tail has live-ins.\n"); in canConvertIf()
473 LLVM_DEBUG(dbgs() << "\nTriangle: " << printMBBReference(*Head) << " -> " in canConvertIf()
474 << printMBBReference(*Succ0) << " -> " in canConvertIf()
481 if (!Predicate && (Tail->empty() || !Tail->front().isPHI())) { in canConvertIf()
488 if (TII->analyzeBranch(*Head, TBB, FBB, Cond)) { in canConvertIf()
493 // This is weird, probably some sort of degenerate CFG. in canConvertIf()
499 // Make sure the analyzed branch is conditional; one of the successors in canConvertIf()
506 // analyzeBranch doesn't set FBB on a fall-through branch. in canConvertIf()
514 for (MachineBasicBlock::iterator I = Tail->begin(), E = Tail->end(); in canConvertIf()
515 I != E && I->isPHI(); ++I) { in canConvertIf()
519 for (unsigned i = 1; i != PI.PHI->getNumOperands(); i += 2) { in canConvertIf()
520 if (PI.PHI->getOperand(i+1).getMBB() == TPred) in canConvertIf()
521 PI.TReg = PI.PHI->getOperand(i).getReg(); in canConvertIf()
522 if (PI.PHI->getOperand(i+1).getMBB() == FPred) in canConvertIf()
523 PI.FReg = PI.PHI->getOperand(i).getReg(); in canConvertIf()
529 if (!TII->canInsertSelect(*Head, Cond, PI.PHI->getOperand(0).getReg(), in canConvertIf()
579 // If there are side-effects, all bets are off. in hasSameValue()
580 if (TDef->hasUnmodeledSideEffects()) in hasSameValue()
585 if (TDef->mayLoadOrStore() && !TDef->isDereferenceableInvariantLoad()) in hasSameValue()
592 if (any_of(TDef->uses(), [](const MachineOperand &MO) { in hasSameValue()
598 if (!TII->produceSameValue(*TDef, *FDef, &MRI)) in hasSameValue()
602 int TIdx = TDef->findRegisterDefOperandIdx(TReg, /*TRI=*/nullptr); in hasSameValue()
603 int FIdx = FDef->findRegisterDefOperandIdx(FReg, /*TRI=*/nullptr); in hasSameValue()
604 if (TIdx == -1 || FIdx == -1) in hasSameValue()
610 /// replacePHIInstrs - Completely replace PHI instructions with selects.
611 /// This is possible when the only Tail predecessors are the if-converted
614 assert(Tail->pred_size() == 2 && "Cannot replace PHIs"); in replacePHIInstrs()
615 MachineBasicBlock::iterator FirstTerm = Head->getFirstTerminator(); in replacePHIInstrs()
616 assert(FirstTerm != Head->end() && "No terminators"); in replacePHIInstrs()
617 DebugLoc HeadDL = FirstTerm->getDebugLoc(); in replacePHIInstrs()
621 LLVM_DEBUG(dbgs() << "If-converting " << *PI.PHI); in replacePHIInstrs()
622 Register DstReg = PI.PHI->getOperand(0).getReg(); in replacePHIInstrs()
626 BuildMI(*Head, FirstTerm, HeadDL, TII->get(TargetOpcode::COPY), DstReg) in replacePHIInstrs()
629 TII->insertSelect(*Head, FirstTerm, HeadDL, DstReg, Cond, PI.TReg, in replacePHIInstrs()
632 LLVM_DEBUG(dbgs() << " --> " << *std::prev(FirstTerm)); in replacePHIInstrs()
633 PI.PHI->eraseFromParent(); in replacePHIInstrs()
638 /// rewritePHIOperands - When there are additional Tail predecessors, insert
642 MachineBasicBlock::iterator FirstTerm = Head->getFirstTerminator(); in rewritePHIOperands()
643 assert(FirstTerm != Head->end() && "No terminators"); in rewritePHIOperands()
644 DebugLoc HeadDL = FirstTerm->getDebugLoc(); in rewritePHIOperands()
650 LLVM_DEBUG(dbgs() << "If-converting " << *PI.PHI); in rewritePHIOperands()
656 Register PHIDst = PI.PHI->getOperand(0).getReg(); in rewritePHIOperands()
657 DstReg = MRI->createVirtualRegister(MRI->getRegClass(PHIDst)); in rewritePHIOperands()
658 TII->insertSelect(*Head, FirstTerm, HeadDL, in rewritePHIOperands()
660 LLVM_DEBUG(dbgs() << " --> " << *std::prev(FirstTerm)); in rewritePHIOperands()
663 // Rewrite PHI operands TPred -> (DstReg, Head), remove FPred. in rewritePHIOperands()
664 for (unsigned i = PI.PHI->getNumOperands(); i != 1; i -= 2) { in rewritePHIOperands()
665 MachineBasicBlock *MBB = PI.PHI->getOperand(i-1).getMBB(); in rewritePHIOperands()
667 PI.PHI->getOperand(i-1).setMBB(Head); in rewritePHIOperands()
668 PI.PHI->getOperand(i-2).setReg(DstReg); in rewritePHIOperands()
670 PI.PHI->removeOperand(i-1); in rewritePHIOperands()
671 PI.PHI->removeOperand(i-2); in rewritePHIOperands()
674 LLVM_DEBUG(dbgs() << " --> " << *PI.PHI); in rewritePHIOperands()
678 /// convertIf - Execute the if conversion after canConvertIf has determined the
697 Head->splice(InsertionPoint, TBB, TBB->begin(), TBB->getFirstTerminator()); in convertIf()
702 Head->splice(InsertionPoint, FBB, FBB->begin(), FBB->getFirstTerminator()); in convertIf()
705 bool ExtraPreds = Tail->pred_size() != 2; in convertIf()
712 Head->removeSuccessor(TBB); in convertIf()
713 Head->removeSuccessor(FBB, true); in convertIf()
715 TBB->removeSuccessor(Tail, true); in convertIf()
717 FBB->removeSuccessor(Tail, true); in convertIf()
721 DebugLoc HeadDL = Head->getFirstTerminator()->getDebugLoc(); in convertIf()
722 TII->removeBranch(*Head); in convertIf()
728 TBB->eraseFromParent(); in convertIf()
732 FBB->eraseFromParent(); in convertIf()
735 assert(Head->succ_empty() && "Additional head successors?"); in convertIf()
736 if (!ExtraPreds && Head->isLayoutSuccessor(Tail)) { in convertIf()
737 // Splice Tail onto the end of Head. in convertIf()
740 Head->splice(Head->end(), Tail, in convertIf()
741 Tail->begin(), Tail->end()); in convertIf()
742 Head->transferSuccessorsAndUpdatePHIs(Tail); in convertIf()
744 Tail->eraseFromParent(); in convertIf()
749 TII->insertBranch(*Head, Tail, nullptr, EmptyCond, HeadDL); in convertIf()
750 Head->addSuccessor(Tail); in convertIf()
755 //===----------------------------------------------------------------------===//
757 //===----------------------------------------------------------------------===//
776 StringRef getPassName() const override { return "Early If-Conversion"; } in getPassName()
783 } // end anonymous namespace
808 /// Update the dominator tree after if-conversion erased some blocks.
814 MachineDomTreeNode *HeadNode = DomTree->getNode(IfConv.Head); in updateDomTree()
816 MachineDomTreeNode *Node = DomTree->getNode(B); in updateDomTree()
818 while (Node->getNumChildren()) { in updateDomTree()
819 assert(Node->getBlock() == IfConv.Tail && "Unexpected children"); in updateDomTree()
820 DomTree->changeImmediateDominator(Node->back(), HeadNode); in updateDomTree()
822 DomTree->eraseNode(B); in updateDomTree()
826 /// Update LoopInfo after if-conversion.
829 // If-conversion doesn't change loop structure, and it doesn't mess with back in updateLoops()
832 Loops->removeBlock(B); in updateLoops()
836 /// Invalidate MachineTraceMetrics before if-conversion.
838 Traces->verifyAnalysis(); in invalidateTraces()
839 Traces->invalidate(IfConv.Head); in invalidateTraces()
840 Traces->invalidate(IfConv.Tail); in invalidateTraces()
841 Traces->invalidate(IfConv.TBB); in invalidateTraces()
842 Traces->invalidate(IfConv.FBB); in invalidateTraces()
843 Traces->verifyAnalysis(); in invalidateTraces()
854 /// Helper class to simplify emission of cycle counts into optimization remarks.
864 /// Apply cost model and heuristics to the if-conversion in IfConv.
865 /// Return true if the conversion is a good idea.
872 // Do not try to if-convert if the condition has a high chance of being in shouldConvertIf()
874 MachineLoop *CurrentLoop = Loops->getLoopFor(IfConv.Head); in shouldConvertIf()
876 // itself or all its operands are loop-invariant. E.g. this considers a load in shouldConvertIf()
877 // from a loop-invariant address predictable; we were unable to prove that it in shouldConvertIf()
878 // doesn't alias any of the memory-writes in the loop, but it is likely to in shouldConvertIf()
887 MachineInstr *Def = MRI->getVRegDef(Reg); in shouldConvertIf()
888 return CurrentLoop->isLoopInvariant(*Def) || in shouldConvertIf()
889 all_of(Def->operands(), [&](MachineOperand &Op) { in shouldConvertIf()
898 MachineInstr *Def = MRI->getVRegDef(Reg); in shouldConvertIf()
899 return CurrentLoop->isLoopInvariant(*Def); in shouldConvertIf()
905 MinInstr = Traces->getEnsemble(MachineTraceStrategy::TS_MinInstrCount); in shouldConvertIf()
907 MachineTraceMetrics::Trace TBBTrace = MinInstr->getTrace(IfConv.getTPred()); in shouldConvertIf()
908 MachineTraceMetrics::Trace FBBTrace = MinInstr->getTrace(IfConv.getFPred()); in shouldConvertIf()
919 // If-conversion only makes sense when there is unexploited ILP. Compute the in shouldConvertIf()
920 // maximum-ILP resource length of the trace after if-conversion. Compare it in shouldConvertIf()
933 R << "did not if-convert branch: the resulting critical path (" in shouldConvertIf()
936 << Cycles{"MinCrit", MinCrit} << ") by more than the threshold of " in shouldConvertIf()
944 // Assume that the depth of the first head terminator will also be the depth in shouldConvertIf()
945 // of the select instruction inserted, as determined by the flag dependency. in shouldConvertIf()
947 MachineTraceMetrics::Trace HeadTrace = MinInstr->getTrace(IfConv.Head); in shouldConvertIf()
949 HeadTrace.getInstrCycles(*IfConv.Head->getFirstTerminator()).Depth; in shouldConvertIf()
954 MachineTraceMetrics::Trace TailTrace = MinInstr->getTrace(IfConv.Tail); in shouldConvertIf()
956 unsigned Extra; // Count of extra cycles that the component adds. in shouldConvertIf()
957 unsigned Depth; // Absolute depth of the component in cycles. in shouldConvertIf()
971 unsigned Extra = CondDepth - MaxDepth; in shouldConvertIf()
976 LLVM_DEBUG(dbgs() << "Exceeds limit of " << CritLimit << '\n'); in shouldConvertIf()
984 unsigned Extra = TDepth - MaxDepth; in shouldConvertIf()
989 LLVM_DEBUG(dbgs() << "Exceeds limit of " << CritLimit << '\n'); in shouldConvertIf()
997 unsigned Extra = FDepth - MaxDepth; in shouldConvertIf()
1002 LLVM_DEBUG(dbgs() << "Exceeds limit of " << CritLimit << '\n'); in shouldConvertIf()
1009 // when referring to the "true" and "false" sides of the branch, given that in shouldConvertIf()
1010 // those don't always correlate with what the user wrote in source-terms. in shouldConvertIf()
1018 R << "performing if-conversion on branch: the condition adds " in shouldConvertIf()
1026 R << ", each staying under the threshold of " in shouldConvertIf()
1034 R << "did not if-convert branch: the condition would add " in shouldConvertIf()
1037 R << " exceeding the limit of " << Cycles{"CritLimit", CritLimit}; in shouldConvertIf()
1042 R << " exceeding the limit of " << Cycles{"CritLimit", CritLimit}; in shouldConvertIf()
1048 R << " exceeding the limit of " << Cycles{"CritLimit", CritLimit}; in shouldConvertIf()
1058 /// Attempt repeated if-conversion on MBB, return true if successful.
1063 // If-convert MBB and update analyses. in tryConvertIf()
1075 LLVM_DEBUG(dbgs() << "********** EARLY IF-CONVERSION **********\n" in runOnMachineFunction()
1080 // Only run if conversion if the target wants it. in runOnMachineFunction()
1097 // Visit blocks in dominator tree post-order. The post-order enables nested in runOnMachineFunction()
1098 // if-conversion in a single pass. The tryConvertIf() function may erase in runOnMachineFunction()
1100 // update the dominator tree while the post-order iterator is still active. in runOnMachineFunction()
1102 if (tryConvertIf(DomNode->getBlock())) in runOnMachineFunction()
1108 //===----------------------------------------------------------------------===//
1110 //===----------------------------------------------------------------------===//
1128 StringRef getPassName() const override { return "Early If-predicator"; } in getPassName()
1134 } // end anonymous namespace
1137 #define DEBUG_TYPE "early-if-predicator"
1160 auto TrueProbability = MBPI->getEdgeProbability(IfConv.Head, IfConv.TBB); in shouldConvertIf()
1170 Cycles += NumCycles - 1; in shouldConvertIf()
1171 ExtraPredCost += TII->getPredicationCost(I); in shouldConvertIf()
1174 return TII->isProfitableToIfCvt(IfBlock, Cycles, ExtraPredCost, in shouldConvertIf()
1184 TCycle += NumCycles - 1; in shouldConvertIf()
1185 TExtra += TII->getPredicationCost(I); in shouldConvertIf()
1190 FCycle += NumCycles - 1; in shouldConvertIf()
1191 FExtra += TII->getPredicationCost(I); in shouldConvertIf()
1193 return TII->isProfitableToIfCvt(*IfConv.TBB, TCycle, TExtra, *IfConv.FBB, in shouldConvertIf()
1197 /// Attempt repeated if-conversion on MBB, return true if successful.
1202 // If-convert MBB and update analyses. in tryConvertIf()
1213 LLVM_DEBUG(dbgs() << "********** EARLY IF-PREDICATOR **********\n" in runOnMachineFunction()
1230 // Visit blocks in dominator tree post-order. The post-order enables nested in runOnMachineFunction()
1231 // if-conversion in a single pass. The tryConvertIf() function may erase in runOnMachineFunction()
1233 // update the dominator tree while the post-order iterator is still active. in runOnMachineFunction()
1235 if (tryConvertIf(DomNode->getBlock())) in runOnMachineFunction()