1193323Sed//===-- PhiElimination.cpp - Eliminate PHI nodes by inserting copies ------===// 2193323Sed// 3193323Sed// The LLVM Compiler Infrastructure 4193323Sed// 5193323Sed// This file is distributed under the University of Illinois Open Source 6193323Sed// License. See LICENSE.TXT for details. 7193323Sed// 8193323Sed//===----------------------------------------------------------------------===// 9193323Sed// 10193323Sed// This pass eliminates machine instruction PHI nodes by inserting copy 11193323Sed// instructions. This destroys SSA information, but is the desired input for 12193323Sed// some register allocators. 13193323Sed// 14193323Sed//===----------------------------------------------------------------------===// 15193323Sed 16193323Sed#define DEBUG_TYPE "phielim" 17249423Sdim#include "llvm/CodeGen/Passes.h" 18218893Sdim#include "PHIEliminationUtils.h" 19249423Sdim#include "llvm/ADT/STLExtras.h" 20249423Sdim#include "llvm/ADT/SmallPtrSet.h" 21249423Sdim#include "llvm/ADT/Statistic.h" 22249423Sdim#include "llvm/CodeGen/LiveIntervalAnalysis.h" 23193323Sed#include "llvm/CodeGen/LiveVariables.h" 24199481Srdivacky#include "llvm/CodeGen/MachineDominators.h" 25193323Sed#include "llvm/CodeGen/MachineInstr.h" 26193323Sed#include "llvm/CodeGen/MachineInstrBuilder.h" 27212904Sdim#include "llvm/CodeGen/MachineLoopInfo.h" 28193323Sed#include "llvm/CodeGen/MachineRegisterInfo.h" 29249423Sdim#include "llvm/IR/Function.h" 30221345Sdim#include "llvm/Support/CommandLine.h" 31193323Sed#include "llvm/Support/Compiler.h" 32199481Srdivacky#include "llvm/Support/Debug.h" 33249423Sdim#include "llvm/Target/TargetInstrInfo.h" 34249423Sdim#include "llvm/Target/TargetMachine.h" 35193323Sed#include <algorithm> 36193323Sedusing namespace llvm; 37193323Sed 38221345Sdimstatic cl::opt<bool> 39221345SdimDisableEdgeSplitting("disable-phi-elim-edge-splitting", cl::init(false), 40221345Sdim cl::Hidden, cl::desc("Disable critical edge splitting " 41221345Sdim "during PHI elimination")); 42221345Sdim 43249423Sdimstatic cl::opt<bool> 44249423SdimSplitAllCriticalEdges("phi-elim-split-all-critical-edges", cl::init(false), 45249423Sdim cl::Hidden, cl::desc("Split all critical edges during " 46249423Sdim "PHI elimination")); 47249423Sdim 48218893Sdimnamespace { 49218893Sdim class PHIElimination : public MachineFunctionPass { 50218893Sdim MachineRegisterInfo *MRI; // Machine register information 51249423Sdim LiveVariables *LV; 52249423Sdim LiveIntervals *LIS; 53218893Sdim 54218893Sdim public: 55218893Sdim static char ID; // Pass identification, replacement for typeid 56218893Sdim PHIElimination() : MachineFunctionPass(ID) { 57218893Sdim initializePHIEliminationPass(*PassRegistry::getPassRegistry()); 58218893Sdim } 59218893Sdim 60218893Sdim virtual bool runOnMachineFunction(MachineFunction &Fn); 61218893Sdim virtual void getAnalysisUsage(AnalysisUsage &AU) const; 62218893Sdim 63218893Sdim private: 64218893Sdim /// EliminatePHINodes - Eliminate phi nodes by inserting copy instructions 65218893Sdim /// in predecessor basic blocks. 66218893Sdim /// 67218893Sdim bool EliminatePHINodes(MachineFunction &MF, MachineBasicBlock &MBB); 68249423Sdim void LowerPHINode(MachineBasicBlock &MBB, 69263508Sdim MachineBasicBlock::iterator LastPHIIt); 70218893Sdim 71218893Sdim /// analyzePHINodes - Gather information about the PHI nodes in 72218893Sdim /// here. In particular, we want to map the number of uses of a virtual 73218893Sdim /// register which is used in a PHI node. We map that to the BB the 74218893Sdim /// vreg is coming from. This is used later to determine when the vreg 75218893Sdim /// is killed in the BB. 76218893Sdim /// 77218893Sdim void analyzePHINodes(const MachineFunction& Fn); 78218893Sdim 79218893Sdim /// Split critical edges where necessary for good coalescer performance. 80218893Sdim bool SplitPHIEdges(MachineFunction &MF, MachineBasicBlock &MBB, 81249423Sdim MachineLoopInfo *MLI); 82218893Sdim 83249423Sdim // These functions are temporary abstractions around LiveVariables and 84249423Sdim // LiveIntervals, so they can go away when LiveVariables does. 85249423Sdim bool isLiveIn(unsigned Reg, MachineBasicBlock *MBB); 86249423Sdim bool isLiveOutPastPHIs(unsigned Reg, MachineBasicBlock *MBB); 87249423Sdim 88218893Sdim typedef std::pair<unsigned, unsigned> BBVRegPair; 89218893Sdim typedef DenseMap<BBVRegPair, unsigned> VRegPHIUse; 90218893Sdim 91218893Sdim VRegPHIUse VRegPHIUseCount; 92218893Sdim 93218893Sdim // Defs of PHI sources which are implicit_def. 94218893Sdim SmallPtrSet<MachineInstr*, 4> ImpDefs; 95218893Sdim 96218893Sdim // Map reusable lowered PHI node -> incoming join register. 97218893Sdim typedef DenseMap<MachineInstr*, unsigned, 98218893Sdim MachineInstrExpressionTrait> LoweredPHIMap; 99218893Sdim LoweredPHIMap LoweredPHIs; 100218893Sdim }; 101218893Sdim} 102218893Sdim 103249423SdimSTATISTIC(NumLowered, "Number of phis lowered"); 104218893SdimSTATISTIC(NumCriticalEdgesSplit, "Number of critical edges split"); 105201360SrdivackySTATISTIC(NumReused, "Number of reused lowered phis"); 106193323Sed 107198090Srdivackychar PHIElimination::ID = 0; 108218893Sdimchar& llvm::PHIEliminationID = PHIElimination::ID; 109193323Sed 110234353SdimINITIALIZE_PASS_BEGIN(PHIElimination, "phi-node-elimination", 111234353Sdim "Eliminate PHI nodes for register allocation", 112234353Sdim false, false) 113234353SdimINITIALIZE_PASS_DEPENDENCY(LiveVariables) 114234353SdimINITIALIZE_PASS_END(PHIElimination, "phi-node-elimination", 115234353Sdim "Eliminate PHI nodes for register allocation", false, false) 116234353Sdim 117218893Sdimvoid PHIElimination::getAnalysisUsage(AnalysisUsage &AU) const { 118198090Srdivacky AU.addPreserved<LiveVariables>(); 119249423Sdim AU.addPreserved<SlotIndexes>(); 120249423Sdim AU.addPreserved<LiveIntervals>(); 121199481Srdivacky AU.addPreserved<MachineDominatorTree>(); 122212904Sdim AU.addPreserved<MachineLoopInfo>(); 123198090Srdivacky MachineFunctionPass::getAnalysisUsage(AU); 124193323Sed} 125193323Sed 126218893Sdimbool PHIElimination::runOnMachineFunction(MachineFunction &MF) { 127207631Srdivacky MRI = &MF.getRegInfo(); 128249423Sdim LV = getAnalysisIfAvailable<LiveVariables>(); 129249423Sdim LIS = getAnalysisIfAvailable<LiveIntervals>(); 130193323Sed 131199481Srdivacky bool Changed = false; 132199481Srdivacky 133226633Sdim // This pass takes the function out of SSA form. 134226633Sdim MRI->leaveSSA(); 135226633Sdim 136249423Sdim // Split critical edges to help the coalescer. This does not yet support 137249423Sdim // updating LiveIntervals, so we disable it. 138249423Sdim if (!DisableEdgeSplitting && (LV || LIS)) { 139249423Sdim MachineLoopInfo *MLI = getAnalysisIfAvailable<MachineLoopInfo>(); 140249423Sdim for (MachineFunction::iterator I = MF.begin(), E = MF.end(); I != E; ++I) 141249423Sdim Changed |= SplitPHIEdges(MF, *I, MLI); 142212904Sdim } 143199481Srdivacky 144199481Srdivacky // Populate VRegPHIUseCount 145207631Srdivacky analyzePHINodes(MF); 146193323Sed 147193323Sed // Eliminate PHI instructions by inserting copies into predecessor blocks. 148207631Srdivacky for (MachineFunction::iterator I = MF.begin(), E = MF.end(); I != E; ++I) 149207631Srdivacky Changed |= EliminatePHINodes(MF, *I); 150193323Sed 151193323Sed // Remove dead IMPLICIT_DEF instructions. 152201360Srdivacky for (SmallPtrSet<MachineInstr*, 4>::iterator I = ImpDefs.begin(), 153193323Sed E = ImpDefs.end(); I != E; ++I) { 154193323Sed MachineInstr *DefMI = *I; 155193323Sed unsigned DefReg = DefMI->getOperand(0).getReg(); 156249423Sdim if (MRI->use_nodbg_empty(DefReg)) { 157249423Sdim if (LIS) 158249423Sdim LIS->RemoveMachineInstrFromMaps(DefMI); 159193323Sed DefMI->eraseFromParent(); 160249423Sdim } 161193323Sed } 162193323Sed 163201360Srdivacky // Clean up the lowered PHI instructions. 164201360Srdivacky for (LoweredPHIMap::iterator I = LoweredPHIs.begin(), E = LoweredPHIs.end(); 165249423Sdim I != E; ++I) { 166249423Sdim if (LIS) 167249423Sdim LIS->RemoveMachineInstrFromMaps(I->first); 168207631Srdivacky MF.DeleteMachineInstr(I->first); 169249423Sdim } 170201360Srdivacky 171201360Srdivacky LoweredPHIs.clear(); 172193323Sed ImpDefs.clear(); 173193323Sed VRegPHIUseCount.clear(); 174207631Srdivacky 175193323Sed return Changed; 176193323Sed} 177193323Sed 178193323Sed/// EliminatePHINodes - Eliminate phi nodes by inserting copy instructions in 179193323Sed/// predecessor basic blocks. 180193323Sed/// 181218893Sdimbool PHIElimination::EliminatePHINodes(MachineFunction &MF, 182198090Srdivacky MachineBasicBlock &MBB) { 183203954Srdivacky if (MBB.empty() || !MBB.front().isPHI()) 184193323Sed return false; // Quick exit for basic blocks without PHIs. 185193323Sed 186193323Sed // Get an iterator to the first instruction after the last PHI node (this may 187193323Sed // also be the end of the basic block). 188263508Sdim MachineBasicBlock::iterator LastPHIIt = 189263508Sdim prior(MBB.SkipPHIsAndLabels(MBB.begin())); 190193323Sed 191203954Srdivacky while (MBB.front().isPHI()) 192263508Sdim LowerPHINode(MBB, LastPHIIt); 193193323Sed 194193323Sed return true; 195193323Sed} 196193323Sed 197239462Sdim/// isImplicitlyDefined - Return true if all defs of VirtReg are implicit-defs. 198239462Sdim/// This includes registers with no defs. 199239462Sdimstatic bool isImplicitlyDefined(unsigned VirtReg, 200239462Sdim const MachineRegisterInfo *MRI) { 201239462Sdim for (MachineRegisterInfo::def_iterator DI = MRI->def_begin(VirtReg), 202239462Sdim DE = MRI->def_end(); DI != DE; ++DI) 203239462Sdim if (!DI->isImplicitDef()) 204239462Sdim return false; 205239462Sdim return true; 206239462Sdim} 207239462Sdim 208193323Sed/// isSourceDefinedByImplicitDef - Return true if all sources of the phi node 209193323Sed/// are implicit_def's. 210193323Sedstatic bool isSourceDefinedByImplicitDef(const MachineInstr *MPhi, 211193323Sed const MachineRegisterInfo *MRI) { 212239462Sdim for (unsigned i = 1; i != MPhi->getNumOperands(); i += 2) 213239462Sdim if (!isImplicitlyDefined(MPhi->getOperand(i).getReg(), MRI)) 214193323Sed return false; 215193323Sed return true; 216193323Sed} 217193323Sed 218193323Sed 219249423Sdim/// LowerPHINode - Lower the PHI node at the top of the specified block, 220199481Srdivacky/// 221249423Sdimvoid PHIElimination::LowerPHINode(MachineBasicBlock &MBB, 222263508Sdim MachineBasicBlock::iterator LastPHIIt) { 223249423Sdim ++NumLowered; 224263508Sdim 225263508Sdim MachineBasicBlock::iterator AfterPHIsIt = llvm::next(LastPHIIt); 226263508Sdim 227193323Sed // Unlink the PHI node from the basic block, but don't delete the PHI yet. 228193323Sed MachineInstr *MPhi = MBB.remove(MBB.begin()); 229193323Sed 230193323Sed unsigned NumSrcs = (MPhi->getNumOperands() - 1) / 2; 231193323Sed unsigned DestReg = MPhi->getOperand(0).getReg(); 232212904Sdim assert(MPhi->getOperand(0).getSubReg() == 0 && "Can't handle sub-reg PHIs"); 233193323Sed bool isDead = MPhi->getOperand(0).isDead(); 234193323Sed 235193323Sed // Create a new register for the incoming PHI arguments. 236193323Sed MachineFunction &MF = *MBB.getParent(); 237193323Sed unsigned IncomingReg = 0; 238201360Srdivacky bool reusedIncoming = false; // Is IncomingReg reused from an earlier PHI? 239193323Sed 240193323Sed // Insert a register to register copy at the top of the current block (but 241193323Sed // after any remaining phi nodes) which copies the new incoming register 242193323Sed // into the phi node destination. 243193323Sed const TargetInstrInfo *TII = MF.getTarget().getInstrInfo(); 244193323Sed if (isSourceDefinedByImplicitDef(MPhi, MRI)) 245193323Sed // If all sources of a PHI node are implicit_def, just emit an 246193323Sed // implicit_def instead of a copy. 247193323Sed BuildMI(MBB, AfterPHIsIt, MPhi->getDebugLoc(), 248203954Srdivacky TII->get(TargetOpcode::IMPLICIT_DEF), DestReg); 249193323Sed else { 250201360Srdivacky // Can we reuse an earlier PHI node? This only happens for critical edges, 251201360Srdivacky // typically those created by tail duplication. 252201360Srdivacky unsigned &entry = LoweredPHIs[MPhi]; 253201360Srdivacky if (entry) { 254201360Srdivacky // An identical PHI node was already lowered. Reuse the incoming register. 255201360Srdivacky IncomingReg = entry; 256201360Srdivacky reusedIncoming = true; 257201360Srdivacky ++NumReused; 258218893Sdim DEBUG(dbgs() << "Reusing " << PrintReg(IncomingReg) << " for " << *MPhi); 259201360Srdivacky } else { 260210299Sed const TargetRegisterClass *RC = MF.getRegInfo().getRegClass(DestReg); 261201360Srdivacky entry = IncomingReg = MF.getRegInfo().createVirtualRegister(RC); 262201360Srdivacky } 263210299Sed BuildMI(MBB, AfterPHIsIt, MPhi->getDebugLoc(), 264210299Sed TII->get(TargetOpcode::COPY), DestReg) 265210299Sed .addReg(IncomingReg); 266193323Sed } 267193323Sed 268193323Sed // Update live variable information if there is any. 269193323Sed if (LV) { 270193323Sed MachineInstr *PHICopy = prior(AfterPHIsIt); 271193323Sed 272193323Sed if (IncomingReg) { 273201360Srdivacky LiveVariables::VarInfo &VI = LV->getVarInfo(IncomingReg); 274201360Srdivacky 275193323Sed // Increment use count of the newly created virtual register. 276204642Srdivacky LV->setPHIJoin(IncomingReg); 277193323Sed 278201360Srdivacky // When we are reusing the incoming register, it may already have been 279201360Srdivacky // killed in this block. The old kill will also have been inserted at 280201360Srdivacky // AfterPHIsIt, so it appears before the current PHICopy. 281201360Srdivacky if (reusedIncoming) 282201360Srdivacky if (MachineInstr *OldKill = VI.findKill(&MBB)) { 283202375Srdivacky DEBUG(dbgs() << "Remove old kill from " << *OldKill); 284201360Srdivacky LV->removeVirtualRegisterKilled(IncomingReg, OldKill); 285201360Srdivacky DEBUG(MBB.dump()); 286201360Srdivacky } 287201360Srdivacky 288193323Sed // Add information to LiveVariables to know that the incoming value is 289193323Sed // killed. Note that because the value is defined in several places (once 290193323Sed // each for each incoming block), the "def" block and instruction fields 291193323Sed // for the VarInfo is not filled in. 292193323Sed LV->addVirtualRegisterKilled(IncomingReg, PHICopy); 293193323Sed } 294193323Sed 295193323Sed // Since we are going to be deleting the PHI node, if it is the last use of 296193323Sed // any registers, or if the value itself is dead, we need to move this 297193323Sed // information over to the new copy we just inserted. 298193323Sed LV->removeVirtualRegistersKilled(MPhi); 299193323Sed 300193323Sed // If the result is dead, update LV. 301193323Sed if (isDead) { 302193323Sed LV->addVirtualRegisterDead(DestReg, PHICopy); 303193323Sed LV->removeVirtualRegisterDead(DestReg, MPhi); 304193323Sed } 305193323Sed } 306193323Sed 307249423Sdim // Update LiveIntervals for the new copy or implicit def. 308249423Sdim if (LIS) { 309249423Sdim MachineInstr *NewInstr = prior(AfterPHIsIt); 310249423Sdim SlotIndex DestCopyIndex = LIS->InsertMachineInstrInMaps(NewInstr); 311249423Sdim 312249423Sdim SlotIndex MBBStartIndex = LIS->getMBBStartIdx(&MBB); 313249423Sdim if (IncomingReg) { 314249423Sdim // Add the region from the beginning of MBB to the copy instruction to 315249423Sdim // IncomingReg's live interval. 316263508Sdim LiveInterval &IncomingLI = LIS->createEmptyInterval(IncomingReg); 317249423Sdim VNInfo *IncomingVNI = IncomingLI.getVNInfoAt(MBBStartIndex); 318249423Sdim if (!IncomingVNI) 319249423Sdim IncomingVNI = IncomingLI.getNextValue(MBBStartIndex, 320249423Sdim LIS->getVNInfoAllocator()); 321263508Sdim IncomingLI.addSegment(LiveInterval::Segment(MBBStartIndex, 322263508Sdim DestCopyIndex.getRegSlot(), 323263508Sdim IncomingVNI)); 324249423Sdim } 325249423Sdim 326249423Sdim LiveInterval &DestLI = LIS->getInterval(DestReg); 327249423Sdim assert(DestLI.begin() != DestLI.end() && 328249423Sdim "PHIs should have nonempty LiveIntervals."); 329249423Sdim if (DestLI.endIndex().isDead()) { 330249423Sdim // A dead PHI's live range begins and ends at the start of the MBB, but 331249423Sdim // the lowered copy, which will still be dead, needs to begin and end at 332249423Sdim // the copy instruction. 333249423Sdim VNInfo *OrigDestVNI = DestLI.getVNInfoAt(MBBStartIndex); 334249423Sdim assert(OrigDestVNI && "PHI destination should be live at block entry."); 335263508Sdim DestLI.removeSegment(MBBStartIndex, MBBStartIndex.getDeadSlot()); 336249423Sdim DestLI.createDeadDef(DestCopyIndex.getRegSlot(), 337249423Sdim LIS->getVNInfoAllocator()); 338249423Sdim DestLI.removeValNo(OrigDestVNI); 339249423Sdim } else { 340249423Sdim // Otherwise, remove the region from the beginning of MBB to the copy 341249423Sdim // instruction from DestReg's live interval. 342263508Sdim DestLI.removeSegment(MBBStartIndex, DestCopyIndex.getRegSlot()); 343249423Sdim VNInfo *DestVNI = DestLI.getVNInfoAt(DestCopyIndex.getRegSlot()); 344249423Sdim assert(DestVNI && "PHI destination should be live at its definition."); 345249423Sdim DestVNI->def = DestCopyIndex.getRegSlot(); 346249423Sdim } 347249423Sdim } 348249423Sdim 349193323Sed // Adjust the VRegPHIUseCount map to account for the removal of this PHI node. 350193323Sed for (unsigned i = 1; i != MPhi->getNumOperands(); i += 2) 351201360Srdivacky --VRegPHIUseCount[BBVRegPair(MPhi->getOperand(i+1).getMBB()->getNumber(), 352193323Sed MPhi->getOperand(i).getReg())]; 353193323Sed 354193323Sed // Now loop over all of the incoming arguments, changing them to copy into the 355193323Sed // IncomingReg register in the corresponding predecessor basic block. 356193323Sed SmallPtrSet<MachineBasicBlock*, 8> MBBsInsertedInto; 357193323Sed for (int i = NumSrcs - 1; i >= 0; --i) { 358193323Sed unsigned SrcReg = MPhi->getOperand(i*2+1).getReg(); 359212904Sdim unsigned SrcSubReg = MPhi->getOperand(i*2+1).getSubReg(); 360239462Sdim bool SrcUndef = MPhi->getOperand(i*2+1).isUndef() || 361239462Sdim isImplicitlyDefined(SrcReg, MRI); 362193323Sed assert(TargetRegisterInfo::isVirtualRegister(SrcReg) && 363193323Sed "Machine PHI Operands must all be virtual registers!"); 364193323Sed 365198090Srdivacky // Get the MachineBasicBlock equivalent of the BasicBlock that is the source 366198090Srdivacky // path the PHI. 367198090Srdivacky MachineBasicBlock &opBlock = *MPhi->getOperand(i*2+2).getMBB(); 368198090Srdivacky 369193323Sed // Check to make sure we haven't already emitted the copy for this block. 370193323Sed // This can happen because PHI nodes may have multiple entries for the same 371193323Sed // basic block. 372193323Sed if (!MBBsInsertedInto.insert(&opBlock)) 373193323Sed continue; // If the copy has already been emitted, we're done. 374199481Srdivacky 375193323Sed // Find a safe location to insert the copy, this may be the first terminator 376193323Sed // in the block (or end()). 377199481Srdivacky MachineBasicBlock::iterator InsertPos = 378218893Sdim findPHICopyInsertPoint(&opBlock, &MBB, SrcReg); 379193323Sed 380193323Sed // Insert the copy. 381249423Sdim MachineInstr *NewSrcInstr = 0; 382239462Sdim if (!reusedIncoming && IncomingReg) { 383239462Sdim if (SrcUndef) { 384239462Sdim // The source register is undefined, so there is no need for a real 385239462Sdim // COPY, but we still need to ensure joint dominance by defs. 386239462Sdim // Insert an IMPLICIT_DEF instruction. 387249423Sdim NewSrcInstr = BuildMI(opBlock, InsertPos, MPhi->getDebugLoc(), 388249423Sdim TII->get(TargetOpcode::IMPLICIT_DEF), 389249423Sdim IncomingReg); 390193323Sed 391239462Sdim // Clean up the old implicit-def, if there even was one. 392239462Sdim if (MachineInstr *DefMI = MRI->getVRegDef(SrcReg)) 393239462Sdim if (DefMI->isImplicitDef()) 394239462Sdim ImpDefs.insert(DefMI); 395239462Sdim } else { 396249423Sdim NewSrcInstr = BuildMI(opBlock, InsertPos, MPhi->getDebugLoc(), 397249423Sdim TII->get(TargetOpcode::COPY), IncomingReg) 398249423Sdim .addReg(SrcReg, 0, SrcSubReg); 399239462Sdim } 400239462Sdim } 401239462Sdim 402249423Sdim // We only need to update the LiveVariables kill of SrcReg if this was the 403249423Sdim // last PHI use of SrcReg to be lowered on this CFG edge and it is not live 404249423Sdim // out of the predecessor. We can also ignore undef sources. 405249423Sdim if (LV && !SrcUndef && 406249423Sdim !VRegPHIUseCount[BBVRegPair(opBlock.getNumber(), SrcReg)] && 407249423Sdim !LV->isLiveOut(SrcReg, opBlock)) { 408249423Sdim // We want to be able to insert a kill of the register if this PHI (aka, 409249423Sdim // the copy we just inserted) is the last use of the source value. Live 410249423Sdim // variable analysis conservatively handles this by saying that the value 411249423Sdim // is live until the end of the block the PHI entry lives in. If the value 412249423Sdim // really is dead at the PHI copy, there will be no successor blocks which 413249423Sdim // have the value live-in. 414199481Srdivacky 415249423Sdim // Okay, if we now know that the value is not live out of the block, we 416249423Sdim // can add a kill marker in this block saying that it kills the incoming 417249423Sdim // value! 418193323Sed 419193323Sed // In our final twist, we have to decide which instruction kills the 420239462Sdim // register. In most cases this is the copy, however, terminator 421239462Sdim // instructions at the end of the block may also use the value. In this 422239462Sdim // case, we should mark the last such terminator as being the killing 423239462Sdim // block, not the copy. 424239462Sdim MachineBasicBlock::iterator KillInst = opBlock.end(); 425239462Sdim MachineBasicBlock::iterator FirstTerm = opBlock.getFirstTerminator(); 426239462Sdim for (MachineBasicBlock::iterator Term = FirstTerm; 427239462Sdim Term != opBlock.end(); ++Term) { 428239462Sdim if (Term->readsRegister(SrcReg)) 429239462Sdim KillInst = Term; 430239462Sdim } 431199481Srdivacky 432239462Sdim if (KillInst == opBlock.end()) { 433239462Sdim // No terminator uses the register. 434239462Sdim 435239462Sdim if (reusedIncoming || !IncomingReg) { 436239462Sdim // We may have to rewind a bit if we didn't insert a copy this time. 437239462Sdim KillInst = FirstTerm; 438239462Sdim while (KillInst != opBlock.begin()) { 439239462Sdim --KillInst; 440239462Sdim if (KillInst->isDebugValue()) 441239462Sdim continue; 442239462Sdim if (KillInst->readsRegister(SrcReg)) 443239462Sdim break; 444239462Sdim } 445239462Sdim } else { 446239462Sdim // We just inserted this copy. 447239462Sdim KillInst = prior(InsertPos); 448193323Sed } 449193323Sed } 450201360Srdivacky assert(KillInst->readsRegister(SrcReg) && "Cannot find kill instruction"); 451199481Srdivacky 452193323Sed // Finally, mark it killed. 453193323Sed LV->addVirtualRegisterKilled(SrcReg, KillInst); 454193323Sed 455193323Sed // This vreg no longer lives all of the way through opBlock. 456193323Sed unsigned opBlockNum = opBlock.getNumber(); 457199481Srdivacky LV->getVarInfo(SrcReg).AliveBlocks.reset(opBlockNum); 458193323Sed } 459249423Sdim 460249423Sdim if (LIS) { 461249423Sdim if (NewSrcInstr) { 462249423Sdim LIS->InsertMachineInstrInMaps(NewSrcInstr); 463263508Sdim LIS->addSegmentToEndOfBlock(IncomingReg, NewSrcInstr); 464249423Sdim } 465249423Sdim 466249423Sdim if (!SrcUndef && 467249423Sdim !VRegPHIUseCount[BBVRegPair(opBlock.getNumber(), SrcReg)]) { 468249423Sdim LiveInterval &SrcLI = LIS->getInterval(SrcReg); 469249423Sdim 470249423Sdim bool isLiveOut = false; 471249423Sdim for (MachineBasicBlock::succ_iterator SI = opBlock.succ_begin(), 472249423Sdim SE = opBlock.succ_end(); SI != SE; ++SI) { 473249423Sdim SlotIndex startIdx = LIS->getMBBStartIdx(*SI); 474249423Sdim VNInfo *VNI = SrcLI.getVNInfoAt(startIdx); 475249423Sdim 476249423Sdim // Definitions by other PHIs are not truly live-in for our purposes. 477249423Sdim if (VNI && VNI->def != startIdx) { 478249423Sdim isLiveOut = true; 479249423Sdim break; 480249423Sdim } 481249423Sdim } 482249423Sdim 483249423Sdim if (!isLiveOut) { 484249423Sdim MachineBasicBlock::iterator KillInst = opBlock.end(); 485249423Sdim MachineBasicBlock::iterator FirstTerm = opBlock.getFirstTerminator(); 486249423Sdim for (MachineBasicBlock::iterator Term = FirstTerm; 487249423Sdim Term != opBlock.end(); ++Term) { 488249423Sdim if (Term->readsRegister(SrcReg)) 489249423Sdim KillInst = Term; 490249423Sdim } 491249423Sdim 492249423Sdim if (KillInst == opBlock.end()) { 493249423Sdim // No terminator uses the register. 494249423Sdim 495249423Sdim if (reusedIncoming || !IncomingReg) { 496249423Sdim // We may have to rewind a bit if we didn't just insert a copy. 497249423Sdim KillInst = FirstTerm; 498249423Sdim while (KillInst != opBlock.begin()) { 499249423Sdim --KillInst; 500249423Sdim if (KillInst->isDebugValue()) 501249423Sdim continue; 502249423Sdim if (KillInst->readsRegister(SrcReg)) 503249423Sdim break; 504249423Sdim } 505249423Sdim } else { 506249423Sdim // We just inserted this copy. 507249423Sdim KillInst = prior(InsertPos); 508249423Sdim } 509249423Sdim } 510249423Sdim assert(KillInst->readsRegister(SrcReg) && 511249423Sdim "Cannot find kill instruction"); 512249423Sdim 513249423Sdim SlotIndex LastUseIndex = LIS->getInstructionIndex(KillInst); 514263508Sdim SrcLI.removeSegment(LastUseIndex.getRegSlot(), 515263508Sdim LIS->getMBBEndIdx(&opBlock)); 516249423Sdim } 517249423Sdim } 518249423Sdim } 519193323Sed } 520199481Srdivacky 521201360Srdivacky // Really delete the PHI instruction now, if it is not in the LoweredPHIs map. 522249423Sdim if (reusedIncoming || !IncomingReg) { 523249423Sdim if (LIS) 524249423Sdim LIS->RemoveMachineInstrFromMaps(MPhi); 525201360Srdivacky MF.DeleteMachineInstr(MPhi); 526249423Sdim } 527193323Sed} 528193323Sed 529193323Sed/// analyzePHINodes - Gather information about the PHI nodes in here. In 530193323Sed/// particular, we want to map the number of uses of a virtual register which is 531193323Sed/// used in a PHI node. We map that to the BB the vreg is coming from. This is 532193323Sed/// used later to determine when the vreg is killed in the BB. 533193323Sed/// 534218893Sdimvoid PHIElimination::analyzePHINodes(const MachineFunction& MF) { 535207631Srdivacky for (MachineFunction::const_iterator I = MF.begin(), E = MF.end(); 536193323Sed I != E; ++I) 537193323Sed for (MachineBasicBlock::const_iterator BBI = I->begin(), BBE = I->end(); 538203954Srdivacky BBI != BBE && BBI->isPHI(); ++BBI) 539193323Sed for (unsigned i = 1, e = BBI->getNumOperands(); i != e; i += 2) 540201360Srdivacky ++VRegPHIUseCount[BBVRegPair(BBI->getOperand(i+1).getMBB()->getNumber(), 541193323Sed BBI->getOperand(i).getReg())]; 542193323Sed} 543199481Srdivacky 544218893Sdimbool PHIElimination::SplitPHIEdges(MachineFunction &MF, 545218893Sdim MachineBasicBlock &MBB, 546218893Sdim MachineLoopInfo *MLI) { 547203954Srdivacky if (MBB.empty() || !MBB.front().isPHI() || MBB.isLandingPad()) 548199481Srdivacky return false; // Quick exit for basic blocks without PHIs. 549199511Srdivacky 550239462Sdim const MachineLoop *CurLoop = MLI ? MLI->getLoopFor(&MBB) : 0; 551239462Sdim bool IsLoopHeader = CurLoop && &MBB == CurLoop->getHeader(); 552239462Sdim 553212904Sdim bool Changed = false; 554234353Sdim for (MachineBasicBlock::iterator BBI = MBB.begin(), BBE = MBB.end(); 555203954Srdivacky BBI != BBE && BBI->isPHI(); ++BBI) { 556199481Srdivacky for (unsigned i = 1, e = BBI->getNumOperands(); i != e; i += 2) { 557199481Srdivacky unsigned Reg = BBI->getOperand(i).getReg(); 558199481Srdivacky MachineBasicBlock *PreMBB = BBI->getOperand(i+1).getMBB(); 559239462Sdim // Is there a critical edge from PreMBB to MBB? 560239462Sdim if (PreMBB->succ_size() == 1) 561239462Sdim continue; 562239462Sdim 563212904Sdim // Avoid splitting backedges of loops. It would introduce small 564212904Sdim // out-of-line blocks into the loop which is very bad for code placement. 565249423Sdim if (PreMBB == &MBB && !SplitAllCriticalEdges) 566239462Sdim continue; 567239462Sdim const MachineLoop *PreLoop = MLI ? MLI->getLoopFor(PreMBB) : 0; 568249423Sdim if (IsLoopHeader && PreLoop == CurLoop && !SplitAllCriticalEdges) 569239462Sdim continue; 570239462Sdim 571239462Sdim // LV doesn't consider a phi use live-out, so isLiveOut only returns true 572239462Sdim // when the source register is live-out for some other reason than a phi 573239462Sdim // use. That means the copy we will insert in PreMBB won't be a kill, and 574239462Sdim // there is a risk it may not be coalesced away. 575239462Sdim // 576239462Sdim // If the copy would be a kill, there is no need to split the edge. 577249423Sdim if (!isLiveOutPastPHIs(Reg, PreMBB) && !SplitAllCriticalEdges) 578239462Sdim continue; 579239462Sdim 580239462Sdim DEBUG(dbgs() << PrintReg(Reg) << " live-out before critical edge BB#" 581239462Sdim << PreMBB->getNumber() << " -> BB#" << MBB.getNumber() 582239462Sdim << ": " << *BBI); 583239462Sdim 584239462Sdim // If Reg is not live-in to MBB, it means it must be live-in to some 585239462Sdim // other PreMBB successor, and we can avoid the interference by splitting 586239462Sdim // the edge. 587239462Sdim // 588239462Sdim // If Reg *is* live-in to MBB, the interference is inevitable and a copy 589239462Sdim // is likely to be left after coalescing. If we are looking at a loop 590239462Sdim // exiting edge, split it so we won't insert code in the loop, otherwise 591239462Sdim // don't bother. 592249423Sdim bool ShouldSplit = !isLiveIn(Reg, &MBB) || SplitAllCriticalEdges; 593239462Sdim 594239462Sdim // Check for a loop exiting edge. 595239462Sdim if (!ShouldSplit && CurLoop != PreLoop) { 596239462Sdim DEBUG({ 597239462Sdim dbgs() << "Split wouldn't help, maybe avoid loop copies?\n"; 598239462Sdim if (PreLoop) dbgs() << "PreLoop: " << *PreLoop; 599239462Sdim if (CurLoop) dbgs() << "CurLoop: " << *CurLoop; 600239462Sdim }); 601239462Sdim // This edge could be entering a loop, exiting a loop, or it could be 602239462Sdim // both: Jumping directly form one loop to the header of a sibling 603239462Sdim // loop. 604239462Sdim // Split unless this edge is entering CurLoop from an outer loop. 605239462Sdim ShouldSplit = PreLoop && !PreLoop->contains(CurLoop); 606212904Sdim } 607239462Sdim if (!ShouldSplit) 608239462Sdim continue; 609239462Sdim if (!PreMBB->SplitCriticalEdge(&MBB, this)) { 610239462Sdim DEBUG(dbgs() << "Failed to split ciritcal edge.\n"); 611239462Sdim continue; 612239462Sdim } 613239462Sdim Changed = true; 614239462Sdim ++NumCriticalEdgesSplit; 615199481Srdivacky } 616199481Srdivacky } 617218893Sdim return Changed; 618199481Srdivacky} 619249423Sdim 620249423Sdimbool PHIElimination::isLiveIn(unsigned Reg, MachineBasicBlock *MBB) { 621249423Sdim assert((LV || LIS) && 622249423Sdim "isLiveIn() requires either LiveVariables or LiveIntervals"); 623249423Sdim if (LIS) 624249423Sdim return LIS->isLiveInToMBB(LIS->getInterval(Reg), MBB); 625249423Sdim else 626249423Sdim return LV->isLiveIn(Reg, *MBB); 627249423Sdim} 628249423Sdim 629249423Sdimbool PHIElimination::isLiveOutPastPHIs(unsigned Reg, MachineBasicBlock *MBB) { 630249423Sdim assert((LV || LIS) && 631249423Sdim "isLiveOutPastPHIs() requires either LiveVariables or LiveIntervals"); 632249423Sdim // LiveVariables considers uses in PHIs to be in the predecessor basic block, 633249423Sdim // so that a register used only in a PHI is not live out of the block. In 634249423Sdim // contrast, LiveIntervals considers uses in PHIs to be on the edge rather than 635249423Sdim // in the predecessor basic block, so that a register used only in a PHI is live 636249423Sdim // out of the block. 637249423Sdim if (LIS) { 638249423Sdim const LiveInterval &LI = LIS->getInterval(Reg); 639249423Sdim for (MachineBasicBlock::succ_iterator SI = MBB->succ_begin(), 640249423Sdim SE = MBB->succ_end(); SI != SE; ++SI) { 641249423Sdim if (LI.liveAt(LIS->getMBBStartIdx(*SI))) 642249423Sdim return true; 643249423Sdim } 644249423Sdim return false; 645249423Sdim } else { 646249423Sdim return LV->isLiveOut(Reg, *MBB); 647249423Sdim } 648249423Sdim} 649