PHIElimination.cpp revision b126d0530d48890e1689975483b9f923a0fca1da
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" 243e20475feebca3bfb29375ac7f3e5acbeb2a95c8Jakob Stoklund Olesen#include "llvm/Function.h" 25bc40e898e153c9b81f246a7971eaac7b14446c49Chris Lattner#include "llvm/Target/TargetMachine.h" 26576a27043d95d0b9b8a010bccfd38ed9c0afa739Evan Cheng#include "llvm/ADT/SmallPtrSet.h" 27551ccae044b0ff658fe629dd67edd5ffe75d10e8Reid Spencer#include "llvm/ADT/STLExtras.h" 286db0756f021a7b9c84d3bb7ae50498feb080a013Chris Lattner#include "llvm/ADT/Statistic.h" 29f235f13931835b3335f3f2ff2d3060381b93626cJakob Stoklund Olesen#include "llvm/Support/CommandLine.h" 30a4f0b3a084d120cfc5b5bb06f64b222f5cb72740Chris Lattner#include "llvm/Support/Compiler.h" 31f235f13931835b3335f3f2ff2d3060381b93626cJakob Stoklund Olesen#include "llvm/Support/Debug.h" 326db0756f021a7b9c84d3bb7ae50498feb080a013Chris Lattner#include <algorithm> 331088317675dd34a1823f427e472fb9e43c616cb1Evan Cheng#include <map> 340742b59913a7760eb26f08121cd244a37e83e3b3Chris Lattnerusing namespace llvm; 35d0fde30ce850b78371fd1386338350591f9ff494Brian Gaeke 36cd3245ac45c595da96bb768a55cddc356dff55feChris LattnerSTATISTIC(NumAtomic, "Number of atomic phis lowered"); 37f235f13931835b3335f3f2ff2d3060381b93626cJakob Stoklund OlesenSTATISTIC(NumSplits, "Number of critical edges split on demand"); 38f235f13931835b3335f3f2ff2d3060381b93626cJakob Stoklund Olesen 39f235f13931835b3335f3f2ff2d3060381b93626cJakob Stoklund Olesenstatic cl::opt<bool> 40f235f13931835b3335f3f2ff2d3060381b93626cJakob Stoklund OlesenSplitEdges("split-phi-edges", 41f235f13931835b3335f3f2ff2d3060381b93626cJakob Stoklund Olesen cl::desc("Split critical edges during phi elimination"), 42f235f13931835b3335f3f2ff2d3060381b93626cJakob Stoklund Olesen cl::init(false), cl::Hidden); 43cd3245ac45c595da96bb768a55cddc356dff55feChris Lattner 44fae02a2ab19abdf12854356e19aeb1da62a0b8eaLang Hameschar PHIElimination::ID = 0; 45fae02a2ab19abdf12854356e19aeb1da62a0b8eaLang Hamesstatic RegisterPass<PHIElimination> 46844731a7f1909f55935e3514c9e713a62d67662eDan GohmanX("phi-node-elimination", "Eliminate PHI nodes for register allocation"); 47844731a7f1909f55935e3514c9e713a62d67662eDan Gohman 486ddba2b933645d308428201e942abe1274fa5085Dan Gohmanconst PassInfo *const llvm::PHIEliminationID = &X; 49bc40e898e153c9b81f246a7971eaac7b14446c49Chris Lattner 50fae02a2ab19abdf12854356e19aeb1da62a0b8eaLang Hamesvoid llvm::PHIElimination::getAnalysisUsage(AnalysisUsage &AU) const { 51845012e6d31799c7fbd1193fa1af8ee2d12e9231Dan Gohman AU.addPreserved<LiveVariables>(); 529aebb61daf4d787aa7dcff9e3caa89bac88e11d1Jakob Stoklund Olesen AU.addPreserved<MachineDominatorTree>(); 53f235f13931835b3335f3f2ff2d3060381b93626cJakob Stoklund Olesen if (SplitEdges) { 54f235f13931835b3335f3f2ff2d3060381b93626cJakob Stoklund Olesen AU.addRequired<LiveVariables>(); 55f235f13931835b3335f3f2ff2d3060381b93626cJakob Stoklund Olesen } else { 56f235f13931835b3335f3f2ff2d3060381b93626cJakob Stoklund Olesen AU.setPreservesCFG(); 57f235f13931835b3335f3f2ff2d3060381b93626cJakob Stoklund Olesen AU.addPreservedID(MachineLoopInfoID); 58f235f13931835b3335f3f2ff2d3060381b93626cJakob Stoklund Olesen } 59845012e6d31799c7fbd1193fa1af8ee2d12e9231Dan Gohman MachineFunctionPass::getAnalysisUsage(AU); 60845012e6d31799c7fbd1193fa1af8ee2d12e9231Dan Gohman} 61fae02a2ab19abdf12854356e19aeb1da62a0b8eaLang Hames 62fae02a2ab19abdf12854356e19aeb1da62a0b8eaLang Hamesbool llvm::PHIElimination::runOnMachineFunction(MachineFunction &Fn) { 63576a27043d95d0b9b8a010bccfd38ed9c0afa739Evan Cheng MRI = &Fn.getRegInfo(); 64576a27043d95d0b9b8a010bccfd38ed9c0afa739Evan Cheng 6520354634ebb64023d322919633f8bd348a63891dLang Hames PHIDefs.clear(); 6620354634ebb64023d322919633f8bd348a63891dLang Hames PHIKills.clear(); 67576a27043d95d0b9b8a010bccfd38ed9c0afa739Evan Cheng bool Changed = false; 68576a27043d95d0b9b8a010bccfd38ed9c0afa739Evan Cheng 693e20475feebca3bfb29375ac7f3e5acbeb2a95c8Jakob Stoklund Olesen // Split critical edges to help the coalescer 703e20475feebca3bfb29375ac7f3e5acbeb2a95c8Jakob Stoklund Olesen if (SplitEdges) 713e20475feebca3bfb29375ac7f3e5acbeb2a95c8Jakob Stoklund Olesen for (MachineFunction::iterator I = Fn.begin(), E = Fn.end(); I != E; ++I) 723e20475feebca3bfb29375ac7f3e5acbeb2a95c8Jakob Stoklund Olesen Changed |= SplitPHIEdges(Fn, *I); 733e20475feebca3bfb29375ac7f3e5acbeb2a95c8Jakob Stoklund Olesen 743e20475feebca3bfb29375ac7f3e5acbeb2a95c8Jakob Stoklund Olesen // Populate VRegPHIUseCount 753e20475feebca3bfb29375ac7f3e5acbeb2a95c8Jakob Stoklund Olesen analyzePHINodes(Fn); 763e20475feebca3bfb29375ac7f3e5acbeb2a95c8Jakob Stoklund Olesen 77576a27043d95d0b9b8a010bccfd38ed9c0afa739Evan Cheng // Eliminate PHI instructions by inserting copies into predecessor blocks. 78576a27043d95d0b9b8a010bccfd38ed9c0afa739Evan Cheng for (MachineFunction::iterator I = Fn.begin(), E = Fn.end(); I != E; ++I) 79576a27043d95d0b9b8a010bccfd38ed9c0afa739Evan Cheng Changed |= EliminatePHINodes(Fn, *I); 80576a27043d95d0b9b8a010bccfd38ed9c0afa739Evan Cheng 81576a27043d95d0b9b8a010bccfd38ed9c0afa739Evan Cheng // Remove dead IMPLICIT_DEF instructions. 82576a27043d95d0b9b8a010bccfd38ed9c0afa739Evan Cheng for (SmallPtrSet<MachineInstr*,4>::iterator I = ImpDefs.begin(), 83576a27043d95d0b9b8a010bccfd38ed9c0afa739Evan Cheng E = ImpDefs.end(); I != E; ++I) { 84576a27043d95d0b9b8a010bccfd38ed9c0afa739Evan Cheng MachineInstr *DefMI = *I; 85576a27043d95d0b9b8a010bccfd38ed9c0afa739Evan Cheng unsigned DefReg = DefMI->getOperand(0).getReg(); 861b38ec83f07d5801035567160008cd7cb99a5c1aEvan Cheng if (MRI->use_empty(DefReg)) 87576a27043d95d0b9b8a010bccfd38ed9c0afa739Evan Cheng DefMI->eraseFromParent(); 88576a27043d95d0b9b8a010bccfd38ed9c0afa739Evan Cheng } 89576a27043d95d0b9b8a010bccfd38ed9c0afa739Evan Cheng 90576a27043d95d0b9b8a010bccfd38ed9c0afa739Evan Cheng ImpDefs.clear(); 91576a27043d95d0b9b8a010bccfd38ed9c0afa739Evan Cheng VRegPHIUseCount.clear(); 92576a27043d95d0b9b8a010bccfd38ed9c0afa739Evan Cheng return Changed; 93576a27043d95d0b9b8a010bccfd38ed9c0afa739Evan Cheng} 94576a27043d95d0b9b8a010bccfd38ed9c0afa739Evan Cheng 95bc40e898e153c9b81f246a7971eaac7b14446c49Chris Lattner/// EliminatePHINodes - Eliminate phi nodes by inserting copy instructions in 96bc40e898e153c9b81f246a7971eaac7b14446c49Chris Lattner/// predecessor basic blocks. 97bc40e898e153c9b81f246a7971eaac7b14446c49Chris Lattner/// 98fae02a2ab19abdf12854356e19aeb1da62a0b8eaLang Hamesbool llvm::PHIElimination::EliminatePHINodes(MachineFunction &MF, 99fae02a2ab19abdf12854356e19aeb1da62a0b8eaLang Hames MachineBasicBlock &MBB) { 100c0b9dc5be79f009d260edb5cd5e1d8346587aaa2Alkis Evlogimenos if (MBB.empty() || MBB.front().getOpcode() != TargetInstrInfo::PHI) 10153a79aaae988d9dc9d12af8970f8b8fe58cc478dChris Lattner return false; // Quick exit for basic blocks without PHIs. 102bc40e898e153c9b81f246a7971eaac7b14446c49Chris Lattner 103791f896d9f8a38b3806878867d61c114069b6195Chris Lattner // Get an iterator to the first instruction after the last PHI node (this may 10453a79aaae988d9dc9d12af8970f8b8fe58cc478dChris Lattner // also be the end of the basic block). 105a5fec0dba34206274041543b5924d2565fb10f9bDuncan Sands MachineBasicBlock::iterator AfterPHIsIt = SkipPHIsAndLabels(MBB, MBB.begin()); 106791f896d9f8a38b3806878867d61c114069b6195Chris Lattner 107ca756d2cf9bd88f210d61dd5f9776920a6178441Bill Wendling while (MBB.front().getOpcode() == TargetInstrInfo::PHI) 108ca756d2cf9bd88f210d61dd5f9776920a6178441Bill Wendling LowerAtomicPHINode(MBB, AfterPHIsIt); 109ca756d2cf9bd88f210d61dd5f9776920a6178441Bill Wendling 11053a79aaae988d9dc9d12af8970f8b8fe58cc478dChris Lattner return true; 11153a79aaae988d9dc9d12af8970f8b8fe58cc478dChris Lattner} 112edf128a7fa90f2b0b7ee24741a04a7ae1ecd6f7eMisha Brukman 1131b38ec83f07d5801035567160008cd7cb99a5c1aEvan Cheng/// isSourceDefinedByImplicitDef - Return true if all sources of the phi node 1141b38ec83f07d5801035567160008cd7cb99a5c1aEvan Cheng/// are implicit_def's. 115ae94dda61a045cb77681940ecc25aba0d2763f74Bill Wendlingstatic bool isSourceDefinedByImplicitDef(const MachineInstr *MPhi, 1161b38ec83f07d5801035567160008cd7cb99a5c1aEvan Cheng const MachineRegisterInfo *MRI) { 117b3e0a6d75c60f01df4fcee4b4309f06ce92a96c9Evan Cheng for (unsigned i = 1; i != MPhi->getNumOperands(); i += 2) { 118b3e0a6d75c60f01df4fcee4b4309f06ce92a96c9Evan Cheng unsigned SrcReg = MPhi->getOperand(i).getReg(); 119ae94dda61a045cb77681940ecc25aba0d2763f74Bill Wendling const MachineInstr *DefMI = MRI->getVRegDef(SrcReg); 120b3e0a6d75c60f01df4fcee4b4309f06ce92a96c9Evan Cheng if (!DefMI || DefMI->getOpcode() != TargetInstrInfo::IMPLICIT_DEF) 121b3e0a6d75c60f01df4fcee4b4309f06ce92a96c9Evan Cheng return false; 122b3e0a6d75c60f01df4fcee4b4309f06ce92a96c9Evan Cheng } 123b3e0a6d75c60f01df4fcee4b4309f06ce92a96c9Evan Cheng return true; 124f870fbc554ac862ad6d45cf97148739802a3ed12Evan Cheng} 125f870fbc554ac862ad6d45cf97148739802a3ed12Evan Cheng 1261222287543a5b5917f8c31aa8c88d740f70222d9Jakob Stoklund Olesen// FindCopyInsertPoint - Find a safe place in MBB to insert a copy from SrcReg 1271222287543a5b5917f8c31aa8c88d740f70222d9Jakob Stoklund Olesen// when following the CFG edge to SuccMBB. This needs to be after any def of 1281222287543a5b5917f8c31aa8c88d740f70222d9Jakob Stoklund Olesen// SrcReg, but before any subsequent point where control flow might jump out of 1291222287543a5b5917f8c31aa8c88d740f70222d9Jakob Stoklund Olesen// the basic block. 130fae02a2ab19abdf12854356e19aeb1da62a0b8eaLang HamesMachineBasicBlock::iterator 131fae02a2ab19abdf12854356e19aeb1da62a0b8eaLang Hamesllvm::PHIElimination::FindCopyInsertPoint(MachineBasicBlock &MBB, 1321222287543a5b5917f8c31aa8c88d740f70222d9Jakob Stoklund Olesen MachineBasicBlock &SuccMBB, 133fae02a2ab19abdf12854356e19aeb1da62a0b8eaLang Hames unsigned SrcReg) { 134a5fec0dba34206274041543b5924d2565fb10f9bDuncan Sands // Handle the trivial case trivially. 135a5fec0dba34206274041543b5924d2565fb10f9bDuncan Sands if (MBB.empty()) 136a5fec0dba34206274041543b5924d2565fb10f9bDuncan Sands return MBB.begin(); 137a5fec0dba34206274041543b5924d2565fb10f9bDuncan Sands 1381222287543a5b5917f8c31aa8c88d740f70222d9Jakob Stoklund Olesen // Usually, we just want to insert the copy before the first terminator 1391222287543a5b5917f8c31aa8c88d740f70222d9Jakob Stoklund Olesen // instruction. However, for the edge going to a landing pad, we must insert 1401222287543a5b5917f8c31aa8c88d740f70222d9Jakob Stoklund Olesen // the copy before the call/invoke instruction. 1411222287543a5b5917f8c31aa8c88d740f70222d9Jakob Stoklund Olesen if (!SuccMBB.isLandingPad()) 142a5fec0dba34206274041543b5924d2565fb10f9bDuncan Sands return MBB.getFirstTerminator(); 143a5fec0dba34206274041543b5924d2565fb10f9bDuncan Sands 144b126d0530d48890e1689975483b9f923a0fca1daLang Hames // Discover any defs/uses in this basic block. 145a5fec0dba34206274041543b5924d2565fb10f9bDuncan Sands SmallPtrSet<MachineInstr*, 8> DefUsesInMBB; 146b126d0530d48890e1689975483b9f923a0fca1daLang Hames for (MachineRegisterInfo::reg_iterator RI = MRI->reg_begin(SrcReg), 147b126d0530d48890e1689975483b9f923a0fca1daLang Hames RE = MRI->reg_end(); RI != RE; ++RI) { 148a5fec0dba34206274041543b5924d2565fb10f9bDuncan Sands MachineInstr *DefUseMI = &*RI; 149a5fec0dba34206274041543b5924d2565fb10f9bDuncan Sands if (DefUseMI->getParent() == &MBB) 150a5fec0dba34206274041543b5924d2565fb10f9bDuncan Sands DefUsesInMBB.insert(DefUseMI); 151fc0b80d9746e5fd4b45057ab814c67371fb0f9eaEvan Cheng } 152fc0b80d9746e5fd4b45057ab814c67371fb0f9eaEvan Cheng 153a5fec0dba34206274041543b5924d2565fb10f9bDuncan Sands MachineBasicBlock::iterator InsertPoint; 154a5fec0dba34206274041543b5924d2565fb10f9bDuncan Sands if (DefUsesInMBB.empty()) { 1551222287543a5b5917f8c31aa8c88d740f70222d9Jakob Stoklund Olesen // No defs. Insert the copy at the start of the basic block. 156a5fec0dba34206274041543b5924d2565fb10f9bDuncan Sands InsertPoint = MBB.begin(); 157a5fec0dba34206274041543b5924d2565fb10f9bDuncan Sands } else if (DefUsesInMBB.size() == 1) { 158b126d0530d48890e1689975483b9f923a0fca1daLang Hames // Insert the copy immediately after the def/use. 159a5fec0dba34206274041543b5924d2565fb10f9bDuncan Sands InsertPoint = *DefUsesInMBB.begin(); 160a5fec0dba34206274041543b5924d2565fb10f9bDuncan Sands ++InsertPoint; 161a5fec0dba34206274041543b5924d2565fb10f9bDuncan Sands } else { 162b126d0530d48890e1689975483b9f923a0fca1daLang Hames // Insert the copy immediately after the last def/use. 163a5fec0dba34206274041543b5924d2565fb10f9bDuncan Sands InsertPoint = MBB.end(); 164a5fec0dba34206274041543b5924d2565fb10f9bDuncan Sands while (!DefUsesInMBB.count(&*--InsertPoint)) {} 165a5fec0dba34206274041543b5924d2565fb10f9bDuncan Sands ++InsertPoint; 166fc0b80d9746e5fd4b45057ab814c67371fb0f9eaEvan Cheng } 167a5fec0dba34206274041543b5924d2565fb10f9bDuncan Sands 168a5fec0dba34206274041543b5924d2565fb10f9bDuncan Sands // Make sure the copy goes after any phi nodes however. 169a5fec0dba34206274041543b5924d2565fb10f9bDuncan Sands return SkipPHIsAndLabels(MBB, InsertPoint); 170fc0b80d9746e5fd4b45057ab814c67371fb0f9eaEvan Cheng} 171fc0b80d9746e5fd4b45057ab814c67371fb0f9eaEvan Cheng 17253a79aaae988d9dc9d12af8970f8b8fe58cc478dChris Lattner/// LowerAtomicPHINode - Lower the PHI node at the top of the specified block, 17353a79aaae988d9dc9d12af8970f8b8fe58cc478dChris Lattner/// under the assuption that it needs to be lowered in a way that supports 17453a79aaae988d9dc9d12af8970f8b8fe58cc478dChris Lattner/// atomic execution of PHIs. This lowering method is always correct all of the 17553a79aaae988d9dc9d12af8970f8b8fe58cc478dChris Lattner/// time. 176e35e3c33dc5533dd1e8ab7d9f4039cc1429d56aaJakob Stoklund Olesen/// 177fae02a2ab19abdf12854356e19aeb1da62a0b8eaLang Hamesvoid llvm::PHIElimination::LowerAtomicPHINode( 178fae02a2ab19abdf12854356e19aeb1da62a0b8eaLang Hames MachineBasicBlock &MBB, 179fae02a2ab19abdf12854356e19aeb1da62a0b8eaLang Hames MachineBasicBlock::iterator AfterPHIsIt) { 18053a79aaae988d9dc9d12af8970f8b8fe58cc478dChris Lattner // Unlink the PHI node from the basic block, but don't delete the PHI yet. 18153a79aaae988d9dc9d12af8970f8b8fe58cc478dChris Lattner MachineInstr *MPhi = MBB.remove(MBB.begin()); 18253a79aaae988d9dc9d12af8970f8b8fe58cc478dChris Lattner 183f870fbc554ac862ad6d45cf97148739802a3ed12Evan Cheng unsigned NumSrcs = (MPhi->getNumOperands() - 1) / 2; 18453a79aaae988d9dc9d12af8970f8b8fe58cc478dChris Lattner unsigned DestReg = MPhi->getOperand(0).getReg(); 1859f1c8317a4676945b4961ddb9827ef2412551620Evan Cheng bool isDead = MPhi->getOperand(0).isDead(); 18653a79aaae988d9dc9d12af8970f8b8fe58cc478dChris Lattner 187ca756d2cf9bd88f210d61dd5f9776920a6178441Bill Wendling // Create a new register for the incoming PHI arguments. 18853a79aaae988d9dc9d12af8970f8b8fe58cc478dChris Lattner MachineFunction &MF = *MBB.getParent(); 18984bc5427d6883f73cfeae3da640acd011d35c006Chris Lattner const TargetRegisterClass *RC = MF.getRegInfo().getRegClass(DestReg); 1909f1c8317a4676945b4961ddb9827ef2412551620Evan Cheng unsigned IncomingReg = 0; 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(), 2009f1c8317a4676945b4961ddb9827ef2412551620Evan Cheng TII->get(TargetInstrInfo::IMPLICIT_DEF), DestReg); 2019f1c8317a4676945b4961ddb9827ef2412551620Evan Cheng else { 2029f1c8317a4676945b4961ddb9827ef2412551620Evan Cheng IncomingReg = MF.getRegInfo().createVirtualRegister(RC); 203f870fbc554ac862ad6d45cf97148739802a3ed12Evan Cheng TII->copyRegToReg(MBB, AfterPHIsIt, DestReg, IncomingReg, RC, RC); 2049f1c8317a4676945b4961ddb9827ef2412551620Evan Cheng } 205bc40e898e153c9b81f246a7971eaac7b14446c49Chris Lattner 206287b8b0301bc6ec7eb70d23d242326a8766bb8ebLang Hames // Record PHI def. 207e35e3c33dc5533dd1e8ab7d9f4039cc1429d56aaJakob Stoklund Olesen assert(!hasPHIDef(DestReg) && "Vreg has multiple phi-defs?"); 20820354634ebb64023d322919633f8bd348a63891dLang Hames PHIDefs[DestReg] = &MBB; 209287b8b0301bc6ec7eb70d23d242326a8766bb8ebLang Hames 210ae94dda61a045cb77681940ecc25aba0d2763f74Bill Wendling // Update live variable information if there is any. 2111465d61bdd36cfd6021036a527895f0dd358e97dDuncan Sands LiveVariables *LV = getAnalysisIfAvailable<LiveVariables>(); 21253a79aaae988d9dc9d12af8970f8b8fe58cc478dChris Lattner if (LV) { 21353a79aaae988d9dc9d12af8970f8b8fe58cc478dChris Lattner MachineInstr *PHICopy = prior(AfterPHIsIt); 214edf128a7fa90f2b0b7ee24741a04a7ae1ecd6f7eMisha Brukman 2159f1c8317a4676945b4961ddb9827ef2412551620Evan Cheng if (IncomingReg) { 2169f1c8317a4676945b4961ddb9827ef2412551620Evan Cheng // Increment use count of the newly created virtual register. 2179f1c8317a4676945b4961ddb9827ef2412551620Evan Cheng LV->getVarInfo(IncomingReg).NumUses++; 2189f1c8317a4676945b4961ddb9827ef2412551620Evan Cheng 2199f1c8317a4676945b4961ddb9827ef2412551620Evan Cheng // Add information to LiveVariables to know that the incoming value is 2209f1c8317a4676945b4961ddb9827ef2412551620Evan Cheng // killed. Note that because the value is defined in several places (once 2219f1c8317a4676945b4961ddb9827ef2412551620Evan Cheng // each for each incoming block), the "def" block and instruction fields 2229f1c8317a4676945b4961ddb9827ef2412551620Evan Cheng // for the VarInfo is not filled in. 2239f1c8317a4676945b4961ddb9827ef2412551620Evan Cheng LV->addVirtualRegisterKilled(IncomingReg, PHICopy); 2249f1c8317a4676945b4961ddb9827ef2412551620Evan Cheng } 225bc40e898e153c9b81f246a7971eaac7b14446c49Chris Lattner 226ae94dda61a045cb77681940ecc25aba0d2763f74Bill Wendling // Since we are going to be deleting the PHI node, if it is the last use of 227ae94dda61a045cb77681940ecc25aba0d2763f74Bill Wendling // any registers, or if the value itself is dead, we need to move this 22853a79aaae988d9dc9d12af8970f8b8fe58cc478dChris Lattner // information over to the new copy we just inserted. 22953a79aaae988d9dc9d12af8970f8b8fe58cc478dChris Lattner LV->removeVirtualRegistersKilled(MPhi); 23053a79aaae988d9dc9d12af8970f8b8fe58cc478dChris Lattner 2316db0756f021a7b9c84d3bb7ae50498feb080a013Chris Lattner // If the result is dead, update LV. 2329f1c8317a4676945b4961ddb9827ef2412551620Evan Cheng if (isDead) { 2336db0756f021a7b9c84d3bb7ae50498feb080a013Chris Lattner LV->addVirtualRegisterDead(DestReg, PHICopy); 2349f1c8317a4676945b4961ddb9827ef2412551620Evan Cheng LV->removeVirtualRegisterDead(DestReg, MPhi); 235927ce5dfaea00453889080cd1c6daf3eb197ad74Chris Lattner } 23653a79aaae988d9dc9d12af8970f8b8fe58cc478dChris Lattner } 23753a79aaae988d9dc9d12af8970f8b8fe58cc478dChris Lattner 238ae94dda61a045cb77681940ecc25aba0d2763f74Bill Wendling // Adjust the VRegPHIUseCount map to account for the removal of this PHI node. 23953a79aaae988d9dc9d12af8970f8b8fe58cc478dChris Lattner for (unsigned i = 1; i != MPhi->getNumOperands(); i += 2) 2408aa797aa51cd4ea1ec6f46f4891a6897944b75b2Chris Lattner --VRegPHIUseCount[BBVRegPair(MPhi->getOperand(i + 1).getMBB(), 2418aa797aa51cd4ea1ec6f46f4891a6897944b75b2Chris Lattner MPhi->getOperand(i).getReg())]; 24253a79aaae988d9dc9d12af8970f8b8fe58cc478dChris Lattner 243ae94dda61a045cb77681940ecc25aba0d2763f74Bill Wendling // Now loop over all of the incoming arguments, changing them to copy into the 244ae94dda61a045cb77681940ecc25aba0d2763f74Bill Wendling // IncomingReg register in the corresponding predecessor basic block. 245576a27043d95d0b9b8a010bccfd38ed9c0afa739Evan Cheng SmallPtrSet<MachineBasicBlock*, 8> MBBsInsertedInto; 246f870fbc554ac862ad6d45cf97148739802a3ed12Evan Cheng for (int i = NumSrcs - 1; i >= 0; --i) { 247f870fbc554ac862ad6d45cf97148739802a3ed12Evan Cheng unsigned SrcReg = MPhi->getOperand(i*2+1).getReg(); 2486f0d024a534af18d9e60b3ea757376cd8a3a980eDan Gohman assert(TargetRegisterInfo::isVirtualRegister(SrcReg) && 2496db0756f021a7b9c84d3bb7ae50498feb080a013Chris Lattner "Machine PHI Operands must all be virtual registers!"); 25053a79aaae988d9dc9d12af8970f8b8fe58cc478dChris Lattner 251287b8b0301bc6ec7eb70d23d242326a8766bb8ebLang Hames // Get the MachineBasicBlock equivalent of the BasicBlock that is the source 252287b8b0301bc6ec7eb70d23d242326a8766bb8ebLang Hames // path the PHI. 253287b8b0301bc6ec7eb70d23d242326a8766bb8ebLang Hames MachineBasicBlock &opBlock = *MPhi->getOperand(i*2+2).getMBB(); 254287b8b0301bc6ec7eb70d23d242326a8766bb8ebLang Hames 255287b8b0301bc6ec7eb70d23d242326a8766bb8ebLang Hames // Record the kill. 25620354634ebb64023d322919633f8bd348a63891dLang Hames PHIKills[SrcReg].insert(&opBlock); 257287b8b0301bc6ec7eb70d23d242326a8766bb8ebLang Hames 258ae94dda61a045cb77681940ecc25aba0d2763f74Bill Wendling // If source is defined by an implicit def, there is no need to insert a 2599f1c8317a4676945b4961ddb9827ef2412551620Evan Cheng // copy. 260576a27043d95d0b9b8a010bccfd38ed9c0afa739Evan Cheng MachineInstr *DefMI = MRI->getVRegDef(SrcReg); 261576a27043d95d0b9b8a010bccfd38ed9c0afa739Evan Cheng if (DefMI->getOpcode() == TargetInstrInfo::IMPLICIT_DEF) { 262576a27043d95d0b9b8a010bccfd38ed9c0afa739Evan Cheng ImpDefs.insert(DefMI); 263576a27043d95d0b9b8a010bccfd38ed9c0afa739Evan Cheng continue; 264576a27043d95d0b9b8a010bccfd38ed9c0afa739Evan Cheng } 265576a27043d95d0b9b8a010bccfd38ed9c0afa739Evan Cheng 26653a79aaae988d9dc9d12af8970f8b8fe58cc478dChris Lattner // Check to make sure we haven't already emitted the copy for this block. 267ae94dda61a045cb77681940ecc25aba0d2763f74Bill Wendling // This can happen because PHI nodes may have multiple entries for the same 268ae94dda61a045cb77681940ecc25aba0d2763f74Bill Wendling // basic block. 269576a27043d95d0b9b8a010bccfd38ed9c0afa739Evan Cheng if (!MBBsInsertedInto.insert(&opBlock)) 2706db0756f021a7b9c84d3bb7ae50498feb080a013Chris Lattner continue; // If the copy has already been emitted, we're done. 271e35e3c33dc5533dd1e8ab7d9f4039cc1429d56aaJakob Stoklund Olesen 272ae94dda61a045cb77681940ecc25aba0d2763f74Bill Wendling // Find a safe location to insert the copy, this may be the first terminator 273ae94dda61a045cb77681940ecc25aba0d2763f74Bill Wendling // in the block (or end()). 2741222287543a5b5917f8c31aa8c88d740f70222d9Jakob Stoklund Olesen MachineBasicBlock::iterator InsertPos = 2751222287543a5b5917f8c31aa8c88d740f70222d9Jakob Stoklund Olesen FindCopyInsertPoint(opBlock, MBB, SrcReg); 276fc0b80d9746e5fd4b45057ab814c67371fb0f9eaEvan Cheng 2776db0756f021a7b9c84d3bb7ae50498feb080a013Chris Lattner // Insert the copy. 278576a27043d95d0b9b8a010bccfd38ed9c0afa739Evan Cheng TII->copyRegToReg(opBlock, InsertPos, IncomingReg, SrcReg, RC, RC); 2796db0756f021a7b9c84d3bb7ae50498feb080a013Chris Lattner 2806db0756f021a7b9c84d3bb7ae50498feb080a013Chris Lattner // Now update live variable information if we have it. Otherwise we're done 2816db0756f021a7b9c84d3bb7ae50498feb080a013Chris Lattner if (!LV) continue; 282e35e3c33dc5533dd1e8ab7d9f4039cc1429d56aaJakob Stoklund Olesen 283ae94dda61a045cb77681940ecc25aba0d2763f74Bill Wendling // We want to be able to insert a kill of the register if this PHI (aka, the 284ae94dda61a045cb77681940ecc25aba0d2763f74Bill Wendling // copy we just inserted) is the last use of the source value. Live 285ae94dda61a045cb77681940ecc25aba0d2763f74Bill Wendling // variable analysis conservatively handles this by saying that the value is 286ae94dda61a045cb77681940ecc25aba0d2763f74Bill Wendling // live until the end of the block the PHI entry lives in. If the value 287ae94dda61a045cb77681940ecc25aba0d2763f74Bill Wendling // really is dead at the PHI copy, there will be no successor blocks which 288ae94dda61a045cb77681940ecc25aba0d2763f74Bill Wendling // have the value live-in. 289e35e3c33dc5533dd1e8ab7d9f4039cc1429d56aaJakob Stoklund Olesen 290ae94dda61a045cb77681940ecc25aba0d2763f74Bill Wendling // Also check to see if this register is in use by another PHI node which 291ae94dda61a045cb77681940ecc25aba0d2763f74Bill Wendling // has not yet been eliminated. If so, it will be killed at an appropriate 292ae94dda61a045cb77681940ecc25aba0d2763f74Bill Wendling // point later. 2936db0756f021a7b9c84d3bb7ae50498feb080a013Chris Lattner 2946db0756f021a7b9c84d3bb7ae50498feb080a013Chris Lattner // Is it used by any PHI instructions in this block? 295e35e3c33dc5533dd1e8ab7d9f4039cc1429d56aaJakob Stoklund Olesen bool ValueIsUsed = VRegPHIUseCount[BBVRegPair(&opBlock, SrcReg)] != 0; 2966db0756f021a7b9c84d3bb7ae50498feb080a013Chris Lattner 297ae94dda61a045cb77681940ecc25aba0d2763f74Bill Wendling // Okay, if we now know that the value is not live out of the block, we can 298ae94dda61a045cb77681940ecc25aba0d2763f74Bill Wendling // add a kill marker in this block saying that it kills the incoming value! 2993e20475feebca3bfb29375ac7f3e5acbeb2a95c8Jakob Stoklund Olesen if (!ValueIsUsed && !isLiveOut(SrcReg, opBlock, *LV)) { 3002adfa7e9320e79859beb556367ea607a329866b3Chris Lattner // In our final twist, we have to decide which instruction kills the 301ae94dda61a045cb77681940ecc25aba0d2763f74Bill Wendling // register. In most cases this is the copy, however, the first 3022adfa7e9320e79859beb556367ea607a329866b3Chris Lattner // terminator instruction at the end of the block may also use the value. 3032adfa7e9320e79859beb556367ea607a329866b3Chris Lattner // In this case, we should mark *it* as being the killing block, not the 3042adfa7e9320e79859beb556367ea607a329866b3Chris Lattner // copy. 305576a27043d95d0b9b8a010bccfd38ed9c0afa739Evan Cheng MachineBasicBlock::iterator KillInst = prior(InsertPos); 306576a27043d95d0b9b8a010bccfd38ed9c0afa739Evan Cheng MachineBasicBlock::iterator Term = opBlock.getFirstTerminator(); 307576a27043d95d0b9b8a010bccfd38ed9c0afa739Evan Cheng if (Term != opBlock.end()) { 308576a27043d95d0b9b8a010bccfd38ed9c0afa739Evan Cheng if (Term->readsRegister(SrcReg)) 309576a27043d95d0b9b8a010bccfd38ed9c0afa739Evan Cheng KillInst = Term; 310e35e3c33dc5533dd1e8ab7d9f4039cc1429d56aaJakob Stoklund Olesen 3112adfa7e9320e79859beb556367ea607a329866b3Chris Lattner // Check that no other terminators use values. 3122adfa7e9320e79859beb556367ea607a329866b3Chris Lattner#ifndef NDEBUG 313576a27043d95d0b9b8a010bccfd38ed9c0afa739Evan Cheng for (MachineBasicBlock::iterator TI = next(Term); TI != opBlock.end(); 3142adfa7e9320e79859beb556367ea607a329866b3Chris Lattner ++TI) { 315576a27043d95d0b9b8a010bccfd38ed9c0afa739Evan Cheng assert(!TI->readsRegister(SrcReg) && 3162adfa7e9320e79859beb556367ea607a329866b3Chris Lattner "Terminator instructions cannot use virtual registers unless" 3172adfa7e9320e79859beb556367ea607a329866b3Chris Lattner "they are the first terminator in a block!"); 3182adfa7e9320e79859beb556367ea607a329866b3Chris Lattner } 3192adfa7e9320e79859beb556367ea607a329866b3Chris Lattner#endif 3202adfa7e9320e79859beb556367ea607a329866b3Chris Lattner } 321e35e3c33dc5533dd1e8ab7d9f4039cc1429d56aaJakob Stoklund Olesen 3222adfa7e9320e79859beb556367ea607a329866b3Chris Lattner // Finally, mark it killed. 3232adfa7e9320e79859beb556367ea607a329866b3Chris Lattner LV->addVirtualRegisterKilled(SrcReg, KillInst); 3246db0756f021a7b9c84d3bb7ae50498feb080a013Chris Lattner 3256db0756f021a7b9c84d3bb7ae50498feb080a013Chris Lattner // This vreg no longer lives all of the way through opBlock. 3266db0756f021a7b9c84d3bb7ae50498feb080a013Chris Lattner unsigned opBlockNum = opBlock.getNumber(); 327e35e3c33dc5533dd1e8ab7d9f4039cc1429d56aaJakob Stoklund Olesen LV->getVarInfo(SrcReg).AliveBlocks.reset(opBlockNum); 328bc40e898e153c9b81f246a7971eaac7b14446c49Chris Lattner } 329bc40e898e153c9b81f246a7971eaac7b14446c49Chris Lattner } 330e35e3c33dc5533dd1e8ab7d9f4039cc1429d56aaJakob Stoklund Olesen 33153a79aaae988d9dc9d12af8970f8b8fe58cc478dChris Lattner // Really delete the PHI instruction now! 3328e5f2c6f65841542e2a7092553fe42a00048e4c7Dan Gohman MF.DeleteMachineInstr(MPhi); 3336db0756f021a7b9c84d3bb7ae50498feb080a013Chris Lattner ++NumAtomic; 334bc40e898e153c9b81f246a7971eaac7b14446c49Chris Lattner} 335ca756d2cf9bd88f210d61dd5f9776920a6178441Bill Wendling 336ca756d2cf9bd88f210d61dd5f9776920a6178441Bill Wendling/// analyzePHINodes - Gather information about the PHI nodes in here. In 337ca756d2cf9bd88f210d61dd5f9776920a6178441Bill Wendling/// particular, we want to map the number of uses of a virtual register which is 338ca756d2cf9bd88f210d61dd5f9776920a6178441Bill Wendling/// used in a PHI node. We map that to the BB the vreg is coming from. This is 339ca756d2cf9bd88f210d61dd5f9776920a6178441Bill Wendling/// used later to determine when the vreg is killed in the BB. 340ca756d2cf9bd88f210d61dd5f9776920a6178441Bill Wendling/// 341fae02a2ab19abdf12854356e19aeb1da62a0b8eaLang Hamesvoid llvm::PHIElimination::analyzePHINodes(const MachineFunction& Fn) { 342ca756d2cf9bd88f210d61dd5f9776920a6178441Bill Wendling for (MachineFunction::const_iterator I = Fn.begin(), E = Fn.end(); 343ca756d2cf9bd88f210d61dd5f9776920a6178441Bill Wendling I != E; ++I) 344ca756d2cf9bd88f210d61dd5f9776920a6178441Bill Wendling for (MachineBasicBlock::const_iterator BBI = I->begin(), BBE = I->end(); 345ca756d2cf9bd88f210d61dd5f9776920a6178441Bill Wendling BBI != BBE && BBI->getOpcode() == TargetInstrInfo::PHI; ++BBI) 346ca756d2cf9bd88f210d61dd5f9776920a6178441Bill Wendling for (unsigned i = 1, e = BBI->getNumOperands(); i != e; i += 2) 3478aa797aa51cd4ea1ec6f46f4891a6897944b75b2Chris Lattner ++VRegPHIUseCount[BBVRegPair(BBI->getOperand(i + 1).getMBB(), 3488aa797aa51cd4ea1ec6f46f4891a6897944b75b2Chris Lattner BBI->getOperand(i).getReg())]; 349ca756d2cf9bd88f210d61dd5f9776920a6178441Bill Wendling} 350e35e3c33dc5533dd1e8ab7d9f4039cc1429d56aaJakob Stoklund Olesen 3513e20475feebca3bfb29375ac7f3e5acbeb2a95c8Jakob Stoklund Olesenbool llvm::PHIElimination::SplitPHIEdges(MachineFunction &MF, 352f235f13931835b3335f3f2ff2d3060381b93626cJakob Stoklund Olesen MachineBasicBlock &MBB) { 3533e20475feebca3bfb29375ac7f3e5acbeb2a95c8Jakob Stoklund Olesen if (MBB.empty() || MBB.front().getOpcode() != TargetInstrInfo::PHI) 3543e20475feebca3bfb29375ac7f3e5acbeb2a95c8Jakob Stoklund Olesen return false; // Quick exit for basic blocks without PHIs. 355f235f13931835b3335f3f2ff2d3060381b93626cJakob Stoklund Olesen LiveVariables &LV = getAnalysis<LiveVariables>(); 356f235f13931835b3335f3f2ff2d3060381b93626cJakob Stoklund Olesen for (MachineBasicBlock::const_iterator BBI = MBB.begin(), BBE = MBB.end(); 357f235f13931835b3335f3f2ff2d3060381b93626cJakob Stoklund Olesen BBI != BBE && BBI->getOpcode() == TargetInstrInfo::PHI; ++BBI) { 358f235f13931835b3335f3f2ff2d3060381b93626cJakob Stoklund Olesen for (unsigned i = 1, e = BBI->getNumOperands(); i != e; i += 2) { 359f235f13931835b3335f3f2ff2d3060381b93626cJakob Stoklund Olesen unsigned Reg = BBI->getOperand(i).getReg(); 360f235f13931835b3335f3f2ff2d3060381b93626cJakob Stoklund Olesen MachineBasicBlock *PreMBB = BBI->getOperand(i+1).getMBB(); 361f235f13931835b3335f3f2ff2d3060381b93626cJakob Stoklund Olesen // We break edges when registers are live out from the predecessor block 3623e20475feebca3bfb29375ac7f3e5acbeb2a95c8Jakob Stoklund Olesen // (not considering PHI nodes). If the register is live in to this block 3633e20475feebca3bfb29375ac7f3e5acbeb2a95c8Jakob Stoklund Olesen // anyway, we would gain nothing from splitting. 3643e20475feebca3bfb29375ac7f3e5acbeb2a95c8Jakob Stoklund Olesen if (isLiveOut(Reg, *PreMBB, LV) && !isLiveIn(Reg, MBB, LV)) 365f235f13931835b3335f3f2ff2d3060381b93626cJakob Stoklund Olesen SplitCriticalEdge(PreMBB, &MBB); 366f235f13931835b3335f3f2ff2d3060381b93626cJakob Stoklund Olesen } 367f235f13931835b3335f3f2ff2d3060381b93626cJakob Stoklund Olesen } 3683e20475feebca3bfb29375ac7f3e5acbeb2a95c8Jakob Stoklund Olesen return true; 369f235f13931835b3335f3f2ff2d3060381b93626cJakob Stoklund Olesen} 370f235f13931835b3335f3f2ff2d3060381b93626cJakob Stoklund Olesen 371e35e3c33dc5533dd1e8ab7d9f4039cc1429d56aaJakob Stoklund Olesenbool llvm::PHIElimination::isLiveOut(unsigned Reg, const MachineBasicBlock &MBB, 372e35e3c33dc5533dd1e8ab7d9f4039cc1429d56aaJakob Stoklund Olesen LiveVariables &LV) { 3733e20475feebca3bfb29375ac7f3e5acbeb2a95c8Jakob Stoklund Olesen LiveVariables::VarInfo &VI = LV.getVarInfo(Reg); 374e35e3c33dc5533dd1e8ab7d9f4039cc1429d56aaJakob Stoklund Olesen 375e35e3c33dc5533dd1e8ab7d9f4039cc1429d56aaJakob Stoklund Olesen // Loop over all of the successors of the basic block, checking to see if 376e35e3c33dc5533dd1e8ab7d9f4039cc1429d56aaJakob Stoklund Olesen // the value is either live in the block, or if it is killed in the block. 377e35e3c33dc5533dd1e8ab7d9f4039cc1429d56aaJakob Stoklund Olesen std::vector<MachineBasicBlock*> OpSuccBlocks; 378e35e3c33dc5533dd1e8ab7d9f4039cc1429d56aaJakob Stoklund Olesen for (MachineBasicBlock::const_succ_iterator SI = MBB.succ_begin(), 379e35e3c33dc5533dd1e8ab7d9f4039cc1429d56aaJakob Stoklund Olesen E = MBB.succ_end(); SI != E; ++SI) { 380e35e3c33dc5533dd1e8ab7d9f4039cc1429d56aaJakob Stoklund Olesen MachineBasicBlock *SuccMBB = *SI; 381e35e3c33dc5533dd1e8ab7d9f4039cc1429d56aaJakob Stoklund Olesen 382e35e3c33dc5533dd1e8ab7d9f4039cc1429d56aaJakob Stoklund Olesen // Is it alive in this successor? 383e35e3c33dc5533dd1e8ab7d9f4039cc1429d56aaJakob Stoklund Olesen unsigned SuccIdx = SuccMBB->getNumber(); 3843e20475feebca3bfb29375ac7f3e5acbeb2a95c8Jakob Stoklund Olesen if (VI.AliveBlocks.test(SuccIdx)) 385e35e3c33dc5533dd1e8ab7d9f4039cc1429d56aaJakob Stoklund Olesen return true; 386e35e3c33dc5533dd1e8ab7d9f4039cc1429d56aaJakob Stoklund Olesen OpSuccBlocks.push_back(SuccMBB); 387e35e3c33dc5533dd1e8ab7d9f4039cc1429d56aaJakob Stoklund Olesen } 388e35e3c33dc5533dd1e8ab7d9f4039cc1429d56aaJakob Stoklund Olesen 389e35e3c33dc5533dd1e8ab7d9f4039cc1429d56aaJakob Stoklund Olesen // Check to see if this value is live because there is a use in a successor 390e35e3c33dc5533dd1e8ab7d9f4039cc1429d56aaJakob Stoklund Olesen // that kills it. 391e35e3c33dc5533dd1e8ab7d9f4039cc1429d56aaJakob Stoklund Olesen switch (OpSuccBlocks.size()) { 392e35e3c33dc5533dd1e8ab7d9f4039cc1429d56aaJakob Stoklund Olesen case 1: { 393e35e3c33dc5533dd1e8ab7d9f4039cc1429d56aaJakob Stoklund Olesen MachineBasicBlock *SuccMBB = OpSuccBlocks[0]; 3943e20475feebca3bfb29375ac7f3e5acbeb2a95c8Jakob Stoklund Olesen for (unsigned i = 0, e = VI.Kills.size(); i != e; ++i) 3953e20475feebca3bfb29375ac7f3e5acbeb2a95c8Jakob Stoklund Olesen if (VI.Kills[i]->getParent() == SuccMBB) 396e35e3c33dc5533dd1e8ab7d9f4039cc1429d56aaJakob Stoklund Olesen return true; 397e35e3c33dc5533dd1e8ab7d9f4039cc1429d56aaJakob Stoklund Olesen break; 398e35e3c33dc5533dd1e8ab7d9f4039cc1429d56aaJakob Stoklund Olesen } 399e35e3c33dc5533dd1e8ab7d9f4039cc1429d56aaJakob Stoklund Olesen case 2: { 400e35e3c33dc5533dd1e8ab7d9f4039cc1429d56aaJakob Stoklund Olesen MachineBasicBlock *SuccMBB1 = OpSuccBlocks[0], *SuccMBB2 = OpSuccBlocks[1]; 4013e20475feebca3bfb29375ac7f3e5acbeb2a95c8Jakob Stoklund Olesen for (unsigned i = 0, e = VI.Kills.size(); i != e; ++i) 4023e20475feebca3bfb29375ac7f3e5acbeb2a95c8Jakob Stoklund Olesen if (VI.Kills[i]->getParent() == SuccMBB1 || 4033e20475feebca3bfb29375ac7f3e5acbeb2a95c8Jakob Stoklund Olesen VI.Kills[i]->getParent() == SuccMBB2) 404e35e3c33dc5533dd1e8ab7d9f4039cc1429d56aaJakob Stoklund Olesen return true; 405e35e3c33dc5533dd1e8ab7d9f4039cc1429d56aaJakob Stoklund Olesen break; 406e35e3c33dc5533dd1e8ab7d9f4039cc1429d56aaJakob Stoklund Olesen } 407e35e3c33dc5533dd1e8ab7d9f4039cc1429d56aaJakob Stoklund Olesen default: 408e35e3c33dc5533dd1e8ab7d9f4039cc1429d56aaJakob Stoklund Olesen std::sort(OpSuccBlocks.begin(), OpSuccBlocks.end()); 4093e20475feebca3bfb29375ac7f3e5acbeb2a95c8Jakob Stoklund Olesen for (unsigned i = 0, e = VI.Kills.size(); i != e; ++i) 410e35e3c33dc5533dd1e8ab7d9f4039cc1429d56aaJakob Stoklund Olesen if (std::binary_search(OpSuccBlocks.begin(), OpSuccBlocks.end(), 4113e20475feebca3bfb29375ac7f3e5acbeb2a95c8Jakob Stoklund Olesen VI.Kills[i]->getParent())) 412e35e3c33dc5533dd1e8ab7d9f4039cc1429d56aaJakob Stoklund Olesen return true; 413e35e3c33dc5533dd1e8ab7d9f4039cc1429d56aaJakob Stoklund Olesen } 414e35e3c33dc5533dd1e8ab7d9f4039cc1429d56aaJakob Stoklund Olesen return false; 415e35e3c33dc5533dd1e8ab7d9f4039cc1429d56aaJakob Stoklund Olesen} 416f235f13931835b3335f3f2ff2d3060381b93626cJakob Stoklund Olesen 4173e20475feebca3bfb29375ac7f3e5acbeb2a95c8Jakob Stoklund Olesenbool llvm::PHIElimination::isLiveIn(unsigned Reg, const MachineBasicBlock &MBB, 4183e20475feebca3bfb29375ac7f3e5acbeb2a95c8Jakob Stoklund Olesen LiveVariables &LV) { 4193e20475feebca3bfb29375ac7f3e5acbeb2a95c8Jakob Stoklund Olesen LiveVariables::VarInfo &VI = LV.getVarInfo(Reg); 4203e20475feebca3bfb29375ac7f3e5acbeb2a95c8Jakob Stoklund Olesen 4213b6ced15108909de2fab0766fc693fe66c48ab68Jakob Stoklund Olesen if (VI.AliveBlocks.test(MBB.getNumber())) 4223b6ced15108909de2fab0766fc693fe66c48ab68Jakob Stoklund Olesen return true; 4233b6ced15108909de2fab0766fc693fe66c48ab68Jakob Stoklund Olesen 4243b6ced15108909de2fab0766fc693fe66c48ab68Jakob Stoklund Olesen // defined in MBB? 4253b6ced15108909de2fab0766fc693fe66c48ab68Jakob Stoklund Olesen const MachineInstr *Def = MRI->getVRegDef(Reg); 4263b6ced15108909de2fab0766fc693fe66c48ab68Jakob Stoklund Olesen if (Def && Def->getParent() == &MBB) 4273b6ced15108909de2fab0766fc693fe66c48ab68Jakob Stoklund Olesen return false; 4283b6ced15108909de2fab0766fc693fe66c48ab68Jakob Stoklund Olesen 4293b6ced15108909de2fab0766fc693fe66c48ab68Jakob Stoklund Olesen // killed in MBB? 4303b6ced15108909de2fab0766fc693fe66c48ab68Jakob Stoklund Olesen return VI.findKill(&MBB); 4313e20475feebca3bfb29375ac7f3e5acbeb2a95c8Jakob Stoklund Olesen} 4323e20475feebca3bfb29375ac7f3e5acbeb2a95c8Jakob Stoklund Olesen 433f235f13931835b3335f3f2ff2d3060381b93626cJakob Stoklund OlesenMachineBasicBlock *PHIElimination::SplitCriticalEdge(MachineBasicBlock *A, 434f235f13931835b3335f3f2ff2d3060381b93626cJakob Stoklund Olesen MachineBasicBlock *B) { 435f235f13931835b3335f3f2ff2d3060381b93626cJakob Stoklund Olesen assert(A && B && "Missing MBB end point"); 436f235f13931835b3335f3f2ff2d3060381b93626cJakob Stoklund Olesen ++NumSplits; 437f235f13931835b3335f3f2ff2d3060381b93626cJakob Stoklund Olesen 438f235f13931835b3335f3f2ff2d3060381b93626cJakob Stoklund Olesen MachineFunction *MF = A->getParent(); 4391222287543a5b5917f8c31aa8c88d740f70222d9Jakob Stoklund Olesen MachineBasicBlock *NMBB = MF->CreateMachineBasicBlock(); 440f235f13931835b3335f3f2ff2d3060381b93626cJakob Stoklund Olesen MF->push_back(NMBB); 441f235f13931835b3335f3f2ff2d3060381b93626cJakob Stoklund Olesen DEBUG(errs() << "PHIElimination splitting critical edge:" 442f235f13931835b3335f3f2ff2d3060381b93626cJakob Stoklund Olesen " BB#" << A->getNumber() 443bf4af353edd2da1d7f2ed0b22238a8d2c038f5cfDaniel Dunbar << " -- BB#" << NMBB->getNumber() 444f235f13931835b3335f3f2ff2d3060381b93626cJakob Stoklund Olesen << " -- BB#" << B->getNumber() << '\n'); 445f235f13931835b3335f3f2ff2d3060381b93626cJakob Stoklund Olesen 446f235f13931835b3335f3f2ff2d3060381b93626cJakob Stoklund Olesen A->ReplaceUsesOfBlockWith(B, NMBB); 4473b6ced15108909de2fab0766fc693fe66c48ab68Jakob Stoklund Olesen // If A may fall through to B, we may have to insert a branch. 4483b6ced15108909de2fab0766fc693fe66c48ab68Jakob Stoklund Olesen if (A->isLayoutSuccessor(B)) 4493b6ced15108909de2fab0766fc693fe66c48ab68Jakob Stoklund Olesen A->updateTerminator(); 450f235f13931835b3335f3f2ff2d3060381b93626cJakob Stoklund Olesen 451f235f13931835b3335f3f2ff2d3060381b93626cJakob Stoklund Olesen // Insert unconditional "jump B" instruction in NMBB. 4523b6ced15108909de2fab0766fc693fe66c48ab68Jakob Stoklund Olesen NMBB->addSuccessor(B); 453f235f13931835b3335f3f2ff2d3060381b93626cJakob Stoklund Olesen SmallVector<MachineOperand, 4> Cond; 454f235f13931835b3335f3f2ff2d3060381b93626cJakob Stoklund Olesen MF->getTarget().getInstrInfo()->InsertBranch(*NMBB, B, NULL, Cond); 455f235f13931835b3335f3f2ff2d3060381b93626cJakob Stoklund Olesen 456f235f13931835b3335f3f2ff2d3060381b93626cJakob Stoklund Olesen // Fix PHI nodes in B so they refer to NMBB instead of A 457f235f13931835b3335f3f2ff2d3060381b93626cJakob Stoklund Olesen for (MachineBasicBlock::iterator i = B->begin(), e = B->end(); 458f235f13931835b3335f3f2ff2d3060381b93626cJakob Stoklund Olesen i != e && i->getOpcode() == TargetInstrInfo::PHI; ++i) 459f235f13931835b3335f3f2ff2d3060381b93626cJakob Stoklund Olesen for (unsigned ni = 1, ne = i->getNumOperands(); ni != ne; ni += 2) 4603e20475feebca3bfb29375ac7f3e5acbeb2a95c8Jakob Stoklund Olesen if (i->getOperand(ni+1).getMBB() == A) 461f235f13931835b3335f3f2ff2d3060381b93626cJakob Stoklund Olesen i->getOperand(ni+1).setMBB(NMBB); 4629aebb61daf4d787aa7dcff9e3caa89bac88e11d1Jakob Stoklund Olesen 4639aebb61daf4d787aa7dcff9e3caa89bac88e11d1Jakob Stoklund Olesen if (LiveVariables *LV=getAnalysisIfAvailable<LiveVariables>()) 4649aebb61daf4d787aa7dcff9e3caa89bac88e11d1Jakob Stoklund Olesen LV->addNewBlock(NMBB, A); 4659aebb61daf4d787aa7dcff9e3caa89bac88e11d1Jakob Stoklund Olesen 4669aebb61daf4d787aa7dcff9e3caa89bac88e11d1Jakob Stoklund Olesen if (MachineDominatorTree *MDT=getAnalysisIfAvailable<MachineDominatorTree>()) 4679aebb61daf4d787aa7dcff9e3caa89bac88e11d1Jakob Stoklund Olesen MDT->addNewBlock(NMBB, A); 4689aebb61daf4d787aa7dcff9e3caa89bac88e11d1Jakob Stoklund Olesen 469f235f13931835b3335f3f2ff2d3060381b93626cJakob Stoklund Olesen return NMBB; 470f235f13931835b3335f3f2ff2d3060381b93626cJakob Stoklund Olesen} 471