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" 17d04a8d4b33ff316ca4cf961e06c9e312eff8e64fChandler Carruth#include "llvm/CodeGen/Passes.h" 18a474685d069a900ab931ee1540c9a79fdd6607a9Cameron Zwarich#include "PHIEliminationUtils.h" 19d04a8d4b33ff316ca4cf961e06c9e312eff8e64fChandler Carruth#include "llvm/ADT/STLExtras.h" 20d04a8d4b33ff316ca4cf961e06c9e312eff8e64fChandler Carruth#include "llvm/ADT/SmallPtrSet.h" 21d04a8d4b33ff316ca4cf961e06c9e312eff8e64fChandler Carruth#include "llvm/ADT/Statistic.h" 22b7cfac32f32f17e64a5addfdb833702160650f14Cameron Zwarich#include "llvm/CodeGen/LiveIntervalAnalysis.h" 23d7a10c8566c1f2e979f8f3abcaab441297a0c44cMisha Brukman#include "llvm/CodeGen/LiveVariables.h" 249aebb61daf4d787aa7dcff9e3caa89bac88e11d1Jakob Stoklund Olesen#include "llvm/CodeGen/MachineDominators.h" 25bc40e898e153c9b81f246a7971eaac7b14446c49Chris Lattner#include "llvm/CodeGen/MachineInstr.h" 26f870fbc554ac862ad6d45cf97148739802a3ed12Evan Cheng#include "llvm/CodeGen/MachineInstrBuilder.h" 2797b9b97853d7e4fbb5c8460ef28126013c76e9a9Evan Cheng#include "llvm/CodeGen/MachineLoopInfo.h" 2884bc5427d6883f73cfeae3da640acd011d35c006Chris Lattner#include "llvm/CodeGen/MachineRegisterInfo.h" 290b8c9a80f20772c3793201ab5b251d3520b9cea3Chandler Carruth#include "llvm/IR/Function.h" 306a951ac63fd6a9aa769c6d98b544b886e5b5d307Cameron Zwarich#include "llvm/Support/CommandLine.h" 31a4f0b3a084d120cfc5b5bb06f64b222f5cb72740Chris Lattner#include "llvm/Support/Compiler.h" 32f235f13931835b3335f3f2ff2d3060381b93626cJakob Stoklund Olesen#include "llvm/Support/Debug.h" 33d04a8d4b33ff316ca4cf961e06c9e312eff8e64fChandler Carruth#include "llvm/Target/TargetInstrInfo.h" 34d04a8d4b33ff316ca4cf961e06c9e312eff8e64fChandler Carruth#include "llvm/Target/TargetMachine.h" 356db0756f021a7b9c84d3bb7ae50498feb080a013Chris Lattner#include <algorithm> 360742b59913a7760eb26f08121cd244a37e83e3b3Chris Lattnerusing namespace llvm; 37d0fde30ce850b78371fd1386338350591f9ff494Brian Gaeke 386a951ac63fd6a9aa769c6d98b544b886e5b5d307Cameron Zwarichstatic cl::opt<bool> 396a951ac63fd6a9aa769c6d98b544b886e5b5d307Cameron ZwarichDisableEdgeSplitting("disable-phi-elim-edge-splitting", cl::init(false), 406a951ac63fd6a9aa769c6d98b544b886e5b5d307Cameron Zwarich cl::Hidden, cl::desc("Disable critical edge splitting " 416a951ac63fd6a9aa769c6d98b544b886e5b5d307Cameron Zwarich "during PHI elimination")); 426a951ac63fd6a9aa769c6d98b544b886e5b5d307Cameron Zwarich 435758a711f4e593d1daff3bae0fa9d694e5980719Cameron Zwarichstatic cl::opt<bool> 445758a711f4e593d1daff3bae0fa9d694e5980719Cameron ZwarichSplitAllCriticalEdges("phi-elim-split-all-critical-edges", cl::init(false), 455758a711f4e593d1daff3bae0fa9d694e5980719Cameron Zwarich cl::Hidden, cl::desc("Split all critical edges during " 465758a711f4e593d1daff3bae0fa9d694e5980719Cameron Zwarich "PHI elimination")); 475758a711f4e593d1daff3bae0fa9d694e5980719Cameron Zwarich 480a3fdd6e11cd351737b4451c05ec5d794e6855cfCameron Zwarichnamespace { 490a3fdd6e11cd351737b4451c05ec5d794e6855cfCameron Zwarich class PHIElimination : public MachineFunctionPass { 500a3fdd6e11cd351737b4451c05ec5d794e6855cfCameron Zwarich MachineRegisterInfo *MRI; // Machine register information 51fe0fd35d5339467fedd59f0cf5bdadb163a8d766Cameron Zwarich LiveVariables *LV; 52b7cfac32f32f17e64a5addfdb833702160650f14Cameron Zwarich LiveIntervals *LIS; 530a3fdd6e11cd351737b4451c05ec5d794e6855cfCameron Zwarich 540a3fdd6e11cd351737b4451c05ec5d794e6855cfCameron Zwarich public: 550a3fdd6e11cd351737b4451c05ec5d794e6855cfCameron Zwarich static char ID; // Pass identification, replacement for typeid 560a3fdd6e11cd351737b4451c05ec5d794e6855cfCameron Zwarich PHIElimination() : MachineFunctionPass(ID) { 570a3fdd6e11cd351737b4451c05ec5d794e6855cfCameron Zwarich initializePHIEliminationPass(*PassRegistry::getPassRegistry()); 580a3fdd6e11cd351737b4451c05ec5d794e6855cfCameron Zwarich } 590a3fdd6e11cd351737b4451c05ec5d794e6855cfCameron Zwarich 600a3fdd6e11cd351737b4451c05ec5d794e6855cfCameron Zwarich virtual bool runOnMachineFunction(MachineFunction &Fn); 610a3fdd6e11cd351737b4451c05ec5d794e6855cfCameron Zwarich virtual void getAnalysisUsage(AnalysisUsage &AU) const; 620a3fdd6e11cd351737b4451c05ec5d794e6855cfCameron Zwarich 630a3fdd6e11cd351737b4451c05ec5d794e6855cfCameron Zwarich private: 640a3fdd6e11cd351737b4451c05ec5d794e6855cfCameron Zwarich /// EliminatePHINodes - Eliminate phi nodes by inserting copy instructions 650a3fdd6e11cd351737b4451c05ec5d794e6855cfCameron Zwarich /// in predecessor basic blocks. 660a3fdd6e11cd351737b4451c05ec5d794e6855cfCameron Zwarich /// 670a3fdd6e11cd351737b4451c05ec5d794e6855cfCameron Zwarich bool EliminatePHINodes(MachineFunction &MF, MachineBasicBlock &MBB); 6802513c05c6333e2f7418b1327eded162b2791828Cameron Zwarich void LowerPHINode(MachineBasicBlock &MBB, 6903fae50cfa5631349fbd47f4c232fc78f5b3b8afCameron Zwarich MachineBasicBlock::iterator LastPHIIt); 700a3fdd6e11cd351737b4451c05ec5d794e6855cfCameron Zwarich 710a3fdd6e11cd351737b4451c05ec5d794e6855cfCameron Zwarich /// analyzePHINodes - Gather information about the PHI nodes in 720a3fdd6e11cd351737b4451c05ec5d794e6855cfCameron Zwarich /// here. In particular, we want to map the number of uses of a virtual 730a3fdd6e11cd351737b4451c05ec5d794e6855cfCameron Zwarich /// register which is used in a PHI node. We map that to the BB the 740a3fdd6e11cd351737b4451c05ec5d794e6855cfCameron Zwarich /// vreg is coming from. This is used later to determine when the vreg 750a3fdd6e11cd351737b4451c05ec5d794e6855cfCameron Zwarich /// is killed in the BB. 760a3fdd6e11cd351737b4451c05ec5d794e6855cfCameron Zwarich /// 770a3fdd6e11cd351737b4451c05ec5d794e6855cfCameron Zwarich void analyzePHINodes(const MachineFunction& Fn); 780a3fdd6e11cd351737b4451c05ec5d794e6855cfCameron Zwarich 790a3fdd6e11cd351737b4451c05ec5d794e6855cfCameron Zwarich /// Split critical edges where necessary for good coalescer performance. 800a3fdd6e11cd351737b4451c05ec5d794e6855cfCameron Zwarich bool SplitPHIEdges(MachineFunction &MF, MachineBasicBlock &MBB, 81fe0fd35d5339467fedd59f0cf5bdadb163a8d766Cameron Zwarich MachineLoopInfo *MLI); 820a3fdd6e11cd351737b4451c05ec5d794e6855cfCameron Zwarich 8336f54480f83d47404aceea5d41f8f6b95da2d00bCameron Zwarich // These functions are temporary abstractions around LiveVariables and 8436f54480f83d47404aceea5d41f8f6b95da2d00bCameron Zwarich // LiveIntervals, so they can go away when LiveVariables does. 8536f54480f83d47404aceea5d41f8f6b95da2d00bCameron Zwarich bool isLiveIn(unsigned Reg, MachineBasicBlock *MBB); 8636f54480f83d47404aceea5d41f8f6b95da2d00bCameron Zwarich bool isLiveOutPastPHIs(unsigned Reg, MachineBasicBlock *MBB); 8736f54480f83d47404aceea5d41f8f6b95da2d00bCameron Zwarich 880a3fdd6e11cd351737b4451c05ec5d794e6855cfCameron Zwarich typedef std::pair<unsigned, unsigned> BBVRegPair; 890a3fdd6e11cd351737b4451c05ec5d794e6855cfCameron Zwarich typedef DenseMap<BBVRegPair, unsigned> VRegPHIUse; 900a3fdd6e11cd351737b4451c05ec5d794e6855cfCameron Zwarich 910a3fdd6e11cd351737b4451c05ec5d794e6855cfCameron Zwarich VRegPHIUse VRegPHIUseCount; 920a3fdd6e11cd351737b4451c05ec5d794e6855cfCameron Zwarich 930a3fdd6e11cd351737b4451c05ec5d794e6855cfCameron Zwarich // Defs of PHI sources which are implicit_def. 940a3fdd6e11cd351737b4451c05ec5d794e6855cfCameron Zwarich SmallPtrSet<MachineInstr*, 4> ImpDefs; 950a3fdd6e11cd351737b4451c05ec5d794e6855cfCameron Zwarich 960a3fdd6e11cd351737b4451c05ec5d794e6855cfCameron Zwarich // Map reusable lowered PHI node -> incoming join register. 970a3fdd6e11cd351737b4451c05ec5d794e6855cfCameron Zwarich typedef DenseMap<MachineInstr*, unsigned, 980a3fdd6e11cd351737b4451c05ec5d794e6855cfCameron Zwarich MachineInstrExpressionTrait> LoweredPHIMap; 990a3fdd6e11cd351737b4451c05ec5d794e6855cfCameron Zwarich LoweredPHIMap LoweredPHIs; 1000a3fdd6e11cd351737b4451c05ec5d794e6855cfCameron Zwarich }; 1010a3fdd6e11cd351737b4451c05ec5d794e6855cfCameron Zwarich} 1020a3fdd6e11cd351737b4451c05ec5d794e6855cfCameron Zwarich 10302513c05c6333e2f7418b1327eded162b2791828Cameron ZwarichSTATISTIC(NumLowered, "Number of phis lowered"); 104117be03cc6cfb91d385938ed94a3cf877bd8c12aCameron ZwarichSTATISTIC(NumCriticalEdgesSplit, "Number of critical edges split"); 10574215fc29fa748e006c0309671555d5873bac56aJakob Stoklund OlesenSTATISTIC(NumReused, "Number of reused lowered phis"); 106f235f13931835b3335f3f2ff2d3060381b93626cJakob Stoklund Olesen 107fae02a2ab19abdf12854356e19aeb1da62a0b8eaLang Hameschar PHIElimination::ID = 0; 1080a3fdd6e11cd351737b4451c05ec5d794e6855cfCameron Zwarichchar& llvm::PHIEliminationID = PHIElimination::ID; 109bc40e898e153c9b81f246a7971eaac7b14446c49Chris Lattner 1108dd26253f54247e77e5accfdd70e7b4bf27b39c2Andrew TrickINITIALIZE_PASS_BEGIN(PHIElimination, "phi-node-elimination", 1118dd26253f54247e77e5accfdd70e7b4bf27b39c2Andrew Trick "Eliminate PHI nodes for register allocation", 1128dd26253f54247e77e5accfdd70e7b4bf27b39c2Andrew Trick false, false) 1138dd26253f54247e77e5accfdd70e7b4bf27b39c2Andrew TrickINITIALIZE_PASS_DEPENDENCY(LiveVariables) 1148dd26253f54247e77e5accfdd70e7b4bf27b39c2Andrew TrickINITIALIZE_PASS_END(PHIElimination, "phi-node-elimination", 1158dd26253f54247e77e5accfdd70e7b4bf27b39c2Andrew Trick "Eliminate PHI nodes for register allocation", false, false) 1168dd26253f54247e77e5accfdd70e7b4bf27b39c2Andrew Trick 1170a3fdd6e11cd351737b4451c05ec5d794e6855cfCameron Zwarichvoid PHIElimination::getAnalysisUsage(AnalysisUsage &AU) const { 118845012e6d31799c7fbd1193fa1af8ee2d12e9231Dan Gohman AU.addPreserved<LiveVariables>(); 1194f659eccafe34efea2a4ba6e57ad09977e9157c2Cameron Zwarich AU.addPreserved<SlotIndexes>(); 120b7cfac32f32f17e64a5addfdb833702160650f14Cameron Zwarich AU.addPreserved<LiveIntervals>(); 1219aebb61daf4d787aa7dcff9e3caa89bac88e11d1Jakob Stoklund Olesen AU.addPreserved<MachineDominatorTree>(); 122148341cc9b60d7d88be9c07a2b32b436e0cd301dEvan Cheng AU.addPreserved<MachineLoopInfo>(); 123845012e6d31799c7fbd1193fa1af8ee2d12e9231Dan Gohman MachineFunctionPass::getAnalysisUsage(AU); 124845012e6d31799c7fbd1193fa1af8ee2d12e9231Dan Gohman} 125fae02a2ab19abdf12854356e19aeb1da62a0b8eaLang Hames 1260a3fdd6e11cd351737b4451c05ec5d794e6855cfCameron Zwarichbool PHIElimination::runOnMachineFunction(MachineFunction &MF) { 12728428cd6f31c1ea3cf4cea03e64189a4c32b84a3Evan Cheng MRI = &MF.getRegInfo(); 128fe0fd35d5339467fedd59f0cf5bdadb163a8d766Cameron Zwarich LV = getAnalysisIfAvailable<LiveVariables>(); 129b7cfac32f32f17e64a5addfdb833702160650f14Cameron Zwarich LIS = getAnalysisIfAvailable<LiveIntervals>(); 130576a27043d95d0b9b8a010bccfd38ed9c0afa739Evan Cheng 131576a27043d95d0b9b8a010bccfd38ed9c0afa739Evan Cheng bool Changed = false; 132576a27043d95d0b9b8a010bccfd38ed9c0afa739Evan Cheng 13373e7dced3892f2abb4344526147d4df0f62aee61Jakob Stoklund Olesen // This pass takes the function out of SSA form. 13473e7dced3892f2abb4344526147d4df0f62aee61Jakob Stoklund Olesen MRI->leaveSSA(); 13573e7dced3892f2abb4344526147d4df0f62aee61Jakob Stoklund Olesen 136b7cfac32f32f17e64a5addfdb833702160650f14Cameron Zwarich // Split critical edges to help the coalescer. This does not yet support 137b7cfac32f32f17e64a5addfdb833702160650f14Cameron Zwarich // updating LiveIntervals, so we disable it. 1388597c14e9b32259cc7cfd752d95fd71e7aaba0ecCameron Zwarich if (!DisableEdgeSplitting && (LV || LIS)) { 139fe0fd35d5339467fedd59f0cf5bdadb163a8d766Cameron Zwarich MachineLoopInfo *MLI = getAnalysisIfAvailable<MachineLoopInfo>(); 140fe0fd35d5339467fedd59f0cf5bdadb163a8d766Cameron Zwarich for (MachineFunction::iterator I = MF.begin(), E = MF.end(); I != E; ++I) 141fe0fd35d5339467fedd59f0cf5bdadb163a8d766Cameron Zwarich Changed |= SplitPHIEdges(MF, *I, MLI); 142148341cc9b60d7d88be9c07a2b32b436e0cd301dEvan Cheng } 1433e20475feebca3bfb29375ac7f3e5acbeb2a95c8Jakob Stoklund Olesen 1443e20475feebca3bfb29375ac7f3e5acbeb2a95c8Jakob Stoklund Olesen // Populate VRegPHIUseCount 14528428cd6f31c1ea3cf4cea03e64189a4c32b84a3Evan Cheng analyzePHINodes(MF); 1463e20475feebca3bfb29375ac7f3e5acbeb2a95c8Jakob Stoklund Olesen 147576a27043d95d0b9b8a010bccfd38ed9c0afa739Evan Cheng // Eliminate PHI instructions by inserting copies into predecessor blocks. 14828428cd6f31c1ea3cf4cea03e64189a4c32b84a3Evan Cheng for (MachineFunction::iterator I = MF.begin(), E = MF.end(); I != E; ++I) 14928428cd6f31c1ea3cf4cea03e64189a4c32b84a3Evan Cheng Changed |= EliminatePHINodes(MF, *I); 150576a27043d95d0b9b8a010bccfd38ed9c0afa739Evan Cheng 151576a27043d95d0b9b8a010bccfd38ed9c0afa739Evan Cheng // Remove dead IMPLICIT_DEF instructions. 1523de8249078354d25b37b40e0f10b4f88226d3dd4Bill Wendling for (SmallPtrSet<MachineInstr*, 4>::iterator I = ImpDefs.begin(), 153576a27043d95d0b9b8a010bccfd38ed9c0afa739Evan Cheng E = ImpDefs.end(); I != E; ++I) { 154576a27043d95d0b9b8a010bccfd38ed9c0afa739Evan Cheng MachineInstr *DefMI = *I; 155576a27043d95d0b9b8a010bccfd38ed9c0afa739Evan Cheng unsigned DefReg = DefMI->getOperand(0).getReg(); 156b7cfac32f32f17e64a5addfdb833702160650f14Cameron Zwarich if (MRI->use_nodbg_empty(DefReg)) { 157b7cfac32f32f17e64a5addfdb833702160650f14Cameron Zwarich if (LIS) 158b7cfac32f32f17e64a5addfdb833702160650f14Cameron Zwarich LIS->RemoveMachineInstrFromMaps(DefMI); 159576a27043d95d0b9b8a010bccfd38ed9c0afa739Evan Cheng DefMI->eraseFromParent(); 160b7cfac32f32f17e64a5addfdb833702160650f14Cameron Zwarich } 161576a27043d95d0b9b8a010bccfd38ed9c0afa739Evan Cheng } 162576a27043d95d0b9b8a010bccfd38ed9c0afa739Evan Cheng 16374215fc29fa748e006c0309671555d5873bac56aJakob Stoklund Olesen // Clean up the lowered PHI instructions. 16474215fc29fa748e006c0309671555d5873bac56aJakob Stoklund Olesen for (LoweredPHIMap::iterator I = LoweredPHIs.begin(), E = LoweredPHIs.end(); 165b7cfac32f32f17e64a5addfdb833702160650f14Cameron Zwarich I != E; ++I) { 1668d49134eeaa36953410c2fba65f7237fb3f079e7Cameron Zwarich if (LIS) 1678d49134eeaa36953410c2fba65f7237fb3f079e7Cameron Zwarich LIS->RemoveMachineInstrFromMaps(I->first); 16828428cd6f31c1ea3cf4cea03e64189a4c32b84a3Evan Cheng MF.DeleteMachineInstr(I->first); 169b7cfac32f32f17e64a5addfdb833702160650f14Cameron Zwarich } 17074215fc29fa748e006c0309671555d5873bac56aJakob Stoklund Olesen 1713de8249078354d25b37b40e0f10b4f88226d3dd4Bill Wendling LoweredPHIs.clear(); 172576a27043d95d0b9b8a010bccfd38ed9c0afa739Evan Cheng ImpDefs.clear(); 173576a27043d95d0b9b8a010bccfd38ed9c0afa739Evan Cheng VRegPHIUseCount.clear(); 17428428cd6f31c1ea3cf4cea03e64189a4c32b84a3Evan Cheng 175576a27043d95d0b9b8a010bccfd38ed9c0afa739Evan Cheng return Changed; 176576a27043d95d0b9b8a010bccfd38ed9c0afa739Evan Cheng} 177576a27043d95d0b9b8a010bccfd38ed9c0afa739Evan Cheng 178bc40e898e153c9b81f246a7971eaac7b14446c49Chris Lattner/// EliminatePHINodes - Eliminate phi nodes by inserting copy instructions in 179bc40e898e153c9b81f246a7971eaac7b14446c49Chris Lattner/// predecessor basic blocks. 180bc40e898e153c9b81f246a7971eaac7b14446c49Chris Lattner/// 1810a3fdd6e11cd351737b4451c05ec5d794e6855cfCameron Zwarichbool PHIElimination::EliminatePHINodes(MachineFunction &MF, 182fae02a2ab19abdf12854356e19aeb1da62a0b8eaLang Hames MachineBasicBlock &MBB) { 183518bb53485df640d7b7e3f6b0544099020c42aa7Chris Lattner if (MBB.empty() || !MBB.front().isPHI()) 18453a79aaae988d9dc9d12af8970f8b8fe58cc478dChris Lattner return false; // Quick exit for basic blocks without PHIs. 185bc40e898e153c9b81f246a7971eaac7b14446c49Chris Lattner 186791f896d9f8a38b3806878867d61c114069b6195Chris Lattner // Get an iterator to the first instruction after the last PHI node (this may 18753a79aaae988d9dc9d12af8970f8b8fe58cc478dChris Lattner // also be the end of the basic block). 18803fae50cfa5631349fbd47f4c232fc78f5b3b8afCameron Zwarich MachineBasicBlock::iterator LastPHIIt = 18903fae50cfa5631349fbd47f4c232fc78f5b3b8afCameron Zwarich prior(MBB.SkipPHIsAndLabels(MBB.begin())); 190791f896d9f8a38b3806878867d61c114069b6195Chris Lattner 191518bb53485df640d7b7e3f6b0544099020c42aa7Chris Lattner while (MBB.front().isPHI()) 19203fae50cfa5631349fbd47f4c232fc78f5b3b8afCameron Zwarich LowerPHINode(MBB, LastPHIIt); 193ca756d2cf9bd88f210d61dd5f9776920a6178441Bill Wendling 19453a79aaae988d9dc9d12af8970f8b8fe58cc478dChris Lattner return true; 19553a79aaae988d9dc9d12af8970f8b8fe58cc478dChris Lattner} 196edf128a7fa90f2b0b7ee24741a04a7ae1ecd6f7eMisha Brukman 1975213750e27c2f9fd7f5a0884c4a15f3b5e3aa843Jakob Stoklund Olesen/// isImplicitlyDefined - Return true if all defs of VirtReg are implicit-defs. 1985213750e27c2f9fd7f5a0884c4a15f3b5e3aa843Jakob Stoklund Olesen/// This includes registers with no defs. 1995213750e27c2f9fd7f5a0884c4a15f3b5e3aa843Jakob Stoklund Olesenstatic bool isImplicitlyDefined(unsigned VirtReg, 2005213750e27c2f9fd7f5a0884c4a15f3b5e3aa843Jakob Stoklund Olesen const MachineRegisterInfo *MRI) { 2015213750e27c2f9fd7f5a0884c4a15f3b5e3aa843Jakob Stoklund Olesen for (MachineRegisterInfo::def_iterator DI = MRI->def_begin(VirtReg), 2025213750e27c2f9fd7f5a0884c4a15f3b5e3aa843Jakob Stoklund Olesen DE = MRI->def_end(); DI != DE; ++DI) 2035213750e27c2f9fd7f5a0884c4a15f3b5e3aa843Jakob Stoklund Olesen if (!DI->isImplicitDef()) 2045213750e27c2f9fd7f5a0884c4a15f3b5e3aa843Jakob Stoklund Olesen return false; 2055213750e27c2f9fd7f5a0884c4a15f3b5e3aa843Jakob Stoklund Olesen return true; 2065213750e27c2f9fd7f5a0884c4a15f3b5e3aa843Jakob Stoklund Olesen} 2075213750e27c2f9fd7f5a0884c4a15f3b5e3aa843Jakob Stoklund Olesen 2081b38ec83f07d5801035567160008cd7cb99a5c1aEvan Cheng/// isSourceDefinedByImplicitDef - Return true if all sources of the phi node 2091b38ec83f07d5801035567160008cd7cb99a5c1aEvan Cheng/// are implicit_def's. 210ae94dda61a045cb77681940ecc25aba0d2763f74Bill Wendlingstatic bool isSourceDefinedByImplicitDef(const MachineInstr *MPhi, 2111b38ec83f07d5801035567160008cd7cb99a5c1aEvan Cheng const MachineRegisterInfo *MRI) { 2125213750e27c2f9fd7f5a0884c4a15f3b5e3aa843Jakob Stoklund Olesen for (unsigned i = 1; i != MPhi->getNumOperands(); i += 2) 2135213750e27c2f9fd7f5a0884c4a15f3b5e3aa843Jakob Stoklund Olesen if (!isImplicitlyDefined(MPhi->getOperand(i).getReg(), MRI)) 214b3e0a6d75c60f01df4fcee4b4309f06ce92a96c9Evan Cheng return false; 215b3e0a6d75c60f01df4fcee4b4309f06ce92a96c9Evan Cheng return true; 216f870fbc554ac862ad6d45cf97148739802a3ed12Evan Cheng} 217f870fbc554ac862ad6d45cf97148739802a3ed12Evan Cheng 218a5fec0dba34206274041543b5924d2565fb10f9bDuncan Sands 21902513c05c6333e2f7418b1327eded162b2791828Cameron Zwarich/// LowerPHINode - Lower the PHI node at the top of the specified block, 220e35e3c33dc5533dd1e8ab7d9f4039cc1429d56aaJakob Stoklund Olesen/// 22102513c05c6333e2f7418b1327eded162b2791828Cameron Zwarichvoid PHIElimination::LowerPHINode(MachineBasicBlock &MBB, 22203fae50cfa5631349fbd47f4c232fc78f5b3b8afCameron Zwarich MachineBasicBlock::iterator LastPHIIt) { 22302513c05c6333e2f7418b1327eded162b2791828Cameron Zwarich ++NumLowered; 22403fae50cfa5631349fbd47f4c232fc78f5b3b8afCameron Zwarich 225f807a6ee3a6c7365ffdf07510767b13a5a7df93cCameron Zwarich MachineBasicBlock::iterator AfterPHIsIt = llvm::next(LastPHIIt); 22603fae50cfa5631349fbd47f4c232fc78f5b3b8afCameron Zwarich 22753a79aaae988d9dc9d12af8970f8b8fe58cc478dChris Lattner // Unlink the PHI node from the basic block, but don't delete the PHI yet. 22853a79aaae988d9dc9d12af8970f8b8fe58cc478dChris Lattner MachineInstr *MPhi = MBB.remove(MBB.begin()); 22953a79aaae988d9dc9d12af8970f8b8fe58cc478dChris Lattner 230f870fbc554ac862ad6d45cf97148739802a3ed12Evan Cheng unsigned NumSrcs = (MPhi->getNumOperands() - 1) / 2; 23153a79aaae988d9dc9d12af8970f8b8fe58cc478dChris Lattner unsigned DestReg = MPhi->getOperand(0).getReg(); 2329ac248848faa839cff8e9f915c9b2c44295bc9f6Jakob Stoklund Olesen assert(MPhi->getOperand(0).getSubReg() == 0 && "Can't handle sub-reg PHIs"); 2339f1c8317a4676945b4961ddb9827ef2412551620Evan Cheng bool isDead = MPhi->getOperand(0).isDead(); 23453a79aaae988d9dc9d12af8970f8b8fe58cc478dChris Lattner 235ca756d2cf9bd88f210d61dd5f9776920a6178441Bill Wendling // Create a new register for the incoming PHI arguments. 23653a79aaae988d9dc9d12af8970f8b8fe58cc478dChris Lattner MachineFunction &MF = *MBB.getParent(); 2379f1c8317a4676945b4961ddb9827ef2412551620Evan Cheng unsigned IncomingReg = 0; 23874215fc29fa748e006c0309671555d5873bac56aJakob Stoklund Olesen bool reusedIncoming = false; // Is IncomingReg reused from an earlier PHI? 23953a79aaae988d9dc9d12af8970f8b8fe58cc478dChris Lattner 240ae94dda61a045cb77681940ecc25aba0d2763f74Bill Wendling // Insert a register to register copy at the top of the current block (but 24153a79aaae988d9dc9d12af8970f8b8fe58cc478dChris Lattner // after any remaining phi nodes) which copies the new incoming register 24253a79aaae988d9dc9d12af8970f8b8fe58cc478dChris Lattner // into the phi node destination. 243d10fd9791c20fd8368fa0ce94b626b769c6c8ba0Owen Anderson const TargetInstrInfo *TII = MF.getTarget().getInstrInfo(); 244b3e0a6d75c60f01df4fcee4b4309f06ce92a96c9Evan Cheng if (isSourceDefinedByImplicitDef(MPhi, MRI)) 2459f1c8317a4676945b4961ddb9827ef2412551620Evan Cheng // If all sources of a PHI node are implicit_def, just emit an 2469f1c8317a4676945b4961ddb9827ef2412551620Evan Cheng // implicit_def instead of a copy. 247d62e06c53b8b7e555617dc9b24b98c007d63de5dBill Wendling BuildMI(MBB, AfterPHIsIt, MPhi->getDebugLoc(), 248518bb53485df640d7b7e3f6b0544099020c42aa7Chris Lattner TII->get(TargetOpcode::IMPLICIT_DEF), DestReg); 2499f1c8317a4676945b4961ddb9827ef2412551620Evan Cheng else { 25074215fc29fa748e006c0309671555d5873bac56aJakob Stoklund Olesen // Can we reuse an earlier PHI node? This only happens for critical edges, 25174215fc29fa748e006c0309671555d5873bac56aJakob Stoklund Olesen // typically those created by tail duplication. 25274215fc29fa748e006c0309671555d5873bac56aJakob Stoklund Olesen unsigned &entry = LoweredPHIs[MPhi]; 25374215fc29fa748e006c0309671555d5873bac56aJakob Stoklund Olesen if (entry) { 25474215fc29fa748e006c0309671555d5873bac56aJakob Stoklund Olesen // An identical PHI node was already lowered. Reuse the incoming register. 25574215fc29fa748e006c0309671555d5873bac56aJakob Stoklund Olesen IncomingReg = entry; 25674215fc29fa748e006c0309671555d5873bac56aJakob Stoklund Olesen reusedIncoming = true; 25774215fc29fa748e006c0309671555d5873bac56aJakob Stoklund Olesen ++NumReused; 2584314268128be6d54c9a7f0709680e5a5b40f3ab3Jakob Stoklund Olesen DEBUG(dbgs() << "Reusing " << PrintReg(IncomingReg) << " for " << *MPhi); 25974215fc29fa748e006c0309671555d5873bac56aJakob Stoklund Olesen } else { 26092c1f72c548e6a5e793ef19a0b04910992115b6cJakob Stoklund Olesen const TargetRegisterClass *RC = MF.getRegInfo().getRegClass(DestReg); 26174215fc29fa748e006c0309671555d5873bac56aJakob Stoklund Olesen entry = IncomingReg = MF.getRegInfo().createVirtualRegister(RC); 26274215fc29fa748e006c0309671555d5873bac56aJakob Stoklund Olesen } 26392c1f72c548e6a5e793ef19a0b04910992115b6cJakob Stoklund Olesen BuildMI(MBB, AfterPHIsIt, MPhi->getDebugLoc(), 26492c1f72c548e6a5e793ef19a0b04910992115b6cJakob Stoklund Olesen TII->get(TargetOpcode::COPY), DestReg) 26592c1f72c548e6a5e793ef19a0b04910992115b6cJakob Stoklund Olesen .addReg(IncomingReg); 2669f1c8317a4676945b4961ddb9827ef2412551620Evan Cheng } 267bc40e898e153c9b81f246a7971eaac7b14446c49Chris Lattner 268ae94dda61a045cb77681940ecc25aba0d2763f74Bill Wendling // Update live variable information if there is any. 26953a79aaae988d9dc9d12af8970f8b8fe58cc478dChris Lattner if (LV) { 27053a79aaae988d9dc9d12af8970f8b8fe58cc478dChris Lattner MachineInstr *PHICopy = prior(AfterPHIsIt); 271edf128a7fa90f2b0b7ee24741a04a7ae1ecd6f7eMisha Brukman 2729f1c8317a4676945b4961ddb9827ef2412551620Evan Cheng if (IncomingReg) { 27374215fc29fa748e006c0309671555d5873bac56aJakob Stoklund Olesen LiveVariables::VarInfo &VI = LV->getVarInfo(IncomingReg); 27474215fc29fa748e006c0309671555d5873bac56aJakob Stoklund Olesen 2759f1c8317a4676945b4961ddb9827ef2412551620Evan Cheng // Increment use count of the newly created virtual register. 276dcfe5f30b5e262971f601a65bebcc0367fef56c5Jakob Stoklund Olesen LV->setPHIJoin(IncomingReg); 27774215fc29fa748e006c0309671555d5873bac56aJakob Stoklund Olesen 27874215fc29fa748e006c0309671555d5873bac56aJakob Stoklund Olesen // When we are reusing the incoming register, it may already have been 27974215fc29fa748e006c0309671555d5873bac56aJakob Stoklund Olesen // killed in this block. The old kill will also have been inserted at 28074215fc29fa748e006c0309671555d5873bac56aJakob Stoklund Olesen // AfterPHIsIt, so it appears before the current PHICopy. 28174215fc29fa748e006c0309671555d5873bac56aJakob Stoklund Olesen if (reusedIncoming) 28274215fc29fa748e006c0309671555d5873bac56aJakob Stoklund Olesen if (MachineInstr *OldKill = VI.findKill(&MBB)) { 283f78829794284afc7c243d9ad0591ae3a87172340David Greene DEBUG(dbgs() << "Remove old kill from " << *OldKill); 28474215fc29fa748e006c0309671555d5873bac56aJakob Stoklund Olesen LV->removeVirtualRegisterKilled(IncomingReg, OldKill); 28574215fc29fa748e006c0309671555d5873bac56aJakob Stoklund Olesen DEBUG(MBB.dump()); 28674215fc29fa748e006c0309671555d5873bac56aJakob Stoklund Olesen } 2879f1c8317a4676945b4961ddb9827ef2412551620Evan Cheng 2889f1c8317a4676945b4961ddb9827ef2412551620Evan Cheng // Add information to LiveVariables to know that the incoming value is 2899f1c8317a4676945b4961ddb9827ef2412551620Evan Cheng // killed. Note that because the value is defined in several places (once 2909f1c8317a4676945b4961ddb9827ef2412551620Evan Cheng // each for each incoming block), the "def" block and instruction fields 2919f1c8317a4676945b4961ddb9827ef2412551620Evan Cheng // for the VarInfo is not filled in. 2929f1c8317a4676945b4961ddb9827ef2412551620Evan Cheng LV->addVirtualRegisterKilled(IncomingReg, PHICopy); 2939f1c8317a4676945b4961ddb9827ef2412551620Evan Cheng } 294bc40e898e153c9b81f246a7971eaac7b14446c49Chris Lattner 295ae94dda61a045cb77681940ecc25aba0d2763f74Bill Wendling // Since we are going to be deleting the PHI node, if it is the last use of 296ae94dda61a045cb77681940ecc25aba0d2763f74Bill Wendling // any registers, or if the value itself is dead, we need to move this 29753a79aaae988d9dc9d12af8970f8b8fe58cc478dChris Lattner // information over to the new copy we just inserted. 29853a79aaae988d9dc9d12af8970f8b8fe58cc478dChris Lattner LV->removeVirtualRegistersKilled(MPhi); 29953a79aaae988d9dc9d12af8970f8b8fe58cc478dChris Lattner 3006db0756f021a7b9c84d3bb7ae50498feb080a013Chris Lattner // If the result is dead, update LV. 3019f1c8317a4676945b4961ddb9827ef2412551620Evan Cheng if (isDead) { 3026db0756f021a7b9c84d3bb7ae50498feb080a013Chris Lattner LV->addVirtualRegisterDead(DestReg, PHICopy); 3039f1c8317a4676945b4961ddb9827ef2412551620Evan Cheng LV->removeVirtualRegisterDead(DestReg, MPhi); 304927ce5dfaea00453889080cd1c6daf3eb197ad74Chris Lattner } 30553a79aaae988d9dc9d12af8970f8b8fe58cc478dChris Lattner } 30653a79aaae988d9dc9d12af8970f8b8fe58cc478dChris Lattner 307b7cfac32f32f17e64a5addfdb833702160650f14Cameron Zwarich // Update LiveIntervals for the new copy or implicit def. 308b7cfac32f32f17e64a5addfdb833702160650f14Cameron Zwarich if (LIS) { 309b7cfac32f32f17e64a5addfdb833702160650f14Cameron Zwarich MachineInstr *NewInstr = prior(AfterPHIsIt); 3102650a82cc4166237f698e3bbc315739e43180431Cameron Zwarich SlotIndex DestCopyIndex = LIS->InsertMachineInstrInMaps(NewInstr); 311b7cfac32f32f17e64a5addfdb833702160650f14Cameron Zwarich 312b7cfac32f32f17e64a5addfdb833702160650f14Cameron Zwarich SlotIndex MBBStartIndex = LIS->getMBBStartIdx(&MBB); 313b7cfac32f32f17e64a5addfdb833702160650f14Cameron Zwarich if (IncomingReg) { 314b7cfac32f32f17e64a5addfdb833702160650f14Cameron Zwarich // Add the region from the beginning of MBB to the copy instruction to 315b7cfac32f32f17e64a5addfdb833702160650f14Cameron Zwarich // IncomingReg's live interval. 316b7cfac32f32f17e64a5addfdb833702160650f14Cameron Zwarich LiveInterval &IncomingLI = LIS->getOrCreateInterval(IncomingReg); 317b7cfac32f32f17e64a5addfdb833702160650f14Cameron Zwarich VNInfo *IncomingVNI = IncomingLI.getVNInfoAt(MBBStartIndex); 318b7cfac32f32f17e64a5addfdb833702160650f14Cameron Zwarich if (!IncomingVNI) 319b7cfac32f32f17e64a5addfdb833702160650f14Cameron Zwarich IncomingVNI = IncomingLI.getNextValue(MBBStartIndex, 320b7cfac32f32f17e64a5addfdb833702160650f14Cameron Zwarich LIS->getVNInfoAllocator()); 321b7cfac32f32f17e64a5addfdb833702160650f14Cameron Zwarich IncomingLI.addRange(LiveRange(MBBStartIndex, 322b7cfac32f32f17e64a5addfdb833702160650f14Cameron Zwarich DestCopyIndex.getRegSlot(), 323b7cfac32f32f17e64a5addfdb833702160650f14Cameron Zwarich IncomingVNI)); 324b7cfac32f32f17e64a5addfdb833702160650f14Cameron Zwarich } 325b7cfac32f32f17e64a5addfdb833702160650f14Cameron Zwarich 326a566d63b61f2a29e89696abba1729ac53b9843e6Cameron Zwarich LiveInterval &DestLI = LIS->getInterval(DestReg); 327197a60a66612ab274a734066962a10126a11fb53Cameron Zwarich assert(DestLI.begin() != DestLI.end() && 328197a60a66612ab274a734066962a10126a11fb53Cameron Zwarich "PHIs should have nonempty LiveIntervals."); 329197a60a66612ab274a734066962a10126a11fb53Cameron Zwarich if (DestLI.endIndex().isDead()) { 330b7cfac32f32f17e64a5addfdb833702160650f14Cameron Zwarich // A dead PHI's live range begins and ends at the start of the MBB, but 331b7cfac32f32f17e64a5addfdb833702160650f14Cameron Zwarich // the lowered copy, which will still be dead, needs to begin and end at 332b7cfac32f32f17e64a5addfdb833702160650f14Cameron Zwarich // the copy instruction. 333b7cfac32f32f17e64a5addfdb833702160650f14Cameron Zwarich VNInfo *OrigDestVNI = DestLI.getVNInfoAt(MBBStartIndex); 334b7cfac32f32f17e64a5addfdb833702160650f14Cameron Zwarich assert(OrigDestVNI && "PHI destination should be live at block entry."); 335b7cfac32f32f17e64a5addfdb833702160650f14Cameron Zwarich DestLI.removeRange(MBBStartIndex, MBBStartIndex.getDeadSlot()); 336b7cfac32f32f17e64a5addfdb833702160650f14Cameron Zwarich DestLI.createDeadDef(DestCopyIndex.getRegSlot(), 337b7cfac32f32f17e64a5addfdb833702160650f14Cameron Zwarich LIS->getVNInfoAllocator()); 338b7cfac32f32f17e64a5addfdb833702160650f14Cameron Zwarich DestLI.removeValNo(OrigDestVNI); 339b7cfac32f32f17e64a5addfdb833702160650f14Cameron Zwarich } else { 340b7cfac32f32f17e64a5addfdb833702160650f14Cameron Zwarich // Otherwise, remove the region from the beginning of MBB to the copy 341b7cfac32f32f17e64a5addfdb833702160650f14Cameron Zwarich // instruction from DestReg's live interval. 342b7cfac32f32f17e64a5addfdb833702160650f14Cameron Zwarich DestLI.removeRange(MBBStartIndex, DestCopyIndex.getRegSlot()); 343b7cfac32f32f17e64a5addfdb833702160650f14Cameron Zwarich VNInfo *DestVNI = DestLI.getVNInfoAt(DestCopyIndex.getRegSlot()); 344b7cfac32f32f17e64a5addfdb833702160650f14Cameron Zwarich assert(DestVNI && "PHI destination should be live at its definition."); 345b7cfac32f32f17e64a5addfdb833702160650f14Cameron Zwarich DestVNI->def = DestCopyIndex.getRegSlot(); 346b7cfac32f32f17e64a5addfdb833702160650f14Cameron Zwarich } 347b7cfac32f32f17e64a5addfdb833702160650f14Cameron Zwarich } 348b7cfac32f32f17e64a5addfdb833702160650f14Cameron Zwarich 349ae94dda61a045cb77681940ecc25aba0d2763f74Bill Wendling // Adjust the VRegPHIUseCount map to account for the removal of this PHI node. 35053a79aaae988d9dc9d12af8970f8b8fe58cc478dChris Lattner for (unsigned i = 1; i != MPhi->getNumOperands(); i += 2) 35174215fc29fa748e006c0309671555d5873bac56aJakob Stoklund Olesen --VRegPHIUseCount[BBVRegPair(MPhi->getOperand(i+1).getMBB()->getNumber(), 3528aa797aa51cd4ea1ec6f46f4891a6897944b75b2Chris Lattner MPhi->getOperand(i).getReg())]; 35353a79aaae988d9dc9d12af8970f8b8fe58cc478dChris Lattner 354ae94dda61a045cb77681940ecc25aba0d2763f74Bill Wendling // Now loop over all of the incoming arguments, changing them to copy into the 355ae94dda61a045cb77681940ecc25aba0d2763f74Bill Wendling // IncomingReg register in the corresponding predecessor basic block. 356576a27043d95d0b9b8a010bccfd38ed9c0afa739Evan Cheng SmallPtrSet<MachineBasicBlock*, 8> MBBsInsertedInto; 357f870fbc554ac862ad6d45cf97148739802a3ed12Evan Cheng for (int i = NumSrcs - 1; i >= 0; --i) { 358f870fbc554ac862ad6d45cf97148739802a3ed12Evan Cheng unsigned SrcReg = MPhi->getOperand(i*2+1).getReg(); 3599ac248848faa839cff8e9f915c9b2c44295bc9f6Jakob Stoklund Olesen unsigned SrcSubReg = MPhi->getOperand(i*2+1).getSubReg(); 3605213750e27c2f9fd7f5a0884c4a15f3b5e3aa843Jakob Stoklund Olesen bool SrcUndef = MPhi->getOperand(i*2+1).isUndef() || 3615213750e27c2f9fd7f5a0884c4a15f3b5e3aa843Jakob Stoklund Olesen isImplicitlyDefined(SrcReg, MRI); 3626f0d024a534af18d9e60b3ea757376cd8a3a980eDan Gohman assert(TargetRegisterInfo::isVirtualRegister(SrcReg) && 3636db0756f021a7b9c84d3bb7ae50498feb080a013Chris Lattner "Machine PHI Operands must all be virtual registers!"); 36453a79aaae988d9dc9d12af8970f8b8fe58cc478dChris Lattner 365287b8b0301bc6ec7eb70d23d242326a8766bb8ebLang Hames // Get the MachineBasicBlock equivalent of the BasicBlock that is the source 366287b8b0301bc6ec7eb70d23d242326a8766bb8ebLang Hames // path the PHI. 367287b8b0301bc6ec7eb70d23d242326a8766bb8ebLang Hames MachineBasicBlock &opBlock = *MPhi->getOperand(i*2+2).getMBB(); 368287b8b0301bc6ec7eb70d23d242326a8766bb8ebLang Hames 36953a79aaae988d9dc9d12af8970f8b8fe58cc478dChris Lattner // Check to make sure we haven't already emitted the copy for this block. 370ae94dda61a045cb77681940ecc25aba0d2763f74Bill Wendling // This can happen because PHI nodes may have multiple entries for the same 371ae94dda61a045cb77681940ecc25aba0d2763f74Bill Wendling // basic block. 372576a27043d95d0b9b8a010bccfd38ed9c0afa739Evan Cheng if (!MBBsInsertedInto.insert(&opBlock)) 3736db0756f021a7b9c84d3bb7ae50498feb080a013Chris Lattner continue; // If the copy has already been emitted, we're done. 374e35e3c33dc5533dd1e8ab7d9f4039cc1429d56aaJakob Stoklund Olesen 375ae94dda61a045cb77681940ecc25aba0d2763f74Bill Wendling // Find a safe location to insert the copy, this may be the first terminator 376ae94dda61a045cb77681940ecc25aba0d2763f74Bill Wendling // in the block (or end()). 3771222287543a5b5917f8c31aa8c88d740f70222d9Jakob Stoklund Olesen MachineBasicBlock::iterator InsertPos = 378a474685d069a900ab931ee1540c9a79fdd6607a9Cameron Zwarich findPHICopyInsertPoint(&opBlock, &MBB, SrcReg); 379fc0b80d9746e5fd4b45057ab814c67371fb0f9eaEvan Cheng 3806db0756f021a7b9c84d3bb7ae50498feb080a013Chris Lattner // Insert the copy. 381b7cfac32f32f17e64a5addfdb833702160650f14Cameron Zwarich MachineInstr *NewSrcInstr = 0; 3825213750e27c2f9fd7f5a0884c4a15f3b5e3aa843Jakob Stoklund Olesen if (!reusedIncoming && IncomingReg) { 3835213750e27c2f9fd7f5a0884c4a15f3b5e3aa843Jakob Stoklund Olesen if (SrcUndef) { 3845213750e27c2f9fd7f5a0884c4a15f3b5e3aa843Jakob Stoklund Olesen // The source register is undefined, so there is no need for a real 3855213750e27c2f9fd7f5a0884c4a15f3b5e3aa843Jakob Stoklund Olesen // COPY, but we still need to ensure joint dominance by defs. 3865213750e27c2f9fd7f5a0884c4a15f3b5e3aa843Jakob Stoklund Olesen // Insert an IMPLICIT_DEF instruction. 387b7cfac32f32f17e64a5addfdb833702160650f14Cameron Zwarich NewSrcInstr = BuildMI(opBlock, InsertPos, MPhi->getDebugLoc(), 388b7cfac32f32f17e64a5addfdb833702160650f14Cameron Zwarich TII->get(TargetOpcode::IMPLICIT_DEF), 389b7cfac32f32f17e64a5addfdb833702160650f14Cameron Zwarich IncomingReg); 3905213750e27c2f9fd7f5a0884c4a15f3b5e3aa843Jakob Stoklund Olesen 3915213750e27c2f9fd7f5a0884c4a15f3b5e3aa843Jakob Stoklund Olesen // Clean up the old implicit-def, if there even was one. 3925213750e27c2f9fd7f5a0884c4a15f3b5e3aa843Jakob Stoklund Olesen if (MachineInstr *DefMI = MRI->getVRegDef(SrcReg)) 3935213750e27c2f9fd7f5a0884c4a15f3b5e3aa843Jakob Stoklund Olesen if (DefMI->isImplicitDef()) 3945213750e27c2f9fd7f5a0884c4a15f3b5e3aa843Jakob Stoklund Olesen ImpDefs.insert(DefMI); 3955213750e27c2f9fd7f5a0884c4a15f3b5e3aa843Jakob Stoklund Olesen } else { 396b7cfac32f32f17e64a5addfdb833702160650f14Cameron Zwarich NewSrcInstr = BuildMI(opBlock, InsertPos, MPhi->getDebugLoc(), 397b7cfac32f32f17e64a5addfdb833702160650f14Cameron Zwarich TII->get(TargetOpcode::COPY), IncomingReg) 398b7cfac32f32f17e64a5addfdb833702160650f14Cameron Zwarich .addReg(SrcReg, 0, SrcSubReg); 3995213750e27c2f9fd7f5a0884c4a15f3b5e3aa843Jakob Stoklund Olesen } 4005213750e27c2f9fd7f5a0884c4a15f3b5e3aa843Jakob Stoklund Olesen } 4016db0756f021a7b9c84d3bb7ae50498feb080a013Chris Lattner 402b7cfac32f32f17e64a5addfdb833702160650f14Cameron Zwarich // We only need to update the LiveVariables kill of SrcReg if this was the 403b7cfac32f32f17e64a5addfdb833702160650f14Cameron Zwarich // last PHI use of SrcReg to be lowered on this CFG edge and it is not live 404b7cfac32f32f17e64a5addfdb833702160650f14Cameron Zwarich // out of the predecessor. We can also ignore undef sources. 405b7cfac32f32f17e64a5addfdb833702160650f14Cameron Zwarich if (LV && !SrcUndef && 406b7cfac32f32f17e64a5addfdb833702160650f14Cameron Zwarich !VRegPHIUseCount[BBVRegPair(opBlock.getNumber(), SrcReg)] && 407b7cfac32f32f17e64a5addfdb833702160650f14Cameron Zwarich !LV->isLiveOut(SrcReg, opBlock)) { 408b7cfac32f32f17e64a5addfdb833702160650f14Cameron Zwarich // We want to be able to insert a kill of the register if this PHI (aka, 409b7cfac32f32f17e64a5addfdb833702160650f14Cameron Zwarich // the copy we just inserted) is the last use of the source value. Live 410b7cfac32f32f17e64a5addfdb833702160650f14Cameron Zwarich // variable analysis conservatively handles this by saying that the value 411b7cfac32f32f17e64a5addfdb833702160650f14Cameron Zwarich // is live until the end of the block the PHI entry lives in. If the value 412b7cfac32f32f17e64a5addfdb833702160650f14Cameron Zwarich // really is dead at the PHI copy, there will be no successor blocks which 413b7cfac32f32f17e64a5addfdb833702160650f14Cameron Zwarich // have the value live-in. 414b7cfac32f32f17e64a5addfdb833702160650f14Cameron Zwarich 415b7cfac32f32f17e64a5addfdb833702160650f14Cameron Zwarich // Okay, if we now know that the value is not live out of the block, we 416b7cfac32f32f17e64a5addfdb833702160650f14Cameron Zwarich // can add a kill marker in this block saying that it kills the incoming 417b7cfac32f32f17e64a5addfdb833702160650f14Cameron Zwarich // value! 4186db0756f021a7b9c84d3bb7ae50498feb080a013Chris Lattner 4192adfa7e9320e79859beb556367ea607a329866b3Chris Lattner // In our final twist, we have to decide which instruction kills the 4209e51b14faa55225a3175c4af9c69f5a45dd9a646Jakob Stoklund Olesen // register. In most cases this is the copy, however, terminator 4219e51b14faa55225a3175c4af9c69f5a45dd9a646Jakob Stoklund Olesen // instructions at the end of the block may also use the value. In this 4229e51b14faa55225a3175c4af9c69f5a45dd9a646Jakob Stoklund Olesen // case, we should mark the last such terminator as being the killing 4239e51b14faa55225a3175c4af9c69f5a45dd9a646Jakob Stoklund Olesen // block, not the copy. 4249e51b14faa55225a3175c4af9c69f5a45dd9a646Jakob Stoklund Olesen MachineBasicBlock::iterator KillInst = opBlock.end(); 4259e51b14faa55225a3175c4af9c69f5a45dd9a646Jakob Stoklund Olesen MachineBasicBlock::iterator FirstTerm = opBlock.getFirstTerminator(); 4269e51b14faa55225a3175c4af9c69f5a45dd9a646Jakob Stoklund Olesen for (MachineBasicBlock::iterator Term = FirstTerm; 4279e51b14faa55225a3175c4af9c69f5a45dd9a646Jakob Stoklund Olesen Term != opBlock.end(); ++Term) { 4289e51b14faa55225a3175c4af9c69f5a45dd9a646Jakob Stoklund Olesen if (Term->readsRegister(SrcReg)) 4299e51b14faa55225a3175c4af9c69f5a45dd9a646Jakob Stoklund Olesen KillInst = Term; 4309e51b14faa55225a3175c4af9c69f5a45dd9a646Jakob Stoklund Olesen } 4319e51b14faa55225a3175c4af9c69f5a45dd9a646Jakob Stoklund Olesen 4329e51b14faa55225a3175c4af9c69f5a45dd9a646Jakob Stoklund Olesen if (KillInst == opBlock.end()) { 4339e51b14faa55225a3175c4af9c69f5a45dd9a646Jakob Stoklund Olesen // No terminator uses the register. 4349e51b14faa55225a3175c4af9c69f5a45dd9a646Jakob Stoklund Olesen 4359e51b14faa55225a3175c4af9c69f5a45dd9a646Jakob Stoklund Olesen if (reusedIncoming || !IncomingReg) { 4369e51b14faa55225a3175c4af9c69f5a45dd9a646Jakob Stoklund Olesen // We may have to rewind a bit if we didn't insert a copy this time. 4379e51b14faa55225a3175c4af9c69f5a45dd9a646Jakob Stoklund Olesen KillInst = FirstTerm; 4389e51b14faa55225a3175c4af9c69f5a45dd9a646Jakob Stoklund Olesen while (KillInst != opBlock.begin()) { 4399e51b14faa55225a3175c4af9c69f5a45dd9a646Jakob Stoklund Olesen --KillInst; 4409e51b14faa55225a3175c4af9c69f5a45dd9a646Jakob Stoklund Olesen if (KillInst->isDebugValue()) 4419e51b14faa55225a3175c4af9c69f5a45dd9a646Jakob Stoklund Olesen continue; 4429e51b14faa55225a3175c4af9c69f5a45dd9a646Jakob Stoklund Olesen if (KillInst->readsRegister(SrcReg)) 4439e51b14faa55225a3175c4af9c69f5a45dd9a646Jakob Stoklund Olesen break; 4449e51b14faa55225a3175c4af9c69f5a45dd9a646Jakob Stoklund Olesen } 4459e51b14faa55225a3175c4af9c69f5a45dd9a646Jakob Stoklund Olesen } else { 4469e51b14faa55225a3175c4af9c69f5a45dd9a646Jakob Stoklund Olesen // We just inserted this copy. 4479e51b14faa55225a3175c4af9c69f5a45dd9a646Jakob Stoklund Olesen KillInst = prior(InsertPos); 44804223909b74fd0634ba26d434fa7fdf2f3c7444fJakob Stoklund Olesen } 4492adfa7e9320e79859beb556367ea607a329866b3Chris Lattner } 45074215fc29fa748e006c0309671555d5873bac56aJakob Stoklund Olesen assert(KillInst->readsRegister(SrcReg) && "Cannot find kill instruction"); 451e35e3c33dc5533dd1e8ab7d9f4039cc1429d56aaJakob Stoklund Olesen 4522adfa7e9320e79859beb556367ea607a329866b3Chris Lattner // Finally, mark it killed. 4532adfa7e9320e79859beb556367ea607a329866b3Chris Lattner LV->addVirtualRegisterKilled(SrcReg, KillInst); 4546db0756f021a7b9c84d3bb7ae50498feb080a013Chris Lattner 4556db0756f021a7b9c84d3bb7ae50498feb080a013Chris Lattner // This vreg no longer lives all of the way through opBlock. 4566db0756f021a7b9c84d3bb7ae50498feb080a013Chris Lattner unsigned opBlockNum = opBlock.getNumber(); 457e35e3c33dc5533dd1e8ab7d9f4039cc1429d56aaJakob Stoklund Olesen LV->getVarInfo(SrcReg).AliveBlocks.reset(opBlockNum); 458bc40e898e153c9b81f246a7971eaac7b14446c49Chris Lattner } 459b7cfac32f32f17e64a5addfdb833702160650f14Cameron Zwarich 460b7cfac32f32f17e64a5addfdb833702160650f14Cameron Zwarich if (LIS) { 461b7cfac32f32f17e64a5addfdb833702160650f14Cameron Zwarich if (NewSrcInstr) { 462b7cfac32f32f17e64a5addfdb833702160650f14Cameron Zwarich LIS->InsertMachineInstrInMaps(NewSrcInstr); 463b7cfac32f32f17e64a5addfdb833702160650f14Cameron Zwarich LIS->addLiveRangeToEndOfBlock(IncomingReg, NewSrcInstr); 464b7cfac32f32f17e64a5addfdb833702160650f14Cameron Zwarich } 465b7cfac32f32f17e64a5addfdb833702160650f14Cameron Zwarich 466b7cfac32f32f17e64a5addfdb833702160650f14Cameron Zwarich if (!SrcUndef && 467b7cfac32f32f17e64a5addfdb833702160650f14Cameron Zwarich !VRegPHIUseCount[BBVRegPair(opBlock.getNumber(), SrcReg)]) { 468b7cfac32f32f17e64a5addfdb833702160650f14Cameron Zwarich LiveInterval &SrcLI = LIS->getInterval(SrcReg); 469b7cfac32f32f17e64a5addfdb833702160650f14Cameron Zwarich 470b7cfac32f32f17e64a5addfdb833702160650f14Cameron Zwarich bool isLiveOut = false; 471b7cfac32f32f17e64a5addfdb833702160650f14Cameron Zwarich for (MachineBasicBlock::succ_iterator SI = opBlock.succ_begin(), 472b7cfac32f32f17e64a5addfdb833702160650f14Cameron Zwarich SE = opBlock.succ_end(); SI != SE; ++SI) { 4734930e7266b7643410cfbbed5ef6e4d3b19178918Cameron Zwarich SlotIndex startIdx = LIS->getMBBStartIdx(*SI); 4744930e7266b7643410cfbbed5ef6e4d3b19178918Cameron Zwarich VNInfo *VNI = SrcLI.getVNInfoAt(startIdx); 4754930e7266b7643410cfbbed5ef6e4d3b19178918Cameron Zwarich 4764930e7266b7643410cfbbed5ef6e4d3b19178918Cameron Zwarich // Definitions by other PHIs are not truly live-in for our purposes. 4774930e7266b7643410cfbbed5ef6e4d3b19178918Cameron Zwarich if (VNI && VNI->def != startIdx) { 478b7cfac32f32f17e64a5addfdb833702160650f14Cameron Zwarich isLiveOut = true; 479b7cfac32f32f17e64a5addfdb833702160650f14Cameron Zwarich break; 480b7cfac32f32f17e64a5addfdb833702160650f14Cameron Zwarich } 481b7cfac32f32f17e64a5addfdb833702160650f14Cameron Zwarich } 482b7cfac32f32f17e64a5addfdb833702160650f14Cameron Zwarich 483b7cfac32f32f17e64a5addfdb833702160650f14Cameron Zwarich if (!isLiveOut) { 484b7cfac32f32f17e64a5addfdb833702160650f14Cameron Zwarich MachineBasicBlock::iterator KillInst = opBlock.end(); 485b7cfac32f32f17e64a5addfdb833702160650f14Cameron Zwarich MachineBasicBlock::iterator FirstTerm = opBlock.getFirstTerminator(); 486b7cfac32f32f17e64a5addfdb833702160650f14Cameron Zwarich for (MachineBasicBlock::iterator Term = FirstTerm; 487b7cfac32f32f17e64a5addfdb833702160650f14Cameron Zwarich Term != opBlock.end(); ++Term) { 488b7cfac32f32f17e64a5addfdb833702160650f14Cameron Zwarich if (Term->readsRegister(SrcReg)) 489b7cfac32f32f17e64a5addfdb833702160650f14Cameron Zwarich KillInst = Term; 490b7cfac32f32f17e64a5addfdb833702160650f14Cameron Zwarich } 491b7cfac32f32f17e64a5addfdb833702160650f14Cameron Zwarich 492b7cfac32f32f17e64a5addfdb833702160650f14Cameron Zwarich if (KillInst == opBlock.end()) { 493b7cfac32f32f17e64a5addfdb833702160650f14Cameron Zwarich // No terminator uses the register. 494b7cfac32f32f17e64a5addfdb833702160650f14Cameron Zwarich 495b7cfac32f32f17e64a5addfdb833702160650f14Cameron Zwarich if (reusedIncoming || !IncomingReg) { 496b7cfac32f32f17e64a5addfdb833702160650f14Cameron Zwarich // We may have to rewind a bit if we didn't just insert a copy. 497b7cfac32f32f17e64a5addfdb833702160650f14Cameron Zwarich KillInst = FirstTerm; 498b7cfac32f32f17e64a5addfdb833702160650f14Cameron Zwarich while (KillInst != opBlock.begin()) { 499b7cfac32f32f17e64a5addfdb833702160650f14Cameron Zwarich --KillInst; 500b7cfac32f32f17e64a5addfdb833702160650f14Cameron Zwarich if (KillInst->isDebugValue()) 501b7cfac32f32f17e64a5addfdb833702160650f14Cameron Zwarich continue; 502b7cfac32f32f17e64a5addfdb833702160650f14Cameron Zwarich if (KillInst->readsRegister(SrcReg)) 503b7cfac32f32f17e64a5addfdb833702160650f14Cameron Zwarich break; 504b7cfac32f32f17e64a5addfdb833702160650f14Cameron Zwarich } 505b7cfac32f32f17e64a5addfdb833702160650f14Cameron Zwarich } else { 506b7cfac32f32f17e64a5addfdb833702160650f14Cameron Zwarich // We just inserted this copy. 507b7cfac32f32f17e64a5addfdb833702160650f14Cameron Zwarich KillInst = prior(InsertPos); 508b7cfac32f32f17e64a5addfdb833702160650f14Cameron Zwarich } 509b7cfac32f32f17e64a5addfdb833702160650f14Cameron Zwarich } 510b7cfac32f32f17e64a5addfdb833702160650f14Cameron Zwarich assert(KillInst->readsRegister(SrcReg) && 511b7cfac32f32f17e64a5addfdb833702160650f14Cameron Zwarich "Cannot find kill instruction"); 512b7cfac32f32f17e64a5addfdb833702160650f14Cameron Zwarich 513b7cfac32f32f17e64a5addfdb833702160650f14Cameron Zwarich SlotIndex LastUseIndex = LIS->getInstructionIndex(KillInst); 514b7cfac32f32f17e64a5addfdb833702160650f14Cameron Zwarich SrcLI.removeRange(LastUseIndex.getRegSlot(), 515b7cfac32f32f17e64a5addfdb833702160650f14Cameron Zwarich LIS->getMBBEndIdx(&opBlock)); 516b7cfac32f32f17e64a5addfdb833702160650f14Cameron Zwarich } 517b7cfac32f32f17e64a5addfdb833702160650f14Cameron Zwarich } 518b7cfac32f32f17e64a5addfdb833702160650f14Cameron Zwarich } 519bc40e898e153c9b81f246a7971eaac7b14446c49Chris Lattner } 520e35e3c33dc5533dd1e8ab7d9f4039cc1429d56aaJakob Stoklund Olesen 52174215fc29fa748e006c0309671555d5873bac56aJakob Stoklund Olesen // Really delete the PHI instruction now, if it is not in the LoweredPHIs map. 522b7cfac32f32f17e64a5addfdb833702160650f14Cameron Zwarich if (reusedIncoming || !IncomingReg) { 523b7cfac32f32f17e64a5addfdb833702160650f14Cameron Zwarich if (LIS) 524b7cfac32f32f17e64a5addfdb833702160650f14Cameron Zwarich LIS->RemoveMachineInstrFromMaps(MPhi); 52574215fc29fa748e006c0309671555d5873bac56aJakob Stoklund Olesen MF.DeleteMachineInstr(MPhi); 526b7cfac32f32f17e64a5addfdb833702160650f14Cameron Zwarich } 527bc40e898e153c9b81f246a7971eaac7b14446c49Chris Lattner} 528ca756d2cf9bd88f210d61dd5f9776920a6178441Bill Wendling 529ca756d2cf9bd88f210d61dd5f9776920a6178441Bill Wendling/// analyzePHINodes - Gather information about the PHI nodes in here. In 530ca756d2cf9bd88f210d61dd5f9776920a6178441Bill Wendling/// particular, we want to map the number of uses of a virtual register which is 531ca756d2cf9bd88f210d61dd5f9776920a6178441Bill Wendling/// used in a PHI node. We map that to the BB the vreg is coming from. This is 532ca756d2cf9bd88f210d61dd5f9776920a6178441Bill Wendling/// used later to determine when the vreg is killed in the BB. 533ca756d2cf9bd88f210d61dd5f9776920a6178441Bill Wendling/// 5340a3fdd6e11cd351737b4451c05ec5d794e6855cfCameron Zwarichvoid PHIElimination::analyzePHINodes(const MachineFunction& MF) { 53528428cd6f31c1ea3cf4cea03e64189a4c32b84a3Evan Cheng for (MachineFunction::const_iterator I = MF.begin(), E = MF.end(); 536ca756d2cf9bd88f210d61dd5f9776920a6178441Bill Wendling I != E; ++I) 537ca756d2cf9bd88f210d61dd5f9776920a6178441Bill Wendling for (MachineBasicBlock::const_iterator BBI = I->begin(), BBE = I->end(); 538518bb53485df640d7b7e3f6b0544099020c42aa7Chris Lattner BBI != BBE && BBI->isPHI(); ++BBI) 539ca756d2cf9bd88f210d61dd5f9776920a6178441Bill Wendling for (unsigned i = 1, e = BBI->getNumOperands(); i != e; i += 2) 54074215fc29fa748e006c0309671555d5873bac56aJakob Stoklund Olesen ++VRegPHIUseCount[BBVRegPair(BBI->getOperand(i+1).getMBB()->getNumber(), 5418aa797aa51cd4ea1ec6f46f4891a6897944b75b2Chris Lattner BBI->getOperand(i).getReg())]; 542ca756d2cf9bd88f210d61dd5f9776920a6178441Bill Wendling} 543e35e3c33dc5533dd1e8ab7d9f4039cc1429d56aaJakob Stoklund Olesen 5440a3fdd6e11cd351737b4451c05ec5d794e6855cfCameron Zwarichbool PHIElimination::SplitPHIEdges(MachineFunction &MF, 54561a733434d9ee6518b8ddb116594bef7206cb627Cameron Zwarich MachineBasicBlock &MBB, 54661a733434d9ee6518b8ddb116594bef7206cb627Cameron Zwarich MachineLoopInfo *MLI) { 547518bb53485df640d7b7e3f6b0544099020c42aa7Chris Lattner if (MBB.empty() || !MBB.front().isPHI() || MBB.isLandingPad()) 5483e20475feebca3bfb29375ac7f3e5acbeb2a95c8Jakob Stoklund Olesen return false; // Quick exit for basic blocks without PHIs. 5490257dd375d64da978887d0c1e97ab3560d7597ceJakob Stoklund Olesen 550c321a20b2e250a755bd06f36d896d00d9fd396adJakob Stoklund Olesen const MachineLoop *CurLoop = MLI ? MLI->getLoopFor(&MBB) : 0; 551c321a20b2e250a755bd06f36d896d00d9fd396adJakob Stoklund Olesen bool IsLoopHeader = CurLoop && &MBB == CurLoop->getHeader(); 552c321a20b2e250a755bd06f36d896d00d9fd396adJakob Stoklund Olesen 55397b9b97853d7e4fbb5c8460ef28126013c76e9a9Evan Cheng bool Changed = false; 5547c2a4a30e0e16762c75adacebd05ec9fcbccf16bEvan Cheng for (MachineBasicBlock::iterator BBI = MBB.begin(), BBE = MBB.end(); 555518bb53485df640d7b7e3f6b0544099020c42aa7Chris Lattner BBI != BBE && BBI->isPHI(); ++BBI) { 556f235f13931835b3335f3f2ff2d3060381b93626cJakob Stoklund Olesen for (unsigned i = 1, e = BBI->getNumOperands(); i != e; i += 2) { 557f235f13931835b3335f3f2ff2d3060381b93626cJakob Stoklund Olesen unsigned Reg = BBI->getOperand(i).getReg(); 558f235f13931835b3335f3f2ff2d3060381b93626cJakob Stoklund Olesen MachineBasicBlock *PreMBB = BBI->getOperand(i+1).getMBB(); 559c321a20b2e250a755bd06f36d896d00d9fd396adJakob Stoklund Olesen // Is there a critical edge from PreMBB to MBB? 560c321a20b2e250a755bd06f36d896d00d9fd396adJakob Stoklund Olesen if (PreMBB->succ_size() == 1) 561c321a20b2e250a755bd06f36d896d00d9fd396adJakob Stoklund Olesen continue; 562c321a20b2e250a755bd06f36d896d00d9fd396adJakob Stoklund Olesen 563e008384508342a2dec110eafaa87d93614976990Evan Cheng // Avoid splitting backedges of loops. It would introduce small 564e008384508342a2dec110eafaa87d93614976990Evan Cheng // out-of-line blocks into the loop which is very bad for code placement. 5655758a711f4e593d1daff3bae0fa9d694e5980719Cameron Zwarich if (PreMBB == &MBB && !SplitAllCriticalEdges) 566c321a20b2e250a755bd06f36d896d00d9fd396adJakob Stoklund Olesen continue; 567c321a20b2e250a755bd06f36d896d00d9fd396adJakob Stoklund Olesen const MachineLoop *PreLoop = MLI ? MLI->getLoopFor(PreMBB) : 0; 5685758a711f4e593d1daff3bae0fa9d694e5980719Cameron Zwarich if (IsLoopHeader && PreLoop == CurLoop && !SplitAllCriticalEdges) 569c321a20b2e250a755bd06f36d896d00d9fd396adJakob Stoklund Olesen continue; 570c321a20b2e250a755bd06f36d896d00d9fd396adJakob Stoklund Olesen 571c321a20b2e250a755bd06f36d896d00d9fd396adJakob Stoklund Olesen // LV doesn't consider a phi use live-out, so isLiveOut only returns true 572c321a20b2e250a755bd06f36d896d00d9fd396adJakob Stoklund Olesen // when the source register is live-out for some other reason than a phi 573c321a20b2e250a755bd06f36d896d00d9fd396adJakob Stoklund Olesen // use. That means the copy we will insert in PreMBB won't be a kill, and 574c321a20b2e250a755bd06f36d896d00d9fd396adJakob Stoklund Olesen // there is a risk it may not be coalesced away. 575c321a20b2e250a755bd06f36d896d00d9fd396adJakob Stoklund Olesen // 576c321a20b2e250a755bd06f36d896d00d9fd396adJakob Stoklund Olesen // If the copy would be a kill, there is no need to split the edge. 5775758a711f4e593d1daff3bae0fa9d694e5980719Cameron Zwarich if (!isLiveOutPastPHIs(Reg, PreMBB) && !SplitAllCriticalEdges) 578c321a20b2e250a755bd06f36d896d00d9fd396adJakob Stoklund Olesen continue; 579c321a20b2e250a755bd06f36d896d00d9fd396adJakob Stoklund Olesen 580c321a20b2e250a755bd06f36d896d00d9fd396adJakob Stoklund Olesen DEBUG(dbgs() << PrintReg(Reg) << " live-out before critical edge BB#" 581c321a20b2e250a755bd06f36d896d00d9fd396adJakob Stoklund Olesen << PreMBB->getNumber() << " -> BB#" << MBB.getNumber() 582c321a20b2e250a755bd06f36d896d00d9fd396adJakob Stoklund Olesen << ": " << *BBI); 583c321a20b2e250a755bd06f36d896d00d9fd396adJakob Stoklund Olesen 584c321a20b2e250a755bd06f36d896d00d9fd396adJakob Stoklund Olesen // If Reg is not live-in to MBB, it means it must be live-in to some 585c321a20b2e250a755bd06f36d896d00d9fd396adJakob Stoklund Olesen // other PreMBB successor, and we can avoid the interference by splitting 586c321a20b2e250a755bd06f36d896d00d9fd396adJakob Stoklund Olesen // the edge. 587c321a20b2e250a755bd06f36d896d00d9fd396adJakob Stoklund Olesen // 588c321a20b2e250a755bd06f36d896d00d9fd396adJakob Stoklund Olesen // If Reg *is* live-in to MBB, the interference is inevitable and a copy 589c321a20b2e250a755bd06f36d896d00d9fd396adJakob Stoklund Olesen // is likely to be left after coalescing. If we are looking at a loop 590c321a20b2e250a755bd06f36d896d00d9fd396adJakob Stoklund Olesen // exiting edge, split it so we won't insert code in the loop, otherwise 591c321a20b2e250a755bd06f36d896d00d9fd396adJakob Stoklund Olesen // don't bother. 5925758a711f4e593d1daff3bae0fa9d694e5980719Cameron Zwarich bool ShouldSplit = !isLiveIn(Reg, &MBB) || SplitAllCriticalEdges; 593c321a20b2e250a755bd06f36d896d00d9fd396adJakob Stoklund Olesen 594c321a20b2e250a755bd06f36d896d00d9fd396adJakob Stoklund Olesen // Check for a loop exiting edge. 595c321a20b2e250a755bd06f36d896d00d9fd396adJakob Stoklund Olesen if (!ShouldSplit && CurLoop != PreLoop) { 596c321a20b2e250a755bd06f36d896d00d9fd396adJakob Stoklund Olesen DEBUG({ 597c321a20b2e250a755bd06f36d896d00d9fd396adJakob Stoklund Olesen dbgs() << "Split wouldn't help, maybe avoid loop copies?\n"; 598c321a20b2e250a755bd06f36d896d00d9fd396adJakob Stoklund Olesen if (PreLoop) dbgs() << "PreLoop: " << *PreLoop; 599c321a20b2e250a755bd06f36d896d00d9fd396adJakob Stoklund Olesen if (CurLoop) dbgs() << "CurLoop: " << *CurLoop; 600c321a20b2e250a755bd06f36d896d00d9fd396adJakob Stoklund Olesen }); 601c321a20b2e250a755bd06f36d896d00d9fd396adJakob Stoklund Olesen // This edge could be entering a loop, exiting a loop, or it could be 602c321a20b2e250a755bd06f36d896d00d9fd396adJakob Stoklund Olesen // both: Jumping directly form one loop to the header of a sibling 603c321a20b2e250a755bd06f36d896d00d9fd396adJakob Stoklund Olesen // loop. 604c321a20b2e250a755bd06f36d896d00d9fd396adJakob Stoklund Olesen // Split unless this edge is entering CurLoop from an outer loop. 605c321a20b2e250a755bd06f36d896d00d9fd396adJakob Stoklund Olesen ShouldSplit = PreLoop && !PreLoop->contains(CurLoop); 606c321a20b2e250a755bd06f36d896d00d9fd396adJakob Stoklund Olesen } 607c321a20b2e250a755bd06f36d896d00d9fd396adJakob Stoklund Olesen if (!ShouldSplit) 608c321a20b2e250a755bd06f36d896d00d9fd396adJakob Stoklund Olesen continue; 609c321a20b2e250a755bd06f36d896d00d9fd396adJakob Stoklund Olesen if (!PreMBB->SplitCriticalEdge(&MBB, this)) { 610c321a20b2e250a755bd06f36d896d00d9fd396adJakob Stoklund Olesen DEBUG(dbgs() << "Failed to split ciritcal edge.\n"); 611c321a20b2e250a755bd06f36d896d00d9fd396adJakob Stoklund Olesen continue; 612e008384508342a2dec110eafaa87d93614976990Evan Cheng } 613c321a20b2e250a755bd06f36d896d00d9fd396adJakob Stoklund Olesen Changed = true; 614c321a20b2e250a755bd06f36d896d00d9fd396adJakob Stoklund Olesen ++NumCriticalEdgesSplit; 615f235f13931835b3335f3f2ff2d3060381b93626cJakob Stoklund Olesen } 616f235f13931835b3335f3f2ff2d3060381b93626cJakob Stoklund Olesen } 617688521ca6f936cb51549b0d505aa89746561263bCameron Zwarich return Changed; 618f235f13931835b3335f3f2ff2d3060381b93626cJakob Stoklund Olesen} 61936f54480f83d47404aceea5d41f8f6b95da2d00bCameron Zwarich 62036f54480f83d47404aceea5d41f8f6b95da2d00bCameron Zwarichbool PHIElimination::isLiveIn(unsigned Reg, MachineBasicBlock *MBB) { 62136f54480f83d47404aceea5d41f8f6b95da2d00bCameron Zwarich assert((LV || LIS) && 62236f54480f83d47404aceea5d41f8f6b95da2d00bCameron Zwarich "isLiveIn() requires either LiveVariables or LiveIntervals"); 62336f54480f83d47404aceea5d41f8f6b95da2d00bCameron Zwarich if (LIS) 62436f54480f83d47404aceea5d41f8f6b95da2d00bCameron Zwarich return LIS->isLiveInToMBB(LIS->getInterval(Reg), MBB); 62536f54480f83d47404aceea5d41f8f6b95da2d00bCameron Zwarich else 62636f54480f83d47404aceea5d41f8f6b95da2d00bCameron Zwarich return LV->isLiveIn(Reg, *MBB); 62736f54480f83d47404aceea5d41f8f6b95da2d00bCameron Zwarich} 62836f54480f83d47404aceea5d41f8f6b95da2d00bCameron Zwarich 62936f54480f83d47404aceea5d41f8f6b95da2d00bCameron Zwarichbool PHIElimination::isLiveOutPastPHIs(unsigned Reg, MachineBasicBlock *MBB) { 63036f54480f83d47404aceea5d41f8f6b95da2d00bCameron Zwarich assert((LV || LIS) && 63136f54480f83d47404aceea5d41f8f6b95da2d00bCameron Zwarich "isLiveOutPastPHIs() requires either LiveVariables or LiveIntervals"); 63236f54480f83d47404aceea5d41f8f6b95da2d00bCameron Zwarich // LiveVariables considers uses in PHIs to be in the predecessor basic block, 63336f54480f83d47404aceea5d41f8f6b95da2d00bCameron Zwarich // so that a register used only in a PHI is not live out of the block. In 63436f54480f83d47404aceea5d41f8f6b95da2d00bCameron Zwarich // contrast, LiveIntervals considers uses in PHIs to be on the edge rather than 63536f54480f83d47404aceea5d41f8f6b95da2d00bCameron Zwarich // in the predecessor basic block, so that a register used only in a PHI is live 63636f54480f83d47404aceea5d41f8f6b95da2d00bCameron Zwarich // out of the block. 63736f54480f83d47404aceea5d41f8f6b95da2d00bCameron Zwarich if (LIS) { 63836f54480f83d47404aceea5d41f8f6b95da2d00bCameron Zwarich const LiveInterval &LI = LIS->getInterval(Reg); 63936f54480f83d47404aceea5d41f8f6b95da2d00bCameron Zwarich for (MachineBasicBlock::succ_iterator SI = MBB->succ_begin(), 64036f54480f83d47404aceea5d41f8f6b95da2d00bCameron Zwarich SE = MBB->succ_end(); SI != SE; ++SI) { 64136f54480f83d47404aceea5d41f8f6b95da2d00bCameron Zwarich if (LI.liveAt(LIS->getMBBStartIdx(*SI))) 64236f54480f83d47404aceea5d41f8f6b95da2d00bCameron Zwarich return true; 64336f54480f83d47404aceea5d41f8f6b95da2d00bCameron Zwarich } 64436f54480f83d47404aceea5d41f8f6b95da2d00bCameron Zwarich return false; 64536f54480f83d47404aceea5d41f8f6b95da2d00bCameron Zwarich } else { 64636f54480f83d47404aceea5d41f8f6b95da2d00bCameron Zwarich return LV->isLiveOut(Reg, *MBB); 64736f54480f83d47404aceea5d41f8f6b95da2d00bCameron Zwarich } 64836f54480f83d47404aceea5d41f8f6b95da2d00bCameron Zwarich} 649