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" 17a474685d069a900ab931ee1540c9a79fdd6607a9Cameron Zwarich#include "PHIEliminationUtils.h" 18d7a10c8566c1f2e979f8f3abcaab441297a0c44cMisha Brukman#include "llvm/CodeGen/LiveVariables.h" 190742b59913a7760eb26f08121cd244a37e83e3b3Chris Lattner#include "llvm/CodeGen/Passes.h" 209aebb61daf4d787aa7dcff9e3caa89bac88e11d1Jakob Stoklund Olesen#include "llvm/CodeGen/MachineDominators.h" 21bc40e898e153c9b81f246a7971eaac7b14446c49Chris Lattner#include "llvm/CodeGen/MachineInstr.h" 22f870fbc554ac862ad6d45cf97148739802a3ed12Evan Cheng#include "llvm/CodeGen/MachineInstrBuilder.h" 2397b9b97853d7e4fbb5c8460ef28126013c76e9a9Evan Cheng#include "llvm/CodeGen/MachineLoopInfo.h" 2484bc5427d6883f73cfeae3da640acd011d35c006Chris Lattner#include "llvm/CodeGen/MachineRegisterInfo.h" 25518bb53485df640d7b7e3f6b0544099020c42aa7Chris Lattner#include "llvm/Target/TargetInstrInfo.h" 263e20475feebca3bfb29375ac7f3e5acbeb2a95c8Jakob Stoklund Olesen#include "llvm/Function.h" 27bc40e898e153c9b81f246a7971eaac7b14446c49Chris Lattner#include "llvm/Target/TargetMachine.h" 28576a27043d95d0b9b8a010bccfd38ed9c0afa739Evan Cheng#include "llvm/ADT/SmallPtrSet.h" 29551ccae044b0ff658fe629dd67edd5ffe75d10e8Reid Spencer#include "llvm/ADT/STLExtras.h" 306db0756f021a7b9c84d3bb7ae50498feb080a013Chris Lattner#include "llvm/ADT/Statistic.h" 316a951ac63fd6a9aa769c6d98b544b886e5b5d307Cameron Zwarich#include "llvm/Support/CommandLine.h" 32a4f0b3a084d120cfc5b5bb06f64b222f5cb72740Chris Lattner#include "llvm/Support/Compiler.h" 33f235f13931835b3335f3f2ff2d3060381b93626cJakob Stoklund Olesen#include "llvm/Support/Debug.h" 346db0756f021a7b9c84d3bb7ae50498feb080a013Chris Lattner#include <algorithm> 350742b59913a7760eb26f08121cd244a37e83e3b3Chris Lattnerusing namespace llvm; 36d0fde30ce850b78371fd1386338350591f9ff494Brian Gaeke 376a951ac63fd6a9aa769c6d98b544b886e5b5d307Cameron Zwarichstatic cl::opt<bool> 386a951ac63fd6a9aa769c6d98b544b886e5b5d307Cameron ZwarichDisableEdgeSplitting("disable-phi-elim-edge-splitting", cl::init(false), 396a951ac63fd6a9aa769c6d98b544b886e5b5d307Cameron Zwarich cl::Hidden, cl::desc("Disable critical edge splitting " 406a951ac63fd6a9aa769c6d98b544b886e5b5d307Cameron Zwarich "during PHI elimination")); 416a951ac63fd6a9aa769c6d98b544b886e5b5d307Cameron Zwarich 420a3fdd6e11cd351737b4451c05ec5d794e6855cfCameron Zwarichnamespace { 430a3fdd6e11cd351737b4451c05ec5d794e6855cfCameron Zwarich class PHIElimination : public MachineFunctionPass { 440a3fdd6e11cd351737b4451c05ec5d794e6855cfCameron Zwarich MachineRegisterInfo *MRI; // Machine register information 450a3fdd6e11cd351737b4451c05ec5d794e6855cfCameron Zwarich 460a3fdd6e11cd351737b4451c05ec5d794e6855cfCameron Zwarich public: 470a3fdd6e11cd351737b4451c05ec5d794e6855cfCameron Zwarich static char ID; // Pass identification, replacement for typeid 480a3fdd6e11cd351737b4451c05ec5d794e6855cfCameron Zwarich PHIElimination() : MachineFunctionPass(ID) { 490a3fdd6e11cd351737b4451c05ec5d794e6855cfCameron Zwarich initializePHIEliminationPass(*PassRegistry::getPassRegistry()); 500a3fdd6e11cd351737b4451c05ec5d794e6855cfCameron Zwarich } 510a3fdd6e11cd351737b4451c05ec5d794e6855cfCameron Zwarich 520a3fdd6e11cd351737b4451c05ec5d794e6855cfCameron Zwarich virtual bool runOnMachineFunction(MachineFunction &Fn); 530a3fdd6e11cd351737b4451c05ec5d794e6855cfCameron Zwarich virtual void getAnalysisUsage(AnalysisUsage &AU) const; 540a3fdd6e11cd351737b4451c05ec5d794e6855cfCameron Zwarich 550a3fdd6e11cd351737b4451c05ec5d794e6855cfCameron Zwarich private: 560a3fdd6e11cd351737b4451c05ec5d794e6855cfCameron Zwarich /// EliminatePHINodes - Eliminate phi nodes by inserting copy instructions 570a3fdd6e11cd351737b4451c05ec5d794e6855cfCameron Zwarich /// in predecessor basic blocks. 580a3fdd6e11cd351737b4451c05ec5d794e6855cfCameron Zwarich /// 590a3fdd6e11cd351737b4451c05ec5d794e6855cfCameron Zwarich bool EliminatePHINodes(MachineFunction &MF, MachineBasicBlock &MBB); 600a3fdd6e11cd351737b4451c05ec5d794e6855cfCameron Zwarich void LowerAtomicPHINode(MachineBasicBlock &MBB, 610a3fdd6e11cd351737b4451c05ec5d794e6855cfCameron Zwarich MachineBasicBlock::iterator AfterPHIsIt); 620a3fdd6e11cd351737b4451c05ec5d794e6855cfCameron Zwarich 630a3fdd6e11cd351737b4451c05ec5d794e6855cfCameron Zwarich /// analyzePHINodes - Gather information about the PHI nodes in 640a3fdd6e11cd351737b4451c05ec5d794e6855cfCameron Zwarich /// here. In particular, we want to map the number of uses of a virtual 650a3fdd6e11cd351737b4451c05ec5d794e6855cfCameron Zwarich /// register which is used in a PHI node. We map that to the BB the 660a3fdd6e11cd351737b4451c05ec5d794e6855cfCameron Zwarich /// vreg is coming from. This is used later to determine when the vreg 670a3fdd6e11cd351737b4451c05ec5d794e6855cfCameron Zwarich /// is killed in the BB. 680a3fdd6e11cd351737b4451c05ec5d794e6855cfCameron Zwarich /// 690a3fdd6e11cd351737b4451c05ec5d794e6855cfCameron Zwarich void analyzePHINodes(const MachineFunction& Fn); 700a3fdd6e11cd351737b4451c05ec5d794e6855cfCameron Zwarich 710a3fdd6e11cd351737b4451c05ec5d794e6855cfCameron Zwarich /// Split critical edges where necessary for good coalescer performance. 720a3fdd6e11cd351737b4451c05ec5d794e6855cfCameron Zwarich bool SplitPHIEdges(MachineFunction &MF, MachineBasicBlock &MBB, 730a3fdd6e11cd351737b4451c05ec5d794e6855cfCameron Zwarich LiveVariables &LV, MachineLoopInfo *MLI); 740a3fdd6e11cd351737b4451c05ec5d794e6855cfCameron Zwarich 750a3fdd6e11cd351737b4451c05ec5d794e6855cfCameron Zwarich typedef std::pair<unsigned, unsigned> BBVRegPair; 760a3fdd6e11cd351737b4451c05ec5d794e6855cfCameron Zwarich typedef DenseMap<BBVRegPair, unsigned> VRegPHIUse; 770a3fdd6e11cd351737b4451c05ec5d794e6855cfCameron Zwarich 780a3fdd6e11cd351737b4451c05ec5d794e6855cfCameron Zwarich VRegPHIUse VRegPHIUseCount; 790a3fdd6e11cd351737b4451c05ec5d794e6855cfCameron Zwarich 800a3fdd6e11cd351737b4451c05ec5d794e6855cfCameron Zwarich // Defs of PHI sources which are implicit_def. 810a3fdd6e11cd351737b4451c05ec5d794e6855cfCameron Zwarich SmallPtrSet<MachineInstr*, 4> ImpDefs; 820a3fdd6e11cd351737b4451c05ec5d794e6855cfCameron Zwarich 830a3fdd6e11cd351737b4451c05ec5d794e6855cfCameron Zwarich // Map reusable lowered PHI node -> incoming join register. 840a3fdd6e11cd351737b4451c05ec5d794e6855cfCameron Zwarich typedef DenseMap<MachineInstr*, unsigned, 850a3fdd6e11cd351737b4451c05ec5d794e6855cfCameron Zwarich MachineInstrExpressionTrait> LoweredPHIMap; 860a3fdd6e11cd351737b4451c05ec5d794e6855cfCameron Zwarich LoweredPHIMap LoweredPHIs; 870a3fdd6e11cd351737b4451c05ec5d794e6855cfCameron Zwarich }; 880a3fdd6e11cd351737b4451c05ec5d794e6855cfCameron Zwarich} 890a3fdd6e11cd351737b4451c05ec5d794e6855cfCameron Zwarich 90cd3245ac45c595da96bb768a55cddc356dff55feChris LattnerSTATISTIC(NumAtomic, "Number of atomic phis lowered"); 91117be03cc6cfb91d385938ed94a3cf877bd8c12aCameron ZwarichSTATISTIC(NumCriticalEdgesSplit, "Number of critical edges split"); 9274215fc29fa748e006c0309671555d5873bac56aJakob Stoklund OlesenSTATISTIC(NumReused, "Number of reused lowered phis"); 93f235f13931835b3335f3f2ff2d3060381b93626cJakob Stoklund Olesen 94fae02a2ab19abdf12854356e19aeb1da62a0b8eaLang Hameschar PHIElimination::ID = 0; 950a3fdd6e11cd351737b4451c05ec5d794e6855cfCameron Zwarichchar& llvm::PHIEliminationID = PHIElimination::ID; 96bc40e898e153c9b81f246a7971eaac7b14446c49Chris Lattner 978dd26253f54247e77e5accfdd70e7b4bf27b39c2Andrew TrickINITIALIZE_PASS_BEGIN(PHIElimination, "phi-node-elimination", 988dd26253f54247e77e5accfdd70e7b4bf27b39c2Andrew Trick "Eliminate PHI nodes for register allocation", 998dd26253f54247e77e5accfdd70e7b4bf27b39c2Andrew Trick false, false) 1008dd26253f54247e77e5accfdd70e7b4bf27b39c2Andrew TrickINITIALIZE_PASS_DEPENDENCY(LiveVariables) 1018dd26253f54247e77e5accfdd70e7b4bf27b39c2Andrew TrickINITIALIZE_PASS_END(PHIElimination, "phi-node-elimination", 1028dd26253f54247e77e5accfdd70e7b4bf27b39c2Andrew Trick "Eliminate PHI nodes for register allocation", false, false) 1038dd26253f54247e77e5accfdd70e7b4bf27b39c2Andrew Trick 1040a3fdd6e11cd351737b4451c05ec5d794e6855cfCameron Zwarichvoid PHIElimination::getAnalysisUsage(AnalysisUsage &AU) const { 105845012e6d31799c7fbd1193fa1af8ee2d12e9231Dan Gohman AU.addPreserved<LiveVariables>(); 1069aebb61daf4d787aa7dcff9e3caa89bac88e11d1Jakob Stoklund Olesen AU.addPreserved<MachineDominatorTree>(); 107148341cc9b60d7d88be9c07a2b32b436e0cd301dEvan Cheng AU.addPreserved<MachineLoopInfo>(); 108845012e6d31799c7fbd1193fa1af8ee2d12e9231Dan Gohman MachineFunctionPass::getAnalysisUsage(AU); 109845012e6d31799c7fbd1193fa1af8ee2d12e9231Dan Gohman} 110fae02a2ab19abdf12854356e19aeb1da62a0b8eaLang Hames 1110a3fdd6e11cd351737b4451c05ec5d794e6855cfCameron Zwarichbool PHIElimination::runOnMachineFunction(MachineFunction &MF) { 11228428cd6f31c1ea3cf4cea03e64189a4c32b84a3Evan Cheng MRI = &MF.getRegInfo(); 113576a27043d95d0b9b8a010bccfd38ed9c0afa739Evan Cheng 114576a27043d95d0b9b8a010bccfd38ed9c0afa739Evan Cheng bool Changed = false; 115576a27043d95d0b9b8a010bccfd38ed9c0afa739Evan Cheng 11673e7dced3892f2abb4344526147d4df0f62aee61Jakob Stoklund Olesen // This pass takes the function out of SSA form. 11773e7dced3892f2abb4344526147d4df0f62aee61Jakob Stoklund Olesen MRI->leaveSSA(); 11873e7dced3892f2abb4344526147d4df0f62aee61Jakob Stoklund Olesen 1193e20475feebca3bfb29375ac7f3e5acbeb2a95c8Jakob Stoklund Olesen // Split critical edges to help the coalescer 1206a951ac63fd6a9aa769c6d98b544b886e5b5d307Cameron Zwarich if (!DisableEdgeSplitting) { 1216a951ac63fd6a9aa769c6d98b544b886e5b5d307Cameron Zwarich if (LiveVariables *LV = getAnalysisIfAvailable<LiveVariables>()) { 1226a951ac63fd6a9aa769c6d98b544b886e5b5d307Cameron Zwarich MachineLoopInfo *MLI = getAnalysisIfAvailable<MachineLoopInfo>(); 1236a951ac63fd6a9aa769c6d98b544b886e5b5d307Cameron Zwarich for (MachineFunction::iterator I = MF.begin(), E = MF.end(); I != E; ++I) 1246a951ac63fd6a9aa769c6d98b544b886e5b5d307Cameron Zwarich Changed |= SplitPHIEdges(MF, *I, *LV, MLI); 1256a951ac63fd6a9aa769c6d98b544b886e5b5d307Cameron Zwarich } 126148341cc9b60d7d88be9c07a2b32b436e0cd301dEvan Cheng } 1273e20475feebca3bfb29375ac7f3e5acbeb2a95c8Jakob Stoklund Olesen 1283e20475feebca3bfb29375ac7f3e5acbeb2a95c8Jakob Stoklund Olesen // Populate VRegPHIUseCount 12928428cd6f31c1ea3cf4cea03e64189a4c32b84a3Evan Cheng analyzePHINodes(MF); 1303e20475feebca3bfb29375ac7f3e5acbeb2a95c8Jakob Stoklund Olesen 131576a27043d95d0b9b8a010bccfd38ed9c0afa739Evan Cheng // Eliminate PHI instructions by inserting copies into predecessor blocks. 13228428cd6f31c1ea3cf4cea03e64189a4c32b84a3Evan Cheng for (MachineFunction::iterator I = MF.begin(), E = MF.end(); I != E; ++I) 13328428cd6f31c1ea3cf4cea03e64189a4c32b84a3Evan Cheng Changed |= EliminatePHINodes(MF, *I); 134576a27043d95d0b9b8a010bccfd38ed9c0afa739Evan Cheng 135576a27043d95d0b9b8a010bccfd38ed9c0afa739Evan Cheng // Remove dead IMPLICIT_DEF instructions. 1363de8249078354d25b37b40e0f10b4f88226d3dd4Bill Wendling for (SmallPtrSet<MachineInstr*, 4>::iterator I = ImpDefs.begin(), 137576a27043d95d0b9b8a010bccfd38ed9c0afa739Evan Cheng E = ImpDefs.end(); I != E; ++I) { 138576a27043d95d0b9b8a010bccfd38ed9c0afa739Evan Cheng MachineInstr *DefMI = *I; 139576a27043d95d0b9b8a010bccfd38ed9c0afa739Evan Cheng unsigned DefReg = DefMI->getOperand(0).getReg(); 14048f2cb926e2512a1c4c33ca5a9e757de1c12036cEvan Cheng if (MRI->use_nodbg_empty(DefReg)) 141576a27043d95d0b9b8a010bccfd38ed9c0afa739Evan Cheng DefMI->eraseFromParent(); 142576a27043d95d0b9b8a010bccfd38ed9c0afa739Evan Cheng } 143576a27043d95d0b9b8a010bccfd38ed9c0afa739Evan Cheng 14474215fc29fa748e006c0309671555d5873bac56aJakob Stoklund Olesen // Clean up the lowered PHI instructions. 14574215fc29fa748e006c0309671555d5873bac56aJakob Stoklund Olesen for (LoweredPHIMap::iterator I = LoweredPHIs.begin(), E = LoweredPHIs.end(); 14674215fc29fa748e006c0309671555d5873bac56aJakob Stoklund Olesen I != E; ++I) 14728428cd6f31c1ea3cf4cea03e64189a4c32b84a3Evan Cheng MF.DeleteMachineInstr(I->first); 14874215fc29fa748e006c0309671555d5873bac56aJakob Stoklund Olesen 1493de8249078354d25b37b40e0f10b4f88226d3dd4Bill Wendling LoweredPHIs.clear(); 150576a27043d95d0b9b8a010bccfd38ed9c0afa739Evan Cheng ImpDefs.clear(); 151576a27043d95d0b9b8a010bccfd38ed9c0afa739Evan Cheng VRegPHIUseCount.clear(); 15228428cd6f31c1ea3cf4cea03e64189a4c32b84a3Evan Cheng 153576a27043d95d0b9b8a010bccfd38ed9c0afa739Evan Cheng return Changed; 154576a27043d95d0b9b8a010bccfd38ed9c0afa739Evan Cheng} 155576a27043d95d0b9b8a010bccfd38ed9c0afa739Evan Cheng 156bc40e898e153c9b81f246a7971eaac7b14446c49Chris Lattner/// EliminatePHINodes - Eliminate phi nodes by inserting copy instructions in 157bc40e898e153c9b81f246a7971eaac7b14446c49Chris Lattner/// predecessor basic blocks. 158bc40e898e153c9b81f246a7971eaac7b14446c49Chris Lattner/// 1590a3fdd6e11cd351737b4451c05ec5d794e6855cfCameron Zwarichbool PHIElimination::EliminatePHINodes(MachineFunction &MF, 160fae02a2ab19abdf12854356e19aeb1da62a0b8eaLang Hames MachineBasicBlock &MBB) { 161518bb53485df640d7b7e3f6b0544099020c42aa7Chris Lattner if (MBB.empty() || !MBB.front().isPHI()) 16253a79aaae988d9dc9d12af8970f8b8fe58cc478dChris Lattner return false; // Quick exit for basic blocks without PHIs. 163bc40e898e153c9b81f246a7971eaac7b14446c49Chris Lattner 164791f896d9f8a38b3806878867d61c114069b6195Chris Lattner // Get an iterator to the first instruction after the last PHI node (this may 16553a79aaae988d9dc9d12af8970f8b8fe58cc478dChris Lattner // also be the end of the basic block). 1662a7942926b753d185cb23ee29a91f2863eda4778Cameron Zwarich MachineBasicBlock::iterator AfterPHIsIt = MBB.SkipPHIsAndLabels(MBB.begin()); 167791f896d9f8a38b3806878867d61c114069b6195Chris Lattner 168518bb53485df640d7b7e3f6b0544099020c42aa7Chris Lattner while (MBB.front().isPHI()) 169ca756d2cf9bd88f210d61dd5f9776920a6178441Bill Wendling LowerAtomicPHINode(MBB, AfterPHIsIt); 170ca756d2cf9bd88f210d61dd5f9776920a6178441Bill Wendling 17153a79aaae988d9dc9d12af8970f8b8fe58cc478dChris Lattner return true; 17253a79aaae988d9dc9d12af8970f8b8fe58cc478dChris Lattner} 173edf128a7fa90f2b0b7ee24741a04a7ae1ecd6f7eMisha Brukman 1741b38ec83f07d5801035567160008cd7cb99a5c1aEvan Cheng/// isSourceDefinedByImplicitDef - Return true if all sources of the phi node 1751b38ec83f07d5801035567160008cd7cb99a5c1aEvan Cheng/// are implicit_def's. 176ae94dda61a045cb77681940ecc25aba0d2763f74Bill Wendlingstatic bool isSourceDefinedByImplicitDef(const MachineInstr *MPhi, 1771b38ec83f07d5801035567160008cd7cb99a5c1aEvan Cheng const MachineRegisterInfo *MRI) { 178b3e0a6d75c60f01df4fcee4b4309f06ce92a96c9Evan Cheng for (unsigned i = 1; i != MPhi->getNumOperands(); i += 2) { 179b3e0a6d75c60f01df4fcee4b4309f06ce92a96c9Evan Cheng unsigned SrcReg = MPhi->getOperand(i).getReg(); 180ae94dda61a045cb77681940ecc25aba0d2763f74Bill Wendling const MachineInstr *DefMI = MRI->getVRegDef(SrcReg); 181518bb53485df640d7b7e3f6b0544099020c42aa7Chris Lattner if (!DefMI || !DefMI->isImplicitDef()) 182b3e0a6d75c60f01df4fcee4b4309f06ce92a96c9Evan Cheng return false; 183b3e0a6d75c60f01df4fcee4b4309f06ce92a96c9Evan Cheng } 184b3e0a6d75c60f01df4fcee4b4309f06ce92a96c9Evan Cheng return true; 185f870fbc554ac862ad6d45cf97148739802a3ed12Evan Cheng} 186f870fbc554ac862ad6d45cf97148739802a3ed12Evan Cheng 187a5fec0dba34206274041543b5924d2565fb10f9bDuncan Sands 188fc0b80d9746e5fd4b45057ab814c67371fb0f9eaEvan Cheng 18953a79aaae988d9dc9d12af8970f8b8fe58cc478dChris Lattner/// LowerAtomicPHINode - Lower the PHI node at the top of the specified block, 19053a79aaae988d9dc9d12af8970f8b8fe58cc478dChris Lattner/// under the assuption that it needs to be lowered in a way that supports 19153a79aaae988d9dc9d12af8970f8b8fe58cc478dChris Lattner/// atomic execution of PHIs. This lowering method is always correct all of the 19253a79aaae988d9dc9d12af8970f8b8fe58cc478dChris Lattner/// time. 193e35e3c33dc5533dd1e8ab7d9f4039cc1429d56aaJakob Stoklund Olesen/// 1940a3fdd6e11cd351737b4451c05ec5d794e6855cfCameron Zwarichvoid PHIElimination::LowerAtomicPHINode( 195fae02a2ab19abdf12854356e19aeb1da62a0b8eaLang Hames MachineBasicBlock &MBB, 196fae02a2ab19abdf12854356e19aeb1da62a0b8eaLang Hames MachineBasicBlock::iterator AfterPHIsIt) { 19774215fc29fa748e006c0309671555d5873bac56aJakob Stoklund Olesen ++NumAtomic; 19853a79aaae988d9dc9d12af8970f8b8fe58cc478dChris Lattner // Unlink the PHI node from the basic block, but don't delete the PHI yet. 19953a79aaae988d9dc9d12af8970f8b8fe58cc478dChris Lattner MachineInstr *MPhi = MBB.remove(MBB.begin()); 20053a79aaae988d9dc9d12af8970f8b8fe58cc478dChris Lattner 201f870fbc554ac862ad6d45cf97148739802a3ed12Evan Cheng unsigned NumSrcs = (MPhi->getNumOperands() - 1) / 2; 20253a79aaae988d9dc9d12af8970f8b8fe58cc478dChris Lattner unsigned DestReg = MPhi->getOperand(0).getReg(); 2039ac248848faa839cff8e9f915c9b2c44295bc9f6Jakob Stoklund Olesen assert(MPhi->getOperand(0).getSubReg() == 0 && "Can't handle sub-reg PHIs"); 2049f1c8317a4676945b4961ddb9827ef2412551620Evan Cheng bool isDead = MPhi->getOperand(0).isDead(); 20553a79aaae988d9dc9d12af8970f8b8fe58cc478dChris Lattner 206ca756d2cf9bd88f210d61dd5f9776920a6178441Bill Wendling // Create a new register for the incoming PHI arguments. 20753a79aaae988d9dc9d12af8970f8b8fe58cc478dChris Lattner MachineFunction &MF = *MBB.getParent(); 2089f1c8317a4676945b4961ddb9827ef2412551620Evan Cheng unsigned IncomingReg = 0; 20974215fc29fa748e006c0309671555d5873bac56aJakob Stoklund Olesen bool reusedIncoming = false; // Is IncomingReg reused from an earlier PHI? 21053a79aaae988d9dc9d12af8970f8b8fe58cc478dChris Lattner 211ae94dda61a045cb77681940ecc25aba0d2763f74Bill Wendling // Insert a register to register copy at the top of the current block (but 21253a79aaae988d9dc9d12af8970f8b8fe58cc478dChris Lattner // after any remaining phi nodes) which copies the new incoming register 21353a79aaae988d9dc9d12af8970f8b8fe58cc478dChris Lattner // into the phi node destination. 214d10fd9791c20fd8368fa0ce94b626b769c6c8ba0Owen Anderson const TargetInstrInfo *TII = MF.getTarget().getInstrInfo(); 215b3e0a6d75c60f01df4fcee4b4309f06ce92a96c9Evan Cheng if (isSourceDefinedByImplicitDef(MPhi, MRI)) 2169f1c8317a4676945b4961ddb9827ef2412551620Evan Cheng // If all sources of a PHI node are implicit_def, just emit an 2179f1c8317a4676945b4961ddb9827ef2412551620Evan Cheng // implicit_def instead of a copy. 218d62e06c53b8b7e555617dc9b24b98c007d63de5dBill Wendling BuildMI(MBB, AfterPHIsIt, MPhi->getDebugLoc(), 219518bb53485df640d7b7e3f6b0544099020c42aa7Chris Lattner TII->get(TargetOpcode::IMPLICIT_DEF), DestReg); 2209f1c8317a4676945b4961ddb9827ef2412551620Evan Cheng else { 22174215fc29fa748e006c0309671555d5873bac56aJakob Stoklund Olesen // Can we reuse an earlier PHI node? This only happens for critical edges, 22274215fc29fa748e006c0309671555d5873bac56aJakob Stoklund Olesen // typically those created by tail duplication. 22374215fc29fa748e006c0309671555d5873bac56aJakob Stoklund Olesen unsigned &entry = LoweredPHIs[MPhi]; 22474215fc29fa748e006c0309671555d5873bac56aJakob Stoklund Olesen if (entry) { 22574215fc29fa748e006c0309671555d5873bac56aJakob Stoklund Olesen // An identical PHI node was already lowered. Reuse the incoming register. 22674215fc29fa748e006c0309671555d5873bac56aJakob Stoklund Olesen IncomingReg = entry; 22774215fc29fa748e006c0309671555d5873bac56aJakob Stoklund Olesen reusedIncoming = true; 22874215fc29fa748e006c0309671555d5873bac56aJakob Stoklund Olesen ++NumReused; 2294314268128be6d54c9a7f0709680e5a5b40f3ab3Jakob Stoklund Olesen DEBUG(dbgs() << "Reusing " << PrintReg(IncomingReg) << " for " << *MPhi); 23074215fc29fa748e006c0309671555d5873bac56aJakob Stoklund Olesen } else { 23192c1f72c548e6a5e793ef19a0b04910992115b6cJakob Stoklund Olesen const TargetRegisterClass *RC = MF.getRegInfo().getRegClass(DestReg); 23274215fc29fa748e006c0309671555d5873bac56aJakob Stoklund Olesen entry = IncomingReg = MF.getRegInfo().createVirtualRegister(RC); 23374215fc29fa748e006c0309671555d5873bac56aJakob Stoklund Olesen } 23492c1f72c548e6a5e793ef19a0b04910992115b6cJakob Stoklund Olesen BuildMI(MBB, AfterPHIsIt, MPhi->getDebugLoc(), 23592c1f72c548e6a5e793ef19a0b04910992115b6cJakob Stoklund Olesen TII->get(TargetOpcode::COPY), DestReg) 23692c1f72c548e6a5e793ef19a0b04910992115b6cJakob Stoklund Olesen .addReg(IncomingReg); 2379f1c8317a4676945b4961ddb9827ef2412551620Evan Cheng } 238bc40e898e153c9b81f246a7971eaac7b14446c49Chris Lattner 239ae94dda61a045cb77681940ecc25aba0d2763f74Bill Wendling // Update live variable information if there is any. 2401465d61bdd36cfd6021036a527895f0dd358e97dDuncan Sands LiveVariables *LV = getAnalysisIfAvailable<LiveVariables>(); 24153a79aaae988d9dc9d12af8970f8b8fe58cc478dChris Lattner if (LV) { 24253a79aaae988d9dc9d12af8970f8b8fe58cc478dChris Lattner MachineInstr *PHICopy = prior(AfterPHIsIt); 243edf128a7fa90f2b0b7ee24741a04a7ae1ecd6f7eMisha Brukman 2449f1c8317a4676945b4961ddb9827ef2412551620Evan Cheng if (IncomingReg) { 24574215fc29fa748e006c0309671555d5873bac56aJakob Stoklund Olesen LiveVariables::VarInfo &VI = LV->getVarInfo(IncomingReg); 24674215fc29fa748e006c0309671555d5873bac56aJakob Stoklund Olesen 2479f1c8317a4676945b4961ddb9827ef2412551620Evan Cheng // Increment use count of the newly created virtual register. 248dcfe5f30b5e262971f601a65bebcc0367fef56c5Jakob Stoklund Olesen LV->setPHIJoin(IncomingReg); 24974215fc29fa748e006c0309671555d5873bac56aJakob Stoklund Olesen 25074215fc29fa748e006c0309671555d5873bac56aJakob Stoklund Olesen // When we are reusing the incoming register, it may already have been 25174215fc29fa748e006c0309671555d5873bac56aJakob Stoklund Olesen // killed in this block. The old kill will also have been inserted at 25274215fc29fa748e006c0309671555d5873bac56aJakob Stoklund Olesen // AfterPHIsIt, so it appears before the current PHICopy. 25374215fc29fa748e006c0309671555d5873bac56aJakob Stoklund Olesen if (reusedIncoming) 25474215fc29fa748e006c0309671555d5873bac56aJakob Stoklund Olesen if (MachineInstr *OldKill = VI.findKill(&MBB)) { 255f78829794284afc7c243d9ad0591ae3a87172340David Greene DEBUG(dbgs() << "Remove old kill from " << *OldKill); 25674215fc29fa748e006c0309671555d5873bac56aJakob Stoklund Olesen LV->removeVirtualRegisterKilled(IncomingReg, OldKill); 25774215fc29fa748e006c0309671555d5873bac56aJakob Stoklund Olesen DEBUG(MBB.dump()); 25874215fc29fa748e006c0309671555d5873bac56aJakob Stoklund Olesen } 2599f1c8317a4676945b4961ddb9827ef2412551620Evan Cheng 2609f1c8317a4676945b4961ddb9827ef2412551620Evan Cheng // Add information to LiveVariables to know that the incoming value is 2619f1c8317a4676945b4961ddb9827ef2412551620Evan Cheng // killed. Note that because the value is defined in several places (once 2629f1c8317a4676945b4961ddb9827ef2412551620Evan Cheng // each for each incoming block), the "def" block and instruction fields 2639f1c8317a4676945b4961ddb9827ef2412551620Evan Cheng // for the VarInfo is not filled in. 2649f1c8317a4676945b4961ddb9827ef2412551620Evan Cheng LV->addVirtualRegisterKilled(IncomingReg, PHICopy); 2659f1c8317a4676945b4961ddb9827ef2412551620Evan Cheng } 266bc40e898e153c9b81f246a7971eaac7b14446c49Chris Lattner 267ae94dda61a045cb77681940ecc25aba0d2763f74Bill Wendling // Since we are going to be deleting the PHI node, if it is the last use of 268ae94dda61a045cb77681940ecc25aba0d2763f74Bill Wendling // any registers, or if the value itself is dead, we need to move this 26953a79aaae988d9dc9d12af8970f8b8fe58cc478dChris Lattner // information over to the new copy we just inserted. 27053a79aaae988d9dc9d12af8970f8b8fe58cc478dChris Lattner LV->removeVirtualRegistersKilled(MPhi); 27153a79aaae988d9dc9d12af8970f8b8fe58cc478dChris Lattner 2726db0756f021a7b9c84d3bb7ae50498feb080a013Chris Lattner // If the result is dead, update LV. 2739f1c8317a4676945b4961ddb9827ef2412551620Evan Cheng if (isDead) { 2746db0756f021a7b9c84d3bb7ae50498feb080a013Chris Lattner LV->addVirtualRegisterDead(DestReg, PHICopy); 2759f1c8317a4676945b4961ddb9827ef2412551620Evan Cheng LV->removeVirtualRegisterDead(DestReg, MPhi); 276927ce5dfaea00453889080cd1c6daf3eb197ad74Chris Lattner } 27753a79aaae988d9dc9d12af8970f8b8fe58cc478dChris Lattner } 27853a79aaae988d9dc9d12af8970f8b8fe58cc478dChris Lattner 279ae94dda61a045cb77681940ecc25aba0d2763f74Bill Wendling // Adjust the VRegPHIUseCount map to account for the removal of this PHI node. 28053a79aaae988d9dc9d12af8970f8b8fe58cc478dChris Lattner for (unsigned i = 1; i != MPhi->getNumOperands(); i += 2) 28174215fc29fa748e006c0309671555d5873bac56aJakob Stoklund Olesen --VRegPHIUseCount[BBVRegPair(MPhi->getOperand(i+1).getMBB()->getNumber(), 2828aa797aa51cd4ea1ec6f46f4891a6897944b75b2Chris Lattner MPhi->getOperand(i).getReg())]; 28353a79aaae988d9dc9d12af8970f8b8fe58cc478dChris Lattner 284ae94dda61a045cb77681940ecc25aba0d2763f74Bill Wendling // Now loop over all of the incoming arguments, changing them to copy into the 285ae94dda61a045cb77681940ecc25aba0d2763f74Bill Wendling // IncomingReg register in the corresponding predecessor basic block. 286576a27043d95d0b9b8a010bccfd38ed9c0afa739Evan Cheng SmallPtrSet<MachineBasicBlock*, 8> MBBsInsertedInto; 287f870fbc554ac862ad6d45cf97148739802a3ed12Evan Cheng for (int i = NumSrcs - 1; i >= 0; --i) { 288f870fbc554ac862ad6d45cf97148739802a3ed12Evan Cheng unsigned SrcReg = MPhi->getOperand(i*2+1).getReg(); 2899ac248848faa839cff8e9f915c9b2c44295bc9f6Jakob Stoklund Olesen unsigned SrcSubReg = MPhi->getOperand(i*2+1).getSubReg(); 2909ac248848faa839cff8e9f915c9b2c44295bc9f6Jakob Stoklund Olesen 2916f0d024a534af18d9e60b3ea757376cd8a3a980eDan Gohman assert(TargetRegisterInfo::isVirtualRegister(SrcReg) && 2926db0756f021a7b9c84d3bb7ae50498feb080a013Chris Lattner "Machine PHI Operands must all be virtual registers!"); 29353a79aaae988d9dc9d12af8970f8b8fe58cc478dChris Lattner 294287b8b0301bc6ec7eb70d23d242326a8766bb8ebLang Hames // Get the MachineBasicBlock equivalent of the BasicBlock that is the source 295287b8b0301bc6ec7eb70d23d242326a8766bb8ebLang Hames // path the PHI. 296287b8b0301bc6ec7eb70d23d242326a8766bb8ebLang Hames MachineBasicBlock &opBlock = *MPhi->getOperand(i*2+2).getMBB(); 297287b8b0301bc6ec7eb70d23d242326a8766bb8ebLang Hames 298ae94dda61a045cb77681940ecc25aba0d2763f74Bill Wendling // If source is defined by an implicit def, there is no need to insert a 2999f1c8317a4676945b4961ddb9827ef2412551620Evan Cheng // copy. 300576a27043d95d0b9b8a010bccfd38ed9c0afa739Evan Cheng MachineInstr *DefMI = MRI->getVRegDef(SrcReg); 301518bb53485df640d7b7e3f6b0544099020c42aa7Chris Lattner if (DefMI->isImplicitDef()) { 302576a27043d95d0b9b8a010bccfd38ed9c0afa739Evan Cheng ImpDefs.insert(DefMI); 303576a27043d95d0b9b8a010bccfd38ed9c0afa739Evan Cheng continue; 304576a27043d95d0b9b8a010bccfd38ed9c0afa739Evan Cheng } 305576a27043d95d0b9b8a010bccfd38ed9c0afa739Evan Cheng 30653a79aaae988d9dc9d12af8970f8b8fe58cc478dChris Lattner // Check to make sure we haven't already emitted the copy for this block. 307ae94dda61a045cb77681940ecc25aba0d2763f74Bill Wendling // This can happen because PHI nodes may have multiple entries for the same 308ae94dda61a045cb77681940ecc25aba0d2763f74Bill Wendling // basic block. 309576a27043d95d0b9b8a010bccfd38ed9c0afa739Evan Cheng if (!MBBsInsertedInto.insert(&opBlock)) 3106db0756f021a7b9c84d3bb7ae50498feb080a013Chris Lattner continue; // If the copy has already been emitted, we're done. 311e35e3c33dc5533dd1e8ab7d9f4039cc1429d56aaJakob Stoklund Olesen 312ae94dda61a045cb77681940ecc25aba0d2763f74Bill Wendling // Find a safe location to insert the copy, this may be the first terminator 313ae94dda61a045cb77681940ecc25aba0d2763f74Bill Wendling // in the block (or end()). 3141222287543a5b5917f8c31aa8c88d740f70222d9Jakob Stoklund Olesen MachineBasicBlock::iterator InsertPos = 315a474685d069a900ab931ee1540c9a79fdd6607a9Cameron Zwarich findPHICopyInsertPoint(&opBlock, &MBB, SrcReg); 316fc0b80d9746e5fd4b45057ab814c67371fb0f9eaEvan Cheng 3176db0756f021a7b9c84d3bb7ae50498feb080a013Chris Lattner // Insert the copy. 31874215fc29fa748e006c0309671555d5873bac56aJakob Stoklund Olesen if (!reusedIncoming && IncomingReg) 31992c1f72c548e6a5e793ef19a0b04910992115b6cJakob Stoklund Olesen BuildMI(opBlock, InsertPos, MPhi->getDebugLoc(), 3209ac248848faa839cff8e9f915c9b2c44295bc9f6Jakob Stoklund Olesen TII->get(TargetOpcode::COPY), IncomingReg).addReg(SrcReg, 0, SrcSubReg); 3216db0756f021a7b9c84d3bb7ae50498feb080a013Chris Lattner 3226db0756f021a7b9c84d3bb7ae50498feb080a013Chris Lattner // Now update live variable information if we have it. Otherwise we're done 3236db0756f021a7b9c84d3bb7ae50498feb080a013Chris Lattner if (!LV) continue; 324e35e3c33dc5533dd1e8ab7d9f4039cc1429d56aaJakob Stoklund Olesen 325ae94dda61a045cb77681940ecc25aba0d2763f74Bill Wendling // We want to be able to insert a kill of the register if this PHI (aka, the 326ae94dda61a045cb77681940ecc25aba0d2763f74Bill Wendling // copy we just inserted) is the last use of the source value. Live 327ae94dda61a045cb77681940ecc25aba0d2763f74Bill Wendling // variable analysis conservatively handles this by saying that the value is 328ae94dda61a045cb77681940ecc25aba0d2763f74Bill Wendling // live until the end of the block the PHI entry lives in. If the value 329ae94dda61a045cb77681940ecc25aba0d2763f74Bill Wendling // really is dead at the PHI copy, there will be no successor blocks which 330ae94dda61a045cb77681940ecc25aba0d2763f74Bill Wendling // have the value live-in. 331e35e3c33dc5533dd1e8ab7d9f4039cc1429d56aaJakob Stoklund Olesen 332ae94dda61a045cb77681940ecc25aba0d2763f74Bill Wendling // Also check to see if this register is in use by another PHI node which 333ae94dda61a045cb77681940ecc25aba0d2763f74Bill Wendling // has not yet been eliminated. If so, it will be killed at an appropriate 334ae94dda61a045cb77681940ecc25aba0d2763f74Bill Wendling // point later. 3356db0756f021a7b9c84d3bb7ae50498feb080a013Chris Lattner 3366db0756f021a7b9c84d3bb7ae50498feb080a013Chris Lattner // Is it used by any PHI instructions in this block? 33774215fc29fa748e006c0309671555d5873bac56aJakob Stoklund Olesen bool ValueIsUsed = VRegPHIUseCount[BBVRegPair(opBlock.getNumber(), SrcReg)]; 3386db0756f021a7b9c84d3bb7ae50498feb080a013Chris Lattner 339ae94dda61a045cb77681940ecc25aba0d2763f74Bill Wendling // Okay, if we now know that the value is not live out of the block, we can 340ae94dda61a045cb77681940ecc25aba0d2763f74Bill Wendling // add a kill marker in this block saying that it kills the incoming value! 3418f72235a77e7ac262471936ea0ad2a3467d18871Jakob Stoklund Olesen if (!ValueIsUsed && !LV->isLiveOut(SrcReg, opBlock)) { 3422adfa7e9320e79859beb556367ea607a329866b3Chris Lattner // In our final twist, we have to decide which instruction kills the 343ae94dda61a045cb77681940ecc25aba0d2763f74Bill Wendling // register. In most cases this is the copy, however, the first 3442adfa7e9320e79859beb556367ea607a329866b3Chris Lattner // terminator instruction at the end of the block may also use the value. 3452adfa7e9320e79859beb556367ea607a329866b3Chris Lattner // In this case, we should mark *it* as being the killing block, not the 3462adfa7e9320e79859beb556367ea607a329866b3Chris Lattner // copy. 34774215fc29fa748e006c0309671555d5873bac56aJakob Stoklund Olesen MachineBasicBlock::iterator KillInst; 348576a27043d95d0b9b8a010bccfd38ed9c0afa739Evan Cheng MachineBasicBlock::iterator Term = opBlock.getFirstTerminator(); 34974215fc29fa748e006c0309671555d5873bac56aJakob Stoklund Olesen if (Term != opBlock.end() && Term->readsRegister(SrcReg)) { 35074215fc29fa748e006c0309671555d5873bac56aJakob Stoklund Olesen KillInst = Term; 351e35e3c33dc5533dd1e8ab7d9f4039cc1429d56aaJakob Stoklund Olesen 3522adfa7e9320e79859beb556367ea607a329866b3Chris Lattner // Check that no other terminators use values. 3532adfa7e9320e79859beb556367ea607a329866b3Chris Lattner#ifndef NDEBUG 3547896c9f436a4eda5ec15e882a7505ba482a2fcd0Chris Lattner for (MachineBasicBlock::iterator TI = llvm::next(Term); 3557896c9f436a4eda5ec15e882a7505ba482a2fcd0Chris Lattner TI != opBlock.end(); ++TI) { 35604223909b74fd0634ba26d434fa7fdf2f3c7444fJakob Stoklund Olesen if (TI->isDebugValue()) 35704223909b74fd0634ba26d434fa7fdf2f3c7444fJakob Stoklund Olesen continue; 358576a27043d95d0b9b8a010bccfd38ed9c0afa739Evan Cheng assert(!TI->readsRegister(SrcReg) && 3592adfa7e9320e79859beb556367ea607a329866b3Chris Lattner "Terminator instructions cannot use virtual registers unless" 3602adfa7e9320e79859beb556367ea607a329866b3Chris Lattner "they are the first terminator in a block!"); 3612adfa7e9320e79859beb556367ea607a329866b3Chris Lattner } 3622adfa7e9320e79859beb556367ea607a329866b3Chris Lattner#endif 36374215fc29fa748e006c0309671555d5873bac56aJakob Stoklund Olesen } else if (reusedIncoming || !IncomingReg) { 36474215fc29fa748e006c0309671555d5873bac56aJakob Stoklund Olesen // We may have to rewind a bit if we didn't insert a copy this time. 36574215fc29fa748e006c0309671555d5873bac56aJakob Stoklund Olesen KillInst = Term; 36604223909b74fd0634ba26d434fa7fdf2f3c7444fJakob Stoklund Olesen while (KillInst != opBlock.begin()) { 36704223909b74fd0634ba26d434fa7fdf2f3c7444fJakob Stoklund Olesen --KillInst; 36804223909b74fd0634ba26d434fa7fdf2f3c7444fJakob Stoklund Olesen if (KillInst->isDebugValue()) 36904223909b74fd0634ba26d434fa7fdf2f3c7444fJakob Stoklund Olesen continue; 37004223909b74fd0634ba26d434fa7fdf2f3c7444fJakob Stoklund Olesen if (KillInst->readsRegister(SrcReg)) 37174215fc29fa748e006c0309671555d5873bac56aJakob Stoklund Olesen break; 37204223909b74fd0634ba26d434fa7fdf2f3c7444fJakob Stoklund Olesen } 37374215fc29fa748e006c0309671555d5873bac56aJakob Stoklund Olesen } else { 37474215fc29fa748e006c0309671555d5873bac56aJakob Stoklund Olesen // We just inserted this copy. 37574215fc29fa748e006c0309671555d5873bac56aJakob Stoklund Olesen KillInst = prior(InsertPos); 3762adfa7e9320e79859beb556367ea607a329866b3Chris Lattner } 37774215fc29fa748e006c0309671555d5873bac56aJakob Stoklund Olesen assert(KillInst->readsRegister(SrcReg) && "Cannot find kill instruction"); 378e35e3c33dc5533dd1e8ab7d9f4039cc1429d56aaJakob Stoklund Olesen 3792adfa7e9320e79859beb556367ea607a329866b3Chris Lattner // Finally, mark it killed. 3802adfa7e9320e79859beb556367ea607a329866b3Chris Lattner LV->addVirtualRegisterKilled(SrcReg, KillInst); 3816db0756f021a7b9c84d3bb7ae50498feb080a013Chris Lattner 3826db0756f021a7b9c84d3bb7ae50498feb080a013Chris Lattner // This vreg no longer lives all of the way through opBlock. 3836db0756f021a7b9c84d3bb7ae50498feb080a013Chris Lattner unsigned opBlockNum = opBlock.getNumber(); 384e35e3c33dc5533dd1e8ab7d9f4039cc1429d56aaJakob Stoklund Olesen LV->getVarInfo(SrcReg).AliveBlocks.reset(opBlockNum); 385bc40e898e153c9b81f246a7971eaac7b14446c49Chris Lattner } 386bc40e898e153c9b81f246a7971eaac7b14446c49Chris Lattner } 387e35e3c33dc5533dd1e8ab7d9f4039cc1429d56aaJakob Stoklund Olesen 38874215fc29fa748e006c0309671555d5873bac56aJakob Stoklund Olesen // Really delete the PHI instruction now, if it is not in the LoweredPHIs map. 38974215fc29fa748e006c0309671555d5873bac56aJakob Stoklund Olesen if (reusedIncoming || !IncomingReg) 39074215fc29fa748e006c0309671555d5873bac56aJakob Stoklund Olesen MF.DeleteMachineInstr(MPhi); 391bc40e898e153c9b81f246a7971eaac7b14446c49Chris Lattner} 392ca756d2cf9bd88f210d61dd5f9776920a6178441Bill Wendling 393ca756d2cf9bd88f210d61dd5f9776920a6178441Bill Wendling/// analyzePHINodes - Gather information about the PHI nodes in here. In 394ca756d2cf9bd88f210d61dd5f9776920a6178441Bill Wendling/// particular, we want to map the number of uses of a virtual register which is 395ca756d2cf9bd88f210d61dd5f9776920a6178441Bill Wendling/// used in a PHI node. We map that to the BB the vreg is coming from. This is 396ca756d2cf9bd88f210d61dd5f9776920a6178441Bill Wendling/// used later to determine when the vreg is killed in the BB. 397ca756d2cf9bd88f210d61dd5f9776920a6178441Bill Wendling/// 3980a3fdd6e11cd351737b4451c05ec5d794e6855cfCameron Zwarichvoid PHIElimination::analyzePHINodes(const MachineFunction& MF) { 39928428cd6f31c1ea3cf4cea03e64189a4c32b84a3Evan Cheng for (MachineFunction::const_iterator I = MF.begin(), E = MF.end(); 400ca756d2cf9bd88f210d61dd5f9776920a6178441Bill Wendling I != E; ++I) 401ca756d2cf9bd88f210d61dd5f9776920a6178441Bill Wendling for (MachineBasicBlock::const_iterator BBI = I->begin(), BBE = I->end(); 402518bb53485df640d7b7e3f6b0544099020c42aa7Chris Lattner BBI != BBE && BBI->isPHI(); ++BBI) 403ca756d2cf9bd88f210d61dd5f9776920a6178441Bill Wendling for (unsigned i = 1, e = BBI->getNumOperands(); i != e; i += 2) 40474215fc29fa748e006c0309671555d5873bac56aJakob Stoklund Olesen ++VRegPHIUseCount[BBVRegPair(BBI->getOperand(i+1).getMBB()->getNumber(), 4058aa797aa51cd4ea1ec6f46f4891a6897944b75b2Chris Lattner BBI->getOperand(i).getReg())]; 406ca756d2cf9bd88f210d61dd5f9776920a6178441Bill Wendling} 407e35e3c33dc5533dd1e8ab7d9f4039cc1429d56aaJakob Stoklund Olesen 4080a3fdd6e11cd351737b4451c05ec5d794e6855cfCameron Zwarichbool PHIElimination::SplitPHIEdges(MachineFunction &MF, 40961a733434d9ee6518b8ddb116594bef7206cb627Cameron Zwarich MachineBasicBlock &MBB, 41061a733434d9ee6518b8ddb116594bef7206cb627Cameron Zwarich LiveVariables &LV, 41161a733434d9ee6518b8ddb116594bef7206cb627Cameron Zwarich MachineLoopInfo *MLI) { 412518bb53485df640d7b7e3f6b0544099020c42aa7Chris Lattner if (MBB.empty() || !MBB.front().isPHI() || MBB.isLandingPad()) 4133e20475feebca3bfb29375ac7f3e5acbeb2a95c8Jakob Stoklund Olesen return false; // Quick exit for basic blocks without PHIs. 4140257dd375d64da978887d0c1e97ab3560d7597ceJakob Stoklund Olesen 41597b9b97853d7e4fbb5c8460ef28126013c76e9a9Evan Cheng bool Changed = false; 4167c2a4a30e0e16762c75adacebd05ec9fcbccf16bEvan Cheng for (MachineBasicBlock::iterator BBI = MBB.begin(), BBE = MBB.end(); 417518bb53485df640d7b7e3f6b0544099020c42aa7Chris Lattner BBI != BBE && BBI->isPHI(); ++BBI) { 418f235f13931835b3335f3f2ff2d3060381b93626cJakob Stoklund Olesen for (unsigned i = 1, e = BBI->getNumOperands(); i != e; i += 2) { 419f235f13931835b3335f3f2ff2d3060381b93626cJakob Stoklund Olesen unsigned Reg = BBI->getOperand(i).getReg(); 420f235f13931835b3335f3f2ff2d3060381b93626cJakob Stoklund Olesen MachineBasicBlock *PreMBB = BBI->getOperand(i+1).getMBB(); 421f235f13931835b3335f3f2ff2d3060381b93626cJakob Stoklund Olesen // We break edges when registers are live out from the predecessor block 4223e20475feebca3bfb29375ac7f3e5acbeb2a95c8Jakob Stoklund Olesen // (not considering PHI nodes). If the register is live in to this block 4233e20475feebca3bfb29375ac7f3e5acbeb2a95c8Jakob Stoklund Olesen // anyway, we would gain nothing from splitting. 424e008384508342a2dec110eafaa87d93614976990Evan Cheng // Avoid splitting backedges of loops. It would introduce small 425e008384508342a2dec110eafaa87d93614976990Evan Cheng // out-of-line blocks into the loop which is very bad for code placement. 426e008384508342a2dec110eafaa87d93614976990Evan Cheng if (PreMBB != &MBB && 427e008384508342a2dec110eafaa87d93614976990Evan Cheng !LV.isLiveIn(Reg, MBB) && LV.isLiveOut(Reg, *PreMBB)) { 428148341cc9b60d7d88be9c07a2b32b436e0cd301dEvan Cheng if (!MLI || 429148341cc9b60d7d88be9c07a2b32b436e0cd301dEvan Cheng !(MLI->getLoopFor(PreMBB) == MLI->getLoopFor(&MBB) && 430117be03cc6cfb91d385938ed94a3cf877bd8c12aCameron Zwarich MLI->isLoopHeader(&MBB))) { 431117be03cc6cfb91d385938ed94a3cf877bd8c12aCameron Zwarich if (PreMBB->SplitCriticalEdge(&MBB, this)) { 432117be03cc6cfb91d385938ed94a3cf877bd8c12aCameron Zwarich Changed = true; 433117be03cc6cfb91d385938ed94a3cf877bd8c12aCameron Zwarich ++NumCriticalEdgesSplit; 434117be03cc6cfb91d385938ed94a3cf877bd8c12aCameron Zwarich } 435117be03cc6cfb91d385938ed94a3cf877bd8c12aCameron Zwarich } 436e008384508342a2dec110eafaa87d93614976990Evan Cheng } 437f235f13931835b3335f3f2ff2d3060381b93626cJakob Stoklund Olesen } 438f235f13931835b3335f3f2ff2d3060381b93626cJakob Stoklund Olesen } 439688521ca6f936cb51549b0d505aa89746561263bCameron Zwarich return Changed; 440f235f13931835b3335f3f2ff2d3060381b93626cJakob Stoklund Olesen} 441