PHIElimination.cpp revision 172c362fefe3d6e762ada119d4084ed4ed31595b
1//===-- PhiElimination.cpp - Eliminate PHI nodes by inserting copies ------===// 2// 3// The LLVM Compiler Infrastructure 4// 5// This file was developed by the LLVM research group and is distributed under 6// the University of Illinois Open Source 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#include "llvm/CodeGen/LiveVariables.h" 17#include "llvm/CodeGen/Passes.h" 18#include "llvm/CodeGen/MachineFunctionPass.h" 19#include "llvm/CodeGen/MachineInstr.h" 20#include "llvm/CodeGen/SSARegMap.h" 21#include "llvm/Target/TargetInstrInfo.h" 22#include "llvm/Target/TargetMachine.h" 23#include "llvm/ADT/DenseMap.h" 24#include "llvm/ADT/STLExtras.h" 25#include "llvm/ADT/Statistic.h" 26#include <set> 27#include <algorithm> 28using namespace llvm; 29 30namespace { 31 Statistic<> NumAtomic("phielim", "Number of atomic phis lowered"); 32 Statistic<> NumSimple("phielim", "Number of simple phis lowered"); 33 34 struct PNE : public MachineFunctionPass { 35 bool runOnMachineFunction(MachineFunction &Fn) { 36 bool Changed = false; 37 38 // Eliminate PHI instructions by inserting copies into predecessor blocks. 39 for (MachineFunction::iterator I = Fn.begin(), E = Fn.end(); I != E; ++I) 40 Changed |= EliminatePHINodes(Fn, *I); 41 42 return Changed; 43 } 44 45 virtual void getAnalysisUsage(AnalysisUsage &AU) const { 46 AU.addPreserved<LiveVariables>(); 47 MachineFunctionPass::getAnalysisUsage(AU); 48 } 49 50 private: 51 /// EliminatePHINodes - Eliminate phi nodes by inserting copy instructions 52 /// in predecessor basic blocks. 53 /// 54 bool EliminatePHINodes(MachineFunction &MF, MachineBasicBlock &MBB); 55 void LowerAtomicPHINode(MachineBasicBlock &MBB, 56 MachineBasicBlock::iterator AfterPHIsIt, 57 DenseMap<unsigned, VirtReg2IndexFunctor> &VUC); 58 }; 59 60 RegisterPass<PNE> X("phi-node-elimination", 61 "Eliminate PHI nodes for register allocation"); 62} 63 64 65const PassInfo *llvm::PHIEliminationID = X.getPassInfo(); 66 67/// EliminatePHINodes - Eliminate phi nodes by inserting copy instructions in 68/// predecessor basic blocks. 69/// 70bool PNE::EliminatePHINodes(MachineFunction &MF, MachineBasicBlock &MBB) { 71 if (MBB.empty() || MBB.front().getOpcode() != TargetInstrInfo::PHI) 72 return false; // Quick exit for basic blocks without PHIs. 73 74 // VRegPHIUseCount - Keep track of the number of times each virtual register 75 // is used by PHI nodes in successors of this block. 76 DenseMap<unsigned, VirtReg2IndexFunctor> VRegPHIUseCount; 77 VRegPHIUseCount.grow(MF.getSSARegMap()->getLastVirtReg()); 78 79 for (MachineBasicBlock::pred_iterator PI = MBB.pred_begin(), 80 E = MBB.pred_end(); PI != E; ++PI) 81 for (MachineBasicBlock::succ_iterator SI = (*PI)->succ_begin(), 82 E = (*PI)->succ_end(); SI != E; ++SI) 83 for (MachineBasicBlock::iterator BBI = (*SI)->begin(), E = (*SI)->end(); 84 BBI != E && BBI->getOpcode() == TargetInstrInfo::PHI; ++BBI) 85 for (unsigned i = 1, e = BBI->getNumOperands(); i != e; i += 2) 86 VRegPHIUseCount[BBI->getOperand(i).getReg()]++; 87 88 // Get an iterator to the first instruction after the last PHI node (this may 89 // also be the end of the basic block). 90 MachineBasicBlock::iterator AfterPHIsIt = MBB.begin(); 91 while (AfterPHIsIt != MBB.end() && 92 AfterPHIsIt->getOpcode() == TargetInstrInfo::PHI) 93 ++AfterPHIsIt; // Skip over all of the PHI nodes... 94 95 while (MBB.front().getOpcode() == TargetInstrInfo::PHI) { 96 LowerAtomicPHINode(MBB, AfterPHIsIt, VRegPHIUseCount); 97 } 98 return true; 99} 100 101/// LowerAtomicPHINode - Lower the PHI node at the top of the specified block, 102/// under the assuption that it needs to be lowered in a way that supports 103/// atomic execution of PHIs. This lowering method is always correct all of the 104/// time. 105void PNE::LowerAtomicPHINode(MachineBasicBlock &MBB, 106 MachineBasicBlock::iterator AfterPHIsIt, 107 DenseMap<unsigned, VirtReg2IndexFunctor> &VRegPHIUseCount) { 108 // Unlink the PHI node from the basic block, but don't delete the PHI yet. 109 MachineInstr *MPhi = MBB.remove(MBB.begin()); 110 111 unsigned DestReg = MPhi->getOperand(0).getReg(); 112 113 // Create a new register for the incoming PHI arguments/ 114 MachineFunction &MF = *MBB.getParent(); 115 const TargetRegisterClass *RC = MF.getSSARegMap()->getRegClass(DestReg); 116 unsigned IncomingReg = MF.getSSARegMap()->createVirtualRegister(RC); 117 118 // Insert a register to register copy in the top of the current block (but 119 // after any remaining phi nodes) which copies the new incoming register 120 // into the phi node destination. 121 // 122 const MRegisterInfo *RegInfo = MF.getTarget().getRegisterInfo(); 123 RegInfo->copyRegToReg(MBB, AfterPHIsIt, DestReg, IncomingReg, RC); 124 125 // Update live variable information if there is any... 126 LiveVariables *LV = getAnalysisToUpdate<LiveVariables>(); 127 if (LV) { 128 MachineInstr *PHICopy = prior(AfterPHIsIt); 129 130 // Add information to LiveVariables to know that the incoming value is 131 // killed. Note that because the value is defined in several places (once 132 // each for each incoming block), the "def" block and instruction fields 133 // for the VarInfo is not filled in. 134 // 135 LV->addVirtualRegisterKilled(IncomingReg, PHICopy); 136 137 // Since we are going to be deleting the PHI node, if it is the last use 138 // of any registers, or if the value itself is dead, we need to move this 139 // information over to the new copy we just inserted. 140 // 141 LV->removeVirtualRegistersKilled(MPhi); 142 143 // If the result is dead, update LV. 144 if (LV->RegisterDefIsDead(MPhi, DestReg)) { 145 LV->addVirtualRegisterDead(DestReg, PHICopy); 146 LV->removeVirtualRegistersDead(MPhi); 147 } 148 149 // Realize that the destination register is defined by the PHI copy now, not 150 // the PHI itself. 151 LV->getVarInfo(DestReg).DefInst = PHICopy; 152 } 153 154 // Adjust the VRegPHIUseCount map to account for the removal of this PHI 155 // node. 156 unsigned NumPreds = (MPhi->getNumOperands()-1)/2; 157 for (unsigned i = 1; i != MPhi->getNumOperands(); i += 2) 158 VRegPHIUseCount[MPhi->getOperand(i).getReg()] -= NumPreds; 159 160 // Now loop over all of the incoming arguments, changing them to copy into 161 // the IncomingReg register in the corresponding predecessor basic block. 162 // 163 std::set<MachineBasicBlock*> MBBsInsertedInto; 164 for (int i = MPhi->getNumOperands() - 1; i >= 2; i-=2) { 165 unsigned SrcReg = MPhi->getOperand(i-1).getReg(); 166 assert(MRegisterInfo::isVirtualRegister(SrcReg) && 167 "Machine PHI Operands must all be virtual registers!"); 168 169 // Get the MachineBasicBlock equivalent of the BasicBlock that is the 170 // source path the PHI. 171 MachineBasicBlock &opBlock = *MPhi->getOperand(i).getMachineBasicBlock(); 172 173 // Check to make sure we haven't already emitted the copy for this block. 174 // This can happen because PHI nodes may have multiple entries for the 175 // same basic block. 176 if (!MBBsInsertedInto.insert(&opBlock).second) 177 continue; // If the copy has already been emitted, we're done. 178 179 // Get an iterator pointing to the first terminator in the block (or end()). 180 // This is the point where we can insert a copy if we'd like to. 181 MachineBasicBlock::iterator I = opBlock.getFirstTerminator(); 182 183 // Insert the copy. 184 RegInfo->copyRegToReg(opBlock, I, IncomingReg, SrcReg, RC); 185 186 // Now update live variable information if we have it. Otherwise we're done 187 if (!LV) continue; 188 189 // We want to be able to insert a kill of the register if this PHI 190 // (aka, the copy we just inserted) is the last use of the source 191 // value. Live variable analysis conservatively handles this by 192 // saying that the value is live until the end of the block the PHI 193 // entry lives in. If the value really is dead at the PHI copy, there 194 // will be no successor blocks which have the value live-in. 195 // 196 // Check to see if the copy is the last use, and if so, update the 197 // live variables information so that it knows the copy source 198 // instruction kills the incoming value. 199 // 200 LiveVariables::VarInfo &InRegVI = LV->getVarInfo(SrcReg); 201 202 // Loop over all of the successors of the basic block, checking to see 203 // if the value is either live in the block, or if it is killed in the 204 // block. Also check to see if this register is in use by another PHI 205 // node which has not yet been eliminated. If so, it will be killed 206 // at an appropriate point later. 207 // 208 209 // Is it used by any PHI instructions in this block? 210 bool ValueIsLive = VRegPHIUseCount[SrcReg] != 0; 211 212 std::vector<MachineBasicBlock*> OpSuccBlocks; 213 214 // Otherwise, scan successors, including the BB the PHI node lives in. 215 for (MachineBasicBlock::succ_iterator SI = opBlock.succ_begin(), 216 E = opBlock.succ_end(); SI != E && !ValueIsLive; ++SI) { 217 MachineBasicBlock *SuccMBB = *SI; 218 219 // Is it alive in this successor? 220 unsigned SuccIdx = SuccMBB->getNumber(); 221 if (SuccIdx < InRegVI.AliveBlocks.size() && 222 InRegVI.AliveBlocks[SuccIdx]) { 223 ValueIsLive = true; 224 break; 225 } 226 227 OpSuccBlocks.push_back(SuccMBB); 228 } 229 230 // Check to see if this value is live because there is a use in a successor 231 // that kills it. 232 if (!ValueIsLive) { 233 switch (OpSuccBlocks.size()) { 234 case 1: { 235 MachineBasicBlock *MBB = OpSuccBlocks[0]; 236 for (unsigned i = 0, e = InRegVI.Kills.size(); i != e; ++i) 237 if (InRegVI.Kills[i]->getParent() == MBB) { 238 ValueIsLive = true; 239 break; 240 } 241 break; 242 } 243 case 2: { 244 MachineBasicBlock *MBB1 = OpSuccBlocks[0], *MBB2 = OpSuccBlocks[1]; 245 for (unsigned i = 0, e = InRegVI.Kills.size(); i != e; ++i) 246 if (InRegVI.Kills[i]->getParent() == MBB1 || 247 InRegVI.Kills[i]->getParent() == MBB2) { 248 ValueIsLive = true; 249 break; 250 } 251 break; 252 } 253 default: 254 std::sort(OpSuccBlocks.begin(), OpSuccBlocks.end()); 255 for (unsigned i = 0, e = InRegVI.Kills.size(); i != e; ++i) 256 if (std::binary_search(OpSuccBlocks.begin(), OpSuccBlocks.end(), 257 InRegVI.Kills[i]->getParent())) { 258 ValueIsLive = true; 259 break; 260 } 261 } 262 } 263 264 // Okay, if we now know that the value is not live out of the block, 265 // we can add a kill marker to the copy we inserted saying that it 266 // kills the incoming value! 267 // 268 if (!ValueIsLive) { 269 MachineBasicBlock::iterator Prev = prior(I); 270 LV->addVirtualRegisterKilled(SrcReg, Prev); 271 272 // This vreg no longer lives all of the way through opBlock. 273 unsigned opBlockNum = opBlock.getNumber(); 274 if (opBlockNum < InRegVI.AliveBlocks.size()) 275 InRegVI.AliveBlocks[opBlockNum] = false; 276 } 277 } 278 279 // Really delete the PHI instruction now! 280 delete MPhi; 281 ++NumAtomic; 282} 283