LLVM API Documentation
00001 //===-- PhiElimination.cpp - Eliminate PHI nodes by inserting copies ------===// 00002 // 00003 // The LLVM Compiler Infrastructure 00004 // 00005 // This file was developed by the LLVM research group and is distributed under 00006 // the University of Illinois Open Source License. See LICENSE.TXT for details. 00007 // 00008 //===----------------------------------------------------------------------===// 00009 // 00010 // This pass eliminates machine instruction PHI nodes by inserting copy 00011 // instructions. This destroys SSA information, but is the desired input for 00012 // some register allocators. 00013 // 00014 //===----------------------------------------------------------------------===// 00015 00016 #include "llvm/CodeGen/LiveVariables.h" 00017 #include "llvm/CodeGen/Passes.h" 00018 #include "llvm/CodeGen/MachineFunctionPass.h" 00019 #include "llvm/CodeGen/MachineInstr.h" 00020 #include "llvm/CodeGen/SSARegMap.h" 00021 #include "llvm/Target/TargetInstrInfo.h" 00022 #include "llvm/Target/TargetMachine.h" 00023 #include "llvm/ADT/DenseMap.h" 00024 #include "llvm/ADT/STLExtras.h" 00025 #include "llvm/ADT/Statistic.h" 00026 #include <set> 00027 #include <algorithm> 00028 using namespace llvm; 00029 00030 namespace { 00031 Statistic<> NumAtomic("phielim", "Number of atomic phis lowered"); 00032 Statistic<> NumSimple("phielim", "Number of simple phis lowered"); 00033 00034 struct PNE : public MachineFunctionPass { 00035 bool runOnMachineFunction(MachineFunction &Fn) { 00036 bool Changed = false; 00037 00038 // Eliminate PHI instructions by inserting copies into predecessor blocks. 00039 for (MachineFunction::iterator I = Fn.begin(), E = Fn.end(); I != E; ++I) 00040 Changed |= EliminatePHINodes(Fn, *I); 00041 00042 return Changed; 00043 } 00044 00045 virtual void getAnalysisUsage(AnalysisUsage &AU) const { 00046 AU.addPreserved<LiveVariables>(); 00047 MachineFunctionPass::getAnalysisUsage(AU); 00048 } 00049 00050 private: 00051 /// EliminatePHINodes - Eliminate phi nodes by inserting copy instructions 00052 /// in predecessor basic blocks. 00053 /// 00054 bool EliminatePHINodes(MachineFunction &MF, MachineBasicBlock &MBB); 00055 void LowerAtomicPHINode(MachineBasicBlock &MBB, 00056 MachineBasicBlock::iterator AfterPHIsIt, 00057 DenseMap<unsigned, VirtReg2IndexFunctor> &VUC); 00058 }; 00059 00060 RegisterPass<PNE> X("phi-node-elimination", 00061 "Eliminate PHI nodes for register allocation"); 00062 } 00063 00064 00065 const PassInfo *llvm::PHIEliminationID = X.getPassInfo(); 00066 00067 /// EliminatePHINodes - Eliminate phi nodes by inserting copy instructions in 00068 /// predecessor basic blocks. 00069 /// 00070 bool PNE::EliminatePHINodes(MachineFunction &MF, MachineBasicBlock &MBB) { 00071 if (MBB.empty() || MBB.front().getOpcode() != TargetInstrInfo::PHI) 00072 return false; // Quick exit for basic blocks without PHIs. 00073 00074 // VRegPHIUseCount - Keep track of the number of times each virtual register 00075 // is used by PHI nodes in successors of this block. 00076 DenseMap<unsigned, VirtReg2IndexFunctor> VRegPHIUseCount; 00077 VRegPHIUseCount.grow(MF.getSSARegMap()->getLastVirtReg()); 00078 00079 for (MachineBasicBlock::pred_iterator PI = MBB.pred_begin(), 00080 E = MBB.pred_end(); PI != E; ++PI) 00081 for (MachineBasicBlock::succ_iterator SI = (*PI)->succ_begin(), 00082 E = (*PI)->succ_end(); SI != E; ++SI) 00083 for (MachineBasicBlock::iterator BBI = (*SI)->begin(), E = (*SI)->end(); 00084 BBI != E && BBI->getOpcode() == TargetInstrInfo::PHI; ++BBI) 00085 for (unsigned i = 1, e = BBI->getNumOperands(); i != e; i += 2) 00086 VRegPHIUseCount[BBI->getOperand(i).getReg()]++; 00087 00088 // Get an iterator to the first instruction after the last PHI node (this may 00089 // also be the end of the basic block). 00090 MachineBasicBlock::iterator AfterPHIsIt = MBB.begin(); 00091 while (AfterPHIsIt != MBB.end() && 00092 AfterPHIsIt->getOpcode() == TargetInstrInfo::PHI) 00093 ++AfterPHIsIt; // Skip over all of the PHI nodes... 00094 00095 while (MBB.front().getOpcode() == TargetInstrInfo::PHI) { 00096 LowerAtomicPHINode(MBB, AfterPHIsIt, VRegPHIUseCount); 00097 } 00098 return true; 00099 } 00100 00101 /// InstructionUsesRegister - Return true if the specified machine instr has a 00102 /// use of the specified register. 00103 static bool InstructionUsesRegister(MachineInstr *MI, unsigned SrcReg) { 00104 for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) 00105 if (MI->getOperand(0).isRegister() && 00106 MI->getOperand(0).getReg() == SrcReg && 00107 MI->getOperand(0).isUse()) 00108 return true; 00109 return false; 00110 } 00111 00112 /// LowerAtomicPHINode - Lower the PHI node at the top of the specified block, 00113 /// under the assuption that it needs to be lowered in a way that supports 00114 /// atomic execution of PHIs. This lowering method is always correct all of the 00115 /// time. 00116 void PNE::LowerAtomicPHINode(MachineBasicBlock &MBB, 00117 MachineBasicBlock::iterator AfterPHIsIt, 00118 DenseMap<unsigned, VirtReg2IndexFunctor> &VRegPHIUseCount) { 00119 // Unlink the PHI node from the basic block, but don't delete the PHI yet. 00120 MachineInstr *MPhi = MBB.remove(MBB.begin()); 00121 00122 unsigned DestReg = MPhi->getOperand(0).getReg(); 00123 00124 // Create a new register for the incoming PHI arguments/ 00125 MachineFunction &MF = *MBB.getParent(); 00126 const TargetRegisterClass *RC = MF.getSSARegMap()->getRegClass(DestReg); 00127 unsigned IncomingReg = MF.getSSARegMap()->createVirtualRegister(RC); 00128 00129 // Insert a register to register copy in the top of the current block (but 00130 // after any remaining phi nodes) which copies the new incoming register 00131 // into the phi node destination. 00132 // 00133 const MRegisterInfo *RegInfo = MF.getTarget().getRegisterInfo(); 00134 RegInfo->copyRegToReg(MBB, AfterPHIsIt, DestReg, IncomingReg, RC); 00135 00136 // Update live variable information if there is any... 00137 LiveVariables *LV = getAnalysisToUpdate<LiveVariables>(); 00138 if (LV) { 00139 MachineInstr *PHICopy = prior(AfterPHIsIt); 00140 00141 // Add information to LiveVariables to know that the incoming value is 00142 // killed. Note that because the value is defined in several places (once 00143 // each for each incoming block), the "def" block and instruction fields 00144 // for the VarInfo is not filled in. 00145 // 00146 LV->addVirtualRegisterKilled(IncomingReg, PHICopy); 00147 00148 // Since we are going to be deleting the PHI node, if it is the last use 00149 // of any registers, or if the value itself is dead, we need to move this 00150 // information over to the new copy we just inserted. 00151 // 00152 LV->removeVirtualRegistersKilled(MPhi); 00153 00154 // If the result is dead, update LV. 00155 if (LV->RegisterDefIsDead(MPhi, DestReg)) { 00156 LV->addVirtualRegisterDead(DestReg, PHICopy); 00157 LV->removeVirtualRegistersDead(MPhi); 00158 } 00159 00160 // Realize that the destination register is defined by the PHI copy now, not 00161 // the PHI itself. 00162 LV->getVarInfo(DestReg).DefInst = PHICopy; 00163 } 00164 00165 // Adjust the VRegPHIUseCount map to account for the removal of this PHI 00166 // node. 00167 unsigned NumPreds = (MPhi->getNumOperands()-1)/2; 00168 for (unsigned i = 1; i != MPhi->getNumOperands(); i += 2) 00169 VRegPHIUseCount[MPhi->getOperand(i).getReg()] -= NumPreds; 00170 00171 // Now loop over all of the incoming arguments, changing them to copy into 00172 // the IncomingReg register in the corresponding predecessor basic block. 00173 // 00174 std::set<MachineBasicBlock*> MBBsInsertedInto; 00175 for (int i = MPhi->getNumOperands() - 1; i >= 2; i-=2) { 00176 unsigned SrcReg = MPhi->getOperand(i-1).getReg(); 00177 assert(MRegisterInfo::isVirtualRegister(SrcReg) && 00178 "Machine PHI Operands must all be virtual registers!"); 00179 00180 // Get the MachineBasicBlock equivalent of the BasicBlock that is the 00181 // source path the PHI. 00182 MachineBasicBlock &opBlock = *MPhi->getOperand(i).getMachineBasicBlock(); 00183 00184 // Check to make sure we haven't already emitted the copy for this block. 00185 // This can happen because PHI nodes may have multiple entries for the 00186 // same basic block. 00187 if (!MBBsInsertedInto.insert(&opBlock).second) 00188 continue; // If the copy has already been emitted, we're done. 00189 00190 // Get an iterator pointing to the first terminator in the block (or end()). 00191 // This is the point where we can insert a copy if we'd like to. 00192 MachineBasicBlock::iterator I = opBlock.getFirstTerminator(); 00193 00194 // Insert the copy. 00195 RegInfo->copyRegToReg(opBlock, I, IncomingReg, SrcReg, RC); 00196 00197 // Now update live variable information if we have it. Otherwise we're done 00198 if (!LV) continue; 00199 00200 // We want to be able to insert a kill of the register if this PHI 00201 // (aka, the copy we just inserted) is the last use of the source 00202 // value. Live variable analysis conservatively handles this by 00203 // saying that the value is live until the end of the block the PHI 00204 // entry lives in. If the value really is dead at the PHI copy, there 00205 // will be no successor blocks which have the value live-in. 00206 // 00207 // Check to see if the copy is the last use, and if so, update the 00208 // live variables information so that it knows the copy source 00209 // instruction kills the incoming value. 00210 // 00211 LiveVariables::VarInfo &InRegVI = LV->getVarInfo(SrcReg); 00212 00213 // Loop over all of the successors of the basic block, checking to see 00214 // if the value is either live in the block, or if it is killed in the 00215 // block. Also check to see if this register is in use by another PHI 00216 // node which has not yet been eliminated. If so, it will be killed 00217 // at an appropriate point later. 00218 // 00219 00220 // Is it used by any PHI instructions in this block? 00221 bool ValueIsLive = VRegPHIUseCount[SrcReg] != 0; 00222 00223 std::vector<MachineBasicBlock*> OpSuccBlocks; 00224 00225 // Otherwise, scan successors, including the BB the PHI node lives in. 00226 for (MachineBasicBlock::succ_iterator SI = opBlock.succ_begin(), 00227 E = opBlock.succ_end(); SI != E && !ValueIsLive; ++SI) { 00228 MachineBasicBlock *SuccMBB = *SI; 00229 00230 // Is it alive in this successor? 00231 unsigned SuccIdx = SuccMBB->getNumber(); 00232 if (SuccIdx < InRegVI.AliveBlocks.size() && 00233 InRegVI.AliveBlocks[SuccIdx]) { 00234 ValueIsLive = true; 00235 break; 00236 } 00237 00238 OpSuccBlocks.push_back(SuccMBB); 00239 } 00240 00241 // Check to see if this value is live because there is a use in a successor 00242 // that kills it. 00243 if (!ValueIsLive) { 00244 switch (OpSuccBlocks.size()) { 00245 case 1: { 00246 MachineBasicBlock *MBB = OpSuccBlocks[0]; 00247 for (unsigned i = 0, e = InRegVI.Kills.size(); i != e; ++i) 00248 if (InRegVI.Kills[i]->getParent() == MBB) { 00249 ValueIsLive = true; 00250 break; 00251 } 00252 break; 00253 } 00254 case 2: { 00255 MachineBasicBlock *MBB1 = OpSuccBlocks[0], *MBB2 = OpSuccBlocks[1]; 00256 for (unsigned i = 0, e = InRegVI.Kills.size(); i != e; ++i) 00257 if (InRegVI.Kills[i]->getParent() == MBB1 || 00258 InRegVI.Kills[i]->getParent() == MBB2) { 00259 ValueIsLive = true; 00260 break; 00261 } 00262 break; 00263 } 00264 default: 00265 std::sort(OpSuccBlocks.begin(), OpSuccBlocks.end()); 00266 for (unsigned i = 0, e = InRegVI.Kills.size(); i != e; ++i) 00267 if (std::binary_search(OpSuccBlocks.begin(), OpSuccBlocks.end(), 00268 InRegVI.Kills[i]->getParent())) { 00269 ValueIsLive = true; 00270 break; 00271 } 00272 } 00273 } 00274 00275 // Okay, if we now know that the value is not live out of the block, 00276 // we can add a kill marker in this block saying that it kills the incoming 00277 // value! 00278 if (!ValueIsLive) { 00279 // In our final twist, we have to decide which instruction kills the 00280 // register. In most cases this is the copy, however, the first 00281 // terminator instruction at the end of the block may also use the value. 00282 // In this case, we should mark *it* as being the killing block, not the 00283 // copy. 00284 bool FirstTerminatorUsesValue = false; 00285 if (I != opBlock.end()) { 00286 FirstTerminatorUsesValue = InstructionUsesRegister(I, SrcReg); 00287 00288 // Check that no other terminators use values. 00289 #ifndef NDEBUG 00290 for (MachineBasicBlock::iterator TI = next(I); TI != opBlock.end(); 00291 ++TI) { 00292 assert(!InstructionUsesRegister(TI, SrcReg) && 00293 "Terminator instructions cannot use virtual registers unless" 00294 "they are the first terminator in a block!"); 00295 } 00296 #endif 00297 } 00298 00299 MachineBasicBlock::iterator KillInst; 00300 if (!FirstTerminatorUsesValue) 00301 KillInst = prior(I); 00302 else 00303 KillInst = I; 00304 00305 // Finally, mark it killed. 00306 LV->addVirtualRegisterKilled(SrcReg, KillInst); 00307 00308 // This vreg no longer lives all of the way through opBlock. 00309 unsigned opBlockNum = opBlock.getNumber(); 00310 if (opBlockNum < InRegVI.AliveBlocks.size()) 00311 InRegVI.AliveBlocks[opBlockNum] = false; 00312 } 00313 } 00314 00315 // Really delete the PHI instruction now! 00316 delete MPhi; 00317 ++NumAtomic; 00318 }