LiveIntervalAnalysis.cpp revision 4281e20aab7f1fe1b35b31c9237ad89c20937e02
1a3b8b5c0e0a1d0942288568b2012592184ca67c5Chris Lattner//===-- LiveIntervalAnalysis.cpp - Live Interval Analysis -----------------===// 2ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos// 3ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos// The LLVM Compiler Infrastructure 4ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos// 54ee451de366474b9c228b4e5fa573795a715216dChris Lattner// This file is distributed under the University of Illinois Open Source 64ee451de366474b9c228b4e5fa573795a715216dChris Lattner// License. See LICENSE.TXT for details. 7ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos// 8ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos//===----------------------------------------------------------------------===// 9ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos// 10ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos// This file implements the LiveInterval analysis pass which is used 11ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos// by the Linear Scan Register allocator. This pass linearizes the 12ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos// basic blocks of the function in DFS order and uses the 13ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos// LiveVariables pass to conservatively compute live intervals for 14ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos// each virtual and physical register. 15ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos// 16ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos//===----------------------------------------------------------------------===// 17ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos 184281e20aab7f1fe1b35b31c9237ad89c20937e02Jakob Stoklund Olesen#define DEBUG_TYPE "regalloc" 193c3fe462f7978b429ecdd71750c26be25c3d1335Chris Lattner#include "llvm/CodeGen/LiveIntervalAnalysis.h" 2008a6c7614be9793754b17930ba619e875aef9585Misha Brukman#include "VirtRegMap.h" 21015959ee38e4fd4a920f6b0065c50e524762f580Chris Lattner#include "llvm/Value.h" 226d69ba8a6901c69d78488cbc41f8dbf080618fdeDan Gohman#include "llvm/Analysis/AliasAnalysis.h" 23eb9f040f0d07e2fa9b3b5ef46d5ee32511d28811Jakob Stoklund Olesen#include "llvm/CodeGen/CalcSpillWeights.h" 24ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos#include "llvm/CodeGen/LiveVariables.h" 25ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos#include "llvm/CodeGen/MachineFrameInfo.h" 26ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos#include "llvm/CodeGen/MachineInstr.h" 272578ba26e72e36dde64be0f52a2788480aad3378Evan Cheng#include "llvm/CodeGen/MachineInstrBuilder.h" 2822f07ffd27d1d721634d502c37267721d2e025cfEvan Cheng#include "llvm/CodeGen/MachineLoopInfo.h" 29c76909abfec876c6b751d693ebd3df07df686aa0Dan Gohman#include "llvm/CodeGen/MachineMemOperand.h" 3084bc5427d6883f73cfeae3da640acd011d35c006Chris Lattner#include "llvm/CodeGen/MachineRegisterInfo.h" 31ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos#include "llvm/CodeGen/Passes.h" 32233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames#include "llvm/CodeGen/ProcessImplicitDefs.h" 336f0d024a534af18d9e60b3ea757376cd8a3a980eDan Gohman#include "llvm/Target/TargetRegisterInfo.h" 34ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos#include "llvm/Target/TargetInstrInfo.h" 35ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos#include "llvm/Target/TargetMachine.h" 3695dad830bbf975cb4cea4e1ac685781a18676a7aOwen Anderson#include "llvm/Target/TargetOptions.h" 37551ccae044b0ff658fe629dd67edd5ffe75d10e8Reid Spencer#include "llvm/Support/CommandLine.h" 38551ccae044b0ff658fe629dd67edd5ffe75d10e8Reid Spencer#include "llvm/Support/Debug.h" 397d696d80409aad20bb5da0fc4eccab941dd371d4Torok Edwin#include "llvm/Support/ErrorHandling.h" 407d696d80409aad20bb5da0fc4eccab941dd371d4Torok Edwin#include "llvm/Support/raw_ostream.h" 412578ba26e72e36dde64be0f52a2788480aad3378Evan Cheng#include "llvm/ADT/DepthFirstIterator.h" 422578ba26e72e36dde64be0f52a2788480aad3378Evan Cheng#include "llvm/ADT/SmallSet.h" 43551ccae044b0ff658fe629dd67edd5ffe75d10e8Reid Spencer#include "llvm/ADT/Statistic.h" 44551ccae044b0ff658fe629dd67edd5ffe75d10e8Reid Spencer#include "llvm/ADT/STLExtras.h" 4520aa474f8fbebde588edc101b90e834df28ce4ceAlkis Evlogimenos#include <algorithm> 46f41538d1b54f55e8900394929b50f7ce3e61125fLang Hames#include <limits> 4797af751deb9b26fd42fbcee082da9ccc4ded5b45Jeff Cohen#include <cmath> 48ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenosusing namespace llvm; 49ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos 50844731a7f1909f55935e3514c9e713a62d67662eDan Gohman// Hidden options for help debugging. 511b2932024f098a6968645ac78d5848951d877c19Jakob Stoklund Olesenstatic cl::opt<bool> DisableReMat("disable-rematerialization", 52844731a7f1909f55935e3514c9e713a62d67662eDan Gohman cl::init(false), cl::Hidden); 53844731a7f1909f55935e3514c9e713a62d67662eDan Gohman 54752195e3c662c6b5db042cf897c984624720f3b8Evan ChengSTATISTIC(numIntervals , "Number of original intervals"); 55cd3245ac45c595da96bb768a55cddc356dff55feChris Lattner 561997473cf72957d0e70322e2fe6fe2ab141c58a6Devang Patelchar LiveIntervals::ID = 0; 572ab36d350293c77fc8941ce1023e4899df7e3a82Owen AndersonINITIALIZE_PASS_BEGIN(LiveIntervals, "liveintervals", 582ab36d350293c77fc8941ce1023e4899df7e3a82Owen Anderson "Live Interval Analysis", false, false) 592ab36d350293c77fc8941ce1023e4899df7e3a82Owen AndersonINITIALIZE_PASS_DEPENDENCY(LiveVariables) 602ab36d350293c77fc8941ce1023e4899df7e3a82Owen AndersonINITIALIZE_PASS_DEPENDENCY(MachineLoopInfo) 612ab36d350293c77fc8941ce1023e4899df7e3a82Owen AndersonINITIALIZE_PASS_DEPENDENCY(PHIElimination) 622ab36d350293c77fc8941ce1023e4899df7e3a82Owen AndersonINITIALIZE_PASS_DEPENDENCY(TwoAddressInstructionPass) 632ab36d350293c77fc8941ce1023e4899df7e3a82Owen AndersonINITIALIZE_PASS_DEPENDENCY(ProcessImplicitDefs) 642ab36d350293c77fc8941ce1023e4899df7e3a82Owen AndersonINITIALIZE_PASS_DEPENDENCY(SlotIndexes) 652ab36d350293c77fc8941ce1023e4899df7e3a82Owen AndersonINITIALIZE_AG_DEPENDENCY(AliasAnalysis) 662ab36d350293c77fc8941ce1023e4899df7e3a82Owen AndersonINITIALIZE_PASS_END(LiveIntervals, "liveintervals", 67ce665bd2e2b581ab0858d1afe359192bac96b868Owen Anderson "Live Interval Analysis", false, false) 68ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos 69f7da2c7b0c6293c268881628fc351bed7763f1f4Chris Lattnervoid LiveIntervals::getAnalysisUsage(AnalysisUsage &AU) const { 70845012e6d31799c7fbd1193fa1af8ee2d12e9231Dan Gohman AU.setPreservesCFG(); 716d69ba8a6901c69d78488cbc41f8dbf080618fdeDan Gohman AU.addRequired<AliasAnalysis>(); 726d69ba8a6901c69d78488cbc41f8dbf080618fdeDan Gohman AU.addPreserved<AliasAnalysis>(); 731a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos AU.addRequired<LiveVariables>(); 74148341cc9b60d7d88be9c07a2b32b436e0cd301dEvan Cheng AU.addPreserved<LiveVariables>(); 75148341cc9b60d7d88be9c07a2b32b436e0cd301dEvan Cheng AU.addRequired<MachineLoopInfo>(); 76148341cc9b60d7d88be9c07a2b32b436e0cd301dEvan Cheng AU.addPreserved<MachineLoopInfo>(); 7767d65bb69d5cad957cbb6d672dc0b4a19c211a42Bill Wendling AU.addPreservedID(MachineDominatorsID); 781b2932024f098a6968645ac78d5848951d877c19Jakob Stoklund Olesen 7995dad830bbf975cb4cea4e1ac685781a18676a7aOwen Anderson if (!StrongPHIElim) { 8095dad830bbf975cb4cea4e1ac685781a18676a7aOwen Anderson AU.addPreservedID(PHIEliminationID); 8195dad830bbf975cb4cea4e1ac685781a18676a7aOwen Anderson AU.addRequiredID(PHIEliminationID); 8295dad830bbf975cb4cea4e1ac685781a18676a7aOwen Anderson } 831b2932024f098a6968645ac78d5848951d877c19Jakob Stoklund Olesen 841a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos AU.addRequiredID(TwoAddressInstructionPassID); 85233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames AU.addPreserved<ProcessImplicitDefs>(); 86233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames AU.addRequired<ProcessImplicitDefs>(); 87233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames AU.addPreserved<SlotIndexes>(); 88233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames AU.addRequiredTransitive<SlotIndexes>(); 891a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos MachineFunctionPass::getAnalysisUsage(AU); 90ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos} 91ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos 92f7da2c7b0c6293c268881628fc351bed7763f1f4Chris Lattnervoid LiveIntervals::releaseMemory() { 9303857b29d8271a23943254579e6cf7b7df4b1bd3Owen Anderson // Free the live intervals themselves. 9420e2839cb975a2d4ee931e1ea4c4660a36ef0177Owen Anderson for (DenseMap<unsigned, LiveInterval*>::iterator I = r2iMap_.begin(), 95d6a6b3b7563a3f54ba48d465fc03ee10bbccb7a8Bob Wilson E = r2iMap_.end(); I != E; ++I) 9603857b29d8271a23943254579e6cf7b7df4b1bd3Owen Anderson delete I->second; 971b2932024f098a6968645ac78d5848951d877c19Jakob Stoklund Olesen 981a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos r2iMap_.clear(); 99ffd1326ff8dfc652a8026c3faebf55bbba7c32c7Lang Hames 100ce9a20b808ba48adf72e0c0615f903a65e9f9eb8Benjamin Kramer // Release VNInfo memory regions, VNInfo objects don't need to be dtor'd. 101ce9a20b808ba48adf72e0c0615f903a65e9f9eb8Benjamin Kramer VNInfoAllocator.Reset(); 102752195e3c662c6b5db042cf897c984624720f3b8Evan Cheng while (!CloneMIs.empty()) { 103752195e3c662c6b5db042cf897c984624720f3b8Evan Cheng MachineInstr *MI = CloneMIs.back(); 104752195e3c662c6b5db042cf897c984624720f3b8Evan Cheng CloneMIs.pop_back(); 1051ed9922794cda9dbe295e74674b909287e544632Evan Cheng mf_->DeleteMachineInstr(MI); 1061ed9922794cda9dbe295e74674b909287e544632Evan Cheng } 107993141402f57b4d4cbb7f8a3113f19c61688f9b7Evan Cheng} 108993141402f57b4d4cbb7f8a3113f19c61688f9b7Evan Cheng 10980b3ce65e294a28b88c882d44a5e749a2924c9e3Owen Anderson/// runOnMachineFunction - Register allocate the whole function 11080b3ce65e294a28b88c882d44a5e749a2924c9e3Owen Anderson/// 11180b3ce65e294a28b88c882d44a5e749a2924c9e3Owen Andersonbool LiveIntervals::runOnMachineFunction(MachineFunction &fn) { 11280b3ce65e294a28b88c882d44a5e749a2924c9e3Owen Anderson mf_ = &fn; 11380b3ce65e294a28b88c882d44a5e749a2924c9e3Owen Anderson mri_ = &mf_->getRegInfo(); 11480b3ce65e294a28b88c882d44a5e749a2924c9e3Owen Anderson tm_ = &fn.getTarget(); 11580b3ce65e294a28b88c882d44a5e749a2924c9e3Owen Anderson tri_ = tm_->getRegisterInfo(); 11680b3ce65e294a28b88c882d44a5e749a2924c9e3Owen Anderson tii_ = tm_->getInstrInfo(); 1176d69ba8a6901c69d78488cbc41f8dbf080618fdeDan Gohman aa_ = &getAnalysis<AliasAnalysis>(); 11880b3ce65e294a28b88c882d44a5e749a2924c9e3Owen Anderson lv_ = &getAnalysis<LiveVariables>(); 119233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames indexes_ = &getAnalysis<SlotIndexes>(); 12080b3ce65e294a28b88c882d44a5e749a2924c9e3Owen Anderson allocatableRegs_ = tri_->getAllocatableSet(fn); 121ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos 1221a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos computeIntervals(); 123ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos 1241a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos numIntervals += getNumIntervals(); 125843b160a2040b3ec4d3452678450afa11704c473Alkis Evlogimenos 12670ca358b7d540b6061236ddf757085042873c12cChris Lattner DEBUG(dump()); 1271a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos return true; 128ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos} 129ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos 13070ca358b7d540b6061236ddf757085042873c12cChris Lattner/// print - Implement the dump method. 13145cfe545ec8177262dabc70580ce05feaa1c3880Chris Lattnervoid LiveIntervals::print(raw_ostream &OS, const Module* ) const { 132705e07f578e2b3af47ddab610feb4e7f2d3063a5Chris Lattner OS << "********** INTERVALS **********\n"; 1338e7a70976deee78a84099b916591d40f7a1cdc34Chris Lattner for (const_iterator I = begin(), E = end(); I != E; ++I) { 134705e07f578e2b3af47ddab610feb4e7f2d3063a5Chris Lattner I->second->print(OS, tri_); 135705e07f578e2b3af47ddab610feb4e7f2d3063a5Chris Lattner OS << "\n"; 1368e7a70976deee78a84099b916591d40f7a1cdc34Chris Lattner } 13770ca358b7d540b6061236ddf757085042873c12cChris Lattner 138752195e3c662c6b5db042cf897c984624720f3b8Evan Cheng printInstrs(OS); 139752195e3c662c6b5db042cf897c984624720f3b8Evan Cheng} 140752195e3c662c6b5db042cf897c984624720f3b8Evan Cheng 141752195e3c662c6b5db042cf897c984624720f3b8Evan Chengvoid LiveIntervals::printInstrs(raw_ostream &OS) const { 142705e07f578e2b3af47ddab610feb4e7f2d3063a5Chris Lattner OS << "********** MACHINEINSTRS **********\n"; 143f4a1e1a69f0727762a73ef0d551e3bbd16b7c04eJakob Stoklund Olesen mf_->print(OS, indexes_); 14470ca358b7d540b6061236ddf757085042873c12cChris Lattner} 14570ca358b7d540b6061236ddf757085042873c12cChris Lattner 146752195e3c662c6b5db042cf897c984624720f3b8Evan Chengvoid LiveIntervals::dumpInstrs() const { 1478a34229dcf484739119857988772572ef0cad9f2David Greene printInstrs(dbgs()); 148752195e3c662c6b5db042cf897c984624720f3b8Evan Cheng} 149752195e3c662c6b5db042cf897c984624720f3b8Evan Cheng 150afff40a62da19be15295c0f8ed5d4d450ccb45a5Evan Chengstatic 1513749943648772743c9c0e852553e50e6700a0c1bEvan Chengbool MultipleDefsBySameMI(const MachineInstr &MI, unsigned MOIdx) { 152afff40a62da19be15295c0f8ed5d4d450ccb45a5Evan Cheng unsigned Reg = MI.getOperand(MOIdx).getReg(); 153afff40a62da19be15295c0f8ed5d4d450ccb45a5Evan Cheng for (unsigned i = MOIdx+1, e = MI.getNumOperands(); i < e; ++i) { 154afff40a62da19be15295c0f8ed5d4d450ccb45a5Evan Cheng const MachineOperand &MO = MI.getOperand(i); 155afff40a62da19be15295c0f8ed5d4d450ccb45a5Evan Cheng if (!MO.isReg()) 156afff40a62da19be15295c0f8ed5d4d450ccb45a5Evan Cheng continue; 157afff40a62da19be15295c0f8ed5d4d450ccb45a5Evan Cheng if (MO.getReg() == Reg && MO.isDef()) { 158afff40a62da19be15295c0f8ed5d4d450ccb45a5Evan Cheng assert(MI.getOperand(MOIdx).getSubReg() != MO.getSubReg() && 159afff40a62da19be15295c0f8ed5d4d450ccb45a5Evan Cheng MI.getOperand(MOIdx).getSubReg() && 160ed2185e171a86b8c0e166803fd4066383a6cff08Jakob Stoklund Olesen (MO.getSubReg() || MO.isImplicit())); 161afff40a62da19be15295c0f8ed5d4d450ccb45a5Evan Cheng return true; 162afff40a62da19be15295c0f8ed5d4d450ccb45a5Evan Cheng } 163afff40a62da19be15295c0f8ed5d4d450ccb45a5Evan Cheng } 164afff40a62da19be15295c0f8ed5d4d450ccb45a5Evan Cheng return false; 165afff40a62da19be15295c0f8ed5d4d450ccb45a5Evan Cheng} 166afff40a62da19be15295c0f8ed5d4d450ccb45a5Evan Cheng 1673749943648772743c9c0e852553e50e6700a0c1bEvan Cheng/// isPartialRedef - Return true if the specified def at the specific index is 1683749943648772743c9c0e852553e50e6700a0c1bEvan Cheng/// partially re-defining the specified live interval. A common case of this is 1691b2932024f098a6968645ac78d5848951d877c19Jakob Stoklund Olesen/// a definition of the sub-register. 1703749943648772743c9c0e852553e50e6700a0c1bEvan Chengbool LiveIntervals::isPartialRedef(SlotIndex MIIdx, MachineOperand &MO, 1713749943648772743c9c0e852553e50e6700a0c1bEvan Cheng LiveInterval &interval) { 1723749943648772743c9c0e852553e50e6700a0c1bEvan Cheng if (!MO.getSubReg() || MO.isEarlyClobber()) 1733749943648772743c9c0e852553e50e6700a0c1bEvan Cheng return false; 1743749943648772743c9c0e852553e50e6700a0c1bEvan Cheng 1752debd48ca790ac01be6e12e094fdf4fdcadc8364Jakob Stoklund Olesen SlotIndex RedefIndex = MIIdx.getRegSlot(); 1763749943648772743c9c0e852553e50e6700a0c1bEvan Cheng const LiveRange *OldLR = 1772debd48ca790ac01be6e12e094fdf4fdcadc8364Jakob Stoklund Olesen interval.getLiveRangeContaining(RedefIndex.getRegSlot(true)); 1786e2968c85c1e162ee5bc813769eab223e3df0f15Lang Hames MachineInstr *DefMI = getInstructionFromIndex(OldLR->valno->def); 1796e2968c85c1e162ee5bc813769eab223e3df0f15Lang Hames if (DefMI != 0) { 1803749943648772743c9c0e852553e50e6700a0c1bEvan Cheng return DefMI->findRegisterDefOperandIdx(interval.reg) != -1; 1813749943648772743c9c0e852553e50e6700a0c1bEvan Cheng } 1823749943648772743c9c0e852553e50e6700a0c1bEvan Cheng return false; 1833749943648772743c9c0e852553e50e6700a0c1bEvan Cheng} 1843749943648772743c9c0e852553e50e6700a0c1bEvan Cheng 185be4f88a8b8bb3311e0dc4cde8533763d7923c3eaChris Lattnervoid LiveIntervals::handleVirtualRegisterDef(MachineBasicBlock *mbb, 186ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos MachineBasicBlock::iterator mi, 187233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames SlotIndex MIIdx, 1888651125d2885f74546b6e2a556082111d5b75da3Lang Hames MachineOperand& MO, 189ef0732d25a9882c947984ae3f2afbef5463ba00fEvan Cheng unsigned MOIdx, 190be4f88a8b8bb3311e0dc4cde8533763d7923c3eaChris Lattner LiveInterval &interval) { 1914314268128be6d54c9a7f0709680e5a5b40f3ab3Jakob Stoklund Olesen DEBUG(dbgs() << "\t\tregister: " << PrintReg(interval.reg, tri_)); 192419852ca8a01aecde4c0e20af6b7bd6450e70f87Evan Cheng 193706515727c6d024015fffded2b3109a4f0ac5299Alkis Evlogimenos // Virtual registers may be defined multiple times (due to phi 194706515727c6d024015fffded2b3109a4f0ac5299Alkis Evlogimenos // elimination and 2-addr elimination). Much of what we do only has to be 195706515727c6d024015fffded2b3109a4f0ac5299Alkis Evlogimenos // done once for the vreg. We use an empty interval to detect the first 1961a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // time we see a vreg. 197d129d73b725e32d2fc0c87f392c239db8801e922Evan Cheng LiveVariables::VarInfo& vi = lv_->getVarInfo(interval.reg); 1981a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos if (interval.empty()) { 1991a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // Get the Idx of the defining instructions. 200d14614e6777771f8fec3062bcaf2986c189ac84dJakob Stoklund Olesen SlotIndex defIndex = MIIdx.getRegSlot(MO.isEarlyClobber()); 20163e6a488cb6c29983415221719d05fbf99e00193Jakob Stoklund Olesen 20263e6a488cb6c29983415221719d05fbf99e00193Jakob Stoklund Olesen // Make sure the first definition is not a partial redefinition. Add an 20363e6a488cb6c29983415221719d05fbf99e00193Jakob Stoklund Olesen // <imp-def> of the full register. 204b0e1bc7b99809e2b45726affd73f72c60c506ea0Jakob Stoklund Olesen // FIXME: LiveIntervals shouldn't modify the code like this. Whoever 205b0e1bc7b99809e2b45726affd73f72c60c506ea0Jakob Stoklund Olesen // created the machine instruction should annotate it with <undef> flags 206b0e1bc7b99809e2b45726affd73f72c60c506ea0Jakob Stoklund Olesen // as needed. Then we can simply assert here. The REG_SEQUENCE lowering 207b0e1bc7b99809e2b45726affd73f72c60c506ea0Jakob Stoklund Olesen // is the main suspect. 2087016cf66ee21ddf3f7823d4e332b2cb84953bebdJakob Stoklund Olesen if (MO.getSubReg()) { 20963e6a488cb6c29983415221719d05fbf99e00193Jakob Stoklund Olesen mi->addRegisterDefined(interval.reg); 2107016cf66ee21ddf3f7823d4e332b2cb84953bebdJakob Stoklund Olesen // Mark all defs of interval.reg on this instruction as reading <undef>. 2117016cf66ee21ddf3f7823d4e332b2cb84953bebdJakob Stoklund Olesen for (unsigned i = MOIdx, e = mi->getNumOperands(); i != e; ++i) { 2127016cf66ee21ddf3f7823d4e332b2cb84953bebdJakob Stoklund Olesen MachineOperand &MO2 = mi->getOperand(i); 2137016cf66ee21ddf3f7823d4e332b2cb84953bebdJakob Stoklund Olesen if (MO2.isReg() && MO2.getReg() == interval.reg && MO2.getSubReg()) 2147016cf66ee21ddf3f7823d4e332b2cb84953bebdJakob Stoklund Olesen MO2.setIsUndef(); 2157016cf66ee21ddf3f7823d4e332b2cb84953bebdJakob Stoklund Olesen } 2167016cf66ee21ddf3f7823d4e332b2cb84953bebdJakob Stoklund Olesen } 21763e6a488cb6c29983415221719d05fbf99e00193Jakob Stoklund Olesen 218c8d044e4f779fdcfc5e7d592927740fd8f672a70Evan Cheng MachineInstr *CopyMI = NULL; 21904c528a0c86ddf3d6a70681f72e1b2ec07b0b53aJakob Stoklund Olesen if (mi->isCopyLike()) { 220c8d044e4f779fdcfc5e7d592927740fd8f672a70Evan Cheng CopyMI = mi; 2210465bcffbbffb5ff5f420787b4350cb8abb196f7Jakob Stoklund Olesen } 2220465bcffbbffb5ff5f420787b4350cb8abb196f7Jakob Stoklund Olesen 2236e2968c85c1e162ee5bc813769eab223e3df0f15Lang Hames VNInfo *ValNo = interval.getNextValue(defIndex, CopyMI, VNInfoAllocator); 2247ecb38be0a533e7b9c7d3b8e9b5c8a6fa5f6b349Evan Cheng assert(ValNo->id == 0 && "First value in interval is not 0?"); 2251a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos 2261a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // Loop over all of the blocks that the vreg is defined in. There are 2271a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // two cases we have to handle here. The most common case is a vreg 2281a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // whose lifetime is contained within a basic block. In this case there 2291a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // will be a single kill, in MBB, which comes after the definition. 2301a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos if (vi.Kills.size() == 1 && vi.Kills[0]->getParent() == mbb) { 2311a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // FIXME: what about dead vars? 232233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames SlotIndex killIdx; 2331a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos if (vi.Kills[0] != mi) 2342debd48ca790ac01be6e12e094fdf4fdcadc8364Jakob Stoklund Olesen killIdx = getInstructionIndex(vi.Kills[0]).getRegSlot(); 2351a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos else 2362debd48ca790ac01be6e12e094fdf4fdcadc8364Jakob Stoklund Olesen killIdx = defIndex.getDeadSlot(); 2371a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos 2381a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // If the kill happens after the definition, we have an intra-block 2391a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // live range. 2401a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos if (killIdx > defIndex) { 241493a3d015cbb2bcc18d9293a4dec3b35c7493818Jeffrey Yasskin assert(vi.AliveBlocks.empty() && 2421a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos "Shouldn't be alive across any blocks!"); 2437ecb38be0a533e7b9c7d3b8e9b5c8a6fa5f6b349Evan Cheng LiveRange LR(defIndex, killIdx, ValNo); 2441a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos interval.addRange(LR); 2458a34229dcf484739119857988772572ef0cad9f2David Greene DEBUG(dbgs() << " +" << LR << "\n"); 2461a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos return; 2471a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos } 2481a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos } 2496097d13b2a624048dbe02e39e2dfb23bfa269b64Chris Lattner 2501a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // The other case we handle is when a virtual register lives to the end 2511a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // of the defining block, potentially live across some blocks, then is 2521a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // live into some number of blocks, but gets killed. Start by adding a 2531a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // range that goes from this definition to the end of the defining block. 25474ab5eeffbd70f2387338e3ee8195be9f73e6dd8Lang Hames LiveRange NewLR(defIndex, getMBBEndIdx(mbb), ValNo); 2558a34229dcf484739119857988772572ef0cad9f2David Greene DEBUG(dbgs() << " +" << NewLR); 2561a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos interval.addRange(NewLR); 2571a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos 258dcfe5f30b5e262971f601a65bebcc0367fef56c5Jakob Stoklund Olesen bool PHIJoin = lv_->isPHIJoin(interval.reg); 259dcfe5f30b5e262971f601a65bebcc0367fef56c5Jakob Stoklund Olesen 260dcfe5f30b5e262971f601a65bebcc0367fef56c5Jakob Stoklund Olesen if (PHIJoin) { 261dcfe5f30b5e262971f601a65bebcc0367fef56c5Jakob Stoklund Olesen // A phi join register is killed at the end of the MBB and revived as a new 262dcfe5f30b5e262971f601a65bebcc0367fef56c5Jakob Stoklund Olesen // valno in the killing blocks. 263dcfe5f30b5e262971f601a65bebcc0367fef56c5Jakob Stoklund Olesen assert(vi.AliveBlocks.empty() && "Phi join can't pass through blocks"); 264dcfe5f30b5e262971f601a65bebcc0367fef56c5Jakob Stoklund Olesen DEBUG(dbgs() << " phi-join"); 265dcfe5f30b5e262971f601a65bebcc0367fef56c5Jakob Stoklund Olesen ValNo->setHasPHIKill(true); 266dcfe5f30b5e262971f601a65bebcc0367fef56c5Jakob Stoklund Olesen } else { 267dcfe5f30b5e262971f601a65bebcc0367fef56c5Jakob Stoklund Olesen // Iterate over all of the blocks that the variable is completely 268dcfe5f30b5e262971f601a65bebcc0367fef56c5Jakob Stoklund Olesen // live in, adding [insrtIndex(begin), instrIndex(end)+4) to the 269dcfe5f30b5e262971f601a65bebcc0367fef56c5Jakob Stoklund Olesen // live interval. 270dcfe5f30b5e262971f601a65bebcc0367fef56c5Jakob Stoklund Olesen for (SparseBitVector<>::iterator I = vi.AliveBlocks.begin(), 271dcfe5f30b5e262971f601a65bebcc0367fef56c5Jakob Stoklund Olesen E = vi.AliveBlocks.end(); I != E; ++I) { 272dcfe5f30b5e262971f601a65bebcc0367fef56c5Jakob Stoklund Olesen MachineBasicBlock *aliveBlock = mf_->getBlockNumbered(*I); 273dcfe5f30b5e262971f601a65bebcc0367fef56c5Jakob Stoklund Olesen LiveRange LR(getMBBStartIdx(aliveBlock), getMBBEndIdx(aliveBlock), ValNo); 274dcfe5f30b5e262971f601a65bebcc0367fef56c5Jakob Stoklund Olesen interval.addRange(LR); 275dcfe5f30b5e262971f601a65bebcc0367fef56c5Jakob Stoklund Olesen DEBUG(dbgs() << " +" << LR); 276dcfe5f30b5e262971f601a65bebcc0367fef56c5Jakob Stoklund Olesen } 2771a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos } 2781a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos 2791a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // Finally, this virtual register is live from the start of any killing 2801a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // block to the 'use' slot of the killing instruction. 2811a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos for (unsigned i = 0, e = vi.Kills.size(); i != e; ++i) { 2821a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos MachineInstr *Kill = vi.Kills[i]; 283dcfe5f30b5e262971f601a65bebcc0367fef56c5Jakob Stoklund Olesen SlotIndex Start = getMBBStartIdx(Kill->getParent()); 2842debd48ca790ac01be6e12e094fdf4fdcadc8364Jakob Stoklund Olesen SlotIndex killIdx = getInstructionIndex(Kill).getRegSlot(); 285dcfe5f30b5e262971f601a65bebcc0367fef56c5Jakob Stoklund Olesen 286dcfe5f30b5e262971f601a65bebcc0367fef56c5Jakob Stoklund Olesen // Create interval with one of a NEW value number. Note that this value 287dcfe5f30b5e262971f601a65bebcc0367fef56c5Jakob Stoklund Olesen // number isn't actually defined by an instruction, weird huh? :) 288dcfe5f30b5e262971f601a65bebcc0367fef56c5Jakob Stoklund Olesen if (PHIJoin) { 2896e2968c85c1e162ee5bc813769eab223e3df0f15Lang Hames assert(getInstructionFromIndex(Start) == 0 && 2906e2968c85c1e162ee5bc813769eab223e3df0f15Lang Hames "PHI def index points at actual instruction."); 2916e2968c85c1e162ee5bc813769eab223e3df0f15Lang Hames ValNo = interval.getNextValue(Start, 0, VNInfoAllocator); 292dcfe5f30b5e262971f601a65bebcc0367fef56c5Jakob Stoklund Olesen ValNo->setIsPHIDef(true); 293dcfe5f30b5e262971f601a65bebcc0367fef56c5Jakob Stoklund Olesen } 294dcfe5f30b5e262971f601a65bebcc0367fef56c5Jakob Stoklund Olesen LiveRange LR(Start, killIdx, ValNo); 2951a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos interval.addRange(LR); 2968a34229dcf484739119857988772572ef0cad9f2David Greene DEBUG(dbgs() << " +" << LR); 2971a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos } 2981a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos 2991a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos } else { 3003749943648772743c9c0e852553e50e6700a0c1bEvan Cheng if (MultipleDefsBySameMI(*mi, MOIdx)) 301761fd4c1d97977c16de9f0cf921056a37b906304Nick Lewycky // Multiple defs of the same virtual register by the same instruction. 302761fd4c1d97977c16de9f0cf921056a37b906304Nick Lewycky // e.g. %reg1031:5<def>, %reg1031:6<def> = VLD1q16 %reg1024<kill>, ... 303afff40a62da19be15295c0f8ed5d4d450ccb45a5Evan Cheng // This is likely due to elimination of REG_SEQUENCE instructions. Return 304afff40a62da19be15295c0f8ed5d4d450ccb45a5Evan Cheng // here since there is nothing to do. 305afff40a62da19be15295c0f8ed5d4d450ccb45a5Evan Cheng return; 306afff40a62da19be15295c0f8ed5d4d450ccb45a5Evan Cheng 3071a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // If this is the second time we see a virtual register definition, it 3081a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // must be due to phi elimination or two addr elimination. If this is 309bf105c842450d3308d024be203ddd533f37051ecEvan Cheng // the result of two address elimination, then the vreg is one of the 310bf105c842450d3308d024be203ddd533f37051ecEvan Cheng // def-and-use register operand. 3113749943648772743c9c0e852553e50e6700a0c1bEvan Cheng 3123749943648772743c9c0e852553e50e6700a0c1bEvan Cheng // It may also be partial redef like this: 3131b2932024f098a6968645ac78d5848951d877c19Jakob Stoklund Olesen // 80 %reg1041:6<def> = VSHRNv4i16 %reg1034<kill>, 12, pred:14, pred:%reg0 3141b2932024f098a6968645ac78d5848951d877c19Jakob Stoklund Olesen // 120 %reg1041:5<def> = VSHRNv4i16 %reg1039<kill>, 12, pred:14, pred:%reg0 3153749943648772743c9c0e852553e50e6700a0c1bEvan Cheng bool PartReDef = isPartialRedef(MIIdx, MO, interval); 3163749943648772743c9c0e852553e50e6700a0c1bEvan Cheng if (PartReDef || mi->isRegTiedToUseOperand(MOIdx)) { 3171a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // If this is a two-address definition, then we have already processed 3181a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // the live range. The only problem is that we didn't realize there 3191a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // are actually two values in the live interval. Because of this we 3201a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // need to take the LiveRegion that defines this register and split it 3211a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // into two values. 322d14614e6777771f8fec3062bcaf2986c189ac84dJakob Stoklund Olesen SlotIndex RedefIndex = MIIdx.getRegSlot(MO.isEarlyClobber()); 3231a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos 32435f291d2c5f80e8e713704190230064311bbbbbeLang Hames const LiveRange *OldLR = 3252debd48ca790ac01be6e12e094fdf4fdcadc8364Jakob Stoklund Olesen interval.getLiveRangeContaining(RedefIndex.getRegSlot(true)); 3267ecb38be0a533e7b9c7d3b8e9b5c8a6fa5f6b349Evan Cheng VNInfo *OldValNo = OldLR->valno; 3272debd48ca790ac01be6e12e094fdf4fdcadc8364Jakob Stoklund Olesen SlotIndex DefIndex = OldValNo->def.getRegSlot(); 3284f8ff168de12eabdeb4b9437bf9402489ecf85cbEvan Cheng 329c66d0f2a9386cc7cb3237b8e3cace2b62a9c7dc8Jakob Stoklund Olesen // Delete the previous value, which should be short and continuous, 330be4f88a8b8bb3311e0dc4cde8533763d7923c3eaChris Lattner // because the 2-addr copy must be in the same MBB as the redef. 3311a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos interval.removeRange(DefIndex, RedefIndex); 332706515727c6d024015fffded2b3109a4f0ac5299Alkis Evlogimenos 33391725b75852443923b419fd23215194cfc65dd88Chris Lattner // The new value number (#1) is defined by the instruction we claimed 33491725b75852443923b419fd23215194cfc65dd88Chris Lattner // defined value #0. 3356e2968c85c1e162ee5bc813769eab223e3df0f15Lang Hames VNInfo *ValNo = interval.createValueCopy(OldValNo, VNInfoAllocator); 336857c4e01f85601cf2084adb860616256ee47c177Lang Hames 33791725b75852443923b419fd23215194cfc65dd88Chris Lattner // Value#0 is now defined by the 2-addr instruction. 338c8d044e4f779fdcfc5e7d592927740fd8f672a70Evan Cheng OldValNo->def = RedefIndex; 339ad6c5a20ba87e7aba91ef7e8b270715a25379770Evan Cheng OldValNo->setCopy(0); 340ad6c5a20ba87e7aba91ef7e8b270715a25379770Evan Cheng 341ad6c5a20ba87e7aba91ef7e8b270715a25379770Evan Cheng // A re-def may be a copy. e.g. %reg1030:6<def> = VMOVD %reg1026, ... 34204c528a0c86ddf3d6a70681f72e1b2ec07b0b53aJakob Stoklund Olesen if (PartReDef && mi->isCopyLike()) 343ad6c5a20ba87e7aba91ef7e8b270715a25379770Evan Cheng OldValNo->setCopy(&*mi); 3441b2932024f098a6968645ac78d5848951d877c19Jakob Stoklund Olesen 345be4f88a8b8bb3311e0dc4cde8533763d7923c3eaChris Lattner // Add the new live interval which replaces the range for the input copy. 346be4f88a8b8bb3311e0dc4cde8533763d7923c3eaChris Lattner LiveRange LR(DefIndex, RedefIndex, ValNo); 3478a34229dcf484739119857988772572ef0cad9f2David Greene DEBUG(dbgs() << " replace range with " << LR); 3481a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos interval.addRange(LR); 3491a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos 3501a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // If this redefinition is dead, we need to add a dummy unit live 3511a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // range covering the def slot. 3526b098dee286cc6fe5a5a476464d92dec5602e406Owen Anderson if (MO.isDead()) 3532debd48ca790ac01be6e12e094fdf4fdcadc8364Jakob Stoklund Olesen interval.addRange(LiveRange(RedefIndex, RedefIndex.getDeadSlot(), 354233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames OldValNo)); 3551a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos 3568e6179fb134af929ee7c937c82d9dc1c9a104c5fBill Wendling DEBUG({ 3578a34229dcf484739119857988772572ef0cad9f2David Greene dbgs() << " RESULT: "; 3588a34229dcf484739119857988772572ef0cad9f2David Greene interval.print(dbgs(), tri_); 3598e6179fb134af929ee7c937c82d9dc1c9a104c5fBill Wendling }); 3603749943648772743c9c0e852553e50e6700a0c1bEvan Cheng } else if (lv_->isPHIJoin(interval.reg)) { 3611a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // In the case of PHI elimination, each variable definition is only 3621a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // live until the end of the block. We've already taken care of the 3631a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // rest of the live range. 364dcfe5f30b5e262971f601a65bebcc0367fef56c5Jakob Stoklund Olesen 3652debd48ca790ac01be6e12e094fdf4fdcadc8364Jakob Stoklund Olesen SlotIndex defIndex = MIIdx.getRegSlot(); 366fb11288109329cb736d9f49769581a0d0c23fe19Evan Cheng if (MO.isEarlyClobber()) 3672debd48ca790ac01be6e12e094fdf4fdcadc8364Jakob Stoklund Olesen defIndex = MIIdx.getRegSlot(true); 368752195e3c662c6b5db042cf897c984624720f3b8Evan Cheng 3697ecb38be0a533e7b9c7d3b8e9b5c8a6fa5f6b349Evan Cheng VNInfo *ValNo; 370c8d044e4f779fdcfc5e7d592927740fd8f672a70Evan Cheng MachineInstr *CopyMI = NULL; 37104c528a0c86ddf3d6a70681f72e1b2ec07b0b53aJakob Stoklund Olesen if (mi->isCopyLike()) 372c8d044e4f779fdcfc5e7d592927740fd8f672a70Evan Cheng CopyMI = mi; 3736e2968c85c1e162ee5bc813769eab223e3df0f15Lang Hames ValNo = interval.getNextValue(defIndex, CopyMI, VNInfoAllocator); 3741b2932024f098a6968645ac78d5848951d877c19Jakob Stoklund Olesen 37574ab5eeffbd70f2387338e3ee8195be9f73e6dd8Lang Hames SlotIndex killIndex = getMBBEndIdx(mbb); 3767ecb38be0a533e7b9c7d3b8e9b5c8a6fa5f6b349Evan Cheng LiveRange LR(defIndex, killIndex, ValNo); 3771a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos interval.addRange(LR); 378857c4e01f85601cf2084adb860616256ee47c177Lang Hames ValNo->setHasPHIKill(true); 379dcfe5f30b5e262971f601a65bebcc0367fef56c5Jakob Stoklund Olesen DEBUG(dbgs() << " phi-join +" << LR); 3803749943648772743c9c0e852553e50e6700a0c1bEvan Cheng } else { 3813749943648772743c9c0e852553e50e6700a0c1bEvan Cheng llvm_unreachable("Multiply defined register"); 382dd2cc65f34f9b7bfda1cd0c42becedfc361d46f8Alkis Evlogimenos } 3831a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos } 384ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos 3858a34229dcf484739119857988772572ef0cad9f2David Greene DEBUG(dbgs() << '\n'); 386ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos} 387ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos 388f35fef7060c465dd7b578bf6339a18e8a8911888Chris Lattnervoid LiveIntervals::handlePhysicalRegisterDef(MachineBasicBlock *MBB, 389ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos MachineBasicBlock::iterator mi, 390233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames SlotIndex MIIdx, 3916b098dee286cc6fe5a5a476464d92dec5602e406Owen Anderson MachineOperand& MO, 39291725b75852443923b419fd23215194cfc65dd88Chris Lattner LiveInterval &interval, 393c8d044e4f779fdcfc5e7d592927740fd8f672a70Evan Cheng MachineInstr *CopyMI) { 3941a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // A physical register cannot be live across basic block, so its 3951a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // lifetime must end somewhere in its defining basic block. 3964314268128be6d54c9a7f0709680e5a5b40f3ab3Jakob Stoklund Olesen DEBUG(dbgs() << "\t\tregister: " << PrintReg(interval.reg, tri_)); 3971a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos 398233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames SlotIndex baseIndex = MIIdx; 399d14614e6777771f8fec3062bcaf2986c189ac84dJakob Stoklund Olesen SlotIndex start = baseIndex.getRegSlot(MO.isEarlyClobber()); 400233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames SlotIndex end = start; 4011a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos 4021a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // If it is not used after definition, it is considered dead at 4031a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // the instruction defining it. Hence its interval is: 4041a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // [defSlot(def), defSlot(def)+1) 40539faac2531268b8555475796c6071556670dc290Dale Johannesen // For earlyclobbers, the defSlot was pushed back one; the extra 40639faac2531268b8555475796c6071556670dc290Dale Johannesen // advance below compensates. 4076b098dee286cc6fe5a5a476464d92dec5602e406Owen Anderson if (MO.isDead()) { 4088a34229dcf484739119857988772572ef0cad9f2David Greene DEBUG(dbgs() << " dead"); 4092debd48ca790ac01be6e12e094fdf4fdcadc8364Jakob Stoklund Olesen end = start.getDeadSlot(); 410ab4b66d4c279e8cd9e448687020fc838e7881dbcChris Lattner goto exit; 4111a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos } 412ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos 4131a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // If it is not dead on definition, it must be killed by a 4141a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // subsequent instruction. Hence its interval is: 4151a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // [defSlot(def), useSlot(kill)+1) 416233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames baseIndex = baseIndex.getNextIndex(); 4175ab6f5fe666d0e3403d9b777324d1a1999118153Chris Lattner while (++mi != MBB->end()) { 418233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames 419bd63520161629385ff5a0b037eccc770d8d15289Dale Johannesen if (mi->isDebugValue()) 420bd63520161629385ff5a0b037eccc770d8d15289Dale Johannesen continue; 421233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames if (getInstructionFromIndex(baseIndex) == 0) 422233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames baseIndex = indexes_->getNextNonNullIndex(baseIndex); 423233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames 4246130f66eaae89f8878590796977678afa8448926Evan Cheng if (mi->killsRegister(interval.reg, tri_)) { 4258a34229dcf484739119857988772572ef0cad9f2David Greene DEBUG(dbgs() << " killed"); 4262debd48ca790ac01be6e12e094fdf4fdcadc8364Jakob Stoklund Olesen end = baseIndex.getRegSlot(); 427ab4b66d4c279e8cd9e448687020fc838e7881dbcChris Lattner goto exit; 428c45288e06bfe7d0b0e74eff350d280fa6c944373Evan Cheng } else { 4291015ba7018c87f48cc7bb45a564eb4a27241e76aEvan Cheng int DefIdx = mi->findRegisterDefOperandIdx(interval.reg,false,false,tri_); 430c45288e06bfe7d0b0e74eff350d280fa6c944373Evan Cheng if (DefIdx != -1) { 431c45288e06bfe7d0b0e74eff350d280fa6c944373Evan Cheng if (mi->isRegTiedToUseOperand(DefIdx)) { 432c45288e06bfe7d0b0e74eff350d280fa6c944373Evan Cheng // Two-address instruction. 4332debd48ca790ac01be6e12e094fdf4fdcadc8364Jakob Stoklund Olesen end = baseIndex.getRegSlot(); 434c45288e06bfe7d0b0e74eff350d280fa6c944373Evan Cheng } else { 435c45288e06bfe7d0b0e74eff350d280fa6c944373Evan Cheng // Another instruction redefines the register before it is ever read. 436bd63520161629385ff5a0b037eccc770d8d15289Dale Johannesen // Then the register is essentially dead at the instruction that 437bd63520161629385ff5a0b037eccc770d8d15289Dale Johannesen // defines it. Hence its interval is: 438c45288e06bfe7d0b0e74eff350d280fa6c944373Evan Cheng // [defSlot(def), defSlot(def)+1) 4398a34229dcf484739119857988772572ef0cad9f2David Greene DEBUG(dbgs() << " dead"); 4402debd48ca790ac01be6e12e094fdf4fdcadc8364Jakob Stoklund Olesen end = start.getDeadSlot(); 441c45288e06bfe7d0b0e74eff350d280fa6c944373Evan Cheng } 442c45288e06bfe7d0b0e74eff350d280fa6c944373Evan Cheng goto exit; 443c45288e06bfe7d0b0e74eff350d280fa6c944373Evan Cheng } 444f35fef7060c465dd7b578bf6339a18e8a8911888Chris Lattner } 4451b2932024f098a6968645ac78d5848951d877c19Jakob Stoklund Olesen 446233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames baseIndex = baseIndex.getNextIndex(); 4471a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos } 4481b2932024f098a6968645ac78d5848951d877c19Jakob Stoklund Olesen 4495ab6f5fe666d0e3403d9b777324d1a1999118153Chris Lattner // The only case we should have a dead physreg here without a killing or 4505ab6f5fe666d0e3403d9b777324d1a1999118153Chris Lattner // instruction where we know it's dead is if it is live-in to the function 451d521bc983b32da71b85d42dd30da87079afa5728Evan Cheng // and never used. Another possible case is the implicit use of the 452d521bc983b32da71b85d42dd30da87079afa5728Evan Cheng // physical register has been deleted by two-address pass. 4532debd48ca790ac01be6e12e094fdf4fdcadc8364Jakob Stoklund Olesen end = start.getDeadSlot(); 45402ba13c9897ae2b19f9201e57460d7ee2b753a0bAlkis Evlogimenos 455ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenosexit: 4561a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos assert(start < end && "did not find end of interval?"); 457f768bba43f5c036039851d2fcca8212edca18467Chris Lattner 45824a3cc4c83e5edb25fadf7b8979a26b4451795c6Evan Cheng // Already exists? Extend old live interval. 45931cc3ec3308c8fafd9865388214ae11662a71af4Jakob Stoklund Olesen VNInfo *ValNo = interval.getVNInfoAt(start); 46031cc3ec3308c8fafd9865388214ae11662a71af4Jakob Stoklund Olesen bool Extend = ValNo != 0; 46131cc3ec3308c8fafd9865388214ae11662a71af4Jakob Stoklund Olesen if (!Extend) 46231cc3ec3308c8fafd9865388214ae11662a71af4Jakob Stoklund Olesen ValNo = interval.getNextValue(start, CopyMI, VNInfoAllocator); 46331cc3ec3308c8fafd9865388214ae11662a71af4Jakob Stoklund Olesen if (Extend && MO.isEarlyClobber()) 464857c4e01f85601cf2084adb860616256ee47c177Lang Hames ValNo->setHasRedefByEC(true); 4657ecb38be0a533e7b9c7d3b8e9b5c8a6fa5f6b349Evan Cheng LiveRange LR(start, end, ValNo); 4661a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos interval.addRange(LR); 4678a34229dcf484739119857988772572ef0cad9f2David Greene DEBUG(dbgs() << " +" << LR << '\n'); 468ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos} 469ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos 470f35fef7060c465dd7b578bf6339a18e8a8911888Chris Lattnervoid LiveIntervals::handleRegisterDef(MachineBasicBlock *MBB, 471f35fef7060c465dd7b578bf6339a18e8a8911888Chris Lattner MachineBasicBlock::iterator MI, 472233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames SlotIndex MIIdx, 473ef0732d25a9882c947984ae3f2afbef5463ba00fEvan Cheng MachineOperand& MO, 474ef0732d25a9882c947984ae3f2afbef5463ba00fEvan Cheng unsigned MOIdx) { 4756b098dee286cc6fe5a5a476464d92dec5602e406Owen Anderson if (TargetRegisterInfo::isVirtualRegister(MO.getReg())) 476ef0732d25a9882c947984ae3f2afbef5463ba00fEvan Cheng handleVirtualRegisterDef(MBB, MI, MIIdx, MO, MOIdx, 4776b098dee286cc6fe5a5a476464d92dec5602e406Owen Anderson getOrCreateInterval(MO.getReg())); 4784662a9f270fe2c916c35545718720ed181384c30Jakob Stoklund Olesen else { 479c8d044e4f779fdcfc5e7d592927740fd8f672a70Evan Cheng MachineInstr *CopyMI = NULL; 48004c528a0c86ddf3d6a70681f72e1b2ec07b0b53aJakob Stoklund Olesen if (MI->isCopyLike()) 481c8d044e4f779fdcfc5e7d592927740fd8f672a70Evan Cheng CopyMI = MI; 482c45288e06bfe7d0b0e74eff350d280fa6c944373Evan Cheng handlePhysicalRegisterDef(MBB, MI, MIIdx, MO, 4836b098dee286cc6fe5a5a476464d92dec5602e406Owen Anderson getOrCreateInterval(MO.getReg()), CopyMI); 484f35fef7060c465dd7b578bf6339a18e8a8911888Chris Lattner } 4854d46e1e521c0df1990ea50f8146d22bd77ea71a6Alkis Evlogimenos} 4864d46e1e521c0df1990ea50f8146d22bd77ea71a6Alkis Evlogimenos 487b371f457b0ea4a652a9f526ba4375c80ae542252Evan Chengvoid LiveIntervals::handleLiveInRegister(MachineBasicBlock *MBB, 488233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames SlotIndex MIIdx, 48924a3cc4c83e5edb25fadf7b8979a26b4451795c6Evan Cheng LiveInterval &interval, bool isAlias) { 4904314268128be6d54c9a7f0709680e5a5b40f3ab3Jakob Stoklund Olesen DEBUG(dbgs() << "\t\tlivein register: " << PrintReg(interval.reg, tri_)); 491b371f457b0ea4a652a9f526ba4375c80ae542252Evan Cheng 492b371f457b0ea4a652a9f526ba4375c80ae542252Evan Cheng // Look for kills, if it reaches a def before it's killed, then it shouldn't 493b371f457b0ea4a652a9f526ba4375c80ae542252Evan Cheng // be considered a livein. 494b371f457b0ea4a652a9f526ba4375c80ae542252Evan Cheng MachineBasicBlock::iterator mi = MBB->begin(); 4954507f089d48c5adb454cd12b68333d5590ce05ddEvan Cheng MachineBasicBlock::iterator E = MBB->end(); 4964507f089d48c5adb454cd12b68333d5590ce05ddEvan Cheng // Skip over DBG_VALUE at the start of the MBB. 4974507f089d48c5adb454cd12b68333d5590ce05ddEvan Cheng if (mi != E && mi->isDebugValue()) { 4984507f089d48c5adb454cd12b68333d5590ce05ddEvan Cheng while (++mi != E && mi->isDebugValue()) 4994507f089d48c5adb454cd12b68333d5590ce05ddEvan Cheng ; 5004507f089d48c5adb454cd12b68333d5590ce05ddEvan Cheng if (mi == E) 5014507f089d48c5adb454cd12b68333d5590ce05ddEvan Cheng // MBB is empty except for DBG_VALUE's. 5024507f089d48c5adb454cd12b68333d5590ce05ddEvan Cheng return; 5034507f089d48c5adb454cd12b68333d5590ce05ddEvan Cheng } 5044507f089d48c5adb454cd12b68333d5590ce05ddEvan Cheng 505233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames SlotIndex baseIndex = MIIdx; 506233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames SlotIndex start = baseIndex; 507233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames if (getInstructionFromIndex(baseIndex) == 0) 508233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames baseIndex = indexes_->getNextNonNullIndex(baseIndex); 509233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames 510233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames SlotIndex end = baseIndex; 5110076c616e8abc2ecf36600a7ac20ec784420cdc4Evan Cheng bool SeenDefUse = false; 512b371f457b0ea4a652a9f526ba4375c80ae542252Evan Cheng 513bd63520161629385ff5a0b037eccc770d8d15289Dale Johannesen while (mi != E) { 5141d0aeabe3fce2ce6610e988b36582b47a7684f74Dale Johannesen if (mi->killsRegister(interval.reg, tri_)) { 5151d0aeabe3fce2ce6610e988b36582b47a7684f74Dale Johannesen DEBUG(dbgs() << " killed"); 5162debd48ca790ac01be6e12e094fdf4fdcadc8364Jakob Stoklund Olesen end = baseIndex.getRegSlot(); 5171d0aeabe3fce2ce6610e988b36582b47a7684f74Dale Johannesen SeenDefUse = true; 5181d0aeabe3fce2ce6610e988b36582b47a7684f74Dale Johannesen break; 5191015ba7018c87f48cc7bb45a564eb4a27241e76aEvan Cheng } else if (mi->definesRegister(interval.reg, tri_)) { 5201d0aeabe3fce2ce6610e988b36582b47a7684f74Dale Johannesen // Another instruction redefines the register before it is ever read. 5211d0aeabe3fce2ce6610e988b36582b47a7684f74Dale Johannesen // Then the register is essentially dead at the instruction that defines 5221d0aeabe3fce2ce6610e988b36582b47a7684f74Dale Johannesen // it. Hence its interval is: 5231d0aeabe3fce2ce6610e988b36582b47a7684f74Dale Johannesen // [defSlot(def), defSlot(def)+1) 5241d0aeabe3fce2ce6610e988b36582b47a7684f74Dale Johannesen DEBUG(dbgs() << " dead"); 5252debd48ca790ac01be6e12e094fdf4fdcadc8364Jakob Stoklund Olesen end = start.getDeadSlot(); 5261d0aeabe3fce2ce6610e988b36582b47a7684f74Dale Johannesen SeenDefUse = true; 5271d0aeabe3fce2ce6610e988b36582b47a7684f74Dale Johannesen break; 528bd63520161629385ff5a0b037eccc770d8d15289Dale Johannesen } 5291d0aeabe3fce2ce6610e988b36582b47a7684f74Dale Johannesen 5304507f089d48c5adb454cd12b68333d5590ce05ddEvan Cheng while (++mi != E && mi->isDebugValue()) 5314507f089d48c5adb454cd12b68333d5590ce05ddEvan Cheng // Skip over DBG_VALUE. 5324507f089d48c5adb454cd12b68333d5590ce05ddEvan Cheng ; 5334507f089d48c5adb454cd12b68333d5590ce05ddEvan Cheng if (mi != E) 534233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames baseIndex = indexes_->getNextNonNullIndex(baseIndex); 535b371f457b0ea4a652a9f526ba4375c80ae542252Evan Cheng } 536b371f457b0ea4a652a9f526ba4375c80ae542252Evan Cheng 53775611fb4e6ab253be30ac29a2b15e9bf8c1d146eEvan Cheng // Live-in register might not be used at all. 5380076c616e8abc2ecf36600a7ac20ec784420cdc4Evan Cheng if (!SeenDefUse) { 539292da949f6c87d6499425d64d37d7c5870ec57adEvan Cheng if (isAlias) { 5408a34229dcf484739119857988772572ef0cad9f2David Greene DEBUG(dbgs() << " dead"); 5412debd48ca790ac01be6e12e094fdf4fdcadc8364Jakob Stoklund Olesen end = MIIdx.getDeadSlot(); 542292da949f6c87d6499425d64d37d7c5870ec57adEvan Cheng } else { 5438a34229dcf484739119857988772572ef0cad9f2David Greene DEBUG(dbgs() << " live through"); 544ec7e4fff960f166be8a8a39b7ba8cc7baac6b02cJakob Stoklund Olesen end = getMBBEndIdx(MBB); 545292da949f6c87d6499425d64d37d7c5870ec57adEvan Cheng } 54624a3cc4c83e5edb25fadf7b8979a26b4451795c6Evan Cheng } 54724a3cc4c83e5edb25fadf7b8979a26b4451795c6Evan Cheng 5486e2968c85c1e162ee5bc813769eab223e3df0f15Lang Hames SlotIndex defIdx = getMBBStartIdx(MBB); 5496e2968c85c1e162ee5bc813769eab223e3df0f15Lang Hames assert(getInstructionFromIndex(defIdx) == 0 && 5506e2968c85c1e162ee5bc813769eab223e3df0f15Lang Hames "PHI def index points at actual instruction."); 55110382fb71d8306f320ecbeb7049d25354c0e5457Lang Hames VNInfo *vni = 5526e2968c85c1e162ee5bc813769eab223e3df0f15Lang Hames interval.getNextValue(defIdx, 0, VNInfoAllocator); 553d21c31610c4a10e9e638f4221b5df89ea932e258Lang Hames vni->setIsPHIDef(true); 554d21c31610c4a10e9e638f4221b5df89ea932e258Lang Hames LiveRange LR(start, end, vni); 5553de23e6f6cf337451a0934159da494d645b93133Jakob Stoklund Olesen 5569b25b8ca24d6df2e097741dcc15016772ee4eda7Jim Laskey interval.addRange(LR); 5578a34229dcf484739119857988772572ef0cad9f2David Greene DEBUG(dbgs() << " +" << LR << '\n'); 558b371f457b0ea4a652a9f526ba4375c80ae542252Evan Cheng} 559b371f457b0ea4a652a9f526ba4375c80ae542252Evan Cheng 560ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos/// computeIntervals - computes the live intervals for virtual 5614d46e1e521c0df1990ea50f8146d22bd77ea71a6Alkis Evlogimenos/// registers. for some ordering of the machine instructions [1,N] a 56208cec00588ec1a8fa85b208555f006d7396ae7a4Alkis Evlogimenos/// live interval is an interval [i, j) where 1 <= i <= j < N for 563ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos/// which a variable is live 5641b2932024f098a6968645ac78d5848951d877c19Jakob Stoklund Olesenvoid LiveIntervals::computeIntervals() { 5658a34229dcf484739119857988772572ef0cad9f2David Greene DEBUG(dbgs() << "********** COMPUTING LIVE INTERVALS **********\n" 5668e6179fb134af929ee7c937c82d9dc1c9a104c5fBill Wendling << "********** Function: " 5678e6179fb134af929ee7c937c82d9dc1c9a104c5fBill Wendling << ((Value*)mf_->getFunction())->getName() << '\n'); 568d129d73b725e32d2fc0c87f392c239db8801e922Evan Cheng 569d129d73b725e32d2fc0c87f392c239db8801e922Evan Cheng SmallVector<unsigned, 8> UndefUses; 570428b92eb83b457b71d29d1d4b7900d36a0ce9a53Chris Lattner for (MachineFunction::iterator MBBI = mf_->begin(), E = mf_->end(); 571428b92eb83b457b71d29d1d4b7900d36a0ce9a53Chris Lattner MBBI != E; ++MBBI) { 572428b92eb83b457b71d29d1d4b7900d36a0ce9a53Chris Lattner MachineBasicBlock *MBB = MBBI; 57300a99a35840451a291eb61a192a750908a4073aeEvan Cheng if (MBB->empty()) 57400a99a35840451a291eb61a192a750908a4073aeEvan Cheng continue; 57500a99a35840451a291eb61a192a750908a4073aeEvan Cheng 576134eb73fc35e6ead3cfd3ed5024d0d7efa507441Owen Anderson // Track the index of the current machine instr. 577233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames SlotIndex MIIndex = getMBBStartIdx(MBB); 578ad98f795d0dba3db721139a8a74a98acdce0ff60Bob Wilson DEBUG(dbgs() << "BB#" << MBB->getNumber() 579ad98f795d0dba3db721139a8a74a98acdce0ff60Bob Wilson << ":\t\t# derived from " << MBB->getName() << "\n"); 5801a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos 581cb406c25973b4e88a6c10ad839ef1beeb3664715Dan Gohman // Create intervals for live-ins to this BB first. 58281bf03eb5cd68243eabb52505105aa5f4a831bf3Dan Gohman for (MachineBasicBlock::livein_iterator LI = MBB->livein_begin(), 583cb406c25973b4e88a6c10ad839ef1beeb3664715Dan Gohman LE = MBB->livein_end(); LI != LE; ++LI) { 584cb406c25973b4e88a6c10ad839ef1beeb3664715Dan Gohman handleLiveInRegister(MBB, MIIndex, getOrCreateInterval(*LI)); 585cb406c25973b4e88a6c10ad839ef1beeb3664715Dan Gohman // Multiple live-ins can alias the same register. 5866f0d024a534af18d9e60b3ea757376cd8a3a980eDan Gohman for (const unsigned* AS = tri_->getSubRegisters(*LI); *AS; ++AS) 587cb406c25973b4e88a6c10ad839ef1beeb3664715Dan Gohman if (!hasInterval(*AS)) 588cb406c25973b4e88a6c10ad839ef1beeb3664715Dan Gohman handleLiveInRegister(MBB, MIIndex, getOrCreateInterval(*AS), 589cb406c25973b4e88a6c10ad839ef1beeb3664715Dan Gohman true); 590dffb2e83ed2546226d09c40aa43524e2392322daChris Lattner } 5911b2932024f098a6968645ac78d5848951d877c19Jakob Stoklund Olesen 59299500aeb7c9a05db57e228544a3f81de2faf24efOwen Anderson // Skip over empty initial indices. 593233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames if (getInstructionFromIndex(MIIndex) == 0) 594233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames MIIndex = indexes_->getNextNonNullIndex(MIIndex); 5951b2932024f098a6968645ac78d5848951d877c19Jakob Stoklund Olesen 5961caedd056dbc3eda1537ad8251323bd985819b80Dale Johannesen for (MachineBasicBlock::iterator MI = MBB->begin(), miEnd = MBB->end(); 5971caedd056dbc3eda1537ad8251323bd985819b80Dale Johannesen MI != miEnd; ++MI) { 5988a34229dcf484739119857988772572ef0cad9f2David Greene DEBUG(dbgs() << MIIndex << "\t" << *MI); 599518bb53485df640d7b7e3f6b0544099020c42aa7Chris Lattner if (MI->isDebugValue()) 6001caedd056dbc3eda1537ad8251323bd985819b80Dale Johannesen continue; 6011a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos 602438f7bc67cf235ccee7e6f7ac7f4ae2186eb8020Evan Cheng // Handle defs. 603428b92eb83b457b71d29d1d4b7900d36a0ce9a53Chris Lattner for (int i = MI->getNumOperands() - 1; i >= 0; --i) { 604428b92eb83b457b71d29d1d4b7900d36a0ce9a53Chris Lattner MachineOperand &MO = MI->getOperand(i); 605d129d73b725e32d2fc0c87f392c239db8801e922Evan Cheng if (!MO.isReg() || !MO.getReg()) 606d129d73b725e32d2fc0c87f392c239db8801e922Evan Cheng continue; 607d129d73b725e32d2fc0c87f392c239db8801e922Evan Cheng 6081a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // handle register defs - build intervals 609d129d73b725e32d2fc0c87f392c239db8801e922Evan Cheng if (MO.isDef()) 610ef0732d25a9882c947984ae3f2afbef5463ba00fEvan Cheng handleRegisterDef(MBB, MI, MIIndex, MO, i); 611d129d73b725e32d2fc0c87f392c239db8801e922Evan Cheng else if (MO.isUndef()) 612d129d73b725e32d2fc0c87f392c239db8801e922Evan Cheng UndefUses.push_back(MO.getReg()); 6131a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos } 6141b2932024f098a6968645ac78d5848951d877c19Jakob Stoklund Olesen 615233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames // Move to the next instr slot. 616233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames MIIndex = indexes_->getNextNonNullIndex(MIIndex); 617ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos } 6181a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos } 619d129d73b725e32d2fc0c87f392c239db8801e922Evan Cheng 620d129d73b725e32d2fc0c87f392c239db8801e922Evan Cheng // Create empty intervals for registers defined by implicit_def's (except 621d129d73b725e32d2fc0c87f392c239db8801e922Evan Cheng // for those implicit_def that define values which are liveout of their 622d129d73b725e32d2fc0c87f392c239db8801e922Evan Cheng // blocks. 623d129d73b725e32d2fc0c87f392c239db8801e922Evan Cheng for (unsigned i = 0, e = UndefUses.size(); i != e; ++i) { 624d129d73b725e32d2fc0c87f392c239db8801e922Evan Cheng unsigned UndefReg = UndefUses[i]; 625d129d73b725e32d2fc0c87f392c239db8801e922Evan Cheng (void)getOrCreateInterval(UndefReg); 626d129d73b725e32d2fc0c87f392c239db8801e922Evan Cheng } 627ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos} 628b27ef248f579b354aab434f63c417ab1103e47e2Alkis Evlogimenos 62903857b29d8271a23943254579e6cf7b7df4b1bd3Owen AndersonLiveInterval* LiveIntervals::createInterval(unsigned reg) { 6300a1fcce09230e9b4bd30a8f07447aa075dce7470Evan Cheng float Weight = TargetRegisterInfo::isPhysicalRegister(reg) ? HUGE_VALF : 0.0F; 63103857b29d8271a23943254579e6cf7b7df4b1bd3Owen Anderson return new LiveInterval(reg, Weight); 6329a8b490735d216435862a3d52e669357f165550fAlkis Evlogimenos} 633f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng 6340a1fcce09230e9b4bd30a8f07447aa075dce7470Evan Cheng/// dupInterval - Duplicate a live interval. The caller is responsible for 6350a1fcce09230e9b4bd30a8f07447aa075dce7470Evan Cheng/// managing the allocated memory. 6360a1fcce09230e9b4bd30a8f07447aa075dce7470Evan ChengLiveInterval* LiveIntervals::dupInterval(LiveInterval *li) { 6370a1fcce09230e9b4bd30a8f07447aa075dce7470Evan Cheng LiveInterval *NewLI = createInterval(li->reg); 63890f95f88c6ce09c6744777dc9d140c3c77203b92Evan Cheng NewLI->Copy(*li, mri_, getVNInfoAllocator()); 6390a1fcce09230e9b4bd30a8f07447aa075dce7470Evan Cheng return NewLI; 6400a1fcce09230e9b4bd30a8f07447aa075dce7470Evan Cheng} 6410a1fcce09230e9b4bd30a8f07447aa075dce7470Evan Cheng 64211513e5d1e1b40e6113668e4b4357596f33fa6c6Jakob Stoklund Olesen/// shrinkToUses - After removing some uses of a register, shrink its live 64311513e5d1e1b40e6113668e4b4357596f33fa6c6Jakob Stoklund Olesen/// range to just the remaining uses. This method does not compute reaching 64411513e5d1e1b40e6113668e4b4357596f33fa6c6Jakob Stoklund Olesen/// defs for new uses, and it doesn't remove dead defs. 6456a3dbd3b25bbc99bd1a233d6a74ddea3493ba6acJakob Stoklund Olesenbool LiveIntervals::shrinkToUses(LiveInterval *li, 6460d8ccaa5c8db820b5b93f37e51563148c57ba6b8Jakob Stoklund Olesen SmallVectorImpl<MachineInstr*> *dead) { 64711513e5d1e1b40e6113668e4b4357596f33fa6c6Jakob Stoklund Olesen DEBUG(dbgs() << "Shrink: " << *li << '\n'); 64811513e5d1e1b40e6113668e4b4357596f33fa6c6Jakob Stoklund Olesen assert(TargetRegisterInfo::isVirtualRegister(li->reg) 649567cdbab28077ea1801ebff3d4291d4006d88ca3Lang Hames && "Can only shrink virtual registers"); 65011513e5d1e1b40e6113668e4b4357596f33fa6c6Jakob Stoklund Olesen // Find all the values used, including PHI kills. 65111513e5d1e1b40e6113668e4b4357596f33fa6c6Jakob Stoklund Olesen SmallVector<std::pair<SlotIndex, VNInfo*>, 16> WorkList; 65211513e5d1e1b40e6113668e4b4357596f33fa6c6Jakob Stoklund Olesen 653031432f9ad24963282b7f71bd0592080f6229d20Jakob Stoklund Olesen // Blocks that have already been added to WorkList as live-out. 654031432f9ad24963282b7f71bd0592080f6229d20Jakob Stoklund Olesen SmallPtrSet<MachineBasicBlock*, 16> LiveOut; 655031432f9ad24963282b7f71bd0592080f6229d20Jakob Stoklund Olesen 65611513e5d1e1b40e6113668e4b4357596f33fa6c6Jakob Stoklund Olesen // Visit all instructions reading li->reg. 65711513e5d1e1b40e6113668e4b4357596f33fa6c6Jakob Stoklund Olesen for (MachineRegisterInfo::reg_iterator I = mri_->reg_begin(li->reg); 65811513e5d1e1b40e6113668e4b4357596f33fa6c6Jakob Stoklund Olesen MachineInstr *UseMI = I.skipInstruction();) { 65911513e5d1e1b40e6113668e4b4357596f33fa6c6Jakob Stoklund Olesen if (UseMI->isDebugValue() || !UseMI->readsVirtualRegister(li->reg)) 66011513e5d1e1b40e6113668e4b4357596f33fa6c6Jakob Stoklund Olesen continue; 6616c9cc21d85cdef79b971f710ace287f3a2f847a3Jakob Stoklund Olesen SlotIndex Idx = getInstructionIndex(UseMI).getRegSlot(); 662f054e198197122011fc80b673f35333bc3e58c98Jakob Stoklund Olesen // Note: This intentionally picks up the wrong VNI in case of an EC redef. 663f054e198197122011fc80b673f35333bc3e58c98Jakob Stoklund Olesen // See below. 664f054e198197122011fc80b673f35333bc3e58c98Jakob Stoklund Olesen VNInfo *VNI = li->getVNInfoBefore(Idx); 6659ef931e71c06a0390d6387859843be1d6d4daad6Jakob Stoklund Olesen if (!VNI) { 6669ef931e71c06a0390d6387859843be1d6d4daad6Jakob Stoklund Olesen // This shouldn't happen: readsVirtualRegister returns true, but there is 6679ef931e71c06a0390d6387859843be1d6d4daad6Jakob Stoklund Olesen // no live value. It is likely caused by a target getting <undef> flags 6689ef931e71c06a0390d6387859843be1d6d4daad6Jakob Stoklund Olesen // wrong. 6699ef931e71c06a0390d6387859843be1d6d4daad6Jakob Stoklund Olesen DEBUG(dbgs() << Idx << '\t' << *UseMI 6709ef931e71c06a0390d6387859843be1d6d4daad6Jakob Stoklund Olesen << "Warning: Instr claims to read non-existent value in " 6719ef931e71c06a0390d6387859843be1d6d4daad6Jakob Stoklund Olesen << *li << '\n'); 6729ef931e71c06a0390d6387859843be1d6d4daad6Jakob Stoklund Olesen continue; 6739ef931e71c06a0390d6387859843be1d6d4daad6Jakob Stoklund Olesen } 674f054e198197122011fc80b673f35333bc3e58c98Jakob Stoklund Olesen // Special case: An early-clobber tied operand reads and writes the 675f054e198197122011fc80b673f35333bc3e58c98Jakob Stoklund Olesen // register one slot early. The getVNInfoBefore call above would have 676f054e198197122011fc80b673f35333bc3e58c98Jakob Stoklund Olesen // picked up the value defined by UseMI. Adjust the kill slot and value. 677f054e198197122011fc80b673f35333bc3e58c98Jakob Stoklund Olesen if (SlotIndex::isSameInstr(VNI->def, Idx)) { 678f054e198197122011fc80b673f35333bc3e58c98Jakob Stoklund Olesen Idx = VNI->def; 6796c9cc21d85cdef79b971f710ace287f3a2f847a3Jakob Stoklund Olesen VNI = li->getVNInfoBefore(Idx); 68011513e5d1e1b40e6113668e4b4357596f33fa6c6Jakob Stoklund Olesen assert(VNI && "Early-clobber tied value not available"); 68111513e5d1e1b40e6113668e4b4357596f33fa6c6Jakob Stoklund Olesen } 68211513e5d1e1b40e6113668e4b4357596f33fa6c6Jakob Stoklund Olesen WorkList.push_back(std::make_pair(Idx, VNI)); 68311513e5d1e1b40e6113668e4b4357596f33fa6c6Jakob Stoklund Olesen } 68411513e5d1e1b40e6113668e4b4357596f33fa6c6Jakob Stoklund Olesen 68511513e5d1e1b40e6113668e4b4357596f33fa6c6Jakob Stoklund Olesen // Create a new live interval with only minimal live segments per def. 68611513e5d1e1b40e6113668e4b4357596f33fa6c6Jakob Stoklund Olesen LiveInterval NewLI(li->reg, 0); 68711513e5d1e1b40e6113668e4b4357596f33fa6c6Jakob Stoklund Olesen for (LiveInterval::vni_iterator I = li->vni_begin(), E = li->vni_end(); 68811513e5d1e1b40e6113668e4b4357596f33fa6c6Jakob Stoklund Olesen I != E; ++I) { 68911513e5d1e1b40e6113668e4b4357596f33fa6c6Jakob Stoklund Olesen VNInfo *VNI = *I; 69011513e5d1e1b40e6113668e4b4357596f33fa6c6Jakob Stoklund Olesen if (VNI->isUnused()) 69111513e5d1e1b40e6113668e4b4357596f33fa6c6Jakob Stoklund Olesen continue; 6921f81e316b042c02c841801a71e7439e166ffa2a0Jakob Stoklund Olesen NewLI.addRange(LiveRange(VNI->def, VNI->def.getDeadSlot(), VNI)); 69311513e5d1e1b40e6113668e4b4357596f33fa6c6Jakob Stoklund Olesen } 69411513e5d1e1b40e6113668e4b4357596f33fa6c6Jakob Stoklund Olesen 695e0ab24532cc11f082d722ab169080322b39afeceJakob Stoklund Olesen // Keep track of the PHIs that are in use. 696e0ab24532cc11f082d722ab169080322b39afeceJakob Stoklund Olesen SmallPtrSet<VNInfo*, 8> UsedPHIs; 697e0ab24532cc11f082d722ab169080322b39afeceJakob Stoklund Olesen 69811513e5d1e1b40e6113668e4b4357596f33fa6c6Jakob Stoklund Olesen // Extend intervals to reach all uses in WorkList. 69911513e5d1e1b40e6113668e4b4357596f33fa6c6Jakob Stoklund Olesen while (!WorkList.empty()) { 70011513e5d1e1b40e6113668e4b4357596f33fa6c6Jakob Stoklund Olesen SlotIndex Idx = WorkList.back().first; 70111513e5d1e1b40e6113668e4b4357596f33fa6c6Jakob Stoklund Olesen VNInfo *VNI = WorkList.back().second; 70211513e5d1e1b40e6113668e4b4357596f33fa6c6Jakob Stoklund Olesen WorkList.pop_back(); 7036c9cc21d85cdef79b971f710ace287f3a2f847a3Jakob Stoklund Olesen const MachineBasicBlock *MBB = getMBBFromIndex(Idx.getPrevSlot()); 70411513e5d1e1b40e6113668e4b4357596f33fa6c6Jakob Stoklund Olesen SlotIndex BlockStart = getMBBStartIdx(MBB); 705e0ab24532cc11f082d722ab169080322b39afeceJakob Stoklund Olesen 706e0ab24532cc11f082d722ab169080322b39afeceJakob Stoklund Olesen // Extend the live range for VNI to be live at Idx. 7076c9cc21d85cdef79b971f710ace287f3a2f847a3Jakob Stoklund Olesen if (VNInfo *ExtVNI = NewLI.extendInBlock(BlockStart, Idx)) { 7084b11a70f7a63dc4c051a96a90ed6687eb0595cdaNick Lewycky (void)ExtVNI; 709e0ab24532cc11f082d722ab169080322b39afeceJakob Stoklund Olesen assert(ExtVNI == VNI && "Unexpected existing value number"); 710e0ab24532cc11f082d722ab169080322b39afeceJakob Stoklund Olesen // Is this a PHIDef we haven't seen before? 711c29d9b3495a2d87af524ad5c4b62f46c4265d828Jakob Stoklund Olesen if (!VNI->isPHIDef() || VNI->def != BlockStart || !UsedPHIs.insert(VNI)) 712e0ab24532cc11f082d722ab169080322b39afeceJakob Stoklund Olesen continue; 713e0ab24532cc11f082d722ab169080322b39afeceJakob Stoklund Olesen // The PHI is live, make sure the predecessors are live-out. 714e0ab24532cc11f082d722ab169080322b39afeceJakob Stoklund Olesen for (MachineBasicBlock::const_pred_iterator PI = MBB->pred_begin(), 715e0ab24532cc11f082d722ab169080322b39afeceJakob Stoklund Olesen PE = MBB->pred_end(); PI != PE; ++PI) { 716031432f9ad24963282b7f71bd0592080f6229d20Jakob Stoklund Olesen if (!LiveOut.insert(*PI)) 717031432f9ad24963282b7f71bd0592080f6229d20Jakob Stoklund Olesen continue; 7186c9cc21d85cdef79b971f710ace287f3a2f847a3Jakob Stoklund Olesen SlotIndex Stop = getMBBEndIdx(*PI); 719e0ab24532cc11f082d722ab169080322b39afeceJakob Stoklund Olesen // A predecessor is not required to have a live-out value for a PHI. 7206c9cc21d85cdef79b971f710ace287f3a2f847a3Jakob Stoklund Olesen if (VNInfo *PVNI = li->getVNInfoBefore(Stop)) 721e0ab24532cc11f082d722ab169080322b39afeceJakob Stoklund Olesen WorkList.push_back(std::make_pair(Stop, PVNI)); 72211513e5d1e1b40e6113668e4b4357596f33fa6c6Jakob Stoklund Olesen } 72311513e5d1e1b40e6113668e4b4357596f33fa6c6Jakob Stoklund Olesen continue; 72411513e5d1e1b40e6113668e4b4357596f33fa6c6Jakob Stoklund Olesen } 72511513e5d1e1b40e6113668e4b4357596f33fa6c6Jakob Stoklund Olesen 72611513e5d1e1b40e6113668e4b4357596f33fa6c6Jakob Stoklund Olesen // VNI is live-in to MBB. 72711513e5d1e1b40e6113668e4b4357596f33fa6c6Jakob Stoklund Olesen DEBUG(dbgs() << " live-in at " << BlockStart << '\n'); 7286c9cc21d85cdef79b971f710ace287f3a2f847a3Jakob Stoklund Olesen NewLI.addRange(LiveRange(BlockStart, Idx, VNI)); 72911513e5d1e1b40e6113668e4b4357596f33fa6c6Jakob Stoklund Olesen 73011513e5d1e1b40e6113668e4b4357596f33fa6c6Jakob Stoklund Olesen // Make sure VNI is live-out from the predecessors. 73111513e5d1e1b40e6113668e4b4357596f33fa6c6Jakob Stoklund Olesen for (MachineBasicBlock::const_pred_iterator PI = MBB->pred_begin(), 73211513e5d1e1b40e6113668e4b4357596f33fa6c6Jakob Stoklund Olesen PE = MBB->pred_end(); PI != PE; ++PI) { 733031432f9ad24963282b7f71bd0592080f6229d20Jakob Stoklund Olesen if (!LiveOut.insert(*PI)) 734031432f9ad24963282b7f71bd0592080f6229d20Jakob Stoklund Olesen continue; 7356c9cc21d85cdef79b971f710ace287f3a2f847a3Jakob Stoklund Olesen SlotIndex Stop = getMBBEndIdx(*PI); 7366c9cc21d85cdef79b971f710ace287f3a2f847a3Jakob Stoklund Olesen assert(li->getVNInfoBefore(Stop) == VNI && 7376c9cc21d85cdef79b971f710ace287f3a2f847a3Jakob Stoklund Olesen "Wrong value out of predecessor"); 73811513e5d1e1b40e6113668e4b4357596f33fa6c6Jakob Stoklund Olesen WorkList.push_back(std::make_pair(Stop, VNI)); 73911513e5d1e1b40e6113668e4b4357596f33fa6c6Jakob Stoklund Olesen } 74011513e5d1e1b40e6113668e4b4357596f33fa6c6Jakob Stoklund Olesen } 74111513e5d1e1b40e6113668e4b4357596f33fa6c6Jakob Stoklund Olesen 74211513e5d1e1b40e6113668e4b4357596f33fa6c6Jakob Stoklund Olesen // Handle dead values. 7436a3dbd3b25bbc99bd1a233d6a74ddea3493ba6acJakob Stoklund Olesen bool CanSeparate = false; 74411513e5d1e1b40e6113668e4b4357596f33fa6c6Jakob Stoklund Olesen for (LiveInterval::vni_iterator I = li->vni_begin(), E = li->vni_end(); 74511513e5d1e1b40e6113668e4b4357596f33fa6c6Jakob Stoklund Olesen I != E; ++I) { 74611513e5d1e1b40e6113668e4b4357596f33fa6c6Jakob Stoklund Olesen VNInfo *VNI = *I; 74711513e5d1e1b40e6113668e4b4357596f33fa6c6Jakob Stoklund Olesen if (VNI->isUnused()) 74811513e5d1e1b40e6113668e4b4357596f33fa6c6Jakob Stoklund Olesen continue; 74911513e5d1e1b40e6113668e4b4357596f33fa6c6Jakob Stoklund Olesen LiveInterval::iterator LII = NewLI.FindLiveRangeContaining(VNI->def); 75011513e5d1e1b40e6113668e4b4357596f33fa6c6Jakob Stoklund Olesen assert(LII != NewLI.end() && "Missing live range for PHI"); 7511f81e316b042c02c841801a71e7439e166ffa2a0Jakob Stoklund Olesen if (LII->end != VNI->def.getDeadSlot()) 75211513e5d1e1b40e6113668e4b4357596f33fa6c6Jakob Stoklund Olesen continue; 753a4d347357ce04d9101130dca0df33cb62ea35a2fJakob Stoklund Olesen if (VNI->isPHIDef()) { 75411513e5d1e1b40e6113668e4b4357596f33fa6c6Jakob Stoklund Olesen // This is a dead PHI. Remove it. 75511513e5d1e1b40e6113668e4b4357596f33fa6c6Jakob Stoklund Olesen VNI->setIsUnused(true); 75611513e5d1e1b40e6113668e4b4357596f33fa6c6Jakob Stoklund Olesen NewLI.removeRange(*LII); 7576a3dbd3b25bbc99bd1a233d6a74ddea3493ba6acJakob Stoklund Olesen DEBUG(dbgs() << "Dead PHI at " << VNI->def << " may separate interval\n"); 7586a3dbd3b25bbc99bd1a233d6a74ddea3493ba6acJakob Stoklund Olesen CanSeparate = true; 75911513e5d1e1b40e6113668e4b4357596f33fa6c6Jakob Stoklund Olesen } else { 76011513e5d1e1b40e6113668e4b4357596f33fa6c6Jakob Stoklund Olesen // This is a dead def. Make sure the instruction knows. 76111513e5d1e1b40e6113668e4b4357596f33fa6c6Jakob Stoklund Olesen MachineInstr *MI = getInstructionFromIndex(VNI->def); 76211513e5d1e1b40e6113668e4b4357596f33fa6c6Jakob Stoklund Olesen assert(MI && "No instruction defining live value"); 76311513e5d1e1b40e6113668e4b4357596f33fa6c6Jakob Stoklund Olesen MI->addRegisterDead(li->reg, tri_); 7640d8ccaa5c8db820b5b93f37e51563148c57ba6b8Jakob Stoklund Olesen if (dead && MI->allDefsAreDead()) { 765c46570dc05851395829bef904bb6ddb1260400d1Jakob Stoklund Olesen DEBUG(dbgs() << "All defs dead: " << VNI->def << '\t' << *MI); 7660d8ccaa5c8db820b5b93f37e51563148c57ba6b8Jakob Stoklund Olesen dead->push_back(MI); 7670d8ccaa5c8db820b5b93f37e51563148c57ba6b8Jakob Stoklund Olesen } 76811513e5d1e1b40e6113668e4b4357596f33fa6c6Jakob Stoklund Olesen } 76911513e5d1e1b40e6113668e4b4357596f33fa6c6Jakob Stoklund Olesen } 77011513e5d1e1b40e6113668e4b4357596f33fa6c6Jakob Stoklund Olesen 77111513e5d1e1b40e6113668e4b4357596f33fa6c6Jakob Stoklund Olesen // Move the trimmed ranges back. 77211513e5d1e1b40e6113668e4b4357596f33fa6c6Jakob Stoklund Olesen li->ranges.swap(NewLI.ranges); 773c46570dc05851395829bef904bb6ddb1260400d1Jakob Stoklund Olesen DEBUG(dbgs() << "Shrunk: " << *li << '\n'); 7746a3dbd3b25bbc99bd1a233d6a74ddea3493ba6acJakob Stoklund Olesen return CanSeparate; 77511513e5d1e1b40e6113668e4b4357596f33fa6c6Jakob Stoklund Olesen} 77611513e5d1e1b40e6113668e4b4357596f33fa6c6Jakob Stoklund Olesen 77711513e5d1e1b40e6113668e4b4357596f33fa6c6Jakob Stoklund Olesen 778f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng//===----------------------------------------------------------------------===// 779f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng// Register allocator hooks. 780f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng// 781f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng 782cb6404711b7fe6f583480adce8d7e9d5e4b99ae6Jakob Stoklund OlesenMachineBasicBlock::iterator 783cb6404711b7fe6f583480adce8d7e9d5e4b99ae6Jakob Stoklund OlesenLiveIntervals::getLastSplitPoint(const LiveInterval &li, 784f0ac26c51173a9a1d6e5b5794107dccc4c5b5792Jakob Stoklund Olesen MachineBasicBlock *mbb) const { 785cb6404711b7fe6f583480adce8d7e9d5e4b99ae6Jakob Stoklund Olesen const MachineBasicBlock *lpad = mbb->getLandingPadSuccessor(); 786cb6404711b7fe6f583480adce8d7e9d5e4b99ae6Jakob Stoklund Olesen 787cb6404711b7fe6f583480adce8d7e9d5e4b99ae6Jakob Stoklund Olesen // If li is not live into a landing pad, we can insert spill code before the 788cb6404711b7fe6f583480adce8d7e9d5e4b99ae6Jakob Stoklund Olesen // first terminator. 789cb6404711b7fe6f583480adce8d7e9d5e4b99ae6Jakob Stoklund Olesen if (!lpad || !isLiveInToMBB(li, lpad)) 790cb6404711b7fe6f583480adce8d7e9d5e4b99ae6Jakob Stoklund Olesen return mbb->getFirstTerminator(); 791cb6404711b7fe6f583480adce8d7e9d5e4b99ae6Jakob Stoklund Olesen 792cb6404711b7fe6f583480adce8d7e9d5e4b99ae6Jakob Stoklund Olesen // When there is a landing pad, spill code must go before the call instruction 793cb6404711b7fe6f583480adce8d7e9d5e4b99ae6Jakob Stoklund Olesen // that can throw. 794cb6404711b7fe6f583480adce8d7e9d5e4b99ae6Jakob Stoklund Olesen MachineBasicBlock::iterator I = mbb->end(), B = mbb->begin(); 795cb6404711b7fe6f583480adce8d7e9d5e4b99ae6Jakob Stoklund Olesen while (I != B) { 796cb6404711b7fe6f583480adce8d7e9d5e4b99ae6Jakob Stoklund Olesen --I; 7975a96b3dad2f634c9081c8b2b6c2575441dc5a2bdEvan Cheng if (I->isCall()) 798cb6404711b7fe6f583480adce8d7e9d5e4b99ae6Jakob Stoklund Olesen return I; 799cb6404711b7fe6f583480adce8d7e9d5e4b99ae6Jakob Stoklund Olesen } 80045e53975f81164d6e5e6322e83dd19030b7d3c88Jakob Stoklund Olesen // The block contains no calls that can throw, so use the first terminator. 801cb6404711b7fe6f583480adce8d7e9d5e4b99ae6Jakob Stoklund Olesen return mbb->getFirstTerminator(); 802cb6404711b7fe6f583480adce8d7e9d5e4b99ae6Jakob Stoklund Olesen} 803cb6404711b7fe6f583480adce8d7e9d5e4b99ae6Jakob Stoklund Olesen 8048a61da8a689ee95874c833af4c7aa965fab5c0a9Jakob Stoklund Olesenvoid LiveIntervals::addKillFlags() { 8058a61da8a689ee95874c833af4c7aa965fab5c0a9Jakob Stoklund Olesen for (iterator I = begin(), E = end(); I != E; ++I) { 8068a61da8a689ee95874c833af4c7aa965fab5c0a9Jakob Stoklund Olesen unsigned Reg = I->first; 8078a61da8a689ee95874c833af4c7aa965fab5c0a9Jakob Stoklund Olesen if (TargetRegisterInfo::isPhysicalRegister(Reg)) 8088a61da8a689ee95874c833af4c7aa965fab5c0a9Jakob Stoklund Olesen continue; 8098a61da8a689ee95874c833af4c7aa965fab5c0a9Jakob Stoklund Olesen if (mri_->reg_nodbg_empty(Reg)) 8108a61da8a689ee95874c833af4c7aa965fab5c0a9Jakob Stoklund Olesen continue; 8118a61da8a689ee95874c833af4c7aa965fab5c0a9Jakob Stoklund Olesen LiveInterval *LI = I->second; 8128a61da8a689ee95874c833af4c7aa965fab5c0a9Jakob Stoklund Olesen 8138a61da8a689ee95874c833af4c7aa965fab5c0a9Jakob Stoklund Olesen // Every instruction that kills Reg corresponds to a live range end point. 8148a61da8a689ee95874c833af4c7aa965fab5c0a9Jakob Stoklund Olesen for (LiveInterval::iterator RI = LI->begin(), RE = LI->end(); RI != RE; 8158a61da8a689ee95874c833af4c7aa965fab5c0a9Jakob Stoklund Olesen ++RI) { 8162debd48ca790ac01be6e12e094fdf4fdcadc8364Jakob Stoklund Olesen // A block index indicates an MBB edge. 8172debd48ca790ac01be6e12e094fdf4fdcadc8364Jakob Stoklund Olesen if (RI->end.isBlock()) 8188a61da8a689ee95874c833af4c7aa965fab5c0a9Jakob Stoklund Olesen continue; 8198a61da8a689ee95874c833af4c7aa965fab5c0a9Jakob Stoklund Olesen MachineInstr *MI = getInstructionFromIndex(RI->end); 8208a61da8a689ee95874c833af4c7aa965fab5c0a9Jakob Stoklund Olesen if (!MI) 8218a61da8a689ee95874c833af4c7aa965fab5c0a9Jakob Stoklund Olesen continue; 8228a61da8a689ee95874c833af4c7aa965fab5c0a9Jakob Stoklund Olesen MI->addRegisterKilled(Reg, NULL); 8238a61da8a689ee95874c833af4c7aa965fab5c0a9Jakob Stoklund Olesen } 8248a61da8a689ee95874c833af4c7aa965fab5c0a9Jakob Stoklund Olesen } 8258a61da8a689ee95874c833af4c7aa965fab5c0a9Jakob Stoklund Olesen} 8268a61da8a689ee95874c833af4c7aa965fab5c0a9Jakob Stoklund Olesen 827d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng/// getReMatImplicitUse - If the remat definition MI has one (for now, we only 828d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng/// allow one) virtual register operand, then its uses are implicitly using 829d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng/// the register. Returns the virtual register. 830d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Chengunsigned LiveIntervals::getReMatImplicitUse(const LiveInterval &li, 831d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng MachineInstr *MI) const { 832d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng unsigned RegOp = 0; 833d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) { 834d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng MachineOperand &MO = MI->getOperand(i); 835d735b8019b0f297d7c14b55adcd887af24d8e602Dan Gohman if (!MO.isReg() || !MO.isUse()) 836d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng continue; 837d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng unsigned Reg = MO.getReg(); 838d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng if (Reg == 0 || Reg == li.reg) 839d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng continue; 8401b2932024f098a6968645ac78d5848951d877c19Jakob Stoklund Olesen 8411873d0c2257b18451c5bb35577f929d0723433a0Chris Lattner if (TargetRegisterInfo::isPhysicalRegister(Reg) && 8421873d0c2257b18451c5bb35577f929d0723433a0Chris Lattner !allocatableRegs_[Reg]) 8431873d0c2257b18451c5bb35577f929d0723433a0Chris Lattner continue; 844d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng // FIXME: For now, only remat MI with at most one register operand. 845d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng assert(!RegOp && 846d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng "Can't rematerialize instruction with multiple register operand!"); 847d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng RegOp = MO.getReg(); 8486d69ba8a6901c69d78488cbc41f8dbf080618fdeDan Gohman#ifndef NDEBUG 849d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng break; 8506d69ba8a6901c69d78488cbc41f8dbf080618fdeDan Gohman#endif 851d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng } 852d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng return RegOp; 853d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng} 854d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng 855d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng/// isValNoAvailableAt - Return true if the val# of the specified interval 856d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng/// which reaches the given instruction also reaches the specified use index. 857d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Chengbool LiveIntervals::isValNoAvailableAt(const LiveInterval &li, MachineInstr *MI, 858233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames SlotIndex UseIdx) const { 85931cc3ec3308c8fafd9865388214ae11662a71af4Jakob Stoklund Olesen VNInfo *UValNo = li.getVNInfoAt(UseIdx); 86031cc3ec3308c8fafd9865388214ae11662a71af4Jakob Stoklund Olesen return UValNo && UValNo == li.getVNInfoAt(getInstructionIndex(MI)); 861d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng} 862d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng 863f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng/// isReMaterializable - Returns true if the definition MI of the specified 864f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng/// val# of the specified interval is re-materializable. 865f4baeaf8485f01beda46d29fd55753199dc68070Andrew Trickbool 866f4baeaf8485f01beda46d29fd55753199dc68070Andrew TrickLiveIntervals::isReMaterializable(const LiveInterval &li, 867f4baeaf8485f01beda46d29fd55753199dc68070Andrew Trick const VNInfo *ValNo, MachineInstr *MI, 86838f6bd0fc8095ef79a89b3db15ff6dc734ac90e7Jakob Stoklund Olesen const SmallVectorImpl<LiveInterval*> *SpillIs, 869f4baeaf8485f01beda46d29fd55753199dc68070Andrew Trick bool &isLoad) { 870f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng if (DisableReMat) 871f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng return false; 872f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng 873a70dca156fa76d452f54829b5c5f962ddfd94ef2Dan Gohman if (!tii_->isTriviallyReMaterializable(MI, aa_)) 874a70dca156fa76d452f54829b5c5f962ddfd94ef2Dan Gohman return false; 875f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng 876a70dca156fa76d452f54829b5c5f962ddfd94ef2Dan Gohman // Target-specific code can mark an instruction as being rematerializable 877a70dca156fa76d452f54829b5c5f962ddfd94ef2Dan Gohman // if it has one virtual reg use, though it had better be something like 878a70dca156fa76d452f54829b5c5f962ddfd94ef2Dan Gohman // a PIC base register which is likely to be live everywhere. 8796d69ba8a6901c69d78488cbc41f8dbf080618fdeDan Gohman unsigned ImpUse = getReMatImplicitUse(li, MI); 8806d69ba8a6901c69d78488cbc41f8dbf080618fdeDan Gohman if (ImpUse) { 8816d69ba8a6901c69d78488cbc41f8dbf080618fdeDan Gohman const LiveInterval &ImpLi = getInterval(ImpUse); 88228a1e486907104b85c5787345914917d74f0cf77Evan Cheng for (MachineRegisterInfo::use_nodbg_iterator 88328a1e486907104b85c5787345914917d74f0cf77Evan Cheng ri = mri_->use_nodbg_begin(li.reg), re = mri_->use_nodbg_end(); 88428a1e486907104b85c5787345914917d74f0cf77Evan Cheng ri != re; ++ri) { 8856d69ba8a6901c69d78488cbc41f8dbf080618fdeDan Gohman MachineInstr *UseMI = &*ri; 886233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames SlotIndex UseIdx = getInstructionIndex(UseMI); 88731cc3ec3308c8fafd9865388214ae11662a71af4Jakob Stoklund Olesen if (li.getVNInfoAt(UseIdx) != ValNo) 8886d69ba8a6901c69d78488cbc41f8dbf080618fdeDan Gohman continue; 8896d69ba8a6901c69d78488cbc41f8dbf080618fdeDan Gohman if (!isValNoAvailableAt(ImpLi, MI, UseIdx)) 8906d69ba8a6901c69d78488cbc41f8dbf080618fdeDan Gohman return false; 8916d69ba8a6901c69d78488cbc41f8dbf080618fdeDan Gohman } 892dc37786595beedd0a68d8e2cbd91ae53ad58d133Evan Cheng 893dc37786595beedd0a68d8e2cbd91ae53ad58d133Evan Cheng // If a register operand of the re-materialized instruction is going to 894dc37786595beedd0a68d8e2cbd91ae53ad58d133Evan Cheng // be spilled next, then it's not legal to re-materialize this instruction. 89538f6bd0fc8095ef79a89b3db15ff6dc734ac90e7Jakob Stoklund Olesen if (SpillIs) 89638f6bd0fc8095ef79a89b3db15ff6dc734ac90e7Jakob Stoklund Olesen for (unsigned i = 0, e = SpillIs->size(); i != e; ++i) 89738f6bd0fc8095ef79a89b3db15ff6dc734ac90e7Jakob Stoklund Olesen if (ImpUse == (*SpillIs)[i]->reg) 89838f6bd0fc8095ef79a89b3db15ff6dc734ac90e7Jakob Stoklund Olesen return false; 8996d69ba8a6901c69d78488cbc41f8dbf080618fdeDan Gohman } 9006d69ba8a6901c69d78488cbc41f8dbf080618fdeDan Gohman return true; 9015ef3a04b542c4e585276768fa9ca2af698ef5c87Evan Cheng} 9025ef3a04b542c4e585276768fa9ca2af698ef5c87Evan Cheng 9035ef3a04b542c4e585276768fa9ca2af698ef5c87Evan Cheng/// isReMaterializable - Returns true if every definition of MI of every 9045ef3a04b542c4e585276768fa9ca2af698ef5c87Evan Cheng/// val# of the specified interval is re-materializable. 905f4baeaf8485f01beda46d29fd55753199dc68070Andrew Trickbool 906f4baeaf8485f01beda46d29fd55753199dc68070Andrew TrickLiveIntervals::isReMaterializable(const LiveInterval &li, 90738f6bd0fc8095ef79a89b3db15ff6dc734ac90e7Jakob Stoklund Olesen const SmallVectorImpl<LiveInterval*> *SpillIs, 908f4baeaf8485f01beda46d29fd55753199dc68070Andrew Trick bool &isLoad) { 9095ef3a04b542c4e585276768fa9ca2af698ef5c87Evan Cheng isLoad = false; 9105ef3a04b542c4e585276768fa9ca2af698ef5c87Evan Cheng for (LiveInterval::const_vni_iterator i = li.vni_begin(), e = li.vni_end(); 9115ef3a04b542c4e585276768fa9ca2af698ef5c87Evan Cheng i != e; ++i) { 9125ef3a04b542c4e585276768fa9ca2af698ef5c87Evan Cheng const VNInfo *VNI = *i; 913857c4e01f85601cf2084adb860616256ee47c177Lang Hames if (VNI->isUnused()) 9145ef3a04b542c4e585276768fa9ca2af698ef5c87Evan Cheng continue; // Dead val#. 9155ef3a04b542c4e585276768fa9ca2af698ef5c87Evan Cheng // Is the def for the val# rematerializable? 916857c4e01f85601cf2084adb860616256ee47c177Lang Hames MachineInstr *ReMatDefMI = getInstructionFromIndex(VNI->def); 9176e2968c85c1e162ee5bc813769eab223e3df0f15Lang Hames if (!ReMatDefMI) 9186e2968c85c1e162ee5bc813769eab223e3df0f15Lang Hames return false; 9195ef3a04b542c4e585276768fa9ca2af698ef5c87Evan Cheng bool DefIsLoad = false; 920d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng if (!ReMatDefMI || 921dc37786595beedd0a68d8e2cbd91ae53ad58d133Evan Cheng !isReMaterializable(li, VNI, ReMatDefMI, SpillIs, DefIsLoad)) 922f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng return false; 9235ef3a04b542c4e585276768fa9ca2af698ef5c87Evan Cheng isLoad |= DefIsLoad; 924f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng } 925f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng return true; 926f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng} 927f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng 92881a038218171860ee4c382849c647d3dc841fe8bEvan Chengbool LiveIntervals::intervalIsInOneMBB(const LiveInterval &li) const { 929233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames LiveInterval::Ranges::const_iterator itr = li.ranges.begin(); 930233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames 931233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames MachineBasicBlock *mbb = indexes_->getMBBCoveringRange(itr->start, itr->end); 932233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames 933233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames if (mbb == 0) 934233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames return false; 935233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames 936233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames for (++itr; itr != li.ranges.end(); ++itr) { 937233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames MachineBasicBlock *mbb2 = 938233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames indexes_->getMBBCoveringRange(itr->start, itr->end); 939233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames 940233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames if (mbb2 != mbb) 94181a038218171860ee4c382849c647d3dc841fe8bEvan Cheng return false; 94281a038218171860ee4c382849c647d3dc841fe8bEvan Cheng } 943233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames 94481a038218171860ee4c382849c647d3dc841fe8bEvan Cheng return true; 94581a038218171860ee4c382849c647d3dc841fe8bEvan Cheng} 94681a038218171860ee4c382849c647d3dc841fe8bEvan Cheng 947e5d90416ee1a4f45eba80789a7a3cbc3d497a4cdJakob Stoklund Olesenfloat 948e5d90416ee1a4f45eba80789a7a3cbc3d497a4cdJakob Stoklund OlesenLiveIntervals::getSpillWeight(bool isDef, bool isUse, unsigned loopDepth) { 949e5d90416ee1a4f45eba80789a7a3cbc3d497a4cdJakob Stoklund Olesen // Limit the loop depth ridiculousness. 950e5d90416ee1a4f45eba80789a7a3cbc3d497a4cdJakob Stoklund Olesen if (loopDepth > 200) 951e5d90416ee1a4f45eba80789a7a3cbc3d497a4cdJakob Stoklund Olesen loopDepth = 200; 952e5d90416ee1a4f45eba80789a7a3cbc3d497a4cdJakob Stoklund Olesen 953e5d90416ee1a4f45eba80789a7a3cbc3d497a4cdJakob Stoklund Olesen // The loop depth is used to roughly estimate the number of times the 954e5d90416ee1a4f45eba80789a7a3cbc3d497a4cdJakob Stoklund Olesen // instruction is executed. Something like 10^d is simple, but will quickly 955e5d90416ee1a4f45eba80789a7a3cbc3d497a4cdJakob Stoklund Olesen // overflow a float. This expression behaves like 10^d for small d, but is 956e5d90416ee1a4f45eba80789a7a3cbc3d497a4cdJakob Stoklund Olesen // more tempered for large d. At d=200 we get 6.7e33 which leaves a bit of 957e5d90416ee1a4f45eba80789a7a3cbc3d497a4cdJakob Stoklund Olesen // headroom before overflow. 958dc5198bac7e3f9b61617c8c46a1c28a84daa9325NAKAMURA Takumi // By the way, powf() might be unavailable here. For consistency, 959dc5198bac7e3f9b61617c8c46a1c28a84daa9325NAKAMURA Takumi // We may take pow(double,double). 960dc5198bac7e3f9b61617c8c46a1c28a84daa9325NAKAMURA Takumi float lc = std::pow(1 + (100.0 / (loopDepth + 10)), (double)loopDepth); 961e5d90416ee1a4f45eba80789a7a3cbc3d497a4cdJakob Stoklund Olesen 962e5d90416ee1a4f45eba80789a7a3cbc3d497a4cdJakob Stoklund Olesen return (isDef + isUse) * lc; 963e5d90416ee1a4f45eba80789a7a3cbc3d497a4cdJakob Stoklund Olesen} 964e5d90416ee1a4f45eba80789a7a3cbc3d497a4cdJakob Stoklund Olesen 965c4dc132c8a787fc41b6a162121251234aa618965Owen AndersonLiveRange LiveIntervals::addLiveRangeToEndOfBlock(unsigned reg, 966ffd1326ff8dfc652a8026c3faebf55bbba7c32c7Lang Hames MachineInstr* startInst) { 967c4dc132c8a787fc41b6a162121251234aa618965Owen Anderson LiveInterval& Interval = getOrCreateInterval(reg); 968c4dc132c8a787fc41b6a162121251234aa618965Owen Anderson VNInfo* VN = Interval.getNextValue( 9692debd48ca790ac01be6e12e094fdf4fdcadc8364Jakob Stoklund Olesen SlotIndex(getInstructionIndex(startInst).getRegSlot()), 9706e2968c85c1e162ee5bc813769eab223e3df0f15Lang Hames startInst, getVNInfoAllocator()); 971857c4e01f85601cf2084adb860616256ee47c177Lang Hames VN->setHasPHIKill(true); 9728651125d2885f74546b6e2a556082111d5b75da3Lang Hames LiveRange LR( 9732debd48ca790ac01be6e12e094fdf4fdcadc8364Jakob Stoklund Olesen SlotIndex(getInstructionIndex(startInst).getRegSlot()), 97474ab5eeffbd70f2387338e3ee8195be9f73e6dd8Lang Hames getMBBEndIdx(startInst->getParent()), VN); 975c4dc132c8a787fc41b6a162121251234aa618965Owen Anderson Interval.addRange(LR); 9761b2932024f098a6968645ac78d5848951d877c19Jakob Stoklund Olesen 977c4dc132c8a787fc41b6a162121251234aa618965Owen Anderson return LR; 978c4dc132c8a787fc41b6a162121251234aa618965Owen Anderson} 979b5257664795d49ada0d4669fe8ed1cd49c04fbf3David Greene 980