PHIElimination.cpp revision 927ce5dfaea00453889080cd1c6daf3eb197ad74
1//===-- PhiElimination.cpp - Eliminate PHI nodes by inserting copies ------===// 2// 3// This pass eliminates machine instruction PHI nodes by inserting copy 4// instructions. This destroys SSA information, but is the desired input for 5// some register allocators. 6// 7//===----------------------------------------------------------------------===// 8 9#include "llvm/CodeGen/MachineFunctionPass.h" 10#include "llvm/CodeGen/MachineInstr.h" 11#include "llvm/CodeGen/SSARegMap.h" 12#include "llvm/CodeGen/LiveVariables.h" 13#include "llvm/Target/TargetInstrInfo.h" 14#include "llvm/Target/TargetMachine.h" 15 16namespace { 17 struct PNE : public MachineFunctionPass { 18 bool runOnMachineFunction(MachineFunction &Fn) { 19 bool Changed = false; 20 21 // Eliminate PHI instructions by inserting copies into predecessor blocks. 22 // 23 for (MachineFunction::iterator I = Fn.begin(), E = Fn.end(); I != E; ++I) 24 Changed |= EliminatePHINodes(Fn, *I); 25 26 //std::cerr << "AFTER PHI NODE ELIM:\n"; 27 //Fn.dump(); 28 return Changed; 29 } 30 31 virtual void getAnalysisUsage(AnalysisUsage &AU) const { 32 AU.addPreserved<LiveVariables>(); 33 MachineFunctionPass::getAnalysisUsage(AU); 34 } 35 36 private: 37 /// EliminatePHINodes - Eliminate phi nodes by inserting copy instructions 38 /// in predecessor basic blocks. 39 /// 40 bool EliminatePHINodes(MachineFunction &MF, MachineBasicBlock &MBB); 41 }; 42 43 RegisterPass<PNE> X("phi-node-elimination", 44 "Eliminate PHI nodes for register allocation"); 45} 46 47const PassInfo *PHIEliminationID = X.getPassInfo(); 48 49/// EliminatePHINodes - Eliminate phi nodes by inserting copy instructions in 50/// predecessor basic blocks. 51/// 52bool PNE::EliminatePHINodes(MachineFunction &MF, MachineBasicBlock &MBB) { 53 if (MBB.empty() || MBB.front()->getOpcode() != TargetInstrInfo::PHI) 54 return false; // Quick exit for normal case... 55 56 LiveVariables *LV = getAnalysisToUpdate<LiveVariables>(); 57 const TargetInstrInfo &MII = MF.getTarget().getInstrInfo(); 58 const MRegisterInfo *RegInfo = MF.getTarget().getRegisterInfo(); 59 60 while (MBB.front()->getOpcode() == TargetInstrInfo::PHI) { 61 MachineInstr *MI = MBB.front(); 62 // Unlink the PHI node from the basic block... but don't delete the PHI yet 63 MBB.erase(MBB.begin()); 64 65 assert(MI->getOperand(0).isVirtualRegister() && 66 "PHI node doesn't write virt reg?"); 67 68 unsigned DestReg = MI->getOperand(0).getAllocatedRegNum(); 69 70 // Create a new register for the incoming PHI arguments 71 const TargetRegisterClass *RC = MF.getSSARegMap()->getRegClass(DestReg); 72 unsigned IncomingReg = MF.getSSARegMap()->createVirtualRegister(RC); 73 74 // Insert a register to register copy in the top of the current block (but 75 // after any remaining phi nodes) which copies the new incoming register 76 // into the phi node destination. 77 // 78 MachineBasicBlock::iterator AfterPHIsIt = MBB.begin(); 79 if (AfterPHIsIt != MBB.end()) 80 while ((*AfterPHIsIt)->getOpcode() == TargetInstrInfo::PHI) ++AfterPHIsIt; 81 RegInfo->copyRegToReg(MBB, AfterPHIsIt, DestReg, IncomingReg, RC); 82 83 // Update live variable information if there is any... 84 if (LV) { 85 MachineInstr *PHICopy = *(AfterPHIsIt-1); 86 87 // Add information to LiveVariables to know that the incoming value is 88 // dead. This says that the register is dead, not killed, because we 89 // cannot use the live variable information to indicate that the variable 90 // is defined in multiple entry blocks. Instead, we pretend that this 91 // instruction defined it and killed it at the same time. 92 // 93 LV->addVirtualRegisterDead(IncomingReg, PHICopy); 94 95 // Since we are going to be deleting the PHI node, if it is the last use 96 // of any registers, or if the value itself is dead, we need to move this 97 // information over to the new copy we just inserted... 98 // 99 std::pair<LiveVariables::killed_iterator, LiveVariables::killed_iterator> 100 RKs = LV->killed_range(MI); 101 if (RKs.first != RKs.second) { 102 for (LiveVariables::killed_iterator I = RKs.first; I != RKs.second; ++I) 103 LV->addVirtualRegisterKilled(I->second, PHICopy); 104 LV->removeVirtualRegistersKilled(RKs.first, RKs.second); 105 } 106 107 RKs = LV->dead_range(MI); 108 if (RKs.first != RKs.second) { 109 for (LiveVariables::killed_iterator I = RKs.first; I != RKs.second; ++I) 110 LV->addVirtualRegisterDead(I->second, PHICopy); 111 LV->removeVirtualRegistersDead(RKs.first, RKs.second); 112 } 113 } 114 115 // Now loop over all of the incoming arguments, changing them to copy into 116 // the IncomingReg register in the corresponding predecessor basic block. 117 // 118 for (int i = MI->getNumOperands() - 1; i >= 2; i-=2) { 119 MachineOperand &opVal = MI->getOperand(i-1); 120 121 // Get the MachineBasicBlock equivalent of the BasicBlock that is the 122 // source path the PHI. 123 MachineBasicBlock &opBlock = *MI->getOperand(i).getMachineBasicBlock(); 124 125 // Check to make sure we haven't already emitted the copy for this block. 126 // This can happen because PHI nodes may have multiple entries for the 127 // same basic block. It doesn't matter which entry we use though, because 128 // all incoming values are guaranteed to be the same for a particular bb. 129 // 130 // Note that this is N^2 in the number of phi node entries, but since the 131 // # of entries is usually small, this is not a problem. FIXME: this 132 // should just check to see if there is already a copy in the bottom of 133 // this basic block! 134 // 135 bool HaveNotEmitted = true; 136 for (int op = MI->getNumOperands() - 1; op != i; op -= 2) 137 if (&opBlock == MI->getOperand(op).getMachineBasicBlock()) { 138 HaveNotEmitted = false; 139 break; 140 } 141 142 if (HaveNotEmitted) { 143 MachineBasicBlock::iterator I = opBlock.end(); 144 if (I != opBlock.begin()) { // Handle empty blocks 145 --I; 146 // must backtrack over ALL the branches in the previous block 147 while (MII.isTerminatorInstr((*I)->getOpcode()) && 148 I != opBlock.begin()) 149 --I; 150 151 // move back to the first branch instruction so new instructions 152 // are inserted right in front of it and not in front of a non-branch 153 if (!MII.isTerminatorInstr((*I)->getOpcode())) 154 ++I; 155 } 156 157 assert(opVal.isVirtualRegister() && 158 "Machine PHI Operands must all be virtual registers!"); 159 RegInfo->copyRegToReg(opBlock, I, IncomingReg, opVal.getReg(), RC); 160 } 161 } 162 163 // really delete the PHI instruction now! 164 delete MI; 165 } 166 167 return true; 168} 169