Lines Matching +full:block +full:- +full:copy
1 //===- PhiElimination.cpp - Eliminate PHI nodes by inserting copies -------===//
5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
7 //===----------------------------------------------------------------------===//
9 // This pass eliminates machine instruction PHI nodes by inserting copy
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>();
120 auto *LISWrapper = P->getAnalysisIfAvailable<LiveIntervalsWrapperPass>();
121 auto *MLIWrapper = P->getAnalysisIfAvailable<MachineLoopInfoWrapperPass>();
123 P->getAnalysisIfAvailable<MachineDominatorTreeWrapperPass>();
124 LV = LVWrapper ? &LVWrapper->getLV() : nullptr;
125 LIS = LISWrapper ? &LISWrapper->getLIS() : nullptr;
126 MLI = MLIWrapper ? &MLIWrapper->getLI() : nullptr;
127 MDT = MDTWrapper ? &MDTWrapper->getDomTree() : nullptr;
210 // A set of live-in regs for each MBB which is used to update LV
215 for (unsigned Index = 0, e = MRI->getNumVirtRegs(); Index != e; ++Index) {
217 // live-through or live-in (killed).
219 MachineInstr *DefMI = MRI->getVRegDef(VirtReg);
222 LiveVariables::VarInfo &VI = LV->getVarInfo(VirtReg);
231 MachineBasicBlock *DefMBB = DefMI->getParent();
233 (!VI.Kills.empty() && VI.Kills.front()->getParent() != DefMBB))
235 LiveInSets[MI->getParent()->getNumber()].set(Index);
244 MRI->leaveSSA();
256 Register DefReg = DefMI->getOperand(0).getReg();
257 if (MRI->use_nodbg_empty(DefReg)) {
259 LIS->RemoveMachineInstrFromMaps(*DefMI);
260 DefMI->eraseFromParent();
267 LIS->RemoveMachineInstrFromMaps(*I.first);
273 MDT->getBase().recalculate(MF);
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
298 // as a successor (=> identical PHI node can't occur in different block).
301 if (Pred->succ_size() < 2) {
313 /// Return true if all defs of VirtReg are implicit-defs.
333 /// LowerPHINode - Lower the PHI node at the top of the specified block.
341 // Unlink the PHI node from the basic block, but don't delete the PHI yet.
344 unsigned NumSrcs = (MPhi->getNumOperands() - 1) / 2;
345 Register DestReg = MPhi->getOperand(0).getReg();
346 assert(MPhi->getOperand(0).getSubReg() == 0 && "Can't handle sub-reg PHIs");
347 bool isDead = MPhi->getOperand(0).isDead();
355 // Insert a register to register copy at the top of the current block (but
362 // implicit_def instead of a copy.
363 PHICopy = BuildMI(MBB, AfterPHIsIt, MPhi->getDebugLoc(),
364 TII->get(TargetOpcode::IMPLICIT_DEF), DestReg);
390 PHICopy = TII->createPHIDestinationCopy(
391 MBB, AfterPHIsIt, MPhi->getDebugLoc(), IncomingReg, DestReg);
394 if (MPhi->peekDebugInstrNum()) {
395 // If referred to by debug-info, store where this PHI was.
397 unsigned ID = MPhi->peekDebugInstrNum();
399 auto Res = MF->DebugPHIPositions.insert({ID, P});
407 LiveVariables::VarInfo &VI = LV->getVarInfo(IncomingReg);
414 // In general, the PHICopy is inserted as the first non-phi instruction
435 LV->removeVirtualRegisterKilled(IncomingReg, *OldKill);
442 // (once each for each incoming block), the "def" block and instruction
445 LV->addVirtualRegisterKilled(IncomingReg, *PHICopy);
450 // information over to the new copy we just inserted.
451 LV->removeVirtualRegistersKilled(*MPhi);
455 LV->addVirtualRegisterDead(DestReg, *PHICopy);
456 LV->removeVirtualRegisterDead(DestReg, *MPhi);
460 // Update LiveIntervals for the new copy or implicit def.
462 SlotIndex DestCopyIndex = LIS->InsertMachineInstrInMaps(*PHICopy);
464 SlotIndex MBBStartIndex = LIS->getMBBStartIdx(&MBB);
466 // Add the region from the beginning of MBB to the copy instruction to
468 LiveInterval &IncomingLI = LIS->getOrCreateEmptyInterval(IncomingReg);
472 IncomingLI.getNextValue(MBBStartIndex, LIS->getVNInfoAllocator());
477 LiveInterval &DestLI = LIS->getInterval(DestReg);
478 assert(!DestLI.empty() && "PHIs should have non-empty LiveIntervals.");
487 auto DestSegment = LR->find(MBBStartIndex);
488 assert(DestSegment != LR->end() &&
489 "PHI destination must be live in block");
491 if (LR->endIndex().isDead()) {
493 // the lowered copy, which will still be dead, needs to begin and end at
494 // the copy instruction.
495 VNInfo *OrigDestVNI = LR->getVNInfoAt(DestSegment->start);
496 assert(OrigDestVNI && "PHI destination should be live at block entry.");
497 LR->removeSegment(DestSegment->start, DestSegment->start.getDeadSlot());
498 LR->createDeadDef(NewStart, LIS->getVNInfoAllocator());
499 LR->removeValNo(OrigDestVNI);
505 // to match the actual slot index of the copy.
506 if (DestSegment->start > NewStart) {
507 VNInfo *VNI = LR->getVNInfoAt(DestSegment->start);
509 LR->addSegment(
510 LiveInterval::Segment(NewStart, DestSegment->start, VNI));
511 } else if (DestSegment->start < NewStart) {
512 assert(DestSegment->start >= MBBStartIndex);
513 assert(DestSegment->end >= DestCopyIndex.getRegSlot());
514 LR->removeSegment(DestSegment->start, NewStart);
516 VNInfo *DestVNI = LR->getVNInfoAt(NewStart);
518 DestVNI->def = NewStart;
524 for (unsigned i = 1; i != MPhi->getNumOperands(); i += 2) {
525 if (!MPhi->getOperand(i).isUndef()) {
526 --VRegPHIUseCount[BBVRegPair(
527 MPhi->getOperand(i + 1).getMBB()->getNumber(),
528 MPhi->getOperand(i).getReg())];
533 // Now loop over all of the incoming arguments, changing them to copy into the
534 // IncomingReg register in the corresponding predecessor basic block.
536 for (int i = NumSrcs - 1; i >= 0; --i) {
537 Register SrcReg = MPhi->getOperand(i * 2 + 1).getReg();
538 unsigned SrcSubReg = MPhi->getOperand(i * 2 + 1).getSubReg();
539 bool SrcUndef = MPhi->getOperand(i * 2 + 1).isUndef() ||
546 MachineBasicBlock &opBlock = *MPhi->getOperand(i * 2 + 2).getMBB();
548 // Check to make sure we haven't already emitted the copy for this block.
550 // basic block.
552 continue; // If the copy has already been emitted, we're done.
554 MachineInstr *SrcRegDef = MRI->getVRegDef(SrcReg);
555 if (SrcRegDef && TII->isUnspillableTerminator(SrcRegDef)) {
556 assert(SrcRegDef->getOperand(0).isReg() &&
557 SrcRegDef->getOperand(0).isDef() &&
561 assert(MRI->use_empty(SrcReg) &&
563 SrcRegDef->getOperand(0).setReg(IncomingReg);
567 LiveVariables::VarInfo &SrcVI = LV->getVarInfo(SrcReg);
568 LiveVariables::VarInfo &IncomingVI = LV->getVarInfo(IncomingReg);
576 // Find a safe location to insert the copy, this may be the first terminator
577 // in the block (or end()).
581 // Insert the copy.
586 // COPY, but we still need to ensure joint dominance by defs.
589 BuildMI(opBlock, InsertPos, MPhi->getDebugLoc(),
590 TII->get(TargetOpcode::IMPLICIT_DEF), IncomingReg);
592 // Clean up the old implicit-def, if there even was one.
593 if (MachineInstr *DefMI = MRI->getVRegDef(SrcReg))
594 if (DefMI->isImplicitDef())
597 // Delete the debug location, since the copy is inserted into a
598 // different basic block.
599 NewSrcInstr = TII->createPHISourceCopy(opBlock, InsertPos, nullptr,
609 !LV->isLiveOut(SrcReg, opBlock)) {
611 // the copy we just inserted) is the last use of the source value. Live
613 // is live until the end of the block the PHI entry lives in. If the value
614 // really is dead at the PHI copy, there will be no successor blocks which
615 // have the value live-in.
617 // Okay, if we now know that the value is not live out of the block, we
618 // can add a kill marker in this block saying that it kills the incoming
622 // register. In most cases this is the copy, however, terminator
623 // instructions at the end of the block may also use the value. In this
625 // block, not the copy.
629 if (Term->readsRegister(SrcReg, /*TRI=*/nullptr))
637 // We may have to rewind a bit if we didn't insert a copy this time.
640 --KillInst;
641 if (KillInst->isDebugInstr())
643 if (KillInst->readsRegister(SrcReg, /*TRI=*/nullptr))
647 // We just inserted this copy.
651 assert(KillInst->readsRegister(SrcReg, /*TRI=*/nullptr) &&
655 LV->addVirtualRegisterKilled(SrcReg, *KillInst);
659 LV->getVarInfo(SrcReg).AliveBlocks.reset(opBlockNum);
664 LIS->InsertMachineInstrInMaps(*NewSrcInstr);
665 LIS->addSegmentToEndOfBlock(IncomingReg, *NewSrcInstr);
670 LiveInterval &SrcLI = LIS->getInterval(SrcReg);
674 SlotIndex startIdx = LIS->getMBBStartIdx(Succ);
677 // Definitions by other PHIs are not truly live-in for our purposes.
678 if (VNI && VNI->def != startIdx) {
688 if (Term->readsRegister(SrcReg, /*TRI=*/nullptr))
696 // We may have to rewind a bit if we didn't just insert a copy.
699 --KillInst;
700 if (KillInst->isDebugInstr())
702 if (KillInst->readsRegister(SrcReg, /*TRI=*/nullptr))
706 // We just inserted this copy.
710 assert(KillInst->readsRegister(SrcReg, /*TRI=*/nullptr) &&
713 SlotIndex LastUseIndex = LIS->getInstructionIndex(*KillInst);
715 LIS->getMBBEndIdx(&opBlock));
718 LIS->getMBBEndIdx(&opBlock));
728 LIS->RemoveMachineInstrFromMaps(*MPhi);
733 /// analyzePHINodes - Gather information about the PHI nodes in here. In
745 BBI.getOperand(i + 1).getMBB()->getNumber(),
759 const MachineLoop *CurLoop = MLI ? MLI->getLoopFor(&MBB) : nullptr;
760 bool IsLoopHeader = CurLoop && &MBB == CurLoop->getHeader();
764 BBI != BBE && BBI->isPHI(); ++BBI) {
765 for (unsigned i = 1, e = BBI->getNumOperands(); i != e; i += 2) {
766 Register Reg = BBI->getOperand(i).getReg();
767 MachineBasicBlock *PreMBB = BBI->getOperand(i + 1).getMBB();
769 if (PreMBB->succ_size() == 1)
773 // out-of-line blocks into the loop which is very bad for code placement.
776 const MachineLoop *PreLoop = MLI ? MLI->getLoopFor(PreMBB) : nullptr;
780 // LV doesn't consider a phi use live-out, so isLiveOut only returns true
781 // when the source register is live-out for some other reason than a phi
782 // use. That means the copy we will insert in PreMBB won't be a kill, and
785 // If the copy would be a kill, there is no need to split the edge.
790 LLVM_DEBUG(dbgs() << printReg(Reg) << " live-out before critical edge "
791 << printMBBReference(*PreMBB) << " -> "
795 // If Reg is not live-in to MBB, it means it must be live-in to some
799 // If Reg *is* live-in to MBB, the interference is inevitable and a copy
818 ShouldSplit = PreLoop && !PreLoop->contains(CurLoop);
822 if (!(P ? PreMBB->SplitCriticalEdge(&MBB, *P, LiveInSets)
823 : PreMBB->SplitCriticalEdge(&MBB, *MFAM, LiveInSets))) {
838 return LIS->isLiveInToMBB(LIS->getInterval(Reg), MBB);
840 return LV->isLiveIn(Reg, *MBB);
847 // LiveVariables considers uses in PHIs to be in the predecessor basic block,
848 // so that a register used only in a PHI is not live out of the block. In
850 // than in the predecessor basic block, so that a register used only in a PHI
851 // is live out of the block.
853 const LiveInterval &LI = LIS->getInterval(Reg);
854 for (const MachineBasicBlock *SI : MBB->successors())
855 if (LI.liveAt(LIS->getMBBStartIdx(SI)))
859 return LV->isLiveOut(Reg, *MBB);