Lines Matching +full:non +full:- +full:live
1 //===- PhiElimination.cpp - Eliminate PHI nodes by inserting copies -------===//
5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
7 //===----------------------------------------------------------------------===//
13 //===----------------------------------------------------------------------===//
48 #define DEBUG_TYPE "phi-node-elimination"
51 DisableEdgeSplitting("disable-phi-elim-edge-splitting", cl::init(false),
57 SplitAllCriticalEdges("phi-elim-split-all-critical-edges", cl::init(false),
63 "no-phi-elim-live-out-early-exit", cl::init(false), cl::Hidden,
75 /// EliminatePHINodes - Eliminate phi nodes by inserting copy instructions
83 /// analyzePHINodes - Gather information about the PHI nodes in
103 // Count the number of non-undef PHI uses of each register in each BB.
109 // Map reusable lowered PHI node -> incoming join register.
119 auto *LVWrapper = P->getAnalysisIfAvailable<LiveVariablesWrapperPass>(); in PHIEliminationImpl()
120 auto *LISWrapper = P->getAnalysisIfAvailable<LiveIntervalsWrapperPass>(); in PHIEliminationImpl()
121 auto *MLIWrapper = P->getAnalysisIfAvailable<MachineLoopInfoWrapperPass>(); in PHIEliminationImpl()
123 P->getAnalysisIfAvailable<MachineDominatorTreeWrapperPass>(); in PHIEliminationImpl()
124 LV = LVWrapper ? &LVWrapper->getLV() : nullptr; in PHIEliminationImpl()
125 LIS = LISWrapper ? &LISWrapper->getLIS() : nullptr; in PHIEliminationImpl()
126 MLI = MLIWrapper ? &MLIWrapper->getLI() : nullptr; in PHIEliminationImpl()
127 MDT = MDTWrapper ? &MDTWrapper->getDomTree() : nullptr; in PHIEliminationImpl()
210 // A set of live-in regs for each MBB which is used to update LV in run()
215 for (unsigned Index = 0, e = MRI->getNumVirtRegs(); Index != e; ++Index) { in run()
217 // live-through or live-in (killed). in run()
219 MachineInstr *DefMI = MRI->getVRegDef(VirtReg); in run()
222 LiveVariables::VarInfo &VI = LV->getVarInfo(VirtReg); in run()
229 // The register is live into an MBB in which it is killed but not in run()
231 MachineBasicBlock *DefMBB = DefMI->getParent(); in run()
233 (!VI.Kills.empty() && VI.Kills.front()->getParent() != DefMBB)) in run()
235 LiveInSets[MI->getParent()->getNumber()].set(Index); in run()
244 MRI->leaveSSA(); in run()
256 Register DefReg = DefMI->getOperand(0).getReg(); in run()
257 if (MRI->use_nodbg_empty(DefReg)) { in run()
259 LIS->RemoveMachineInstrFromMaps(*DefMI); in run()
260 DefMI->eraseFromParent(); in run()
267 LIS->RemoveMachineInstrFromMaps(*I.first); in run()
273 MDT->getBase().recalculate(MF); in run()
284 /// EliminatePHINodes - Eliminate phi nodes by inserting copy instructions in
296 // that we generate fewer copies. If at any edge is non-critical, we either in EliminatePHINodes()
301 if (Pred->succ_size() < 2) { in EliminatePHINodes()
313 /// Return true if all defs of VirtReg are implicit-defs.
333 /// LowerPHINode - Lower the PHI node at the top of the specified block.
344 unsigned NumSrcs = (MPhi->getNumOperands() - 1) / 2; in LowerPHINode()
345 Register DestReg = MPhi->getOperand(0).getReg(); in LowerPHINode()
346 assert(MPhi->getOperand(0).getSubReg() == 0 && "Can't handle sub-reg PHIs"); in LowerPHINode()
347 bool isDead = MPhi->getOperand(0).isDead(); in LowerPHINode()
363 PHICopy = BuildMI(MBB, AfterPHIsIt, MPhi->getDebugLoc(), in LowerPHINode()
364 TII->get(TargetOpcode::IMPLICIT_DEF), DestReg); in LowerPHINode()
390 PHICopy = TII->createPHIDestinationCopy( in LowerPHINode()
391 MBB, AfterPHIsIt, MPhi->getDebugLoc(), IncomingReg, DestReg); in LowerPHINode()
394 if (MPhi->peekDebugInstrNum()) { in LowerPHINode()
395 // If referred to by debug-info, store where this PHI was. in LowerPHINode()
397 unsigned ID = MPhi->peekDebugInstrNum(); in LowerPHINode()
399 auto Res = MF->DebugPHIPositions.insert({ID, P}); in LowerPHINode()
404 // Update live variable information if there is any. in LowerPHINode()
407 LiveVariables::VarInfo &VI = LV->getVarInfo(IncomingReg); in LowerPHINode()
414 // In general, the PHICopy is inserted as the first non-phi instruction in LowerPHINode()
435 LV->removeVirtualRegisterKilled(IncomingReg, *OldKill); in LowerPHINode()
445 LV->addVirtualRegisterKilled(IncomingReg, *PHICopy); in LowerPHINode()
451 LV->removeVirtualRegistersKilled(*MPhi); in LowerPHINode()
455 LV->addVirtualRegisterDead(DestReg, *PHICopy); in LowerPHINode()
456 LV->removeVirtualRegisterDead(DestReg, *MPhi); in LowerPHINode()
462 SlotIndex DestCopyIndex = LIS->InsertMachineInstrInMaps(*PHICopy); in LowerPHINode()
464 SlotIndex MBBStartIndex = LIS->getMBBStartIdx(&MBB); in LowerPHINode()
467 // IncomingReg's live interval. in LowerPHINode()
468 LiveInterval &IncomingLI = LIS->getOrCreateEmptyInterval(IncomingReg); in LowerPHINode()
472 IncomingLI.getNextValue(MBBStartIndex, LIS->getVNInfoAllocator()); in LowerPHINode()
477 LiveInterval &DestLI = LIS->getInterval(DestReg); in LowerPHINode()
478 assert(!DestLI.empty() && "PHIs should have non-empty LiveIntervals."); in LowerPHINode()
487 auto DestSegment = LR->find(MBBStartIndex); in LowerPHINode()
488 assert(DestSegment != LR->end() && in LowerPHINode()
489 "PHI destination must be live in block"); in LowerPHINode()
491 if (LR->endIndex().isDead()) { in LowerPHINode()
492 // A dead PHI's live range begins and ends at the start of the MBB, but in LowerPHINode()
495 VNInfo *OrigDestVNI = LR->getVNInfoAt(DestSegment->start); in LowerPHINode()
496 assert(OrigDestVNI && "PHI destination should be live at block entry."); in LowerPHINode()
497 LR->removeSegment(DestSegment->start, DestSegment->start.getDeadSlot()); in LowerPHINode()
498 LR->createDeadDef(NewStart, LIS->getVNInfoAllocator()); in LowerPHINode()
499 LR->removeValNo(OrigDestVNI); in LowerPHINode()
504 // they replace. Hence the start of the live range may need to be adjusted in LowerPHINode()
506 if (DestSegment->start > NewStart) { in LowerPHINode()
507 VNInfo *VNI = LR->getVNInfoAt(DestSegment->start); in LowerPHINode()
509 LR->addSegment( in LowerPHINode()
510 LiveInterval::Segment(NewStart, DestSegment->start, VNI)); in LowerPHINode()
511 } else if (DestSegment->start < NewStart) { in LowerPHINode()
512 assert(DestSegment->start >= MBBStartIndex); in LowerPHINode()
513 assert(DestSegment->end >= DestCopyIndex.getRegSlot()); in LowerPHINode()
514 LR->removeSegment(DestSegment->start, NewStart); in LowerPHINode()
516 VNInfo *DestVNI = LR->getVNInfoAt(NewStart); in LowerPHINode()
517 assert(DestVNI && "PHI destination should be live at its definition."); in LowerPHINode()
518 DestVNI->def = NewStart; in LowerPHINode()
524 for (unsigned i = 1; i != MPhi->getNumOperands(); i += 2) { in LowerPHINode()
525 if (!MPhi->getOperand(i).isUndef()) { in LowerPHINode()
526 --VRegPHIUseCount[BBVRegPair( in LowerPHINode()
527 MPhi->getOperand(i + 1).getMBB()->getNumber(), in LowerPHINode()
528 MPhi->getOperand(i).getReg())]; in LowerPHINode()
536 for (int i = NumSrcs - 1; i >= 0; --i) { in LowerPHINode()
537 Register SrcReg = MPhi->getOperand(i * 2 + 1).getReg(); in LowerPHINode()
538 unsigned SrcSubReg = MPhi->getOperand(i * 2 + 1).getSubReg(); in LowerPHINode()
539 bool SrcUndef = MPhi->getOperand(i * 2 + 1).isUndef() || in LowerPHINode()
546 MachineBasicBlock &opBlock = *MPhi->getOperand(i * 2 + 2).getMBB(); in LowerPHINode()
554 MachineInstr *SrcRegDef = MRI->getVRegDef(SrcReg); in LowerPHINode()
555 if (SrcRegDef && TII->isUnspillableTerminator(SrcRegDef)) { in LowerPHINode()
556 assert(SrcRegDef->getOperand(0).isReg() && in LowerPHINode()
557 SrcRegDef->getOperand(0).isDef() && in LowerPHINode()
561 assert(MRI->use_empty(SrcReg) && in LowerPHINode()
563 SrcRegDef->getOperand(0).setReg(IncomingReg); in LowerPHINode()
567 LiveVariables::VarInfo &SrcVI = LV->getVarInfo(SrcReg); in LowerPHINode()
568 LiveVariables::VarInfo &IncomingVI = LV->getVarInfo(IncomingReg); in LowerPHINode()
589 BuildMI(opBlock, InsertPos, MPhi->getDebugLoc(), in LowerPHINode()
590 TII->get(TargetOpcode::IMPLICIT_DEF), IncomingReg); in LowerPHINode()
592 // Clean up the old implicit-def, if there even was one. in LowerPHINode()
593 if (MachineInstr *DefMI = MRI->getVRegDef(SrcReg)) in LowerPHINode()
594 if (DefMI->isImplicitDef()) in LowerPHINode()
599 NewSrcInstr = TII->createPHISourceCopy(opBlock, InsertPos, nullptr, in LowerPHINode()
605 // last PHI use of SrcReg to be lowered on this CFG edge and it is not live in LowerPHINode()
609 !LV->isLiveOut(SrcReg, opBlock)) { in LowerPHINode()
611 // the copy we just inserted) is the last use of the source value. Live in LowerPHINode()
613 // is live until the end of the block the PHI entry lives in. If the value in LowerPHINode()
615 // have the value live-in. in LowerPHINode()
617 // Okay, if we now know that the value is not live out of the block, we in LowerPHINode()
629 if (Term->readsRegister(SrcReg, /*TRI=*/nullptr)) in LowerPHINode()
640 --KillInst; in LowerPHINode()
641 if (KillInst->isDebugInstr()) in LowerPHINode()
643 if (KillInst->readsRegister(SrcReg, /*TRI=*/nullptr)) in LowerPHINode()
651 assert(KillInst->readsRegister(SrcReg, /*TRI=*/nullptr) && in LowerPHINode()
655 LV->addVirtualRegisterKilled(SrcReg, *KillInst); in LowerPHINode()
659 LV->getVarInfo(SrcReg).AliveBlocks.reset(opBlockNum); in LowerPHINode()
664 LIS->InsertMachineInstrInMaps(*NewSrcInstr); in LowerPHINode()
665 LIS->addSegmentToEndOfBlock(IncomingReg, *NewSrcInstr); in LowerPHINode()
670 LiveInterval &SrcLI = LIS->getInterval(SrcReg); in LowerPHINode()
674 SlotIndex startIdx = LIS->getMBBStartIdx(Succ); in LowerPHINode()
677 // Definitions by other PHIs are not truly live-in for our purposes. in LowerPHINode()
678 if (VNI && VNI->def != startIdx) { in LowerPHINode()
688 if (Term->readsRegister(SrcReg, /*TRI=*/nullptr)) in LowerPHINode()
699 --KillInst; in LowerPHINode()
700 if (KillInst->isDebugInstr()) in LowerPHINode()
702 if (KillInst->readsRegister(SrcReg, /*TRI=*/nullptr)) in LowerPHINode()
710 assert(KillInst->readsRegister(SrcReg, /*TRI=*/nullptr) && in LowerPHINode()
713 SlotIndex LastUseIndex = LIS->getInstructionIndex(*KillInst); in LowerPHINode()
715 LIS->getMBBEndIdx(&opBlock)); in LowerPHINode()
718 LIS->getMBBEndIdx(&opBlock)); in LowerPHINode()
728 LIS->RemoveMachineInstrFromMaps(*MPhi); in LowerPHINode()
733 /// analyzePHINodes - Gather information about the PHI nodes in here. In
745 BBI.getOperand(i + 1).getMBB()->getNumber(), in analyzePHINodes()
759 const MachineLoop *CurLoop = MLI ? MLI->getLoopFor(&MBB) : nullptr; in SplitPHIEdges()
760 bool IsLoopHeader = CurLoop && &MBB == CurLoop->getHeader(); in SplitPHIEdges()
764 BBI != BBE && BBI->isPHI(); ++BBI) { in SplitPHIEdges()
765 for (unsigned i = 1, e = BBI->getNumOperands(); i != e; i += 2) { in SplitPHIEdges()
766 Register Reg = BBI->getOperand(i).getReg(); in SplitPHIEdges()
767 MachineBasicBlock *PreMBB = BBI->getOperand(i + 1).getMBB(); in SplitPHIEdges()
769 if (PreMBB->succ_size() == 1) in SplitPHIEdges()
773 // out-of-line blocks into the loop which is very bad for code placement. in SplitPHIEdges()
776 const MachineLoop *PreLoop = MLI ? MLI->getLoopFor(PreMBB) : nullptr; in SplitPHIEdges()
780 // LV doesn't consider a phi use live-out, so isLiveOut only returns true in SplitPHIEdges()
781 // when the source register is live-out for some other reason than a phi in SplitPHIEdges()
790 LLVM_DEBUG(dbgs() << printReg(Reg) << " live-out before critical edge " in SplitPHIEdges()
791 << printMBBReference(*PreMBB) << " -> " in SplitPHIEdges()
795 // If Reg is not live-in to MBB, it means it must be live-in to some in SplitPHIEdges()
799 // If Reg *is* live-in to MBB, the interference is inevitable and a copy in SplitPHIEdges()
818 ShouldSplit = PreLoop && !PreLoop->contains(CurLoop); in SplitPHIEdges()
822 if (!(P ? PreMBB->SplitCriticalEdge(&MBB, *P, LiveInSets) in SplitPHIEdges()
823 : PreMBB->SplitCriticalEdge(&MBB, *MFAM, LiveInSets))) { in SplitPHIEdges()
838 return LIS->isLiveInToMBB(LIS->getInterval(Reg), MBB); in isLiveIn()
840 return LV->isLiveIn(Reg, *MBB); in isLiveIn()
848 // so that a register used only in a PHI is not live out of the block. In in isLiveOutPastPHIs()
851 // is live out of the block. in isLiveOutPastPHIs()
853 const LiveInterval &LI = LIS->getInterval(Reg); in isLiveOutPastPHIs()
854 for (const MachineBasicBlock *SI : MBB->successors()) in isLiveOutPastPHIs()
855 if (LI.liveAt(LIS->getMBBStartIdx(SI))) in isLiveOutPastPHIs()
859 return LV->isLiveOut(Reg, *MBB); in isLiveOutPastPHIs()