PHIElimination.cpp revision 67d65bb69d5cad957cbb6d672dc0b4a19c211a42
1bc40e898e153c9b81f246a7971eaac7b14446c49Chris Lattner//===-- PhiElimination.cpp - Eliminate PHI nodes by inserting copies ------===// 2edf128a7fa90f2b0b7ee24741a04a7ae1ecd6f7eMisha Brukman// 3b576c94c15af9a440f69d9d03c2afead7971118cJohn Criswell// The LLVM Compiler Infrastructure 4b576c94c15af9a440f69d9d03c2afead7971118cJohn Criswell// 54ee451de366474b9c228b4e5fa573795a715216dChris Lattner// This file is distributed under the University of Illinois Open Source 64ee451de366474b9c228b4e5fa573795a715216dChris Lattner// License. See LICENSE.TXT for details. 7edf128a7fa90f2b0b7ee24741a04a7ae1ecd6f7eMisha Brukman// 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 16cd3245ac45c595da96bb768a55cddc356dff55feChris Lattner#define DEBUG_TYPE "phielim" 17d7a10c8566c1f2e979f8f3abcaab441297a0c44cMisha Brukman#include "llvm/CodeGen/LiveVariables.h" 180742b59913a7760eb26f08121cd244a37e83e3b3Chris Lattner#include "llvm/CodeGen/Passes.h" 19bc40e898e153c9b81f246a7971eaac7b14446c49Chris Lattner#include "llvm/CodeGen/MachineFunctionPass.h" 20bc40e898e153c9b81f246a7971eaac7b14446c49Chris Lattner#include "llvm/CodeGen/MachineInstr.h" 2184bc5427d6883f73cfeae3da640acd011d35c006Chris Lattner#include "llvm/CodeGen/MachineRegisterInfo.h" 223501feab811c86c9659248a4875fc31a3165f84dChris Lattner#include "llvm/Target/TargetInstrInfo.h" 23bc40e898e153c9b81f246a7971eaac7b14446c49Chris Lattner#include "llvm/Target/TargetMachine.h" 24551ccae044b0ff658fe629dd67edd5ffe75d10e8Reid Spencer#include "llvm/ADT/STLExtras.h" 256db0756f021a7b9c84d3bb7ae50498feb080a013Chris Lattner#include "llvm/ADT/Statistic.h" 26a4f0b3a084d120cfc5b5bb06f64b222f5cb72740Chris Lattner#include "llvm/Support/Compiler.h" 2753a79aaae988d9dc9d12af8970f8b8fe58cc478dChris Lattner#include <set> 286db0756f021a7b9c84d3bb7ae50498feb080a013Chris Lattner#include <algorithm> 290742b59913a7760eb26f08121cd244a37e83e3b3Chris Lattnerusing namespace llvm; 30d0fde30ce850b78371fd1386338350591f9ff494Brian Gaeke 31cd3245ac45c595da96bb768a55cddc356dff55feChris LattnerSTATISTIC(NumAtomic, "Number of atomic phis lowered"); 32cd3245ac45c595da96bb768a55cddc356dff55feChris Lattner//STATISTIC(NumSimple, "Number of simple phis lowered"); 33cd3245ac45c595da96bb768a55cddc356dff55feChris Lattner 34bc40e898e153c9b81f246a7971eaac7b14446c49Chris Lattnernamespace { 359525528a7dc5462b6374d38c81ba5c07b11741feChris Lattner struct VISIBILITY_HIDDEN PNE : public MachineFunctionPass { 36ecd94c804a563f2a86572dcf1d2e81f397e19daaNick Lewycky static char ID; // Pass identification, replacement for typeid 37794fd75c67a2cdc128d67342c6d88a504d186896Devang Patel PNE() : MachineFunctionPass((intptr_t)&ID) {} 38794fd75c67a2cdc128d67342c6d88a504d186896Devang Patel 39bc40e898e153c9b81f246a7971eaac7b14446c49Chris Lattner bool runOnMachineFunction(MachineFunction &Fn) { 40ca756d2cf9bd88f210d61dd5f9776920a6178441Bill Wendling analyzePHINodes(Fn); 41ca756d2cf9bd88f210d61dd5f9776920a6178441Bill Wendling 42bc40e898e153c9b81f246a7971eaac7b14446c49Chris Lattner bool Changed = false; 43bc40e898e153c9b81f246a7971eaac7b14446c49Chris Lattner 44bc40e898e153c9b81f246a7971eaac7b14446c49Chris Lattner // Eliminate PHI instructions by inserting copies into predecessor blocks. 45bc40e898e153c9b81f246a7971eaac7b14446c49Chris Lattner for (MachineFunction::iterator I = Fn.begin(), E = Fn.end(); I != E; ++I) 46dedf2bd5a34dac25e4245f58bb902ced6b64edd9Misha Brukman Changed |= EliminatePHINodes(Fn, *I); 47bc40e898e153c9b81f246a7971eaac7b14446c49Chris Lattner 48ca756d2cf9bd88f210d61dd5f9776920a6178441Bill Wendling VRegPHIUseCount.clear(); 49bc40e898e153c9b81f246a7971eaac7b14446c49Chris Lattner return Changed; 50bc40e898e153c9b81f246a7971eaac7b14446c49Chris Lattner } 51bc40e898e153c9b81f246a7971eaac7b14446c49Chris Lattner 52bc40e898e153c9b81f246a7971eaac7b14446c49Chris Lattner virtual void getAnalysisUsage(AnalysisUsage &AU) const { 53bc40e898e153c9b81f246a7971eaac7b14446c49Chris Lattner AU.addPreserved<LiveVariables>(); 5467d65bb69d5cad957cbb6d672dc0b4a19c211a42Bill Wendling AU.addPreservedID(MachineLoopInfoID); 5567d65bb69d5cad957cbb6d672dc0b4a19c211a42Bill Wendling AU.addPreservedID(MachineDominatorsID); 56bc40e898e153c9b81f246a7971eaac7b14446c49Chris Lattner MachineFunctionPass::getAnalysisUsage(AU); 57bc40e898e153c9b81f246a7971eaac7b14446c49Chris Lattner } 58bc40e898e153c9b81f246a7971eaac7b14446c49Chris Lattner 59bc40e898e153c9b81f246a7971eaac7b14446c49Chris Lattner private: 60bc40e898e153c9b81f246a7971eaac7b14446c49Chris Lattner /// EliminatePHINodes - Eliminate phi nodes by inserting copy instructions 61bc40e898e153c9b81f246a7971eaac7b14446c49Chris Lattner /// in predecessor basic blocks. 62bc40e898e153c9b81f246a7971eaac7b14446c49Chris Lattner /// 63bc40e898e153c9b81f246a7971eaac7b14446c49Chris Lattner bool EliminatePHINodes(MachineFunction &MF, MachineBasicBlock &MBB); 6453a79aaae988d9dc9d12af8970f8b8fe58cc478dChris Lattner void LowerAtomicPHINode(MachineBasicBlock &MBB, 65ca756d2cf9bd88f210d61dd5f9776920a6178441Bill Wendling MachineBasicBlock::iterator AfterPHIsIt); 66ca756d2cf9bd88f210d61dd5f9776920a6178441Bill Wendling 67ca756d2cf9bd88f210d61dd5f9776920a6178441Bill Wendling /// analyzePHINodes - Gather information about the PHI nodes in 68ca756d2cf9bd88f210d61dd5f9776920a6178441Bill Wendling /// here. In particular, we want to map the number of uses of a virtual 69ca756d2cf9bd88f210d61dd5f9776920a6178441Bill Wendling /// register which is used in a PHI node. We map that to the BB the 70ca756d2cf9bd88f210d61dd5f9776920a6178441Bill Wendling /// vreg is coming from. This is used later to determine when the vreg 71ca756d2cf9bd88f210d61dd5f9776920a6178441Bill Wendling /// is killed in the BB. 72ca756d2cf9bd88f210d61dd5f9776920a6178441Bill Wendling /// 73ca756d2cf9bd88f210d61dd5f9776920a6178441Bill Wendling void analyzePHINodes(const MachineFunction& Fn); 74ca756d2cf9bd88f210d61dd5f9776920a6178441Bill Wendling 75ca756d2cf9bd88f210d61dd5f9776920a6178441Bill Wendling typedef std::pair<const MachineBasicBlock*, unsigned> BBVRegPair; 76ca756d2cf9bd88f210d61dd5f9776920a6178441Bill Wendling typedef std::map<BBVRegPair, unsigned> VRegPHIUse; 77ca756d2cf9bd88f210d61dd5f9776920a6178441Bill Wendling 78ca756d2cf9bd88f210d61dd5f9776920a6178441Bill Wendling VRegPHIUse VRegPHIUseCount; 79bc40e898e153c9b81f246a7971eaac7b14446c49Chris Lattner }; 80bc40e898e153c9b81f246a7971eaac7b14446c49Chris Lattner 811997473cf72957d0e70322e2fe6fe2ab141c58a6Devang Patel char PNE::ID = 0; 82bc40e898e153c9b81f246a7971eaac7b14446c49Chris Lattner RegisterPass<PNE> X("phi-node-elimination", 83dedf2bd5a34dac25e4245f58bb902ced6b64edd9Misha Brukman "Eliminate PHI nodes for register allocation"); 84bc40e898e153c9b81f246a7971eaac7b14446c49Chris Lattner} 85bc40e898e153c9b81f246a7971eaac7b14446c49Chris Lattner 860742b59913a7760eb26f08121cd244a37e83e3b3Chris Lattnerconst PassInfo *llvm::PHIEliminationID = X.getPassInfo(); 87bc40e898e153c9b81f246a7971eaac7b14446c49Chris Lattner 88bc40e898e153c9b81f246a7971eaac7b14446c49Chris Lattner/// EliminatePHINodes - Eliminate phi nodes by inserting copy instructions in 89bc40e898e153c9b81f246a7971eaac7b14446c49Chris Lattner/// predecessor basic blocks. 90bc40e898e153c9b81f246a7971eaac7b14446c49Chris Lattner/// 91bc40e898e153c9b81f246a7971eaac7b14446c49Chris Lattnerbool PNE::EliminatePHINodes(MachineFunction &MF, MachineBasicBlock &MBB) { 92c0b9dc5be79f009d260edb5cd5e1d8346587aaa2Alkis Evlogimenos if (MBB.empty() || MBB.front().getOpcode() != TargetInstrInfo::PHI) 9353a79aaae988d9dc9d12af8970f8b8fe58cc478dChris Lattner return false; // Quick exit for basic blocks without PHIs. 94bc40e898e153c9b81f246a7971eaac7b14446c49Chris Lattner 95791f896d9f8a38b3806878867d61c114069b6195Chris Lattner // Get an iterator to the first instruction after the last PHI node (this may 9653a79aaae988d9dc9d12af8970f8b8fe58cc478dChris Lattner // also be the end of the basic block). 97791f896d9f8a38b3806878867d61c114069b6195Chris Lattner MachineBasicBlock::iterator AfterPHIsIt = MBB.begin(); 98791f896d9f8a38b3806878867d61c114069b6195Chris Lattner while (AfterPHIsIt != MBB.end() && 99bee887211b603a7e19bf72a4c04e120b47ad82e9Chris Lattner AfterPHIsIt->getOpcode() == TargetInstrInfo::PHI) 100791f896d9f8a38b3806878867d61c114069b6195Chris Lattner ++AfterPHIsIt; // Skip over all of the PHI nodes... 101791f896d9f8a38b3806878867d61c114069b6195Chris Lattner 102ca756d2cf9bd88f210d61dd5f9776920a6178441Bill Wendling while (MBB.front().getOpcode() == TargetInstrInfo::PHI) 103ca756d2cf9bd88f210d61dd5f9776920a6178441Bill Wendling LowerAtomicPHINode(MBB, AfterPHIsIt); 104ca756d2cf9bd88f210d61dd5f9776920a6178441Bill Wendling 10553a79aaae988d9dc9d12af8970f8b8fe58cc478dChris Lattner return true; 10653a79aaae988d9dc9d12af8970f8b8fe58cc478dChris Lattner} 107edf128a7fa90f2b0b7ee24741a04a7ae1ecd6f7eMisha Brukman 1082adfa7e9320e79859beb556367ea607a329866b3Chris Lattner/// InstructionUsesRegister - Return true if the specified machine instr has a 1092adfa7e9320e79859beb556367ea607a329866b3Chris Lattner/// use of the specified register. 1102adfa7e9320e79859beb556367ea607a329866b3Chris Lattnerstatic bool InstructionUsesRegister(MachineInstr *MI, unsigned SrcReg) { 1112adfa7e9320e79859beb556367ea607a329866b3Chris Lattner for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) 112103de7785aaf7375460adac32c63335a24fc440dChris Lattner if (MI->getOperand(i).isRegister() && 113103de7785aaf7375460adac32c63335a24fc440dChris Lattner MI->getOperand(i).getReg() == SrcReg && 114103de7785aaf7375460adac32c63335a24fc440dChris Lattner MI->getOperand(i).isUse()) 1152adfa7e9320e79859beb556367ea607a329866b3Chris Lattner return true; 1162adfa7e9320e79859beb556367ea607a329866b3Chris Lattner return false; 1172adfa7e9320e79859beb556367ea607a329866b3Chris Lattner} 1182adfa7e9320e79859beb556367ea607a329866b3Chris Lattner 11953a79aaae988d9dc9d12af8970f8b8fe58cc478dChris Lattner/// LowerAtomicPHINode - Lower the PHI node at the top of the specified block, 12053a79aaae988d9dc9d12af8970f8b8fe58cc478dChris Lattner/// under the assuption that it needs to be lowered in a way that supports 12153a79aaae988d9dc9d12af8970f8b8fe58cc478dChris Lattner/// atomic execution of PHIs. This lowering method is always correct all of the 12253a79aaae988d9dc9d12af8970f8b8fe58cc478dChris Lattner/// time. 12353a79aaae988d9dc9d12af8970f8b8fe58cc478dChris Lattnervoid PNE::LowerAtomicPHINode(MachineBasicBlock &MBB, 124ca756d2cf9bd88f210d61dd5f9776920a6178441Bill Wendling MachineBasicBlock::iterator AfterPHIsIt) { 12553a79aaae988d9dc9d12af8970f8b8fe58cc478dChris Lattner // Unlink the PHI node from the basic block, but don't delete the PHI yet. 12653a79aaae988d9dc9d12af8970f8b8fe58cc478dChris Lattner MachineInstr *MPhi = MBB.remove(MBB.begin()); 12753a79aaae988d9dc9d12af8970f8b8fe58cc478dChris Lattner 12853a79aaae988d9dc9d12af8970f8b8fe58cc478dChris Lattner unsigned DestReg = MPhi->getOperand(0).getReg(); 12953a79aaae988d9dc9d12af8970f8b8fe58cc478dChris Lattner 130ca756d2cf9bd88f210d61dd5f9776920a6178441Bill Wendling // Create a new register for the incoming PHI arguments. 13153a79aaae988d9dc9d12af8970f8b8fe58cc478dChris Lattner MachineFunction &MF = *MBB.getParent(); 13284bc5427d6883f73cfeae3da640acd011d35c006Chris Lattner const TargetRegisterClass *RC = MF.getRegInfo().getRegClass(DestReg); 13384bc5427d6883f73cfeae3da640acd011d35c006Chris Lattner unsigned IncomingReg = MF.getRegInfo().createVirtualRegister(RC); 13453a79aaae988d9dc9d12af8970f8b8fe58cc478dChris Lattner 13553a79aaae988d9dc9d12af8970f8b8fe58cc478dChris Lattner // Insert a register to register copy in the top of the current block (but 13653a79aaae988d9dc9d12af8970f8b8fe58cc478dChris Lattner // after any remaining phi nodes) which copies the new incoming register 13753a79aaae988d9dc9d12af8970f8b8fe58cc478dChris Lattner // into the phi node destination. 13853a79aaae988d9dc9d12af8970f8b8fe58cc478dChris Lattner // 139d10fd9791c20fd8368fa0ce94b626b769c6c8ba0Owen Anderson const TargetInstrInfo *TII = MF.getTarget().getInstrInfo(); 140d10fd9791c20fd8368fa0ce94b626b769c6c8ba0Owen Anderson TII->copyRegToReg(MBB, AfterPHIsIt, DestReg, IncomingReg, RC, RC); 141bc40e898e153c9b81f246a7971eaac7b14446c49Chris Lattner 14253a79aaae988d9dc9d12af8970f8b8fe58cc478dChris Lattner // Update live variable information if there is any... 14353a79aaae988d9dc9d12af8970f8b8fe58cc478dChris Lattner LiveVariables *LV = getAnalysisToUpdate<LiveVariables>(); 14453a79aaae988d9dc9d12af8970f8b8fe58cc478dChris Lattner if (LV) { 14553a79aaae988d9dc9d12af8970f8b8fe58cc478dChris Lattner MachineInstr *PHICopy = prior(AfterPHIsIt); 146edf128a7fa90f2b0b7ee24741a04a7ae1ecd6f7eMisha Brukman 1473fefc182a00663bfadbcbe17711b6d08469c9727Evan Cheng // Increment use count of the newly created virtual register. 1483fefc182a00663bfadbcbe17711b6d08469c9727Evan Cheng LV->getVarInfo(IncomingReg).NumUses++; 1493fefc182a00663bfadbcbe17711b6d08469c9727Evan Cheng 15053a79aaae988d9dc9d12af8970f8b8fe58cc478dChris Lattner // Add information to LiveVariables to know that the incoming value is 15153a79aaae988d9dc9d12af8970f8b8fe58cc478dChris Lattner // killed. Note that because the value is defined in several places (once 15253a79aaae988d9dc9d12af8970f8b8fe58cc478dChris Lattner // each for each incoming block), the "def" block and instruction fields 15353a79aaae988d9dc9d12af8970f8b8fe58cc478dChris Lattner // for the VarInfo is not filled in. 15453a79aaae988d9dc9d12af8970f8b8fe58cc478dChris Lattner // 15553a79aaae988d9dc9d12af8970f8b8fe58cc478dChris Lattner LV->addVirtualRegisterKilled(IncomingReg, PHICopy); 156bc40e898e153c9b81f246a7971eaac7b14446c49Chris Lattner 15753a79aaae988d9dc9d12af8970f8b8fe58cc478dChris Lattner // Since we are going to be deleting the PHI node, if it is the last use 15853a79aaae988d9dc9d12af8970f8b8fe58cc478dChris Lattner // of any registers, or if the value itself is dead, we need to move this 15953a79aaae988d9dc9d12af8970f8b8fe58cc478dChris Lattner // information over to the new copy we just inserted. 160bc40e898e153c9b81f246a7971eaac7b14446c49Chris Lattner // 16153a79aaae988d9dc9d12af8970f8b8fe58cc478dChris Lattner LV->removeVirtualRegistersKilled(MPhi); 16253a79aaae988d9dc9d12af8970f8b8fe58cc478dChris Lattner 1636db0756f021a7b9c84d3bb7ae50498feb080a013Chris Lattner // If the result is dead, update LV. 1646db0756f021a7b9c84d3bb7ae50498feb080a013Chris Lattner if (LV->RegisterDefIsDead(MPhi, DestReg)) { 1656db0756f021a7b9c84d3bb7ae50498feb080a013Chris Lattner LV->addVirtualRegisterDead(DestReg, PHICopy); 16653a79aaae988d9dc9d12af8970f8b8fe58cc478dChris Lattner LV->removeVirtualRegistersDead(MPhi); 167927ce5dfaea00453889080cd1c6daf3eb197ad74Chris Lattner } 168172c362fefe3d6e762ada119d4084ed4ed31595bChris Lattner 169172c362fefe3d6e762ada119d4084ed4ed31595bChris Lattner // Realize that the destination register is defined by the PHI copy now, not 170172c362fefe3d6e762ada119d4084ed4ed31595bChris Lattner // the PHI itself. 171172c362fefe3d6e762ada119d4084ed4ed31595bChris Lattner LV->getVarInfo(DestReg).DefInst = PHICopy; 172a018540807775703d630e9c92f9d8013d545599eOwen Anderson 173a018540807775703d630e9c92f9d8013d545599eOwen Anderson LV->getVarInfo(IncomingReg).UsedBlocks[MBB.getNumber()] = true; 17453a79aaae988d9dc9d12af8970f8b8fe58cc478dChris Lattner } 17553a79aaae988d9dc9d12af8970f8b8fe58cc478dChris Lattner 17653a79aaae988d9dc9d12af8970f8b8fe58cc478dChris Lattner // Adjust the VRegPHIUseCount map to account for the removal of this PHI 17753a79aaae988d9dc9d12af8970f8b8fe58cc478dChris Lattner // node. 17853a79aaae988d9dc9d12af8970f8b8fe58cc478dChris Lattner for (unsigned i = 1; i != MPhi->getNumOperands(); i += 2) 1798aa797aa51cd4ea1ec6f46f4891a6897944b75b2Chris Lattner --VRegPHIUseCount[BBVRegPair(MPhi->getOperand(i + 1).getMBB(), 1808aa797aa51cd4ea1ec6f46f4891a6897944b75b2Chris Lattner MPhi->getOperand(i).getReg())]; 18153a79aaae988d9dc9d12af8970f8b8fe58cc478dChris Lattner 18253a79aaae988d9dc9d12af8970f8b8fe58cc478dChris Lattner // Now loop over all of the incoming arguments, changing them to copy into 18353a79aaae988d9dc9d12af8970f8b8fe58cc478dChris Lattner // the IncomingReg register in the corresponding predecessor basic block. 18453a79aaae988d9dc9d12af8970f8b8fe58cc478dChris Lattner // 1856db0756f021a7b9c84d3bb7ae50498feb080a013Chris Lattner std::set<MachineBasicBlock*> MBBsInsertedInto; 18653a79aaae988d9dc9d12af8970f8b8fe58cc478dChris Lattner for (int i = MPhi->getNumOperands() - 1; i >= 2; i-=2) { 1876db0756f021a7b9c84d3bb7ae50498feb080a013Chris Lattner unsigned SrcReg = MPhi->getOperand(i-1).getReg(); 1886db0756f021a7b9c84d3bb7ae50498feb080a013Chris Lattner assert(MRegisterInfo::isVirtualRegister(SrcReg) && 1896db0756f021a7b9c84d3bb7ae50498feb080a013Chris Lattner "Machine PHI Operands must all be virtual registers!"); 19053a79aaae988d9dc9d12af8970f8b8fe58cc478dChris Lattner 19153a79aaae988d9dc9d12af8970f8b8fe58cc478dChris Lattner // Get the MachineBasicBlock equivalent of the BasicBlock that is the 19253a79aaae988d9dc9d12af8970f8b8fe58cc478dChris Lattner // source path the PHI. 1938aa797aa51cd4ea1ec6f46f4891a6897944b75b2Chris Lattner MachineBasicBlock &opBlock = *MPhi->getOperand(i).getMBB(); 194bc40e898e153c9b81f246a7971eaac7b14446c49Chris Lattner 19553a79aaae988d9dc9d12af8970f8b8fe58cc478dChris Lattner // Check to make sure we haven't already emitted the copy for this block. 19653a79aaae988d9dc9d12af8970f8b8fe58cc478dChris Lattner // This can happen because PHI nodes may have multiple entries for the 1976db0756f021a7b9c84d3bb7ae50498feb080a013Chris Lattner // same basic block. 1986db0756f021a7b9c84d3bb7ae50498feb080a013Chris Lattner if (!MBBsInsertedInto.insert(&opBlock).second) 1996db0756f021a7b9c84d3bb7ae50498feb080a013Chris Lattner continue; // If the copy has already been emitted, we're done. 2006db0756f021a7b9c84d3bb7ae50498feb080a013Chris Lattner 2016db0756f021a7b9c84d3bb7ae50498feb080a013Chris Lattner // Get an iterator pointing to the first terminator in the block (or end()). 2026db0756f021a7b9c84d3bb7ae50498feb080a013Chris Lattner // This is the point where we can insert a copy if we'd like to. 2036db0756f021a7b9c84d3bb7ae50498feb080a013Chris Lattner MachineBasicBlock::iterator I = opBlock.getFirstTerminator(); 2046db0756f021a7b9c84d3bb7ae50498feb080a013Chris Lattner 2056db0756f021a7b9c84d3bb7ae50498feb080a013Chris Lattner // Insert the copy. 206d10fd9791c20fd8368fa0ce94b626b769c6c8ba0Owen Anderson TII->copyRegToReg(opBlock, I, IncomingReg, SrcReg, RC, RC); 2076db0756f021a7b9c84d3bb7ae50498feb080a013Chris Lattner 2086db0756f021a7b9c84d3bb7ae50498feb080a013Chris Lattner // Now update live variable information if we have it. Otherwise we're done 2096db0756f021a7b9c84d3bb7ae50498feb080a013Chris Lattner if (!LV) continue; 2106db0756f021a7b9c84d3bb7ae50498feb080a013Chris Lattner 2116db0756f021a7b9c84d3bb7ae50498feb080a013Chris Lattner // We want to be able to insert a kill of the register if this PHI 2126db0756f021a7b9c84d3bb7ae50498feb080a013Chris Lattner // (aka, the copy we just inserted) is the last use of the source 2136db0756f021a7b9c84d3bb7ae50498feb080a013Chris Lattner // value. Live variable analysis conservatively handles this by 2146db0756f021a7b9c84d3bb7ae50498feb080a013Chris Lattner // saying that the value is live until the end of the block the PHI 2156db0756f021a7b9c84d3bb7ae50498feb080a013Chris Lattner // entry lives in. If the value really is dead at the PHI copy, there 2166db0756f021a7b9c84d3bb7ae50498feb080a013Chris Lattner // will be no successor blocks which have the value live-in. 217bc40e898e153c9b81f246a7971eaac7b14446c49Chris Lattner // 2186db0756f021a7b9c84d3bb7ae50498feb080a013Chris Lattner // Check to see if the copy is the last use, and if so, update the 2196db0756f021a7b9c84d3bb7ae50498feb080a013Chris Lattner // live variables information so that it knows the copy source 2206db0756f021a7b9c84d3bb7ae50498feb080a013Chris Lattner // instruction kills the incoming value. 22153a79aaae988d9dc9d12af8970f8b8fe58cc478dChris Lattner // 2226db0756f021a7b9c84d3bb7ae50498feb080a013Chris Lattner LiveVariables::VarInfo &InRegVI = LV->getVarInfo(SrcReg); 223a018540807775703d630e9c92f9d8013d545599eOwen Anderson InRegVI.UsedBlocks[opBlock.getNumber()] = true; 2246db0756f021a7b9c84d3bb7ae50498feb080a013Chris Lattner 2256db0756f021a7b9c84d3bb7ae50498feb080a013Chris Lattner // Loop over all of the successors of the basic block, checking to see 2266db0756f021a7b9c84d3bb7ae50498feb080a013Chris Lattner // if the value is either live in the block, or if it is killed in the 2276db0756f021a7b9c84d3bb7ae50498feb080a013Chris Lattner // block. Also check to see if this register is in use by another PHI 2286db0756f021a7b9c84d3bb7ae50498feb080a013Chris Lattner // node which has not yet been eliminated. If so, it will be killed 2296db0756f021a7b9c84d3bb7ae50498feb080a013Chris Lattner // at an appropriate point later. 2306db0756f021a7b9c84d3bb7ae50498feb080a013Chris Lattner // 2316db0756f021a7b9c84d3bb7ae50498feb080a013Chris Lattner 2326db0756f021a7b9c84d3bb7ae50498feb080a013Chris Lattner // Is it used by any PHI instructions in this block? 233ca756d2cf9bd88f210d61dd5f9776920a6178441Bill Wendling bool ValueIsLive = VRegPHIUseCount[BBVRegPair(&opBlock, SrcReg)] != 0; 2346db0756f021a7b9c84d3bb7ae50498feb080a013Chris Lattner 2356db0756f021a7b9c84d3bb7ae50498feb080a013Chris Lattner std::vector<MachineBasicBlock*> OpSuccBlocks; 2366db0756f021a7b9c84d3bb7ae50498feb080a013Chris Lattner 2376db0756f021a7b9c84d3bb7ae50498feb080a013Chris Lattner // Otherwise, scan successors, including the BB the PHI node lives in. 2386db0756f021a7b9c84d3bb7ae50498feb080a013Chris Lattner for (MachineBasicBlock::succ_iterator SI = opBlock.succ_begin(), 2396db0756f021a7b9c84d3bb7ae50498feb080a013Chris Lattner E = opBlock.succ_end(); SI != E && !ValueIsLive; ++SI) { 2406db0756f021a7b9c84d3bb7ae50498feb080a013Chris Lattner MachineBasicBlock *SuccMBB = *SI; 2416db0756f021a7b9c84d3bb7ae50498feb080a013Chris Lattner 2426db0756f021a7b9c84d3bb7ae50498feb080a013Chris Lattner // Is it alive in this successor? 2436db0756f021a7b9c84d3bb7ae50498feb080a013Chris Lattner unsigned SuccIdx = SuccMBB->getNumber(); 2446db0756f021a7b9c84d3bb7ae50498feb080a013Chris Lattner if (SuccIdx < InRegVI.AliveBlocks.size() && 2456db0756f021a7b9c84d3bb7ae50498feb080a013Chris Lattner InRegVI.AliveBlocks[SuccIdx]) { 2466db0756f021a7b9c84d3bb7ae50498feb080a013Chris Lattner ValueIsLive = true; 2476db0756f021a7b9c84d3bb7ae50498feb080a013Chris Lattner break; 24898719d7cdc693c077d179fe3461ce625d6faef34Chris Lattner } 2496db0756f021a7b9c84d3bb7ae50498feb080a013Chris Lattner 2506db0756f021a7b9c84d3bb7ae50498feb080a013Chris Lattner OpSuccBlocks.push_back(SuccMBB); 25153a79aaae988d9dc9d12af8970f8b8fe58cc478dChris Lattner } 25253a79aaae988d9dc9d12af8970f8b8fe58cc478dChris Lattner 2536db0756f021a7b9c84d3bb7ae50498feb080a013Chris Lattner // Check to see if this value is live because there is a use in a successor 2546db0756f021a7b9c84d3bb7ae50498feb080a013Chris Lattner // that kills it. 2556db0756f021a7b9c84d3bb7ae50498feb080a013Chris Lattner if (!ValueIsLive) { 2566db0756f021a7b9c84d3bb7ae50498feb080a013Chris Lattner switch (OpSuccBlocks.size()) { 2576db0756f021a7b9c84d3bb7ae50498feb080a013Chris Lattner case 1: { 2586db0756f021a7b9c84d3bb7ae50498feb080a013Chris Lattner MachineBasicBlock *MBB = OpSuccBlocks[0]; 2596db0756f021a7b9c84d3bb7ae50498feb080a013Chris Lattner for (unsigned i = 0, e = InRegVI.Kills.size(); i != e; ++i) 2606db0756f021a7b9c84d3bb7ae50498feb080a013Chris Lattner if (InRegVI.Kills[i]->getParent() == MBB) { 26153a79aaae988d9dc9d12af8970f8b8fe58cc478dChris Lattner ValueIsLive = true; 26253a79aaae988d9dc9d12af8970f8b8fe58cc478dChris Lattner break; 26353a79aaae988d9dc9d12af8970f8b8fe58cc478dChris Lattner } 2646db0756f021a7b9c84d3bb7ae50498feb080a013Chris Lattner break; 2656db0756f021a7b9c84d3bb7ae50498feb080a013Chris Lattner } 2666db0756f021a7b9c84d3bb7ae50498feb080a013Chris Lattner case 2: { 2676db0756f021a7b9c84d3bb7ae50498feb080a013Chris Lattner MachineBasicBlock *MBB1 = OpSuccBlocks[0], *MBB2 = OpSuccBlocks[1]; 2686db0756f021a7b9c84d3bb7ae50498feb080a013Chris Lattner for (unsigned i = 0, e = InRegVI.Kills.size(); i != e; ++i) 2696db0756f021a7b9c84d3bb7ae50498feb080a013Chris Lattner if (InRegVI.Kills[i]->getParent() == MBB1 || 2706db0756f021a7b9c84d3bb7ae50498feb080a013Chris Lattner InRegVI.Kills[i]->getParent() == MBB2) { 2716db0756f021a7b9c84d3bb7ae50498feb080a013Chris Lattner ValueIsLive = true; 2726db0756f021a7b9c84d3bb7ae50498feb080a013Chris Lattner break; 2736db0756f021a7b9c84d3bb7ae50498feb080a013Chris Lattner } 2746db0756f021a7b9c84d3bb7ae50498feb080a013Chris Lattner break; 275bc40e898e153c9b81f246a7971eaac7b14446c49Chris Lattner } 2766db0756f021a7b9c84d3bb7ae50498feb080a013Chris Lattner default: 2776db0756f021a7b9c84d3bb7ae50498feb080a013Chris Lattner std::sort(OpSuccBlocks.begin(), OpSuccBlocks.end()); 2786db0756f021a7b9c84d3bb7ae50498feb080a013Chris Lattner for (unsigned i = 0, e = InRegVI.Kills.size(); i != e; ++i) 2796db0756f021a7b9c84d3bb7ae50498feb080a013Chris Lattner if (std::binary_search(OpSuccBlocks.begin(), OpSuccBlocks.end(), 2806db0756f021a7b9c84d3bb7ae50498feb080a013Chris Lattner InRegVI.Kills[i]->getParent())) { 2816db0756f021a7b9c84d3bb7ae50498feb080a013Chris Lattner ValueIsLive = true; 2826db0756f021a7b9c84d3bb7ae50498feb080a013Chris Lattner break; 2836db0756f021a7b9c84d3bb7ae50498feb080a013Chris Lattner } 2846db0756f021a7b9c84d3bb7ae50498feb080a013Chris Lattner } 2856db0756f021a7b9c84d3bb7ae50498feb080a013Chris Lattner } 2866db0756f021a7b9c84d3bb7ae50498feb080a013Chris Lattner 2876db0756f021a7b9c84d3bb7ae50498feb080a013Chris Lattner // Okay, if we now know that the value is not live out of the block, 2882adfa7e9320e79859beb556367ea607a329866b3Chris Lattner // we can add a kill marker in this block saying that it kills the incoming 2892adfa7e9320e79859beb556367ea607a329866b3Chris Lattner // value! 2906db0756f021a7b9c84d3bb7ae50498feb080a013Chris Lattner if (!ValueIsLive) { 2912adfa7e9320e79859beb556367ea607a329866b3Chris Lattner // In our final twist, we have to decide which instruction kills the 2922adfa7e9320e79859beb556367ea607a329866b3Chris Lattner // register. In most cases this is the copy, however, the first 2932adfa7e9320e79859beb556367ea607a329866b3Chris Lattner // terminator instruction at the end of the block may also use the value. 2942adfa7e9320e79859beb556367ea607a329866b3Chris Lattner // In this case, we should mark *it* as being the killing block, not the 2952adfa7e9320e79859beb556367ea607a329866b3Chris Lattner // copy. 2962adfa7e9320e79859beb556367ea607a329866b3Chris Lattner bool FirstTerminatorUsesValue = false; 2972adfa7e9320e79859beb556367ea607a329866b3Chris Lattner if (I != opBlock.end()) { 2982adfa7e9320e79859beb556367ea607a329866b3Chris Lattner FirstTerminatorUsesValue = InstructionUsesRegister(I, SrcReg); 2992adfa7e9320e79859beb556367ea607a329866b3Chris Lattner 3002adfa7e9320e79859beb556367ea607a329866b3Chris Lattner // Check that no other terminators use values. 3012adfa7e9320e79859beb556367ea607a329866b3Chris Lattner#ifndef NDEBUG 3022adfa7e9320e79859beb556367ea607a329866b3Chris Lattner for (MachineBasicBlock::iterator TI = next(I); TI != opBlock.end(); 3032adfa7e9320e79859beb556367ea607a329866b3Chris Lattner ++TI) { 3042adfa7e9320e79859beb556367ea607a329866b3Chris Lattner assert(!InstructionUsesRegister(TI, SrcReg) && 3052adfa7e9320e79859beb556367ea607a329866b3Chris Lattner "Terminator instructions cannot use virtual registers unless" 3062adfa7e9320e79859beb556367ea607a329866b3Chris Lattner "they are the first terminator in a block!"); 3072adfa7e9320e79859beb556367ea607a329866b3Chris Lattner } 3082adfa7e9320e79859beb556367ea607a329866b3Chris Lattner#endif 3092adfa7e9320e79859beb556367ea607a329866b3Chris Lattner } 3102adfa7e9320e79859beb556367ea607a329866b3Chris Lattner 3112adfa7e9320e79859beb556367ea607a329866b3Chris Lattner MachineBasicBlock::iterator KillInst; 3122adfa7e9320e79859beb556367ea607a329866b3Chris Lattner if (!FirstTerminatorUsesValue) 3132adfa7e9320e79859beb556367ea607a329866b3Chris Lattner KillInst = prior(I); 3142adfa7e9320e79859beb556367ea607a329866b3Chris Lattner else 3152adfa7e9320e79859beb556367ea607a329866b3Chris Lattner KillInst = I; 3162adfa7e9320e79859beb556367ea607a329866b3Chris Lattner 3172adfa7e9320e79859beb556367ea607a329866b3Chris Lattner // Finally, mark it killed. 3182adfa7e9320e79859beb556367ea607a329866b3Chris Lattner LV->addVirtualRegisterKilled(SrcReg, KillInst); 3196db0756f021a7b9c84d3bb7ae50498feb080a013Chris Lattner 3206db0756f021a7b9c84d3bb7ae50498feb080a013Chris Lattner // This vreg no longer lives all of the way through opBlock. 3216db0756f021a7b9c84d3bb7ae50498feb080a013Chris Lattner unsigned opBlockNum = opBlock.getNumber(); 3226db0756f021a7b9c84d3bb7ae50498feb080a013Chris Lattner if (opBlockNum < InRegVI.AliveBlocks.size()) 3236db0756f021a7b9c84d3bb7ae50498feb080a013Chris Lattner InRegVI.AliveBlocks[opBlockNum] = false; 324bc40e898e153c9b81f246a7971eaac7b14446c49Chris Lattner } 325bc40e898e153c9b81f246a7971eaac7b14446c49Chris Lattner } 32653a79aaae988d9dc9d12af8970f8b8fe58cc478dChris Lattner 32753a79aaae988d9dc9d12af8970f8b8fe58cc478dChris Lattner // Really delete the PHI instruction now! 32853a79aaae988d9dc9d12af8970f8b8fe58cc478dChris Lattner delete MPhi; 3296db0756f021a7b9c84d3bb7ae50498feb080a013Chris Lattner ++NumAtomic; 330bc40e898e153c9b81f246a7971eaac7b14446c49Chris Lattner} 331ca756d2cf9bd88f210d61dd5f9776920a6178441Bill Wendling 332ca756d2cf9bd88f210d61dd5f9776920a6178441Bill Wendling/// analyzePHINodes - Gather information about the PHI nodes in here. In 333ca756d2cf9bd88f210d61dd5f9776920a6178441Bill Wendling/// particular, we want to map the number of uses of a virtual register which is 334ca756d2cf9bd88f210d61dd5f9776920a6178441Bill Wendling/// used in a PHI node. We map that to the BB the vreg is coming from. This is 335ca756d2cf9bd88f210d61dd5f9776920a6178441Bill Wendling/// used later to determine when the vreg is killed in the BB. 336ca756d2cf9bd88f210d61dd5f9776920a6178441Bill Wendling/// 337ca756d2cf9bd88f210d61dd5f9776920a6178441Bill Wendlingvoid PNE::analyzePHINodes(const MachineFunction& Fn) { 338ca756d2cf9bd88f210d61dd5f9776920a6178441Bill Wendling for (MachineFunction::const_iterator I = Fn.begin(), E = Fn.end(); 339ca756d2cf9bd88f210d61dd5f9776920a6178441Bill Wendling I != E; ++I) 340ca756d2cf9bd88f210d61dd5f9776920a6178441Bill Wendling for (MachineBasicBlock::const_iterator BBI = I->begin(), BBE = I->end(); 341ca756d2cf9bd88f210d61dd5f9776920a6178441Bill Wendling BBI != BBE && BBI->getOpcode() == TargetInstrInfo::PHI; ++BBI) 342ca756d2cf9bd88f210d61dd5f9776920a6178441Bill Wendling for (unsigned i = 1, e = BBI->getNumOperands(); i != e; i += 2) 3438aa797aa51cd4ea1ec6f46f4891a6897944b75b2Chris Lattner ++VRegPHIUseCount[BBVRegPair(BBI->getOperand(i + 1).getMBB(), 3448aa797aa51cd4ea1ec6f46f4891a6897944b75b2Chris Lattner BBI->getOperand(i).getReg())]; 345ca756d2cf9bd88f210d61dd5f9776920a6178441Bill Wendling} 346