PHIElimination.cpp revision 0416d2a70aea644c3e0c06301c29f3b81ec1e42d
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 (by 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 // Add information to LiveVariables to know that the incoming value is dead 84 if (LV) LV->addVirtualRegisterKill(IncomingReg, *(AfterPHIsIt-1)); 85 86 // Now loop over all of the incoming arguments turning them into copies into 87 // the IncomingReg register in the corresponding predecessor basic block. 88 // 89 for (int i = MI->getNumOperands() - 1; i >= 2; i-=2) { 90 MachineOperand &opVal = MI->getOperand(i-1); 91 92 // Get the MachineBasicBlock equivalent of the BasicBlock that is the 93 // source path the phi 94 MachineBasicBlock &opBlock = *MI->getOperand(i).getMachineBasicBlock(); 95 96 // Check to make sure we haven't already emitted the copy for this block. 97 // This can happen because PHI nodes may have multiple entries for the 98 // same basic block. It doesn't matter which entry we use though, because 99 // all incoming values are guaranteed to be the same for a particular bb. 100 // 101 // Note that this is N^2 in the number of phi node entries, but since the 102 // # of entries is tiny, this is not a problem. 103 // 104 bool HaveNotEmitted = true; 105 for (int op = MI->getNumOperands() - 1; op != i; op -= 2) 106 if (&opBlock == MI->getOperand(op).getMachineBasicBlock()) { 107 HaveNotEmitted = false; 108 break; 109 } 110 111 if (HaveNotEmitted) { 112 MachineBasicBlock::iterator I = opBlock.end(); 113 if (I != opBlock.begin()) { // Handle empty blocks 114 --I; 115 // must backtrack over ALL the branches in the previous block 116 while (MII.isTerminatorInstr((*I)->getOpcode()) && 117 I != opBlock.begin()) 118 --I; 119 120 // move back to the first branch instruction so new instructions 121 // are inserted right in front of it and not in front of a non-branch 122 if (!MII.isTerminatorInstr((*I)->getOpcode())) 123 ++I; 124 } 125 126 assert(opVal.isVirtualRegister() && 127 "Machine PHI Operands must all be virtual registers!"); 128 RegInfo->copyRegToReg(opBlock, I, IncomingReg, opVal.getReg(), RC); 129 } 130 } 131 132 // really delete the PHI instruction now! 133 delete MI; 134 } 135 136 return true; 137} 138