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