PHIElimination.cpp revision 6a951ac63fd6a9aa769c6d98b544b886e5b5d307
1//===-- PhiElimination.cpp - Eliminate PHI nodes by inserting copies ------===// 2// 3// The LLVM Compiler Infrastructure 4// 5// This file is distributed under the University of Illinois Open Source 6// License. See LICENSE.TXT for details. 7// 8//===----------------------------------------------------------------------===// 9// 10// This pass eliminates machine instruction PHI nodes by inserting copy 11// instructions. This destroys SSA information, but is the desired input for 12// some register allocators. 13// 14//===----------------------------------------------------------------------===// 15 16#define DEBUG_TYPE "phielim" 17#include "PHIEliminationUtils.h" 18#include "llvm/CodeGen/LiveVariables.h" 19#include "llvm/CodeGen/Passes.h" 20#include "llvm/CodeGen/MachineDominators.h" 21#include "llvm/CodeGen/MachineInstr.h" 22#include "llvm/CodeGen/MachineInstrBuilder.h" 23#include "llvm/CodeGen/MachineLoopInfo.h" 24#include "llvm/CodeGen/MachineRegisterInfo.h" 25#include "llvm/Target/TargetInstrInfo.h" 26#include "llvm/Function.h" 27#include "llvm/Target/TargetMachine.h" 28#include "llvm/ADT/SmallPtrSet.h" 29#include "llvm/ADT/STLExtras.h" 30#include "llvm/ADT/Statistic.h" 31#include "llvm/Support/CommandLine.h" 32#include "llvm/Support/Compiler.h" 33#include "llvm/Support/Debug.h" 34#include <algorithm> 35#include <map> 36using namespace llvm; 37 38static cl::opt<bool> 39DisableEdgeSplitting("disable-phi-elim-edge-splitting", cl::init(false), 40 cl::Hidden, cl::desc("Disable critical edge splitting " 41 "during PHI elimination")); 42 43namespace { 44 class PHIElimination : public MachineFunctionPass { 45 MachineRegisterInfo *MRI; // Machine register information 46 47 public: 48 static char ID; // Pass identification, replacement for typeid 49 PHIElimination() : MachineFunctionPass(ID) { 50 initializePHIEliminationPass(*PassRegistry::getPassRegistry()); 51 } 52 53 virtual bool runOnMachineFunction(MachineFunction &Fn); 54 virtual void getAnalysisUsage(AnalysisUsage &AU) const; 55 56 private: 57 /// EliminatePHINodes - Eliminate phi nodes by inserting copy instructions 58 /// in predecessor basic blocks. 59 /// 60 bool EliminatePHINodes(MachineFunction &MF, MachineBasicBlock &MBB); 61 void LowerAtomicPHINode(MachineBasicBlock &MBB, 62 MachineBasicBlock::iterator AfterPHIsIt); 63 64 /// analyzePHINodes - Gather information about the PHI nodes in 65 /// here. In particular, we want to map the number of uses of a virtual 66 /// register which is used in a PHI node. We map that to the BB the 67 /// vreg is coming from. This is used later to determine when the vreg 68 /// is killed in the BB. 69 /// 70 void analyzePHINodes(const MachineFunction& Fn); 71 72 /// Split critical edges where necessary for good coalescer performance. 73 bool SplitPHIEdges(MachineFunction &MF, MachineBasicBlock &MBB, 74 LiveVariables &LV, MachineLoopInfo *MLI); 75 76 typedef std::pair<unsigned, unsigned> BBVRegPair; 77 typedef DenseMap<BBVRegPair, unsigned> VRegPHIUse; 78 79 VRegPHIUse VRegPHIUseCount; 80 81 // Defs of PHI sources which are implicit_def. 82 SmallPtrSet<MachineInstr*, 4> ImpDefs; 83 84 // Map reusable lowered PHI node -> incoming join register. 85 typedef DenseMap<MachineInstr*, unsigned, 86 MachineInstrExpressionTrait> LoweredPHIMap; 87 LoweredPHIMap LoweredPHIs; 88 }; 89} 90 91STATISTIC(NumAtomic, "Number of atomic phis lowered"); 92STATISTIC(NumCriticalEdgesSplit, "Number of critical edges split"); 93STATISTIC(NumReused, "Number of reused lowered phis"); 94 95char PHIElimination::ID = 0; 96INITIALIZE_PASS(PHIElimination, "phi-node-elimination", 97 "Eliminate PHI nodes for register allocation", false, false) 98 99char& llvm::PHIEliminationID = PHIElimination::ID; 100 101void PHIElimination::getAnalysisUsage(AnalysisUsage &AU) const { 102 AU.addPreserved<LiveVariables>(); 103 AU.addPreserved<MachineDominatorTree>(); 104 AU.addPreserved<MachineLoopInfo>(); 105 MachineFunctionPass::getAnalysisUsage(AU); 106} 107 108bool PHIElimination::runOnMachineFunction(MachineFunction &MF) { 109 MRI = &MF.getRegInfo(); 110 111 bool Changed = false; 112 113 // Split critical edges to help the coalescer 114 if (!DisableEdgeSplitting) { 115 if (LiveVariables *LV = getAnalysisIfAvailable<LiveVariables>()) { 116 MachineLoopInfo *MLI = getAnalysisIfAvailable<MachineLoopInfo>(); 117 for (MachineFunction::iterator I = MF.begin(), E = MF.end(); I != E; ++I) 118 Changed |= SplitPHIEdges(MF, *I, *LV, MLI); 119 } 120 } 121 122 // Populate VRegPHIUseCount 123 analyzePHINodes(MF); 124 125 // Eliminate PHI instructions by inserting copies into predecessor blocks. 126 for (MachineFunction::iterator I = MF.begin(), E = MF.end(); I != E; ++I) 127 Changed |= EliminatePHINodes(MF, *I); 128 129 // Remove dead IMPLICIT_DEF instructions. 130 for (SmallPtrSet<MachineInstr*, 4>::iterator I = ImpDefs.begin(), 131 E = ImpDefs.end(); I != E; ++I) { 132 MachineInstr *DefMI = *I; 133 unsigned DefReg = DefMI->getOperand(0).getReg(); 134 if (MRI->use_nodbg_empty(DefReg)) 135 DefMI->eraseFromParent(); 136 } 137 138 // Clean up the lowered PHI instructions. 139 for (LoweredPHIMap::iterator I = LoweredPHIs.begin(), E = LoweredPHIs.end(); 140 I != E; ++I) 141 MF.DeleteMachineInstr(I->first); 142 143 LoweredPHIs.clear(); 144 ImpDefs.clear(); 145 VRegPHIUseCount.clear(); 146 147 return Changed; 148} 149 150/// EliminatePHINodes - Eliminate phi nodes by inserting copy instructions in 151/// predecessor basic blocks. 152/// 153bool PHIElimination::EliminatePHINodes(MachineFunction &MF, 154 MachineBasicBlock &MBB) { 155 if (MBB.empty() || !MBB.front().isPHI()) 156 return false; // Quick exit for basic blocks without PHIs. 157 158 // Get an iterator to the first instruction after the last PHI node (this may 159 // also be the end of the basic block). 160 MachineBasicBlock::iterator AfterPHIsIt = MBB.SkipPHIsAndLabels(MBB.begin()); 161 162 while (MBB.front().isPHI()) 163 LowerAtomicPHINode(MBB, AfterPHIsIt); 164 165 return true; 166} 167 168/// isSourceDefinedByImplicitDef - Return true if all sources of the phi node 169/// are implicit_def's. 170static bool isSourceDefinedByImplicitDef(const MachineInstr *MPhi, 171 const MachineRegisterInfo *MRI) { 172 for (unsigned i = 1; i != MPhi->getNumOperands(); i += 2) { 173 unsigned SrcReg = MPhi->getOperand(i).getReg(); 174 const MachineInstr *DefMI = MRI->getVRegDef(SrcReg); 175 if (!DefMI || !DefMI->isImplicitDef()) 176 return false; 177 } 178 return true; 179} 180 181 182 183/// LowerAtomicPHINode - Lower the PHI node at the top of the specified block, 184/// under the assuption that it needs to be lowered in a way that supports 185/// atomic execution of PHIs. This lowering method is always correct all of the 186/// time. 187/// 188void PHIElimination::LowerAtomicPHINode( 189 MachineBasicBlock &MBB, 190 MachineBasicBlock::iterator AfterPHIsIt) { 191 ++NumAtomic; 192 // Unlink the PHI node from the basic block, but don't delete the PHI yet. 193 MachineInstr *MPhi = MBB.remove(MBB.begin()); 194 195 unsigned NumSrcs = (MPhi->getNumOperands() - 1) / 2; 196 unsigned DestReg = MPhi->getOperand(0).getReg(); 197 assert(MPhi->getOperand(0).getSubReg() == 0 && "Can't handle sub-reg PHIs"); 198 bool isDead = MPhi->getOperand(0).isDead(); 199 200 // Create a new register for the incoming PHI arguments. 201 MachineFunction &MF = *MBB.getParent(); 202 unsigned IncomingReg = 0; 203 bool reusedIncoming = false; // Is IncomingReg reused from an earlier PHI? 204 205 // Insert a register to register copy at the top of the current block (but 206 // after any remaining phi nodes) which copies the new incoming register 207 // into the phi node destination. 208 const TargetInstrInfo *TII = MF.getTarget().getInstrInfo(); 209 if (isSourceDefinedByImplicitDef(MPhi, MRI)) 210 // If all sources of a PHI node are implicit_def, just emit an 211 // implicit_def instead of a copy. 212 BuildMI(MBB, AfterPHIsIt, MPhi->getDebugLoc(), 213 TII->get(TargetOpcode::IMPLICIT_DEF), DestReg); 214 else { 215 // Can we reuse an earlier PHI node? This only happens for critical edges, 216 // typically those created by tail duplication. 217 unsigned &entry = LoweredPHIs[MPhi]; 218 if (entry) { 219 // An identical PHI node was already lowered. Reuse the incoming register. 220 IncomingReg = entry; 221 reusedIncoming = true; 222 ++NumReused; 223 DEBUG(dbgs() << "Reusing " << PrintReg(IncomingReg) << " for " << *MPhi); 224 } else { 225 const TargetRegisterClass *RC = MF.getRegInfo().getRegClass(DestReg); 226 entry = IncomingReg = MF.getRegInfo().createVirtualRegister(RC); 227 } 228 BuildMI(MBB, AfterPHIsIt, MPhi->getDebugLoc(), 229 TII->get(TargetOpcode::COPY), DestReg) 230 .addReg(IncomingReg); 231 } 232 233 // Update live variable information if there is any. 234 LiveVariables *LV = getAnalysisIfAvailable<LiveVariables>(); 235 if (LV) { 236 MachineInstr *PHICopy = prior(AfterPHIsIt); 237 238 if (IncomingReg) { 239 LiveVariables::VarInfo &VI = LV->getVarInfo(IncomingReg); 240 241 // Increment use count of the newly created virtual register. 242 VI.NumUses++; 243 LV->setPHIJoin(IncomingReg); 244 245 // When we are reusing the incoming register, it may already have been 246 // killed in this block. The old kill will also have been inserted at 247 // AfterPHIsIt, so it appears before the current PHICopy. 248 if (reusedIncoming) 249 if (MachineInstr *OldKill = VI.findKill(&MBB)) { 250 DEBUG(dbgs() << "Remove old kill from " << *OldKill); 251 LV->removeVirtualRegisterKilled(IncomingReg, OldKill); 252 DEBUG(MBB.dump()); 253 } 254 255 // Add information to LiveVariables to know that the incoming value is 256 // killed. Note that because the value is defined in several places (once 257 // each for each incoming block), the "def" block and instruction fields 258 // for the VarInfo is not filled in. 259 LV->addVirtualRegisterKilled(IncomingReg, PHICopy); 260 } 261 262 // Since we are going to be deleting the PHI node, if it is the last use of 263 // any registers, or if the value itself is dead, we need to move this 264 // information over to the new copy we just inserted. 265 LV->removeVirtualRegistersKilled(MPhi); 266 267 // If the result is dead, update LV. 268 if (isDead) { 269 LV->addVirtualRegisterDead(DestReg, PHICopy); 270 LV->removeVirtualRegisterDead(DestReg, MPhi); 271 } 272 } 273 274 // Adjust the VRegPHIUseCount map to account for the removal of this PHI node. 275 for (unsigned i = 1; i != MPhi->getNumOperands(); i += 2) 276 --VRegPHIUseCount[BBVRegPair(MPhi->getOperand(i+1).getMBB()->getNumber(), 277 MPhi->getOperand(i).getReg())]; 278 279 // Now loop over all of the incoming arguments, changing them to copy into the 280 // IncomingReg register in the corresponding predecessor basic block. 281 SmallPtrSet<MachineBasicBlock*, 8> MBBsInsertedInto; 282 for (int i = NumSrcs - 1; i >= 0; --i) { 283 unsigned SrcReg = MPhi->getOperand(i*2+1).getReg(); 284 unsigned SrcSubReg = MPhi->getOperand(i*2+1).getSubReg(); 285 286 assert(TargetRegisterInfo::isVirtualRegister(SrcReg) && 287 "Machine PHI Operands must all be virtual registers!"); 288 289 // Get the MachineBasicBlock equivalent of the BasicBlock that is the source 290 // path the PHI. 291 MachineBasicBlock &opBlock = *MPhi->getOperand(i*2+2).getMBB(); 292 293 // If source is defined by an implicit def, there is no need to insert a 294 // copy. 295 MachineInstr *DefMI = MRI->getVRegDef(SrcReg); 296 if (DefMI->isImplicitDef()) { 297 ImpDefs.insert(DefMI); 298 continue; 299 } 300 301 // Check to make sure we haven't already emitted the copy for this block. 302 // This can happen because PHI nodes may have multiple entries for the same 303 // basic block. 304 if (!MBBsInsertedInto.insert(&opBlock)) 305 continue; // If the copy has already been emitted, we're done. 306 307 // Find a safe location to insert the copy, this may be the first terminator 308 // in the block (or end()). 309 MachineBasicBlock::iterator InsertPos = 310 findPHICopyInsertPoint(&opBlock, &MBB, SrcReg); 311 312 // Insert the copy. 313 if (!reusedIncoming && IncomingReg) 314 BuildMI(opBlock, InsertPos, MPhi->getDebugLoc(), 315 TII->get(TargetOpcode::COPY), IncomingReg).addReg(SrcReg, 0, SrcSubReg); 316 317 // Now update live variable information if we have it. Otherwise we're done 318 if (!LV) continue; 319 320 // We want to be able to insert a kill of the register if this PHI (aka, the 321 // copy we just inserted) is the last use of the source value. Live 322 // variable analysis conservatively handles this by saying that the value is 323 // live until the end of the block the PHI entry lives in. If the value 324 // really is dead at the PHI copy, there will be no successor blocks which 325 // have the value live-in. 326 327 // Also check to see if this register is in use by another PHI node which 328 // has not yet been eliminated. If so, it will be killed at an appropriate 329 // point later. 330 331 // Is it used by any PHI instructions in this block? 332 bool ValueIsUsed = VRegPHIUseCount[BBVRegPair(opBlock.getNumber(), SrcReg)]; 333 334 // Okay, if we now know that the value is not live out of the block, we can 335 // add a kill marker in this block saying that it kills the incoming value! 336 if (!ValueIsUsed && !LV->isLiveOut(SrcReg, opBlock)) { 337 // In our final twist, we have to decide which instruction kills the 338 // register. In most cases this is the copy, however, the first 339 // terminator instruction at the end of the block may also use the value. 340 // In this case, we should mark *it* as being the killing block, not the 341 // copy. 342 MachineBasicBlock::iterator KillInst; 343 MachineBasicBlock::iterator Term = opBlock.getFirstTerminator(); 344 if (Term != opBlock.end() && Term->readsRegister(SrcReg)) { 345 KillInst = Term; 346 347 // Check that no other terminators use values. 348#ifndef NDEBUG 349 for (MachineBasicBlock::iterator TI = llvm::next(Term); 350 TI != opBlock.end(); ++TI) { 351 if (TI->isDebugValue()) 352 continue; 353 assert(!TI->readsRegister(SrcReg) && 354 "Terminator instructions cannot use virtual registers unless" 355 "they are the first terminator in a block!"); 356 } 357#endif 358 } else if (reusedIncoming || !IncomingReg) { 359 // We may have to rewind a bit if we didn't insert a copy this time. 360 KillInst = Term; 361 while (KillInst != opBlock.begin()) { 362 --KillInst; 363 if (KillInst->isDebugValue()) 364 continue; 365 if (KillInst->readsRegister(SrcReg)) 366 break; 367 } 368 } else { 369 // We just inserted this copy. 370 KillInst = prior(InsertPos); 371 } 372 assert(KillInst->readsRegister(SrcReg) && "Cannot find kill instruction"); 373 374 // Finally, mark it killed. 375 LV->addVirtualRegisterKilled(SrcReg, KillInst); 376 377 // This vreg no longer lives all of the way through opBlock. 378 unsigned opBlockNum = opBlock.getNumber(); 379 LV->getVarInfo(SrcReg).AliveBlocks.reset(opBlockNum); 380 } 381 } 382 383 // Really delete the PHI instruction now, if it is not in the LoweredPHIs map. 384 if (reusedIncoming || !IncomingReg) 385 MF.DeleteMachineInstr(MPhi); 386} 387 388/// analyzePHINodes - Gather information about the PHI nodes in here. In 389/// particular, we want to map the number of uses of a virtual register which is 390/// used in a PHI node. We map that to the BB the vreg is coming from. This is 391/// used later to determine when the vreg is killed in the BB. 392/// 393void PHIElimination::analyzePHINodes(const MachineFunction& MF) { 394 for (MachineFunction::const_iterator I = MF.begin(), E = MF.end(); 395 I != E; ++I) 396 for (MachineBasicBlock::const_iterator BBI = I->begin(), BBE = I->end(); 397 BBI != BBE && BBI->isPHI(); ++BBI) 398 for (unsigned i = 1, e = BBI->getNumOperands(); i != e; i += 2) 399 ++VRegPHIUseCount[BBVRegPair(BBI->getOperand(i+1).getMBB()->getNumber(), 400 BBI->getOperand(i).getReg())]; 401} 402 403bool PHIElimination::SplitPHIEdges(MachineFunction &MF, 404 MachineBasicBlock &MBB, 405 LiveVariables &LV, 406 MachineLoopInfo *MLI) { 407 if (MBB.empty() || !MBB.front().isPHI() || MBB.isLandingPad()) 408 return false; // Quick exit for basic blocks without PHIs. 409 410 bool Changed = false; 411 for (MachineBasicBlock::const_iterator BBI = MBB.begin(), BBE = MBB.end(); 412 BBI != BBE && BBI->isPHI(); ++BBI) { 413 for (unsigned i = 1, e = BBI->getNumOperands(); i != e; i += 2) { 414 unsigned Reg = BBI->getOperand(i).getReg(); 415 MachineBasicBlock *PreMBB = BBI->getOperand(i+1).getMBB(); 416 // We break edges when registers are live out from the predecessor block 417 // (not considering PHI nodes). If the register is live in to this block 418 // anyway, we would gain nothing from splitting. 419 // Avoid splitting backedges of loops. It would introduce small 420 // out-of-line blocks into the loop which is very bad for code placement. 421 if (PreMBB != &MBB && 422 !LV.isLiveIn(Reg, MBB) && LV.isLiveOut(Reg, *PreMBB)) { 423 if (!MLI || 424 !(MLI->getLoopFor(PreMBB) == MLI->getLoopFor(&MBB) && 425 MLI->isLoopHeader(&MBB))) { 426 if (PreMBB->SplitCriticalEdge(&MBB, this)) { 427 Changed = true; 428 ++NumCriticalEdgesSplit; 429 } 430 } 431 } 432 } 433 } 434 return Changed; 435} 436