PHIElimination.cpp revision 551ccae044b0ff658fe629dd67edd5ffe75d10e8
1bc40e898e153c9b81f246a7971eaac7b14446c49Chris Lattner//===-- PhiElimination.cpp - Eliminate PHI nodes by inserting copies ------===// 2b576c94c15af9a440f69d9d03c2afead7971118cJohn Criswell// 3b576c94c15af9a440f69d9d03c2afead7971118cJohn Criswell// The LLVM Compiler Infrastructure 4b576c94c15af9a440f69d9d03c2afead7971118cJohn Criswell// 5b576c94c15af9a440f69d9d03c2afead7971118cJohn Criswell// This file was developed by the LLVM research group and is distributed under 6b576c94c15af9a440f69d9d03c2afead7971118cJohn Criswell// the University of Illinois Open Source License. See LICENSE.TXT for details. 7b576c94c15af9a440f69d9d03c2afead7971118cJohn Criswell// 8b576c94c15af9a440f69d9d03c2afead7971118cJohn Criswell//===----------------------------------------------------------------------===// 9bc40e898e153c9b81f246a7971eaac7b14446c49Chris Lattner// 10bc40e898e153c9b81f246a7971eaac7b14446c49Chris Lattner// This pass eliminates machine instruction PHI nodes by inserting copy 11bc40e898e153c9b81f246a7971eaac7b14446c49Chris Lattner// instructions. This destroys SSA information, but is the desired input for 12bc40e898e153c9b81f246a7971eaac7b14446c49Chris Lattner// some register allocators. 13bc40e898e153c9b81f246a7971eaac7b14446c49Chris Lattner// 14bc40e898e153c9b81f246a7971eaac7b14446c49Chris Lattner//===----------------------------------------------------------------------===// 15bc40e898e153c9b81f246a7971eaac7b14446c49Chris Lattner 160742b59913a7760eb26f08121cd244a37e83e3b3Chris Lattner#include "llvm/CodeGen/Passes.h" 17bc40e898e153c9b81f246a7971eaac7b14446c49Chris Lattner#include "llvm/CodeGen/MachineFunctionPass.h" 18bc40e898e153c9b81f246a7971eaac7b14446c49Chris Lattner#include "llvm/CodeGen/MachineInstr.h" 19bc40e898e153c9b81f246a7971eaac7b14446c49Chris Lattner#include "llvm/CodeGen/SSARegMap.h" 20bc40e898e153c9b81f246a7971eaac7b14446c49Chris Lattner#include "llvm/CodeGen/LiveVariables.h" 213501feab811c86c9659248a4875fc31a3165f84dChris Lattner#include "llvm/Target/TargetInstrInfo.h" 22bc40e898e153c9b81f246a7971eaac7b14446c49Chris Lattner#include "llvm/Target/TargetMachine.h" 23551ccae044b0ff658fe629dd67edd5ffe75d10e8Reid Spencer#include "llvm/ADT/DenseMap.h" 24551ccae044b0ff658fe629dd67edd5ffe75d10e8Reid Spencer#include "llvm/ADT/STLExtras.h" 250742b59913a7760eb26f08121cd244a37e83e3b3Chris Lattnerusing namespace llvm; 26d0fde30ce850b78371fd1386338350591f9ff494Brian Gaeke 27bc40e898e153c9b81f246a7971eaac7b14446c49Chris Lattnernamespace { 28bc40e898e153c9b81f246a7971eaac7b14446c49Chris Lattner struct PNE : public MachineFunctionPass { 29bc40e898e153c9b81f246a7971eaac7b14446c49Chris Lattner bool runOnMachineFunction(MachineFunction &Fn) { 30bc40e898e153c9b81f246a7971eaac7b14446c49Chris Lattner bool Changed = false; 31bc40e898e153c9b81f246a7971eaac7b14446c49Chris Lattner 32bc40e898e153c9b81f246a7971eaac7b14446c49Chris Lattner // Eliminate PHI instructions by inserting copies into predecessor blocks. 33bc40e898e153c9b81f246a7971eaac7b14446c49Chris Lattner // 34bc40e898e153c9b81f246a7971eaac7b14446c49Chris Lattner for (MachineFunction::iterator I = Fn.begin(), E = Fn.end(); I != E; ++I) 35bc40e898e153c9b81f246a7971eaac7b14446c49Chris Lattner Changed |= EliminatePHINodes(Fn, *I); 36bc40e898e153c9b81f246a7971eaac7b14446c49Chris Lattner 37bc40e898e153c9b81f246a7971eaac7b14446c49Chris Lattner //std::cerr << "AFTER PHI NODE ELIM:\n"; 38bc40e898e153c9b81f246a7971eaac7b14446c49Chris Lattner //Fn.dump(); 39bc40e898e153c9b81f246a7971eaac7b14446c49Chris Lattner return Changed; 40bc40e898e153c9b81f246a7971eaac7b14446c49Chris Lattner } 41bc40e898e153c9b81f246a7971eaac7b14446c49Chris Lattner 42bc40e898e153c9b81f246a7971eaac7b14446c49Chris Lattner virtual void getAnalysisUsage(AnalysisUsage &AU) const { 43bc40e898e153c9b81f246a7971eaac7b14446c49Chris Lattner AU.addPreserved<LiveVariables>(); 44bc40e898e153c9b81f246a7971eaac7b14446c49Chris Lattner MachineFunctionPass::getAnalysisUsage(AU); 45bc40e898e153c9b81f246a7971eaac7b14446c49Chris Lattner } 46bc40e898e153c9b81f246a7971eaac7b14446c49Chris Lattner 47bc40e898e153c9b81f246a7971eaac7b14446c49Chris Lattner private: 48bc40e898e153c9b81f246a7971eaac7b14446c49Chris Lattner /// EliminatePHINodes - Eliminate phi nodes by inserting copy instructions 49bc40e898e153c9b81f246a7971eaac7b14446c49Chris Lattner /// in predecessor basic blocks. 50bc40e898e153c9b81f246a7971eaac7b14446c49Chris Lattner /// 51bc40e898e153c9b81f246a7971eaac7b14446c49Chris Lattner bool EliminatePHINodes(MachineFunction &MF, MachineBasicBlock &MBB); 52bc40e898e153c9b81f246a7971eaac7b14446c49Chris Lattner }; 53bc40e898e153c9b81f246a7971eaac7b14446c49Chris Lattner 54bc40e898e153c9b81f246a7971eaac7b14446c49Chris Lattner RegisterPass<PNE> X("phi-node-elimination", 55bc40e898e153c9b81f246a7971eaac7b14446c49Chris Lattner "Eliminate PHI nodes for register allocation"); 56bc40e898e153c9b81f246a7971eaac7b14446c49Chris Lattner} 57bc40e898e153c9b81f246a7971eaac7b14446c49Chris Lattner 58d0fde30ce850b78371fd1386338350591f9ff494Brian Gaeke 590742b59913a7760eb26f08121cd244a37e83e3b3Chris Lattnerconst PassInfo *llvm::PHIEliminationID = X.getPassInfo(); 60bc40e898e153c9b81f246a7971eaac7b14446c49Chris Lattner 61bc40e898e153c9b81f246a7971eaac7b14446c49Chris Lattner/// EliminatePHINodes - Eliminate phi nodes by inserting copy instructions in 62bc40e898e153c9b81f246a7971eaac7b14446c49Chris Lattner/// predecessor basic blocks. 63bc40e898e153c9b81f246a7971eaac7b14446c49Chris Lattner/// 64bc40e898e153c9b81f246a7971eaac7b14446c49Chris Lattnerbool PNE::EliminatePHINodes(MachineFunction &MF, MachineBasicBlock &MBB) { 65c0b9dc5be79f009d260edb5cd5e1d8346587aaa2Alkis Evlogimenos if (MBB.empty() || MBB.front().getOpcode() != TargetInstrInfo::PHI) 66bc40e898e153c9b81f246a7971eaac7b14446c49Chris Lattner return false; // Quick exit for normal case... 67bc40e898e153c9b81f246a7971eaac7b14446c49Chris Lattner 68bc40e898e153c9b81f246a7971eaac7b14446c49Chris Lattner LiveVariables *LV = getAnalysisToUpdate<LiveVariables>(); 699bcdcd17c7219dbc68de2f11ca2de86471c8c390Chris Lattner const TargetInstrInfo &MII = *MF.getTarget().getInstrInfo(); 70bc40e898e153c9b81f246a7971eaac7b14446c49Chris Lattner const MRegisterInfo *RegInfo = MF.getTarget().getRegisterInfo(); 71bc40e898e153c9b81f246a7971eaac7b14446c49Chris Lattner 7280e20eb487e5e7bc41a7a52d5e985d332c552ef9Chris Lattner // VRegPHIUseCount - Keep track of the number of times each virtual register 73bee887211b603a7e19bf72a4c04e120b47ad82e9Chris Lattner // is used by PHI nodes in successors of this block. 748abf69374e9c34068ddc970817738c0eb24ece2bChris Lattner DenseMap<unsigned, VirtReg2IndexFunctor> VRegPHIUseCount; 758abf69374e9c34068ddc970817738c0eb24ece2bChris Lattner VRegPHIUseCount.grow(MF.getSSARegMap()->getLastVirtReg()); 7680e20eb487e5e7bc41a7a52d5e985d332c552ef9Chris Lattner 77bee887211b603a7e19bf72a4c04e120b47ad82e9Chris Lattner unsigned BBIsSuccOfPreds = 0; // Number of times MBB is a succ of preds 78bee887211b603a7e19bf72a4c04e120b47ad82e9Chris Lattner for (MachineBasicBlock::pred_iterator PI = MBB.pred_begin(), 79bee887211b603a7e19bf72a4c04e120b47ad82e9Chris Lattner E = MBB.pred_end(); PI != E; ++PI) 80bee887211b603a7e19bf72a4c04e120b47ad82e9Chris Lattner for (MachineBasicBlock::succ_iterator SI = (*PI)->succ_begin(), 81bee887211b603a7e19bf72a4c04e120b47ad82e9Chris Lattner E = (*PI)->succ_end(); SI != E; ++SI) { 82bee887211b603a7e19bf72a4c04e120b47ad82e9Chris Lattner BBIsSuccOfPreds += *SI == &MBB; 83bee887211b603a7e19bf72a4c04e120b47ad82e9Chris Lattner for (MachineBasicBlock::iterator BBI = (*SI)->begin(); BBI !=(*SI)->end() && 84bee887211b603a7e19bf72a4c04e120b47ad82e9Chris Lattner BBI->getOpcode() == TargetInstrInfo::PHI; ++BBI) 85bee887211b603a7e19bf72a4c04e120b47ad82e9Chris Lattner for (unsigned i = 1, e = BBI->getNumOperands(); i != e; i += 2) 86bee887211b603a7e19bf72a4c04e120b47ad82e9Chris Lattner VRegPHIUseCount[BBI->getOperand(i).getReg()]++; 87bee887211b603a7e19bf72a4c04e120b47ad82e9Chris Lattner } 88bee887211b603a7e19bf72a4c04e120b47ad82e9Chris Lattner 89791f896d9f8a38b3806878867d61c114069b6195Chris Lattner // Get an iterator to the first instruction after the last PHI node (this may 90bee887211b603a7e19bf72a4c04e120b47ad82e9Chris Lattner // also be the end of the basic block). While we are scanning the PHIs, 9180e20eb487e5e7bc41a7a52d5e985d332c552ef9Chris Lattner // populate the VRegPHIUseCount map. 92791f896d9f8a38b3806878867d61c114069b6195Chris Lattner MachineBasicBlock::iterator AfterPHIsIt = MBB.begin(); 93791f896d9f8a38b3806878867d61c114069b6195Chris Lattner while (AfterPHIsIt != MBB.end() && 94bee887211b603a7e19bf72a4c04e120b47ad82e9Chris Lattner AfterPHIsIt->getOpcode() == TargetInstrInfo::PHI) 95791f896d9f8a38b3806878867d61c114069b6195Chris Lattner ++AfterPHIsIt; // Skip over all of the PHI nodes... 96791f896d9f8a38b3806878867d61c114069b6195Chris Lattner 97c0b9dc5be79f009d260edb5cd5e1d8346587aaa2Alkis Evlogimenos while (MBB.front().getOpcode() == TargetInstrInfo::PHI) { 98a7bfbba856f6fc99803c9a670fd110d7a72f4843Chris Lattner // Unlink the PHI node from the basic block, but don't delete the PHI yet. 99a7bfbba856f6fc99803c9a670fd110d7a72f4843Chris Lattner MachineInstr *MPhi = MBB.remove(MBB.begin()); 100c0b9dc5be79f009d260edb5cd5e1d8346587aaa2Alkis Evlogimenos 101a7bfbba856f6fc99803c9a670fd110d7a72f4843Chris Lattner assert(MRegisterInfo::isVirtualRegister(MPhi->getOperand(0).getReg()) && 102bc40e898e153c9b81f246a7971eaac7b14446c49Chris Lattner "PHI node doesn't write virt reg?"); 103bc40e898e153c9b81f246a7971eaac7b14446c49Chris Lattner 104a7bfbba856f6fc99803c9a670fd110d7a72f4843Chris Lattner unsigned DestReg = MPhi->getOperand(0).getReg(); 105bc40e898e153c9b81f246a7971eaac7b14446c49Chris Lattner 106bc40e898e153c9b81f246a7971eaac7b14446c49Chris Lattner // Create a new register for the incoming PHI arguments 107bc40e898e153c9b81f246a7971eaac7b14446c49Chris Lattner const TargetRegisterClass *RC = MF.getSSARegMap()->getRegClass(DestReg); 108bc40e898e153c9b81f246a7971eaac7b14446c49Chris Lattner unsigned IncomingReg = MF.getSSARegMap()->createVirtualRegister(RC); 109bc40e898e153c9b81f246a7971eaac7b14446c49Chris Lattner 110927ce5dfaea00453889080cd1c6daf3eb197ad74Chris Lattner // Insert a register to register copy in the top of the current block (but 111bc40e898e153c9b81f246a7971eaac7b14446c49Chris Lattner // after any remaining phi nodes) which copies the new incoming register 112bc40e898e153c9b81f246a7971eaac7b14446c49Chris Lattner // into the phi node destination. 113bc40e898e153c9b81f246a7971eaac7b14446c49Chris Lattner // 114bc40e898e153c9b81f246a7971eaac7b14446c49Chris Lattner RegInfo->copyRegToReg(MBB, AfterPHIsIt, DestReg, IncomingReg, RC); 115927ce5dfaea00453889080cd1c6daf3eb197ad74Chris Lattner 116927ce5dfaea00453889080cd1c6daf3eb197ad74Chris Lattner // Update live variable information if there is any... 117927ce5dfaea00453889080cd1c6daf3eb197ad74Chris Lattner if (LV) { 118791f896d9f8a38b3806878867d61c114069b6195Chris Lattner MachineInstr *PHICopy = prior(AfterPHIsIt); 119927ce5dfaea00453889080cd1c6daf3eb197ad74Chris Lattner 120927ce5dfaea00453889080cd1c6daf3eb197ad74Chris Lattner // Add information to LiveVariables to know that the incoming value is 121b52e0241c03a257f96bd9c77788eff5b1a7fd437Chris Lattner // killed. Note that because the value is defined in several places (once 122b52e0241c03a257f96bd9c77788eff5b1a7fd437Chris Lattner // each for each incoming block), the "def" block and instruction fields 123b52e0241c03a257f96bd9c77788eff5b1a7fd437Chris Lattner // for the VarInfo is not filled in. 124927ce5dfaea00453889080cd1c6daf3eb197ad74Chris Lattner // 125472405e0dc05f6fb8c09af00713ff893fff25b94Chris Lattner LV->addVirtualRegisterKilled(IncomingReg, PHICopy); 126bc40e898e153c9b81f246a7971eaac7b14446c49Chris Lattner 127927ce5dfaea00453889080cd1c6daf3eb197ad74Chris Lattner // Since we are going to be deleting the PHI node, if it is the last use 128927ce5dfaea00453889080cd1c6daf3eb197ad74Chris Lattner // of any registers, or if the value itself is dead, we need to move this 129a7bfbba856f6fc99803c9a670fd110d7a72f4843Chris Lattner // information over to the new copy we just inserted. 130927ce5dfaea00453889080cd1c6daf3eb197ad74Chris Lattner // 131927ce5dfaea00453889080cd1c6daf3eb197ad74Chris Lattner std::pair<LiveVariables::killed_iterator, LiveVariables::killed_iterator> 132a7bfbba856f6fc99803c9a670fd110d7a72f4843Chris Lattner RKs = LV->killed_range(MPhi); 133572c77066808fc0e9ee1d212dab227f28bf5e28aChris Lattner std::vector<std::pair<MachineInstr*, unsigned> > Range; 13494881e8c4522e368df38275d28c8ececdd1e171eChris Lattner if (RKs.first != RKs.second) // Delete the range. 135927ce5dfaea00453889080cd1c6daf3eb197ad74Chris Lattner LV->removeVirtualRegistersKilled(RKs.first, RKs.second); 136572c77066808fc0e9ee1d212dab227f28bf5e28aChris Lattner 137a7bfbba856f6fc99803c9a670fd110d7a72f4843Chris Lattner RKs = LV->dead_range(MPhi); 138927ce5dfaea00453889080cd1c6daf3eb197ad74Chris Lattner if (RKs.first != RKs.second) { 139572c77066808fc0e9ee1d212dab227f28bf5e28aChris Lattner // Works as above... 140572c77066808fc0e9ee1d212dab227f28bf5e28aChris Lattner Range.assign(RKs.first, RKs.second); 141927ce5dfaea00453889080cd1c6daf3eb197ad74Chris Lattner LV->removeVirtualRegistersDead(RKs.first, RKs.second); 142572c77066808fc0e9ee1d212dab227f28bf5e28aChris Lattner for (unsigned i = 0, e = Range.size(); i != e; ++i) 143472405e0dc05f6fb8c09af00713ff893fff25b94Chris Lattner LV->addVirtualRegisterDead(Range[i].second, PHICopy); 144927ce5dfaea00453889080cd1c6daf3eb197ad74Chris Lattner } 145927ce5dfaea00453889080cd1c6daf3eb197ad74Chris Lattner } 146bc40e898e153c9b81f246a7971eaac7b14446c49Chris Lattner 14780e20eb487e5e7bc41a7a52d5e985d332c552ef9Chris Lattner // Adjust the VRegPHIUseCount map to account for the removal of this PHI 14880e20eb487e5e7bc41a7a52d5e985d332c552ef9Chris Lattner // node. 149a7bfbba856f6fc99803c9a670fd110d7a72f4843Chris Lattner for (unsigned i = 1; i != MPhi->getNumOperands(); i += 2) 150a7bfbba856f6fc99803c9a670fd110d7a72f4843Chris Lattner VRegPHIUseCount[MPhi->getOperand(i).getReg()] -= BBIsSuccOfPreds; 15180e20eb487e5e7bc41a7a52d5e985d332c552ef9Chris Lattner 152927ce5dfaea00453889080cd1c6daf3eb197ad74Chris Lattner // Now loop over all of the incoming arguments, changing them to copy into 153bc40e898e153c9b81f246a7971eaac7b14446c49Chris Lattner // the IncomingReg register in the corresponding predecessor basic block. 154bc40e898e153c9b81f246a7971eaac7b14446c49Chris Lattner // 155a7bfbba856f6fc99803c9a670fd110d7a72f4843Chris Lattner for (int i = MPhi->getNumOperands() - 1; i >= 2; i-=2) { 156a7bfbba856f6fc99803c9a670fd110d7a72f4843Chris Lattner MachineOperand &opVal = MPhi->getOperand(i-1); 157bc40e898e153c9b81f246a7971eaac7b14446c49Chris Lattner 158bc40e898e153c9b81f246a7971eaac7b14446c49Chris Lattner // Get the MachineBasicBlock equivalent of the BasicBlock that is the 159927ce5dfaea00453889080cd1c6daf3eb197ad74Chris Lattner // source path the PHI. 160a7bfbba856f6fc99803c9a670fd110d7a72f4843Chris Lattner MachineBasicBlock &opBlock = *MPhi->getOperand(i).getMachineBasicBlock(); 161bc40e898e153c9b81f246a7971eaac7b14446c49Chris Lattner 162743d0a1f831f1d5a3141a6ca730558f40c35690aAlkis Evlogimenos MachineBasicBlock::iterator I = opBlock.getFirstTerminator(); 16398719d7cdc693c077d179fe3461ce625d6faef34Chris Lattner 164bc40e898e153c9b81f246a7971eaac7b14446c49Chris Lattner // Check to make sure we haven't already emitted the copy for this block. 165bc40e898e153c9b81f246a7971eaac7b14446c49Chris Lattner // This can happen because PHI nodes may have multiple entries for the 166bc40e898e153c9b81f246a7971eaac7b14446c49Chris Lattner // same basic block. It doesn't matter which entry we use though, because 167bc40e898e153c9b81f246a7971eaac7b14446c49Chris Lattner // all incoming values are guaranteed to be the same for a particular bb. 168bc40e898e153c9b81f246a7971eaac7b14446c49Chris Lattner // 16998719d7cdc693c077d179fe3461ce625d6faef34Chris Lattner // If we emitted a copy for this basic block already, it will be right 17098719d7cdc693c077d179fe3461ce625d6faef34Chris Lattner // where we want to insert one now. Just check for a definition of the 17198719d7cdc693c077d179fe3461ce625d6faef34Chris Lattner // register we are interested in! 172bc40e898e153c9b81f246a7971eaac7b14446c49Chris Lattner // 173bc40e898e153c9b81f246a7971eaac7b14446c49Chris Lattner bool HaveNotEmitted = true; 17498719d7cdc693c077d179fe3461ce625d6faef34Chris Lattner 17598719d7cdc693c077d179fe3461ce625d6faef34Chris Lattner if (I != opBlock.begin()) { 176f81af21caf9c0f62c60b72762d9a927e8c24f679Alkis Evlogimenos MachineBasicBlock::iterator PrevInst = prior(I); 17798719d7cdc693c077d179fe3461ce625d6faef34Chris Lattner for (unsigned i = 0, e = PrevInst->getNumOperands(); i != e; ++i) { 17898719d7cdc693c077d179fe3461ce625d6faef34Chris Lattner MachineOperand &MO = PrevInst->getOperand(i); 1791cbe4d0ad0888e50858cca83cf2a0d3083709513Chris Lattner if (MO.isRegister() && MO.getReg() == IncomingReg) 1804d7af65903cbc858464362e70a6adf499982ec8aAlkis Evlogimenos if (MO.isDef()) { 18198719d7cdc693c077d179fe3461ce625d6faef34Chris Lattner HaveNotEmitted = false; 18298719d7cdc693c077d179fe3461ce625d6faef34Chris Lattner break; 18398719d7cdc693c077d179fe3461ce625d6faef34Chris Lattner } 184bc40e898e153c9b81f246a7971eaac7b14446c49Chris Lattner } 18598719d7cdc693c077d179fe3461ce625d6faef34Chris Lattner } 186bc40e898e153c9b81f246a7971eaac7b14446c49Chris Lattner 187572c77066808fc0e9ee1d212dab227f28bf5e28aChris Lattner if (HaveNotEmitted) { // If the copy has not already been emitted, do it. 1881cbe4d0ad0888e50858cca83cf2a0d3083709513Chris Lattner assert(MRegisterInfo::isVirtualRegister(opVal.getReg()) && 18998719d7cdc693c077d179fe3461ce625d6faef34Chris Lattner "Machine PHI Operands must all be virtual registers!"); 190572c77066808fc0e9ee1d212dab227f28bf5e28aChris Lattner unsigned SrcReg = opVal.getReg(); 191572c77066808fc0e9ee1d212dab227f28bf5e28aChris Lattner RegInfo->copyRegToReg(opBlock, I, IncomingReg, SrcReg, RC); 192572c77066808fc0e9ee1d212dab227f28bf5e28aChris Lattner 193572c77066808fc0e9ee1d212dab227f28bf5e28aChris Lattner // Now update live variable information if we have it. 194572c77066808fc0e9ee1d212dab227f28bf5e28aChris Lattner if (LV) { 195572c77066808fc0e9ee1d212dab227f28bf5e28aChris Lattner // We want to be able to insert a kill of the register if this PHI 196572c77066808fc0e9ee1d212dab227f28bf5e28aChris Lattner // (aka, the copy we just inserted) is the last use of the source 197572c77066808fc0e9ee1d212dab227f28bf5e28aChris Lattner // value. Live variable analysis conservatively handles this by 198572c77066808fc0e9ee1d212dab227f28bf5e28aChris Lattner // saying that the value is live until the end of the block the PHI 199572c77066808fc0e9ee1d212dab227f28bf5e28aChris Lattner // entry lives in. If the value really is dead at the PHI copy, there 200572c77066808fc0e9ee1d212dab227f28bf5e28aChris Lattner // will be no successor blocks which have the value live-in. 201572c77066808fc0e9ee1d212dab227f28bf5e28aChris Lattner // 202572c77066808fc0e9ee1d212dab227f28bf5e28aChris Lattner // Check to see if the copy is the last use, and if so, update the 203572c77066808fc0e9ee1d212dab227f28bf5e28aChris Lattner // live variables information so that it knows the copy source 204572c77066808fc0e9ee1d212dab227f28bf5e28aChris Lattner // instruction kills the incoming value. 205572c77066808fc0e9ee1d212dab227f28bf5e28aChris Lattner // 206572c77066808fc0e9ee1d212dab227f28bf5e28aChris Lattner LiveVariables::VarInfo &InRegVI = LV->getVarInfo(SrcReg); 207572c77066808fc0e9ee1d212dab227f28bf5e28aChris Lattner 20808d2e4e09adc53aa93c08c8327d2f5f2814acb74Chris Lattner // Loop over all of the successors of the basic block, checking to see 20908d2e4e09adc53aa93c08c8327d2f5f2814acb74Chris Lattner // if the value is either live in the block, or if it is killed in the 21008d2e4e09adc53aa93c08c8327d2f5f2814acb74Chris Lattner // block. Also check to see if this register is in use by another PHI 21108d2e4e09adc53aa93c08c8327d2f5f2814acb74Chris Lattner // node which has not yet been eliminated. If so, it will be killed 21208d2e4e09adc53aa93c08c8327d2f5f2814acb74Chris Lattner // at an appropriate point later. 213572c77066808fc0e9ee1d212dab227f28bf5e28aChris Lattner // 214572c77066808fc0e9ee1d212dab227f28bf5e28aChris Lattner bool ValueIsLive = false; 215015959ee38e4fd4a920f6b0065c50e524762f580Chris Lattner for (MachineBasicBlock::succ_iterator SI = opBlock.succ_begin(), 216015959ee38e4fd4a920f6b0065c50e524762f580Chris Lattner E = opBlock.succ_end(); SI != E && !ValueIsLive; ++SI) { 217bee887211b603a7e19bf72a4c04e120b47ad82e9Chris Lattner MachineBasicBlock *SuccMBB = *SI; 218572c77066808fc0e9ee1d212dab227f28bf5e28aChris Lattner 219572c77066808fc0e9ee1d212dab227f28bf5e28aChris Lattner // Is it alive in this successor? 2208ba9771549bcff6109ad45ff3944a1b6c3c54b46Chris Lattner unsigned SuccIdx = SuccMBB->getNumber(); 221572c77066808fc0e9ee1d212dab227f28bf5e28aChris Lattner if (SuccIdx < InRegVI.AliveBlocks.size() && 222572c77066808fc0e9ee1d212dab227f28bf5e28aChris Lattner InRegVI.AliveBlocks[SuccIdx]) { 223572c77066808fc0e9ee1d212dab227f28bf5e28aChris Lattner ValueIsLive = true; 224572c77066808fc0e9ee1d212dab227f28bf5e28aChris Lattner break; 225572c77066808fc0e9ee1d212dab227f28bf5e28aChris Lattner } 226572c77066808fc0e9ee1d212dab227f28bf5e28aChris Lattner 227572c77066808fc0e9ee1d212dab227f28bf5e28aChris Lattner // Is it killed in this successor? 228572c77066808fc0e9ee1d212dab227f28bf5e28aChris Lattner for (unsigned i = 0, e = InRegVI.Kills.size(); i != e; ++i) 22974de8b1b26b12fda3364382946e519a2e37b6709Chris Lattner if (InRegVI.Kills[i]->getParent() == SuccMBB) { 230572c77066808fc0e9ee1d212dab227f28bf5e28aChris Lattner ValueIsLive = true; 231572c77066808fc0e9ee1d212dab227f28bf5e28aChris Lattner break; 232572c77066808fc0e9ee1d212dab227f28bf5e28aChris Lattner } 23308d2e4e09adc53aa93c08c8327d2f5f2814acb74Chris Lattner 23408d2e4e09adc53aa93c08c8327d2f5f2814acb74Chris Lattner // Is it used by any PHI instructions in this block? 2358abf69374e9c34068ddc970817738c0eb24ece2bChris Lattner if (!ValueIsLive) 2368abf69374e9c34068ddc970817738c0eb24ece2bChris Lattner ValueIsLive = VRegPHIUseCount[SrcReg] != 0; 237572c77066808fc0e9ee1d212dab227f28bf5e28aChris Lattner } 238572c77066808fc0e9ee1d212dab227f28bf5e28aChris Lattner 239572c77066808fc0e9ee1d212dab227f28bf5e28aChris Lattner // Okay, if we now know that the value is not live out of the block, 240572c77066808fc0e9ee1d212dab227f28bf5e28aChris Lattner // we can add a kill marker to the copy we inserted saying that it 241572c77066808fc0e9ee1d212dab227f28bf5e28aChris Lattner // kills the incoming value! 242572c77066808fc0e9ee1d212dab227f28bf5e28aChris Lattner // 243c0b9dc5be79f009d260edb5cd5e1d8346587aaa2Alkis Evlogimenos if (!ValueIsLive) { 244f81af21caf9c0f62c60b72762d9a927e8c24f679Alkis Evlogimenos MachineBasicBlock::iterator Prev = prior(I); 245472405e0dc05f6fb8c09af00713ff893fff25b94Chris Lattner LV->addVirtualRegisterKilled(SrcReg, Prev); 24694881e8c4522e368df38275d28c8ececdd1e171eChris Lattner 24794881e8c4522e368df38275d28c8ececdd1e171eChris Lattner // This vreg no longer lives all of the way through opBlock. 24894881e8c4522e368df38275d28c8ececdd1e171eChris Lattner unsigned opBlockNum = opBlock.getNumber(); 24994881e8c4522e368df38275d28c8ececdd1e171eChris Lattner if (opBlockNum < InRegVI.AliveBlocks.size()) 25094881e8c4522e368df38275d28c8ececdd1e171eChris Lattner InRegVI.AliveBlocks[opBlockNum] = false; 251c0b9dc5be79f009d260edb5cd5e1d8346587aaa2Alkis Evlogimenos } 252572c77066808fc0e9ee1d212dab227f28bf5e28aChris Lattner } 253bc40e898e153c9b81f246a7971eaac7b14446c49Chris Lattner } 254bc40e898e153c9b81f246a7971eaac7b14446c49Chris Lattner } 255bc40e898e153c9b81f246a7971eaac7b14446c49Chris Lattner 256a7bfbba856f6fc99803c9a670fd110d7a72f4843Chris Lattner // Really delete the PHI instruction now! 257a7bfbba856f6fc99803c9a670fd110d7a72f4843Chris Lattner delete MPhi; 258bc40e898e153c9b81f246a7971eaac7b14446c49Chris Lattner } 259bc40e898e153c9b81f246a7971eaac7b14446c49Chris Lattner return true; 260bc40e898e153c9b81f246a7971eaac7b14446c49Chris Lattner} 261