PHIElimination.cpp revision 28428cd6f31c1ea3cf4cea03e64189a4c32b84a3
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" 17fae02a2ab19abdf12854356e19aeb1da62a0b8eaLang Hames#include "PHIElimination.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" 2384bc5427d6883f73cfeae3da640acd011d35c006Chris Lattner#include "llvm/CodeGen/MachineRegisterInfo.h" 24518bb53485df640d7b7e3f6b0544099020c42aa7Chris Lattner#include "llvm/Target/TargetInstrInfo.h" 253e20475feebca3bfb29375ac7f3e5acbeb2a95c8Jakob Stoklund Olesen#include "llvm/Function.h" 26bc40e898e153c9b81f246a7971eaac7b14446c49Chris Lattner#include "llvm/Target/TargetMachine.h" 27576a27043d95d0b9b8a010bccfd38ed9c0afa739Evan Cheng#include "llvm/ADT/SmallPtrSet.h" 28551ccae044b0ff658fe629dd67edd5ffe75d10e8Reid Spencer#include "llvm/ADT/STLExtras.h" 296db0756f021a7b9c84d3bb7ae50498feb080a013Chris Lattner#include "llvm/ADT/Statistic.h" 30f235f13931835b3335f3f2ff2d3060381b93626cJakob Stoklund Olesen#include "llvm/Support/CommandLine.h" 31a4f0b3a084d120cfc5b5bb06f64b222f5cb72740Chris Lattner#include "llvm/Support/Compiler.h" 32f235f13931835b3335f3f2ff2d3060381b93626cJakob Stoklund Olesen#include "llvm/Support/Debug.h" 336db0756f021a7b9c84d3bb7ae50498feb080a013Chris Lattner#include <algorithm> 341088317675dd34a1823f427e472fb9e43c616cb1Evan Cheng#include <map> 350742b59913a7760eb26f08121cd244a37e83e3b3Chris Lattnerusing namespace llvm; 36d0fde30ce850b78371fd1386338350591f9ff494Brian Gaeke 37cd3245ac45c595da96bb768a55cddc356dff55feChris LattnerSTATISTIC(NumAtomic, "Number of atomic phis lowered"); 38f235f13931835b3335f3f2ff2d3060381b93626cJakob Stoklund OlesenSTATISTIC(NumSplits, "Number of critical edges split on demand"); 3974215fc29fa748e006c0309671555d5873bac56aJakob Stoklund OlesenSTATISTIC(NumReused, "Number of reused lowered phis"); 40f235f13931835b3335f3f2ff2d3060381b93626cJakob Stoklund Olesen 41fae02a2ab19abdf12854356e19aeb1da62a0b8eaLang Hameschar PHIElimination::ID = 0; 42fae02a2ab19abdf12854356e19aeb1da62a0b8eaLang Hamesstatic RegisterPass<PHIElimination> 43844731a7f1909f55935e3514c9e713a62d67662eDan GohmanX("phi-node-elimination", "Eliminate PHI nodes for register allocation"); 44844731a7f1909f55935e3514c9e713a62d67662eDan Gohman 456ddba2b933645d308428201e942abe1274fa5085Dan Gohmanconst PassInfo *const llvm::PHIEliminationID = &X; 46bc40e898e153c9b81f246a7971eaac7b14446c49Chris Lattner 47fae02a2ab19abdf12854356e19aeb1da62a0b8eaLang Hamesvoid llvm::PHIElimination::getAnalysisUsage(AnalysisUsage &AU) const { 48845012e6d31799c7fbd1193fa1af8ee2d12e9231Dan Gohman AU.addPreserved<LiveVariables>(); 499aebb61daf4d787aa7dcff9e3caa89bac88e11d1Jakob Stoklund Olesen AU.addPreserved<MachineDominatorTree>(); 500257dd375d64da978887d0c1e97ab3560d7597ceJakob Stoklund Olesen // rdar://7401784 This would be nice: 510257dd375d64da978887d0c1e97ab3560d7597ceJakob Stoklund Olesen // AU.addPreservedID(MachineLoopInfoID); 52845012e6d31799c7fbd1193fa1af8ee2d12e9231Dan Gohman MachineFunctionPass::getAnalysisUsage(AU); 53845012e6d31799c7fbd1193fa1af8ee2d12e9231Dan Gohman} 54fae02a2ab19abdf12854356e19aeb1da62a0b8eaLang Hames 5528428cd6f31c1ea3cf4cea03e64189a4c32b84a3Evan Chengbool llvm::PHIElimination::runOnMachineFunction(MachineFunction &MF) { 5628428cd6f31c1ea3cf4cea03e64189a4c32b84a3Evan Cheng MRI = &MF.getRegInfo(); 57576a27043d95d0b9b8a010bccfd38ed9c0afa739Evan Cheng 58576a27043d95d0b9b8a010bccfd38ed9c0afa739Evan Cheng bool Changed = false; 59576a27043d95d0b9b8a010bccfd38ed9c0afa739Evan Cheng 603e20475feebca3bfb29375ac7f3e5acbeb2a95c8Jakob Stoklund Olesen // Split critical edges to help the coalescer 610257dd375d64da978887d0c1e97ab3560d7597ceJakob Stoklund Olesen if (LiveVariables *LV = getAnalysisIfAvailable<LiveVariables>()) 6228428cd6f31c1ea3cf4cea03e64189a4c32b84a3Evan Cheng for (MachineFunction::iterator I = MF.begin(), E = MF.end(); I != E; ++I) 6328428cd6f31c1ea3cf4cea03e64189a4c32b84a3Evan Cheng Changed |= SplitPHIEdges(MF, *I, *LV); 643e20475feebca3bfb29375ac7f3e5acbeb2a95c8Jakob Stoklund Olesen 653e20475feebca3bfb29375ac7f3e5acbeb2a95c8Jakob Stoklund Olesen // Populate VRegPHIUseCount 6628428cd6f31c1ea3cf4cea03e64189a4c32b84a3Evan Cheng analyzePHINodes(MF); 673e20475feebca3bfb29375ac7f3e5acbeb2a95c8Jakob Stoklund Olesen 68576a27043d95d0b9b8a010bccfd38ed9c0afa739Evan Cheng // Eliminate PHI instructions by inserting copies into predecessor blocks. 6928428cd6f31c1ea3cf4cea03e64189a4c32b84a3Evan Cheng for (MachineFunction::iterator I = MF.begin(), E = MF.end(); I != E; ++I) 7028428cd6f31c1ea3cf4cea03e64189a4c32b84a3Evan Cheng Changed |= EliminatePHINodes(MF, *I); 71576a27043d95d0b9b8a010bccfd38ed9c0afa739Evan Cheng 72576a27043d95d0b9b8a010bccfd38ed9c0afa739Evan Cheng // Remove dead IMPLICIT_DEF instructions. 733de8249078354d25b37b40e0f10b4f88226d3dd4Bill Wendling for (SmallPtrSet<MachineInstr*, 4>::iterator I = ImpDefs.begin(), 74576a27043d95d0b9b8a010bccfd38ed9c0afa739Evan Cheng E = ImpDefs.end(); I != E; ++I) { 75576a27043d95d0b9b8a010bccfd38ed9c0afa739Evan Cheng MachineInstr *DefMI = *I; 76576a27043d95d0b9b8a010bccfd38ed9c0afa739Evan Cheng unsigned DefReg = DefMI->getOperand(0).getReg(); 7748f2cb926e2512a1c4c33ca5a9e757de1c12036cEvan Cheng if (MRI->use_nodbg_empty(DefReg)) 78576a27043d95d0b9b8a010bccfd38ed9c0afa739Evan Cheng DefMI->eraseFromParent(); 79576a27043d95d0b9b8a010bccfd38ed9c0afa739Evan Cheng } 80576a27043d95d0b9b8a010bccfd38ed9c0afa739Evan Cheng 8174215fc29fa748e006c0309671555d5873bac56aJakob Stoklund Olesen // Clean up the lowered PHI instructions. 8274215fc29fa748e006c0309671555d5873bac56aJakob Stoklund Olesen for (LoweredPHIMap::iterator I = LoweredPHIs.begin(), E = LoweredPHIs.end(); 8374215fc29fa748e006c0309671555d5873bac56aJakob Stoklund Olesen I != E; ++I) 8428428cd6f31c1ea3cf4cea03e64189a4c32b84a3Evan Cheng MF.DeleteMachineInstr(I->first); 8574215fc29fa748e006c0309671555d5873bac56aJakob Stoklund Olesen 863de8249078354d25b37b40e0f10b4f88226d3dd4Bill Wendling LoweredPHIs.clear(); 87576a27043d95d0b9b8a010bccfd38ed9c0afa739Evan Cheng ImpDefs.clear(); 88576a27043d95d0b9b8a010bccfd38ed9c0afa739Evan Cheng VRegPHIUseCount.clear(); 8928428cd6f31c1ea3cf4cea03e64189a4c32b84a3Evan Cheng 90576a27043d95d0b9b8a010bccfd38ed9c0afa739Evan Cheng return Changed; 91576a27043d95d0b9b8a010bccfd38ed9c0afa739Evan Cheng} 92576a27043d95d0b9b8a010bccfd38ed9c0afa739Evan Cheng 93bc40e898e153c9b81f246a7971eaac7b14446c49Chris Lattner/// EliminatePHINodes - Eliminate phi nodes by inserting copy instructions in 94bc40e898e153c9b81f246a7971eaac7b14446c49Chris Lattner/// predecessor basic blocks. 95bc40e898e153c9b81f246a7971eaac7b14446c49Chris Lattner/// 96fae02a2ab19abdf12854356e19aeb1da62a0b8eaLang Hamesbool llvm::PHIElimination::EliminatePHINodes(MachineFunction &MF, 97fae02a2ab19abdf12854356e19aeb1da62a0b8eaLang Hames MachineBasicBlock &MBB) { 98518bb53485df640d7b7e3f6b0544099020c42aa7Chris Lattner if (MBB.empty() || !MBB.front().isPHI()) 9953a79aaae988d9dc9d12af8970f8b8fe58cc478dChris Lattner return false; // Quick exit for basic blocks without PHIs. 100bc40e898e153c9b81f246a7971eaac7b14446c49Chris Lattner 101791f896d9f8a38b3806878867d61c114069b6195Chris Lattner // Get an iterator to the first instruction after the last PHI node (this may 10253a79aaae988d9dc9d12af8970f8b8fe58cc478dChris Lattner // also be the end of the basic block). 103a5fec0dba34206274041543b5924d2565fb10f9bDuncan Sands MachineBasicBlock::iterator AfterPHIsIt = SkipPHIsAndLabels(MBB, MBB.begin()); 104791f896d9f8a38b3806878867d61c114069b6195Chris Lattner 105518bb53485df640d7b7e3f6b0544099020c42aa7Chris Lattner while (MBB.front().isPHI()) 106ca756d2cf9bd88f210d61dd5f9776920a6178441Bill Wendling LowerAtomicPHINode(MBB, AfterPHIsIt); 107ca756d2cf9bd88f210d61dd5f9776920a6178441Bill Wendling 10853a79aaae988d9dc9d12af8970f8b8fe58cc478dChris Lattner return true; 10953a79aaae988d9dc9d12af8970f8b8fe58cc478dChris Lattner} 110edf128a7fa90f2b0b7ee24741a04a7ae1ecd6f7eMisha Brukman 1111b38ec83f07d5801035567160008cd7cb99a5c1aEvan Cheng/// isSourceDefinedByImplicitDef - Return true if all sources of the phi node 1121b38ec83f07d5801035567160008cd7cb99a5c1aEvan Cheng/// are implicit_def's. 113ae94dda61a045cb77681940ecc25aba0d2763f74Bill Wendlingstatic bool isSourceDefinedByImplicitDef(const MachineInstr *MPhi, 1141b38ec83f07d5801035567160008cd7cb99a5c1aEvan Cheng const MachineRegisterInfo *MRI) { 115b3e0a6d75c60f01df4fcee4b4309f06ce92a96c9Evan Cheng for (unsigned i = 1; i != MPhi->getNumOperands(); i += 2) { 116b3e0a6d75c60f01df4fcee4b4309f06ce92a96c9Evan Cheng unsigned SrcReg = MPhi->getOperand(i).getReg(); 117ae94dda61a045cb77681940ecc25aba0d2763f74Bill Wendling const MachineInstr *DefMI = MRI->getVRegDef(SrcReg); 118518bb53485df640d7b7e3f6b0544099020c42aa7Chris Lattner if (!DefMI || !DefMI->isImplicitDef()) 119b3e0a6d75c60f01df4fcee4b4309f06ce92a96c9Evan Cheng return false; 120b3e0a6d75c60f01df4fcee4b4309f06ce92a96c9Evan Cheng } 121b3e0a6d75c60f01df4fcee4b4309f06ce92a96c9Evan Cheng return true; 122f870fbc554ac862ad6d45cf97148739802a3ed12Evan Cheng} 123f870fbc554ac862ad6d45cf97148739802a3ed12Evan Cheng 1241222287543a5b5917f8c31aa8c88d740f70222d9Jakob Stoklund Olesen// FindCopyInsertPoint - Find a safe place in MBB to insert a copy from SrcReg 1251222287543a5b5917f8c31aa8c88d740f70222d9Jakob Stoklund Olesen// when following the CFG edge to SuccMBB. This needs to be after any def of 1261222287543a5b5917f8c31aa8c88d740f70222d9Jakob Stoklund Olesen// SrcReg, but before any subsequent point where control flow might jump out of 1271222287543a5b5917f8c31aa8c88d740f70222d9Jakob Stoklund Olesen// the basic block. 128fae02a2ab19abdf12854356e19aeb1da62a0b8eaLang HamesMachineBasicBlock::iterator 129fae02a2ab19abdf12854356e19aeb1da62a0b8eaLang Hamesllvm::PHIElimination::FindCopyInsertPoint(MachineBasicBlock &MBB, 1301222287543a5b5917f8c31aa8c88d740f70222d9Jakob Stoklund Olesen MachineBasicBlock &SuccMBB, 131fae02a2ab19abdf12854356e19aeb1da62a0b8eaLang Hames unsigned SrcReg) { 132a5fec0dba34206274041543b5924d2565fb10f9bDuncan Sands // Handle the trivial case trivially. 133a5fec0dba34206274041543b5924d2565fb10f9bDuncan Sands if (MBB.empty()) 134a5fec0dba34206274041543b5924d2565fb10f9bDuncan Sands return MBB.begin(); 135a5fec0dba34206274041543b5924d2565fb10f9bDuncan Sands 1361222287543a5b5917f8c31aa8c88d740f70222d9Jakob Stoklund Olesen // Usually, we just want to insert the copy before the first terminator 1371222287543a5b5917f8c31aa8c88d740f70222d9Jakob Stoklund Olesen // instruction. However, for the edge going to a landing pad, we must insert 1381222287543a5b5917f8c31aa8c88d740f70222d9Jakob Stoklund Olesen // the copy before the call/invoke instruction. 1391222287543a5b5917f8c31aa8c88d740f70222d9Jakob Stoklund Olesen if (!SuccMBB.isLandingPad()) 140a5fec0dba34206274041543b5924d2565fb10f9bDuncan Sands return MBB.getFirstTerminator(); 141a5fec0dba34206274041543b5924d2565fb10f9bDuncan Sands 142b126d0530d48890e1689975483b9f923a0fca1daLang Hames // Discover any defs/uses in this basic block. 143a5fec0dba34206274041543b5924d2565fb10f9bDuncan Sands SmallPtrSet<MachineInstr*, 8> DefUsesInMBB; 144b126d0530d48890e1689975483b9f923a0fca1daLang Hames for (MachineRegisterInfo::reg_iterator RI = MRI->reg_begin(SrcReg), 145b126d0530d48890e1689975483b9f923a0fca1daLang Hames RE = MRI->reg_end(); RI != RE; ++RI) { 146a5fec0dba34206274041543b5924d2565fb10f9bDuncan Sands MachineInstr *DefUseMI = &*RI; 147a5fec0dba34206274041543b5924d2565fb10f9bDuncan Sands if (DefUseMI->getParent() == &MBB) 148a5fec0dba34206274041543b5924d2565fb10f9bDuncan Sands DefUsesInMBB.insert(DefUseMI); 149fc0b80d9746e5fd4b45057ab814c67371fb0f9eaEvan Cheng } 150fc0b80d9746e5fd4b45057ab814c67371fb0f9eaEvan Cheng 151a5fec0dba34206274041543b5924d2565fb10f9bDuncan Sands MachineBasicBlock::iterator InsertPoint; 152a5fec0dba34206274041543b5924d2565fb10f9bDuncan Sands if (DefUsesInMBB.empty()) { 1531222287543a5b5917f8c31aa8c88d740f70222d9Jakob Stoklund Olesen // No defs. Insert the copy at the start of the basic block. 154a5fec0dba34206274041543b5924d2565fb10f9bDuncan Sands InsertPoint = MBB.begin(); 155a5fec0dba34206274041543b5924d2565fb10f9bDuncan Sands } else if (DefUsesInMBB.size() == 1) { 156b126d0530d48890e1689975483b9f923a0fca1daLang Hames // Insert the copy immediately after the def/use. 157a5fec0dba34206274041543b5924d2565fb10f9bDuncan Sands InsertPoint = *DefUsesInMBB.begin(); 158a5fec0dba34206274041543b5924d2565fb10f9bDuncan Sands ++InsertPoint; 159a5fec0dba34206274041543b5924d2565fb10f9bDuncan Sands } else { 160b126d0530d48890e1689975483b9f923a0fca1daLang Hames // Insert the copy immediately after the last def/use. 161a5fec0dba34206274041543b5924d2565fb10f9bDuncan Sands InsertPoint = MBB.end(); 162a5fec0dba34206274041543b5924d2565fb10f9bDuncan Sands while (!DefUsesInMBB.count(&*--InsertPoint)) {} 163a5fec0dba34206274041543b5924d2565fb10f9bDuncan Sands ++InsertPoint; 164fc0b80d9746e5fd4b45057ab814c67371fb0f9eaEvan Cheng } 165a5fec0dba34206274041543b5924d2565fb10f9bDuncan Sands 166a5fec0dba34206274041543b5924d2565fb10f9bDuncan Sands // Make sure the copy goes after any phi nodes however. 167a5fec0dba34206274041543b5924d2565fb10f9bDuncan Sands return SkipPHIsAndLabels(MBB, InsertPoint); 168fc0b80d9746e5fd4b45057ab814c67371fb0f9eaEvan Cheng} 169fc0b80d9746e5fd4b45057ab814c67371fb0f9eaEvan Cheng 17053a79aaae988d9dc9d12af8970f8b8fe58cc478dChris Lattner/// LowerAtomicPHINode - Lower the PHI node at the top of the specified block, 17153a79aaae988d9dc9d12af8970f8b8fe58cc478dChris Lattner/// under the assuption that it needs to be lowered in a way that supports 17253a79aaae988d9dc9d12af8970f8b8fe58cc478dChris Lattner/// atomic execution of PHIs. This lowering method is always correct all of the 17353a79aaae988d9dc9d12af8970f8b8fe58cc478dChris Lattner/// time. 174e35e3c33dc5533dd1e8ab7d9f4039cc1429d56aaJakob Stoklund Olesen/// 175fae02a2ab19abdf12854356e19aeb1da62a0b8eaLang Hamesvoid llvm::PHIElimination::LowerAtomicPHINode( 176fae02a2ab19abdf12854356e19aeb1da62a0b8eaLang Hames MachineBasicBlock &MBB, 177fae02a2ab19abdf12854356e19aeb1da62a0b8eaLang Hames MachineBasicBlock::iterator AfterPHIsIt) { 17874215fc29fa748e006c0309671555d5873bac56aJakob Stoklund Olesen ++NumAtomic; 17953a79aaae988d9dc9d12af8970f8b8fe58cc478dChris Lattner // Unlink the PHI node from the basic block, but don't delete the PHI yet. 18053a79aaae988d9dc9d12af8970f8b8fe58cc478dChris Lattner MachineInstr *MPhi = MBB.remove(MBB.begin()); 18153a79aaae988d9dc9d12af8970f8b8fe58cc478dChris Lattner 182f870fbc554ac862ad6d45cf97148739802a3ed12Evan Cheng unsigned NumSrcs = (MPhi->getNumOperands() - 1) / 2; 18353a79aaae988d9dc9d12af8970f8b8fe58cc478dChris Lattner unsigned DestReg = MPhi->getOperand(0).getReg(); 1849f1c8317a4676945b4961ddb9827ef2412551620Evan Cheng bool isDead = MPhi->getOperand(0).isDead(); 18553a79aaae988d9dc9d12af8970f8b8fe58cc478dChris Lattner 186ca756d2cf9bd88f210d61dd5f9776920a6178441Bill Wendling // Create a new register for the incoming PHI arguments. 18753a79aaae988d9dc9d12af8970f8b8fe58cc478dChris Lattner MachineFunction &MF = *MBB.getParent(); 18884bc5427d6883f73cfeae3da640acd011d35c006Chris Lattner const TargetRegisterClass *RC = MF.getRegInfo().getRegClass(DestReg); 1899f1c8317a4676945b4961ddb9827ef2412551620Evan Cheng unsigned IncomingReg = 0; 19074215fc29fa748e006c0309671555d5873bac56aJakob Stoklund Olesen bool reusedIncoming = false; // Is IncomingReg reused from an earlier PHI? 19153a79aaae988d9dc9d12af8970f8b8fe58cc478dChris Lattner 192ae94dda61a045cb77681940ecc25aba0d2763f74Bill Wendling // Insert a register to register copy at the top of the current block (but 19353a79aaae988d9dc9d12af8970f8b8fe58cc478dChris Lattner // after any remaining phi nodes) which copies the new incoming register 19453a79aaae988d9dc9d12af8970f8b8fe58cc478dChris Lattner // into the phi node destination. 195d10fd9791c20fd8368fa0ce94b626b769c6c8ba0Owen Anderson const TargetInstrInfo *TII = MF.getTarget().getInstrInfo(); 196b3e0a6d75c60f01df4fcee4b4309f06ce92a96c9Evan Cheng if (isSourceDefinedByImplicitDef(MPhi, MRI)) 1979f1c8317a4676945b4961ddb9827ef2412551620Evan Cheng // If all sources of a PHI node are implicit_def, just emit an 1989f1c8317a4676945b4961ddb9827ef2412551620Evan Cheng // implicit_def instead of a copy. 199d62e06c53b8b7e555617dc9b24b98c007d63de5dBill Wendling BuildMI(MBB, AfterPHIsIt, MPhi->getDebugLoc(), 200518bb53485df640d7b7e3f6b0544099020c42aa7Chris Lattner TII->get(TargetOpcode::IMPLICIT_DEF), DestReg); 2019f1c8317a4676945b4961ddb9827ef2412551620Evan Cheng else { 20274215fc29fa748e006c0309671555d5873bac56aJakob Stoklund Olesen // Can we reuse an earlier PHI node? This only happens for critical edges, 20374215fc29fa748e006c0309671555d5873bac56aJakob Stoklund Olesen // typically those created by tail duplication. 20474215fc29fa748e006c0309671555d5873bac56aJakob Stoklund Olesen unsigned &entry = LoweredPHIs[MPhi]; 20574215fc29fa748e006c0309671555d5873bac56aJakob Stoklund Olesen if (entry) { 20674215fc29fa748e006c0309671555d5873bac56aJakob Stoklund Olesen // An identical PHI node was already lowered. Reuse the incoming register. 20774215fc29fa748e006c0309671555d5873bac56aJakob Stoklund Olesen IncomingReg = entry; 20874215fc29fa748e006c0309671555d5873bac56aJakob Stoklund Olesen reusedIncoming = true; 20974215fc29fa748e006c0309671555d5873bac56aJakob Stoklund Olesen ++NumReused; 210f78829794284afc7c243d9ad0591ae3a87172340David Greene DEBUG(dbgs() << "Reusing %reg" << IncomingReg << " for " << *MPhi); 21174215fc29fa748e006c0309671555d5873bac56aJakob Stoklund Olesen } else { 21274215fc29fa748e006c0309671555d5873bac56aJakob Stoklund Olesen entry = IncomingReg = MF.getRegInfo().createVirtualRegister(RC); 21374215fc29fa748e006c0309671555d5873bac56aJakob Stoklund Olesen } 214f870fbc554ac862ad6d45cf97148739802a3ed12Evan Cheng TII->copyRegToReg(MBB, AfterPHIsIt, DestReg, IncomingReg, RC, RC); 2159f1c8317a4676945b4961ddb9827ef2412551620Evan Cheng } 216bc40e898e153c9b81f246a7971eaac7b14446c49Chris Lattner 217ae94dda61a045cb77681940ecc25aba0d2763f74Bill Wendling // Update live variable information if there is any. 2181465d61bdd36cfd6021036a527895f0dd358e97dDuncan Sands LiveVariables *LV = getAnalysisIfAvailable<LiveVariables>(); 21953a79aaae988d9dc9d12af8970f8b8fe58cc478dChris Lattner if (LV) { 22053a79aaae988d9dc9d12af8970f8b8fe58cc478dChris Lattner MachineInstr *PHICopy = prior(AfterPHIsIt); 221edf128a7fa90f2b0b7ee24741a04a7ae1ecd6f7eMisha Brukman 2229f1c8317a4676945b4961ddb9827ef2412551620Evan Cheng if (IncomingReg) { 22374215fc29fa748e006c0309671555d5873bac56aJakob Stoklund Olesen LiveVariables::VarInfo &VI = LV->getVarInfo(IncomingReg); 22474215fc29fa748e006c0309671555d5873bac56aJakob Stoklund Olesen 2259f1c8317a4676945b4961ddb9827ef2412551620Evan Cheng // Increment use count of the newly created virtual register. 22674215fc29fa748e006c0309671555d5873bac56aJakob Stoklund Olesen VI.NumUses++; 227dcfe5f30b5e262971f601a65bebcc0367fef56c5Jakob Stoklund Olesen LV->setPHIJoin(IncomingReg); 22874215fc29fa748e006c0309671555d5873bac56aJakob Stoklund Olesen 22974215fc29fa748e006c0309671555d5873bac56aJakob Stoklund Olesen // When we are reusing the incoming register, it may already have been 23074215fc29fa748e006c0309671555d5873bac56aJakob Stoklund Olesen // killed in this block. The old kill will also have been inserted at 23174215fc29fa748e006c0309671555d5873bac56aJakob Stoklund Olesen // AfterPHIsIt, so it appears before the current PHICopy. 23274215fc29fa748e006c0309671555d5873bac56aJakob Stoklund Olesen if (reusedIncoming) 23374215fc29fa748e006c0309671555d5873bac56aJakob Stoklund Olesen if (MachineInstr *OldKill = VI.findKill(&MBB)) { 234f78829794284afc7c243d9ad0591ae3a87172340David Greene DEBUG(dbgs() << "Remove old kill from " << *OldKill); 23574215fc29fa748e006c0309671555d5873bac56aJakob Stoklund Olesen LV->removeVirtualRegisterKilled(IncomingReg, OldKill); 23674215fc29fa748e006c0309671555d5873bac56aJakob Stoklund Olesen DEBUG(MBB.dump()); 23774215fc29fa748e006c0309671555d5873bac56aJakob Stoklund Olesen } 2389f1c8317a4676945b4961ddb9827ef2412551620Evan Cheng 2399f1c8317a4676945b4961ddb9827ef2412551620Evan Cheng // Add information to LiveVariables to know that the incoming value is 2409f1c8317a4676945b4961ddb9827ef2412551620Evan Cheng // killed. Note that because the value is defined in several places (once 2419f1c8317a4676945b4961ddb9827ef2412551620Evan Cheng // each for each incoming block), the "def" block and instruction fields 2429f1c8317a4676945b4961ddb9827ef2412551620Evan Cheng // for the VarInfo is not filled in. 2439f1c8317a4676945b4961ddb9827ef2412551620Evan Cheng LV->addVirtualRegisterKilled(IncomingReg, PHICopy); 2449f1c8317a4676945b4961ddb9827ef2412551620Evan Cheng } 245bc40e898e153c9b81f246a7971eaac7b14446c49Chris Lattner 246ae94dda61a045cb77681940ecc25aba0d2763f74Bill Wendling // Since we are going to be deleting the PHI node, if it is the last use of 247ae94dda61a045cb77681940ecc25aba0d2763f74Bill Wendling // any registers, or if the value itself is dead, we need to move this 24853a79aaae988d9dc9d12af8970f8b8fe58cc478dChris Lattner // information over to the new copy we just inserted. 24953a79aaae988d9dc9d12af8970f8b8fe58cc478dChris Lattner LV->removeVirtualRegistersKilled(MPhi); 25053a79aaae988d9dc9d12af8970f8b8fe58cc478dChris Lattner 2516db0756f021a7b9c84d3bb7ae50498feb080a013Chris Lattner // If the result is dead, update LV. 2529f1c8317a4676945b4961ddb9827ef2412551620Evan Cheng if (isDead) { 2536db0756f021a7b9c84d3bb7ae50498feb080a013Chris Lattner LV->addVirtualRegisterDead(DestReg, PHICopy); 2549f1c8317a4676945b4961ddb9827ef2412551620Evan Cheng LV->removeVirtualRegisterDead(DestReg, MPhi); 255927ce5dfaea00453889080cd1c6daf3eb197ad74Chris Lattner } 25653a79aaae988d9dc9d12af8970f8b8fe58cc478dChris Lattner } 25753a79aaae988d9dc9d12af8970f8b8fe58cc478dChris Lattner 258ae94dda61a045cb77681940ecc25aba0d2763f74Bill Wendling // Adjust the VRegPHIUseCount map to account for the removal of this PHI node. 25953a79aaae988d9dc9d12af8970f8b8fe58cc478dChris Lattner for (unsigned i = 1; i != MPhi->getNumOperands(); i += 2) 26074215fc29fa748e006c0309671555d5873bac56aJakob Stoklund Olesen --VRegPHIUseCount[BBVRegPair(MPhi->getOperand(i+1).getMBB()->getNumber(), 2618aa797aa51cd4ea1ec6f46f4891a6897944b75b2Chris Lattner MPhi->getOperand(i).getReg())]; 26253a79aaae988d9dc9d12af8970f8b8fe58cc478dChris Lattner 263ae94dda61a045cb77681940ecc25aba0d2763f74Bill Wendling // Now loop over all of the incoming arguments, changing them to copy into the 264ae94dda61a045cb77681940ecc25aba0d2763f74Bill Wendling // IncomingReg register in the corresponding predecessor basic block. 265576a27043d95d0b9b8a010bccfd38ed9c0afa739Evan Cheng SmallPtrSet<MachineBasicBlock*, 8> MBBsInsertedInto; 266f870fbc554ac862ad6d45cf97148739802a3ed12Evan Cheng for (int i = NumSrcs - 1; i >= 0; --i) { 267f870fbc554ac862ad6d45cf97148739802a3ed12Evan Cheng unsigned SrcReg = MPhi->getOperand(i*2+1).getReg(); 2686f0d024a534af18d9e60b3ea757376cd8a3a980eDan Gohman assert(TargetRegisterInfo::isVirtualRegister(SrcReg) && 2696db0756f021a7b9c84d3bb7ae50498feb080a013Chris Lattner "Machine PHI Operands must all be virtual registers!"); 27053a79aaae988d9dc9d12af8970f8b8fe58cc478dChris Lattner 271287b8b0301bc6ec7eb70d23d242326a8766bb8ebLang Hames // Get the MachineBasicBlock equivalent of the BasicBlock that is the source 272287b8b0301bc6ec7eb70d23d242326a8766bb8ebLang Hames // path the PHI. 273287b8b0301bc6ec7eb70d23d242326a8766bb8ebLang Hames MachineBasicBlock &opBlock = *MPhi->getOperand(i*2+2).getMBB(); 274287b8b0301bc6ec7eb70d23d242326a8766bb8ebLang Hames 275ae94dda61a045cb77681940ecc25aba0d2763f74Bill Wendling // If source is defined by an implicit def, there is no need to insert a 2769f1c8317a4676945b4961ddb9827ef2412551620Evan Cheng // copy. 277576a27043d95d0b9b8a010bccfd38ed9c0afa739Evan Cheng MachineInstr *DefMI = MRI->getVRegDef(SrcReg); 278518bb53485df640d7b7e3f6b0544099020c42aa7Chris Lattner if (DefMI->isImplicitDef()) { 279576a27043d95d0b9b8a010bccfd38ed9c0afa739Evan Cheng ImpDefs.insert(DefMI); 280576a27043d95d0b9b8a010bccfd38ed9c0afa739Evan Cheng continue; 281576a27043d95d0b9b8a010bccfd38ed9c0afa739Evan Cheng } 282576a27043d95d0b9b8a010bccfd38ed9c0afa739Evan Cheng 28353a79aaae988d9dc9d12af8970f8b8fe58cc478dChris Lattner // Check to make sure we haven't already emitted the copy for this block. 284ae94dda61a045cb77681940ecc25aba0d2763f74Bill Wendling // This can happen because PHI nodes may have multiple entries for the same 285ae94dda61a045cb77681940ecc25aba0d2763f74Bill Wendling // basic block. 286576a27043d95d0b9b8a010bccfd38ed9c0afa739Evan Cheng if (!MBBsInsertedInto.insert(&opBlock)) 2876db0756f021a7b9c84d3bb7ae50498feb080a013Chris Lattner continue; // If the copy has already been emitted, we're done. 288e35e3c33dc5533dd1e8ab7d9f4039cc1429d56aaJakob Stoklund Olesen 289ae94dda61a045cb77681940ecc25aba0d2763f74Bill Wendling // Find a safe location to insert the copy, this may be the first terminator 290ae94dda61a045cb77681940ecc25aba0d2763f74Bill Wendling // in the block (or end()). 2911222287543a5b5917f8c31aa8c88d740f70222d9Jakob Stoklund Olesen MachineBasicBlock::iterator InsertPos = 2921222287543a5b5917f8c31aa8c88d740f70222d9Jakob Stoklund Olesen FindCopyInsertPoint(opBlock, MBB, SrcReg); 293fc0b80d9746e5fd4b45057ab814c67371fb0f9eaEvan Cheng 2946db0756f021a7b9c84d3bb7ae50498feb080a013Chris Lattner // Insert the copy. 29574215fc29fa748e006c0309671555d5873bac56aJakob Stoklund Olesen if (!reusedIncoming && IncomingReg) 29674215fc29fa748e006c0309671555d5873bac56aJakob Stoklund Olesen TII->copyRegToReg(opBlock, InsertPos, IncomingReg, SrcReg, RC, RC); 2976db0756f021a7b9c84d3bb7ae50498feb080a013Chris Lattner 2986db0756f021a7b9c84d3bb7ae50498feb080a013Chris Lattner // Now update live variable information if we have it. Otherwise we're done 2996db0756f021a7b9c84d3bb7ae50498feb080a013Chris Lattner if (!LV) continue; 300e35e3c33dc5533dd1e8ab7d9f4039cc1429d56aaJakob Stoklund Olesen 301ae94dda61a045cb77681940ecc25aba0d2763f74Bill Wendling // We want to be able to insert a kill of the register if this PHI (aka, the 302ae94dda61a045cb77681940ecc25aba0d2763f74Bill Wendling // copy we just inserted) is the last use of the source value. Live 303ae94dda61a045cb77681940ecc25aba0d2763f74Bill Wendling // variable analysis conservatively handles this by saying that the value is 304ae94dda61a045cb77681940ecc25aba0d2763f74Bill Wendling // live until the end of the block the PHI entry lives in. If the value 305ae94dda61a045cb77681940ecc25aba0d2763f74Bill Wendling // really is dead at the PHI copy, there will be no successor blocks which 306ae94dda61a045cb77681940ecc25aba0d2763f74Bill Wendling // have the value live-in. 307e35e3c33dc5533dd1e8ab7d9f4039cc1429d56aaJakob Stoklund Olesen 308ae94dda61a045cb77681940ecc25aba0d2763f74Bill Wendling // Also check to see if this register is in use by another PHI node which 309ae94dda61a045cb77681940ecc25aba0d2763f74Bill Wendling // has not yet been eliminated. If so, it will be killed at an appropriate 310ae94dda61a045cb77681940ecc25aba0d2763f74Bill Wendling // point later. 3116db0756f021a7b9c84d3bb7ae50498feb080a013Chris Lattner 3126db0756f021a7b9c84d3bb7ae50498feb080a013Chris Lattner // Is it used by any PHI instructions in this block? 31374215fc29fa748e006c0309671555d5873bac56aJakob Stoklund Olesen bool ValueIsUsed = VRegPHIUseCount[BBVRegPair(opBlock.getNumber(), SrcReg)]; 3146db0756f021a7b9c84d3bb7ae50498feb080a013Chris Lattner 315ae94dda61a045cb77681940ecc25aba0d2763f74Bill Wendling // Okay, if we now know that the value is not live out of the block, we can 316ae94dda61a045cb77681940ecc25aba0d2763f74Bill Wendling // add a kill marker in this block saying that it kills the incoming value! 3178f72235a77e7ac262471936ea0ad2a3467d18871Jakob Stoklund Olesen if (!ValueIsUsed && !LV->isLiveOut(SrcReg, opBlock)) { 3182adfa7e9320e79859beb556367ea607a329866b3Chris Lattner // In our final twist, we have to decide which instruction kills the 319ae94dda61a045cb77681940ecc25aba0d2763f74Bill Wendling // register. In most cases this is the copy, however, the first 3202adfa7e9320e79859beb556367ea607a329866b3Chris Lattner // terminator instruction at the end of the block may also use the value. 3212adfa7e9320e79859beb556367ea607a329866b3Chris Lattner // In this case, we should mark *it* as being the killing block, not the 3222adfa7e9320e79859beb556367ea607a329866b3Chris Lattner // copy. 32374215fc29fa748e006c0309671555d5873bac56aJakob Stoklund Olesen MachineBasicBlock::iterator KillInst; 324576a27043d95d0b9b8a010bccfd38ed9c0afa739Evan Cheng MachineBasicBlock::iterator Term = opBlock.getFirstTerminator(); 32574215fc29fa748e006c0309671555d5873bac56aJakob Stoklund Olesen if (Term != opBlock.end() && Term->readsRegister(SrcReg)) { 32674215fc29fa748e006c0309671555d5873bac56aJakob Stoklund Olesen KillInst = Term; 327e35e3c33dc5533dd1e8ab7d9f4039cc1429d56aaJakob Stoklund Olesen 3282adfa7e9320e79859beb556367ea607a329866b3Chris Lattner // Check that no other terminators use values. 3292adfa7e9320e79859beb556367ea607a329866b3Chris Lattner#ifndef NDEBUG 3307896c9f436a4eda5ec15e882a7505ba482a2fcd0Chris Lattner for (MachineBasicBlock::iterator TI = llvm::next(Term); 3317896c9f436a4eda5ec15e882a7505ba482a2fcd0Chris Lattner TI != opBlock.end(); ++TI) { 332576a27043d95d0b9b8a010bccfd38ed9c0afa739Evan Cheng assert(!TI->readsRegister(SrcReg) && 3332adfa7e9320e79859beb556367ea607a329866b3Chris Lattner "Terminator instructions cannot use virtual registers unless" 3342adfa7e9320e79859beb556367ea607a329866b3Chris Lattner "they are the first terminator in a block!"); 3352adfa7e9320e79859beb556367ea607a329866b3Chris Lattner } 3362adfa7e9320e79859beb556367ea607a329866b3Chris Lattner#endif 33774215fc29fa748e006c0309671555d5873bac56aJakob Stoklund Olesen } else if (reusedIncoming || !IncomingReg) { 33874215fc29fa748e006c0309671555d5873bac56aJakob Stoklund Olesen // We may have to rewind a bit if we didn't insert a copy this time. 33974215fc29fa748e006c0309671555d5873bac56aJakob Stoklund Olesen KillInst = Term; 34074215fc29fa748e006c0309671555d5873bac56aJakob Stoklund Olesen while (KillInst != opBlock.begin()) 34174215fc29fa748e006c0309671555d5873bac56aJakob Stoklund Olesen if ((--KillInst)->readsRegister(SrcReg)) 34274215fc29fa748e006c0309671555d5873bac56aJakob Stoklund Olesen break; 34374215fc29fa748e006c0309671555d5873bac56aJakob Stoklund Olesen } else { 34474215fc29fa748e006c0309671555d5873bac56aJakob Stoklund Olesen // We just inserted this copy. 34574215fc29fa748e006c0309671555d5873bac56aJakob Stoklund Olesen KillInst = prior(InsertPos); 3462adfa7e9320e79859beb556367ea607a329866b3Chris Lattner } 34774215fc29fa748e006c0309671555d5873bac56aJakob Stoklund Olesen assert(KillInst->readsRegister(SrcReg) && "Cannot find kill instruction"); 348e35e3c33dc5533dd1e8ab7d9f4039cc1429d56aaJakob Stoklund Olesen 3492adfa7e9320e79859beb556367ea607a329866b3Chris Lattner // Finally, mark it killed. 3502adfa7e9320e79859beb556367ea607a329866b3Chris Lattner LV->addVirtualRegisterKilled(SrcReg, KillInst); 3516db0756f021a7b9c84d3bb7ae50498feb080a013Chris Lattner 3526db0756f021a7b9c84d3bb7ae50498feb080a013Chris Lattner // This vreg no longer lives all of the way through opBlock. 3536db0756f021a7b9c84d3bb7ae50498feb080a013Chris Lattner unsigned opBlockNum = opBlock.getNumber(); 354e35e3c33dc5533dd1e8ab7d9f4039cc1429d56aaJakob Stoklund Olesen LV->getVarInfo(SrcReg).AliveBlocks.reset(opBlockNum); 355bc40e898e153c9b81f246a7971eaac7b14446c49Chris Lattner } 356bc40e898e153c9b81f246a7971eaac7b14446c49Chris Lattner } 357e35e3c33dc5533dd1e8ab7d9f4039cc1429d56aaJakob Stoklund Olesen 35874215fc29fa748e006c0309671555d5873bac56aJakob Stoklund Olesen // Really delete the PHI instruction now, if it is not in the LoweredPHIs map. 35974215fc29fa748e006c0309671555d5873bac56aJakob Stoklund Olesen if (reusedIncoming || !IncomingReg) 36074215fc29fa748e006c0309671555d5873bac56aJakob Stoklund Olesen MF.DeleteMachineInstr(MPhi); 361bc40e898e153c9b81f246a7971eaac7b14446c49Chris Lattner} 362ca756d2cf9bd88f210d61dd5f9776920a6178441Bill Wendling 363ca756d2cf9bd88f210d61dd5f9776920a6178441Bill Wendling/// analyzePHINodes - Gather information about the PHI nodes in here. In 364ca756d2cf9bd88f210d61dd5f9776920a6178441Bill Wendling/// particular, we want to map the number of uses of a virtual register which is 365ca756d2cf9bd88f210d61dd5f9776920a6178441Bill Wendling/// used in a PHI node. We map that to the BB the vreg is coming from. This is 366ca756d2cf9bd88f210d61dd5f9776920a6178441Bill Wendling/// used later to determine when the vreg is killed in the BB. 367ca756d2cf9bd88f210d61dd5f9776920a6178441Bill Wendling/// 36828428cd6f31c1ea3cf4cea03e64189a4c32b84a3Evan Chengvoid llvm::PHIElimination::analyzePHINodes(const MachineFunction& MF) { 36928428cd6f31c1ea3cf4cea03e64189a4c32b84a3Evan Cheng for (MachineFunction::const_iterator I = MF.begin(), E = MF.end(); 370ca756d2cf9bd88f210d61dd5f9776920a6178441Bill Wendling I != E; ++I) 371ca756d2cf9bd88f210d61dd5f9776920a6178441Bill Wendling for (MachineBasicBlock::const_iterator BBI = I->begin(), BBE = I->end(); 372518bb53485df640d7b7e3f6b0544099020c42aa7Chris Lattner BBI != BBE && BBI->isPHI(); ++BBI) 373ca756d2cf9bd88f210d61dd5f9776920a6178441Bill Wendling for (unsigned i = 1, e = BBI->getNumOperands(); i != e; i += 2) 37474215fc29fa748e006c0309671555d5873bac56aJakob Stoklund Olesen ++VRegPHIUseCount[BBVRegPair(BBI->getOperand(i+1).getMBB()->getNumber(), 3758aa797aa51cd4ea1ec6f46f4891a6897944b75b2Chris Lattner BBI->getOperand(i).getReg())]; 376ca756d2cf9bd88f210d61dd5f9776920a6178441Bill Wendling} 377e35e3c33dc5533dd1e8ab7d9f4039cc1429d56aaJakob Stoklund Olesen 3783e20475feebca3bfb29375ac7f3e5acbeb2a95c8Jakob Stoklund Olesenbool llvm::PHIElimination::SplitPHIEdges(MachineFunction &MF, 3790257dd375d64da978887d0c1e97ab3560d7597ceJakob Stoklund Olesen MachineBasicBlock &MBB, 3800257dd375d64da978887d0c1e97ab3560d7597ceJakob Stoklund Olesen LiveVariables &LV) { 381518bb53485df640d7b7e3f6b0544099020c42aa7Chris Lattner if (MBB.empty() || !MBB.front().isPHI() || MBB.isLandingPad()) 3823e20475feebca3bfb29375ac7f3e5acbeb2a95c8Jakob Stoklund Olesen return false; // Quick exit for basic blocks without PHIs. 3830257dd375d64da978887d0c1e97ab3560d7597ceJakob Stoklund Olesen 384f235f13931835b3335f3f2ff2d3060381b93626cJakob Stoklund Olesen for (MachineBasicBlock::const_iterator BBI = MBB.begin(), BBE = MBB.end(); 385518bb53485df640d7b7e3f6b0544099020c42aa7Chris Lattner BBI != BBE && BBI->isPHI(); ++BBI) { 386f235f13931835b3335f3f2ff2d3060381b93626cJakob Stoklund Olesen for (unsigned i = 1, e = BBI->getNumOperands(); i != e; i += 2) { 387f235f13931835b3335f3f2ff2d3060381b93626cJakob Stoklund Olesen unsigned Reg = BBI->getOperand(i).getReg(); 388f235f13931835b3335f3f2ff2d3060381b93626cJakob Stoklund Olesen MachineBasicBlock *PreMBB = BBI->getOperand(i+1).getMBB(); 389f235f13931835b3335f3f2ff2d3060381b93626cJakob Stoklund Olesen // We break edges when registers are live out from the predecessor block 3903e20475feebca3bfb29375ac7f3e5acbeb2a95c8Jakob Stoklund Olesen // (not considering PHI nodes). If the register is live in to this block 3913e20475feebca3bfb29375ac7f3e5acbeb2a95c8Jakob Stoklund Olesen // anyway, we would gain nothing from splitting. 3928f72235a77e7ac262471936ea0ad2a3467d18871Jakob Stoklund Olesen if (!LV.isLiveIn(Reg, MBB) && LV.isLiveOut(Reg, *PreMBB)) 393f235f13931835b3335f3f2ff2d3060381b93626cJakob Stoklund Olesen SplitCriticalEdge(PreMBB, &MBB); 394f235f13931835b3335f3f2ff2d3060381b93626cJakob Stoklund Olesen } 395f235f13931835b3335f3f2ff2d3060381b93626cJakob Stoklund Olesen } 3963e20475feebca3bfb29375ac7f3e5acbeb2a95c8Jakob Stoklund Olesen return true; 397f235f13931835b3335f3f2ff2d3060381b93626cJakob Stoklund Olesen} 398f235f13931835b3335f3f2ff2d3060381b93626cJakob Stoklund Olesen 399f235f13931835b3335f3f2ff2d3060381b93626cJakob Stoklund OlesenMachineBasicBlock *PHIElimination::SplitCriticalEdge(MachineBasicBlock *A, 400f235f13931835b3335f3f2ff2d3060381b93626cJakob Stoklund Olesen MachineBasicBlock *B) { 401f235f13931835b3335f3f2ff2d3060381b93626cJakob Stoklund Olesen assert(A && B && "Missing MBB end point"); 402f235f13931835b3335f3f2ff2d3060381b93626cJakob Stoklund Olesen 403f235f13931835b3335f3f2ff2d3060381b93626cJakob Stoklund Olesen MachineFunction *MF = A->getParent(); 4045493acac6fcc06ef6fa8577bf9f720762d78e870Jakob Stoklund Olesen 4055493acac6fcc06ef6fa8577bf9f720762d78e870Jakob Stoklund Olesen // We may need to update A's terminator, but we can't do that if AnalyzeBranch 4065052c1547ef75f401fd397084831e0bb15311b09Jakob Stoklund Olesen // fails. If A uses a jump table, we won't touch it. 4075052c1547ef75f401fd397084831e0bb15311b09Jakob Stoklund Olesen const TargetInstrInfo *TII = MF->getTarget().getInstrInfo(); 4085052c1547ef75f401fd397084831e0bb15311b09Jakob Stoklund Olesen MachineBasicBlock *TBB = 0, *FBB = 0; 4095052c1547ef75f401fd397084831e0bb15311b09Jakob Stoklund Olesen SmallVector<MachineOperand, 4> Cond; 4105052c1547ef75f401fd397084831e0bb15311b09Jakob Stoklund Olesen if (TII->AnalyzeBranch(*A, TBB, FBB, Cond)) 4115052c1547ef75f401fd397084831e0bb15311b09Jakob Stoklund Olesen return NULL; 4125493acac6fcc06ef6fa8577bf9f720762d78e870Jakob Stoklund Olesen 4135493acac6fcc06ef6fa8577bf9f720762d78e870Jakob Stoklund Olesen ++NumSplits; 4145493acac6fcc06ef6fa8577bf9f720762d78e870Jakob Stoklund Olesen 4151222287543a5b5917f8c31aa8c88d740f70222d9Jakob Stoklund Olesen MachineBasicBlock *NMBB = MF->CreateMachineBasicBlock(); 4167896c9f436a4eda5ec15e882a7505ba482a2fcd0Chris Lattner MF->insert(llvm::next(MachineFunction::iterator(A)), NMBB); 417f78829794284afc7c243d9ad0591ae3a87172340David Greene DEBUG(dbgs() << "PHIElimination splitting critical edge:" 418f235f13931835b3335f3f2ff2d3060381b93626cJakob Stoklund Olesen " BB#" << A->getNumber() 419bf4af353edd2da1d7f2ed0b22238a8d2c038f5cfDaniel Dunbar << " -- BB#" << NMBB->getNumber() 420f235f13931835b3335f3f2ff2d3060381b93626cJakob Stoklund Olesen << " -- BB#" << B->getNumber() << '\n'); 421f235f13931835b3335f3f2ff2d3060381b93626cJakob Stoklund Olesen 422f235f13931835b3335f3f2ff2d3060381b93626cJakob Stoklund Olesen A->ReplaceUsesOfBlockWith(B, NMBB); 423160069d15aef1cd756bae112da9149c98308da68Jakob Stoklund Olesen A->updateTerminator(); 424f235f13931835b3335f3f2ff2d3060381b93626cJakob Stoklund Olesen 425160069d15aef1cd756bae112da9149c98308da68Jakob Stoklund Olesen // Insert unconditional "jump B" instruction in NMBB if necessary. 4263b6ced15108909de2fab0766fc693fe66c48ab68Jakob Stoklund Olesen NMBB->addSuccessor(B); 427160069d15aef1cd756bae112da9149c98308da68Jakob Stoklund Olesen if (!NMBB->isLayoutSuccessor(B)) { 428160069d15aef1cd756bae112da9149c98308da68Jakob Stoklund Olesen Cond.clear(); 429160069d15aef1cd756bae112da9149c98308da68Jakob Stoklund Olesen MF->getTarget().getInstrInfo()->InsertBranch(*NMBB, B, NULL, Cond); 430160069d15aef1cd756bae112da9149c98308da68Jakob Stoklund Olesen } 431f235f13931835b3335f3f2ff2d3060381b93626cJakob Stoklund Olesen 432f235f13931835b3335f3f2ff2d3060381b93626cJakob Stoklund Olesen // Fix PHI nodes in B so they refer to NMBB instead of A 433f235f13931835b3335f3f2ff2d3060381b93626cJakob Stoklund Olesen for (MachineBasicBlock::iterator i = B->begin(), e = B->end(); 434518bb53485df640d7b7e3f6b0544099020c42aa7Chris Lattner i != e && i->isPHI(); ++i) 435f235f13931835b3335f3f2ff2d3060381b93626cJakob Stoklund Olesen for (unsigned ni = 1, ne = i->getNumOperands(); ni != ne; ni += 2) 4363e20475feebca3bfb29375ac7f3e5acbeb2a95c8Jakob Stoklund Olesen if (i->getOperand(ni+1).getMBB() == A) 437f235f13931835b3335f3f2ff2d3060381b93626cJakob Stoklund Olesen i->getOperand(ni+1).setMBB(NMBB); 4389aebb61daf4d787aa7dcff9e3caa89bac88e11d1Jakob Stoklund Olesen 4399aebb61daf4d787aa7dcff9e3caa89bac88e11d1Jakob Stoklund Olesen if (LiveVariables *LV=getAnalysisIfAvailable<LiveVariables>()) 440323d8c3ed72c9e440c2079e8c1954af69357c7cfJakob Stoklund Olesen LV->addNewBlock(NMBB, A, B); 4419aebb61daf4d787aa7dcff9e3caa89bac88e11d1Jakob Stoklund Olesen 4429aebb61daf4d787aa7dcff9e3caa89bac88e11d1Jakob Stoklund Olesen if (MachineDominatorTree *MDT=getAnalysisIfAvailable<MachineDominatorTree>()) 4439aebb61daf4d787aa7dcff9e3caa89bac88e11d1Jakob Stoklund Olesen MDT->addNewBlock(NMBB, A); 4449aebb61daf4d787aa7dcff9e3caa89bac88e11d1Jakob Stoklund Olesen 445f235f13931835b3335f3f2ff2d3060381b93626cJakob Stoklund Olesen return NMBB; 446f235f13931835b3335f3f2ff2d3060381b93626cJakob Stoklund Olesen} 447