872 lines · cpp
1//===- PhiElimination.cpp - Eliminate PHI nodes by inserting copies -------===//2//3// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.4// See https://llvm.org/LICENSE.txt for license information.5// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception6//7//===----------------------------------------------------------------------===//8//9// This pass eliminates machine instruction PHI nodes by inserting copy10// instructions. This destroys SSA information, but is the desired input for11// some register allocators.12//13//===----------------------------------------------------------------------===//14 15#include "llvm/CodeGen/PHIElimination.h"16#include "PHIEliminationUtils.h"17#include "llvm/ADT/DenseMap.h"18#include "llvm/ADT/SmallPtrSet.h"19#include "llvm/ADT/Statistic.h"20#include "llvm/Analysis/LoopInfo.h"21#include "llvm/CodeGen/LiveInterval.h"22#include "llvm/CodeGen/LiveIntervals.h"23#include "llvm/CodeGen/LiveVariables.h"24#include "llvm/CodeGen/MachineBasicBlock.h"25#include "llvm/CodeGen/MachineDomTreeUpdater.h"26#include "llvm/CodeGen/MachineDominators.h"27#include "llvm/CodeGen/MachineFunction.h"28#include "llvm/CodeGen/MachineFunctionPass.h"29#include "llvm/CodeGen/MachineInstr.h"30#include "llvm/CodeGen/MachineInstrBuilder.h"31#include "llvm/CodeGen/MachineLoopInfo.h"32#include "llvm/CodeGen/MachineOperand.h"33#include "llvm/CodeGen/MachinePostDominators.h"34#include "llvm/CodeGen/MachineRegisterInfo.h"35#include "llvm/CodeGen/SlotIndexes.h"36#include "llvm/CodeGen/TargetInstrInfo.h"37#include "llvm/CodeGen/TargetOpcodes.h"38#include "llvm/CodeGen/TargetRegisterInfo.h"39#include "llvm/CodeGen/TargetSubtargetInfo.h"40#include "llvm/Pass.h"41#include "llvm/Support/CommandLine.h"42#include "llvm/Support/Debug.h"43#include "llvm/Support/raw_ostream.h"44#include <cassert>45#include <iterator>46#include <utility>47 48using namespace llvm;49 50#define DEBUG_TYPE "phi-node-elimination"51 52static cl::opt<bool>53 DisableEdgeSplitting("disable-phi-elim-edge-splitting", cl::init(false),54 cl::Hidden,55 cl::desc("Disable critical edge splitting "56 "during PHI elimination"));57 58static cl::opt<bool>59 SplitAllCriticalEdges("phi-elim-split-all-critical-edges", cl::init(false),60 cl::Hidden,61 cl::desc("Split all critical edges during "62 "PHI elimination"));63 64static cl::opt<bool> NoPhiElimLiveOutEarlyExit(65 "no-phi-elim-live-out-early-exit", cl::init(false), cl::Hidden,66 cl::desc("Do not use an early exit if isLiveOutPastPHIs returns true."));67 68namespace {69 70class PHIEliminationImpl {71 MachineRegisterInfo *MRI = nullptr; // Machine register information72 LiveVariables *LV = nullptr;73 LiveIntervals *LIS = nullptr;74 MachineLoopInfo *MLI = nullptr;75 MachineDominatorTree *MDT = nullptr;76 MachinePostDominatorTree *PDT = nullptr;77 78 /// EliminatePHINodes - Eliminate phi nodes by inserting copy instructions79 /// in predecessor basic blocks.80 bool EliminatePHINodes(MachineFunction &MF, MachineBasicBlock &MBB);81 82 void LowerPHINode(MachineBasicBlock &MBB,83 MachineBasicBlock::iterator LastPHIIt,84 bool AllEdgesCritical);85 86 /// analyzePHINodes - Gather information about the PHI nodes in87 /// here. In particular, we want to map the number of uses of a virtual88 /// register which is used in a PHI node. We map that to the BB the89 /// vreg is coming from. This is used later to determine when the vreg90 /// is killed in the BB.91 void analyzePHINodes(const MachineFunction &MF);92 93 /// Split critical edges where necessary for good coalescer performance.94 bool SplitPHIEdges(MachineFunction &MF, MachineBasicBlock &MBB,95 MachineLoopInfo *MLI,96 std::vector<SparseBitVector<>> *LiveInSets,97 MachineDomTreeUpdater &MDTU);98 99 // These functions are temporary abstractions around LiveVariables and100 // LiveIntervals, so they can go away when LiveVariables does.101 bool isLiveIn(Register Reg, const MachineBasicBlock *MBB);102 bool isLiveOutPastPHIs(Register Reg, const MachineBasicBlock *MBB);103 104 using BBVRegPair = std::pair<unsigned, Register>;105 using VRegPHIUse = DenseMap<BBVRegPair, unsigned>;106 107 // Count the number of non-undef PHI uses of each register in each BB.108 VRegPHIUse VRegPHIUseCount;109 110 // Defs of PHI sources which are implicit_def.111 SmallPtrSet<MachineInstr *, 4> ImpDefs;112 113 // Map reusable lowered PHI node -> incoming join register.114 using LoweredPHIMap =115 DenseMap<MachineInstr *, Register, MachineInstrExpressionTrait>;116 LoweredPHIMap LoweredPHIs;117 118 MachineFunctionPass *P = nullptr;119 MachineFunctionAnalysisManager *MFAM = nullptr;120 121public:122 PHIEliminationImpl(MachineFunctionPass *P) : P(P) {123 auto *LVWrapper = P->getAnalysisIfAvailable<LiveVariablesWrapperPass>();124 auto *LISWrapper = P->getAnalysisIfAvailable<LiveIntervalsWrapperPass>();125 auto *MLIWrapper = P->getAnalysisIfAvailable<MachineLoopInfoWrapperPass>();126 auto *MDTWrapper =127 P->getAnalysisIfAvailable<MachineDominatorTreeWrapperPass>();128 auto *PDTWrapper =129 P->getAnalysisIfAvailable<MachinePostDominatorTreeWrapperPass>();130 LV = LVWrapper ? &LVWrapper->getLV() : nullptr;131 LIS = LISWrapper ? &LISWrapper->getLIS() : nullptr;132 MLI = MLIWrapper ? &MLIWrapper->getLI() : nullptr;133 MDT = MDTWrapper ? &MDTWrapper->getDomTree() : nullptr;134 PDT = PDTWrapper ? &PDTWrapper->getPostDomTree() : nullptr;135 }136 137 PHIEliminationImpl(MachineFunction &MF, MachineFunctionAnalysisManager &AM)138 : LV(AM.getCachedResult<LiveVariablesAnalysis>(MF)),139 LIS(AM.getCachedResult<LiveIntervalsAnalysis>(MF)),140 MLI(AM.getCachedResult<MachineLoopAnalysis>(MF)),141 MDT(AM.getCachedResult<MachineDominatorTreeAnalysis>(MF)),142 PDT(AM.getCachedResult<MachinePostDominatorTreeAnalysis>(MF)),143 MFAM(&AM) {}144 145 bool run(MachineFunction &MF);146};147 148class PHIElimination : public MachineFunctionPass {149public:150 static char ID; // Pass identification, replacement for typeid151 152 PHIElimination() : MachineFunctionPass(ID) {153 initializePHIEliminationPass(*PassRegistry::getPassRegistry());154 }155 156 bool runOnMachineFunction(MachineFunction &MF) override {157 PHIEliminationImpl Impl(this);158 return Impl.run(MF);159 }160 161 MachineFunctionProperties getSetProperties() const override {162 return MachineFunctionProperties().setNoPHIs();163 }164 165 void getAnalysisUsage(AnalysisUsage &AU) const override;166};167 168} // end anonymous namespace169 170PreservedAnalyses171PHIEliminationPass::run(MachineFunction &MF,172 MachineFunctionAnalysisManager &MFAM) {173 PHIEliminationImpl Impl(MF, MFAM);174 bool Changed = Impl.run(MF);175 if (!Changed)176 return PreservedAnalyses::all();177 auto PA = getMachineFunctionPassPreservedAnalyses();178 PA.preserve<LiveIntervalsAnalysis>();179 PA.preserve<LiveVariablesAnalysis>();180 PA.preserve<SlotIndexesAnalysis>();181 PA.preserve<MachineDominatorTreeAnalysis>();182 PA.preserve<MachinePostDominatorTreeAnalysis>();183 PA.preserve<MachineLoopAnalysis>();184 return PA;185}186 187STATISTIC(NumLowered, "Number of phis lowered");188STATISTIC(NumCriticalEdgesSplit, "Number of critical edges split");189STATISTIC(NumReused, "Number of reused lowered phis");190 191char PHIElimination::ID = 0;192 193char &llvm::PHIEliminationID = PHIElimination::ID;194 195INITIALIZE_PASS_BEGIN(PHIElimination, DEBUG_TYPE,196 "Eliminate PHI nodes for register allocation", false,197 false)198INITIALIZE_PASS_DEPENDENCY(LiveVariablesWrapperPass)199INITIALIZE_PASS_END(PHIElimination, DEBUG_TYPE,200 "Eliminate PHI nodes for register allocation", false, false)201 202void PHIElimination::getAnalysisUsage(AnalysisUsage &AU) const {203 AU.addUsedIfAvailable<LiveVariablesWrapperPass>();204 AU.addPreserved<LiveVariablesWrapperPass>();205 AU.addPreserved<SlotIndexesWrapperPass>();206 AU.addPreserved<LiveIntervalsWrapperPass>();207 AU.addPreserved<MachineDominatorTreeWrapperPass>();208 AU.addPreserved<MachinePostDominatorTreeWrapperPass>();209 AU.addPreserved<MachineLoopInfoWrapperPass>();210 MachineFunctionPass::getAnalysisUsage(AU);211}212 213bool PHIEliminationImpl::run(MachineFunction &MF) {214 MRI = &MF.getRegInfo();215 216 MachineDomTreeUpdater MDTU(MDT, PDT,217 MachineDomTreeUpdater::UpdateStrategy::Lazy);218 219 bool Changed = false;220 221 // Split critical edges to help the coalescer.222 if (!DisableEdgeSplitting && (LV || LIS)) {223 // A set of live-in regs for each MBB which is used to update LV224 // efficiently also with large functions.225 std::vector<SparseBitVector<>> LiveInSets;226 if (LV) {227 LiveInSets.resize(MF.size());228 for (unsigned Index = 0, e = MRI->getNumVirtRegs(); Index != e; ++Index) {229 // Set the bit for this register for each MBB where it is230 // live-through or live-in (killed).231 Register VirtReg = Register::index2VirtReg(Index);232 MachineInstr *DefMI = MRI->getVRegDef(VirtReg);233 if (!DefMI)234 continue;235 LiveVariables::VarInfo &VI = LV->getVarInfo(VirtReg);236 SparseBitVector<>::iterator AliveBlockItr = VI.AliveBlocks.begin();237 SparseBitVector<>::iterator EndItr = VI.AliveBlocks.end();238 while (AliveBlockItr != EndItr) {239 unsigned BlockNum = *(AliveBlockItr++);240 LiveInSets[BlockNum].set(Index);241 }242 // The register is live into an MBB in which it is killed but not243 // defined. See comment for VarInfo in LiveVariables.h.244 MachineBasicBlock *DefMBB = DefMI->getParent();245 if (VI.Kills.size() > 1 ||246 (!VI.Kills.empty() && VI.Kills.front()->getParent() != DefMBB))247 for (auto *MI : VI.Kills)248 LiveInSets[MI->getParent()->getNumber()].set(Index);249 }250 }251 252 for (auto &MBB : MF)253 Changed |=254 SplitPHIEdges(MF, MBB, MLI, (LV ? &LiveInSets : nullptr), MDTU);255 }256 257 // This pass takes the function out of SSA form.258 MRI->leaveSSA();259 260 // Populate VRegPHIUseCount261 if (LV || LIS)262 analyzePHINodes(MF);263 264 // Eliminate PHI instructions by inserting copies into predecessor blocks.265 for (auto &MBB : MF)266 Changed |= EliminatePHINodes(MF, MBB);267 268 // Remove dead IMPLICIT_DEF instructions.269 for (MachineInstr *DefMI : ImpDefs) {270 Register DefReg = DefMI->getOperand(0).getReg();271 if (MRI->use_nodbg_empty(DefReg)) {272 if (LIS)273 LIS->RemoveMachineInstrFromMaps(*DefMI);274 DefMI->eraseFromParent();275 }276 }277 278 // Clean up the lowered PHI instructions.279 for (auto &I : LoweredPHIs) {280 if (LIS)281 LIS->RemoveMachineInstrFromMaps(*I.first);282 MF.deleteMachineInstr(I.first);283 }284 285 LoweredPHIs.clear();286 ImpDefs.clear();287 VRegPHIUseCount.clear();288 289 MF.getProperties().setNoPHIs();290 291 return Changed;292}293 294/// EliminatePHINodes - Eliminate phi nodes by inserting copy instructions in295/// predecessor basic blocks.296bool PHIEliminationImpl::EliminatePHINodes(MachineFunction &MF,297 MachineBasicBlock &MBB) {298 if (MBB.empty() || !MBB.front().isPHI())299 return false; // Quick exit for basic blocks without PHIs.300 301 // Get an iterator to the last PHI node.302 MachineBasicBlock::iterator LastPHIIt =303 std::prev(MBB.SkipPHIsAndLabels(MBB.begin()));304 305 // If all incoming edges are critical, we try to deduplicate identical PHIs so306 // that we generate fewer copies. If at any edge is non-critical, we either307 // have less than two predecessors (=> no PHIs) or a predecessor has only us308 // as a successor (=> identical PHI node can't occur in different block).309 bool AllEdgesCritical = MBB.pred_size() >= 2;310 for (MachineBasicBlock *Pred : MBB.predecessors()) {311 if (Pred->succ_size() < 2) {312 AllEdgesCritical = false;313 break;314 }315 }316 317 while (MBB.front().isPHI())318 LowerPHINode(MBB, LastPHIIt, AllEdgesCritical);319 320 return true;321}322 323/// Return true if all defs of VirtReg are implicit-defs.324/// This includes registers with no defs.325static bool isImplicitlyDefined(Register VirtReg,326 const MachineRegisterInfo &MRI) {327 for (MachineInstr &DI : MRI.def_instructions(VirtReg))328 if (!DI.isImplicitDef())329 return false;330 return true;331}332 333/// Return true if all sources of the phi node are implicit_def's, or undef's.334static bool allPhiOperandsUndefined(const MachineInstr &MPhi,335 const MachineRegisterInfo &MRI) {336 for (unsigned I = 1, E = MPhi.getNumOperands(); I != E; I += 2) {337 const MachineOperand &MO = MPhi.getOperand(I);338 if (!isImplicitlyDefined(MO.getReg(), MRI) && !MO.isUndef())339 return false;340 }341 return true;342}343/// LowerPHINode - Lower the PHI node at the top of the specified block.344void PHIEliminationImpl::LowerPHINode(MachineBasicBlock &MBB,345 MachineBasicBlock::iterator LastPHIIt,346 bool AllEdgesCritical) {347 ++NumLowered;348 349 MachineBasicBlock::iterator AfterPHIsIt = std::next(LastPHIIt);350 351 // Unlink the PHI node from the basic block, but don't delete the PHI yet.352 MachineInstr *MPhi = MBB.remove(&*MBB.begin());353 354 unsigned NumSrcs = (MPhi->getNumOperands() - 1) / 2;355 Register DestReg = MPhi->getOperand(0).getReg();356 assert(MPhi->getOperand(0).getSubReg() == 0 && "Can't handle sub-reg PHIs");357 bool isDead = MPhi->getOperand(0).isDead();358 359 // Create a new register for the incoming PHI arguments.360 MachineFunction &MF = *MBB.getParent();361 Register IncomingReg;362 bool EliminateNow = true; // delay elimination of nodes in LoweredPHIs363 bool reusedIncoming = false; // Is IncomingReg reused from an earlier PHI?364 365 // Insert a register to register copy at the top of the current block (but366 // after any remaining phi nodes) which copies the new incoming register367 // into the phi node destination.368 MachineInstr *PHICopy = nullptr;369 const TargetInstrInfo *TII = MF.getSubtarget().getInstrInfo();370 if (allPhiOperandsUndefined(*MPhi, *MRI))371 // If all sources of a PHI node are implicit_def or undef uses, just emit an372 // implicit_def instead of a copy.373 PHICopy = BuildMI(MBB, AfterPHIsIt, MPhi->getDebugLoc(),374 TII->get(TargetOpcode::IMPLICIT_DEF), DestReg);375 else {376 // Can we reuse an earlier PHI node? This only happens for critical edges,377 // typically those created by tail duplication. Typically, an identical PHI378 // node can't occur, so avoid hashing/storing such PHIs, which is somewhat379 // expensive.380 Register *Entry = nullptr;381 if (AllEdgesCritical)382 Entry = &LoweredPHIs[MPhi];383 if (Entry && *Entry) {384 // An identical PHI node was already lowered. Reuse the incoming register.385 IncomingReg = *Entry;386 reusedIncoming = true;387 ++NumReused;388 LLVM_DEBUG(dbgs() << "Reusing " << printReg(IncomingReg) << " for "389 << *MPhi);390 } else {391 const TargetRegisterClass *RC = MF.getRegInfo().getRegClass(DestReg);392 IncomingReg = MF.getRegInfo().createVirtualRegister(RC);393 if (Entry) {394 EliminateNow = false;395 *Entry = IncomingReg;396 }397 }398 399 // Give the target possiblity to handle special cases fallthrough otherwise400 PHICopy = TII->createPHIDestinationCopy(401 MBB, AfterPHIsIt, MPhi->getDebugLoc(), IncomingReg, DestReg);402 }403 404 if (MPhi->peekDebugInstrNum()) {405 // If referred to by debug-info, store where this PHI was.406 MachineFunction *MF = MBB.getParent();407 unsigned ID = MPhi->peekDebugInstrNum();408 auto P = MachineFunction::DebugPHIRegallocPos(&MBB, IncomingReg, 0);409 auto Res = MF->DebugPHIPositions.insert({ID, P});410 assert(Res.second);411 (void)Res;412 }413 414 // Update live variable information if there is any.415 if (LV) {416 if (IncomingReg) {417 LiveVariables::VarInfo &VI = LV->getVarInfo(IncomingReg);418 419 MachineInstr *OldKill = nullptr;420 bool IsPHICopyAfterOldKill = false;421 422 if (reusedIncoming && (OldKill = VI.findKill(&MBB))) {423 // Calculate whether the PHICopy is after the OldKill.424 // In general, the PHICopy is inserted as the first non-phi instruction425 // by default, so it's before the OldKill. But some Target hooks for426 // createPHIDestinationCopy() may modify the default insert position of427 // PHICopy.428 for (auto I = MBB.SkipPHIsAndLabels(MBB.begin()), E = MBB.end(); I != E;429 ++I) {430 if (I == PHICopy)431 break;432 433 if (I == OldKill) {434 IsPHICopyAfterOldKill = true;435 break;436 }437 }438 }439 440 // When we are reusing the incoming register and it has been marked killed441 // by OldKill, if the PHICopy is after the OldKill, we should remove the442 // killed flag from OldKill.443 if (IsPHICopyAfterOldKill) {444 LLVM_DEBUG(dbgs() << "Remove old kill from " << *OldKill);445 LV->removeVirtualRegisterKilled(IncomingReg, *OldKill);446 LLVM_DEBUG(MBB.dump());447 }448 449 // Add information to LiveVariables to know that the first used incoming450 // value or the resued incoming value whose PHICopy is after the OldKIll451 // is killed. Note that because the value is defined in several places452 // (once each for each incoming block), the "def" block and instruction453 // fields for the VarInfo is not filled in.454 if (!OldKill || IsPHICopyAfterOldKill)455 LV->addVirtualRegisterKilled(IncomingReg, *PHICopy);456 }457 458 // Since we are going to be deleting the PHI node, if it is the last use of459 // any registers, or if the value itself is dead, we need to move this460 // information over to the new copy we just inserted.461 LV->removeVirtualRegistersKilled(*MPhi);462 463 // If the result is dead, update LV.464 if (isDead) {465 LV->addVirtualRegisterDead(DestReg, *PHICopy);466 LV->removeVirtualRegisterDead(DestReg, *MPhi);467 }468 }469 470 // Update LiveIntervals for the new copy or implicit def.471 if (LIS) {472 SlotIndex DestCopyIndex = LIS->InsertMachineInstrInMaps(*PHICopy);473 474 SlotIndex MBBStartIndex = LIS->getMBBStartIdx(&MBB);475 if (IncomingReg) {476 // Add the region from the beginning of MBB to the copy instruction to477 // IncomingReg's live interval.478 LiveInterval &IncomingLI = LIS->getOrCreateEmptyInterval(IncomingReg);479 VNInfo *IncomingVNI = IncomingLI.getVNInfoAt(MBBStartIndex);480 if (!IncomingVNI)481 IncomingVNI =482 IncomingLI.getNextValue(MBBStartIndex, LIS->getVNInfoAllocator());483 IncomingLI.addSegment(LiveInterval::Segment(484 MBBStartIndex, DestCopyIndex.getRegSlot(), IncomingVNI));485 }486 487 LiveInterval &DestLI = LIS->getInterval(DestReg);488 assert(!DestLI.empty() && "PHIs should have non-empty LiveIntervals.");489 490 SlotIndex NewStart = DestCopyIndex.getRegSlot();491 492 SmallVector<LiveRange *> ToUpdate({&DestLI});493 for (auto &SR : DestLI.subranges())494 ToUpdate.push_back(&SR);495 496 for (auto LR : ToUpdate) {497 auto DestSegment = LR->find(MBBStartIndex);498 assert(DestSegment != LR->end() &&499 "PHI destination must be live in block");500 501 if (LR->endIndex().isDead()) {502 // A dead PHI's live range begins and ends at the start of the MBB, but503 // the lowered copy, which will still be dead, needs to begin and end at504 // the copy instruction.505 VNInfo *OrigDestVNI = LR->getVNInfoAt(DestSegment->start);506 assert(OrigDestVNI && "PHI destination should be live at block entry.");507 LR->removeSegment(DestSegment->start, DestSegment->start.getDeadSlot());508 LR->createDeadDef(NewStart, LIS->getVNInfoAllocator());509 LR->removeValNo(OrigDestVNI);510 continue;511 }512 513 // Destination copies are not inserted in the same order as the PHI nodes514 // they replace. Hence the start of the live range may need to be adjusted515 // to match the actual slot index of the copy.516 if (DestSegment->start > NewStart) {517 VNInfo *VNI = LR->getVNInfoAt(DestSegment->start);518 assert(VNI && "value should be defined for known segment");519 LR->addSegment(520 LiveInterval::Segment(NewStart, DestSegment->start, VNI));521 } else if (DestSegment->start < NewStart) {522 assert(DestSegment->start >= MBBStartIndex);523 assert(DestSegment->end >= DestCopyIndex.getRegSlot());524 LR->removeSegment(DestSegment->start, NewStart);525 }526 VNInfo *DestVNI = LR->getVNInfoAt(NewStart);527 assert(DestVNI && "PHI destination should be live at its definition.");528 DestVNI->def = NewStart;529 }530 }531 532 // Adjust the VRegPHIUseCount map to account for the removal of this PHI node.533 if (LV || LIS) {534 for (unsigned i = 1; i != MPhi->getNumOperands(); i += 2) {535 if (!MPhi->getOperand(i).isUndef()) {536 --VRegPHIUseCount[BBVRegPair(537 MPhi->getOperand(i + 1).getMBB()->getNumber(),538 MPhi->getOperand(i).getReg())];539 }540 }541 }542 543 // Now loop over all of the incoming arguments, changing them to copy into the544 // IncomingReg register in the corresponding predecessor basic block.545 SmallPtrSet<MachineBasicBlock *, 8> MBBsInsertedInto;546 for (int i = NumSrcs - 1; i >= 0; --i) {547 Register SrcReg = MPhi->getOperand(i * 2 + 1).getReg();548 unsigned SrcSubReg = MPhi->getOperand(i * 2 + 1).getSubReg();549 bool SrcUndef = MPhi->getOperand(i * 2 + 1).isUndef() ||550 isImplicitlyDefined(SrcReg, *MRI);551 assert(SrcReg.isVirtual() &&552 "Machine PHI Operands must all be virtual registers!");553 554 // Get the MachineBasicBlock equivalent of the BasicBlock that is the source555 // path the PHI.556 MachineBasicBlock &opBlock = *MPhi->getOperand(i * 2 + 2).getMBB();557 558 // Check to make sure we haven't already emitted the copy for this block.559 // This can happen because PHI nodes may have multiple entries for the same560 // basic block.561 if (!MBBsInsertedInto.insert(&opBlock).second)562 continue; // If the copy has already been emitted, we're done.563 564 MachineInstr *SrcRegDef = MRI->getVRegDef(SrcReg);565 if (SrcRegDef && TII->isUnspillableTerminator(SrcRegDef)) {566 assert(SrcRegDef->getOperand(0).isReg() &&567 SrcRegDef->getOperand(0).isDef() &&568 "Expected operand 0 to be a reg def!");569 // Now that the PHI's use has been removed (as the instruction was570 // removed) there should be no other uses of the SrcReg.571 assert(MRI->use_empty(SrcReg) &&572 "Expected a single use from UnspillableTerminator");573 SrcRegDef->getOperand(0).setReg(IncomingReg);574 575 // Update LiveVariables.576 if (LV) {577 LiveVariables::VarInfo &SrcVI = LV->getVarInfo(SrcReg);578 LiveVariables::VarInfo &IncomingVI = LV->getVarInfo(IncomingReg);579 IncomingVI.AliveBlocks = std::move(SrcVI.AliveBlocks);580 SrcVI.AliveBlocks.clear();581 }582 583 continue;584 }585 586 // Find a safe location to insert the copy, this may be the first terminator587 // in the block (or end()).588 MachineBasicBlock::iterator InsertPos =589 findPHICopyInsertPoint(&opBlock, &MBB, SrcReg);590 591 // Insert the copy.592 MachineInstr *NewSrcInstr = nullptr;593 if (!reusedIncoming && IncomingReg) {594 if (SrcUndef) {595 // The source register is undefined, so there is no need for a real596 // COPY, but we still need to ensure joint dominance by defs.597 // Insert an IMPLICIT_DEF instruction.598 NewSrcInstr =599 BuildMI(opBlock, InsertPos, MPhi->getDebugLoc(),600 TII->get(TargetOpcode::IMPLICIT_DEF), IncomingReg);601 602 // Clean up the old implicit-def, if there even was one.603 if (MachineInstr *DefMI = MRI->getVRegDef(SrcReg))604 if (DefMI->isImplicitDef())605 ImpDefs.insert(DefMI);606 } else {607 // Delete the debug location, since the copy is inserted into a608 // different basic block.609 NewSrcInstr = TII->createPHISourceCopy(opBlock, InsertPos, nullptr,610 SrcReg, SrcSubReg, IncomingReg);611 }612 }613 614 // We only need to update the LiveVariables kill of SrcReg if this was the615 // last PHI use of SrcReg to be lowered on this CFG edge and it is not live616 // out of the predecessor. We can also ignore undef sources.617 if (LV && !SrcUndef &&618 !VRegPHIUseCount[BBVRegPair(opBlock.getNumber(), SrcReg)] &&619 !LV->isLiveOut(SrcReg, opBlock)) {620 // We want to be able to insert a kill of the register if this PHI (aka,621 // the copy we just inserted) is the last use of the source value. Live622 // variable analysis conservatively handles this by saying that the value623 // is live until the end of the block the PHI entry lives in. If the value624 // really is dead at the PHI copy, there will be no successor blocks which625 // have the value live-in.626 627 // Okay, if we now know that the value is not live out of the block, we628 // can add a kill marker in this block saying that it kills the incoming629 // value!630 631 // In our final twist, we have to decide which instruction kills the632 // register. In most cases this is the copy, however, terminator633 // instructions at the end of the block may also use the value. In this634 // case, we should mark the last such terminator as being the killing635 // block, not the copy.636 MachineBasicBlock::iterator KillInst = opBlock.end();637 for (MachineBasicBlock::iterator Term = InsertPos; Term != opBlock.end();638 ++Term) {639 if (Term->readsRegister(SrcReg, /*TRI=*/nullptr))640 KillInst = Term;641 }642 643 if (KillInst == opBlock.end()) {644 // No terminator uses the register.645 646 if (reusedIncoming || !IncomingReg) {647 // We may have to rewind a bit if we didn't insert a copy this time.648 KillInst = InsertPos;649 while (KillInst != opBlock.begin()) {650 --KillInst;651 if (KillInst->isDebugInstr())652 continue;653 if (KillInst->readsRegister(SrcReg, /*TRI=*/nullptr))654 break;655 }656 } else {657 // We just inserted this copy.658 KillInst = NewSrcInstr;659 }660 }661 assert(KillInst->readsRegister(SrcReg, /*TRI=*/nullptr) &&662 "Cannot find kill instruction");663 664 // Finally, mark it killed.665 LV->addVirtualRegisterKilled(SrcReg, *KillInst);666 667 // This vreg no longer lives all of the way through opBlock.668 unsigned opBlockNum = opBlock.getNumber();669 LV->getVarInfo(SrcReg).AliveBlocks.reset(opBlockNum);670 }671 672 if (LIS) {673 if (NewSrcInstr) {674 LIS->InsertMachineInstrInMaps(*NewSrcInstr);675 LIS->addSegmentToEndOfBlock(IncomingReg, *NewSrcInstr);676 }677 678 if (!SrcUndef &&679 !VRegPHIUseCount[BBVRegPair(opBlock.getNumber(), SrcReg)]) {680 LiveInterval &SrcLI = LIS->getInterval(SrcReg);681 682 bool isLiveOut = false;683 for (MachineBasicBlock *Succ : opBlock.successors()) {684 SlotIndex startIdx = LIS->getMBBStartIdx(Succ);685 VNInfo *VNI = SrcLI.getVNInfoAt(startIdx);686 687 // Definitions by other PHIs are not truly live-in for our purposes.688 if (VNI && VNI->def != startIdx) {689 isLiveOut = true;690 break;691 }692 }693 694 if (!isLiveOut) {695 MachineBasicBlock::iterator KillInst = opBlock.end();696 for (MachineBasicBlock::iterator Term = InsertPos;697 Term != opBlock.end(); ++Term) {698 if (Term->readsRegister(SrcReg, /*TRI=*/nullptr))699 KillInst = Term;700 }701 702 if (KillInst == opBlock.end()) {703 // No terminator uses the register.704 705 if (reusedIncoming || !IncomingReg) {706 // We may have to rewind a bit if we didn't just insert a copy.707 KillInst = InsertPos;708 while (KillInst != opBlock.begin()) {709 --KillInst;710 if (KillInst->isDebugInstr())711 continue;712 if (KillInst->readsRegister(SrcReg, /*TRI=*/nullptr))713 break;714 }715 } else {716 // We just inserted this copy.717 KillInst = std::prev(InsertPos);718 }719 }720 assert(KillInst->readsRegister(SrcReg, /*TRI=*/nullptr) &&721 "Cannot find kill instruction");722 723 SlotIndex LastUseIndex = LIS->getInstructionIndex(*KillInst);724 SrcLI.removeSegment(LastUseIndex.getRegSlot(),725 LIS->getMBBEndIdx(&opBlock));726 for (auto &SR : SrcLI.subranges()) {727 SR.removeSegment(LastUseIndex.getRegSlot(),728 LIS->getMBBEndIdx(&opBlock));729 }730 }731 }732 }733 }734 735 // Really delete the PHI instruction now, if it is not in the LoweredPHIs map.736 if (EliminateNow) {737 if (LIS)738 LIS->RemoveMachineInstrFromMaps(*MPhi);739 MF.deleteMachineInstr(MPhi);740 }741}742 743/// analyzePHINodes - Gather information about the PHI nodes in here. In744/// particular, we want to map the number of uses of a virtual register which is745/// used in a PHI node. We map that to the BB the vreg is coming from. This is746/// used later to determine when the vreg is killed in the BB.747void PHIEliminationImpl::analyzePHINodes(const MachineFunction &MF) {748 for (const auto &MBB : MF) {749 for (const auto &BBI : MBB) {750 if (!BBI.isPHI())751 break;752 for (unsigned i = 1, e = BBI.getNumOperands(); i != e; i += 2) {753 if (!BBI.getOperand(i).isUndef()) {754 ++VRegPHIUseCount[BBVRegPair(755 BBI.getOperand(i + 1).getMBB()->getNumber(),756 BBI.getOperand(i).getReg())];757 }758 }759 }760 }761}762 763bool PHIEliminationImpl::SplitPHIEdges(764 MachineFunction &MF, MachineBasicBlock &MBB, MachineLoopInfo *MLI,765 std::vector<SparseBitVector<>> *LiveInSets, MachineDomTreeUpdater &MDTU) {766 if (MBB.empty() || !MBB.front().isPHI() || MBB.isEHPad())767 return false; // Quick exit for basic blocks without PHIs.768 769 const MachineLoop *CurLoop = MLI ? MLI->getLoopFor(&MBB) : nullptr;770 bool IsLoopHeader = CurLoop && &MBB == CurLoop->getHeader();771 772 bool Changed = false;773 for (MachineBasicBlock::iterator BBI = MBB.begin(), BBE = MBB.end();774 BBI != BBE && BBI->isPHI(); ++BBI) {775 for (unsigned i = 1, e = BBI->getNumOperands(); i != e; i += 2) {776 Register Reg = BBI->getOperand(i).getReg();777 MachineBasicBlock *PreMBB = BBI->getOperand(i + 1).getMBB();778 // Is there a critical edge from PreMBB to MBB?779 if (PreMBB->succ_size() == 1)780 continue;781 782 // Avoid splitting backedges of loops. It would introduce small783 // out-of-line blocks into the loop which is very bad for code placement.784 if (PreMBB == &MBB && !SplitAllCriticalEdges)785 continue;786 const MachineLoop *PreLoop = MLI ? MLI->getLoopFor(PreMBB) : nullptr;787 if (IsLoopHeader && PreLoop == CurLoop && !SplitAllCriticalEdges)788 continue;789 790 // LV doesn't consider a phi use live-out, so isLiveOut only returns true791 // when the source register is live-out for some other reason than a phi792 // use. That means the copy we will insert in PreMBB won't be a kill, and793 // there is a risk it may not be coalesced away.794 //795 // If the copy would be a kill, there is no need to split the edge.796 bool ShouldSplit = isLiveOutPastPHIs(Reg, PreMBB);797 if (!ShouldSplit && !NoPhiElimLiveOutEarlyExit)798 continue;799 if (ShouldSplit) {800 LLVM_DEBUG(dbgs() << printReg(Reg) << " live-out before critical edge "801 << printMBBReference(*PreMBB) << " -> "802 << printMBBReference(MBB) << ": " << *BBI);803 }804 805 // If Reg is not live-in to MBB, it means it must be live-in to some806 // other PreMBB successor, and we can avoid the interference by splitting807 // the edge.808 //809 // If Reg *is* live-in to MBB, the interference is inevitable and a copy810 // is likely to be left after coalescing. If we are looking at a loop811 // exiting edge, split it so we won't insert code in the loop, otherwise812 // don't bother.813 ShouldSplit = ShouldSplit && !isLiveIn(Reg, &MBB);814 815 // Check for a loop exiting edge.816 if (!ShouldSplit && CurLoop != PreLoop) {817 LLVM_DEBUG({818 dbgs() << "Split wouldn't help, maybe avoid loop copies?\n";819 if (PreLoop)820 dbgs() << "PreLoop: " << *PreLoop;821 if (CurLoop)822 dbgs() << "CurLoop: " << *CurLoop;823 });824 // This edge could be entering a loop, exiting a loop, or it could be825 // both: Jumping directly form one loop to the header of a sibling826 // loop.827 // Split unless this edge is entering CurLoop from an outer loop.828 ShouldSplit = PreLoop && !PreLoop->contains(CurLoop);829 }830 if (!ShouldSplit && !SplitAllCriticalEdges)831 continue;832 if (!(P ? PreMBB->SplitCriticalEdge(&MBB, *P, LiveInSets, &MDTU)833 : PreMBB->SplitCriticalEdge(&MBB, *MFAM, LiveInSets, &MDTU))) {834 LLVM_DEBUG(dbgs() << "Failed to split critical edge.\n");835 continue;836 }837 Changed = true;838 ++NumCriticalEdgesSplit;839 }840 }841 return Changed;842}843 844bool PHIEliminationImpl::isLiveIn(Register Reg, const MachineBasicBlock *MBB) {845 assert((LV || LIS) &&846 "isLiveIn() requires either LiveVariables or LiveIntervals");847 if (LIS)848 return LIS->isLiveInToMBB(LIS->getInterval(Reg), MBB);849 else850 return LV->isLiveIn(Reg, *MBB);851}852 853bool PHIEliminationImpl::isLiveOutPastPHIs(Register Reg,854 const MachineBasicBlock *MBB) {855 assert((LV || LIS) &&856 "isLiveOutPastPHIs() requires either LiveVariables or LiveIntervals");857 // LiveVariables considers uses in PHIs to be in the predecessor basic block,858 // so that a register used only in a PHI is not live out of the block. In859 // contrast, LiveIntervals considers uses in PHIs to be on the edge rather860 // than in the predecessor basic block, so that a register used only in a PHI861 // is live out of the block.862 if (LIS) {863 const LiveInterval &LI = LIS->getInterval(Reg);864 for (const MachineBasicBlock *SI : MBB->successors())865 if (LI.liveAt(LIS->getMBBStartIdx(SI)))866 return true;867 return false;868 } else {869 return LV->isLiveOut(Reg, *MBB);870 }871}872