PHIElimination.cpp revision 576a27043d95d0b9b8a010bccfd38ed9c0afa739
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" 24576a27043d95d0b9b8a010bccfd38ed9c0afa739Evan Cheng#include "llvm/ADT/SmallPtrSet.h" 25551ccae044b0ff658fe629dd67edd5ffe75d10e8Reid Spencer#include "llvm/ADT/STLExtras.h" 266db0756f021a7b9c84d3bb7ae50498feb080a013Chris Lattner#include "llvm/ADT/Statistic.h" 27a4f0b3a084d120cfc5b5bb06f64b222f5cb72740Chris Lattner#include "llvm/Support/Compiler.h" 286db0756f021a7b9c84d3bb7ae50498feb080a013Chris Lattner#include <algorithm> 291088317675dd34a1823f427e472fb9e43c616cb1Evan Cheng#include <map> 300742b59913a7760eb26f08121cd244a37e83e3b3Chris Lattnerusing namespace llvm; 31d0fde30ce850b78371fd1386338350591f9ff494Brian Gaeke 32cd3245ac45c595da96bb768a55cddc356dff55feChris LattnerSTATISTIC(NumAtomic, "Number of atomic phis lowered"); 33cd3245ac45c595da96bb768a55cddc356dff55feChris Lattner 34bc40e898e153c9b81f246a7971eaac7b14446c49Chris Lattnernamespace { 35576a27043d95d0b9b8a010bccfd38ed9c0afa739Evan Cheng class VISIBILITY_HIDDEN PNE : public MachineFunctionPass { 36576a27043d95d0b9b8a010bccfd38ed9c0afa739Evan Cheng MachineRegisterInfo *MRI; // Machine register information 37576a27043d95d0b9b8a010bccfd38ed9c0afa739Evan Cheng 38576a27043d95d0b9b8a010bccfd38ed9c0afa739Evan Cheng public: 39ecd94c804a563f2a86572dcf1d2e81f397e19daaNick Lewycky static char ID; // Pass identification, replacement for typeid 40794fd75c67a2cdc128d67342c6d88a504d186896Devang Patel PNE() : MachineFunctionPass((intptr_t)&ID) {} 41794fd75c67a2cdc128d67342c6d88a504d186896Devang Patel 42576a27043d95d0b9b8a010bccfd38ed9c0afa739Evan Cheng virtual bool runOnMachineFunction(MachineFunction &Fn); 43576a27043d95d0b9b8a010bccfd38ed9c0afa739Evan Cheng 44bc40e898e153c9b81f246a7971eaac7b14446c49Chris Lattner virtual void getAnalysisUsage(AnalysisUsage &AU) const { 45bc40e898e153c9b81f246a7971eaac7b14446c49Chris Lattner AU.addPreserved<LiveVariables>(); 4667d65bb69d5cad957cbb6d672dc0b4a19c211a42Bill Wendling AU.addPreservedID(MachineLoopInfoID); 4767d65bb69d5cad957cbb6d672dc0b4a19c211a42Bill Wendling AU.addPreservedID(MachineDominatorsID); 48bc40e898e153c9b81f246a7971eaac7b14446c49Chris Lattner MachineFunctionPass::getAnalysisUsage(AU); 49bc40e898e153c9b81f246a7971eaac7b14446c49Chris Lattner } 50bc40e898e153c9b81f246a7971eaac7b14446c49Chris Lattner 51bc40e898e153c9b81f246a7971eaac7b14446c49Chris Lattner private: 52576a27043d95d0b9b8a010bccfd38ed9c0afa739Evan Cheng /// findInsertionPoint - Find a safe location to insert a move to copy 53576a27043d95d0b9b8a010bccfd38ed9c0afa739Evan Cheng /// source of a PHI instruction. 54576a27043d95d0b9b8a010bccfd38ed9c0afa739Evan Cheng MachineBasicBlock::iterator 55576a27043d95d0b9b8a010bccfd38ed9c0afa739Evan Cheng findInsertionPoint(MachineBasicBlock &MBB, MachineInstr *DefMI, 56576a27043d95d0b9b8a010bccfd38ed9c0afa739Evan Cheng unsigned DstReg, unsigned SrcReg) const; 57576a27043d95d0b9b8a010bccfd38ed9c0afa739Evan Cheng 58bc40e898e153c9b81f246a7971eaac7b14446c49Chris Lattner /// EliminatePHINodes - Eliminate phi nodes by inserting copy instructions 59bc40e898e153c9b81f246a7971eaac7b14446c49Chris Lattner /// in predecessor basic blocks. 60bc40e898e153c9b81f246a7971eaac7b14446c49Chris Lattner /// 61bc40e898e153c9b81f246a7971eaac7b14446c49Chris Lattner bool EliminatePHINodes(MachineFunction &MF, MachineBasicBlock &MBB); 6253a79aaae988d9dc9d12af8970f8b8fe58cc478dChris Lattner void LowerAtomicPHINode(MachineBasicBlock &MBB, 63ca756d2cf9bd88f210d61dd5f9776920a6178441Bill Wendling MachineBasicBlock::iterator AfterPHIsIt); 64ca756d2cf9bd88f210d61dd5f9776920a6178441Bill Wendling 65ca756d2cf9bd88f210d61dd5f9776920a6178441Bill Wendling /// analyzePHINodes - Gather information about the PHI nodes in 66ca756d2cf9bd88f210d61dd5f9776920a6178441Bill Wendling /// here. In particular, we want to map the number of uses of a virtual 67ca756d2cf9bd88f210d61dd5f9776920a6178441Bill Wendling /// register which is used in a PHI node. We map that to the BB the 68ca756d2cf9bd88f210d61dd5f9776920a6178441Bill Wendling /// vreg is coming from. This is used later to determine when the vreg 69ca756d2cf9bd88f210d61dd5f9776920a6178441Bill Wendling /// is killed in the BB. 70ca756d2cf9bd88f210d61dd5f9776920a6178441Bill Wendling /// 71ca756d2cf9bd88f210d61dd5f9776920a6178441Bill Wendling void analyzePHINodes(const MachineFunction& Fn); 72ca756d2cf9bd88f210d61dd5f9776920a6178441Bill Wendling 73ca756d2cf9bd88f210d61dd5f9776920a6178441Bill Wendling typedef std::pair<const MachineBasicBlock*, unsigned> BBVRegPair; 74ca756d2cf9bd88f210d61dd5f9776920a6178441Bill Wendling typedef std::map<BBVRegPair, unsigned> VRegPHIUse; 75ca756d2cf9bd88f210d61dd5f9776920a6178441Bill Wendling 76ca756d2cf9bd88f210d61dd5f9776920a6178441Bill Wendling VRegPHIUse VRegPHIUseCount; 77576a27043d95d0b9b8a010bccfd38ed9c0afa739Evan Cheng 78576a27043d95d0b9b8a010bccfd38ed9c0afa739Evan Cheng // Defs of PHI sources which are implicit_def. 79576a27043d95d0b9b8a010bccfd38ed9c0afa739Evan Cheng SmallPtrSet<MachineInstr*, 4> ImpDefs; 80bc40e898e153c9b81f246a7971eaac7b14446c49Chris Lattner }; 81bc40e898e153c9b81f246a7971eaac7b14446c49Chris Lattner 821997473cf72957d0e70322e2fe6fe2ab141c58a6Devang Patel char PNE::ID = 0; 83bc40e898e153c9b81f246a7971eaac7b14446c49Chris Lattner RegisterPass<PNE> X("phi-node-elimination", 84dedf2bd5a34dac25e4245f58bb902ced6b64edd9Misha Brukman "Eliminate PHI nodes for register allocation"); 85bc40e898e153c9b81f246a7971eaac7b14446c49Chris Lattner} 86bc40e898e153c9b81f246a7971eaac7b14446c49Chris Lattner 870742b59913a7760eb26f08121cd244a37e83e3b3Chris Lattnerconst PassInfo *llvm::PHIEliminationID = X.getPassInfo(); 88bc40e898e153c9b81f246a7971eaac7b14446c49Chris Lattner 89576a27043d95d0b9b8a010bccfd38ed9c0afa739Evan Chengbool PNE::runOnMachineFunction(MachineFunction &Fn) { 90576a27043d95d0b9b8a010bccfd38ed9c0afa739Evan Cheng MRI = &Fn.getRegInfo(); 91576a27043d95d0b9b8a010bccfd38ed9c0afa739Evan Cheng 92576a27043d95d0b9b8a010bccfd38ed9c0afa739Evan Cheng analyzePHINodes(Fn); 93576a27043d95d0b9b8a010bccfd38ed9c0afa739Evan Cheng 94576a27043d95d0b9b8a010bccfd38ed9c0afa739Evan Cheng bool Changed = false; 95576a27043d95d0b9b8a010bccfd38ed9c0afa739Evan Cheng 96576a27043d95d0b9b8a010bccfd38ed9c0afa739Evan Cheng // Eliminate PHI instructions by inserting copies into predecessor blocks. 97576a27043d95d0b9b8a010bccfd38ed9c0afa739Evan Cheng for (MachineFunction::iterator I = Fn.begin(), E = Fn.end(); I != E; ++I) 98576a27043d95d0b9b8a010bccfd38ed9c0afa739Evan Cheng Changed |= EliminatePHINodes(Fn, *I); 99576a27043d95d0b9b8a010bccfd38ed9c0afa739Evan Cheng 100576a27043d95d0b9b8a010bccfd38ed9c0afa739Evan Cheng // Remove dead IMPLICIT_DEF instructions. 101576a27043d95d0b9b8a010bccfd38ed9c0afa739Evan Cheng for (SmallPtrSet<MachineInstr*,4>::iterator I = ImpDefs.begin(), 102576a27043d95d0b9b8a010bccfd38ed9c0afa739Evan Cheng E = ImpDefs.end(); I != E; ++I) { 103576a27043d95d0b9b8a010bccfd38ed9c0afa739Evan Cheng MachineInstr *DefMI = *I; 104576a27043d95d0b9b8a010bccfd38ed9c0afa739Evan Cheng unsigned DefReg = DefMI->getOperand(0).getReg(); 105576a27043d95d0b9b8a010bccfd38ed9c0afa739Evan Cheng if (MRI->use_begin(DefReg) == MRI->use_end()) 106576a27043d95d0b9b8a010bccfd38ed9c0afa739Evan Cheng DefMI->eraseFromParent(); 107576a27043d95d0b9b8a010bccfd38ed9c0afa739Evan Cheng } 108576a27043d95d0b9b8a010bccfd38ed9c0afa739Evan Cheng 109576a27043d95d0b9b8a010bccfd38ed9c0afa739Evan Cheng ImpDefs.clear(); 110576a27043d95d0b9b8a010bccfd38ed9c0afa739Evan Cheng VRegPHIUseCount.clear(); 111576a27043d95d0b9b8a010bccfd38ed9c0afa739Evan Cheng return Changed; 112576a27043d95d0b9b8a010bccfd38ed9c0afa739Evan Cheng} 113576a27043d95d0b9b8a010bccfd38ed9c0afa739Evan Cheng 114576a27043d95d0b9b8a010bccfd38ed9c0afa739Evan Cheng 115bc40e898e153c9b81f246a7971eaac7b14446c49Chris Lattner/// EliminatePHINodes - Eliminate phi nodes by inserting copy instructions in 116bc40e898e153c9b81f246a7971eaac7b14446c49Chris Lattner/// predecessor basic blocks. 117bc40e898e153c9b81f246a7971eaac7b14446c49Chris Lattner/// 118bc40e898e153c9b81f246a7971eaac7b14446c49Chris Lattnerbool PNE::EliminatePHINodes(MachineFunction &MF, MachineBasicBlock &MBB) { 119c0b9dc5be79f009d260edb5cd5e1d8346587aaa2Alkis Evlogimenos if (MBB.empty() || MBB.front().getOpcode() != TargetInstrInfo::PHI) 12053a79aaae988d9dc9d12af8970f8b8fe58cc478dChris Lattner return false; // Quick exit for basic blocks without PHIs. 121bc40e898e153c9b81f246a7971eaac7b14446c49Chris Lattner 122791f896d9f8a38b3806878867d61c114069b6195Chris Lattner // Get an iterator to the first instruction after the last PHI node (this may 12353a79aaae988d9dc9d12af8970f8b8fe58cc478dChris Lattner // also be the end of the basic block). 124791f896d9f8a38b3806878867d61c114069b6195Chris Lattner MachineBasicBlock::iterator AfterPHIsIt = MBB.begin(); 125791f896d9f8a38b3806878867d61c114069b6195Chris Lattner while (AfterPHIsIt != MBB.end() && 126bee887211b603a7e19bf72a4c04e120b47ad82e9Chris Lattner AfterPHIsIt->getOpcode() == TargetInstrInfo::PHI) 127791f896d9f8a38b3806878867d61c114069b6195Chris Lattner ++AfterPHIsIt; // Skip over all of the PHI nodes... 128791f896d9f8a38b3806878867d61c114069b6195Chris Lattner 129ca756d2cf9bd88f210d61dd5f9776920a6178441Bill Wendling while (MBB.front().getOpcode() == TargetInstrInfo::PHI) 130ca756d2cf9bd88f210d61dd5f9776920a6178441Bill Wendling LowerAtomicPHINode(MBB, AfterPHIsIt); 131ca756d2cf9bd88f210d61dd5f9776920a6178441Bill Wendling 13253a79aaae988d9dc9d12af8970f8b8fe58cc478dChris Lattner return true; 13353a79aaae988d9dc9d12af8970f8b8fe58cc478dChris Lattner} 134edf128a7fa90f2b0b7ee24741a04a7ae1ecd6f7eMisha Brukman 135576a27043d95d0b9b8a010bccfd38ed9c0afa739Evan Cheng/// findInsertionPoint - Find a safe location to insert a move to copy 136576a27043d95d0b9b8a010bccfd38ed9c0afa739Evan Cheng/// source of a PHI instruction. 137576a27043d95d0b9b8a010bccfd38ed9c0afa739Evan ChengMachineBasicBlock::iterator 138576a27043d95d0b9b8a010bccfd38ed9c0afa739Evan ChengPNE::findInsertionPoint(MachineBasicBlock &MBB, MachineInstr *DefMI, 139576a27043d95d0b9b8a010bccfd38ed9c0afa739Evan Cheng unsigned DstReg, unsigned SrcReg) const { 140576a27043d95d0b9b8a010bccfd38ed9c0afa739Evan Cheng if (DefMI->getOpcode() == TargetInstrInfo::PHI || 141576a27043d95d0b9b8a010bccfd38ed9c0afa739Evan Cheng DefMI->getParent() != &MBB) 142576a27043d95d0b9b8a010bccfd38ed9c0afa739Evan Cheng return MBB.getFirstTerminator(); 143576a27043d95d0b9b8a010bccfd38ed9c0afa739Evan Cheng 144576a27043d95d0b9b8a010bccfd38ed9c0afa739Evan Cheng for (MachineRegisterInfo::use_iterator I = MRI->use_begin(SrcReg), 145576a27043d95d0b9b8a010bccfd38ed9c0afa739Evan Cheng E = MRI->use_end(); I != E; ++I) 146576a27043d95d0b9b8a010bccfd38ed9c0afa739Evan Cheng if (I->getParent() == &MBB) 147576a27043d95d0b9b8a010bccfd38ed9c0afa739Evan Cheng return MBB.getFirstTerminator(); 148576a27043d95d0b9b8a010bccfd38ed9c0afa739Evan Cheng for (MachineRegisterInfo::use_iterator I = MRI->use_begin(DstReg), 149576a27043d95d0b9b8a010bccfd38ed9c0afa739Evan Cheng E = MRI->use_end(); I != E; ++I) 150576a27043d95d0b9b8a010bccfd38ed9c0afa739Evan Cheng if (I->getParent() == &MBB) 151576a27043d95d0b9b8a010bccfd38ed9c0afa739Evan Cheng return MBB.getFirstTerminator(); 152576a27043d95d0b9b8a010bccfd38ed9c0afa739Evan Cheng 153576a27043d95d0b9b8a010bccfd38ed9c0afa739Evan Cheng MachineBasicBlock::iterator I = DefMI; 154576a27043d95d0b9b8a010bccfd38ed9c0afa739Evan Cheng return ++I; 1552adfa7e9320e79859beb556367ea607a329866b3Chris Lattner} 1562adfa7e9320e79859beb556367ea607a329866b3Chris Lattner 15753a79aaae988d9dc9d12af8970f8b8fe58cc478dChris Lattner/// LowerAtomicPHINode - Lower the PHI node at the top of the specified block, 15853a79aaae988d9dc9d12af8970f8b8fe58cc478dChris Lattner/// under the assuption that it needs to be lowered in a way that supports 15953a79aaae988d9dc9d12af8970f8b8fe58cc478dChris Lattner/// atomic execution of PHIs. This lowering method is always correct all of the 16053a79aaae988d9dc9d12af8970f8b8fe58cc478dChris Lattner/// time. 16153a79aaae988d9dc9d12af8970f8b8fe58cc478dChris Lattnervoid PNE::LowerAtomicPHINode(MachineBasicBlock &MBB, 162ca756d2cf9bd88f210d61dd5f9776920a6178441Bill Wendling MachineBasicBlock::iterator AfterPHIsIt) { 16353a79aaae988d9dc9d12af8970f8b8fe58cc478dChris Lattner // Unlink the PHI node from the basic block, but don't delete the PHI yet. 16453a79aaae988d9dc9d12af8970f8b8fe58cc478dChris Lattner MachineInstr *MPhi = MBB.remove(MBB.begin()); 16553a79aaae988d9dc9d12af8970f8b8fe58cc478dChris Lattner 16653a79aaae988d9dc9d12af8970f8b8fe58cc478dChris Lattner unsigned DestReg = MPhi->getOperand(0).getReg(); 16753a79aaae988d9dc9d12af8970f8b8fe58cc478dChris Lattner 168ca756d2cf9bd88f210d61dd5f9776920a6178441Bill Wendling // Create a new register for the incoming PHI arguments. 16953a79aaae988d9dc9d12af8970f8b8fe58cc478dChris Lattner MachineFunction &MF = *MBB.getParent(); 17084bc5427d6883f73cfeae3da640acd011d35c006Chris Lattner const TargetRegisterClass *RC = MF.getRegInfo().getRegClass(DestReg); 17184bc5427d6883f73cfeae3da640acd011d35c006Chris Lattner unsigned IncomingReg = MF.getRegInfo().createVirtualRegister(RC); 17253a79aaae988d9dc9d12af8970f8b8fe58cc478dChris Lattner 17353a79aaae988d9dc9d12af8970f8b8fe58cc478dChris Lattner // Insert a register to register copy in the top of the current block (but 17453a79aaae988d9dc9d12af8970f8b8fe58cc478dChris Lattner // after any remaining phi nodes) which copies the new incoming register 17553a79aaae988d9dc9d12af8970f8b8fe58cc478dChris Lattner // into the phi node destination. 17653a79aaae988d9dc9d12af8970f8b8fe58cc478dChris Lattner // 177d10fd9791c20fd8368fa0ce94b626b769c6c8ba0Owen Anderson const TargetInstrInfo *TII = MF.getTarget().getInstrInfo(); 178d10fd9791c20fd8368fa0ce94b626b769c6c8ba0Owen Anderson TII->copyRegToReg(MBB, AfterPHIsIt, DestReg, IncomingReg, RC, RC); 179bc40e898e153c9b81f246a7971eaac7b14446c49Chris Lattner 18053a79aaae988d9dc9d12af8970f8b8fe58cc478dChris Lattner // Update live variable information if there is any... 18153a79aaae988d9dc9d12af8970f8b8fe58cc478dChris Lattner LiveVariables *LV = getAnalysisToUpdate<LiveVariables>(); 18253a79aaae988d9dc9d12af8970f8b8fe58cc478dChris Lattner if (LV) { 18353a79aaae988d9dc9d12af8970f8b8fe58cc478dChris Lattner MachineInstr *PHICopy = prior(AfterPHIsIt); 184edf128a7fa90f2b0b7ee24741a04a7ae1ecd6f7eMisha Brukman 1853fefc182a00663bfadbcbe17711b6d08469c9727Evan Cheng // Increment use count of the newly created virtual register. 1863fefc182a00663bfadbcbe17711b6d08469c9727Evan Cheng LV->getVarInfo(IncomingReg).NumUses++; 1873fefc182a00663bfadbcbe17711b6d08469c9727Evan Cheng 18853a79aaae988d9dc9d12af8970f8b8fe58cc478dChris Lattner // Add information to LiveVariables to know that the incoming value is 18953a79aaae988d9dc9d12af8970f8b8fe58cc478dChris Lattner // killed. Note that because the value is defined in several places (once 19053a79aaae988d9dc9d12af8970f8b8fe58cc478dChris Lattner // each for each incoming block), the "def" block and instruction fields 19153a79aaae988d9dc9d12af8970f8b8fe58cc478dChris Lattner // for the VarInfo is not filled in. 19253a79aaae988d9dc9d12af8970f8b8fe58cc478dChris Lattner // 19353a79aaae988d9dc9d12af8970f8b8fe58cc478dChris Lattner LV->addVirtualRegisterKilled(IncomingReg, PHICopy); 194bc40e898e153c9b81f246a7971eaac7b14446c49Chris Lattner 19553a79aaae988d9dc9d12af8970f8b8fe58cc478dChris Lattner // Since we are going to be deleting the PHI node, if it is the last use 19653a79aaae988d9dc9d12af8970f8b8fe58cc478dChris Lattner // of any registers, or if the value itself is dead, we need to move this 19753a79aaae988d9dc9d12af8970f8b8fe58cc478dChris Lattner // information over to the new copy we just inserted. 198bc40e898e153c9b81f246a7971eaac7b14446c49Chris Lattner // 19953a79aaae988d9dc9d12af8970f8b8fe58cc478dChris Lattner LV->removeVirtualRegistersKilled(MPhi); 20053a79aaae988d9dc9d12af8970f8b8fe58cc478dChris Lattner 2016db0756f021a7b9c84d3bb7ae50498feb080a013Chris Lattner // If the result is dead, update LV. 2026130f66eaae89f8878590796977678afa8448926Evan Cheng if (MPhi->registerDefIsDead(DestReg)) { 2036db0756f021a7b9c84d3bb7ae50498feb080a013Chris Lattner LV->addVirtualRegisterDead(DestReg, PHICopy); 20453a79aaae988d9dc9d12af8970f8b8fe58cc478dChris Lattner LV->removeVirtualRegistersDead(MPhi); 205927ce5dfaea00453889080cd1c6daf3eb197ad74Chris Lattner } 206a018540807775703d630e9c92f9d8013d545599eOwen Anderson 207a018540807775703d630e9c92f9d8013d545599eOwen Anderson LV->getVarInfo(IncomingReg).UsedBlocks[MBB.getNumber()] = true; 20853a79aaae988d9dc9d12af8970f8b8fe58cc478dChris Lattner } 20953a79aaae988d9dc9d12af8970f8b8fe58cc478dChris Lattner 21053a79aaae988d9dc9d12af8970f8b8fe58cc478dChris Lattner // Adjust the VRegPHIUseCount map to account for the removal of this PHI 21153a79aaae988d9dc9d12af8970f8b8fe58cc478dChris Lattner // node. 21253a79aaae988d9dc9d12af8970f8b8fe58cc478dChris Lattner for (unsigned i = 1; i != MPhi->getNumOperands(); i += 2) 2138aa797aa51cd4ea1ec6f46f4891a6897944b75b2Chris Lattner --VRegPHIUseCount[BBVRegPair(MPhi->getOperand(i + 1).getMBB(), 2148aa797aa51cd4ea1ec6f46f4891a6897944b75b2Chris Lattner MPhi->getOperand(i).getReg())]; 21553a79aaae988d9dc9d12af8970f8b8fe58cc478dChris Lattner 21653a79aaae988d9dc9d12af8970f8b8fe58cc478dChris Lattner // Now loop over all of the incoming arguments, changing them to copy into 21753a79aaae988d9dc9d12af8970f8b8fe58cc478dChris Lattner // the IncomingReg register in the corresponding predecessor basic block. 21853a79aaae988d9dc9d12af8970f8b8fe58cc478dChris Lattner // 219576a27043d95d0b9b8a010bccfd38ed9c0afa739Evan Cheng SmallPtrSet<MachineBasicBlock*, 8> MBBsInsertedInto; 22053a79aaae988d9dc9d12af8970f8b8fe58cc478dChris Lattner for (int i = MPhi->getNumOperands() - 1; i >= 2; i-=2) { 2216db0756f021a7b9c84d3bb7ae50498feb080a013Chris Lattner unsigned SrcReg = MPhi->getOperand(i-1).getReg(); 2226f0d024a534af18d9e60b3ea757376cd8a3a980eDan Gohman assert(TargetRegisterInfo::isVirtualRegister(SrcReg) && 2236db0756f021a7b9c84d3bb7ae50498feb080a013Chris Lattner "Machine PHI Operands must all be virtual registers!"); 22453a79aaae988d9dc9d12af8970f8b8fe58cc478dChris Lattner 225576a27043d95d0b9b8a010bccfd38ed9c0afa739Evan Cheng // If source is defined by an implicit def, there is no need to insert 226576a27043d95d0b9b8a010bccfd38ed9c0afa739Evan Cheng // a copy. 227576a27043d95d0b9b8a010bccfd38ed9c0afa739Evan Cheng MachineInstr *DefMI = MRI->getVRegDef(SrcReg); 228576a27043d95d0b9b8a010bccfd38ed9c0afa739Evan Cheng if (DefMI->getOpcode() == TargetInstrInfo::IMPLICIT_DEF) { 229576a27043d95d0b9b8a010bccfd38ed9c0afa739Evan Cheng ImpDefs.insert(DefMI); 230576a27043d95d0b9b8a010bccfd38ed9c0afa739Evan Cheng continue; 231576a27043d95d0b9b8a010bccfd38ed9c0afa739Evan Cheng } 232576a27043d95d0b9b8a010bccfd38ed9c0afa739Evan Cheng 23353a79aaae988d9dc9d12af8970f8b8fe58cc478dChris Lattner // Get the MachineBasicBlock equivalent of the BasicBlock that is the 23453a79aaae988d9dc9d12af8970f8b8fe58cc478dChris Lattner // source path the PHI. 2358aa797aa51cd4ea1ec6f46f4891a6897944b75b2Chris Lattner MachineBasicBlock &opBlock = *MPhi->getOperand(i).getMBB(); 236bc40e898e153c9b81f246a7971eaac7b14446c49Chris Lattner 23753a79aaae988d9dc9d12af8970f8b8fe58cc478dChris Lattner // Check to make sure we haven't already emitted the copy for this block. 23853a79aaae988d9dc9d12af8970f8b8fe58cc478dChris Lattner // This can happen because PHI nodes may have multiple entries for the 2396db0756f021a7b9c84d3bb7ae50498feb080a013Chris Lattner // same basic block. 240576a27043d95d0b9b8a010bccfd38ed9c0afa739Evan Cheng if (!MBBsInsertedInto.insert(&opBlock)) 2416db0756f021a7b9c84d3bb7ae50498feb080a013Chris Lattner continue; // If the copy has already been emitted, we're done. 2426db0756f021a7b9c84d3bb7ae50498feb080a013Chris Lattner 243576a27043d95d0b9b8a010bccfd38ed9c0afa739Evan Cheng // Find a safe location to insert the copy, this may be the first 244576a27043d95d0b9b8a010bccfd38ed9c0afa739Evan Cheng // terminator in the block (or end()). 245576a27043d95d0b9b8a010bccfd38ed9c0afa739Evan Cheng MachineBasicBlock::iterator InsertPos = 246576a27043d95d0b9b8a010bccfd38ed9c0afa739Evan Cheng findInsertionPoint(opBlock, DefMI, IncomingReg, SrcReg); 2476db0756f021a7b9c84d3bb7ae50498feb080a013Chris Lattner 2486db0756f021a7b9c84d3bb7ae50498feb080a013Chris Lattner // Insert the copy. 249576a27043d95d0b9b8a010bccfd38ed9c0afa739Evan Cheng TII->copyRegToReg(opBlock, InsertPos, IncomingReg, SrcReg, RC, RC); 2506db0756f021a7b9c84d3bb7ae50498feb080a013Chris Lattner 2516db0756f021a7b9c84d3bb7ae50498feb080a013Chris Lattner // Now update live variable information if we have it. Otherwise we're done 2526db0756f021a7b9c84d3bb7ae50498feb080a013Chris Lattner if (!LV) continue; 2536db0756f021a7b9c84d3bb7ae50498feb080a013Chris Lattner 2546db0756f021a7b9c84d3bb7ae50498feb080a013Chris Lattner // We want to be able to insert a kill of the register if this PHI 2556db0756f021a7b9c84d3bb7ae50498feb080a013Chris Lattner // (aka, the copy we just inserted) is the last use of the source 2566db0756f021a7b9c84d3bb7ae50498feb080a013Chris Lattner // value. Live variable analysis conservatively handles this by 2576db0756f021a7b9c84d3bb7ae50498feb080a013Chris Lattner // saying that the value is live until the end of the block the PHI 2586db0756f021a7b9c84d3bb7ae50498feb080a013Chris Lattner // entry lives in. If the value really is dead at the PHI copy, there 2596db0756f021a7b9c84d3bb7ae50498feb080a013Chris Lattner // will be no successor blocks which have the value live-in. 260bc40e898e153c9b81f246a7971eaac7b14446c49Chris Lattner // 2616db0756f021a7b9c84d3bb7ae50498feb080a013Chris Lattner // Check to see if the copy is the last use, and if so, update the 2626db0756f021a7b9c84d3bb7ae50498feb080a013Chris Lattner // live variables information so that it knows the copy source 2636db0756f021a7b9c84d3bb7ae50498feb080a013Chris Lattner // instruction kills the incoming value. 26453a79aaae988d9dc9d12af8970f8b8fe58cc478dChris Lattner // 2656db0756f021a7b9c84d3bb7ae50498feb080a013Chris Lattner LiveVariables::VarInfo &InRegVI = LV->getVarInfo(SrcReg); 266a018540807775703d630e9c92f9d8013d545599eOwen Anderson InRegVI.UsedBlocks[opBlock.getNumber()] = true; 2676db0756f021a7b9c84d3bb7ae50498feb080a013Chris Lattner 2686db0756f021a7b9c84d3bb7ae50498feb080a013Chris Lattner // Loop over all of the successors of the basic block, checking to see 2696db0756f021a7b9c84d3bb7ae50498feb080a013Chris Lattner // if the value is either live in the block, or if it is killed in the 2706db0756f021a7b9c84d3bb7ae50498feb080a013Chris Lattner // block. Also check to see if this register is in use by another PHI 2716db0756f021a7b9c84d3bb7ae50498feb080a013Chris Lattner // node which has not yet been eliminated. If so, it will be killed 2726db0756f021a7b9c84d3bb7ae50498feb080a013Chris Lattner // at an appropriate point later. 2736db0756f021a7b9c84d3bb7ae50498feb080a013Chris Lattner // 2746db0756f021a7b9c84d3bb7ae50498feb080a013Chris Lattner 2756db0756f021a7b9c84d3bb7ae50498feb080a013Chris Lattner // Is it used by any PHI instructions in this block? 276ca756d2cf9bd88f210d61dd5f9776920a6178441Bill Wendling bool ValueIsLive = VRegPHIUseCount[BBVRegPair(&opBlock, SrcReg)] != 0; 2776db0756f021a7b9c84d3bb7ae50498feb080a013Chris Lattner 2786db0756f021a7b9c84d3bb7ae50498feb080a013Chris Lattner std::vector<MachineBasicBlock*> OpSuccBlocks; 2796db0756f021a7b9c84d3bb7ae50498feb080a013Chris Lattner 2806db0756f021a7b9c84d3bb7ae50498feb080a013Chris Lattner // Otherwise, scan successors, including the BB the PHI node lives in. 2816db0756f021a7b9c84d3bb7ae50498feb080a013Chris Lattner for (MachineBasicBlock::succ_iterator SI = opBlock.succ_begin(), 2826db0756f021a7b9c84d3bb7ae50498feb080a013Chris Lattner E = opBlock.succ_end(); SI != E && !ValueIsLive; ++SI) { 2836db0756f021a7b9c84d3bb7ae50498feb080a013Chris Lattner MachineBasicBlock *SuccMBB = *SI; 2846db0756f021a7b9c84d3bb7ae50498feb080a013Chris Lattner 2856db0756f021a7b9c84d3bb7ae50498feb080a013Chris Lattner // Is it alive in this successor? 2866db0756f021a7b9c84d3bb7ae50498feb080a013Chris Lattner unsigned SuccIdx = SuccMBB->getNumber(); 2876db0756f021a7b9c84d3bb7ae50498feb080a013Chris Lattner if (SuccIdx < InRegVI.AliveBlocks.size() && 2886db0756f021a7b9c84d3bb7ae50498feb080a013Chris Lattner InRegVI.AliveBlocks[SuccIdx]) { 2896db0756f021a7b9c84d3bb7ae50498feb080a013Chris Lattner ValueIsLive = true; 2906db0756f021a7b9c84d3bb7ae50498feb080a013Chris Lattner break; 29198719d7cdc693c077d179fe3461ce625d6faef34Chris Lattner } 2926db0756f021a7b9c84d3bb7ae50498feb080a013Chris Lattner 2936db0756f021a7b9c84d3bb7ae50498feb080a013Chris Lattner OpSuccBlocks.push_back(SuccMBB); 29453a79aaae988d9dc9d12af8970f8b8fe58cc478dChris Lattner } 29553a79aaae988d9dc9d12af8970f8b8fe58cc478dChris Lattner 2966db0756f021a7b9c84d3bb7ae50498feb080a013Chris Lattner // Check to see if this value is live because there is a use in a successor 2976db0756f021a7b9c84d3bb7ae50498feb080a013Chris Lattner // that kills it. 2986db0756f021a7b9c84d3bb7ae50498feb080a013Chris Lattner if (!ValueIsLive) { 2996db0756f021a7b9c84d3bb7ae50498feb080a013Chris Lattner switch (OpSuccBlocks.size()) { 3006db0756f021a7b9c84d3bb7ae50498feb080a013Chris Lattner case 1: { 3016db0756f021a7b9c84d3bb7ae50498feb080a013Chris Lattner MachineBasicBlock *MBB = OpSuccBlocks[0]; 3026db0756f021a7b9c84d3bb7ae50498feb080a013Chris Lattner for (unsigned i = 0, e = InRegVI.Kills.size(); i != e; ++i) 3036db0756f021a7b9c84d3bb7ae50498feb080a013Chris Lattner if (InRegVI.Kills[i]->getParent() == MBB) { 30453a79aaae988d9dc9d12af8970f8b8fe58cc478dChris Lattner ValueIsLive = true; 30553a79aaae988d9dc9d12af8970f8b8fe58cc478dChris Lattner break; 30653a79aaae988d9dc9d12af8970f8b8fe58cc478dChris Lattner } 3076db0756f021a7b9c84d3bb7ae50498feb080a013Chris Lattner break; 3086db0756f021a7b9c84d3bb7ae50498feb080a013Chris Lattner } 3096db0756f021a7b9c84d3bb7ae50498feb080a013Chris Lattner case 2: { 3106db0756f021a7b9c84d3bb7ae50498feb080a013Chris Lattner MachineBasicBlock *MBB1 = OpSuccBlocks[0], *MBB2 = OpSuccBlocks[1]; 3116db0756f021a7b9c84d3bb7ae50498feb080a013Chris Lattner for (unsigned i = 0, e = InRegVI.Kills.size(); i != e; ++i) 3126db0756f021a7b9c84d3bb7ae50498feb080a013Chris Lattner if (InRegVI.Kills[i]->getParent() == MBB1 || 3136db0756f021a7b9c84d3bb7ae50498feb080a013Chris Lattner InRegVI.Kills[i]->getParent() == MBB2) { 3146db0756f021a7b9c84d3bb7ae50498feb080a013Chris Lattner ValueIsLive = true; 3156db0756f021a7b9c84d3bb7ae50498feb080a013Chris Lattner break; 3166db0756f021a7b9c84d3bb7ae50498feb080a013Chris Lattner } 3176db0756f021a7b9c84d3bb7ae50498feb080a013Chris Lattner break; 318bc40e898e153c9b81f246a7971eaac7b14446c49Chris Lattner } 3196db0756f021a7b9c84d3bb7ae50498feb080a013Chris Lattner default: 3206db0756f021a7b9c84d3bb7ae50498feb080a013Chris Lattner std::sort(OpSuccBlocks.begin(), OpSuccBlocks.end()); 3216db0756f021a7b9c84d3bb7ae50498feb080a013Chris Lattner for (unsigned i = 0, e = InRegVI.Kills.size(); i != e; ++i) 3226db0756f021a7b9c84d3bb7ae50498feb080a013Chris Lattner if (std::binary_search(OpSuccBlocks.begin(), OpSuccBlocks.end(), 3236db0756f021a7b9c84d3bb7ae50498feb080a013Chris Lattner InRegVI.Kills[i]->getParent())) { 3246db0756f021a7b9c84d3bb7ae50498feb080a013Chris Lattner ValueIsLive = true; 3256db0756f021a7b9c84d3bb7ae50498feb080a013Chris Lattner break; 3266db0756f021a7b9c84d3bb7ae50498feb080a013Chris Lattner } 3276db0756f021a7b9c84d3bb7ae50498feb080a013Chris Lattner } 3286db0756f021a7b9c84d3bb7ae50498feb080a013Chris Lattner } 3296db0756f021a7b9c84d3bb7ae50498feb080a013Chris Lattner 3306db0756f021a7b9c84d3bb7ae50498feb080a013Chris Lattner // Okay, if we now know that the value is not live out of the block, 3312adfa7e9320e79859beb556367ea607a329866b3Chris Lattner // we can add a kill marker in this block saying that it kills the incoming 3322adfa7e9320e79859beb556367ea607a329866b3Chris Lattner // value! 3336db0756f021a7b9c84d3bb7ae50498feb080a013Chris Lattner if (!ValueIsLive) { 3342adfa7e9320e79859beb556367ea607a329866b3Chris Lattner // In our final twist, we have to decide which instruction kills the 3352adfa7e9320e79859beb556367ea607a329866b3Chris Lattner // register. In most cases this is the copy, however, the first 3362adfa7e9320e79859beb556367ea607a329866b3Chris Lattner // terminator instruction at the end of the block may also use the value. 3372adfa7e9320e79859beb556367ea607a329866b3Chris Lattner // In this case, we should mark *it* as being the killing block, not the 3382adfa7e9320e79859beb556367ea607a329866b3Chris Lattner // copy. 339576a27043d95d0b9b8a010bccfd38ed9c0afa739Evan Cheng MachineBasicBlock::iterator KillInst = prior(InsertPos); 340576a27043d95d0b9b8a010bccfd38ed9c0afa739Evan Cheng MachineBasicBlock::iterator Term = opBlock.getFirstTerminator(); 341576a27043d95d0b9b8a010bccfd38ed9c0afa739Evan Cheng if (Term != opBlock.end()) { 342576a27043d95d0b9b8a010bccfd38ed9c0afa739Evan Cheng if (Term->readsRegister(SrcReg)) 343576a27043d95d0b9b8a010bccfd38ed9c0afa739Evan Cheng KillInst = Term; 3442adfa7e9320e79859beb556367ea607a329866b3Chris Lattner 3452adfa7e9320e79859beb556367ea607a329866b3Chris Lattner // Check that no other terminators use values. 3462adfa7e9320e79859beb556367ea607a329866b3Chris Lattner#ifndef NDEBUG 347576a27043d95d0b9b8a010bccfd38ed9c0afa739Evan Cheng for (MachineBasicBlock::iterator TI = next(Term); TI != opBlock.end(); 3482adfa7e9320e79859beb556367ea607a329866b3Chris Lattner ++TI) { 349576a27043d95d0b9b8a010bccfd38ed9c0afa739Evan Cheng assert(!TI->readsRegister(SrcReg) && 3502adfa7e9320e79859beb556367ea607a329866b3Chris Lattner "Terminator instructions cannot use virtual registers unless" 3512adfa7e9320e79859beb556367ea607a329866b3Chris Lattner "they are the first terminator in a block!"); 3522adfa7e9320e79859beb556367ea607a329866b3Chris Lattner } 3532adfa7e9320e79859beb556367ea607a329866b3Chris Lattner#endif 3542adfa7e9320e79859beb556367ea607a329866b3Chris Lattner } 3552adfa7e9320e79859beb556367ea607a329866b3Chris Lattner 3562adfa7e9320e79859beb556367ea607a329866b3Chris Lattner // Finally, mark it killed. 3572adfa7e9320e79859beb556367ea607a329866b3Chris Lattner LV->addVirtualRegisterKilled(SrcReg, KillInst); 3586db0756f021a7b9c84d3bb7ae50498feb080a013Chris Lattner 3596db0756f021a7b9c84d3bb7ae50498feb080a013Chris Lattner // This vreg no longer lives all of the way through opBlock. 3606db0756f021a7b9c84d3bb7ae50498feb080a013Chris Lattner unsigned opBlockNum = opBlock.getNumber(); 3616db0756f021a7b9c84d3bb7ae50498feb080a013Chris Lattner if (opBlockNum < InRegVI.AliveBlocks.size()) 3626db0756f021a7b9c84d3bb7ae50498feb080a013Chris Lattner InRegVI.AliveBlocks[opBlockNum] = false; 363bc40e898e153c9b81f246a7971eaac7b14446c49Chris Lattner } 364bc40e898e153c9b81f246a7971eaac7b14446c49Chris Lattner } 36553a79aaae988d9dc9d12af8970f8b8fe58cc478dChris Lattner 36653a79aaae988d9dc9d12af8970f8b8fe58cc478dChris Lattner // Really delete the PHI instruction now! 36753a79aaae988d9dc9d12af8970f8b8fe58cc478dChris Lattner delete MPhi; 3686db0756f021a7b9c84d3bb7ae50498feb080a013Chris Lattner ++NumAtomic; 369bc40e898e153c9b81f246a7971eaac7b14446c49Chris Lattner} 370ca756d2cf9bd88f210d61dd5f9776920a6178441Bill Wendling 371ca756d2cf9bd88f210d61dd5f9776920a6178441Bill Wendling/// analyzePHINodes - Gather information about the PHI nodes in here. In 372ca756d2cf9bd88f210d61dd5f9776920a6178441Bill Wendling/// particular, we want to map the number of uses of a virtual register which is 373ca756d2cf9bd88f210d61dd5f9776920a6178441Bill Wendling/// used in a PHI node. We map that to the BB the vreg is coming from. This is 374ca756d2cf9bd88f210d61dd5f9776920a6178441Bill Wendling/// used later to determine when the vreg is killed in the BB. 375ca756d2cf9bd88f210d61dd5f9776920a6178441Bill Wendling/// 376ca756d2cf9bd88f210d61dd5f9776920a6178441Bill Wendlingvoid PNE::analyzePHINodes(const MachineFunction& Fn) { 377ca756d2cf9bd88f210d61dd5f9776920a6178441Bill Wendling for (MachineFunction::const_iterator I = Fn.begin(), E = Fn.end(); 378ca756d2cf9bd88f210d61dd5f9776920a6178441Bill Wendling I != E; ++I) 379ca756d2cf9bd88f210d61dd5f9776920a6178441Bill Wendling for (MachineBasicBlock::const_iterator BBI = I->begin(), BBE = I->end(); 380ca756d2cf9bd88f210d61dd5f9776920a6178441Bill Wendling BBI != BBE && BBI->getOpcode() == TargetInstrInfo::PHI; ++BBI) 381ca756d2cf9bd88f210d61dd5f9776920a6178441Bill Wendling for (unsigned i = 1, e = BBI->getNumOperands(); i != e; i += 2) 3828aa797aa51cd4ea1ec6f46f4891a6897944b75b2Chris Lattner ++VRegPHIUseCount[BBVRegPair(BBI->getOperand(i + 1).getMBB(), 3838aa797aa51cd4ea1ec6f46f4891a6897944b75b2Chris Lattner BBI->getOperand(i).getReg())]; 384ca756d2cf9bd88f210d61dd5f9776920a6178441Bill Wendling} 385