PHIElimination.cpp revision ae94dda61a045cb77681940ecc25aba0d2763f74
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" 21f870fbc554ac862ad6d45cf97148739802a3ed12Evan Cheng#include "llvm/CodeGen/MachineInstrBuilder.h" 2284bc5427d6883f73cfeae3da640acd011d35c006Chris Lattner#include "llvm/CodeGen/MachineRegisterInfo.h" 233501feab811c86c9659248a4875fc31a3165f84dChris Lattner#include "llvm/Target/TargetInstrInfo.h" 24bc40e898e153c9b81f246a7971eaac7b14446c49Chris Lattner#include "llvm/Target/TargetMachine.h" 25576a27043d95d0b9b8a010bccfd38ed9c0afa739Evan Cheng#include "llvm/ADT/SmallPtrSet.h" 26551ccae044b0ff658fe629dd67edd5ffe75d10e8Reid Spencer#include "llvm/ADT/STLExtras.h" 276db0756f021a7b9c84d3bb7ae50498feb080a013Chris Lattner#include "llvm/ADT/Statistic.h" 28a4f0b3a084d120cfc5b5bb06f64b222f5cb72740Chris Lattner#include "llvm/Support/Compiler.h" 296db0756f021a7b9c84d3bb7ae50498feb080a013Chris Lattner#include <algorithm> 301088317675dd34a1823f427e472fb9e43c616cb1Evan Cheng#include <map> 310742b59913a7760eb26f08121cd244a37e83e3b3Chris Lattnerusing namespace llvm; 32d0fde30ce850b78371fd1386338350591f9ff494Brian Gaeke 33cd3245ac45c595da96bb768a55cddc356dff55feChris LattnerSTATISTIC(NumAtomic, "Number of atomic phis lowered"); 34cd3245ac45c595da96bb768a55cddc356dff55feChris Lattner 35bc40e898e153c9b81f246a7971eaac7b14446c49Chris Lattnernamespace { 36576a27043d95d0b9b8a010bccfd38ed9c0afa739Evan Cheng class VISIBILITY_HIDDEN PNE : public MachineFunctionPass { 37576a27043d95d0b9b8a010bccfd38ed9c0afa739Evan Cheng MachineRegisterInfo *MRI; // Machine register information 38576a27043d95d0b9b8a010bccfd38ed9c0afa739Evan Cheng 39576a27043d95d0b9b8a010bccfd38ed9c0afa739Evan Cheng public: 40ecd94c804a563f2a86572dcf1d2e81f397e19daaNick Lewycky static char ID; // Pass identification, replacement for typeid 41794fd75c67a2cdc128d67342c6d88a504d186896Devang Patel PNE() : MachineFunctionPass((intptr_t)&ID) {} 42794fd75c67a2cdc128d67342c6d88a504d186896Devang Patel 43576a27043d95d0b9b8a010bccfd38ed9c0afa739Evan Cheng virtual bool runOnMachineFunction(MachineFunction &Fn); 44576a27043d95d0b9b8a010bccfd38ed9c0afa739Evan Cheng 45bc40e898e153c9b81f246a7971eaac7b14446c49Chris Lattner virtual void getAnalysisUsage(AnalysisUsage &AU) const { 46bc40e898e153c9b81f246a7971eaac7b14446c49Chris Lattner AU.addPreserved<LiveVariables>(); 4767d65bb69d5cad957cbb6d672dc0b4a19c211a42Bill Wendling AU.addPreservedID(MachineLoopInfoID); 4867d65bb69d5cad957cbb6d672dc0b4a19c211a42Bill Wendling AU.addPreservedID(MachineDominatorsID); 49bc40e898e153c9b81f246a7971eaac7b14446c49Chris Lattner MachineFunctionPass::getAnalysisUsage(AU); 50bc40e898e153c9b81f246a7971eaac7b14446c49Chris Lattner } 51bc40e898e153c9b81f246a7971eaac7b14446c49Chris Lattner 52bc40e898e153c9b81f246a7971eaac7b14446c49Chris Lattner private: 53bc40e898e153c9b81f246a7971eaac7b14446c49Chris Lattner /// EliminatePHINodes - Eliminate phi nodes by inserting copy instructions 54bc40e898e153c9b81f246a7971eaac7b14446c49Chris Lattner /// in predecessor basic blocks. 55bc40e898e153c9b81f246a7971eaac7b14446c49Chris Lattner /// 56bc40e898e153c9b81f246a7971eaac7b14446c49Chris Lattner bool EliminatePHINodes(MachineFunction &MF, MachineBasicBlock &MBB); 5753a79aaae988d9dc9d12af8970f8b8fe58cc478dChris Lattner void LowerAtomicPHINode(MachineBasicBlock &MBB, 58ca756d2cf9bd88f210d61dd5f9776920a6178441Bill Wendling MachineBasicBlock::iterator AfterPHIsIt); 59ca756d2cf9bd88f210d61dd5f9776920a6178441Bill Wendling 60ca756d2cf9bd88f210d61dd5f9776920a6178441Bill Wendling /// analyzePHINodes - Gather information about the PHI nodes in 61ca756d2cf9bd88f210d61dd5f9776920a6178441Bill Wendling /// here. In particular, we want to map the number of uses of a virtual 62ca756d2cf9bd88f210d61dd5f9776920a6178441Bill Wendling /// register which is used in a PHI node. We map that to the BB the 63ca756d2cf9bd88f210d61dd5f9776920a6178441Bill Wendling /// vreg is coming from. This is used later to determine when the vreg 64ca756d2cf9bd88f210d61dd5f9776920a6178441Bill Wendling /// is killed in the BB. 65ca756d2cf9bd88f210d61dd5f9776920a6178441Bill Wendling /// 66ca756d2cf9bd88f210d61dd5f9776920a6178441Bill Wendling void analyzePHINodes(const MachineFunction& Fn); 67ca756d2cf9bd88f210d61dd5f9776920a6178441Bill Wendling 68ca756d2cf9bd88f210d61dd5f9776920a6178441Bill Wendling typedef std::pair<const MachineBasicBlock*, unsigned> BBVRegPair; 69ca756d2cf9bd88f210d61dd5f9776920a6178441Bill Wendling typedef std::map<BBVRegPair, unsigned> VRegPHIUse; 70ca756d2cf9bd88f210d61dd5f9776920a6178441Bill Wendling 71ca756d2cf9bd88f210d61dd5f9776920a6178441Bill Wendling VRegPHIUse VRegPHIUseCount; 72576a27043d95d0b9b8a010bccfd38ed9c0afa739Evan Cheng 73576a27043d95d0b9b8a010bccfd38ed9c0afa739Evan Cheng // Defs of PHI sources which are implicit_def. 74576a27043d95d0b9b8a010bccfd38ed9c0afa739Evan Cheng SmallPtrSet<MachineInstr*, 4> ImpDefs; 75bc40e898e153c9b81f246a7971eaac7b14446c49Chris Lattner }; 76bc40e898e153c9b81f246a7971eaac7b14446c49Chris Lattner 771997473cf72957d0e70322e2fe6fe2ab141c58a6Devang Patel char PNE::ID = 0; 78bc40e898e153c9b81f246a7971eaac7b14446c49Chris Lattner RegisterPass<PNE> X("phi-node-elimination", 79dedf2bd5a34dac25e4245f58bb902ced6b64edd9Misha Brukman "Eliminate PHI nodes for register allocation"); 80bc40e898e153c9b81f246a7971eaac7b14446c49Chris Lattner} 81bc40e898e153c9b81f246a7971eaac7b14446c49Chris Lattner 820742b59913a7760eb26f08121cd244a37e83e3b3Chris Lattnerconst PassInfo *llvm::PHIEliminationID = X.getPassInfo(); 83bc40e898e153c9b81f246a7971eaac7b14446c49Chris Lattner 84576a27043d95d0b9b8a010bccfd38ed9c0afa739Evan Chengbool PNE::runOnMachineFunction(MachineFunction &Fn) { 85576a27043d95d0b9b8a010bccfd38ed9c0afa739Evan Cheng MRI = &Fn.getRegInfo(); 86576a27043d95d0b9b8a010bccfd38ed9c0afa739Evan Cheng 87576a27043d95d0b9b8a010bccfd38ed9c0afa739Evan Cheng analyzePHINodes(Fn); 88576a27043d95d0b9b8a010bccfd38ed9c0afa739Evan Cheng 89576a27043d95d0b9b8a010bccfd38ed9c0afa739Evan Cheng bool Changed = false; 90576a27043d95d0b9b8a010bccfd38ed9c0afa739Evan Cheng 91576a27043d95d0b9b8a010bccfd38ed9c0afa739Evan Cheng // Eliminate PHI instructions by inserting copies into predecessor blocks. 92576a27043d95d0b9b8a010bccfd38ed9c0afa739Evan Cheng for (MachineFunction::iterator I = Fn.begin(), E = Fn.end(); I != E; ++I) 93576a27043d95d0b9b8a010bccfd38ed9c0afa739Evan Cheng Changed |= EliminatePHINodes(Fn, *I); 94576a27043d95d0b9b8a010bccfd38ed9c0afa739Evan Cheng 95576a27043d95d0b9b8a010bccfd38ed9c0afa739Evan Cheng // Remove dead IMPLICIT_DEF instructions. 96576a27043d95d0b9b8a010bccfd38ed9c0afa739Evan Cheng for (SmallPtrSet<MachineInstr*,4>::iterator I = ImpDefs.begin(), 97576a27043d95d0b9b8a010bccfd38ed9c0afa739Evan Cheng E = ImpDefs.end(); I != E; ++I) { 98576a27043d95d0b9b8a010bccfd38ed9c0afa739Evan Cheng MachineInstr *DefMI = *I; 99576a27043d95d0b9b8a010bccfd38ed9c0afa739Evan Cheng unsigned DefReg = DefMI->getOperand(0).getReg(); 100576a27043d95d0b9b8a010bccfd38ed9c0afa739Evan Cheng if (MRI->use_begin(DefReg) == MRI->use_end()) 101576a27043d95d0b9b8a010bccfd38ed9c0afa739Evan Cheng DefMI->eraseFromParent(); 102576a27043d95d0b9b8a010bccfd38ed9c0afa739Evan Cheng } 103576a27043d95d0b9b8a010bccfd38ed9c0afa739Evan Cheng 104576a27043d95d0b9b8a010bccfd38ed9c0afa739Evan Cheng ImpDefs.clear(); 105576a27043d95d0b9b8a010bccfd38ed9c0afa739Evan Cheng VRegPHIUseCount.clear(); 106576a27043d95d0b9b8a010bccfd38ed9c0afa739Evan Cheng return Changed; 107576a27043d95d0b9b8a010bccfd38ed9c0afa739Evan Cheng} 108576a27043d95d0b9b8a010bccfd38ed9c0afa739Evan Cheng 109576a27043d95d0b9b8a010bccfd38ed9c0afa739Evan Cheng 110bc40e898e153c9b81f246a7971eaac7b14446c49Chris Lattner/// EliminatePHINodes - Eliminate phi nodes by inserting copy instructions in 111bc40e898e153c9b81f246a7971eaac7b14446c49Chris Lattner/// predecessor basic blocks. 112bc40e898e153c9b81f246a7971eaac7b14446c49Chris Lattner/// 113bc40e898e153c9b81f246a7971eaac7b14446c49Chris Lattnerbool PNE::EliminatePHINodes(MachineFunction &MF, MachineBasicBlock &MBB) { 114c0b9dc5be79f009d260edb5cd5e1d8346587aaa2Alkis Evlogimenos if (MBB.empty() || MBB.front().getOpcode() != TargetInstrInfo::PHI) 11553a79aaae988d9dc9d12af8970f8b8fe58cc478dChris Lattner return false; // Quick exit for basic blocks without PHIs. 116bc40e898e153c9b81f246a7971eaac7b14446c49Chris Lattner 117791f896d9f8a38b3806878867d61c114069b6195Chris Lattner // Get an iterator to the first instruction after the last PHI node (this may 11853a79aaae988d9dc9d12af8970f8b8fe58cc478dChris Lattner // also be the end of the basic block). 119791f896d9f8a38b3806878867d61c114069b6195Chris Lattner MachineBasicBlock::iterator AfterPHIsIt = MBB.begin(); 120791f896d9f8a38b3806878867d61c114069b6195Chris Lattner while (AfterPHIsIt != MBB.end() && 121bee887211b603a7e19bf72a4c04e120b47ad82e9Chris Lattner AfterPHIsIt->getOpcode() == TargetInstrInfo::PHI) 122791f896d9f8a38b3806878867d61c114069b6195Chris Lattner ++AfterPHIsIt; // Skip over all of the PHI nodes... 123791f896d9f8a38b3806878867d61c114069b6195Chris Lattner 124ca756d2cf9bd88f210d61dd5f9776920a6178441Bill Wendling while (MBB.front().getOpcode() == TargetInstrInfo::PHI) 125ca756d2cf9bd88f210d61dd5f9776920a6178441Bill Wendling LowerAtomicPHINode(MBB, AfterPHIsIt); 126ca756d2cf9bd88f210d61dd5f9776920a6178441Bill Wendling 12753a79aaae988d9dc9d12af8970f8b8fe58cc478dChris Lattner return true; 12853a79aaae988d9dc9d12af8970f8b8fe58cc478dChris Lattner} 129edf128a7fa90f2b0b7ee24741a04a7ae1ecd6f7eMisha Brukman 130ae94dda61a045cb77681940ecc25aba0d2763f74Bill Wendlingstatic bool isSourceDefinedByImplicitDef(const MachineInstr *MPhi, 131ae94dda61a045cb77681940ecc25aba0d2763f74Bill Wendling const MachineRegisterInfo *MRI) { 132b3e0a6d75c60f01df4fcee4b4309f06ce92a96c9Evan Cheng for (unsigned i = 1; i != MPhi->getNumOperands(); i += 2) { 133b3e0a6d75c60f01df4fcee4b4309f06ce92a96c9Evan Cheng unsigned SrcReg = MPhi->getOperand(i).getReg(); 134ae94dda61a045cb77681940ecc25aba0d2763f74Bill Wendling const MachineInstr *DefMI = MRI->getVRegDef(SrcReg); 135b3e0a6d75c60f01df4fcee4b4309f06ce92a96c9Evan Cheng if (!DefMI || DefMI->getOpcode() != TargetInstrInfo::IMPLICIT_DEF) 136b3e0a6d75c60f01df4fcee4b4309f06ce92a96c9Evan Cheng return false; 137b3e0a6d75c60f01df4fcee4b4309f06ce92a96c9Evan Cheng } 138b3e0a6d75c60f01df4fcee4b4309f06ce92a96c9Evan Cheng return true; 139f870fbc554ac862ad6d45cf97148739802a3ed12Evan Cheng} 140f870fbc554ac862ad6d45cf97148739802a3ed12Evan Cheng 14153a79aaae988d9dc9d12af8970f8b8fe58cc478dChris Lattner/// LowerAtomicPHINode - Lower the PHI node at the top of the specified block, 14253a79aaae988d9dc9d12af8970f8b8fe58cc478dChris Lattner/// under the assuption that it needs to be lowered in a way that supports 14353a79aaae988d9dc9d12af8970f8b8fe58cc478dChris Lattner/// atomic execution of PHIs. This lowering method is always correct all of the 14453a79aaae988d9dc9d12af8970f8b8fe58cc478dChris Lattner/// time. 145ae94dda61a045cb77681940ecc25aba0d2763f74Bill Wendling/// 14653a79aaae988d9dc9d12af8970f8b8fe58cc478dChris Lattnervoid PNE::LowerAtomicPHINode(MachineBasicBlock &MBB, 147ca756d2cf9bd88f210d61dd5f9776920a6178441Bill Wendling MachineBasicBlock::iterator AfterPHIsIt) { 14853a79aaae988d9dc9d12af8970f8b8fe58cc478dChris Lattner // Unlink the PHI node from the basic block, but don't delete the PHI yet. 14953a79aaae988d9dc9d12af8970f8b8fe58cc478dChris Lattner MachineInstr *MPhi = MBB.remove(MBB.begin()); 15053a79aaae988d9dc9d12af8970f8b8fe58cc478dChris Lattner 151f870fbc554ac862ad6d45cf97148739802a3ed12Evan Cheng unsigned NumSrcs = (MPhi->getNumOperands() - 1) / 2; 15253a79aaae988d9dc9d12af8970f8b8fe58cc478dChris Lattner unsigned DestReg = MPhi->getOperand(0).getReg(); 15353a79aaae988d9dc9d12af8970f8b8fe58cc478dChris Lattner 154ca756d2cf9bd88f210d61dd5f9776920a6178441Bill Wendling // Create a new register for the incoming PHI arguments. 15553a79aaae988d9dc9d12af8970f8b8fe58cc478dChris Lattner MachineFunction &MF = *MBB.getParent(); 15684bc5427d6883f73cfeae3da640acd011d35c006Chris Lattner const TargetRegisterClass *RC = MF.getRegInfo().getRegClass(DestReg); 15784bc5427d6883f73cfeae3da640acd011d35c006Chris Lattner unsigned IncomingReg = MF.getRegInfo().createVirtualRegister(RC); 15853a79aaae988d9dc9d12af8970f8b8fe58cc478dChris Lattner 159ae94dda61a045cb77681940ecc25aba0d2763f74Bill Wendling // Insert a register to register copy at the top of the current block (but 16053a79aaae988d9dc9d12af8970f8b8fe58cc478dChris Lattner // after any remaining phi nodes) which copies the new incoming register 16153a79aaae988d9dc9d12af8970f8b8fe58cc478dChris Lattner // into the phi node destination. 162d10fd9791c20fd8368fa0ce94b626b769c6c8ba0Owen Anderson const TargetInstrInfo *TII = MF.getTarget().getInstrInfo(); 163b3e0a6d75c60f01df4fcee4b4309f06ce92a96c9Evan Cheng if (isSourceDefinedByImplicitDef(MPhi, MRI)) 164b3e0a6d75c60f01df4fcee4b4309f06ce92a96c9Evan Cheng // If all sources of a PHI node are implicit_def, just emit an implicit_def 165b3e0a6d75c60f01df4fcee4b4309f06ce92a96c9Evan Cheng // instead of a copy. 166f870fbc554ac862ad6d45cf97148739802a3ed12Evan Cheng BuildMI(MBB, AfterPHIsIt, TII->get(TargetInstrInfo::IMPLICIT_DEF), DestReg); 167f870fbc554ac862ad6d45cf97148739802a3ed12Evan Cheng else 168f870fbc554ac862ad6d45cf97148739802a3ed12Evan Cheng TII->copyRegToReg(MBB, AfterPHIsIt, DestReg, IncomingReg, RC, RC); 169bc40e898e153c9b81f246a7971eaac7b14446c49Chris Lattner 170ae94dda61a045cb77681940ecc25aba0d2763f74Bill Wendling // Update live variable information if there is any. 17153a79aaae988d9dc9d12af8970f8b8fe58cc478dChris Lattner LiveVariables *LV = getAnalysisToUpdate<LiveVariables>(); 17253a79aaae988d9dc9d12af8970f8b8fe58cc478dChris Lattner if (LV) { 17353a79aaae988d9dc9d12af8970f8b8fe58cc478dChris Lattner MachineInstr *PHICopy = prior(AfterPHIsIt); 174edf128a7fa90f2b0b7ee24741a04a7ae1ecd6f7eMisha Brukman 1753fefc182a00663bfadbcbe17711b6d08469c9727Evan Cheng // Increment use count of the newly created virtual register. 1763fefc182a00663bfadbcbe17711b6d08469c9727Evan Cheng LV->getVarInfo(IncomingReg).NumUses++; 1773fefc182a00663bfadbcbe17711b6d08469c9727Evan Cheng 17853a79aaae988d9dc9d12af8970f8b8fe58cc478dChris Lattner // Add information to LiveVariables to know that the incoming value is 17953a79aaae988d9dc9d12af8970f8b8fe58cc478dChris Lattner // killed. Note that because the value is defined in several places (once 180ae94dda61a045cb77681940ecc25aba0d2763f74Bill Wendling // each for each incoming block), the "def" block and instruction fields for 181ae94dda61a045cb77681940ecc25aba0d2763f74Bill Wendling // the VarInfo is not filled in. 18253a79aaae988d9dc9d12af8970f8b8fe58cc478dChris Lattner LV->addVirtualRegisterKilled(IncomingReg, PHICopy); 183bc40e898e153c9b81f246a7971eaac7b14446c49Chris Lattner 184ae94dda61a045cb77681940ecc25aba0d2763f74Bill Wendling // Since we are going to be deleting the PHI node, if it is the last use of 185ae94dda61a045cb77681940ecc25aba0d2763f74Bill Wendling // any registers, or if the value itself is dead, we need to move this 18653a79aaae988d9dc9d12af8970f8b8fe58cc478dChris Lattner // information over to the new copy we just inserted. 18753a79aaae988d9dc9d12af8970f8b8fe58cc478dChris Lattner LV->removeVirtualRegistersKilled(MPhi); 18853a79aaae988d9dc9d12af8970f8b8fe58cc478dChris Lattner 1896db0756f021a7b9c84d3bb7ae50498feb080a013Chris Lattner // If the result is dead, update LV. 1906130f66eaae89f8878590796977678afa8448926Evan Cheng if (MPhi->registerDefIsDead(DestReg)) { 1916db0756f021a7b9c84d3bb7ae50498feb080a013Chris Lattner LV->addVirtualRegisterDead(DestReg, PHICopy); 19253a79aaae988d9dc9d12af8970f8b8fe58cc478dChris Lattner LV->removeVirtualRegistersDead(MPhi); 193927ce5dfaea00453889080cd1c6daf3eb197ad74Chris Lattner } 194a018540807775703d630e9c92f9d8013d545599eOwen Anderson 195a018540807775703d630e9c92f9d8013d545599eOwen Anderson LV->getVarInfo(IncomingReg).UsedBlocks[MBB.getNumber()] = true; 19653a79aaae988d9dc9d12af8970f8b8fe58cc478dChris Lattner } 19753a79aaae988d9dc9d12af8970f8b8fe58cc478dChris Lattner 198ae94dda61a045cb77681940ecc25aba0d2763f74Bill Wendling // Adjust the VRegPHIUseCount map to account for the removal of this PHI node. 19953a79aaae988d9dc9d12af8970f8b8fe58cc478dChris Lattner for (unsigned i = 1; i != MPhi->getNumOperands(); i += 2) 2008aa797aa51cd4ea1ec6f46f4891a6897944b75b2Chris Lattner --VRegPHIUseCount[BBVRegPair(MPhi->getOperand(i + 1).getMBB(), 2018aa797aa51cd4ea1ec6f46f4891a6897944b75b2Chris Lattner MPhi->getOperand(i).getReg())]; 20253a79aaae988d9dc9d12af8970f8b8fe58cc478dChris Lattner 203ae94dda61a045cb77681940ecc25aba0d2763f74Bill Wendling // Now loop over all of the incoming arguments, changing them to copy into the 204ae94dda61a045cb77681940ecc25aba0d2763f74Bill Wendling // IncomingReg register in the corresponding predecessor basic block. 205576a27043d95d0b9b8a010bccfd38ed9c0afa739Evan Cheng SmallPtrSet<MachineBasicBlock*, 8> MBBsInsertedInto; 206f870fbc554ac862ad6d45cf97148739802a3ed12Evan Cheng for (int i = NumSrcs - 1; i >= 0; --i) { 207f870fbc554ac862ad6d45cf97148739802a3ed12Evan Cheng unsigned SrcReg = MPhi->getOperand(i*2+1).getReg(); 2086f0d024a534af18d9e60b3ea757376cd8a3a980eDan Gohman assert(TargetRegisterInfo::isVirtualRegister(SrcReg) && 2096db0756f021a7b9c84d3bb7ae50498feb080a013Chris Lattner "Machine PHI Operands must all be virtual registers!"); 21053a79aaae988d9dc9d12af8970f8b8fe58cc478dChris Lattner 211ae94dda61a045cb77681940ecc25aba0d2763f74Bill Wendling // If source is defined by an implicit def, there is no need to insert a 212ae94dda61a045cb77681940ecc25aba0d2763f74Bill Wendling // copy unless it's the only source. 213576a27043d95d0b9b8a010bccfd38ed9c0afa739Evan Cheng MachineInstr *DefMI = MRI->getVRegDef(SrcReg); 214576a27043d95d0b9b8a010bccfd38ed9c0afa739Evan Cheng if (DefMI->getOpcode() == TargetInstrInfo::IMPLICIT_DEF) { 215576a27043d95d0b9b8a010bccfd38ed9c0afa739Evan Cheng ImpDefs.insert(DefMI); 216576a27043d95d0b9b8a010bccfd38ed9c0afa739Evan Cheng continue; 217576a27043d95d0b9b8a010bccfd38ed9c0afa739Evan Cheng } 218576a27043d95d0b9b8a010bccfd38ed9c0afa739Evan Cheng 219ae94dda61a045cb77681940ecc25aba0d2763f74Bill Wendling // Get the MachineBasicBlock equivalent of the BasicBlock that is the source 220ae94dda61a045cb77681940ecc25aba0d2763f74Bill Wendling // path the PHI. 221f870fbc554ac862ad6d45cf97148739802a3ed12Evan Cheng MachineBasicBlock &opBlock = *MPhi->getOperand(i*2+2).getMBB(); 222bc40e898e153c9b81f246a7971eaac7b14446c49Chris Lattner 22353a79aaae988d9dc9d12af8970f8b8fe58cc478dChris Lattner // Check to make sure we haven't already emitted the copy for this block. 224ae94dda61a045cb77681940ecc25aba0d2763f74Bill Wendling // This can happen because PHI nodes may have multiple entries for the same 225ae94dda61a045cb77681940ecc25aba0d2763f74Bill Wendling // basic block. 226576a27043d95d0b9b8a010bccfd38ed9c0afa739Evan Cheng if (!MBBsInsertedInto.insert(&opBlock)) 2276db0756f021a7b9c84d3bb7ae50498feb080a013Chris Lattner continue; // If the copy has already been emitted, we're done. 2286db0756f021a7b9c84d3bb7ae50498feb080a013Chris Lattner 229ae94dda61a045cb77681940ecc25aba0d2763f74Bill Wendling // Find a safe location to insert the copy, this may be the first terminator 230ae94dda61a045cb77681940ecc25aba0d2763f74Bill Wendling // in the block (or end()). 231fc5423d561bb7624bf328e3ed554efce6e296cbcEvan Cheng MachineBasicBlock::iterator InsertPos = opBlock.getFirstTerminator(); 2326db0756f021a7b9c84d3bb7ae50498feb080a013Chris Lattner 2336db0756f021a7b9c84d3bb7ae50498feb080a013Chris Lattner // Insert the copy. 234576a27043d95d0b9b8a010bccfd38ed9c0afa739Evan Cheng TII->copyRegToReg(opBlock, InsertPos, IncomingReg, SrcReg, RC, RC); 2356db0756f021a7b9c84d3bb7ae50498feb080a013Chris Lattner 2366db0756f021a7b9c84d3bb7ae50498feb080a013Chris Lattner // Now update live variable information if we have it. Otherwise we're done 2376db0756f021a7b9c84d3bb7ae50498feb080a013Chris Lattner if (!LV) continue; 2386db0756f021a7b9c84d3bb7ae50498feb080a013Chris Lattner 239ae94dda61a045cb77681940ecc25aba0d2763f74Bill Wendling // We want to be able to insert a kill of the register if this PHI (aka, the 240ae94dda61a045cb77681940ecc25aba0d2763f74Bill Wendling // copy we just inserted) is the last use of the source value. Live 241ae94dda61a045cb77681940ecc25aba0d2763f74Bill Wendling // variable analysis conservatively handles this by saying that the value is 242ae94dda61a045cb77681940ecc25aba0d2763f74Bill Wendling // live until the end of the block the PHI entry lives in. If the value 243ae94dda61a045cb77681940ecc25aba0d2763f74Bill Wendling // really is dead at the PHI copy, there will be no successor blocks which 244ae94dda61a045cb77681940ecc25aba0d2763f74Bill Wendling // have the value live-in. 24553a79aaae988d9dc9d12af8970f8b8fe58cc478dChris Lattner // 246ae94dda61a045cb77681940ecc25aba0d2763f74Bill Wendling // Check to see if the copy is the last use, and if so, update the live 247ae94dda61a045cb77681940ecc25aba0d2763f74Bill Wendling // variables information so that it knows the copy source instruction kills 248ae94dda61a045cb77681940ecc25aba0d2763f74Bill Wendling // the incoming value. 2496db0756f021a7b9c84d3bb7ae50498feb080a013Chris Lattner LiveVariables::VarInfo &InRegVI = LV->getVarInfo(SrcReg); 250a018540807775703d630e9c92f9d8013d545599eOwen Anderson InRegVI.UsedBlocks[opBlock.getNumber()] = true; 2516db0756f021a7b9c84d3bb7ae50498feb080a013Chris Lattner 252ae94dda61a045cb77681940ecc25aba0d2763f74Bill Wendling // Loop over all of the successors of the basic block, checking to see if 253ae94dda61a045cb77681940ecc25aba0d2763f74Bill Wendling // the value is either live in the block, or if it is killed in the block. 254ae94dda61a045cb77681940ecc25aba0d2763f74Bill Wendling // Also check to see if this register is in use by another PHI node which 255ae94dda61a045cb77681940ecc25aba0d2763f74Bill Wendling // has not yet been eliminated. If so, it will be killed at an appropriate 256ae94dda61a045cb77681940ecc25aba0d2763f74Bill Wendling // point later. 2576db0756f021a7b9c84d3bb7ae50498feb080a013Chris Lattner 2586db0756f021a7b9c84d3bb7ae50498feb080a013Chris Lattner // Is it used by any PHI instructions in this block? 259ca756d2cf9bd88f210d61dd5f9776920a6178441Bill Wendling bool ValueIsLive = VRegPHIUseCount[BBVRegPair(&opBlock, SrcReg)] != 0; 2606db0756f021a7b9c84d3bb7ae50498feb080a013Chris Lattner 2616db0756f021a7b9c84d3bb7ae50498feb080a013Chris Lattner std::vector<MachineBasicBlock*> OpSuccBlocks; 2626db0756f021a7b9c84d3bb7ae50498feb080a013Chris Lattner 2636db0756f021a7b9c84d3bb7ae50498feb080a013Chris Lattner // Otherwise, scan successors, including the BB the PHI node lives in. 2646db0756f021a7b9c84d3bb7ae50498feb080a013Chris Lattner for (MachineBasicBlock::succ_iterator SI = opBlock.succ_begin(), 2656db0756f021a7b9c84d3bb7ae50498feb080a013Chris Lattner E = opBlock.succ_end(); SI != E && !ValueIsLive; ++SI) { 2666db0756f021a7b9c84d3bb7ae50498feb080a013Chris Lattner MachineBasicBlock *SuccMBB = *SI; 2676db0756f021a7b9c84d3bb7ae50498feb080a013Chris Lattner 2686db0756f021a7b9c84d3bb7ae50498feb080a013Chris Lattner // Is it alive in this successor? 2696db0756f021a7b9c84d3bb7ae50498feb080a013Chris Lattner unsigned SuccIdx = SuccMBB->getNumber(); 2706db0756f021a7b9c84d3bb7ae50498feb080a013Chris Lattner if (SuccIdx < InRegVI.AliveBlocks.size() && 2716db0756f021a7b9c84d3bb7ae50498feb080a013Chris Lattner InRegVI.AliveBlocks[SuccIdx]) { 2726db0756f021a7b9c84d3bb7ae50498feb080a013Chris Lattner ValueIsLive = true; 2736db0756f021a7b9c84d3bb7ae50498feb080a013Chris Lattner break; 27498719d7cdc693c077d179fe3461ce625d6faef34Chris Lattner } 2756db0756f021a7b9c84d3bb7ae50498feb080a013Chris Lattner 2766db0756f021a7b9c84d3bb7ae50498feb080a013Chris Lattner OpSuccBlocks.push_back(SuccMBB); 27753a79aaae988d9dc9d12af8970f8b8fe58cc478dChris Lattner } 27853a79aaae988d9dc9d12af8970f8b8fe58cc478dChris Lattner 2796db0756f021a7b9c84d3bb7ae50498feb080a013Chris Lattner // Check to see if this value is live because there is a use in a successor 2806db0756f021a7b9c84d3bb7ae50498feb080a013Chris Lattner // that kills it. 2816db0756f021a7b9c84d3bb7ae50498feb080a013Chris Lattner if (!ValueIsLive) { 2826db0756f021a7b9c84d3bb7ae50498feb080a013Chris Lattner switch (OpSuccBlocks.size()) { 2836db0756f021a7b9c84d3bb7ae50498feb080a013Chris Lattner case 1: { 2846db0756f021a7b9c84d3bb7ae50498feb080a013Chris Lattner MachineBasicBlock *MBB = OpSuccBlocks[0]; 2856db0756f021a7b9c84d3bb7ae50498feb080a013Chris Lattner for (unsigned i = 0, e = InRegVI.Kills.size(); i != e; ++i) 2866db0756f021a7b9c84d3bb7ae50498feb080a013Chris Lattner if (InRegVI.Kills[i]->getParent() == MBB) { 28753a79aaae988d9dc9d12af8970f8b8fe58cc478dChris Lattner ValueIsLive = true; 28853a79aaae988d9dc9d12af8970f8b8fe58cc478dChris Lattner break; 28953a79aaae988d9dc9d12af8970f8b8fe58cc478dChris Lattner } 2906db0756f021a7b9c84d3bb7ae50498feb080a013Chris Lattner break; 2916db0756f021a7b9c84d3bb7ae50498feb080a013Chris Lattner } 2926db0756f021a7b9c84d3bb7ae50498feb080a013Chris Lattner case 2: { 2936db0756f021a7b9c84d3bb7ae50498feb080a013Chris Lattner MachineBasicBlock *MBB1 = OpSuccBlocks[0], *MBB2 = OpSuccBlocks[1]; 2946db0756f021a7b9c84d3bb7ae50498feb080a013Chris Lattner for (unsigned i = 0, e = InRegVI.Kills.size(); i != e; ++i) 2956db0756f021a7b9c84d3bb7ae50498feb080a013Chris Lattner if (InRegVI.Kills[i]->getParent() == MBB1 || 2966db0756f021a7b9c84d3bb7ae50498feb080a013Chris Lattner InRegVI.Kills[i]->getParent() == MBB2) { 2976db0756f021a7b9c84d3bb7ae50498feb080a013Chris Lattner ValueIsLive = true; 2986db0756f021a7b9c84d3bb7ae50498feb080a013Chris Lattner break; 2996db0756f021a7b9c84d3bb7ae50498feb080a013Chris Lattner } 3006db0756f021a7b9c84d3bb7ae50498feb080a013Chris Lattner break; 301bc40e898e153c9b81f246a7971eaac7b14446c49Chris Lattner } 3026db0756f021a7b9c84d3bb7ae50498feb080a013Chris Lattner default: 3036db0756f021a7b9c84d3bb7ae50498feb080a013Chris Lattner std::sort(OpSuccBlocks.begin(), OpSuccBlocks.end()); 3046db0756f021a7b9c84d3bb7ae50498feb080a013Chris Lattner for (unsigned i = 0, e = InRegVI.Kills.size(); i != e; ++i) 3056db0756f021a7b9c84d3bb7ae50498feb080a013Chris Lattner if (std::binary_search(OpSuccBlocks.begin(), OpSuccBlocks.end(), 3066db0756f021a7b9c84d3bb7ae50498feb080a013Chris Lattner InRegVI.Kills[i]->getParent())) { 3076db0756f021a7b9c84d3bb7ae50498feb080a013Chris Lattner ValueIsLive = true; 3086db0756f021a7b9c84d3bb7ae50498feb080a013Chris Lattner break; 3096db0756f021a7b9c84d3bb7ae50498feb080a013Chris Lattner } 3106db0756f021a7b9c84d3bb7ae50498feb080a013Chris Lattner } 3116db0756f021a7b9c84d3bb7ae50498feb080a013Chris Lattner } 3126db0756f021a7b9c84d3bb7ae50498feb080a013Chris Lattner 313ae94dda61a045cb77681940ecc25aba0d2763f74Bill Wendling // Okay, if we now know that the value is not live out of the block, we can 314ae94dda61a045cb77681940ecc25aba0d2763f74Bill Wendling // add a kill marker in this block saying that it kills the incoming value! 3156db0756f021a7b9c84d3bb7ae50498feb080a013Chris Lattner if (!ValueIsLive) { 3162adfa7e9320e79859beb556367ea607a329866b3Chris Lattner // In our final twist, we have to decide which instruction kills the 317ae94dda61a045cb77681940ecc25aba0d2763f74Bill Wendling // register. In most cases this is the copy, however, the first 3182adfa7e9320e79859beb556367ea607a329866b3Chris Lattner // terminator instruction at the end of the block may also use the value. 3192adfa7e9320e79859beb556367ea607a329866b3Chris Lattner // In this case, we should mark *it* as being the killing block, not the 3202adfa7e9320e79859beb556367ea607a329866b3Chris Lattner // copy. 321576a27043d95d0b9b8a010bccfd38ed9c0afa739Evan Cheng MachineBasicBlock::iterator KillInst = prior(InsertPos); 322576a27043d95d0b9b8a010bccfd38ed9c0afa739Evan Cheng MachineBasicBlock::iterator Term = opBlock.getFirstTerminator(); 323576a27043d95d0b9b8a010bccfd38ed9c0afa739Evan Cheng if (Term != opBlock.end()) { 324576a27043d95d0b9b8a010bccfd38ed9c0afa739Evan Cheng if (Term->readsRegister(SrcReg)) 325576a27043d95d0b9b8a010bccfd38ed9c0afa739Evan Cheng KillInst = Term; 3262adfa7e9320e79859beb556367ea607a329866b3Chris Lattner 3272adfa7e9320e79859beb556367ea607a329866b3Chris Lattner // Check that no other terminators use values. 3282adfa7e9320e79859beb556367ea607a329866b3Chris Lattner#ifndef NDEBUG 329576a27043d95d0b9b8a010bccfd38ed9c0afa739Evan Cheng for (MachineBasicBlock::iterator TI = next(Term); TI != opBlock.end(); 3302adfa7e9320e79859beb556367ea607a329866b3Chris Lattner ++TI) { 331576a27043d95d0b9b8a010bccfd38ed9c0afa739Evan Cheng assert(!TI->readsRegister(SrcReg) && 3322adfa7e9320e79859beb556367ea607a329866b3Chris Lattner "Terminator instructions cannot use virtual registers unless" 3332adfa7e9320e79859beb556367ea607a329866b3Chris Lattner "they are the first terminator in a block!"); 3342adfa7e9320e79859beb556367ea607a329866b3Chris Lattner } 3352adfa7e9320e79859beb556367ea607a329866b3Chris Lattner#endif 3362adfa7e9320e79859beb556367ea607a329866b3Chris Lattner } 3372adfa7e9320e79859beb556367ea607a329866b3Chris Lattner 3382adfa7e9320e79859beb556367ea607a329866b3Chris Lattner // Finally, mark it killed. 3392adfa7e9320e79859beb556367ea607a329866b3Chris Lattner LV->addVirtualRegisterKilled(SrcReg, KillInst); 3406db0756f021a7b9c84d3bb7ae50498feb080a013Chris Lattner 3416db0756f021a7b9c84d3bb7ae50498feb080a013Chris Lattner // This vreg no longer lives all of the way through opBlock. 3426db0756f021a7b9c84d3bb7ae50498feb080a013Chris Lattner unsigned opBlockNum = opBlock.getNumber(); 3436db0756f021a7b9c84d3bb7ae50498feb080a013Chris Lattner if (opBlockNum < InRegVI.AliveBlocks.size()) 3446db0756f021a7b9c84d3bb7ae50498feb080a013Chris Lattner InRegVI.AliveBlocks[opBlockNum] = false; 345bc40e898e153c9b81f246a7971eaac7b14446c49Chris Lattner } 346bc40e898e153c9b81f246a7971eaac7b14446c49Chris Lattner } 34753a79aaae988d9dc9d12af8970f8b8fe58cc478dChris Lattner 34853a79aaae988d9dc9d12af8970f8b8fe58cc478dChris Lattner // Really delete the PHI instruction now! 34953a79aaae988d9dc9d12af8970f8b8fe58cc478dChris Lattner delete MPhi; 3506db0756f021a7b9c84d3bb7ae50498feb080a013Chris Lattner ++NumAtomic; 351bc40e898e153c9b81f246a7971eaac7b14446c49Chris Lattner} 352ca756d2cf9bd88f210d61dd5f9776920a6178441Bill Wendling 353ca756d2cf9bd88f210d61dd5f9776920a6178441Bill Wendling/// analyzePHINodes - Gather information about the PHI nodes in here. In 354ca756d2cf9bd88f210d61dd5f9776920a6178441Bill Wendling/// particular, we want to map the number of uses of a virtual register which is 355ca756d2cf9bd88f210d61dd5f9776920a6178441Bill Wendling/// used in a PHI node. We map that to the BB the vreg is coming from. This is 356ca756d2cf9bd88f210d61dd5f9776920a6178441Bill Wendling/// used later to determine when the vreg is killed in the BB. 357ca756d2cf9bd88f210d61dd5f9776920a6178441Bill Wendling/// 358ca756d2cf9bd88f210d61dd5f9776920a6178441Bill Wendlingvoid PNE::analyzePHINodes(const MachineFunction& Fn) { 359ca756d2cf9bd88f210d61dd5f9776920a6178441Bill Wendling for (MachineFunction::const_iterator I = Fn.begin(), E = Fn.end(); 360ca756d2cf9bd88f210d61dd5f9776920a6178441Bill Wendling I != E; ++I) 361ca756d2cf9bd88f210d61dd5f9776920a6178441Bill Wendling for (MachineBasicBlock::const_iterator BBI = I->begin(), BBE = I->end(); 362ca756d2cf9bd88f210d61dd5f9776920a6178441Bill Wendling BBI != BBE && BBI->getOpcode() == TargetInstrInfo::PHI; ++BBI) 363ca756d2cf9bd88f210d61dd5f9776920a6178441Bill Wendling for (unsigned i = 1, e = BBI->getNumOperands(); i != e; i += 2) 3648aa797aa51cd4ea1ec6f46f4891a6897944b75b2Chris Lattner ++VRegPHIUseCount[BBVRegPair(BBI->getOperand(i + 1).getMBB(), 3658aa797aa51cd4ea1ec6f46f4891a6897944b75b2Chris Lattner BBI->getOperand(i).getReg())]; 366ca756d2cf9bd88f210d61dd5f9776920a6178441Bill Wendling} 367