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 using namespace llvm; 36 37 static cl::opt<bool> 38 DisableEdgeSplitting("disable-phi-elim-edge-splitting", cl::init(false), 39 cl::Hidden, cl::desc("Disable critical edge splitting " 40 "during PHI elimination")); 41 42 namespace { 43 class PHIElimination : public MachineFunctionPass { 44 MachineRegisterInfo *MRI; // Machine register information 45 46 public: 47 static char ID; // Pass identification, replacement for typeid 48 PHIElimination() : MachineFunctionPass(ID) { 49 initializePHIEliminationPass(*PassRegistry::getPassRegistry()); 50 } 51 52 virtual bool runOnMachineFunction(MachineFunction &Fn); 53 virtual void getAnalysisUsage(AnalysisUsage &AU) const; 54 55 private: 56 /// EliminatePHINodes - Eliminate phi nodes by inserting copy instructions 57 /// in predecessor basic blocks. 58 /// 59 bool EliminatePHINodes(MachineFunction &MF, MachineBasicBlock &MBB); 60 void LowerAtomicPHINode(MachineBasicBlock &MBB, 61 MachineBasicBlock::iterator AfterPHIsIt); 62 63 /// analyzePHINodes - Gather information about the PHI nodes in 64 /// here. In particular, we want to map the number of uses of a virtual 65 /// register which is used in a PHI node. We map that to the BB the 66 /// vreg is coming from. This is used later to determine when the vreg 67 /// is killed in the BB. 68 /// 69 void analyzePHINodes(const MachineFunction& Fn); 70 71 /// Split critical edges where necessary for good coalescer performance. 72 bool SplitPHIEdges(MachineFunction &MF, MachineBasicBlock &MBB, 73 LiveVariables &LV, MachineLoopInfo *MLI); 74 75 typedef std::pair<unsigned, unsigned> BBVRegPair; 76 typedef DenseMap<BBVRegPair, unsigned> VRegPHIUse; 77 78 VRegPHIUse VRegPHIUseCount; 79 80 // Defs of PHI sources which are implicit_def. 81 SmallPtrSet<MachineInstr*, 4> ImpDefs; 82 83 // Map reusable lowered PHI node -> incoming join register. 84 typedef DenseMap<MachineInstr*, unsigned, 85 MachineInstrExpressionTrait> LoweredPHIMap; 86 LoweredPHIMap LoweredPHIs; 87 }; 88 } 89 90 STATISTIC(NumAtomic, "Number of atomic phis lowered"); 91 STATISTIC(NumCriticalEdgesSplit, "Number of critical edges split"); 92 STATISTIC(NumReused, "Number of reused lowered phis"); 93 94 char PHIElimination::ID = 0; 95 char& llvm::PHIEliminationID = PHIElimination::ID; 96 97 INITIALIZE_PASS_BEGIN(PHIElimination, "phi-node-elimination", 98 "Eliminate PHI nodes for register allocation", 99 false, false) 100 INITIALIZE_PASS_DEPENDENCY(LiveVariables) 101 INITIALIZE_PASS_END(PHIElimination, "phi-node-elimination", 102 "Eliminate PHI nodes for register allocation", false, false) 103 104 void PHIElimination::getAnalysisUsage(AnalysisUsage &AU) const { 105 AU.addPreserved<LiveVariables>(); 106 AU.addPreserved<MachineDominatorTree>(); 107 AU.addPreserved<MachineLoopInfo>(); 108 MachineFunctionPass::getAnalysisUsage(AU); 109 } 110 111 bool PHIElimination::runOnMachineFunction(MachineFunction &MF) { 112 MRI = &MF.getRegInfo(); 113 114 bool Changed = false; 115 116 // This pass takes the function out of SSA form. 117 MRI->leaveSSA(); 118 119 // Split critical edges to help the coalescer 120 if (!DisableEdgeSplitting) { 121 if (LiveVariables *LV = getAnalysisIfAvailable<LiveVariables>()) { 122 MachineLoopInfo *MLI = getAnalysisIfAvailable<MachineLoopInfo>(); 123 for (MachineFunction::iterator I = MF.begin(), E = MF.end(); I != E; ++I) 124 Changed |= SplitPHIEdges(MF, *I, *LV, MLI); 125 } 126 } 127 128 // Populate VRegPHIUseCount 129 analyzePHINodes(MF); 130 131 // Eliminate PHI instructions by inserting copies into predecessor blocks. 132 for (MachineFunction::iterator I = MF.begin(), E = MF.end(); I != E; ++I) 133 Changed |= EliminatePHINodes(MF, *I); 134 135 // Remove dead IMPLICIT_DEF instructions. 136 for (SmallPtrSet<MachineInstr*, 4>::iterator I = ImpDefs.begin(), 137 E = ImpDefs.end(); I != E; ++I) { 138 MachineInstr *DefMI = *I; 139 unsigned DefReg = DefMI->getOperand(0).getReg(); 140 if (MRI->use_nodbg_empty(DefReg)) 141 DefMI->eraseFromParent(); 142 } 143 144 // Clean up the lowered PHI instructions. 145 for (LoweredPHIMap::iterator I = LoweredPHIs.begin(), E = LoweredPHIs.end(); 146 I != E; ++I) 147 MF.DeleteMachineInstr(I->first); 148 149 LoweredPHIs.clear(); 150 ImpDefs.clear(); 151 VRegPHIUseCount.clear(); 152 153 return Changed; 154 } 155 156 /// EliminatePHINodes - Eliminate phi nodes by inserting copy instructions in 157 /// predecessor basic blocks. 158 /// 159 bool PHIElimination::EliminatePHINodes(MachineFunction &MF, 160 MachineBasicBlock &MBB) { 161 if (MBB.empty() || !MBB.front().isPHI()) 162 return false; // Quick exit for basic blocks without PHIs. 163 164 // Get an iterator to the first instruction after the last PHI node (this may 165 // also be the end of the basic block). 166 MachineBasicBlock::iterator AfterPHIsIt = MBB.SkipPHIsAndLabels(MBB.begin()); 167 168 while (MBB.front().isPHI()) 169 LowerAtomicPHINode(MBB, AfterPHIsIt); 170 171 return true; 172 } 173 174 /// isImplicitlyDefined - Return true if all defs of VirtReg are implicit-defs. 175 /// This includes registers with no defs. 176 static bool isImplicitlyDefined(unsigned VirtReg, 177 const MachineRegisterInfo *MRI) { 178 for (MachineRegisterInfo::def_iterator DI = MRI->def_begin(VirtReg), 179 DE = MRI->def_end(); DI != DE; ++DI) 180 if (!DI->isImplicitDef()) 181 return false; 182 return true; 183 } 184 185 /// isSourceDefinedByImplicitDef - Return true if all sources of the phi node 186 /// are implicit_def's. 187 static bool isSourceDefinedByImplicitDef(const MachineInstr *MPhi, 188 const MachineRegisterInfo *MRI) { 189 for (unsigned i = 1; i != MPhi->getNumOperands(); i += 2) 190 if (!isImplicitlyDefined(MPhi->getOperand(i).getReg(), MRI)) 191 return false; 192 return true; 193 } 194 195 196 /// LowerAtomicPHINode - Lower the PHI node at the top of the specified block, 197 /// under the assumption that it needs to be lowered in a way that supports 198 /// atomic execution of PHIs. This lowering method is always correct all of the 199 /// time. 200 /// 201 void PHIElimination::LowerAtomicPHINode( 202 MachineBasicBlock &MBB, 203 MachineBasicBlock::iterator AfterPHIsIt) { 204 ++NumAtomic; 205 // Unlink the PHI node from the basic block, but don't delete the PHI yet. 206 MachineInstr *MPhi = MBB.remove(MBB.begin()); 207 208 unsigned NumSrcs = (MPhi->getNumOperands() - 1) / 2; 209 unsigned DestReg = MPhi->getOperand(0).getReg(); 210 assert(MPhi->getOperand(0).getSubReg() == 0 && "Can't handle sub-reg PHIs"); 211 bool isDead = MPhi->getOperand(0).isDead(); 212 213 // Create a new register for the incoming PHI arguments. 214 MachineFunction &MF = *MBB.getParent(); 215 unsigned IncomingReg = 0; 216 bool reusedIncoming = false; // Is IncomingReg reused from an earlier PHI? 217 218 // Insert a register to register copy at the top of the current block (but 219 // after any remaining phi nodes) which copies the new incoming register 220 // into the phi node destination. 221 const TargetInstrInfo *TII = MF.getTarget().getInstrInfo(); 222 if (isSourceDefinedByImplicitDef(MPhi, MRI)) 223 // If all sources of a PHI node are implicit_def, just emit an 224 // implicit_def instead of a copy. 225 BuildMI(MBB, AfterPHIsIt, MPhi->getDebugLoc(), 226 TII->get(TargetOpcode::IMPLICIT_DEF), DestReg); 227 else { 228 // Can we reuse an earlier PHI node? This only happens for critical edges, 229 // typically those created by tail duplication. 230 unsigned &entry = LoweredPHIs[MPhi]; 231 if (entry) { 232 // An identical PHI node was already lowered. Reuse the incoming register. 233 IncomingReg = entry; 234 reusedIncoming = true; 235 ++NumReused; 236 DEBUG(dbgs() << "Reusing " << PrintReg(IncomingReg) << " for " << *MPhi); 237 } else { 238 const TargetRegisterClass *RC = MF.getRegInfo().getRegClass(DestReg); 239 entry = IncomingReg = MF.getRegInfo().createVirtualRegister(RC); 240 } 241 BuildMI(MBB, AfterPHIsIt, MPhi->getDebugLoc(), 242 TII->get(TargetOpcode::COPY), DestReg) 243 .addReg(IncomingReg); 244 } 245 246 // Update live variable information if there is any. 247 LiveVariables *LV = getAnalysisIfAvailable<LiveVariables>(); 248 if (LV) { 249 MachineInstr *PHICopy = prior(AfterPHIsIt); 250 251 if (IncomingReg) { 252 LiveVariables::VarInfo &VI = LV->getVarInfo(IncomingReg); 253 254 // Increment use count of the newly created virtual register. 255 LV->setPHIJoin(IncomingReg); 256 257 // When we are reusing the incoming register, it may already have been 258 // killed in this block. The old kill will also have been inserted at 259 // AfterPHIsIt, so it appears before the current PHICopy. 260 if (reusedIncoming) 261 if (MachineInstr *OldKill = VI.findKill(&MBB)) { 262 DEBUG(dbgs() << "Remove old kill from " << *OldKill); 263 LV->removeVirtualRegisterKilled(IncomingReg, OldKill); 264 DEBUG(MBB.dump()); 265 } 266 267 // Add information to LiveVariables to know that the incoming value is 268 // killed. Note that because the value is defined in several places (once 269 // each for each incoming block), the "def" block and instruction fields 270 // for the VarInfo is not filled in. 271 LV->addVirtualRegisterKilled(IncomingReg, PHICopy); 272 } 273 274 // Since we are going to be deleting the PHI node, if it is the last use of 275 // any registers, or if the value itself is dead, we need to move this 276 // information over to the new copy we just inserted. 277 LV->removeVirtualRegistersKilled(MPhi); 278 279 // If the result is dead, update LV. 280 if (isDead) { 281 LV->addVirtualRegisterDead(DestReg, PHICopy); 282 LV->removeVirtualRegisterDead(DestReg, MPhi); 283 } 284 } 285 286 // Adjust the VRegPHIUseCount map to account for the removal of this PHI node. 287 for (unsigned i = 1; i != MPhi->getNumOperands(); i += 2) 288 --VRegPHIUseCount[BBVRegPair(MPhi->getOperand(i+1).getMBB()->getNumber(), 289 MPhi->getOperand(i).getReg())]; 290 291 // Now loop over all of the incoming arguments, changing them to copy into the 292 // IncomingReg register in the corresponding predecessor basic block. 293 SmallPtrSet<MachineBasicBlock*, 8> MBBsInsertedInto; 294 for (int i = NumSrcs - 1; i >= 0; --i) { 295 unsigned SrcReg = MPhi->getOperand(i*2+1).getReg(); 296 unsigned SrcSubReg = MPhi->getOperand(i*2+1).getSubReg(); 297 bool SrcUndef = MPhi->getOperand(i*2+1).isUndef() || 298 isImplicitlyDefined(SrcReg, MRI); 299 assert(TargetRegisterInfo::isVirtualRegister(SrcReg) && 300 "Machine PHI Operands must all be virtual registers!"); 301 302 // Get the MachineBasicBlock equivalent of the BasicBlock that is the source 303 // path the PHI. 304 MachineBasicBlock &opBlock = *MPhi->getOperand(i*2+2).getMBB(); 305 306 // Check to make sure we haven't already emitted the copy for this block. 307 // This can happen because PHI nodes may have multiple entries for the same 308 // basic block. 309 if (!MBBsInsertedInto.insert(&opBlock)) 310 continue; // If the copy has already been emitted, we're done. 311 312 // Find a safe location to insert the copy, this may be the first terminator 313 // in the block (or end()). 314 MachineBasicBlock::iterator InsertPos = 315 findPHICopyInsertPoint(&opBlock, &MBB, SrcReg); 316 317 // Insert the copy. 318 if (!reusedIncoming && IncomingReg) { 319 if (SrcUndef) { 320 // The source register is undefined, so there is no need for a real 321 // COPY, but we still need to ensure joint dominance by defs. 322 // Insert an IMPLICIT_DEF instruction. 323 BuildMI(opBlock, InsertPos, MPhi->getDebugLoc(), 324 TII->get(TargetOpcode::IMPLICIT_DEF), IncomingReg); 325 326 // Clean up the old implicit-def, if there even was one. 327 if (MachineInstr *DefMI = MRI->getVRegDef(SrcReg)) 328 if (DefMI->isImplicitDef()) 329 ImpDefs.insert(DefMI); 330 } else { 331 BuildMI(opBlock, InsertPos, MPhi->getDebugLoc(), 332 TII->get(TargetOpcode::COPY), IncomingReg) 333 .addReg(SrcReg, 0, SrcSubReg); 334 } 335 } 336 337 // Now update live variable information if we have it. Otherwise we're done 338 if (SrcUndef || !LV) continue; 339 340 // We want to be able to insert a kill of the register if this PHI (aka, the 341 // copy we just inserted) is the last use of the source value. Live 342 // variable analysis conservatively handles this by saying that the value is 343 // live until the end of the block the PHI entry lives in. If the value 344 // really is dead at the PHI copy, there will be no successor blocks which 345 // have the value live-in. 346 347 // Also check to see if this register is in use by another PHI node which 348 // has not yet been eliminated. If so, it will be killed at an appropriate 349 // point later. 350 351 // Is it used by any PHI instructions in this block? 352 bool ValueIsUsed = VRegPHIUseCount[BBVRegPair(opBlock.getNumber(), SrcReg)]; 353 354 // Okay, if we now know that the value is not live out of the block, we can 355 // add a kill marker in this block saying that it kills the incoming value! 356 if (!ValueIsUsed && !LV->isLiveOut(SrcReg, opBlock)) { 357 // In our final twist, we have to decide which instruction kills the 358 // register. In most cases this is the copy, however, terminator 359 // instructions at the end of the block may also use the value. In this 360 // case, we should mark the last such terminator as being the killing 361 // block, not the copy. 362 MachineBasicBlock::iterator KillInst = opBlock.end(); 363 MachineBasicBlock::iterator FirstTerm = opBlock.getFirstTerminator(); 364 for (MachineBasicBlock::iterator Term = FirstTerm; 365 Term != opBlock.end(); ++Term) { 366 if (Term->readsRegister(SrcReg)) 367 KillInst = Term; 368 } 369 370 if (KillInst == opBlock.end()) { 371 // No terminator uses the register. 372 373 if (reusedIncoming || !IncomingReg) { 374 // We may have to rewind a bit if we didn't insert a copy this time. 375 KillInst = FirstTerm; 376 while (KillInst != opBlock.begin()) { 377 --KillInst; 378 if (KillInst->isDebugValue()) 379 continue; 380 if (KillInst->readsRegister(SrcReg)) 381 break; 382 } 383 } else { 384 // We just inserted this copy. 385 KillInst = prior(InsertPos); 386 } 387 } 388 assert(KillInst->readsRegister(SrcReg) && "Cannot find kill instruction"); 389 390 // Finally, mark it killed. 391 LV->addVirtualRegisterKilled(SrcReg, KillInst); 392 393 // This vreg no longer lives all of the way through opBlock. 394 unsigned opBlockNum = opBlock.getNumber(); 395 LV->getVarInfo(SrcReg).AliveBlocks.reset(opBlockNum); 396 } 397 } 398 399 // Really delete the PHI instruction now, if it is not in the LoweredPHIs map. 400 if (reusedIncoming || !IncomingReg) 401 MF.DeleteMachineInstr(MPhi); 402 } 403 404 /// analyzePHINodes - Gather information about the PHI nodes in here. In 405 /// particular, we want to map the number of uses of a virtual register which is 406 /// used in a PHI node. We map that to the BB the vreg is coming from. This is 407 /// used later to determine when the vreg is killed in the BB. 408 /// 409 void PHIElimination::analyzePHINodes(const MachineFunction& MF) { 410 for (MachineFunction::const_iterator I = MF.begin(), E = MF.end(); 411 I != E; ++I) 412 for (MachineBasicBlock::const_iterator BBI = I->begin(), BBE = I->end(); 413 BBI != BBE && BBI->isPHI(); ++BBI) 414 for (unsigned i = 1, e = BBI->getNumOperands(); i != e; i += 2) 415 ++VRegPHIUseCount[BBVRegPair(BBI->getOperand(i+1).getMBB()->getNumber(), 416 BBI->getOperand(i).getReg())]; 417 } 418 419 bool PHIElimination::SplitPHIEdges(MachineFunction &MF, 420 MachineBasicBlock &MBB, 421 LiveVariables &LV, 422 MachineLoopInfo *MLI) { 423 if (MBB.empty() || !MBB.front().isPHI() || MBB.isLandingPad()) 424 return false; // Quick exit for basic blocks without PHIs. 425 426 const MachineLoop *CurLoop = MLI ? MLI->getLoopFor(&MBB) : 0; 427 bool IsLoopHeader = CurLoop && &MBB == CurLoop->getHeader(); 428 429 bool Changed = false; 430 for (MachineBasicBlock::iterator BBI = MBB.begin(), BBE = MBB.end(); 431 BBI != BBE && BBI->isPHI(); ++BBI) { 432 for (unsigned i = 1, e = BBI->getNumOperands(); i != e; i += 2) { 433 unsigned Reg = BBI->getOperand(i).getReg(); 434 MachineBasicBlock *PreMBB = BBI->getOperand(i+1).getMBB(); 435 // Is there a critical edge from PreMBB to MBB? 436 if (PreMBB->succ_size() == 1) 437 continue; 438 439 // Avoid splitting backedges of loops. It would introduce small 440 // out-of-line blocks into the loop which is very bad for code placement. 441 if (PreMBB == &MBB) 442 continue; 443 const MachineLoop *PreLoop = MLI ? MLI->getLoopFor(PreMBB) : 0; 444 if (IsLoopHeader && PreLoop == CurLoop) 445 continue; 446 447 // LV doesn't consider a phi use live-out, so isLiveOut only returns true 448 // when the source register is live-out for some other reason than a phi 449 // use. That means the copy we will insert in PreMBB won't be a kill, and 450 // there is a risk it may not be coalesced away. 451 // 452 // If the copy would be a kill, there is no need to split the edge. 453 if (!LV.isLiveOut(Reg, *PreMBB)) 454 continue; 455 456 DEBUG(dbgs() << PrintReg(Reg) << " live-out before critical edge BB#" 457 << PreMBB->getNumber() << " -> BB#" << MBB.getNumber() 458 << ": " << *BBI); 459 460 // If Reg is not live-in to MBB, it means it must be live-in to some 461 // other PreMBB successor, and we can avoid the interference by splitting 462 // the edge. 463 // 464 // If Reg *is* live-in to MBB, the interference is inevitable and a copy 465 // is likely to be left after coalescing. If we are looking at a loop 466 // exiting edge, split it so we won't insert code in the loop, otherwise 467 // don't bother. 468 bool ShouldSplit = !LV.isLiveIn(Reg, MBB); 469 470 // Check for a loop exiting edge. 471 if (!ShouldSplit && CurLoop != PreLoop) { 472 DEBUG({ 473 dbgs() << "Split wouldn't help, maybe avoid loop copies?\n"; 474 if (PreLoop) dbgs() << "PreLoop: " << *PreLoop; 475 if (CurLoop) dbgs() << "CurLoop: " << *CurLoop; 476 }); 477 // This edge could be entering a loop, exiting a loop, or it could be 478 // both: Jumping directly form one loop to the header of a sibling 479 // loop. 480 // Split unless this edge is entering CurLoop from an outer loop. 481 ShouldSplit = PreLoop && !PreLoop->contains(CurLoop); 482 } 483 if (!ShouldSplit) 484 continue; 485 if (!PreMBB->SplitCriticalEdge(&MBB, this)) { 486 DEBUG(dbgs() << "Failed to split ciritcal edge.\n"); 487 continue; 488 } 489 Changed = true; 490 ++NumCriticalEdgesSplit; 491 } 492 } 493 return Changed; 494 } 495