LLVM API Documentation
00001 //===- StrongPhiElimination.cpp - Eliminate PHI nodes by inserting copies -===// 00002 // 00003 // The LLVM Compiler Infrastructure 00004 // 00005 // This file is distributed under the University of Illinois Open Source 00006 // License. See LICENSE.TXT for details. 00007 // 00008 //===----------------------------------------------------------------------===// 00009 // 00010 // This pass eliminates machine instruction PHI nodes by inserting copy 00011 // instructions, using an intelligent copy-folding technique based on 00012 // dominator information. This is technique is derived from: 00013 // 00014 // Budimlic, et al. Fast copy coalescing and live-range identification. 00015 // In Proceedings of the ACM SIGPLAN 2002 Conference on Programming Language 00016 // Design and Implementation (Berlin, Germany, June 17 - 19, 2002). 00017 // PLDI '02. ACM, New York, NY, 25-32. 00018 // DOI= http://doi.acm.org/10.1145/512529.512534 00019 // 00020 //===----------------------------------------------------------------------===// 00021 00022 #define DEBUG_TYPE "strongphielim" 00023 #include "llvm/CodeGen/Passes.h" 00024 #include "llvm/CodeGen/LiveIntervalAnalysis.h" 00025 #include "llvm/CodeGen/MachineDominators.h" 00026 #include "llvm/CodeGen/MachineFunctionPass.h" 00027 #include "llvm/CodeGen/MachineInstr.h" 00028 #include "llvm/CodeGen/MachineLoopInfo.h" 00029 #include "llvm/CodeGen/MachineRegisterInfo.h" 00030 #include "llvm/CodeGen/RegisterCoalescer.h" 00031 #include "llvm/Target/TargetInstrInfo.h" 00032 #include "llvm/Target/TargetMachine.h" 00033 #include "llvm/ADT/DepthFirstIterator.h" 00034 #include "llvm/ADT/Statistic.h" 00035 #include "llvm/Support/Compiler.h" 00036 #include "llvm/Support/Debug.h" 00037 using namespace llvm; 00038 00039 namespace { 00040 struct VISIBILITY_HIDDEN StrongPHIElimination : public MachineFunctionPass { 00041 static char ID; // Pass identification, replacement for typeid 00042 StrongPHIElimination() : MachineFunctionPass(&ID) {} 00043 00044 // Waiting stores, for each MBB, the set of copies that need to 00045 // be inserted into that MBB 00046 DenseMap<MachineBasicBlock*, 00047 std::multimap<unsigned, unsigned> > Waiting; 00048 00049 // Stacks holds the renaming stack for each register 00050 std::map<unsigned, std::vector<unsigned> > Stacks; 00051 00052 // Registers in UsedByAnother are PHI nodes that are themselves 00053 // used as operands to another another PHI node 00054 std::set<unsigned> UsedByAnother; 00055 00056 // RenameSets are the is a map from a PHI-defined register 00057 // to the input registers to be coalesced along with the 00058 // predecessor block for those input registers. 00059 std::map<unsigned, std::map<unsigned, MachineBasicBlock*> > RenameSets; 00060 00061 // PhiValueNumber holds the ID numbers of the VNs for each phi that we're 00062 // eliminating, indexed by the register defined by that phi. 00063 std::map<unsigned, unsigned> PhiValueNumber; 00064 00065 // Store the DFS-in number of each block 00066 DenseMap<MachineBasicBlock*, unsigned> preorder; 00067 00068 // Store the DFS-out number of each block 00069 DenseMap<MachineBasicBlock*, unsigned> maxpreorder; 00070 00071 bool runOnMachineFunction(MachineFunction &Fn); 00072 00073 virtual void getAnalysisUsage(AnalysisUsage &AU) const { 00074 AU.setPreservesCFG(); 00075 AU.addRequired<MachineDominatorTree>(); 00076 AU.addRequired<LiveIntervals>(); 00077 00078 // TODO: Actually make this true. 00079 AU.addPreserved<LiveIntervals>(); 00080 AU.addPreserved<RegisterCoalescer>(); 00081 MachineFunctionPass::getAnalysisUsage(AU); 00082 } 00083 00084 virtual void releaseMemory() { 00085 preorder.clear(); 00086 maxpreorder.clear(); 00087 00088 Waiting.clear(); 00089 Stacks.clear(); 00090 UsedByAnother.clear(); 00091 RenameSets.clear(); 00092 } 00093 00094 private: 00095 00096 /// DomForestNode - Represents a node in the "dominator forest". This is 00097 /// a forest in which the nodes represent registers and the edges 00098 /// represent a dominance relation in the block defining those registers. 00099 struct DomForestNode { 00100 private: 00101 // Store references to our children 00102 std::vector<DomForestNode*> children; 00103 // The register we represent 00104 unsigned reg; 00105 00106 // Add another node as our child 00107 void addChild(DomForestNode* DFN) { children.push_back(DFN); } 00108 00109 public: 00110 typedef std::vector<DomForestNode*>::iterator iterator; 00111 00112 // Create a DomForestNode by providing the register it represents, and 00113 // the node to be its parent. The virtual root node has register 0 00114 // and a null parent. 00115 DomForestNode(unsigned r, DomForestNode* parent) : reg(r) { 00116 if (parent) 00117 parent->addChild(this); 00118 } 00119 00120 ~DomForestNode() { 00121 for (iterator I = begin(), E = end(); I != E; ++I) 00122 delete *I; 00123 } 00124 00125 /// getReg - Return the regiser that this node represents 00126 inline unsigned getReg() { return reg; } 00127 00128 // Provide iterator access to our children 00129 inline DomForestNode::iterator begin() { return children.begin(); } 00130 inline DomForestNode::iterator end() { return children.end(); } 00131 }; 00132 00133 void computeDFS(MachineFunction& MF); 00134 void processBlock(MachineBasicBlock* MBB); 00135 00136 std::vector<DomForestNode*> computeDomForest( 00137 std::map<unsigned, MachineBasicBlock*>& instrs, 00138 MachineRegisterInfo& MRI); 00139 void processPHIUnion(MachineInstr* Inst, 00140 std::map<unsigned, MachineBasicBlock*>& PHIUnion, 00141 std::vector<StrongPHIElimination::DomForestNode*>& DF, 00142 std::vector<std::pair<unsigned, unsigned> >& locals); 00143 void ScheduleCopies(MachineBasicBlock* MBB, std::set<unsigned>& pushed); 00144 void InsertCopies(MachineDomTreeNode* MBB, 00145 SmallPtrSet<MachineBasicBlock*, 16>& v); 00146 bool mergeLiveIntervals(unsigned primary, unsigned secondary); 00147 }; 00148 } 00149 00150 char StrongPHIElimination::ID = 0; 00151 static RegisterPass<StrongPHIElimination> 00152 X("strong-phi-node-elimination", 00153 "Eliminate PHI nodes for register allocation, intelligently"); 00154 00155 const PassInfo *const llvm::StrongPHIEliminationID = &X; 00156 00157 /// computeDFS - Computes the DFS-in and DFS-out numbers of the dominator tree 00158 /// of the given MachineFunction. These numbers are then used in other parts 00159 /// of the PHI elimination process. 00160 void StrongPHIElimination::computeDFS(MachineFunction& MF) { 00161 SmallPtrSet<MachineDomTreeNode*, 8> frontier; 00162 SmallPtrSet<MachineDomTreeNode*, 8> visited; 00163 00164 unsigned time = 0; 00165 00166 MachineDominatorTree& DT = getAnalysis<MachineDominatorTree>(); 00167 00168 MachineDomTreeNode* node = DT.getRootNode(); 00169 00170 std::vector<MachineDomTreeNode*> worklist; 00171 worklist.push_back(node); 00172 00173 while (!worklist.empty()) { 00174 MachineDomTreeNode* currNode = worklist.back(); 00175 00176 if (!frontier.count(currNode)) { 00177 frontier.insert(currNode); 00178 ++time; 00179 preorder.insert(std::make_pair(currNode->getBlock(), time)); 00180 } 00181 00182 bool inserted = false; 00183 for (MachineDomTreeNode::iterator I = currNode->begin(), E = currNode->end(); 00184 I != E; ++I) 00185 if (!frontier.count(*I) && !visited.count(*I)) { 00186 worklist.push_back(*I); 00187 inserted = true; 00188 break; 00189 } 00190 00191 if (!inserted) { 00192 frontier.erase(currNode); 00193 visited.insert(currNode); 00194 maxpreorder.insert(std::make_pair(currNode->getBlock(), time)); 00195 00196 worklist.pop_back(); 00197 } 00198 } 00199 } 00200 00201 namespace { 00202 00203 /// PreorderSorter - a helper class that is used to sort registers 00204 /// according to the preorder number of their defining blocks 00205 class PreorderSorter { 00206 private: 00207 DenseMap<MachineBasicBlock*, unsigned>& preorder; 00208 MachineRegisterInfo& MRI; 00209 00210 public: 00211 PreorderSorter(DenseMap<MachineBasicBlock*, unsigned>& p, 00212 MachineRegisterInfo& M) : preorder(p), MRI(M) { } 00213 00214 bool operator()(unsigned A, unsigned B) { 00215 if (A == B) 00216 return false; 00217 00218 MachineBasicBlock* ABlock = MRI.getVRegDef(A)->getParent(); 00219 MachineBasicBlock* BBlock = MRI.getVRegDef(B)->getParent(); 00220 00221 if (preorder[ABlock] < preorder[BBlock]) 00222 return true; 00223 else if (preorder[ABlock] > preorder[BBlock]) 00224 return false; 00225 00226 return false; 00227 } 00228 }; 00229 00230 } 00231 00232 /// computeDomForest - compute the subforest of the DomTree corresponding 00233 /// to the defining blocks of the registers in question 00234 std::vector<StrongPHIElimination::DomForestNode*> 00235 StrongPHIElimination::computeDomForest( 00236 std::map<unsigned, MachineBasicBlock*>& regs, 00237 MachineRegisterInfo& MRI) { 00238 // Begin by creating a virtual root node, since the actual results 00239 // may well be a forest. Assume this node has maximum DFS-out number. 00240 DomForestNode* VirtualRoot = new DomForestNode(0, 0); 00241 maxpreorder.insert(std::make_pair((MachineBasicBlock*)0, ~0UL)); 00242 00243 // Populate a worklist with the registers 00244 std::vector<unsigned> worklist; 00245 worklist.reserve(regs.size()); 00246 for (std::map<unsigned, MachineBasicBlock*>::iterator I = regs.begin(), 00247 E = regs.end(); I != E; ++I) 00248 worklist.push_back(I->first); 00249 00250 // Sort the registers by the DFS-in number of their defining block 00251 PreorderSorter PS(preorder, MRI); 00252 std::sort(worklist.begin(), worklist.end(), PS); 00253 00254 // Create a "current parent" stack, and put the virtual root on top of it 00255 DomForestNode* CurrentParent = VirtualRoot; 00256 std::vector<DomForestNode*> stack; 00257 stack.push_back(VirtualRoot); 00258 00259 // Iterate over all the registers in the previously computed order 00260 for (std::vector<unsigned>::iterator I = worklist.begin(), E = worklist.end(); 00261 I != E; ++I) { 00262 unsigned pre = preorder[MRI.getVRegDef(*I)->getParent()]; 00263 MachineBasicBlock* parentBlock = CurrentParent->getReg() ? 00264 MRI.getVRegDef(CurrentParent->getReg())->getParent() : 00265 0; 00266 00267 // If the DFS-in number of the register is greater than the DFS-out number 00268 // of the current parent, repeatedly pop the parent stack until it isn't. 00269 while (pre > maxpreorder[parentBlock]) { 00270 stack.pop_back(); 00271 CurrentParent = stack.back(); 00272 00273 parentBlock = CurrentParent->getReg() ? 00274 MRI.getVRegDef(CurrentParent->getReg())->getParent() : 00275 0; 00276 } 00277 00278 // Now that we've found the appropriate parent, create a DomForestNode for 00279 // this register and attach it to the forest 00280 DomForestNode* child = new DomForestNode(*I, CurrentParent); 00281 00282 // Push this new node on the "current parent" stack 00283 stack.push_back(child); 00284 CurrentParent = child; 00285 } 00286 00287 // Return a vector containing the children of the virtual root node 00288 std::vector<DomForestNode*> ret; 00289 ret.insert(ret.end(), VirtualRoot->begin(), VirtualRoot->end()); 00290 return ret; 00291 } 00292 00293 /// isLiveIn - helper method that determines, from a regno, if a register 00294 /// is live into a block 00295 static bool isLiveIn(unsigned r, MachineBasicBlock* MBB, 00296 LiveIntervals& LI) { 00297 LiveInterval& I = LI.getOrCreateInterval(r); 00298 unsigned idx = LI.getMBBStartIdx(MBB); 00299 return I.liveAt(idx); 00300 } 00301 00302 /// isLiveOut - help method that determines, from a regno, if a register is 00303 /// live out of a block. 00304 static bool isLiveOut(unsigned r, MachineBasicBlock* MBB, 00305 LiveIntervals& LI) { 00306 for (MachineBasicBlock::succ_iterator PI = MBB->succ_begin(), 00307 E = MBB->succ_end(); PI != E; ++PI) 00308 if (isLiveIn(r, *PI, LI)) 00309 return true; 00310 00311 return false; 00312 } 00313 00314 /// interferes - checks for local interferences by scanning a block. The only 00315 /// trick parameter is 'mode' which tells it the relationship of the two 00316 /// registers. 0 - defined in the same block, 1 - first properly dominates 00317 /// second, 2 - second properly dominates first 00318 static bool interferes(unsigned a, unsigned b, MachineBasicBlock* scan, 00319 LiveIntervals& LV, unsigned mode) { 00320 MachineInstr* def = 0; 00321 MachineInstr* kill = 0; 00322 00323 // The code is still in SSA form at this point, so there is only one 00324 // definition per VReg. Thus we can safely use MRI->getVRegDef(). 00325 const MachineRegisterInfo* MRI = &scan->getParent()->getRegInfo(); 00326 00327 bool interference = false; 00328 00329 // Wallk the block, checking for interferences 00330 for (MachineBasicBlock::iterator MBI = scan->begin(), MBE = scan->end(); 00331 MBI != MBE; ++MBI) { 00332 MachineInstr* curr = MBI; 00333 00334 // Same defining block... 00335 if (mode == 0) { 00336 if (curr == MRI->getVRegDef(a)) { 00337 // If we find our first definition, save it 00338 if (!def) { 00339 def = curr; 00340 // If there's already an unkilled definition, then 00341 // this is an interference 00342 } else if (!kill) { 00343 interference = true; 00344 break; 00345 // If there's a definition followed by a KillInst, then 00346 // they can't interfere 00347 } else { 00348 interference = false; 00349 break; 00350 } 00351 // Symmetric with the above 00352 } else if (curr == MRI->getVRegDef(b)) { 00353 if (!def) { 00354 def = curr; 00355 } else if (!kill) { 00356 interference = true; 00357 break; 00358 } else { 00359 interference = false; 00360 break; 00361 } 00362 // Store KillInsts if they match up with the definition 00363 } else if (curr->killsRegister(a)) { 00364 if (def == MRI->getVRegDef(a)) { 00365 kill = curr; 00366 } else if (curr->killsRegister(b)) { 00367 if (def == MRI->getVRegDef(b)) { 00368 kill = curr; 00369 } 00370 } 00371 } 00372 // First properly dominates second... 00373 } else if (mode == 1) { 00374 if (curr == MRI->getVRegDef(b)) { 00375 // Definition of second without kill of first is an interference 00376 if (!kill) { 00377 interference = true; 00378 break; 00379 // Definition after a kill is a non-interference 00380 } else { 00381 interference = false; 00382 break; 00383 } 00384 // Save KillInsts of First 00385 } else if (curr->killsRegister(a)) { 00386 kill = curr; 00387 } 00388 // Symmetric with the above 00389 } else if (mode == 2) { 00390 if (curr == MRI->getVRegDef(a)) { 00391 if (!kill) { 00392 interference = true; 00393 break; 00394 } else { 00395 interference = false; 00396 break; 00397 } 00398 } else if (curr->killsRegister(b)) { 00399 kill = curr; 00400 } 00401 } 00402 } 00403 00404 return interference; 00405 } 00406 00407 /// processBlock - Determine how to break up PHIs in the current block. Each 00408 /// PHI is broken up by some combination of renaming its operands and inserting 00409 /// copies. This method is responsible for determining which operands receive 00410 /// which treatment. 00411 void StrongPHIElimination::processBlock(MachineBasicBlock* MBB) { 00412 LiveIntervals& LI = getAnalysis<LiveIntervals>(); 00413 MachineRegisterInfo& MRI = MBB->getParent()->getRegInfo(); 00414 00415 // Holds names that have been added to a set in any PHI within this block 00416 // before the current one. 00417 std::set<unsigned> ProcessedNames; 00418 00419 // Iterate over all the PHI nodes in this block 00420 MachineBasicBlock::iterator P = MBB->begin(); 00421 while (P != MBB->end() && P->getOpcode() == TargetInstrInfo::PHI) { 00422 unsigned DestReg = P->getOperand(0).getReg(); 00423 00424 // Don't both doing PHI elimination for dead PHI's. 00425 if (P->registerDefIsDead(DestReg)) { 00426 ++P; 00427 continue; 00428 } 00429 00430 LiveInterval& PI = LI.getOrCreateInterval(DestReg); 00431 unsigned pIdx = LI.getDefIndex(LI.getInstructionIndex(P)); 00432 VNInfo* PVN = PI.getLiveRangeContaining(pIdx)->valno; 00433 PhiValueNumber.insert(std::make_pair(DestReg, PVN->id)); 00434 00435 // PHIUnion is the set of incoming registers to the PHI node that 00436 // are going to be renames rather than having copies inserted. This set 00437 // is refinded over the course of this function. UnionedBlocks is the set 00438 // of corresponding MBBs. 00439 std::map<unsigned, MachineBasicBlock*> PHIUnion; 00440 SmallPtrSet<MachineBasicBlock*, 8> UnionedBlocks; 00441 00442 // Iterate over the operands of the PHI node 00443 for (int i = P->getNumOperands() - 1; i >= 2; i-=2) { 00444 unsigned SrcReg = P->getOperand(i-1).getReg(); 00445 00446 // Don't need to try to coalesce a register with itself. 00447 if (SrcReg == DestReg) { 00448 ProcessedNames.insert(SrcReg); 00449 continue; 00450 } 00451 00452 // We don't need to insert copies for implicit_defs. 00453 MachineInstr* DefMI = MRI.getVRegDef(SrcReg); 00454 if (DefMI->getOpcode() == TargetInstrInfo::IMPLICIT_DEF) 00455 ProcessedNames.insert(SrcReg); 00456 00457 // Check for trivial interferences via liveness information, allowing us 00458 // to avoid extra work later. Any registers that interfere cannot both 00459 // be in the renaming set, so choose one and add copies for it instead. 00460 // The conditions are: 00461 // 1) if the operand is live into the PHI node's block OR 00462 // 2) if the PHI node is live out of the operand's defining block OR 00463 // 3) if the operand is itself a PHI node and the original PHI is 00464 // live into the operand's defining block OR 00465 // 4) if the operand is already being renamed for another PHI node 00466 // in this block OR 00467 // 5) if any two operands are defined in the same block, insert copies 00468 // for one of them 00469 if (isLiveIn(SrcReg, P->getParent(), LI) || 00470 isLiveOut(P->getOperand(0).getReg(), 00471 MRI.getVRegDef(SrcReg)->getParent(), LI) || 00472 ( MRI.getVRegDef(SrcReg)->getOpcode() == TargetInstrInfo::PHI && 00473 isLiveIn(P->getOperand(0).getReg(), 00474 MRI.getVRegDef(SrcReg)->getParent(), LI) ) || 00475 ProcessedNames.count(SrcReg) || 00476 UnionedBlocks.count(MRI.getVRegDef(SrcReg)->getParent())) { 00477 00478 // Add a copy for the selected register 00479 MachineBasicBlock* From = P->getOperand(i).getMBB(); 00480 Waiting[From].insert(std::make_pair(SrcReg, DestReg)); 00481 UsedByAnother.insert(SrcReg); 00482 } else { 00483 // Otherwise, add it to the renaming set 00484 PHIUnion.insert(std::make_pair(SrcReg,P->getOperand(i).getMBB())); 00485 UnionedBlocks.insert(MRI.getVRegDef(SrcReg)->getParent()); 00486 } 00487 } 00488 00489 // Compute the dominator forest for the renaming set. This is a forest 00490 // where the nodes are the registers and the edges represent dominance 00491 // relations between the defining blocks of the registers 00492 std::vector<StrongPHIElimination::DomForestNode*> DF = 00493 computeDomForest(PHIUnion, MRI); 00494 00495 // Walk DomForest to resolve interferences at an inter-block level. This 00496 // will remove registers from the renaming set (and insert copies for them) 00497 // if interferences are found. 00498 std::vector<std::pair<unsigned, unsigned> > localInterferences; 00499 processPHIUnion(P, PHIUnion, DF, localInterferences); 00500 00501 // If one of the inputs is defined in the same block as the current PHI 00502 // then we need to check for a local interference between that input and 00503 // the PHI. 00504 for (std::map<unsigned, MachineBasicBlock*>::iterator I = PHIUnion.begin(), 00505 E = PHIUnion.end(); I != E; ++I) 00506 if (MRI.getVRegDef(I->first)->getParent() == P->getParent()) 00507 localInterferences.push_back(std::make_pair(I->first, 00508 P->getOperand(0).getReg())); 00509 00510 // The dominator forest walk may have returned some register pairs whose 00511 // interference cannot be determined from dominator analysis. We now 00512 // examine these pairs for local interferences. 00513 for (std::vector<std::pair<unsigned, unsigned> >::iterator I = 00514 localInterferences.begin(), E = localInterferences.end(); I != E; ++I) { 00515 std::pair<unsigned, unsigned> p = *I; 00516 00517 MachineDominatorTree& MDT = getAnalysis<MachineDominatorTree>(); 00518 00519 // Determine the block we need to scan and the relationship between 00520 // the two registers 00521 MachineBasicBlock* scan = 0; 00522 unsigned mode = 0; 00523 if (MRI.getVRegDef(p.first)->getParent() == 00524 MRI.getVRegDef(p.second)->getParent()) { 00525 scan = MRI.getVRegDef(p.first)->getParent(); 00526 mode = 0; // Same block 00527 } else if (MDT.dominates(MRI.getVRegDef(p.first)->getParent(), 00528 MRI.getVRegDef(p.second)->getParent())) { 00529 scan = MRI.getVRegDef(p.second)->getParent(); 00530 mode = 1; // First dominates second 00531 } else { 00532 scan = MRI.getVRegDef(p.first)->getParent(); 00533 mode = 2; // Second dominates first 00534 } 00535 00536 // If there's an interference, we need to insert copies 00537 if (interferes(p.first, p.second, scan, LI, mode)) { 00538 // Insert copies for First 00539 for (int i = P->getNumOperands() - 1; i >= 2; i-=2) { 00540 if (P->getOperand(i-1).getReg() == p.first) { 00541 unsigned SrcReg = p.first; 00542 MachineBasicBlock* From = P->getOperand(i).getMBB(); 00543 00544 Waiting[From].insert(std::make_pair(SrcReg, 00545 P->getOperand(0).getReg())); 00546 UsedByAnother.insert(SrcReg); 00547 00548 PHIUnion.erase(SrcReg); 00549 } 00550 } 00551 } 00552 } 00553 00554 // Add the renaming set for this PHI node to our overall renaming information 00555 for (std::map<unsigned, MachineBasicBlock*>::iterator QI = PHIUnion.begin(), 00556 QE = PHIUnion.end(); QI != QE; ++QI) { 00557 DOUT << "Adding Renaming: " << QI->first << " -> " 00558 << P->getOperand(0).getReg() << "\n"; 00559 } 00560 00561 RenameSets.insert(std::make_pair(P->getOperand(0).getReg(), PHIUnion)); 00562 00563 // Remember which registers are already renamed, so that we don't try to 00564 // rename them for another PHI node in this block 00565 for (std::map<unsigned, MachineBasicBlock*>::iterator I = PHIUnion.begin(), 00566 E = PHIUnion.end(); I != E; ++I) 00567 ProcessedNames.insert(I->first); 00568 00569 ++P; 00570 } 00571 } 00572 00573 /// processPHIUnion - Take a set of candidate registers to be coalesced when 00574 /// decomposing the PHI instruction. Use the DominanceForest to remove the ones 00575 /// that are known to interfere, and flag others that need to be checked for 00576 /// local interferences. 00577 void StrongPHIElimination::processPHIUnion(MachineInstr* Inst, 00578 std::map<unsigned, MachineBasicBlock*>& PHIUnion, 00579 std::vector<StrongPHIElimination::DomForestNode*>& DF, 00580 std::vector<std::pair<unsigned, unsigned> >& locals) { 00581 00582 std::vector<DomForestNode*> worklist(DF.begin(), DF.end()); 00583 SmallPtrSet<DomForestNode*, 4> visited; 00584 00585 // Code is still in SSA form, so we can use MRI::getVRegDef() 00586 MachineRegisterInfo& MRI = Inst->getParent()->getParent()->getRegInfo(); 00587 00588 LiveIntervals& LI = getAnalysis<LiveIntervals>(); 00589 unsigned DestReg = Inst->getOperand(0).getReg(); 00590 00591 // DF walk on the DomForest 00592 while (!worklist.empty()) { 00593 DomForestNode* DFNode = worklist.back(); 00594 00595 visited.insert(DFNode); 00596 00597 bool inserted = false; 00598 for (DomForestNode::iterator CI = DFNode->begin(), CE = DFNode->end(); 00599 CI != CE; ++CI) { 00600 DomForestNode* child = *CI; 00601 00602 // If the current node is live-out of the defining block of one of its 00603 // children, insert a copy for it. NOTE: The paper actually calls for 00604 // a more elaborate heuristic for determining whether to insert copies 00605 // for the child or the parent. In the interest of simplicity, we're 00606 // just always choosing the parent. 00607 if (isLiveOut(DFNode->getReg(), 00608 MRI.getVRegDef(child->getReg())->getParent(), LI)) { 00609 // Insert copies for parent 00610 for (int i = Inst->getNumOperands() - 1; i >= 2; i-=2) { 00611 if (Inst->getOperand(i-1).getReg() == DFNode->getReg()) { 00612 unsigned SrcReg = DFNode->getReg(); 00613 MachineBasicBlock* From = Inst->getOperand(i).getMBB(); 00614 00615 Waiting[From].insert(std::make_pair(SrcReg, DestReg)); 00616 UsedByAnother.insert(SrcReg); 00617 00618 PHIUnion.erase(SrcReg); 00619 } 00620 } 00621 00622 // If a node is live-in to the defining block of one of its children, but 00623 // not live-out, then we need to scan that block for local interferences. 00624 } else if (isLiveIn(DFNode->getReg(), 00625 MRI.getVRegDef(child->getReg())->getParent(), LI) || 00626 MRI.getVRegDef(DFNode->getReg())->getParent() == 00627 MRI.getVRegDef(child->getReg())->getParent()) { 00628 // Add (p, c) to possible local interferences 00629 locals.push_back(std::make_pair(DFNode->getReg(), child->getReg())); 00630 } 00631 00632 if (!visited.count(child)) { 00633 worklist.push_back(child); 00634 inserted = true; 00635 } 00636 } 00637 00638 if (!inserted) worklist.pop_back(); 00639 } 00640 } 00641 00642 /// ScheduleCopies - Insert copies into predecessor blocks, scheduling 00643 /// them properly so as to avoid the 'lost copy' and the 'virtual swap' 00644 /// problems. 00645 /// 00646 /// Based on "Practical Improvements to the Construction and Destruction 00647 /// of Static Single Assignment Form" by Briggs, et al. 00648 void StrongPHIElimination::ScheduleCopies(MachineBasicBlock* MBB, 00649 std::set<unsigned>& pushed) { 00650 // FIXME: This function needs to update LiveIntervals 00651 std::multimap<unsigned, unsigned>& copy_set= Waiting[MBB]; 00652 00653 std::multimap<unsigned, unsigned> worklist; 00654 std::map<unsigned, unsigned> map; 00655 00656 // Setup worklist of initial copies 00657 for (std::multimap<unsigned, unsigned>::iterator I = copy_set.begin(), 00658 E = copy_set.end(); I != E; ) { 00659 map.insert(std::make_pair(I->first, I->first)); 00660 map.insert(std::make_pair(I->second, I->second)); 00661 00662 if (!UsedByAnother.count(I->second)) { 00663 worklist.insert(*I); 00664 00665 // Avoid iterator invalidation 00666 std::multimap<unsigned, unsigned>::iterator OI = I; 00667 ++I; 00668 copy_set.erase(OI); 00669 } else { 00670 ++I; 00671 } 00672 } 00673 00674 LiveIntervals& LI = getAnalysis<LiveIntervals>(); 00675 MachineFunction* MF = MBB->getParent(); 00676 MachineRegisterInfo& MRI = MF->getRegInfo(); 00677 const TargetInstrInfo *TII = MF->getTarget().getInstrInfo(); 00678 00679 SmallVector<std::pair<unsigned, MachineInstr*>, 4> InsertedPHIDests; 00680 00681 // Iterate over the worklist, inserting copies 00682 while (!worklist.empty() || !copy_set.empty()) { 00683 while (!worklist.empty()) { 00684 std::multimap<unsigned, unsigned>::iterator WI = worklist.begin(); 00685 std::pair<unsigned, unsigned> curr = *WI; 00686 worklist.erase(WI); 00687 00688 const TargetRegisterClass *RC = MF->getRegInfo().getRegClass(curr.first); 00689 00690 if (isLiveOut(curr.second, MBB, LI)) { 00691 // Create a temporary 00692 unsigned t = MF->getRegInfo().createVirtualRegister(RC); 00693 00694 // Insert copy from curr.second to a temporary at 00695 // the Phi defining curr.second 00696 MachineBasicBlock::iterator PI = MRI.getVRegDef(curr.second); 00697 TII->copyRegToReg(*PI->getParent(), PI, t, 00698 curr.second, RC, RC); 00699 00700 DOUT << "Inserted copy from " << curr.second << " to " << t << "\n"; 00701 00702 // Push temporary on Stacks 00703 Stacks[curr.second].push_back(t); 00704 00705 // Insert curr.second in pushed 00706 pushed.insert(curr.second); 00707 00708 // Create a live interval for this temporary 00709 InsertedPHIDests.push_back(std::make_pair(t, --PI)); 00710 } 00711 00712 // Insert copy from map[curr.first] to curr.second 00713 TII->copyRegToReg(*MBB, MBB->getFirstTerminator(), curr.second, 00714 map[curr.first], RC, RC); 00715 map[curr.first] = curr.second; 00716 DOUT << "Inserted copy from " << curr.first << " to " 00717 << curr.second << "\n"; 00718 00719 // Push this copy onto InsertedPHICopies so we can 00720 // update LiveIntervals with it. 00721 MachineBasicBlock::iterator MI = MBB->getFirstTerminator(); 00722 InsertedPHIDests.push_back(std::make_pair(curr.second, --MI)); 00723 00724 // If curr.first is a destination in copy_set... 00725 for (std::multimap<unsigned, unsigned>::iterator I = copy_set.begin(), 00726 E = copy_set.end(); I != E; ) 00727 if (curr.first == I->second) { 00728 std::pair<unsigned, unsigned> temp = *I; 00729 worklist.insert(temp); 00730 00731 // Avoid iterator invalidation 00732 std::multimap<unsigned, unsigned>::iterator OI = I; 00733 ++I; 00734 copy_set.erase(OI); 00735 00736 break; 00737 } else { 00738 ++I; 00739 } 00740 } 00741 00742 if (!copy_set.empty()) { 00743 std::multimap<unsigned, unsigned>::iterator CI = copy_set.begin(); 00744 std::pair<unsigned, unsigned> curr = *CI; 00745 worklist.insert(curr); 00746 copy_set.erase(CI); 00747 00748 LiveInterval& I = LI.getInterval(curr.second); 00749 MachineBasicBlock::iterator term = MBB->getFirstTerminator(); 00750 unsigned endIdx = 0; 00751 if (term != MBB->end()) 00752 endIdx = LI.getInstructionIndex(term); 00753 else 00754 endIdx = LI.getMBBEndIdx(MBB); 00755 00756 if (I.liveAt(endIdx)) { 00757 const TargetRegisterClass *RC = 00758 MF->getRegInfo().getRegClass(curr.first); 00759 00760 // Insert a copy from dest to a new temporary t at the end of b 00761 unsigned t = MF->getRegInfo().createVirtualRegister(RC); 00762 TII->copyRegToReg(*MBB, MBB->getFirstTerminator(), t, 00763 curr.second, RC, RC); 00764 map[curr.second] = t; 00765 00766 MachineBasicBlock::iterator TI = MBB->getFirstTerminator(); 00767 InsertedPHIDests.push_back(std::make_pair(t, --TI)); 00768 } 00769 } 00770 } 00771 00772 // Renumber the instructions so that we can perform the index computations 00773 // needed to create new live intervals. 00774 LI.computeNumbering(); 00775 00776 // For copies that we inserted at the ends of predecessors, we construct 00777 // live intervals. This is pretty easy, since we know that the destination 00778 // register cannot have be in live at that point previously. We just have 00779 // to make sure that, for registers that serve as inputs to more than one 00780 // PHI, we don't create multiple overlapping live intervals. 00781 std::set<unsigned> RegHandled; 00782 for (SmallVector<std::pair<unsigned, MachineInstr*>, 4>::iterator I = 00783 InsertedPHIDests.begin(), E = InsertedPHIDests.end(); I != E; ++I) { 00784 if (RegHandled.insert(I->first).second) { 00785 LiveInterval& Int = LI.getOrCreateInterval(I->first); 00786 unsigned instrIdx = LI.getInstructionIndex(I->second); 00787 if (Int.liveAt(LiveIntervals::getDefIndex(instrIdx))) 00788 Int.removeRange(LiveIntervals::getDefIndex(instrIdx), 00789 LI.getMBBEndIdx(I->second->getParent())+1, 00790 true); 00791 00792 LiveRange R = LI.addLiveRangeToEndOfBlock(I->first, I->second); 00793 R.valno->setCopy(I->second); 00794 R.valno->def = 00795 LiveIntervals::getDefIndex(LI.getInstructionIndex(I->second)); 00796 } 00797 } 00798 } 00799 00800 /// InsertCopies - insert copies into MBB and all of its successors 00801 void StrongPHIElimination::InsertCopies(MachineDomTreeNode* MDTN, 00802 SmallPtrSet<MachineBasicBlock*, 16>& visited) { 00803 MachineBasicBlock* MBB = MDTN->getBlock(); 00804 visited.insert(MBB); 00805 00806 std::set<unsigned> pushed; 00807 00808 LiveIntervals& LI = getAnalysis<LiveIntervals>(); 00809 // Rewrite register uses from Stacks 00810 for (MachineBasicBlock::iterator I = MBB->begin(), E = MBB->end(); 00811 I != E; ++I) { 00812 if (I->getOpcode() == TargetInstrInfo::PHI) 00813 continue; 00814 00815 for (unsigned i = 0; i < I->getNumOperands(); ++i) 00816 if (I->getOperand(i).isReg() && 00817 Stacks[I->getOperand(i).getReg()].size()) { 00818 // Remove the live range for the old vreg. 00819 LiveInterval& OldInt = LI.getInterval(I->getOperand(i).getReg()); 00820 LiveInterval::iterator OldLR = OldInt.FindLiveRangeContaining( 00821 LiveIntervals::getUseIndex(LI.getInstructionIndex(I))); 00822 if (OldLR != OldInt.end()) 00823 OldInt.removeRange(*OldLR, true); 00824 00825 // Change the register 00826 I->getOperand(i).setReg(Stacks[I->getOperand(i).getReg()].back()); 00827 00828 // Add a live range for the new vreg 00829 LiveInterval& Int = LI.getInterval(I->getOperand(i).getReg()); 00830 VNInfo* FirstVN = *Int.vni_begin(); 00831 FirstVN->setHasPHIKill(false); 00832 if (I->getOperand(i).isKill()) 00833 Int.addKill(FirstVN, 00834 LiveIntervals::getUseIndex(LI.getInstructionIndex(I)), false); 00835 00836 LiveRange LR (LI.getMBBStartIdx(I->getParent()), 00837 LiveIntervals::getUseIndex(LI.getInstructionIndex(I))+1, 00838 FirstVN); 00839 00840 Int.addRange(LR); 00841 } 00842 } 00843 00844 // Schedule the copies for this block 00845 ScheduleCopies(MBB, pushed); 00846 00847 // Recur down the dominator tree. 00848 for (MachineDomTreeNode::iterator I = MDTN->begin(), 00849 E = MDTN->end(); I != E; ++I) 00850 if (!visited.count((*I)->getBlock())) 00851 InsertCopies(*I, visited); 00852 00853 // As we exit this block, pop the names we pushed while processing it 00854 for (std::set<unsigned>::iterator I = pushed.begin(), 00855 E = pushed.end(); I != E; ++I) 00856 Stacks[*I].pop_back(); 00857 } 00858 00859 bool StrongPHIElimination::mergeLiveIntervals(unsigned primary, 00860 unsigned secondary) { 00861 00862 LiveIntervals& LI = getAnalysis<LiveIntervals>(); 00863 LiveInterval& LHS = LI.getOrCreateInterval(primary); 00864 LiveInterval& RHS = LI.getOrCreateInterval(secondary); 00865 00866 LI.computeNumbering(); 00867 00868 DenseMap<VNInfo*, VNInfo*> VNMap; 00869 for (LiveInterval::iterator I = RHS.begin(), E = RHS.end(); I != E; ++I) { 00870 LiveRange R = *I; 00871 00872 unsigned Start = R.start; 00873 unsigned End = R.end; 00874 if (LHS.getLiveRangeContaining(Start)) 00875 return false; 00876 00877 if (LHS.getLiveRangeContaining(End)) 00878 return false; 00879 00880 LiveInterval::iterator RI = std::upper_bound(LHS.begin(), LHS.end(), R); 00881 if (RI != LHS.end() && RI->start < End) 00882 return false; 00883 } 00884 00885 for (LiveInterval::iterator I = RHS.begin(), E = RHS.end(); I != E; ++I) { 00886 LiveRange R = *I; 00887 VNInfo* OldVN = R.valno; 00888 VNInfo*& NewVN = VNMap[OldVN]; 00889 if (!NewVN) { 00890 NewVN = LHS.createValueCopy(OldVN, LI.getVNInfoAllocator()); 00891 } 00892 00893 LiveRange LR (R.start, R.end, NewVN); 00894 LHS.addRange(LR); 00895 } 00896 00897 LI.removeInterval(RHS.reg); 00898 00899 return true; 00900 } 00901 00902 bool StrongPHIElimination::runOnMachineFunction(MachineFunction &Fn) { 00903 LiveIntervals& LI = getAnalysis<LiveIntervals>(); 00904 00905 // Compute DFS numbers of each block 00906 computeDFS(Fn); 00907 00908 // Determine which phi node operands need copies 00909 for (MachineFunction::iterator I = Fn.begin(), E = Fn.end(); I != E; ++I) 00910 if (!I->empty() && 00911 I->begin()->getOpcode() == TargetInstrInfo::PHI) 00912 processBlock(I); 00913 00914 // Break interferences where two different phis want to coalesce 00915 // in the same register. 00916 std::set<unsigned> seen; 00917 typedef std::map<unsigned, std::map<unsigned, MachineBasicBlock*> > 00918 RenameSetType; 00919 for (RenameSetType::iterator I = RenameSets.begin(), E = RenameSets.end(); 00920 I != E; ++I) { 00921 for (std::map<unsigned, MachineBasicBlock*>::iterator 00922 OI = I->second.begin(), OE = I->second.end(); OI != OE; ) { 00923 if (!seen.count(OI->first)) { 00924 seen.insert(OI->first); 00925 ++OI; 00926 } else { 00927 Waiting[OI->second].insert(std::make_pair(OI->first, I->first)); 00928 unsigned reg = OI->first; 00929 ++OI; 00930 I->second.erase(reg); 00931 DOUT << "Removing Renaming: " << reg << " -> " << I->first << "\n"; 00932 } 00933 } 00934 } 00935 00936 // Insert copies 00937 // FIXME: This process should probably preserve LiveIntervals 00938 SmallPtrSet<MachineBasicBlock*, 16> visited; 00939 MachineDominatorTree& MDT = getAnalysis<MachineDominatorTree>(); 00940 InsertCopies(MDT.getRootNode(), visited); 00941 00942 // Perform renaming 00943 for (RenameSetType::iterator I = RenameSets.begin(), E = RenameSets.end(); 00944 I != E; ++I) 00945 while (I->second.size()) { 00946 std::map<unsigned, MachineBasicBlock*>::iterator SI = I->second.begin(); 00947 00948 DOUT << "Renaming: " << SI->first << " -> " << I->first << "\n"; 00949 00950 if (SI->first != I->first) { 00951 if (mergeLiveIntervals(I->first, SI->first)) { 00952 Fn.getRegInfo().replaceRegWith(SI->first, I->first); 00953 00954 if (RenameSets.count(SI->first)) { 00955 I->second.insert(RenameSets[SI->first].begin(), 00956 RenameSets[SI->first].end()); 00957 RenameSets.erase(SI->first); 00958 } 00959 } else { 00960 // Insert a last-minute copy if a conflict was detected. 00961 const TargetInstrInfo *TII = Fn.getTarget().getInstrInfo(); 00962 const TargetRegisterClass *RC = Fn.getRegInfo().getRegClass(I->first); 00963 TII->copyRegToReg(*SI->second, SI->second->getFirstTerminator(), 00964 I->first, SI->first, RC, RC); 00965 00966 LI.computeNumbering(); 00967 00968 LiveInterval& Int = LI.getOrCreateInterval(I->first); 00969 unsigned instrIdx = 00970 LI.getInstructionIndex(--SI->second->getFirstTerminator()); 00971 if (Int.liveAt(LiveIntervals::getDefIndex(instrIdx))) 00972 Int.removeRange(LiveIntervals::getDefIndex(instrIdx), 00973 LI.getMBBEndIdx(SI->second)+1, true); 00974 00975 LiveRange R = LI.addLiveRangeToEndOfBlock(I->first, 00976 --SI->second->getFirstTerminator()); 00977 R.valno->setCopy(--SI->second->getFirstTerminator()); 00978 R.valno->def = LiveIntervals::getDefIndex(instrIdx); 00979 00980 DOUT << "Renaming failed: " << SI->first << " -> " 00981 << I->first << "\n"; 00982 } 00983 } 00984 00985 LiveInterval& Int = LI.getOrCreateInterval(I->first); 00986 const LiveRange* LR = 00987 Int.getLiveRangeContaining(LI.getMBBEndIdx(SI->second)); 00988 LR->valno->setHasPHIKill(true); 00989 00990 I->second.erase(SI->first); 00991 } 00992 00993 // Remove PHIs 00994 std::vector<MachineInstr*> phis; 00995 for (MachineFunction::iterator I = Fn.begin(), E = Fn.end(); I != E; ++I) { 00996 for (MachineBasicBlock::iterator BI = I->begin(), BE = I->end(); 00997 BI != BE; ++BI) 00998 if (BI->getOpcode() == TargetInstrInfo::PHI) 00999 phis.push_back(BI); 01000 } 01001 01002 for (std::vector<MachineInstr*>::iterator I = phis.begin(), E = phis.end(); 01003 I != E; ) { 01004 MachineInstr* PInstr = *(I++); 01005 01006 // If this is a dead PHI node, then remove it from LiveIntervals. 01007 unsigned DestReg = PInstr->getOperand(0).getReg(); 01008 LiveInterval& PI = LI.getInterval(DestReg); 01009 if (PInstr->registerDefIsDead(DestReg)) { 01010 if (PI.containsOneValue()) { 01011 LI.removeInterval(DestReg); 01012 } else { 01013 unsigned idx = LI.getDefIndex(LI.getInstructionIndex(PInstr)); 01014 PI.removeRange(*PI.getLiveRangeContaining(idx), true); 01015 } 01016 } else { 01017 // Trim live intervals of input registers. They are no longer live into 01018 // this block if they died after the PHI. If they lived after it, don't 01019 // trim them because they might have other legitimate uses. 01020 for (unsigned i = 1; i < PInstr->getNumOperands(); i += 2) { 01021 unsigned reg = PInstr->getOperand(i).getReg(); 01022 01023 MachineBasicBlock* MBB = PInstr->getOperand(i+1).getMBB(); 01024 LiveInterval& InputI = LI.getInterval(reg); 01025 if (MBB != PInstr->getParent() && 01026 InputI.liveAt(LI.getMBBStartIdx(PInstr->getParent())) && 01027 InputI.expiredAt(LI.getInstructionIndex(PInstr) + 01028 LiveInterval::InstrSlots::NUM)) 01029 InputI.removeRange(LI.getMBBStartIdx(PInstr->getParent()), 01030 LI.getInstructionIndex(PInstr), 01031 true); 01032 } 01033 01034 // If the PHI is not dead, then the valno defined by the PHI 01035 // now has an unknown def. 01036 unsigned idx = LI.getDefIndex(LI.getInstructionIndex(PInstr)); 01037 const LiveRange* PLR = PI.getLiveRangeContaining(idx); 01038 PLR->valno->setIsPHIDef(true); 01039 LiveRange R (LI.getMBBStartIdx(PInstr->getParent()), 01040 PLR->start, PLR->valno); 01041 PI.addRange(R); 01042 } 01043 01044 LI.RemoveMachineInstrFromMaps(PInstr); 01045 PInstr->eraseFromParent(); 01046 } 01047 01048 LI.computeNumbering(); 01049 01050 return true; 01051 }