PHIElimination.cpp revision 08d2e4e09adc53aa93c08c8327d2f5f2814acb74
1bc40e898e153c9b81f246a7971eaac7b14446c49Chris Lattner//===-- PhiElimination.cpp - Eliminate PHI nodes by inserting copies ------===// 2bc40e898e153c9b81f246a7971eaac7b14446c49Chris Lattner// 3bc40e898e153c9b81f246a7971eaac7b14446c49Chris Lattner// This pass eliminates machine instruction PHI nodes by inserting copy 4bc40e898e153c9b81f246a7971eaac7b14446c49Chris Lattner// instructions. This destroys SSA information, but is the desired input for 5bc40e898e153c9b81f246a7971eaac7b14446c49Chris Lattner// some register allocators. 6bc40e898e153c9b81f246a7971eaac7b14446c49Chris Lattner// 7bc40e898e153c9b81f246a7971eaac7b14446c49Chris Lattner//===----------------------------------------------------------------------===// 8bc40e898e153c9b81f246a7971eaac7b14446c49Chris Lattner 9bc40e898e153c9b81f246a7971eaac7b14446c49Chris Lattner#include "llvm/CodeGen/MachineFunctionPass.h" 10bc40e898e153c9b81f246a7971eaac7b14446c49Chris Lattner#include "llvm/CodeGen/MachineInstr.h" 11bc40e898e153c9b81f246a7971eaac7b14446c49Chris Lattner#include "llvm/CodeGen/SSARegMap.h" 12bc40e898e153c9b81f246a7971eaac7b14446c49Chris Lattner#include "llvm/CodeGen/LiveVariables.h" 133501feab811c86c9659248a4875fc31a3165f84dChris Lattner#include "llvm/Target/TargetInstrInfo.h" 14bc40e898e153c9b81f246a7971eaac7b14446c49Chris Lattner#include "llvm/Target/TargetMachine.h" 15572c77066808fc0e9ee1d212dab227f28bf5e28aChris Lattner#include "llvm/Support/CFG.h" 16bc40e898e153c9b81f246a7971eaac7b14446c49Chris Lattner 17bc40e898e153c9b81f246a7971eaac7b14446c49Chris Lattnernamespace { 18bc40e898e153c9b81f246a7971eaac7b14446c49Chris Lattner struct PNE : public MachineFunctionPass { 19bc40e898e153c9b81f246a7971eaac7b14446c49Chris Lattner bool runOnMachineFunction(MachineFunction &Fn) { 20bc40e898e153c9b81f246a7971eaac7b14446c49Chris Lattner bool Changed = false; 21bc40e898e153c9b81f246a7971eaac7b14446c49Chris Lattner 22bc40e898e153c9b81f246a7971eaac7b14446c49Chris Lattner // Eliminate PHI instructions by inserting copies into predecessor blocks. 23bc40e898e153c9b81f246a7971eaac7b14446c49Chris Lattner // 24bc40e898e153c9b81f246a7971eaac7b14446c49Chris Lattner for (MachineFunction::iterator I = Fn.begin(), E = Fn.end(); I != E; ++I) 25bc40e898e153c9b81f246a7971eaac7b14446c49Chris Lattner Changed |= EliminatePHINodes(Fn, *I); 26bc40e898e153c9b81f246a7971eaac7b14446c49Chris Lattner 27bc40e898e153c9b81f246a7971eaac7b14446c49Chris Lattner //std::cerr << "AFTER PHI NODE ELIM:\n"; 28bc40e898e153c9b81f246a7971eaac7b14446c49Chris Lattner //Fn.dump(); 29bc40e898e153c9b81f246a7971eaac7b14446c49Chris Lattner return Changed; 30bc40e898e153c9b81f246a7971eaac7b14446c49Chris Lattner } 31bc40e898e153c9b81f246a7971eaac7b14446c49Chris Lattner 32bc40e898e153c9b81f246a7971eaac7b14446c49Chris Lattner virtual void getAnalysisUsage(AnalysisUsage &AU) const { 33bc40e898e153c9b81f246a7971eaac7b14446c49Chris Lattner AU.addPreserved<LiveVariables>(); 34bc40e898e153c9b81f246a7971eaac7b14446c49Chris Lattner MachineFunctionPass::getAnalysisUsage(AU); 35bc40e898e153c9b81f246a7971eaac7b14446c49Chris Lattner } 36bc40e898e153c9b81f246a7971eaac7b14446c49Chris Lattner 37bc40e898e153c9b81f246a7971eaac7b14446c49Chris Lattner private: 38bc40e898e153c9b81f246a7971eaac7b14446c49Chris Lattner /// EliminatePHINodes - Eliminate phi nodes by inserting copy instructions 39bc40e898e153c9b81f246a7971eaac7b14446c49Chris Lattner /// in predecessor basic blocks. 40bc40e898e153c9b81f246a7971eaac7b14446c49Chris Lattner /// 41bc40e898e153c9b81f246a7971eaac7b14446c49Chris Lattner bool EliminatePHINodes(MachineFunction &MF, MachineBasicBlock &MBB); 42bc40e898e153c9b81f246a7971eaac7b14446c49Chris Lattner }; 43bc40e898e153c9b81f246a7971eaac7b14446c49Chris Lattner 44bc40e898e153c9b81f246a7971eaac7b14446c49Chris Lattner RegisterPass<PNE> X("phi-node-elimination", 45bc40e898e153c9b81f246a7971eaac7b14446c49Chris Lattner "Eliminate PHI nodes for register allocation"); 46bc40e898e153c9b81f246a7971eaac7b14446c49Chris Lattner} 47bc40e898e153c9b81f246a7971eaac7b14446c49Chris Lattner 48bc40e898e153c9b81f246a7971eaac7b14446c49Chris Lattnerconst PassInfo *PHIEliminationID = X.getPassInfo(); 49bc40e898e153c9b81f246a7971eaac7b14446c49Chris Lattner 50bc40e898e153c9b81f246a7971eaac7b14446c49Chris Lattner/// EliminatePHINodes - Eliminate phi nodes by inserting copy instructions in 51bc40e898e153c9b81f246a7971eaac7b14446c49Chris Lattner/// predecessor basic blocks. 52bc40e898e153c9b81f246a7971eaac7b14446c49Chris Lattner/// 53bc40e898e153c9b81f246a7971eaac7b14446c49Chris Lattnerbool PNE::EliminatePHINodes(MachineFunction &MF, MachineBasicBlock &MBB) { 540416d2a70aea644c3e0c06301c29f3b81ec1e42dChris Lattner if (MBB.empty() || MBB.front()->getOpcode() != TargetInstrInfo::PHI) 55bc40e898e153c9b81f246a7971eaac7b14446c49Chris Lattner return false; // Quick exit for normal case... 56bc40e898e153c9b81f246a7971eaac7b14446c49Chris Lattner 57bc40e898e153c9b81f246a7971eaac7b14446c49Chris Lattner LiveVariables *LV = getAnalysisToUpdate<LiveVariables>(); 58bc40e898e153c9b81f246a7971eaac7b14446c49Chris Lattner const TargetInstrInfo &MII = MF.getTarget().getInstrInfo(); 59bc40e898e153c9b81f246a7971eaac7b14446c49Chris Lattner const MRegisterInfo *RegInfo = MF.getTarget().getRegisterInfo(); 60bc40e898e153c9b81f246a7971eaac7b14446c49Chris Lattner 61bc40e898e153c9b81f246a7971eaac7b14446c49Chris Lattner while (MBB.front()->getOpcode() == TargetInstrInfo::PHI) { 62bc40e898e153c9b81f246a7971eaac7b14446c49Chris Lattner MachineInstr *MI = MBB.front(); 63bc40e898e153c9b81f246a7971eaac7b14446c49Chris Lattner // Unlink the PHI node from the basic block... but don't delete the PHI yet 64bc40e898e153c9b81f246a7971eaac7b14446c49Chris Lattner MBB.erase(MBB.begin()); 65bc40e898e153c9b81f246a7971eaac7b14446c49Chris Lattner 66bc40e898e153c9b81f246a7971eaac7b14446c49Chris Lattner assert(MI->getOperand(0).isVirtualRegister() && 67bc40e898e153c9b81f246a7971eaac7b14446c49Chris Lattner "PHI node doesn't write virt reg?"); 68bc40e898e153c9b81f246a7971eaac7b14446c49Chris Lattner 69bc40e898e153c9b81f246a7971eaac7b14446c49Chris Lattner unsigned DestReg = MI->getOperand(0).getAllocatedRegNum(); 70bc40e898e153c9b81f246a7971eaac7b14446c49Chris Lattner 71bc40e898e153c9b81f246a7971eaac7b14446c49Chris Lattner // Create a new register for the incoming PHI arguments 72bc40e898e153c9b81f246a7971eaac7b14446c49Chris Lattner const TargetRegisterClass *RC = MF.getSSARegMap()->getRegClass(DestReg); 73bc40e898e153c9b81f246a7971eaac7b14446c49Chris Lattner unsigned IncomingReg = MF.getSSARegMap()->createVirtualRegister(RC); 74bc40e898e153c9b81f246a7971eaac7b14446c49Chris Lattner 75927ce5dfaea00453889080cd1c6daf3eb197ad74Chris Lattner // Insert a register to register copy in the top of the current block (but 76bc40e898e153c9b81f246a7971eaac7b14446c49Chris Lattner // after any remaining phi nodes) which copies the new incoming register 77bc40e898e153c9b81f246a7971eaac7b14446c49Chris Lattner // into the phi node destination. 78bc40e898e153c9b81f246a7971eaac7b14446c49Chris Lattner // 79bc40e898e153c9b81f246a7971eaac7b14446c49Chris Lattner MachineBasicBlock::iterator AfterPHIsIt = MBB.begin(); 80a13f0d3f4159b1f54bcfc733ccd94977b020ea56Chris Lattner while (AfterPHIsIt != MBB.end() && 81a13f0d3f4159b1f54bcfc733ccd94977b020ea56Chris Lattner (*AfterPHIsIt)->getOpcode() == TargetInstrInfo::PHI) 82a13f0d3f4159b1f54bcfc733ccd94977b020ea56Chris Lattner ++AfterPHIsIt; // Skip over all of the PHI nodes... 83bc40e898e153c9b81f246a7971eaac7b14446c49Chris Lattner RegInfo->copyRegToReg(MBB, AfterPHIsIt, DestReg, IncomingReg, RC); 84927ce5dfaea00453889080cd1c6daf3eb197ad74Chris Lattner 85927ce5dfaea00453889080cd1c6daf3eb197ad74Chris Lattner // Update live variable information if there is any... 86927ce5dfaea00453889080cd1c6daf3eb197ad74Chris Lattner if (LV) { 87927ce5dfaea00453889080cd1c6daf3eb197ad74Chris Lattner MachineInstr *PHICopy = *(AfterPHIsIt-1); 88927ce5dfaea00453889080cd1c6daf3eb197ad74Chris Lattner 89927ce5dfaea00453889080cd1c6daf3eb197ad74Chris Lattner // Add information to LiveVariables to know that the incoming value is 90b52e0241c03a257f96bd9c77788eff5b1a7fd437Chris Lattner // killed. Note that because the value is defined in several places (once 91b52e0241c03a257f96bd9c77788eff5b1a7fd437Chris Lattner // each for each incoming block), the "def" block and instruction fields 92b52e0241c03a257f96bd9c77788eff5b1a7fd437Chris Lattner // for the VarInfo is not filled in. 93927ce5dfaea00453889080cd1c6daf3eb197ad74Chris Lattner // 94b52e0241c03a257f96bd9c77788eff5b1a7fd437Chris Lattner LV->addVirtualRegisterKilled(IncomingReg, &MBB, PHICopy); 95bc40e898e153c9b81f246a7971eaac7b14446c49Chris Lattner 96927ce5dfaea00453889080cd1c6daf3eb197ad74Chris Lattner // Since we are going to be deleting the PHI node, if it is the last use 97927ce5dfaea00453889080cd1c6daf3eb197ad74Chris Lattner // of any registers, or if the value itself is dead, we need to move this 98927ce5dfaea00453889080cd1c6daf3eb197ad74Chris Lattner // information over to the new copy we just inserted... 99927ce5dfaea00453889080cd1c6daf3eb197ad74Chris Lattner // 100927ce5dfaea00453889080cd1c6daf3eb197ad74Chris Lattner std::pair<LiveVariables::killed_iterator, LiveVariables::killed_iterator> 101927ce5dfaea00453889080cd1c6daf3eb197ad74Chris Lattner RKs = LV->killed_range(MI); 102572c77066808fc0e9ee1d212dab227f28bf5e28aChris Lattner std::vector<std::pair<MachineInstr*, unsigned> > Range; 103927ce5dfaea00453889080cd1c6daf3eb197ad74Chris Lattner if (RKs.first != RKs.second) { 104572c77066808fc0e9ee1d212dab227f28bf5e28aChris Lattner // Copy the range into a vector... 105572c77066808fc0e9ee1d212dab227f28bf5e28aChris Lattner Range.assign(RKs.first, RKs.second); 106572c77066808fc0e9ee1d212dab227f28bf5e28aChris Lattner 107572c77066808fc0e9ee1d212dab227f28bf5e28aChris Lattner // Delete the range... 108927ce5dfaea00453889080cd1c6daf3eb197ad74Chris Lattner LV->removeVirtualRegistersKilled(RKs.first, RKs.second); 109572c77066808fc0e9ee1d212dab227f28bf5e28aChris Lattner 110572c77066808fc0e9ee1d212dab227f28bf5e28aChris Lattner // Add all of the kills back, which will update the appropriate info... 111572c77066808fc0e9ee1d212dab227f28bf5e28aChris Lattner for (unsigned i = 0, e = Range.size(); i != e; ++i) 112572c77066808fc0e9ee1d212dab227f28bf5e28aChris Lattner LV->addVirtualRegisterKilled(Range[i].second, &MBB, PHICopy); 113927ce5dfaea00453889080cd1c6daf3eb197ad74Chris Lattner } 114927ce5dfaea00453889080cd1c6daf3eb197ad74Chris Lattner 115927ce5dfaea00453889080cd1c6daf3eb197ad74Chris Lattner RKs = LV->dead_range(MI); 116927ce5dfaea00453889080cd1c6daf3eb197ad74Chris Lattner if (RKs.first != RKs.second) { 117572c77066808fc0e9ee1d212dab227f28bf5e28aChris Lattner // Works as above... 118572c77066808fc0e9ee1d212dab227f28bf5e28aChris Lattner Range.assign(RKs.first, RKs.second); 119927ce5dfaea00453889080cd1c6daf3eb197ad74Chris Lattner LV->removeVirtualRegistersDead(RKs.first, RKs.second); 120572c77066808fc0e9ee1d212dab227f28bf5e28aChris Lattner for (unsigned i = 0, e = Range.size(); i != e; ++i) 121572c77066808fc0e9ee1d212dab227f28bf5e28aChris Lattner LV->addVirtualRegisterDead(Range[i].second, &MBB, PHICopy); 122927ce5dfaea00453889080cd1c6daf3eb197ad74Chris Lattner } 123927ce5dfaea00453889080cd1c6daf3eb197ad74Chris Lattner } 124bc40e898e153c9b81f246a7971eaac7b14446c49Chris Lattner 125927ce5dfaea00453889080cd1c6daf3eb197ad74Chris Lattner // Now loop over all of the incoming arguments, changing them to copy into 126bc40e898e153c9b81f246a7971eaac7b14446c49Chris Lattner // the IncomingReg register in the corresponding predecessor basic block. 127bc40e898e153c9b81f246a7971eaac7b14446c49Chris Lattner // 128bc40e898e153c9b81f246a7971eaac7b14446c49Chris Lattner for (int i = MI->getNumOperands() - 1; i >= 2; i-=2) { 129bc40e898e153c9b81f246a7971eaac7b14446c49Chris Lattner MachineOperand &opVal = MI->getOperand(i-1); 130bc40e898e153c9b81f246a7971eaac7b14446c49Chris Lattner 131bc40e898e153c9b81f246a7971eaac7b14446c49Chris Lattner // Get the MachineBasicBlock equivalent of the BasicBlock that is the 132927ce5dfaea00453889080cd1c6daf3eb197ad74Chris Lattner // source path the PHI. 133bc40e898e153c9b81f246a7971eaac7b14446c49Chris Lattner MachineBasicBlock &opBlock = *MI->getOperand(i).getMachineBasicBlock(); 134bc40e898e153c9b81f246a7971eaac7b14446c49Chris Lattner 13598719d7cdc693c077d179fe3461ce625d6faef34Chris Lattner // Figure out where to insert the copy, which is at the end of the 13698719d7cdc693c077d179fe3461ce625d6faef34Chris Lattner // predecessor basic block, but before any terminator/branch 13798719d7cdc693c077d179fe3461ce625d6faef34Chris Lattner // instructions... 13898719d7cdc693c077d179fe3461ce625d6faef34Chris Lattner MachineBasicBlock::iterator I = opBlock.end(); 13998719d7cdc693c077d179fe3461ce625d6faef34Chris Lattner if (I != opBlock.begin()) { // Handle empty blocks 14098719d7cdc693c077d179fe3461ce625d6faef34Chris Lattner --I; 14198719d7cdc693c077d179fe3461ce625d6faef34Chris Lattner // must backtrack over ALL the branches in the previous block 14298719d7cdc693c077d179fe3461ce625d6faef34Chris Lattner while (MII.isTerminatorInstr((*I)->getOpcode()) && 14398719d7cdc693c077d179fe3461ce625d6faef34Chris Lattner I != opBlock.begin()) 14498719d7cdc693c077d179fe3461ce625d6faef34Chris Lattner --I; 14598719d7cdc693c077d179fe3461ce625d6faef34Chris Lattner 14698719d7cdc693c077d179fe3461ce625d6faef34Chris Lattner // move back to the first branch instruction so new instructions 14798719d7cdc693c077d179fe3461ce625d6faef34Chris Lattner // are inserted right in front of it and not in front of a non-branch 14898719d7cdc693c077d179fe3461ce625d6faef34Chris Lattner if (!MII.isTerminatorInstr((*I)->getOpcode())) 14998719d7cdc693c077d179fe3461ce625d6faef34Chris Lattner ++I; 15098719d7cdc693c077d179fe3461ce625d6faef34Chris Lattner } 15198719d7cdc693c077d179fe3461ce625d6faef34Chris Lattner 152bc40e898e153c9b81f246a7971eaac7b14446c49Chris Lattner // Check to make sure we haven't already emitted the copy for this block. 153bc40e898e153c9b81f246a7971eaac7b14446c49Chris Lattner // This can happen because PHI nodes may have multiple entries for the 154bc40e898e153c9b81f246a7971eaac7b14446c49Chris Lattner // same basic block. It doesn't matter which entry we use though, because 155bc40e898e153c9b81f246a7971eaac7b14446c49Chris Lattner // all incoming values are guaranteed to be the same for a particular bb. 156bc40e898e153c9b81f246a7971eaac7b14446c49Chris Lattner // 15798719d7cdc693c077d179fe3461ce625d6faef34Chris Lattner // If we emitted a copy for this basic block already, it will be right 15898719d7cdc693c077d179fe3461ce625d6faef34Chris Lattner // where we want to insert one now. Just check for a definition of the 15998719d7cdc693c077d179fe3461ce625d6faef34Chris Lattner // register we are interested in! 160bc40e898e153c9b81f246a7971eaac7b14446c49Chris Lattner // 161bc40e898e153c9b81f246a7971eaac7b14446c49Chris Lattner bool HaveNotEmitted = true; 16298719d7cdc693c077d179fe3461ce625d6faef34Chris Lattner 16398719d7cdc693c077d179fe3461ce625d6faef34Chris Lattner if (I != opBlock.begin()) { 16498719d7cdc693c077d179fe3461ce625d6faef34Chris Lattner MachineInstr *PrevInst = *(I-1); 16598719d7cdc693c077d179fe3461ce625d6faef34Chris Lattner for (unsigned i = 0, e = PrevInst->getNumOperands(); i != e; ++i) { 16698719d7cdc693c077d179fe3461ce625d6faef34Chris Lattner MachineOperand &MO = PrevInst->getOperand(i); 16798719d7cdc693c077d179fe3461ce625d6faef34Chris Lattner if (MO.isVirtualRegister() && MO.getReg() == IncomingReg) 1685f2180c53330502eb2f0f5bf3f21a838ad800906Vikram S. Adve if (MO.opIsDefOnly() || MO.opIsDefAndUse()) { 16998719d7cdc693c077d179fe3461ce625d6faef34Chris Lattner HaveNotEmitted = false; 17098719d7cdc693c077d179fe3461ce625d6faef34Chris Lattner break; 17198719d7cdc693c077d179fe3461ce625d6faef34Chris Lattner } 172bc40e898e153c9b81f246a7971eaac7b14446c49Chris Lattner } 17398719d7cdc693c077d179fe3461ce625d6faef34Chris Lattner } 174bc40e898e153c9b81f246a7971eaac7b14446c49Chris Lattner 175572c77066808fc0e9ee1d212dab227f28bf5e28aChris Lattner if (HaveNotEmitted) { // If the copy has not already been emitted, do it. 17698719d7cdc693c077d179fe3461ce625d6faef34Chris Lattner assert(opVal.isVirtualRegister() && 17798719d7cdc693c077d179fe3461ce625d6faef34Chris Lattner "Machine PHI Operands must all be virtual registers!"); 178572c77066808fc0e9ee1d212dab227f28bf5e28aChris Lattner unsigned SrcReg = opVal.getReg(); 179572c77066808fc0e9ee1d212dab227f28bf5e28aChris Lattner RegInfo->copyRegToReg(opBlock, I, IncomingReg, SrcReg, RC); 180572c77066808fc0e9ee1d212dab227f28bf5e28aChris Lattner 181572c77066808fc0e9ee1d212dab227f28bf5e28aChris Lattner // Now update live variable information if we have it. 182572c77066808fc0e9ee1d212dab227f28bf5e28aChris Lattner if (LV) { 183572c77066808fc0e9ee1d212dab227f28bf5e28aChris Lattner // We want to be able to insert a kill of the register if this PHI 184572c77066808fc0e9ee1d212dab227f28bf5e28aChris Lattner // (aka, the copy we just inserted) is the last use of the source 185572c77066808fc0e9ee1d212dab227f28bf5e28aChris Lattner // value. Live variable analysis conservatively handles this by 186572c77066808fc0e9ee1d212dab227f28bf5e28aChris Lattner // saying that the value is live until the end of the block the PHI 187572c77066808fc0e9ee1d212dab227f28bf5e28aChris Lattner // entry lives in. If the value really is dead at the PHI copy, there 188572c77066808fc0e9ee1d212dab227f28bf5e28aChris Lattner // will be no successor blocks which have the value live-in. 189572c77066808fc0e9ee1d212dab227f28bf5e28aChris Lattner // 190572c77066808fc0e9ee1d212dab227f28bf5e28aChris Lattner // Check to see if the copy is the last use, and if so, update the 191572c77066808fc0e9ee1d212dab227f28bf5e28aChris Lattner // live variables information so that it knows the copy source 192572c77066808fc0e9ee1d212dab227f28bf5e28aChris Lattner // instruction kills the incoming value. 193572c77066808fc0e9ee1d212dab227f28bf5e28aChris Lattner // 194572c77066808fc0e9ee1d212dab227f28bf5e28aChris Lattner LiveVariables::VarInfo &InRegVI = LV->getVarInfo(SrcReg); 195572c77066808fc0e9ee1d212dab227f28bf5e28aChris Lattner 19608d2e4e09adc53aa93c08c8327d2f5f2814acb74Chris Lattner // Loop over all of the successors of the basic block, checking to see 19708d2e4e09adc53aa93c08c8327d2f5f2814acb74Chris Lattner // if the value is either live in the block, or if it is killed in the 19808d2e4e09adc53aa93c08c8327d2f5f2814acb74Chris Lattner // block. Also check to see if this register is in use by another PHI 19908d2e4e09adc53aa93c08c8327d2f5f2814acb74Chris Lattner // node which has not yet been eliminated. If so, it will be killed 20008d2e4e09adc53aa93c08c8327d2f5f2814acb74Chris Lattner // at an appropriate point later. 201572c77066808fc0e9ee1d212dab227f28bf5e28aChris Lattner // 202572c77066808fc0e9ee1d212dab227f28bf5e28aChris Lattner bool ValueIsLive = false; 203572c77066808fc0e9ee1d212dab227f28bf5e28aChris Lattner BasicBlock *BB = opBlock.getBasicBlock(); 204572c77066808fc0e9ee1d212dab227f28bf5e28aChris Lattner for (succ_iterator SI = succ_begin(BB), E = succ_end(BB); 20508d2e4e09adc53aa93c08c8327d2f5f2814acb74Chris Lattner SI != E && !ValueIsLive; ++SI) { 206572c77066808fc0e9ee1d212dab227f28bf5e28aChris Lattner const std::pair<MachineBasicBlock*, unsigned> & 207572c77066808fc0e9ee1d212dab227f28bf5e28aChris Lattner SuccInfo = LV->getBasicBlockInfo(*SI); 208572c77066808fc0e9ee1d212dab227f28bf5e28aChris Lattner 209572c77066808fc0e9ee1d212dab227f28bf5e28aChris Lattner // Is it alive in this successor? 210572c77066808fc0e9ee1d212dab227f28bf5e28aChris Lattner unsigned SuccIdx = SuccInfo.second; 211572c77066808fc0e9ee1d212dab227f28bf5e28aChris Lattner if (SuccIdx < InRegVI.AliveBlocks.size() && 212572c77066808fc0e9ee1d212dab227f28bf5e28aChris Lattner InRegVI.AliveBlocks[SuccIdx]) { 213572c77066808fc0e9ee1d212dab227f28bf5e28aChris Lattner ValueIsLive = true; 214572c77066808fc0e9ee1d212dab227f28bf5e28aChris Lattner break; 215572c77066808fc0e9ee1d212dab227f28bf5e28aChris Lattner } 216572c77066808fc0e9ee1d212dab227f28bf5e28aChris Lattner 217572c77066808fc0e9ee1d212dab227f28bf5e28aChris Lattner // Is it killed in this successor? 218572c77066808fc0e9ee1d212dab227f28bf5e28aChris Lattner MachineBasicBlock *MBB = SuccInfo.first; 219572c77066808fc0e9ee1d212dab227f28bf5e28aChris Lattner for (unsigned i = 0, e = InRegVI.Kills.size(); i != e; ++i) 220572c77066808fc0e9ee1d212dab227f28bf5e28aChris Lattner if (InRegVI.Kills[i].first == MBB) { 221572c77066808fc0e9ee1d212dab227f28bf5e28aChris Lattner ValueIsLive = true; 222572c77066808fc0e9ee1d212dab227f28bf5e28aChris Lattner break; 223572c77066808fc0e9ee1d212dab227f28bf5e28aChris Lattner } 22408d2e4e09adc53aa93c08c8327d2f5f2814acb74Chris Lattner 22508d2e4e09adc53aa93c08c8327d2f5f2814acb74Chris Lattner // Is it used by any PHI instructions in this block? 22608d2e4e09adc53aa93c08c8327d2f5f2814acb74Chris Lattner if (ValueIsLive) break; 22708d2e4e09adc53aa93c08c8327d2f5f2814acb74Chris Lattner 22808d2e4e09adc53aa93c08c8327d2f5f2814acb74Chris Lattner // Loop over all of the PHIs in this successor, checking to see if 22908d2e4e09adc53aa93c08c8327d2f5f2814acb74Chris Lattner // the register is being used... 23008d2e4e09adc53aa93c08c8327d2f5f2814acb74Chris Lattner for (MachineBasicBlock::iterator BBI = MBB->begin(), E=MBB->end(); 23108d2e4e09adc53aa93c08c8327d2f5f2814acb74Chris Lattner BBI != E && (*BBI)->getOpcode() == TargetInstrInfo::PHI; 23208d2e4e09adc53aa93c08c8327d2f5f2814acb74Chris Lattner ++BBI) 23308d2e4e09adc53aa93c08c8327d2f5f2814acb74Chris Lattner for (unsigned i = 1, e = (*BBI)->getNumOperands(); i < e; i += 2) 23408d2e4e09adc53aa93c08c8327d2f5f2814acb74Chris Lattner if ((*BBI)->getOperand(i).getReg() == SrcReg) { 23508d2e4e09adc53aa93c08c8327d2f5f2814acb74Chris Lattner ValueIsLive = true; 23608d2e4e09adc53aa93c08c8327d2f5f2814acb74Chris Lattner break; 23708d2e4e09adc53aa93c08c8327d2f5f2814acb74Chris Lattner } 238572c77066808fc0e9ee1d212dab227f28bf5e28aChris Lattner } 239572c77066808fc0e9ee1d212dab227f28bf5e28aChris Lattner 240572c77066808fc0e9ee1d212dab227f28bf5e28aChris Lattner // Okay, if we now know that the value is not live out of the block, 241572c77066808fc0e9ee1d212dab227f28bf5e28aChris Lattner // we can add a kill marker to the copy we inserted saying that it 242572c77066808fc0e9ee1d212dab227f28bf5e28aChris Lattner // kills the incoming value! 243572c77066808fc0e9ee1d212dab227f28bf5e28aChris Lattner // 24408d2e4e09adc53aa93c08c8327d2f5f2814acb74Chris Lattner if (!ValueIsLive) 245572c77066808fc0e9ee1d212dab227f28bf5e28aChris Lattner LV->addVirtualRegisterKilled(SrcReg, &opBlock, *(I-1)); 246572c77066808fc0e9ee1d212dab227f28bf5e28aChris Lattner } 247bc40e898e153c9b81f246a7971eaac7b14446c49Chris Lattner } 248bc40e898e153c9b81f246a7971eaac7b14446c49Chris Lattner } 249bc40e898e153c9b81f246a7971eaac7b14446c49Chris Lattner 250bc40e898e153c9b81f246a7971eaac7b14446c49Chris Lattner // really delete the PHI instruction now! 251bc40e898e153c9b81f246a7971eaac7b14446c49Chris Lattner delete MI; 252bc40e898e153c9b81f246a7971eaac7b14446c49Chris Lattner } 253bc40e898e153c9b81f246a7971eaac7b14446c49Chris Lattner 254bc40e898e153c9b81f246a7971eaac7b14446c49Chris Lattner return true; 255bc40e898e153c9b81f246a7971eaac7b14446c49Chris Lattner} 256