LiveIntervalAnalysis.cpp revision 8dd26253f54247e77e5accfdd70e7b4bf27b39c2
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" 20015959ee38e4fd4a920f6b0065c50e524762f580Chris Lattner#include "llvm/Value.h" 216d69ba8a6901c69d78488cbc41f8dbf080618fdeDan Gohman#include "llvm/Analysis/AliasAnalysis.h" 22ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos#include "llvm/CodeGen/LiveVariables.h" 23ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos#include "llvm/CodeGen/MachineInstr.h" 2422f07ffd27d1d721634d502c37267721d2e025cfEvan Cheng#include "llvm/CodeGen/MachineLoopInfo.h" 2584bc5427d6883f73cfeae3da640acd011d35c006Chris Lattner#include "llvm/CodeGen/MachineRegisterInfo.h" 26ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos#include "llvm/CodeGen/Passes.h" 276f0d024a534af18d9e60b3ea757376cd8a3a980eDan Gohman#include "llvm/Target/TargetRegisterInfo.h" 28ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos#include "llvm/Target/TargetInstrInfo.h" 29ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos#include "llvm/Target/TargetMachine.h" 30551ccae044b0ff658fe629dd67edd5ffe75d10e8Reid Spencer#include "llvm/Support/CommandLine.h" 31551ccae044b0ff658fe629dd67edd5ffe75d10e8Reid Spencer#include "llvm/Support/Debug.h" 327d696d80409aad20bb5da0fc4eccab941dd371d4Torok Edwin#include "llvm/Support/ErrorHandling.h" 337d696d80409aad20bb5da0fc4eccab941dd371d4Torok Edwin#include "llvm/Support/raw_ostream.h" 34551ccae044b0ff658fe629dd67edd5ffe75d10e8Reid Spencer#include "llvm/ADT/Statistic.h" 35551ccae044b0ff658fe629dd67edd5ffe75d10e8Reid Spencer#include "llvm/ADT/STLExtras.h" 3620aa474f8fbebde588edc101b90e834df28ce4ceAlkis Evlogimenos#include <algorithm> 37f41538d1b54f55e8900394929b50f7ce3e61125fLang Hames#include <limits> 3897af751deb9b26fd42fbcee082da9ccc4ded5b45Jeff Cohen#include <cmath> 39ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenosusing namespace llvm; 40ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos 41844731a7f1909f55935e3514c9e713a62d67662eDan Gohman// Hidden options for help debugging. 421b2932024f098a6968645ac78d5848951d877c19Jakob Stoklund Olesenstatic cl::opt<bool> DisableReMat("disable-rematerialization", 43844731a7f1909f55935e3514c9e713a62d67662eDan Gohman cl::init(false), cl::Hidden); 44844731a7f1909f55935e3514c9e713a62d67662eDan Gohman 45752195e3c662c6b5db042cf897c984624720f3b8Evan ChengSTATISTIC(numIntervals , "Number of original intervals"); 46cd3245ac45c595da96bb768a55cddc356dff55feChris Lattner 471997473cf72957d0e70322e2fe6fe2ab141c58a6Devang Patelchar LiveIntervals::ID = 0; 482ab36d350293c77fc8941ce1023e4899df7e3a82Owen AndersonINITIALIZE_PASS_BEGIN(LiveIntervals, "liveintervals", 492ab36d350293c77fc8941ce1023e4899df7e3a82Owen Anderson "Live Interval Analysis", false, false) 508dd26253f54247e77e5accfdd70e7b4bf27b39c2Andrew TrickINITIALIZE_AG_DEPENDENCY(AliasAnalysis) 512ab36d350293c77fc8941ce1023e4899df7e3a82Owen AndersonINITIALIZE_PASS_DEPENDENCY(LiveVariables) 522ab36d350293c77fc8941ce1023e4899df7e3a82Owen AndersonINITIALIZE_PASS_DEPENDENCY(MachineLoopInfo) 538dd26253f54247e77e5accfdd70e7b4bf27b39c2Andrew TrickINITIALIZE_PASS_DEPENDENCY(MachineDominatorTree) 542ab36d350293c77fc8941ce1023e4899df7e3a82Owen AndersonINITIALIZE_PASS_DEPENDENCY(SlotIndexes) 552ab36d350293c77fc8941ce1023e4899df7e3a82Owen AndersonINITIALIZE_PASS_END(LiveIntervals, "liveintervals", 56ce665bd2e2b581ab0858d1afe359192bac96b868Owen Anderson "Live Interval Analysis", false, false) 57ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos 58f7da2c7b0c6293c268881628fc351bed7763f1f4Chris Lattnervoid LiveIntervals::getAnalysisUsage(AnalysisUsage &AU) const { 59845012e6d31799c7fbd1193fa1af8ee2d12e9231Dan Gohman AU.setPreservesCFG(); 606d69ba8a6901c69d78488cbc41f8dbf080618fdeDan Gohman AU.addRequired<AliasAnalysis>(); 616d69ba8a6901c69d78488cbc41f8dbf080618fdeDan Gohman AU.addPreserved<AliasAnalysis>(); 621a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos AU.addRequired<LiveVariables>(); 63148341cc9b60d7d88be9c07a2b32b436e0cd301dEvan Cheng AU.addPreserved<LiveVariables>(); 64148341cc9b60d7d88be9c07a2b32b436e0cd301dEvan Cheng AU.addRequired<MachineLoopInfo>(); 65148341cc9b60d7d88be9c07a2b32b436e0cd301dEvan Cheng AU.addPreserved<MachineLoopInfo>(); 6667d65bb69d5cad957cbb6d672dc0b4a19c211a42Bill Wendling AU.addPreservedID(MachineDominatorsID); 67233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames AU.addPreserved<SlotIndexes>(); 68233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames AU.addRequiredTransitive<SlotIndexes>(); 691a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos MachineFunctionPass::getAnalysisUsage(AU); 70ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos} 71ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos 72f7da2c7b0c6293c268881628fc351bed7763f1f4Chris Lattnervoid LiveIntervals::releaseMemory() { 7303857b29d8271a23943254579e6cf7b7df4b1bd3Owen Anderson // Free the live intervals themselves. 7420e2839cb975a2d4ee931e1ea4c4660a36ef0177Owen Anderson for (DenseMap<unsigned, LiveInterval*>::iterator I = r2iMap_.begin(), 75d6a6b3b7563a3f54ba48d465fc03ee10bbccb7a8Bob Wilson E = r2iMap_.end(); I != E; ++I) 7603857b29d8271a23943254579e6cf7b7df4b1bd3Owen Anderson delete I->second; 771b2932024f098a6968645ac78d5848951d877c19Jakob Stoklund Olesen 781a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos r2iMap_.clear(); 793fd3a840c50fe4ede1b200be18990bc955c536fdJakob Stoklund Olesen RegMaskSlots.clear(); 803fd3a840c50fe4ede1b200be18990bc955c536fdJakob Stoklund Olesen RegMaskBits.clear(); 8134e85d0307e3c17e5061622dccf8a20e5457b099Jakob Stoklund Olesen RegMaskBlocks.clear(); 82ffd1326ff8dfc652a8026c3faebf55bbba7c32c7Lang Hames 83ce9a20b808ba48adf72e0c0615f903a65e9f9eb8Benjamin Kramer // Release VNInfo memory regions, VNInfo objects don't need to be dtor'd. 84ce9a20b808ba48adf72e0c0615f903a65e9f9eb8Benjamin Kramer VNInfoAllocator.Reset(); 85993141402f57b4d4cbb7f8a3113f19c61688f9b7Evan Cheng} 86993141402f57b4d4cbb7f8a3113f19c61688f9b7Evan Cheng 8780b3ce65e294a28b88c882d44a5e749a2924c9e3Owen Anderson/// runOnMachineFunction - Register allocate the whole function 8880b3ce65e294a28b88c882d44a5e749a2924c9e3Owen Anderson/// 8980b3ce65e294a28b88c882d44a5e749a2924c9e3Owen Andersonbool LiveIntervals::runOnMachineFunction(MachineFunction &fn) { 9080b3ce65e294a28b88c882d44a5e749a2924c9e3Owen Anderson mf_ = &fn; 9180b3ce65e294a28b88c882d44a5e749a2924c9e3Owen Anderson mri_ = &mf_->getRegInfo(); 9280b3ce65e294a28b88c882d44a5e749a2924c9e3Owen Anderson tm_ = &fn.getTarget(); 9380b3ce65e294a28b88c882d44a5e749a2924c9e3Owen Anderson tri_ = tm_->getRegisterInfo(); 9480b3ce65e294a28b88c882d44a5e749a2924c9e3Owen Anderson tii_ = tm_->getInstrInfo(); 956d69ba8a6901c69d78488cbc41f8dbf080618fdeDan Gohman aa_ = &getAnalysis<AliasAnalysis>(); 9680b3ce65e294a28b88c882d44a5e749a2924c9e3Owen Anderson lv_ = &getAnalysis<LiveVariables>(); 97233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames indexes_ = &getAnalysis<SlotIndexes>(); 9880b3ce65e294a28b88c882d44a5e749a2924c9e3Owen Anderson allocatableRegs_ = tri_->getAllocatableSet(fn); 99ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos 1001a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos computeIntervals(); 101ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos 1021a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos numIntervals += getNumIntervals(); 103843b160a2040b3ec4d3452678450afa11704c473Alkis Evlogimenos 10470ca358b7d540b6061236ddf757085042873c12cChris Lattner DEBUG(dump()); 1051a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos return true; 106ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos} 107ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos 10870ca358b7d540b6061236ddf757085042873c12cChris Lattner/// print - Implement the dump method. 10945cfe545ec8177262dabc70580ce05feaa1c3880Chris Lattnervoid LiveIntervals::print(raw_ostream &OS, const Module* ) const { 110705e07f578e2b3af47ddab610feb4e7f2d3063a5Chris Lattner OS << "********** INTERVALS **********\n"; 1118e7a70976deee78a84099b916591d40f7a1cdc34Chris Lattner for (const_iterator I = begin(), E = end(); I != E; ++I) { 112705e07f578e2b3af47ddab610feb4e7f2d3063a5Chris Lattner I->second->print(OS, tri_); 113705e07f578e2b3af47ddab610feb4e7f2d3063a5Chris Lattner OS << "\n"; 1148e7a70976deee78a84099b916591d40f7a1cdc34Chris Lattner } 11570ca358b7d540b6061236ddf757085042873c12cChris Lattner 116752195e3c662c6b5db042cf897c984624720f3b8Evan Cheng printInstrs(OS); 117752195e3c662c6b5db042cf897c984624720f3b8Evan Cheng} 118752195e3c662c6b5db042cf897c984624720f3b8Evan Cheng 119752195e3c662c6b5db042cf897c984624720f3b8Evan Chengvoid LiveIntervals::printInstrs(raw_ostream &OS) const { 120705e07f578e2b3af47ddab610feb4e7f2d3063a5Chris Lattner OS << "********** MACHINEINSTRS **********\n"; 121f4a1e1a69f0727762a73ef0d551e3bbd16b7c04eJakob Stoklund Olesen mf_->print(OS, indexes_); 12270ca358b7d540b6061236ddf757085042873c12cChris Lattner} 12370ca358b7d540b6061236ddf757085042873c12cChris Lattner 124752195e3c662c6b5db042cf897c984624720f3b8Evan Chengvoid LiveIntervals::dumpInstrs() const { 1258a34229dcf484739119857988772572ef0cad9f2David Greene printInstrs(dbgs()); 126752195e3c662c6b5db042cf897c984624720f3b8Evan Cheng} 127752195e3c662c6b5db042cf897c984624720f3b8Evan Cheng 128afff40a62da19be15295c0f8ed5d4d450ccb45a5Evan Chengstatic 1293749943648772743c9c0e852553e50e6700a0c1bEvan Chengbool MultipleDefsBySameMI(const MachineInstr &MI, unsigned MOIdx) { 130afff40a62da19be15295c0f8ed5d4d450ccb45a5Evan Cheng unsigned Reg = MI.getOperand(MOIdx).getReg(); 131afff40a62da19be15295c0f8ed5d4d450ccb45a5Evan Cheng for (unsigned i = MOIdx+1, e = MI.getNumOperands(); i < e; ++i) { 132afff40a62da19be15295c0f8ed5d4d450ccb45a5Evan Cheng const MachineOperand &MO = MI.getOperand(i); 133afff40a62da19be15295c0f8ed5d4d450ccb45a5Evan Cheng if (!MO.isReg()) 134afff40a62da19be15295c0f8ed5d4d450ccb45a5Evan Cheng continue; 135afff40a62da19be15295c0f8ed5d4d450ccb45a5Evan Cheng if (MO.getReg() == Reg && MO.isDef()) { 136afff40a62da19be15295c0f8ed5d4d450ccb45a5Evan Cheng assert(MI.getOperand(MOIdx).getSubReg() != MO.getSubReg() && 137afff40a62da19be15295c0f8ed5d4d450ccb45a5Evan Cheng MI.getOperand(MOIdx).getSubReg() && 138ed2185e171a86b8c0e166803fd4066383a6cff08Jakob Stoklund Olesen (MO.getSubReg() || MO.isImplicit())); 139afff40a62da19be15295c0f8ed5d4d450ccb45a5Evan Cheng return true; 140afff40a62da19be15295c0f8ed5d4d450ccb45a5Evan Cheng } 141afff40a62da19be15295c0f8ed5d4d450ccb45a5Evan Cheng } 142afff40a62da19be15295c0f8ed5d4d450ccb45a5Evan Cheng return false; 143afff40a62da19be15295c0f8ed5d4d450ccb45a5Evan Cheng} 144afff40a62da19be15295c0f8ed5d4d450ccb45a5Evan Cheng 1453749943648772743c9c0e852553e50e6700a0c1bEvan Cheng/// isPartialRedef - Return true if the specified def at the specific index is 1463749943648772743c9c0e852553e50e6700a0c1bEvan Cheng/// partially re-defining the specified live interval. A common case of this is 1471b2932024f098a6968645ac78d5848951d877c19Jakob Stoklund Olesen/// a definition of the sub-register. 1483749943648772743c9c0e852553e50e6700a0c1bEvan Chengbool LiveIntervals::isPartialRedef(SlotIndex MIIdx, MachineOperand &MO, 1493749943648772743c9c0e852553e50e6700a0c1bEvan Cheng LiveInterval &interval) { 1503749943648772743c9c0e852553e50e6700a0c1bEvan Cheng if (!MO.getSubReg() || MO.isEarlyClobber()) 1513749943648772743c9c0e852553e50e6700a0c1bEvan Cheng return false; 1523749943648772743c9c0e852553e50e6700a0c1bEvan Cheng 1532debd48ca790ac01be6e12e094fdf4fdcadc8364Jakob Stoklund Olesen SlotIndex RedefIndex = MIIdx.getRegSlot(); 1543749943648772743c9c0e852553e50e6700a0c1bEvan Cheng const LiveRange *OldLR = 1552debd48ca790ac01be6e12e094fdf4fdcadc8364Jakob Stoklund Olesen interval.getLiveRangeContaining(RedefIndex.getRegSlot(true)); 1566e2968c85c1e162ee5bc813769eab223e3df0f15Lang Hames MachineInstr *DefMI = getInstructionFromIndex(OldLR->valno->def); 1576e2968c85c1e162ee5bc813769eab223e3df0f15Lang Hames if (DefMI != 0) { 1583749943648772743c9c0e852553e50e6700a0c1bEvan Cheng return DefMI->findRegisterDefOperandIdx(interval.reg) != -1; 1593749943648772743c9c0e852553e50e6700a0c1bEvan Cheng } 1603749943648772743c9c0e852553e50e6700a0c1bEvan Cheng return false; 1613749943648772743c9c0e852553e50e6700a0c1bEvan Cheng} 1623749943648772743c9c0e852553e50e6700a0c1bEvan Cheng 163be4f88a8b8bb3311e0dc4cde8533763d7923c3eaChris Lattnervoid LiveIntervals::handleVirtualRegisterDef(MachineBasicBlock *mbb, 164ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos MachineBasicBlock::iterator mi, 165233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames SlotIndex MIIdx, 1668651125d2885f74546b6e2a556082111d5b75da3Lang Hames MachineOperand& MO, 167ef0732d25a9882c947984ae3f2afbef5463ba00fEvan Cheng unsigned MOIdx, 168be4f88a8b8bb3311e0dc4cde8533763d7923c3eaChris Lattner LiveInterval &interval) { 1694314268128be6d54c9a7f0709680e5a5b40f3ab3Jakob Stoklund Olesen DEBUG(dbgs() << "\t\tregister: " << PrintReg(interval.reg, tri_)); 170419852ca8a01aecde4c0e20af6b7bd6450e70f87Evan Cheng 171706515727c6d024015fffded2b3109a4f0ac5299Alkis Evlogimenos // Virtual registers may be defined multiple times (due to phi 172706515727c6d024015fffded2b3109a4f0ac5299Alkis Evlogimenos // elimination and 2-addr elimination). Much of what we do only has to be 173706515727c6d024015fffded2b3109a4f0ac5299Alkis Evlogimenos // done once for the vreg. We use an empty interval to detect the first 1741a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // time we see a vreg. 175d129d73b725e32d2fc0c87f392c239db8801e922Evan Cheng LiveVariables::VarInfo& vi = lv_->getVarInfo(interval.reg); 1761a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos if (interval.empty()) { 1771a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // Get the Idx of the defining instructions. 178d14614e6777771f8fec3062bcaf2986c189ac84dJakob Stoklund Olesen SlotIndex defIndex = MIIdx.getRegSlot(MO.isEarlyClobber()); 17963e6a488cb6c29983415221719d05fbf99e00193Jakob Stoklund Olesen 18063e6a488cb6c29983415221719d05fbf99e00193Jakob Stoklund Olesen // Make sure the first definition is not a partial redefinition. Add an 18163e6a488cb6c29983415221719d05fbf99e00193Jakob Stoklund Olesen // <imp-def> of the full register. 182b0e1bc7b99809e2b45726affd73f72c60c506ea0Jakob Stoklund Olesen // FIXME: LiveIntervals shouldn't modify the code like this. Whoever 183b0e1bc7b99809e2b45726affd73f72c60c506ea0Jakob Stoklund Olesen // created the machine instruction should annotate it with <undef> flags 184b0e1bc7b99809e2b45726affd73f72c60c506ea0Jakob Stoklund Olesen // as needed. Then we can simply assert here. The REG_SEQUENCE lowering 185b0e1bc7b99809e2b45726affd73f72c60c506ea0Jakob Stoklund Olesen // is the main suspect. 1867016cf66ee21ddf3f7823d4e332b2cb84953bebdJakob Stoklund Olesen if (MO.getSubReg()) { 18763e6a488cb6c29983415221719d05fbf99e00193Jakob Stoklund Olesen mi->addRegisterDefined(interval.reg); 1887016cf66ee21ddf3f7823d4e332b2cb84953bebdJakob Stoklund Olesen // Mark all defs of interval.reg on this instruction as reading <undef>. 1897016cf66ee21ddf3f7823d4e332b2cb84953bebdJakob Stoklund Olesen for (unsigned i = MOIdx, e = mi->getNumOperands(); i != e; ++i) { 1907016cf66ee21ddf3f7823d4e332b2cb84953bebdJakob Stoklund Olesen MachineOperand &MO2 = mi->getOperand(i); 1917016cf66ee21ddf3f7823d4e332b2cb84953bebdJakob Stoklund Olesen if (MO2.isReg() && MO2.getReg() == interval.reg && MO2.getSubReg()) 1927016cf66ee21ddf3f7823d4e332b2cb84953bebdJakob Stoklund Olesen MO2.setIsUndef(); 1937016cf66ee21ddf3f7823d4e332b2cb84953bebdJakob Stoklund Olesen } 1947016cf66ee21ddf3f7823d4e332b2cb84953bebdJakob Stoklund Olesen } 19563e6a488cb6c29983415221719d05fbf99e00193Jakob Stoklund Olesen 1963b1088a2cc15a39c7a7b8dd95a56143f1dda6863Jakob Stoklund Olesen VNInfo *ValNo = interval.getNextValue(defIndex, VNInfoAllocator); 1977ecb38be0a533e7b9c7d3b8e9b5c8a6fa5f6b349Evan Cheng assert(ValNo->id == 0 && "First value in interval is not 0?"); 1981a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos 1991a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // Loop over all of the blocks that the vreg is defined in. There are 2001a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // two cases we have to handle here. The most common case is a vreg 2011a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // whose lifetime is contained within a basic block. In this case there 2021a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // will be a single kill, in MBB, which comes after the definition. 2031a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos if (vi.Kills.size() == 1 && vi.Kills[0]->getParent() == mbb) { 2041a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // FIXME: what about dead vars? 205233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames SlotIndex killIdx; 2061a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos if (vi.Kills[0] != mi) 2072debd48ca790ac01be6e12e094fdf4fdcadc8364Jakob Stoklund Olesen killIdx = getInstructionIndex(vi.Kills[0]).getRegSlot(); 2081a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos else 2092debd48ca790ac01be6e12e094fdf4fdcadc8364Jakob Stoklund Olesen killIdx = defIndex.getDeadSlot(); 2101a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos 2111a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // If the kill happens after the definition, we have an intra-block 2121a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // live range. 2131a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos if (killIdx > defIndex) { 214493a3d015cbb2bcc18d9293a4dec3b35c7493818Jeffrey Yasskin assert(vi.AliveBlocks.empty() && 2151a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos "Shouldn't be alive across any blocks!"); 2167ecb38be0a533e7b9c7d3b8e9b5c8a6fa5f6b349Evan Cheng LiveRange LR(defIndex, killIdx, ValNo); 2171a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos interval.addRange(LR); 2188a34229dcf484739119857988772572ef0cad9f2David Greene DEBUG(dbgs() << " +" << LR << "\n"); 2191a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos return; 2201a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos } 2211a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos } 2226097d13b2a624048dbe02e39e2dfb23bfa269b64Chris Lattner 2231a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // The other case we handle is when a virtual register lives to the end 2241a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // of the defining block, potentially live across some blocks, then is 2251a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // live into some number of blocks, but gets killed. Start by adding a 2261a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // range that goes from this definition to the end of the defining block. 22774ab5eeffbd70f2387338e3ee8195be9f73e6dd8Lang Hames LiveRange NewLR(defIndex, getMBBEndIdx(mbb), ValNo); 2288a34229dcf484739119857988772572ef0cad9f2David Greene DEBUG(dbgs() << " +" << NewLR); 2291a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos interval.addRange(NewLR); 2301a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos 231dcfe5f30b5e262971f601a65bebcc0367fef56c5Jakob Stoklund Olesen bool PHIJoin = lv_->isPHIJoin(interval.reg); 232dcfe5f30b5e262971f601a65bebcc0367fef56c5Jakob Stoklund Olesen 233dcfe5f30b5e262971f601a65bebcc0367fef56c5Jakob Stoklund Olesen if (PHIJoin) { 234dcfe5f30b5e262971f601a65bebcc0367fef56c5Jakob Stoklund Olesen // A phi join register is killed at the end of the MBB and revived as a new 235dcfe5f30b5e262971f601a65bebcc0367fef56c5Jakob Stoklund Olesen // valno in the killing blocks. 236dcfe5f30b5e262971f601a65bebcc0367fef56c5Jakob Stoklund Olesen assert(vi.AliveBlocks.empty() && "Phi join can't pass through blocks"); 237dcfe5f30b5e262971f601a65bebcc0367fef56c5Jakob Stoklund Olesen DEBUG(dbgs() << " phi-join"); 238dcfe5f30b5e262971f601a65bebcc0367fef56c5Jakob Stoklund Olesen ValNo->setHasPHIKill(true); 239dcfe5f30b5e262971f601a65bebcc0367fef56c5Jakob Stoklund Olesen } else { 240dcfe5f30b5e262971f601a65bebcc0367fef56c5Jakob Stoklund Olesen // Iterate over all of the blocks that the variable is completely 241dcfe5f30b5e262971f601a65bebcc0367fef56c5Jakob Stoklund Olesen // live in, adding [insrtIndex(begin), instrIndex(end)+4) to the 242dcfe5f30b5e262971f601a65bebcc0367fef56c5Jakob Stoklund Olesen // live interval. 243dcfe5f30b5e262971f601a65bebcc0367fef56c5Jakob Stoklund Olesen for (SparseBitVector<>::iterator I = vi.AliveBlocks.begin(), 244dcfe5f30b5e262971f601a65bebcc0367fef56c5Jakob Stoklund Olesen E = vi.AliveBlocks.end(); I != E; ++I) { 245dcfe5f30b5e262971f601a65bebcc0367fef56c5Jakob Stoklund Olesen MachineBasicBlock *aliveBlock = mf_->getBlockNumbered(*I); 246dcfe5f30b5e262971f601a65bebcc0367fef56c5Jakob Stoklund Olesen LiveRange LR(getMBBStartIdx(aliveBlock), getMBBEndIdx(aliveBlock), ValNo); 247dcfe5f30b5e262971f601a65bebcc0367fef56c5Jakob Stoklund Olesen interval.addRange(LR); 248dcfe5f30b5e262971f601a65bebcc0367fef56c5Jakob Stoklund Olesen DEBUG(dbgs() << " +" << LR); 249dcfe5f30b5e262971f601a65bebcc0367fef56c5Jakob Stoklund Olesen } 2501a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos } 2511a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos 2521a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // Finally, this virtual register is live from the start of any killing 2531a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // block to the 'use' slot of the killing instruction. 2541a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos for (unsigned i = 0, e = vi.Kills.size(); i != e; ++i) { 2551a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos MachineInstr *Kill = vi.Kills[i]; 256dcfe5f30b5e262971f601a65bebcc0367fef56c5Jakob Stoklund Olesen SlotIndex Start = getMBBStartIdx(Kill->getParent()); 2572debd48ca790ac01be6e12e094fdf4fdcadc8364Jakob Stoklund Olesen SlotIndex killIdx = getInstructionIndex(Kill).getRegSlot(); 258dcfe5f30b5e262971f601a65bebcc0367fef56c5Jakob Stoklund Olesen 259dcfe5f30b5e262971f601a65bebcc0367fef56c5Jakob Stoklund Olesen // Create interval with one of a NEW value number. Note that this value 260dcfe5f30b5e262971f601a65bebcc0367fef56c5Jakob Stoklund Olesen // number isn't actually defined by an instruction, weird huh? :) 261dcfe5f30b5e262971f601a65bebcc0367fef56c5Jakob Stoklund Olesen if (PHIJoin) { 2626e2968c85c1e162ee5bc813769eab223e3df0f15Lang Hames assert(getInstructionFromIndex(Start) == 0 && 2636e2968c85c1e162ee5bc813769eab223e3df0f15Lang Hames "PHI def index points at actual instruction."); 2643b1088a2cc15a39c7a7b8dd95a56143f1dda6863Jakob Stoklund Olesen ValNo = interval.getNextValue(Start, VNInfoAllocator); 265dcfe5f30b5e262971f601a65bebcc0367fef56c5Jakob Stoklund Olesen ValNo->setIsPHIDef(true); 266dcfe5f30b5e262971f601a65bebcc0367fef56c5Jakob Stoklund Olesen } 267dcfe5f30b5e262971f601a65bebcc0367fef56c5Jakob Stoklund Olesen LiveRange LR(Start, killIdx, ValNo); 2681a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos interval.addRange(LR); 2698a34229dcf484739119857988772572ef0cad9f2David Greene DEBUG(dbgs() << " +" << LR); 2701a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos } 2711a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos 2721a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos } else { 2733749943648772743c9c0e852553e50e6700a0c1bEvan Cheng if (MultipleDefsBySameMI(*mi, MOIdx)) 274761fd4c1d97977c16de9f0cf921056a37b906304Nick Lewycky // Multiple defs of the same virtual register by the same instruction. 275761fd4c1d97977c16de9f0cf921056a37b906304Nick Lewycky // e.g. %reg1031:5<def>, %reg1031:6<def> = VLD1q16 %reg1024<kill>, ... 276afff40a62da19be15295c0f8ed5d4d450ccb45a5Evan Cheng // This is likely due to elimination of REG_SEQUENCE instructions. Return 277afff40a62da19be15295c0f8ed5d4d450ccb45a5Evan Cheng // here since there is nothing to do. 278afff40a62da19be15295c0f8ed5d4d450ccb45a5Evan Cheng return; 279afff40a62da19be15295c0f8ed5d4d450ccb45a5Evan Cheng 2801a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // If this is the second time we see a virtual register definition, it 2811a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // must be due to phi elimination or two addr elimination. If this is 282bf105c842450d3308d024be203ddd533f37051ecEvan Cheng // the result of two address elimination, then the vreg is one of the 283bf105c842450d3308d024be203ddd533f37051ecEvan Cheng // def-and-use register operand. 2843749943648772743c9c0e852553e50e6700a0c1bEvan Cheng 2853749943648772743c9c0e852553e50e6700a0c1bEvan Cheng // It may also be partial redef like this: 2861b2932024f098a6968645ac78d5848951d877c19Jakob Stoklund Olesen // 80 %reg1041:6<def> = VSHRNv4i16 %reg1034<kill>, 12, pred:14, pred:%reg0 2871b2932024f098a6968645ac78d5848951d877c19Jakob Stoklund Olesen // 120 %reg1041:5<def> = VSHRNv4i16 %reg1039<kill>, 12, pred:14, pred:%reg0 2883749943648772743c9c0e852553e50e6700a0c1bEvan Cheng bool PartReDef = isPartialRedef(MIIdx, MO, interval); 2893749943648772743c9c0e852553e50e6700a0c1bEvan Cheng if (PartReDef || mi->isRegTiedToUseOperand(MOIdx)) { 2901a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // If this is a two-address definition, then we have already processed 2911a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // the live range. The only problem is that we didn't realize there 2921a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // are actually two values in the live interval. Because of this we 2931a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // need to take the LiveRegion that defines this register and split it 2941a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // into two values. 295d14614e6777771f8fec3062bcaf2986c189ac84dJakob Stoklund Olesen SlotIndex RedefIndex = MIIdx.getRegSlot(MO.isEarlyClobber()); 2961a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos 29735f291d2c5f80e8e713704190230064311bbbbbeLang Hames const LiveRange *OldLR = 2982debd48ca790ac01be6e12e094fdf4fdcadc8364Jakob Stoklund Olesen interval.getLiveRangeContaining(RedefIndex.getRegSlot(true)); 2997ecb38be0a533e7b9c7d3b8e9b5c8a6fa5f6b349Evan Cheng VNInfo *OldValNo = OldLR->valno; 3002debd48ca790ac01be6e12e094fdf4fdcadc8364Jakob Stoklund Olesen SlotIndex DefIndex = OldValNo->def.getRegSlot(); 3014f8ff168de12eabdeb4b9437bf9402489ecf85cbEvan Cheng 302c66d0f2a9386cc7cb3237b8e3cace2b62a9c7dc8Jakob Stoklund Olesen // Delete the previous value, which should be short and continuous, 303be4f88a8b8bb3311e0dc4cde8533763d7923c3eaChris Lattner // because the 2-addr copy must be in the same MBB as the redef. 3041a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos interval.removeRange(DefIndex, RedefIndex); 305706515727c6d024015fffded2b3109a4f0ac5299Alkis Evlogimenos 30691725b75852443923b419fd23215194cfc65dd88Chris Lattner // The new value number (#1) is defined by the instruction we claimed 30791725b75852443923b419fd23215194cfc65dd88Chris Lattner // defined value #0. 3086e2968c85c1e162ee5bc813769eab223e3df0f15Lang Hames VNInfo *ValNo = interval.createValueCopy(OldValNo, VNInfoAllocator); 309857c4e01f85601cf2084adb860616256ee47c177Lang Hames 31091725b75852443923b419fd23215194cfc65dd88Chris Lattner // Value#0 is now defined by the 2-addr instruction. 3113b1088a2cc15a39c7a7b8dd95a56143f1dda6863Jakob Stoklund Olesen OldValNo->def = RedefIndex; 3121b2932024f098a6968645ac78d5848951d877c19Jakob Stoklund Olesen 313be4f88a8b8bb3311e0dc4cde8533763d7923c3eaChris Lattner // Add the new live interval which replaces the range for the input copy. 314be4f88a8b8bb3311e0dc4cde8533763d7923c3eaChris Lattner LiveRange LR(DefIndex, RedefIndex, ValNo); 3158a34229dcf484739119857988772572ef0cad9f2David Greene DEBUG(dbgs() << " replace range with " << LR); 3161a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos interval.addRange(LR); 3171a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos 3181a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // If this redefinition is dead, we need to add a dummy unit live 3191a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // range covering the def slot. 3206b098dee286cc6fe5a5a476464d92dec5602e406Owen Anderson if (MO.isDead()) 3212debd48ca790ac01be6e12e094fdf4fdcadc8364Jakob Stoklund Olesen interval.addRange(LiveRange(RedefIndex, RedefIndex.getDeadSlot(), 322233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames OldValNo)); 3231a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos 3248e6179fb134af929ee7c937c82d9dc1c9a104c5fBill Wendling DEBUG({ 3258a34229dcf484739119857988772572ef0cad9f2David Greene dbgs() << " RESULT: "; 3268a34229dcf484739119857988772572ef0cad9f2David Greene interval.print(dbgs(), tri_); 3278e6179fb134af929ee7c937c82d9dc1c9a104c5fBill Wendling }); 3283749943648772743c9c0e852553e50e6700a0c1bEvan Cheng } else if (lv_->isPHIJoin(interval.reg)) { 3291a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // In the case of PHI elimination, each variable definition is only 3301a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // live until the end of the block. We've already taken care of the 3311a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // rest of the live range. 332dcfe5f30b5e262971f601a65bebcc0367fef56c5Jakob Stoklund Olesen 3332debd48ca790ac01be6e12e094fdf4fdcadc8364Jakob Stoklund Olesen SlotIndex defIndex = MIIdx.getRegSlot(); 334fb11288109329cb736d9f49769581a0d0c23fe19Evan Cheng if (MO.isEarlyClobber()) 3352debd48ca790ac01be6e12e094fdf4fdcadc8364Jakob Stoklund Olesen defIndex = MIIdx.getRegSlot(true); 336752195e3c662c6b5db042cf897c984624720f3b8Evan Cheng 3373b1088a2cc15a39c7a7b8dd95a56143f1dda6863Jakob Stoklund Olesen VNInfo *ValNo = interval.getNextValue(defIndex, VNInfoAllocator); 3381b2932024f098a6968645ac78d5848951d877c19Jakob Stoklund Olesen 33974ab5eeffbd70f2387338e3ee8195be9f73e6dd8Lang Hames SlotIndex killIndex = getMBBEndIdx(mbb); 3407ecb38be0a533e7b9c7d3b8e9b5c8a6fa5f6b349Evan Cheng LiveRange LR(defIndex, killIndex, ValNo); 3411a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos interval.addRange(LR); 342857c4e01f85601cf2084adb860616256ee47c177Lang Hames ValNo->setHasPHIKill(true); 343dcfe5f30b5e262971f601a65bebcc0367fef56c5Jakob Stoklund Olesen DEBUG(dbgs() << " phi-join +" << LR); 3443749943648772743c9c0e852553e50e6700a0c1bEvan Cheng } else { 3453749943648772743c9c0e852553e50e6700a0c1bEvan Cheng llvm_unreachable("Multiply defined register"); 346dd2cc65f34f9b7bfda1cd0c42becedfc361d46f8Alkis Evlogimenos } 3471a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos } 348ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos 3498a34229dcf484739119857988772572ef0cad9f2David Greene DEBUG(dbgs() << '\n'); 350ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos} 351ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos 352f35fef7060c465dd7b578bf6339a18e8a8911888Chris Lattnervoid LiveIntervals::handlePhysicalRegisterDef(MachineBasicBlock *MBB, 353ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos MachineBasicBlock::iterator mi, 354233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames SlotIndex MIIdx, 3556b098dee286cc6fe5a5a476464d92dec5602e406Owen Anderson MachineOperand& MO, 3563b1088a2cc15a39c7a7b8dd95a56143f1dda6863Jakob Stoklund Olesen LiveInterval &interval) { 3571a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // A physical register cannot be live across basic block, so its 3581a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // lifetime must end somewhere in its defining basic block. 3594314268128be6d54c9a7f0709680e5a5b40f3ab3Jakob Stoklund Olesen DEBUG(dbgs() << "\t\tregister: " << PrintReg(interval.reg, tri_)); 3601a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos 361233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames SlotIndex baseIndex = MIIdx; 362d14614e6777771f8fec3062bcaf2986c189ac84dJakob Stoklund Olesen SlotIndex start = baseIndex.getRegSlot(MO.isEarlyClobber()); 363233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames SlotIndex end = start; 3641a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos 3651a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // If it is not used after definition, it is considered dead at 3661a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // the instruction defining it. Hence its interval is: 3671a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // [defSlot(def), defSlot(def)+1) 36839faac2531268b8555475796c6071556670dc290Dale Johannesen // For earlyclobbers, the defSlot was pushed back one; the extra 36939faac2531268b8555475796c6071556670dc290Dale Johannesen // advance below compensates. 3706b098dee286cc6fe5a5a476464d92dec5602e406Owen Anderson if (MO.isDead()) { 3718a34229dcf484739119857988772572ef0cad9f2David Greene DEBUG(dbgs() << " dead"); 3722debd48ca790ac01be6e12e094fdf4fdcadc8364Jakob Stoklund Olesen end = start.getDeadSlot(); 373ab4b66d4c279e8cd9e448687020fc838e7881dbcChris Lattner goto exit; 3741a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos } 375ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos 3761a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // If it is not dead on definition, it must be killed by a 3771a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // subsequent instruction. Hence its interval is: 3781a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // [defSlot(def), useSlot(kill)+1) 379233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames baseIndex = baseIndex.getNextIndex(); 3805ab6f5fe666d0e3403d9b777324d1a1999118153Chris Lattner while (++mi != MBB->end()) { 381233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames 382bd63520161629385ff5a0b037eccc770d8d15289Dale Johannesen if (mi->isDebugValue()) 383bd63520161629385ff5a0b037eccc770d8d15289Dale Johannesen continue; 384233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames if (getInstructionFromIndex(baseIndex) == 0) 385233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames baseIndex = indexes_->getNextNonNullIndex(baseIndex); 386233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames 3876130f66eaae89f8878590796977678afa8448926Evan Cheng if (mi->killsRegister(interval.reg, tri_)) { 3888a34229dcf484739119857988772572ef0cad9f2David Greene DEBUG(dbgs() << " killed"); 3892debd48ca790ac01be6e12e094fdf4fdcadc8364Jakob Stoklund Olesen end = baseIndex.getRegSlot(); 390ab4b66d4c279e8cd9e448687020fc838e7881dbcChris Lattner goto exit; 391c45288e06bfe7d0b0e74eff350d280fa6c944373Evan Cheng } else { 3921015ba7018c87f48cc7bb45a564eb4a27241e76aEvan Cheng int DefIdx = mi->findRegisterDefOperandIdx(interval.reg,false,false,tri_); 393c45288e06bfe7d0b0e74eff350d280fa6c944373Evan Cheng if (DefIdx != -1) { 394c45288e06bfe7d0b0e74eff350d280fa6c944373Evan Cheng if (mi->isRegTiedToUseOperand(DefIdx)) { 395c45288e06bfe7d0b0e74eff350d280fa6c944373Evan Cheng // Two-address instruction. 3967e899cbb9127c02c58f6e774186a533b0d00681dJakob Stoklund Olesen end = baseIndex.getRegSlot(mi->getOperand(DefIdx).isEarlyClobber()); 397c45288e06bfe7d0b0e74eff350d280fa6c944373Evan Cheng } else { 398c45288e06bfe7d0b0e74eff350d280fa6c944373Evan Cheng // Another instruction redefines the register before it is ever read. 399bd63520161629385ff5a0b037eccc770d8d15289Dale Johannesen // Then the register is essentially dead at the instruction that 400bd63520161629385ff5a0b037eccc770d8d15289Dale Johannesen // defines it. Hence its interval is: 401c45288e06bfe7d0b0e74eff350d280fa6c944373Evan Cheng // [defSlot(def), defSlot(def)+1) 4028a34229dcf484739119857988772572ef0cad9f2David Greene DEBUG(dbgs() << " dead"); 4032debd48ca790ac01be6e12e094fdf4fdcadc8364Jakob Stoklund Olesen end = start.getDeadSlot(); 404c45288e06bfe7d0b0e74eff350d280fa6c944373Evan Cheng } 405c45288e06bfe7d0b0e74eff350d280fa6c944373Evan Cheng goto exit; 406c45288e06bfe7d0b0e74eff350d280fa6c944373Evan Cheng } 407f35fef7060c465dd7b578bf6339a18e8a8911888Chris Lattner } 4081b2932024f098a6968645ac78d5848951d877c19Jakob Stoklund Olesen 409233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames baseIndex = baseIndex.getNextIndex(); 4101a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos } 4111b2932024f098a6968645ac78d5848951d877c19Jakob Stoklund Olesen 4125ab6f5fe666d0e3403d9b777324d1a1999118153Chris Lattner // The only case we should have a dead physreg here without a killing or 4135ab6f5fe666d0e3403d9b777324d1a1999118153Chris Lattner // instruction where we know it's dead is if it is live-in to the function 414d521bc983b32da71b85d42dd30da87079afa5728Evan Cheng // and never used. Another possible case is the implicit use of the 415d521bc983b32da71b85d42dd30da87079afa5728Evan Cheng // physical register has been deleted by two-address pass. 4162debd48ca790ac01be6e12e094fdf4fdcadc8364Jakob Stoklund Olesen end = start.getDeadSlot(); 41702ba13c9897ae2b19f9201e57460d7ee2b753a0bAlkis Evlogimenos 418ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenosexit: 4191a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos assert(start < end && "did not find end of interval?"); 420f768bba43f5c036039851d2fcca8212edca18467Chris Lattner 42124a3cc4c83e5edb25fadf7b8979a26b4451795c6Evan Cheng // Already exists? Extend old live interval. 42231cc3ec3308c8fafd9865388214ae11662a71af4Jakob Stoklund Olesen VNInfo *ValNo = interval.getVNInfoAt(start); 42331cc3ec3308c8fafd9865388214ae11662a71af4Jakob Stoklund Olesen bool Extend = ValNo != 0; 42431cc3ec3308c8fafd9865388214ae11662a71af4Jakob Stoklund Olesen if (!Extend) 4253b1088a2cc15a39c7a7b8dd95a56143f1dda6863Jakob Stoklund Olesen ValNo = interval.getNextValue(start, VNInfoAllocator); 4267ecb38be0a533e7b9c7d3b8e9b5c8a6fa5f6b349Evan Cheng LiveRange LR(start, end, ValNo); 4271a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos interval.addRange(LR); 4288a34229dcf484739119857988772572ef0cad9f2David Greene DEBUG(dbgs() << " +" << LR << '\n'); 429ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos} 430ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos 431f35fef7060c465dd7b578bf6339a18e8a8911888Chris Lattnervoid LiveIntervals::handleRegisterDef(MachineBasicBlock *MBB, 432f35fef7060c465dd7b578bf6339a18e8a8911888Chris Lattner MachineBasicBlock::iterator MI, 433233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames SlotIndex MIIdx, 434ef0732d25a9882c947984ae3f2afbef5463ba00fEvan Cheng MachineOperand& MO, 435ef0732d25a9882c947984ae3f2afbef5463ba00fEvan Cheng unsigned MOIdx) { 4366b098dee286cc6fe5a5a476464d92dec5602e406Owen Anderson if (TargetRegisterInfo::isVirtualRegister(MO.getReg())) 437ef0732d25a9882c947984ae3f2afbef5463ba00fEvan Cheng handleVirtualRegisterDef(MBB, MI, MIIdx, MO, MOIdx, 4386b098dee286cc6fe5a5a476464d92dec5602e406Owen Anderson getOrCreateInterval(MO.getReg())); 4393b1088a2cc15a39c7a7b8dd95a56143f1dda6863Jakob Stoklund Olesen else 440c45288e06bfe7d0b0e74eff350d280fa6c944373Evan Cheng handlePhysicalRegisterDef(MBB, MI, MIIdx, MO, 4413b1088a2cc15a39c7a7b8dd95a56143f1dda6863Jakob Stoklund Olesen getOrCreateInterval(MO.getReg())); 4424d46e1e521c0df1990ea50f8146d22bd77ea71a6Alkis Evlogimenos} 4434d46e1e521c0df1990ea50f8146d22bd77ea71a6Alkis Evlogimenos 444b371f457b0ea4a652a9f526ba4375c80ae542252Evan Chengvoid LiveIntervals::handleLiveInRegister(MachineBasicBlock *MBB, 445233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames SlotIndex MIIdx, 4464465b6f6b2ebd061f4f321e666b47d540651f686Lang Hames LiveInterval &interval) { 4474314268128be6d54c9a7f0709680e5a5b40f3ab3Jakob Stoklund Olesen DEBUG(dbgs() << "\t\tlivein register: " << PrintReg(interval.reg, tri_)); 448b371f457b0ea4a652a9f526ba4375c80ae542252Evan Cheng 449b371f457b0ea4a652a9f526ba4375c80ae542252Evan Cheng // Look for kills, if it reaches a def before it's killed, then it shouldn't 450b371f457b0ea4a652a9f526ba4375c80ae542252Evan Cheng // be considered a livein. 451b371f457b0ea4a652a9f526ba4375c80ae542252Evan Cheng MachineBasicBlock::iterator mi = MBB->begin(); 4524507f089d48c5adb454cd12b68333d5590ce05ddEvan Cheng MachineBasicBlock::iterator E = MBB->end(); 4534507f089d48c5adb454cd12b68333d5590ce05ddEvan Cheng // Skip over DBG_VALUE at the start of the MBB. 4544507f089d48c5adb454cd12b68333d5590ce05ddEvan Cheng if (mi != E && mi->isDebugValue()) { 4554507f089d48c5adb454cd12b68333d5590ce05ddEvan Cheng while (++mi != E && mi->isDebugValue()) 4564507f089d48c5adb454cd12b68333d5590ce05ddEvan Cheng ; 4574507f089d48c5adb454cd12b68333d5590ce05ddEvan Cheng if (mi == E) 4584507f089d48c5adb454cd12b68333d5590ce05ddEvan Cheng // MBB is empty except for DBG_VALUE's. 4594507f089d48c5adb454cd12b68333d5590ce05ddEvan Cheng return; 4604507f089d48c5adb454cd12b68333d5590ce05ddEvan Cheng } 4614507f089d48c5adb454cd12b68333d5590ce05ddEvan Cheng 462233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames SlotIndex baseIndex = MIIdx; 463233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames SlotIndex start = baseIndex; 464233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames if (getInstructionFromIndex(baseIndex) == 0) 465233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames baseIndex = indexes_->getNextNonNullIndex(baseIndex); 466233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames 467233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames SlotIndex end = baseIndex; 4680076c616e8abc2ecf36600a7ac20ec784420cdc4Evan Cheng bool SeenDefUse = false; 469b371f457b0ea4a652a9f526ba4375c80ae542252Evan Cheng 470bd63520161629385ff5a0b037eccc770d8d15289Dale Johannesen while (mi != E) { 4711d0aeabe3fce2ce6610e988b36582b47a7684f74Dale Johannesen if (mi->killsRegister(interval.reg, tri_)) { 4721d0aeabe3fce2ce6610e988b36582b47a7684f74Dale Johannesen DEBUG(dbgs() << " killed"); 4732debd48ca790ac01be6e12e094fdf4fdcadc8364Jakob Stoklund Olesen end = baseIndex.getRegSlot(); 4741d0aeabe3fce2ce6610e988b36582b47a7684f74Dale Johannesen SeenDefUse = true; 4751d0aeabe3fce2ce6610e988b36582b47a7684f74Dale Johannesen break; 4761015ba7018c87f48cc7bb45a564eb4a27241e76aEvan Cheng } else if (mi->definesRegister(interval.reg, tri_)) { 4771d0aeabe3fce2ce6610e988b36582b47a7684f74Dale Johannesen // Another instruction redefines the register before it is ever read. 4781d0aeabe3fce2ce6610e988b36582b47a7684f74Dale Johannesen // Then the register is essentially dead at the instruction that defines 4791d0aeabe3fce2ce6610e988b36582b47a7684f74Dale Johannesen // it. Hence its interval is: 4801d0aeabe3fce2ce6610e988b36582b47a7684f74Dale Johannesen // [defSlot(def), defSlot(def)+1) 4811d0aeabe3fce2ce6610e988b36582b47a7684f74Dale Johannesen DEBUG(dbgs() << " dead"); 4822debd48ca790ac01be6e12e094fdf4fdcadc8364Jakob Stoklund Olesen end = start.getDeadSlot(); 4831d0aeabe3fce2ce6610e988b36582b47a7684f74Dale Johannesen SeenDefUse = true; 4841d0aeabe3fce2ce6610e988b36582b47a7684f74Dale Johannesen break; 485bd63520161629385ff5a0b037eccc770d8d15289Dale Johannesen } 4861d0aeabe3fce2ce6610e988b36582b47a7684f74Dale Johannesen 4874507f089d48c5adb454cd12b68333d5590ce05ddEvan Cheng while (++mi != E && mi->isDebugValue()) 4884507f089d48c5adb454cd12b68333d5590ce05ddEvan Cheng // Skip over DBG_VALUE. 4894507f089d48c5adb454cd12b68333d5590ce05ddEvan Cheng ; 4904507f089d48c5adb454cd12b68333d5590ce05ddEvan Cheng if (mi != E) 491233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames baseIndex = indexes_->getNextNonNullIndex(baseIndex); 492b371f457b0ea4a652a9f526ba4375c80ae542252Evan Cheng } 493b371f457b0ea4a652a9f526ba4375c80ae542252Evan Cheng 49475611fb4e6ab253be30ac29a2b15e9bf8c1d146eEvan Cheng // Live-in register might not be used at all. 4950076c616e8abc2ecf36600a7ac20ec784420cdc4Evan Cheng if (!SeenDefUse) { 4964465b6f6b2ebd061f4f321e666b47d540651f686Lang Hames DEBUG(dbgs() << " live through"); 4974465b6f6b2ebd061f4f321e666b47d540651f686Lang Hames end = getMBBEndIdx(MBB); 49824a3cc4c83e5edb25fadf7b8979a26b4451795c6Evan Cheng } 49924a3cc4c83e5edb25fadf7b8979a26b4451795c6Evan Cheng 5006e2968c85c1e162ee5bc813769eab223e3df0f15Lang Hames SlotIndex defIdx = getMBBStartIdx(MBB); 5016e2968c85c1e162ee5bc813769eab223e3df0f15Lang Hames assert(getInstructionFromIndex(defIdx) == 0 && 5026e2968c85c1e162ee5bc813769eab223e3df0f15Lang Hames "PHI def index points at actual instruction."); 5033b1088a2cc15a39c7a7b8dd95a56143f1dda6863Jakob Stoklund Olesen VNInfo *vni = interval.getNextValue(defIdx, VNInfoAllocator); 504d21c31610c4a10e9e638f4221b5df89ea932e258Lang Hames vni->setIsPHIDef(true); 505d21c31610c4a10e9e638f4221b5df89ea932e258Lang Hames LiveRange LR(start, end, vni); 5063de23e6f6cf337451a0934159da494d645b93133Jakob Stoklund Olesen 5079b25b8ca24d6df2e097741dcc15016772ee4eda7Jim Laskey interval.addRange(LR); 5088a34229dcf484739119857988772572ef0cad9f2David Greene DEBUG(dbgs() << " +" << LR << '\n'); 509b371f457b0ea4a652a9f526ba4375c80ae542252Evan Cheng} 510b371f457b0ea4a652a9f526ba4375c80ae542252Evan Cheng 511ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos/// computeIntervals - computes the live intervals for virtual 5124d46e1e521c0df1990ea50f8146d22bd77ea71a6Alkis Evlogimenos/// registers. for some ordering of the machine instructions [1,N] a 51308cec00588ec1a8fa85b208555f006d7396ae7a4Alkis Evlogimenos/// live interval is an interval [i, j) where 1 <= i <= j < N for 514ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos/// which a variable is live 5151b2932024f098a6968645ac78d5848951d877c19Jakob Stoklund Olesenvoid LiveIntervals::computeIntervals() { 5168a34229dcf484739119857988772572ef0cad9f2David Greene DEBUG(dbgs() << "********** COMPUTING LIVE INTERVALS **********\n" 5178e6179fb134af929ee7c937c82d9dc1c9a104c5fBill Wendling << "********** Function: " 5188e6179fb134af929ee7c937c82d9dc1c9a104c5fBill Wendling << ((Value*)mf_->getFunction())->getName() << '\n'); 519d129d73b725e32d2fc0c87f392c239db8801e922Evan Cheng 52034e85d0307e3c17e5061622dccf8a20e5457b099Jakob Stoklund Olesen RegMaskBlocks.resize(mf_->getNumBlockIDs()); 52134e85d0307e3c17e5061622dccf8a20e5457b099Jakob Stoklund Olesen 522d129d73b725e32d2fc0c87f392c239db8801e922Evan Cheng SmallVector<unsigned, 8> UndefUses; 523428b92eb83b457b71d29d1d4b7900d36a0ce9a53Chris Lattner for (MachineFunction::iterator MBBI = mf_->begin(), E = mf_->end(); 524428b92eb83b457b71d29d1d4b7900d36a0ce9a53Chris Lattner MBBI != E; ++MBBI) { 525428b92eb83b457b71d29d1d4b7900d36a0ce9a53Chris Lattner MachineBasicBlock *MBB = MBBI; 52634e85d0307e3c17e5061622dccf8a20e5457b099Jakob Stoklund Olesen RegMaskBlocks[MBB->getNumber()].first = RegMaskSlots.size(); 52734e85d0307e3c17e5061622dccf8a20e5457b099Jakob Stoklund Olesen 52800a99a35840451a291eb61a192a750908a4073aeEvan Cheng if (MBB->empty()) 52900a99a35840451a291eb61a192a750908a4073aeEvan Cheng continue; 53000a99a35840451a291eb61a192a750908a4073aeEvan Cheng 531134eb73fc35e6ead3cfd3ed5024d0d7efa507441Owen Anderson // Track the index of the current machine instr. 532233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames SlotIndex MIIndex = getMBBStartIdx(MBB); 533ad98f795d0dba3db721139a8a74a98acdce0ff60Bob Wilson DEBUG(dbgs() << "BB#" << MBB->getNumber() 534ad98f795d0dba3db721139a8a74a98acdce0ff60Bob Wilson << ":\t\t# derived from " << MBB->getName() << "\n"); 5351a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos 536cb406c25973b4e88a6c10ad839ef1beeb3664715Dan Gohman // Create intervals for live-ins to this BB first. 53781bf03eb5cd68243eabb52505105aa5f4a831bf3Dan Gohman for (MachineBasicBlock::livein_iterator LI = MBB->livein_begin(), 538cb406c25973b4e88a6c10ad839ef1beeb3664715Dan Gohman LE = MBB->livein_end(); LI != LE; ++LI) { 539cb406c25973b4e88a6c10ad839ef1beeb3664715Dan Gohman handleLiveInRegister(MBB, MIIndex, getOrCreateInterval(*LI)); 540dffb2e83ed2546226d09c40aa43524e2392322daChris Lattner } 5411b2932024f098a6968645ac78d5848951d877c19Jakob Stoklund Olesen 54299500aeb7c9a05db57e228544a3f81de2faf24efOwen Anderson // Skip over empty initial indices. 543233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames if (getInstructionFromIndex(MIIndex) == 0) 544233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames MIIndex = indexes_->getNextNonNullIndex(MIIndex); 5451b2932024f098a6968645ac78d5848951d877c19Jakob Stoklund Olesen 5461caedd056dbc3eda1537ad8251323bd985819b80Dale Johannesen for (MachineBasicBlock::iterator MI = MBB->begin(), miEnd = MBB->end(); 5471caedd056dbc3eda1537ad8251323bd985819b80Dale Johannesen MI != miEnd; ++MI) { 5488a34229dcf484739119857988772572ef0cad9f2David Greene DEBUG(dbgs() << MIIndex << "\t" << *MI); 549518bb53485df640d7b7e3f6b0544099020c42aa7Chris Lattner if (MI->isDebugValue()) 5501caedd056dbc3eda1537ad8251323bd985819b80Dale Johannesen continue; 5513fd3a840c50fe4ede1b200be18990bc955c536fdJakob Stoklund Olesen assert(indexes_->getInstructionFromIndex(MIIndex) == MI && 5523fd3a840c50fe4ede1b200be18990bc955c536fdJakob Stoklund Olesen "Lost SlotIndex synchronization"); 5531a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos 554438f7bc67cf235ccee7e6f7ac7f4ae2186eb8020Evan Cheng // Handle defs. 555428b92eb83b457b71d29d1d4b7900d36a0ce9a53Chris Lattner for (int i = MI->getNumOperands() - 1; i >= 0; --i) { 556428b92eb83b457b71d29d1d4b7900d36a0ce9a53Chris Lattner MachineOperand &MO = MI->getOperand(i); 5573fd3a840c50fe4ede1b200be18990bc955c536fdJakob Stoklund Olesen 5583fd3a840c50fe4ede1b200be18990bc955c536fdJakob Stoklund Olesen // Collect register masks. 5593fd3a840c50fe4ede1b200be18990bc955c536fdJakob Stoklund Olesen if (MO.isRegMask()) { 5603fd3a840c50fe4ede1b200be18990bc955c536fdJakob Stoklund Olesen RegMaskSlots.push_back(MIIndex.getRegSlot()); 5613fd3a840c50fe4ede1b200be18990bc955c536fdJakob Stoklund Olesen RegMaskBits.push_back(MO.getRegMask()); 5623fd3a840c50fe4ede1b200be18990bc955c536fdJakob Stoklund Olesen continue; 5633fd3a840c50fe4ede1b200be18990bc955c536fdJakob Stoklund Olesen } 5643fd3a840c50fe4ede1b200be18990bc955c536fdJakob Stoklund Olesen 565d129d73b725e32d2fc0c87f392c239db8801e922Evan Cheng if (!MO.isReg() || !MO.getReg()) 566d129d73b725e32d2fc0c87f392c239db8801e922Evan Cheng continue; 567d129d73b725e32d2fc0c87f392c239db8801e922Evan Cheng 5681a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // handle register defs - build intervals 569d129d73b725e32d2fc0c87f392c239db8801e922Evan Cheng if (MO.isDef()) 570ef0732d25a9882c947984ae3f2afbef5463ba00fEvan Cheng handleRegisterDef(MBB, MI, MIIndex, MO, i); 571d129d73b725e32d2fc0c87f392c239db8801e922Evan Cheng else if (MO.isUndef()) 572d129d73b725e32d2fc0c87f392c239db8801e922Evan Cheng UndefUses.push_back(MO.getReg()); 5731a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos } 5741b2932024f098a6968645ac78d5848951d877c19Jakob Stoklund Olesen 575233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames // Move to the next instr slot. 576233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames MIIndex = indexes_->getNextNonNullIndex(MIIndex); 577ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos } 57834e85d0307e3c17e5061622dccf8a20e5457b099Jakob Stoklund Olesen 57934e85d0307e3c17e5061622dccf8a20e5457b099Jakob Stoklund Olesen // Compute the number of register mask instructions in this block. 58034e85d0307e3c17e5061622dccf8a20e5457b099Jakob Stoklund Olesen std::pair<unsigned, unsigned> &RMB = RegMaskBlocks[MBB->getNumber()]; 58134e85d0307e3c17e5061622dccf8a20e5457b099Jakob Stoklund Olesen RMB.second = RegMaskSlots.size() - RMB.first;; 5821a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos } 583d129d73b725e32d2fc0c87f392c239db8801e922Evan Cheng 584d129d73b725e32d2fc0c87f392c239db8801e922Evan Cheng // Create empty intervals for registers defined by implicit_def's (except 585d129d73b725e32d2fc0c87f392c239db8801e922Evan Cheng // for those implicit_def that define values which are liveout of their 586d129d73b725e32d2fc0c87f392c239db8801e922Evan Cheng // blocks. 587d129d73b725e32d2fc0c87f392c239db8801e922Evan Cheng for (unsigned i = 0, e = UndefUses.size(); i != e; ++i) { 588d129d73b725e32d2fc0c87f392c239db8801e922Evan Cheng unsigned UndefReg = UndefUses[i]; 589d129d73b725e32d2fc0c87f392c239db8801e922Evan Cheng (void)getOrCreateInterval(UndefReg); 590d129d73b725e32d2fc0c87f392c239db8801e922Evan Cheng } 591ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos} 592b27ef248f579b354aab434f63c417ab1103e47e2Alkis Evlogimenos 59303857b29d8271a23943254579e6cf7b7df4b1bd3Owen AndersonLiveInterval* LiveIntervals::createInterval(unsigned reg) { 5940a1fcce09230e9b4bd30a8f07447aa075dce7470Evan Cheng float Weight = TargetRegisterInfo::isPhysicalRegister(reg) ? HUGE_VALF : 0.0F; 59503857b29d8271a23943254579e6cf7b7df4b1bd3Owen Anderson return new LiveInterval(reg, Weight); 5969a8b490735d216435862a3d52e669357f165550fAlkis Evlogimenos} 597f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng 5980a1fcce09230e9b4bd30a8f07447aa075dce7470Evan Cheng/// dupInterval - Duplicate a live interval. The caller is responsible for 5990a1fcce09230e9b4bd30a8f07447aa075dce7470Evan Cheng/// managing the allocated memory. 6000a1fcce09230e9b4bd30a8f07447aa075dce7470Evan ChengLiveInterval* LiveIntervals::dupInterval(LiveInterval *li) { 6010a1fcce09230e9b4bd30a8f07447aa075dce7470Evan Cheng LiveInterval *NewLI = createInterval(li->reg); 60290f95f88c6ce09c6744777dc9d140c3c77203b92Evan Cheng NewLI->Copy(*li, mri_, getVNInfoAllocator()); 6030a1fcce09230e9b4bd30a8f07447aa075dce7470Evan Cheng return NewLI; 6040a1fcce09230e9b4bd30a8f07447aa075dce7470Evan Cheng} 6050a1fcce09230e9b4bd30a8f07447aa075dce7470Evan Cheng 60611513e5d1e1b40e6113668e4b4357596f33fa6c6Jakob Stoklund Olesen/// shrinkToUses - After removing some uses of a register, shrink its live 60711513e5d1e1b40e6113668e4b4357596f33fa6c6Jakob Stoklund Olesen/// range to just the remaining uses. This method does not compute reaching 60811513e5d1e1b40e6113668e4b4357596f33fa6c6Jakob Stoklund Olesen/// defs for new uses, and it doesn't remove dead defs. 6096a3dbd3b25bbc99bd1a233d6a74ddea3493ba6acJakob Stoklund Olesenbool LiveIntervals::shrinkToUses(LiveInterval *li, 6100d8ccaa5c8db820b5b93f37e51563148c57ba6b8Jakob Stoklund Olesen SmallVectorImpl<MachineInstr*> *dead) { 61111513e5d1e1b40e6113668e4b4357596f33fa6c6Jakob Stoklund Olesen DEBUG(dbgs() << "Shrink: " << *li << '\n'); 61211513e5d1e1b40e6113668e4b4357596f33fa6c6Jakob Stoklund Olesen assert(TargetRegisterInfo::isVirtualRegister(li->reg) 613567cdbab28077ea1801ebff3d4291d4006d88ca3Lang Hames && "Can only shrink virtual registers"); 61411513e5d1e1b40e6113668e4b4357596f33fa6c6Jakob Stoklund Olesen // Find all the values used, including PHI kills. 61511513e5d1e1b40e6113668e4b4357596f33fa6c6Jakob Stoklund Olesen SmallVector<std::pair<SlotIndex, VNInfo*>, 16> WorkList; 61611513e5d1e1b40e6113668e4b4357596f33fa6c6Jakob Stoklund Olesen 617031432f9ad24963282b7f71bd0592080f6229d20Jakob Stoklund Olesen // Blocks that have already been added to WorkList as live-out. 618031432f9ad24963282b7f71bd0592080f6229d20Jakob Stoklund Olesen SmallPtrSet<MachineBasicBlock*, 16> LiveOut; 619031432f9ad24963282b7f71bd0592080f6229d20Jakob Stoklund Olesen 62011513e5d1e1b40e6113668e4b4357596f33fa6c6Jakob Stoklund Olesen // Visit all instructions reading li->reg. 62111513e5d1e1b40e6113668e4b4357596f33fa6c6Jakob Stoklund Olesen for (MachineRegisterInfo::reg_iterator I = mri_->reg_begin(li->reg); 62211513e5d1e1b40e6113668e4b4357596f33fa6c6Jakob Stoklund Olesen MachineInstr *UseMI = I.skipInstruction();) { 62311513e5d1e1b40e6113668e4b4357596f33fa6c6Jakob Stoklund Olesen if (UseMI->isDebugValue() || !UseMI->readsVirtualRegister(li->reg)) 62411513e5d1e1b40e6113668e4b4357596f33fa6c6Jakob Stoklund Olesen continue; 6256c9cc21d85cdef79b971f710ace287f3a2f847a3Jakob Stoklund Olesen SlotIndex Idx = getInstructionIndex(UseMI).getRegSlot(); 626f054e198197122011fc80b673f35333bc3e58c98Jakob Stoklund Olesen // Note: This intentionally picks up the wrong VNI in case of an EC redef. 627f054e198197122011fc80b673f35333bc3e58c98Jakob Stoklund Olesen // See below. 628f054e198197122011fc80b673f35333bc3e58c98Jakob Stoklund Olesen VNInfo *VNI = li->getVNInfoBefore(Idx); 6299ef931e71c06a0390d6387859843be1d6d4daad6Jakob Stoklund Olesen if (!VNI) { 6309ef931e71c06a0390d6387859843be1d6d4daad6Jakob Stoklund Olesen // This shouldn't happen: readsVirtualRegister returns true, but there is 6319ef931e71c06a0390d6387859843be1d6d4daad6Jakob Stoklund Olesen // no live value. It is likely caused by a target getting <undef> flags 6329ef931e71c06a0390d6387859843be1d6d4daad6Jakob Stoklund Olesen // wrong. 6339ef931e71c06a0390d6387859843be1d6d4daad6Jakob Stoklund Olesen DEBUG(dbgs() << Idx << '\t' << *UseMI 6349ef931e71c06a0390d6387859843be1d6d4daad6Jakob Stoklund Olesen << "Warning: Instr claims to read non-existent value in " 6359ef931e71c06a0390d6387859843be1d6d4daad6Jakob Stoklund Olesen << *li << '\n'); 6369ef931e71c06a0390d6387859843be1d6d4daad6Jakob Stoklund Olesen continue; 6379ef931e71c06a0390d6387859843be1d6d4daad6Jakob Stoklund Olesen } 638f054e198197122011fc80b673f35333bc3e58c98Jakob Stoklund Olesen // Special case: An early-clobber tied operand reads and writes the 639f054e198197122011fc80b673f35333bc3e58c98Jakob Stoklund Olesen // register one slot early. The getVNInfoBefore call above would have 640f054e198197122011fc80b673f35333bc3e58c98Jakob Stoklund Olesen // picked up the value defined by UseMI. Adjust the kill slot and value. 641f054e198197122011fc80b673f35333bc3e58c98Jakob Stoklund Olesen if (SlotIndex::isSameInstr(VNI->def, Idx)) { 642f054e198197122011fc80b673f35333bc3e58c98Jakob Stoklund Olesen Idx = VNI->def; 6436c9cc21d85cdef79b971f710ace287f3a2f847a3Jakob Stoklund Olesen VNI = li->getVNInfoBefore(Idx); 64411513e5d1e1b40e6113668e4b4357596f33fa6c6Jakob Stoklund Olesen assert(VNI && "Early-clobber tied value not available"); 64511513e5d1e1b40e6113668e4b4357596f33fa6c6Jakob Stoklund Olesen } 64611513e5d1e1b40e6113668e4b4357596f33fa6c6Jakob Stoklund Olesen WorkList.push_back(std::make_pair(Idx, VNI)); 64711513e5d1e1b40e6113668e4b4357596f33fa6c6Jakob Stoklund Olesen } 64811513e5d1e1b40e6113668e4b4357596f33fa6c6Jakob Stoklund Olesen 64911513e5d1e1b40e6113668e4b4357596f33fa6c6Jakob Stoklund Olesen // Create a new live interval with only minimal live segments per def. 65011513e5d1e1b40e6113668e4b4357596f33fa6c6Jakob Stoklund Olesen LiveInterval NewLI(li->reg, 0); 65111513e5d1e1b40e6113668e4b4357596f33fa6c6Jakob Stoklund Olesen for (LiveInterval::vni_iterator I = li->vni_begin(), E = li->vni_end(); 65211513e5d1e1b40e6113668e4b4357596f33fa6c6Jakob Stoklund Olesen I != E; ++I) { 65311513e5d1e1b40e6113668e4b4357596f33fa6c6Jakob Stoklund Olesen VNInfo *VNI = *I; 65411513e5d1e1b40e6113668e4b4357596f33fa6c6Jakob Stoklund Olesen if (VNI->isUnused()) 65511513e5d1e1b40e6113668e4b4357596f33fa6c6Jakob Stoklund Olesen continue; 6561f81e316b042c02c841801a71e7439e166ffa2a0Jakob Stoklund Olesen NewLI.addRange(LiveRange(VNI->def, VNI->def.getDeadSlot(), VNI)); 65711513e5d1e1b40e6113668e4b4357596f33fa6c6Jakob Stoklund Olesen } 65811513e5d1e1b40e6113668e4b4357596f33fa6c6Jakob Stoklund Olesen 659e0ab24532cc11f082d722ab169080322b39afeceJakob Stoklund Olesen // Keep track of the PHIs that are in use. 660e0ab24532cc11f082d722ab169080322b39afeceJakob Stoklund Olesen SmallPtrSet<VNInfo*, 8> UsedPHIs; 661e0ab24532cc11f082d722ab169080322b39afeceJakob Stoklund Olesen 66211513e5d1e1b40e6113668e4b4357596f33fa6c6Jakob Stoklund Olesen // Extend intervals to reach all uses in WorkList. 66311513e5d1e1b40e6113668e4b4357596f33fa6c6Jakob Stoklund Olesen while (!WorkList.empty()) { 66411513e5d1e1b40e6113668e4b4357596f33fa6c6Jakob Stoklund Olesen SlotIndex Idx = WorkList.back().first; 66511513e5d1e1b40e6113668e4b4357596f33fa6c6Jakob Stoklund Olesen VNInfo *VNI = WorkList.back().second; 66611513e5d1e1b40e6113668e4b4357596f33fa6c6Jakob Stoklund Olesen WorkList.pop_back(); 6676c9cc21d85cdef79b971f710ace287f3a2f847a3Jakob Stoklund Olesen const MachineBasicBlock *MBB = getMBBFromIndex(Idx.getPrevSlot()); 66811513e5d1e1b40e6113668e4b4357596f33fa6c6Jakob Stoklund Olesen SlotIndex BlockStart = getMBBStartIdx(MBB); 669e0ab24532cc11f082d722ab169080322b39afeceJakob Stoklund Olesen 670e0ab24532cc11f082d722ab169080322b39afeceJakob Stoklund Olesen // Extend the live range for VNI to be live at Idx. 6716c9cc21d85cdef79b971f710ace287f3a2f847a3Jakob Stoklund Olesen if (VNInfo *ExtVNI = NewLI.extendInBlock(BlockStart, Idx)) { 6724b11a70f7a63dc4c051a96a90ed6687eb0595cdaNick Lewycky (void)ExtVNI; 673e0ab24532cc11f082d722ab169080322b39afeceJakob Stoklund Olesen assert(ExtVNI == VNI && "Unexpected existing value number"); 674e0ab24532cc11f082d722ab169080322b39afeceJakob Stoklund Olesen // Is this a PHIDef we haven't seen before? 675c29d9b3495a2d87af524ad5c4b62f46c4265d828Jakob Stoklund Olesen if (!VNI->isPHIDef() || VNI->def != BlockStart || !UsedPHIs.insert(VNI)) 676e0ab24532cc11f082d722ab169080322b39afeceJakob Stoklund Olesen continue; 677e0ab24532cc11f082d722ab169080322b39afeceJakob Stoklund Olesen // The PHI is live, make sure the predecessors are live-out. 678e0ab24532cc11f082d722ab169080322b39afeceJakob Stoklund Olesen for (MachineBasicBlock::const_pred_iterator PI = MBB->pred_begin(), 679e0ab24532cc11f082d722ab169080322b39afeceJakob Stoklund Olesen PE = MBB->pred_end(); PI != PE; ++PI) { 680031432f9ad24963282b7f71bd0592080f6229d20Jakob Stoklund Olesen if (!LiveOut.insert(*PI)) 681031432f9ad24963282b7f71bd0592080f6229d20Jakob Stoklund Olesen continue; 6826c9cc21d85cdef79b971f710ace287f3a2f847a3Jakob Stoklund Olesen SlotIndex Stop = getMBBEndIdx(*PI); 683e0ab24532cc11f082d722ab169080322b39afeceJakob Stoklund Olesen // A predecessor is not required to have a live-out value for a PHI. 6846c9cc21d85cdef79b971f710ace287f3a2f847a3Jakob Stoklund Olesen if (VNInfo *PVNI = li->getVNInfoBefore(Stop)) 685e0ab24532cc11f082d722ab169080322b39afeceJakob Stoklund Olesen WorkList.push_back(std::make_pair(Stop, PVNI)); 68611513e5d1e1b40e6113668e4b4357596f33fa6c6Jakob Stoklund Olesen } 68711513e5d1e1b40e6113668e4b4357596f33fa6c6Jakob Stoklund Olesen continue; 68811513e5d1e1b40e6113668e4b4357596f33fa6c6Jakob Stoklund Olesen } 68911513e5d1e1b40e6113668e4b4357596f33fa6c6Jakob Stoklund Olesen 69011513e5d1e1b40e6113668e4b4357596f33fa6c6Jakob Stoklund Olesen // VNI is live-in to MBB. 69111513e5d1e1b40e6113668e4b4357596f33fa6c6Jakob Stoklund Olesen DEBUG(dbgs() << " live-in at " << BlockStart << '\n'); 6926c9cc21d85cdef79b971f710ace287f3a2f847a3Jakob Stoklund Olesen NewLI.addRange(LiveRange(BlockStart, Idx, VNI)); 69311513e5d1e1b40e6113668e4b4357596f33fa6c6Jakob Stoklund Olesen 69411513e5d1e1b40e6113668e4b4357596f33fa6c6Jakob Stoklund Olesen // Make sure VNI is live-out from the predecessors. 69511513e5d1e1b40e6113668e4b4357596f33fa6c6Jakob Stoklund Olesen for (MachineBasicBlock::const_pred_iterator PI = MBB->pred_begin(), 69611513e5d1e1b40e6113668e4b4357596f33fa6c6Jakob Stoklund Olesen PE = MBB->pred_end(); PI != PE; ++PI) { 697031432f9ad24963282b7f71bd0592080f6229d20Jakob Stoklund Olesen if (!LiveOut.insert(*PI)) 698031432f9ad24963282b7f71bd0592080f6229d20Jakob Stoklund Olesen continue; 6996c9cc21d85cdef79b971f710ace287f3a2f847a3Jakob Stoklund Olesen SlotIndex Stop = getMBBEndIdx(*PI); 7006c9cc21d85cdef79b971f710ace287f3a2f847a3Jakob Stoklund Olesen assert(li->getVNInfoBefore(Stop) == VNI && 7016c9cc21d85cdef79b971f710ace287f3a2f847a3Jakob Stoklund Olesen "Wrong value out of predecessor"); 70211513e5d1e1b40e6113668e4b4357596f33fa6c6Jakob Stoklund Olesen WorkList.push_back(std::make_pair(Stop, VNI)); 70311513e5d1e1b40e6113668e4b4357596f33fa6c6Jakob Stoklund Olesen } 70411513e5d1e1b40e6113668e4b4357596f33fa6c6Jakob Stoklund Olesen } 70511513e5d1e1b40e6113668e4b4357596f33fa6c6Jakob Stoklund Olesen 70611513e5d1e1b40e6113668e4b4357596f33fa6c6Jakob Stoklund Olesen // Handle dead values. 7076a3dbd3b25bbc99bd1a233d6a74ddea3493ba6acJakob Stoklund Olesen bool CanSeparate = false; 70811513e5d1e1b40e6113668e4b4357596f33fa6c6Jakob Stoklund Olesen for (LiveInterval::vni_iterator I = li->vni_begin(), E = li->vni_end(); 70911513e5d1e1b40e6113668e4b4357596f33fa6c6Jakob Stoklund Olesen I != E; ++I) { 71011513e5d1e1b40e6113668e4b4357596f33fa6c6Jakob Stoklund Olesen VNInfo *VNI = *I; 71111513e5d1e1b40e6113668e4b4357596f33fa6c6Jakob Stoklund Olesen if (VNI->isUnused()) 71211513e5d1e1b40e6113668e4b4357596f33fa6c6Jakob Stoklund Olesen continue; 71311513e5d1e1b40e6113668e4b4357596f33fa6c6Jakob Stoklund Olesen LiveInterval::iterator LII = NewLI.FindLiveRangeContaining(VNI->def); 71411513e5d1e1b40e6113668e4b4357596f33fa6c6Jakob Stoklund Olesen assert(LII != NewLI.end() && "Missing live range for PHI"); 7151f81e316b042c02c841801a71e7439e166ffa2a0Jakob Stoklund Olesen if (LII->end != VNI->def.getDeadSlot()) 71611513e5d1e1b40e6113668e4b4357596f33fa6c6Jakob Stoklund Olesen continue; 717a4d347357ce04d9101130dca0df33cb62ea35a2fJakob Stoklund Olesen if (VNI->isPHIDef()) { 71811513e5d1e1b40e6113668e4b4357596f33fa6c6Jakob Stoklund Olesen // This is a dead PHI. Remove it. 71911513e5d1e1b40e6113668e4b4357596f33fa6c6Jakob Stoklund Olesen VNI->setIsUnused(true); 72011513e5d1e1b40e6113668e4b4357596f33fa6c6Jakob Stoklund Olesen NewLI.removeRange(*LII); 7216a3dbd3b25bbc99bd1a233d6a74ddea3493ba6acJakob Stoklund Olesen DEBUG(dbgs() << "Dead PHI at " << VNI->def << " may separate interval\n"); 7226a3dbd3b25bbc99bd1a233d6a74ddea3493ba6acJakob Stoklund Olesen CanSeparate = true; 72311513e5d1e1b40e6113668e4b4357596f33fa6c6Jakob Stoklund Olesen } else { 72411513e5d1e1b40e6113668e4b4357596f33fa6c6Jakob Stoklund Olesen // This is a dead def. Make sure the instruction knows. 72511513e5d1e1b40e6113668e4b4357596f33fa6c6Jakob Stoklund Olesen MachineInstr *MI = getInstructionFromIndex(VNI->def); 72611513e5d1e1b40e6113668e4b4357596f33fa6c6Jakob Stoklund Olesen assert(MI && "No instruction defining live value"); 72711513e5d1e1b40e6113668e4b4357596f33fa6c6Jakob Stoklund Olesen MI->addRegisterDead(li->reg, tri_); 7280d8ccaa5c8db820b5b93f37e51563148c57ba6b8Jakob Stoklund Olesen if (dead && MI->allDefsAreDead()) { 729c46570dc05851395829bef904bb6ddb1260400d1Jakob Stoklund Olesen DEBUG(dbgs() << "All defs dead: " << VNI->def << '\t' << *MI); 7300d8ccaa5c8db820b5b93f37e51563148c57ba6b8Jakob Stoklund Olesen dead->push_back(MI); 7310d8ccaa5c8db820b5b93f37e51563148c57ba6b8Jakob Stoklund Olesen } 73211513e5d1e1b40e6113668e4b4357596f33fa6c6Jakob Stoklund Olesen } 73311513e5d1e1b40e6113668e4b4357596f33fa6c6Jakob Stoklund Olesen } 73411513e5d1e1b40e6113668e4b4357596f33fa6c6Jakob Stoklund Olesen 73511513e5d1e1b40e6113668e4b4357596f33fa6c6Jakob Stoklund Olesen // Move the trimmed ranges back. 73611513e5d1e1b40e6113668e4b4357596f33fa6c6Jakob Stoklund Olesen li->ranges.swap(NewLI.ranges); 737c46570dc05851395829bef904bb6ddb1260400d1Jakob Stoklund Olesen DEBUG(dbgs() << "Shrunk: " << *li << '\n'); 7386a3dbd3b25bbc99bd1a233d6a74ddea3493ba6acJakob Stoklund Olesen return CanSeparate; 73911513e5d1e1b40e6113668e4b4357596f33fa6c6Jakob Stoklund Olesen} 74011513e5d1e1b40e6113668e4b4357596f33fa6c6Jakob Stoklund Olesen 74111513e5d1e1b40e6113668e4b4357596f33fa6c6Jakob Stoklund Olesen 742f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng//===----------------------------------------------------------------------===// 743f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng// Register allocator hooks. 744f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng// 745f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng 7468a61da8a689ee95874c833af4c7aa965fab5c0a9Jakob Stoklund Olesenvoid LiveIntervals::addKillFlags() { 7478a61da8a689ee95874c833af4c7aa965fab5c0a9Jakob Stoklund Olesen for (iterator I = begin(), E = end(); I != E; ++I) { 7488a61da8a689ee95874c833af4c7aa965fab5c0a9Jakob Stoklund Olesen unsigned Reg = I->first; 7498a61da8a689ee95874c833af4c7aa965fab5c0a9Jakob Stoklund Olesen if (TargetRegisterInfo::isPhysicalRegister(Reg)) 7508a61da8a689ee95874c833af4c7aa965fab5c0a9Jakob Stoklund Olesen continue; 7518a61da8a689ee95874c833af4c7aa965fab5c0a9Jakob Stoklund Olesen if (mri_->reg_nodbg_empty(Reg)) 7528a61da8a689ee95874c833af4c7aa965fab5c0a9Jakob Stoklund Olesen continue; 7538a61da8a689ee95874c833af4c7aa965fab5c0a9Jakob Stoklund Olesen LiveInterval *LI = I->second; 7548a61da8a689ee95874c833af4c7aa965fab5c0a9Jakob Stoklund Olesen 7558a61da8a689ee95874c833af4c7aa965fab5c0a9Jakob Stoklund Olesen // Every instruction that kills Reg corresponds to a live range end point. 7568a61da8a689ee95874c833af4c7aa965fab5c0a9Jakob Stoklund Olesen for (LiveInterval::iterator RI = LI->begin(), RE = LI->end(); RI != RE; 7578a61da8a689ee95874c833af4c7aa965fab5c0a9Jakob Stoklund Olesen ++RI) { 7582debd48ca790ac01be6e12e094fdf4fdcadc8364Jakob Stoklund Olesen // A block index indicates an MBB edge. 7592debd48ca790ac01be6e12e094fdf4fdcadc8364Jakob Stoklund Olesen if (RI->end.isBlock()) 7608a61da8a689ee95874c833af4c7aa965fab5c0a9Jakob Stoklund Olesen continue; 7618a61da8a689ee95874c833af4c7aa965fab5c0a9Jakob Stoklund Olesen MachineInstr *MI = getInstructionFromIndex(RI->end); 7628a61da8a689ee95874c833af4c7aa965fab5c0a9Jakob Stoklund Olesen if (!MI) 7638a61da8a689ee95874c833af4c7aa965fab5c0a9Jakob Stoklund Olesen continue; 7648a61da8a689ee95874c833af4c7aa965fab5c0a9Jakob Stoklund Olesen MI->addRegisterKilled(Reg, NULL); 7658a61da8a689ee95874c833af4c7aa965fab5c0a9Jakob Stoklund Olesen } 7668a61da8a689ee95874c833af4c7aa965fab5c0a9Jakob Stoklund Olesen } 7678a61da8a689ee95874c833af4c7aa965fab5c0a9Jakob Stoklund Olesen} 7688a61da8a689ee95874c833af4c7aa965fab5c0a9Jakob Stoklund Olesen 769baffe7a6f3c3f9588048db37a59b9b2f52ffe248Matt Beaumont-Gay#ifndef NDEBUG 770907cc8f38df212a87a6028682d91df01ba923f4fLang Hamesstatic bool intervalRangesSane(const LiveInterval& li) { 771907cc8f38df212a87a6028682d91df01ba923f4fLang Hames if (li.empty()) { 772907cc8f38df212a87a6028682d91df01ba923f4fLang Hames return true; 773907cc8f38df212a87a6028682d91df01ba923f4fLang Hames } 774907cc8f38df212a87a6028682d91df01ba923f4fLang Hames 775907cc8f38df212a87a6028682d91df01ba923f4fLang Hames SlotIndex lastEnd = li.begin()->start; 776907cc8f38df212a87a6028682d91df01ba923f4fLang Hames for (LiveInterval::const_iterator lrItr = li.begin(), lrEnd = li.end(); 777907cc8f38df212a87a6028682d91df01ba923f4fLang Hames lrItr != lrEnd; ++lrItr) { 778907cc8f38df212a87a6028682d91df01ba923f4fLang Hames const LiveRange& lr = *lrItr; 779907cc8f38df212a87a6028682d91df01ba923f4fLang Hames if (lastEnd > lr.start || lr.start >= lr.end) 780907cc8f38df212a87a6028682d91df01ba923f4fLang Hames return false; 781907cc8f38df212a87a6028682d91df01ba923f4fLang Hames lastEnd = lr.end; 782907cc8f38df212a87a6028682d91df01ba923f4fLang Hames } 783907cc8f38df212a87a6028682d91df01ba923f4fLang Hames 784907cc8f38df212a87a6028682d91df01ba923f4fLang Hames return true; 785907cc8f38df212a87a6028682d91df01ba923f4fLang Hames} 786baffe7a6f3c3f9588048db37a59b9b2f52ffe248Matt Beaumont-Gay#endif 787907cc8f38df212a87a6028682d91df01ba923f4fLang Hames 788907cc8f38df212a87a6028682d91df01ba923f4fLang Hamestemplate <typename DefSetT> 789907cc8f38df212a87a6028682d91df01ba923f4fLang Hamesstatic void handleMoveDefs(LiveIntervals& lis, SlotIndex origIdx, 790907cc8f38df212a87a6028682d91df01ba923f4fLang Hames SlotIndex miIdx, const DefSetT& defs) { 791907cc8f38df212a87a6028682d91df01ba923f4fLang Hames for (typename DefSetT::const_iterator defItr = defs.begin(), 792907cc8f38df212a87a6028682d91df01ba923f4fLang Hames defEnd = defs.end(); 793907cc8f38df212a87a6028682d91df01ba923f4fLang Hames defItr != defEnd; ++defItr) { 794907cc8f38df212a87a6028682d91df01ba923f4fLang Hames unsigned def = *defItr; 795907cc8f38df212a87a6028682d91df01ba923f4fLang Hames LiveInterval& li = lis.getInterval(def); 796907cc8f38df212a87a6028682d91df01ba923f4fLang Hames LiveRange* lr = li.getLiveRangeContaining(origIdx.getRegSlot()); 797907cc8f38df212a87a6028682d91df01ba923f4fLang Hames assert(lr != 0 && "No range for def?"); 798907cc8f38df212a87a6028682d91df01ba923f4fLang Hames lr->start = miIdx.getRegSlot(); 799907cc8f38df212a87a6028682d91df01ba923f4fLang Hames lr->valno->def = miIdx.getRegSlot(); 800907cc8f38df212a87a6028682d91df01ba923f4fLang Hames assert(intervalRangesSane(li) && "Broke live interval moving def."); 801907cc8f38df212a87a6028682d91df01ba923f4fLang Hames } 802907cc8f38df212a87a6028682d91df01ba923f4fLang Hames} 803907cc8f38df212a87a6028682d91df01ba923f4fLang Hames 804907cc8f38df212a87a6028682d91df01ba923f4fLang Hamestemplate <typename DeadDefSetT> 805907cc8f38df212a87a6028682d91df01ba923f4fLang Hamesstatic void handleMoveDeadDefs(LiveIntervals& lis, SlotIndex origIdx, 806907cc8f38df212a87a6028682d91df01ba923f4fLang Hames SlotIndex miIdx, const DeadDefSetT& deadDefs) { 807907cc8f38df212a87a6028682d91df01ba923f4fLang Hames for (typename DeadDefSetT::const_iterator deadDefItr = deadDefs.begin(), 808907cc8f38df212a87a6028682d91df01ba923f4fLang Hames deadDefEnd = deadDefs.end(); 809907cc8f38df212a87a6028682d91df01ba923f4fLang Hames deadDefItr != deadDefEnd; ++deadDefItr) { 810907cc8f38df212a87a6028682d91df01ba923f4fLang Hames unsigned deadDef = *deadDefItr; 811907cc8f38df212a87a6028682d91df01ba923f4fLang Hames LiveInterval& li = lis.getInterval(deadDef); 812907cc8f38df212a87a6028682d91df01ba923f4fLang Hames LiveRange* lr = li.getLiveRangeContaining(origIdx.getRegSlot()); 813907cc8f38df212a87a6028682d91df01ba923f4fLang Hames assert(lr != 0 && "No range for dead def?"); 814907cc8f38df212a87a6028682d91df01ba923f4fLang Hames assert(lr->start == origIdx.getRegSlot() && "Bad dead range start?"); 815907cc8f38df212a87a6028682d91df01ba923f4fLang Hames assert(lr->end == origIdx.getDeadSlot() && "Bad dead range end?"); 816907cc8f38df212a87a6028682d91df01ba923f4fLang Hames assert(lr->valno->def == origIdx.getRegSlot() && "Bad dead valno def."); 817907cc8f38df212a87a6028682d91df01ba923f4fLang Hames LiveRange t(*lr); 818907cc8f38df212a87a6028682d91df01ba923f4fLang Hames t.start = miIdx.getRegSlot(); 819907cc8f38df212a87a6028682d91df01ba923f4fLang Hames t.valno->def = miIdx.getRegSlot(); 820907cc8f38df212a87a6028682d91df01ba923f4fLang Hames t.end = miIdx.getDeadSlot(); 821907cc8f38df212a87a6028682d91df01ba923f4fLang Hames li.removeRange(*lr); 822907cc8f38df212a87a6028682d91df01ba923f4fLang Hames li.addRange(t); 823907cc8f38df212a87a6028682d91df01ba923f4fLang Hames assert(intervalRangesSane(li) && "Broke live interval moving dead def."); 824907cc8f38df212a87a6028682d91df01ba923f4fLang Hames } 825907cc8f38df212a87a6028682d91df01ba923f4fLang Hames} 826907cc8f38df212a87a6028682d91df01ba923f4fLang Hames 827907cc8f38df212a87a6028682d91df01ba923f4fLang Hamestemplate <typename ECSetT> 828907cc8f38df212a87a6028682d91df01ba923f4fLang Hamesstatic void handleMoveECs(LiveIntervals& lis, SlotIndex origIdx, 829907cc8f38df212a87a6028682d91df01ba923f4fLang Hames SlotIndex miIdx, const ECSetT& ecs) { 830907cc8f38df212a87a6028682d91df01ba923f4fLang Hames for (typename ECSetT::const_iterator ecItr = ecs.begin(), ecEnd = ecs.end(); 831907cc8f38df212a87a6028682d91df01ba923f4fLang Hames ecItr != ecEnd; ++ecItr) { 832907cc8f38df212a87a6028682d91df01ba923f4fLang Hames unsigned ec = *ecItr; 833907cc8f38df212a87a6028682d91df01ba923f4fLang Hames LiveInterval& li = lis.getInterval(ec); 834907cc8f38df212a87a6028682d91df01ba923f4fLang Hames LiveRange* lr = li.getLiveRangeContaining(origIdx.getRegSlot(true)); 835907cc8f38df212a87a6028682d91df01ba923f4fLang Hames assert(lr != 0 && "No range for early clobber?"); 836907cc8f38df212a87a6028682d91df01ba923f4fLang Hames assert(lr->start == origIdx.getRegSlot(true) && "Bad EC range start?"); 837907cc8f38df212a87a6028682d91df01ba923f4fLang Hames assert(lr->end == origIdx.getRegSlot() && "Bad EC range end."); 838907cc8f38df212a87a6028682d91df01ba923f4fLang Hames assert(lr->valno->def == origIdx.getRegSlot(true) && "Bad EC valno def."); 839907cc8f38df212a87a6028682d91df01ba923f4fLang Hames LiveRange t(*lr); 840907cc8f38df212a87a6028682d91df01ba923f4fLang Hames t.start = miIdx.getRegSlot(true); 841907cc8f38df212a87a6028682d91df01ba923f4fLang Hames t.valno->def = miIdx.getRegSlot(true); 842907cc8f38df212a87a6028682d91df01ba923f4fLang Hames t.end = miIdx.getRegSlot(); 843907cc8f38df212a87a6028682d91df01ba923f4fLang Hames li.removeRange(*lr); 844907cc8f38df212a87a6028682d91df01ba923f4fLang Hames li.addRange(t); 845907cc8f38df212a87a6028682d91df01ba923f4fLang Hames assert(intervalRangesSane(li) && "Broke live interval moving EC."); 846907cc8f38df212a87a6028682d91df01ba923f4fLang Hames } 847907cc8f38df212a87a6028682d91df01ba923f4fLang Hames} 848907cc8f38df212a87a6028682d91df01ba923f4fLang Hames 849fb08b90bf402bcd08a3474772d505294d9d7aa79Lang Hamesstatic void moveKillFlags(unsigned reg, SlotIndex oldIdx, SlotIndex newIdx, 850fb08b90bf402bcd08a3474772d505294d9d7aa79Lang Hames LiveIntervals& lis, 851fb08b90bf402bcd08a3474772d505294d9d7aa79Lang Hames const TargetRegisterInfo& tri) { 852fb08b90bf402bcd08a3474772d505294d9d7aa79Lang Hames MachineInstr* oldKillMI = lis.getInstructionFromIndex(oldIdx); 853fb08b90bf402bcd08a3474772d505294d9d7aa79Lang Hames MachineInstr* newKillMI = lis.getInstructionFromIndex(newIdx); 854fb08b90bf402bcd08a3474772d505294d9d7aa79Lang Hames assert(oldKillMI->killsRegister(reg) && "Old 'kill' instr isn't a kill."); 855fb08b90bf402bcd08a3474772d505294d9d7aa79Lang Hames assert(!newKillMI->killsRegister(reg) && "New kill instr is already a kill."); 856fb08b90bf402bcd08a3474772d505294d9d7aa79Lang Hames oldKillMI->clearRegisterKills(reg, &tri); 857fb08b90bf402bcd08a3474772d505294d9d7aa79Lang Hames newKillMI->addRegisterKilled(reg, &tri); 858fb08b90bf402bcd08a3474772d505294d9d7aa79Lang Hames} 859fb08b90bf402bcd08a3474772d505294d9d7aa79Lang Hames 860907cc8f38df212a87a6028682d91df01ba923f4fLang Hamestemplate <typename UseSetT> 861907cc8f38df212a87a6028682d91df01ba923f4fLang Hamesstatic void handleMoveUses(const MachineBasicBlock *mbb, 862907cc8f38df212a87a6028682d91df01ba923f4fLang Hames const MachineRegisterInfo& mri, 863fb08b90bf402bcd08a3474772d505294d9d7aa79Lang Hames const TargetRegisterInfo& tri, 864907cc8f38df212a87a6028682d91df01ba923f4fLang Hames const BitVector& reservedRegs, LiveIntervals &lis, 865907cc8f38df212a87a6028682d91df01ba923f4fLang Hames SlotIndex origIdx, SlotIndex miIdx, 866907cc8f38df212a87a6028682d91df01ba923f4fLang Hames const UseSetT &uses) { 867907cc8f38df212a87a6028682d91df01ba923f4fLang Hames bool movingUp = miIdx < origIdx; 868907cc8f38df212a87a6028682d91df01ba923f4fLang Hames for (typename UseSetT::const_iterator usesItr = uses.begin(), 869907cc8f38df212a87a6028682d91df01ba923f4fLang Hames usesEnd = uses.end(); 870907cc8f38df212a87a6028682d91df01ba923f4fLang Hames usesItr != usesEnd; ++usesItr) { 871907cc8f38df212a87a6028682d91df01ba923f4fLang Hames unsigned use = *usesItr; 872907cc8f38df212a87a6028682d91df01ba923f4fLang Hames if (!lis.hasInterval(use)) 873907cc8f38df212a87a6028682d91df01ba923f4fLang Hames continue; 874907cc8f38df212a87a6028682d91df01ba923f4fLang Hames if (TargetRegisterInfo::isPhysicalRegister(use) && reservedRegs.test(use)) 875907cc8f38df212a87a6028682d91df01ba923f4fLang Hames continue; 876907cc8f38df212a87a6028682d91df01ba923f4fLang Hames LiveInterval& li = lis.getInterval(use); 877907cc8f38df212a87a6028682d91df01ba923f4fLang Hames LiveRange* lr = li.getLiveRangeBefore(origIdx.getRegSlot()); 878907cc8f38df212a87a6028682d91df01ba923f4fLang Hames assert(lr != 0 && "No range for use?"); 879907cc8f38df212a87a6028682d91df01ba923f4fLang Hames bool liveThrough = lr->end > origIdx.getRegSlot(); 880907cc8f38df212a87a6028682d91df01ba923f4fLang Hames 881907cc8f38df212a87a6028682d91df01ba923f4fLang Hames if (movingUp) { 882907cc8f38df212a87a6028682d91df01ba923f4fLang Hames // If moving up and liveThrough - nothing to do. 883907cc8f38df212a87a6028682d91df01ba923f4fLang Hames // If not live through we need to extend the range to the last use 884907cc8f38df212a87a6028682d91df01ba923f4fLang Hames // between the old location and the new one. 885907cc8f38df212a87a6028682d91df01ba923f4fLang Hames if (!liveThrough) { 886907cc8f38df212a87a6028682d91df01ba923f4fLang Hames SlotIndex lastUseInRange = miIdx.getRegSlot(); 887907cc8f38df212a87a6028682d91df01ba923f4fLang Hames for (MachineRegisterInfo::use_iterator useI = mri.use_begin(use), 888907cc8f38df212a87a6028682d91df01ba923f4fLang Hames useE = mri.use_end(); 889907cc8f38df212a87a6028682d91df01ba923f4fLang Hames useI != useE; ++useI) { 890907cc8f38df212a87a6028682d91df01ba923f4fLang Hames const MachineInstr* mopI = &*useI; 891907cc8f38df212a87a6028682d91df01ba923f4fLang Hames const MachineOperand& mop = useI.getOperand(); 892907cc8f38df212a87a6028682d91df01ba923f4fLang Hames SlotIndex instSlot = lis.getSlotIndexes()->getInstructionIndex(mopI); 893907cc8f38df212a87a6028682d91df01ba923f4fLang Hames SlotIndex opSlot = instSlot.getRegSlot(mop.isEarlyClobber()); 894fb08b90bf402bcd08a3474772d505294d9d7aa79Lang Hames if (opSlot > lastUseInRange && opSlot < origIdx) 895907cc8f38df212a87a6028682d91df01ba923f4fLang Hames lastUseInRange = opSlot; 896907cc8f38df212a87a6028682d91df01ba923f4fLang Hames } 897fb08b90bf402bcd08a3474772d505294d9d7aa79Lang Hames 898fb08b90bf402bcd08a3474772d505294d9d7aa79Lang Hames // If we found a new instr endpoint update the kill flags. 899fb08b90bf402bcd08a3474772d505294d9d7aa79Lang Hames if (lastUseInRange != miIdx.getRegSlot()) 900fb08b90bf402bcd08a3474772d505294d9d7aa79Lang Hames moveKillFlags(use, miIdx, lastUseInRange, lis, tri); 901fb08b90bf402bcd08a3474772d505294d9d7aa79Lang Hames 902fb08b90bf402bcd08a3474772d505294d9d7aa79Lang Hames // Fix up the range end. 903907cc8f38df212a87a6028682d91df01ba923f4fLang Hames lr->end = lastUseInRange; 904907cc8f38df212a87a6028682d91df01ba923f4fLang Hames } 905907cc8f38df212a87a6028682d91df01ba923f4fLang Hames } else { 906907cc8f38df212a87a6028682d91df01ba923f4fLang Hames // Moving down is easy - the existing live range end tells us where 907907cc8f38df212a87a6028682d91df01ba923f4fLang Hames // the last kill is. 908907cc8f38df212a87a6028682d91df01ba923f4fLang Hames if (!liveThrough) { 909907cc8f38df212a87a6028682d91df01ba923f4fLang Hames // Easy fix - just update the range endpoint. 910907cc8f38df212a87a6028682d91df01ba923f4fLang Hames lr->end = miIdx.getRegSlot(); 911907cc8f38df212a87a6028682d91df01ba923f4fLang Hames } else { 912907cc8f38df212a87a6028682d91df01ba923f4fLang Hames bool liveOut = lr->end >= lis.getSlotIndexes()->getMBBEndIdx(mbb); 913907cc8f38df212a87a6028682d91df01ba923f4fLang Hames if (!liveOut && miIdx.getRegSlot() > lr->end) { 914fb08b90bf402bcd08a3474772d505294d9d7aa79Lang Hames moveKillFlags(use, lr->end, miIdx, lis, tri); 915907cc8f38df212a87a6028682d91df01ba923f4fLang Hames lr->end = miIdx.getRegSlot(); 916907cc8f38df212a87a6028682d91df01ba923f4fLang Hames } 917907cc8f38df212a87a6028682d91df01ba923f4fLang Hames } 918907cc8f38df212a87a6028682d91df01ba923f4fLang Hames } 919907cc8f38df212a87a6028682d91df01ba923f4fLang Hames assert(intervalRangesSane(li) && "Broke live interval moving use."); 920907cc8f38df212a87a6028682d91df01ba923f4fLang Hames } 921907cc8f38df212a87a6028682d91df01ba923f4fLang Hames} 922907cc8f38df212a87a6028682d91df01ba923f4fLang Hames 923907cc8f38df212a87a6028682d91df01ba923f4fLang Hamesvoid LiveIntervals::moveInstr(MachineBasicBlock::iterator insertPt, 924907cc8f38df212a87a6028682d91df01ba923f4fLang Hames MachineInstr *mi) { 925907cc8f38df212a87a6028682d91df01ba923f4fLang Hames MachineBasicBlock* mbb = mi->getParent(); 9263f8d3c7d72367244e56efd9ce2c64ef5905cb377Lang Hames assert((insertPt == mbb->end() || insertPt->getParent() == mbb) && 927907cc8f38df212a87a6028682d91df01ba923f4fLang Hames "Cannot handle moves across basic block boundaries."); 928907cc8f38df212a87a6028682d91df01ba923f4fLang Hames assert(&*insertPt != mi && "No-op move requested?"); 92999a7a13f4aa5bf8f272c95f7b09ba997d2b30a35Andrew Trick assert(!mi->isBundled() && "Can't handle bundled instructions yet."); 930907cc8f38df212a87a6028682d91df01ba923f4fLang Hames 931907cc8f38df212a87a6028682d91df01ba923f4fLang Hames // Grab the original instruction index. 932907cc8f38df212a87a6028682d91df01ba923f4fLang Hames SlotIndex origIdx = indexes_->getInstructionIndex(mi); 933907cc8f38df212a87a6028682d91df01ba923f4fLang Hames 934907cc8f38df212a87a6028682d91df01ba923f4fLang Hames // Move the machine instr and obtain its new index. 935907cc8f38df212a87a6028682d91df01ba923f4fLang Hames indexes_->removeMachineInstrFromMaps(mi); 936fb08b90bf402bcd08a3474772d505294d9d7aa79Lang Hames mbb->splice(insertPt, mbb, mi); 937907cc8f38df212a87a6028682d91df01ba923f4fLang Hames SlotIndex miIdx = indexes_->insertMachineInstrInMaps(mi); 938907cc8f38df212a87a6028682d91df01ba923f4fLang Hames 939907cc8f38df212a87a6028682d91df01ba923f4fLang Hames // Pick the direction. 940907cc8f38df212a87a6028682d91df01ba923f4fLang Hames bool movingUp = miIdx < origIdx; 941907cc8f38df212a87a6028682d91df01ba923f4fLang Hames 942907cc8f38df212a87a6028682d91df01ba923f4fLang Hames // Collect the operands. 943907cc8f38df212a87a6028682d91df01ba923f4fLang Hames DenseSet<unsigned> uses, defs, deadDefs, ecs; 944907cc8f38df212a87a6028682d91df01ba923f4fLang Hames for (MachineInstr::mop_iterator mopItr = mi->operands_begin(), 945907cc8f38df212a87a6028682d91df01ba923f4fLang Hames mopEnd = mi->operands_end(); 946907cc8f38df212a87a6028682d91df01ba923f4fLang Hames mopItr != mopEnd; ++mopItr) { 947907cc8f38df212a87a6028682d91df01ba923f4fLang Hames const MachineOperand& mop = *mopItr; 948907cc8f38df212a87a6028682d91df01ba923f4fLang Hames 949907cc8f38df212a87a6028682d91df01ba923f4fLang Hames if (!mop.isReg() || mop.getReg() == 0) 950907cc8f38df212a87a6028682d91df01ba923f4fLang Hames continue; 951907cc8f38df212a87a6028682d91df01ba923f4fLang Hames unsigned reg = mop.getReg(); 952907cc8f38df212a87a6028682d91df01ba923f4fLang Hames 953907cc8f38df212a87a6028682d91df01ba923f4fLang Hames if (mop.readsReg() && !ecs.count(reg)) { 954907cc8f38df212a87a6028682d91df01ba923f4fLang Hames uses.insert(reg); 955907cc8f38df212a87a6028682d91df01ba923f4fLang Hames } 956907cc8f38df212a87a6028682d91df01ba923f4fLang Hames if (mop.isDef()) { 957907cc8f38df212a87a6028682d91df01ba923f4fLang Hames if (mop.isDead()) { 958907cc8f38df212a87a6028682d91df01ba923f4fLang Hames assert(!defs.count(reg) && "Can't mix defs with dead-defs."); 959907cc8f38df212a87a6028682d91df01ba923f4fLang Hames deadDefs.insert(reg); 960907cc8f38df212a87a6028682d91df01ba923f4fLang Hames } else if (mop.isEarlyClobber()) { 961907cc8f38df212a87a6028682d91df01ba923f4fLang Hames uses.erase(reg); 962907cc8f38df212a87a6028682d91df01ba923f4fLang Hames ecs.insert(reg); 963907cc8f38df212a87a6028682d91df01ba923f4fLang Hames } else { 964907cc8f38df212a87a6028682d91df01ba923f4fLang Hames assert(!deadDefs.count(reg) && "Can't mix defs with dead-defs."); 965907cc8f38df212a87a6028682d91df01ba923f4fLang Hames defs.insert(reg); 966907cc8f38df212a87a6028682d91df01ba923f4fLang Hames } 967907cc8f38df212a87a6028682d91df01ba923f4fLang Hames } 968907cc8f38df212a87a6028682d91df01ba923f4fLang Hames } 969907cc8f38df212a87a6028682d91df01ba923f4fLang Hames 970907cc8f38df212a87a6028682d91df01ba923f4fLang Hames BitVector reservedRegs(tri_->getReservedRegs(*mbb->getParent())); 971907cc8f38df212a87a6028682d91df01ba923f4fLang Hames 972907cc8f38df212a87a6028682d91df01ba923f4fLang Hames if (movingUp) { 973fb08b90bf402bcd08a3474772d505294d9d7aa79Lang Hames handleMoveUses(mbb, *mri_, *tri_, reservedRegs, *this, origIdx, miIdx, uses); 974907cc8f38df212a87a6028682d91df01ba923f4fLang Hames handleMoveECs(*this, origIdx, miIdx, ecs); 975907cc8f38df212a87a6028682d91df01ba923f4fLang Hames handleMoveDeadDefs(*this, origIdx, miIdx, deadDefs); 976907cc8f38df212a87a6028682d91df01ba923f4fLang Hames handleMoveDefs(*this, origIdx, miIdx, defs); 977907cc8f38df212a87a6028682d91df01ba923f4fLang Hames } else { 978907cc8f38df212a87a6028682d91df01ba923f4fLang Hames handleMoveDefs(*this, origIdx, miIdx, defs); 979907cc8f38df212a87a6028682d91df01ba923f4fLang Hames handleMoveDeadDefs(*this, origIdx, miIdx, deadDefs); 980907cc8f38df212a87a6028682d91df01ba923f4fLang Hames handleMoveECs(*this, origIdx, miIdx, ecs); 981fb08b90bf402bcd08a3474772d505294d9d7aa79Lang Hames handleMoveUses(mbb, *mri_, *tri_, reservedRegs, *this, origIdx, miIdx, uses); 982907cc8f38df212a87a6028682d91df01ba923f4fLang Hames } 983907cc8f38df212a87a6028682d91df01ba923f4fLang Hames} 984907cc8f38df212a87a6028682d91df01ba923f4fLang Hames 985d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng/// getReMatImplicitUse - If the remat definition MI has one (for now, we only 986d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng/// allow one) virtual register operand, then its uses are implicitly using 987d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng/// the register. Returns the virtual register. 988d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Chengunsigned LiveIntervals::getReMatImplicitUse(const LiveInterval &li, 989d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng MachineInstr *MI) const { 990d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng unsigned RegOp = 0; 991d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) { 992d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng MachineOperand &MO = MI->getOperand(i); 993d735b8019b0f297d7c14b55adcd887af24d8e602Dan Gohman if (!MO.isReg() || !MO.isUse()) 994d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng continue; 995d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng unsigned Reg = MO.getReg(); 996d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng if (Reg == 0 || Reg == li.reg) 997d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng continue; 9981b2932024f098a6968645ac78d5848951d877c19Jakob Stoklund Olesen 9991873d0c2257b18451c5bb35577f929d0723433a0Chris Lattner if (TargetRegisterInfo::isPhysicalRegister(Reg) && 10001873d0c2257b18451c5bb35577f929d0723433a0Chris Lattner !allocatableRegs_[Reg]) 10011873d0c2257b18451c5bb35577f929d0723433a0Chris Lattner continue; 1002d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng RegOp = MO.getReg(); 10036c76e80753cfc83dc6804fcd5d949c517dfe3434Lang Hames break; // Found vreg operand - leave the loop. 1004d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng } 1005d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng return RegOp; 1006d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng} 1007d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng 1008d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng/// isValNoAvailableAt - Return true if the val# of the specified interval 1009d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng/// which reaches the given instruction also reaches the specified use index. 1010d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Chengbool LiveIntervals::isValNoAvailableAt(const LiveInterval &li, MachineInstr *MI, 1011233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames SlotIndex UseIdx) const { 101231cc3ec3308c8fafd9865388214ae11662a71af4Jakob Stoklund Olesen VNInfo *UValNo = li.getVNInfoAt(UseIdx); 101331cc3ec3308c8fafd9865388214ae11662a71af4Jakob Stoklund Olesen return UValNo && UValNo == li.getVNInfoAt(getInstructionIndex(MI)); 1014d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng} 1015d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng 1016f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng/// isReMaterializable - Returns true if the definition MI of the specified 1017f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng/// val# of the specified interval is re-materializable. 1018f4baeaf8485f01beda46d29fd55753199dc68070Andrew Trickbool 1019f4baeaf8485f01beda46d29fd55753199dc68070Andrew TrickLiveIntervals::isReMaterializable(const LiveInterval &li, 1020f4baeaf8485f01beda46d29fd55753199dc68070Andrew Trick const VNInfo *ValNo, MachineInstr *MI, 102138f6bd0fc8095ef79a89b3db15ff6dc734ac90e7Jakob Stoklund Olesen const SmallVectorImpl<LiveInterval*> *SpillIs, 1022f4baeaf8485f01beda46d29fd55753199dc68070Andrew Trick bool &isLoad) { 1023f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng if (DisableReMat) 1024f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng return false; 1025f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng 1026a70dca156fa76d452f54829b5c5f962ddfd94ef2Dan Gohman if (!tii_->isTriviallyReMaterializable(MI, aa_)) 1027a70dca156fa76d452f54829b5c5f962ddfd94ef2Dan Gohman return false; 1028f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng 1029a70dca156fa76d452f54829b5c5f962ddfd94ef2Dan Gohman // Target-specific code can mark an instruction as being rematerializable 1030a70dca156fa76d452f54829b5c5f962ddfd94ef2Dan Gohman // if it has one virtual reg use, though it had better be something like 1031a70dca156fa76d452f54829b5c5f962ddfd94ef2Dan Gohman // a PIC base register which is likely to be live everywhere. 10326d69ba8a6901c69d78488cbc41f8dbf080618fdeDan Gohman unsigned ImpUse = getReMatImplicitUse(li, MI); 10336d69ba8a6901c69d78488cbc41f8dbf080618fdeDan Gohman if (ImpUse) { 10346d69ba8a6901c69d78488cbc41f8dbf080618fdeDan Gohman const LiveInterval &ImpLi = getInterval(ImpUse); 103528a1e486907104b85c5787345914917d74f0cf77Evan Cheng for (MachineRegisterInfo::use_nodbg_iterator 103628a1e486907104b85c5787345914917d74f0cf77Evan Cheng ri = mri_->use_nodbg_begin(li.reg), re = mri_->use_nodbg_end(); 103728a1e486907104b85c5787345914917d74f0cf77Evan Cheng ri != re; ++ri) { 10386d69ba8a6901c69d78488cbc41f8dbf080618fdeDan Gohman MachineInstr *UseMI = &*ri; 1039233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames SlotIndex UseIdx = getInstructionIndex(UseMI); 104031cc3ec3308c8fafd9865388214ae11662a71af4Jakob Stoklund Olesen if (li.getVNInfoAt(UseIdx) != ValNo) 10416d69ba8a6901c69d78488cbc41f8dbf080618fdeDan Gohman continue; 10426d69ba8a6901c69d78488cbc41f8dbf080618fdeDan Gohman if (!isValNoAvailableAt(ImpLi, MI, UseIdx)) 10436d69ba8a6901c69d78488cbc41f8dbf080618fdeDan Gohman return false; 10446d69ba8a6901c69d78488cbc41f8dbf080618fdeDan Gohman } 1045dc37786595beedd0a68d8e2cbd91ae53ad58d133Evan Cheng 1046dc37786595beedd0a68d8e2cbd91ae53ad58d133Evan Cheng // If a register operand of the re-materialized instruction is going to 1047dc37786595beedd0a68d8e2cbd91ae53ad58d133Evan Cheng // be spilled next, then it's not legal to re-materialize this instruction. 104838f6bd0fc8095ef79a89b3db15ff6dc734ac90e7Jakob Stoklund Olesen if (SpillIs) 104938f6bd0fc8095ef79a89b3db15ff6dc734ac90e7Jakob Stoklund Olesen for (unsigned i = 0, e = SpillIs->size(); i != e; ++i) 105038f6bd0fc8095ef79a89b3db15ff6dc734ac90e7Jakob Stoklund Olesen if (ImpUse == (*SpillIs)[i]->reg) 105138f6bd0fc8095ef79a89b3db15ff6dc734ac90e7Jakob Stoklund Olesen return false; 10526d69ba8a6901c69d78488cbc41f8dbf080618fdeDan Gohman } 10536d69ba8a6901c69d78488cbc41f8dbf080618fdeDan Gohman return true; 10545ef3a04b542c4e585276768fa9ca2af698ef5c87Evan Cheng} 10555ef3a04b542c4e585276768fa9ca2af698ef5c87Evan Cheng 10565ef3a04b542c4e585276768fa9ca2af698ef5c87Evan Cheng/// isReMaterializable - Returns true if every definition of MI of every 10575ef3a04b542c4e585276768fa9ca2af698ef5c87Evan Cheng/// val# of the specified interval is re-materializable. 1058f4baeaf8485f01beda46d29fd55753199dc68070Andrew Trickbool 1059f4baeaf8485f01beda46d29fd55753199dc68070Andrew TrickLiveIntervals::isReMaterializable(const LiveInterval &li, 106038f6bd0fc8095ef79a89b3db15ff6dc734ac90e7Jakob Stoklund Olesen const SmallVectorImpl<LiveInterval*> *SpillIs, 1061f4baeaf8485f01beda46d29fd55753199dc68070Andrew Trick bool &isLoad) { 10625ef3a04b542c4e585276768fa9ca2af698ef5c87Evan Cheng isLoad = false; 10635ef3a04b542c4e585276768fa9ca2af698ef5c87Evan Cheng for (LiveInterval::const_vni_iterator i = li.vni_begin(), e = li.vni_end(); 10645ef3a04b542c4e585276768fa9ca2af698ef5c87Evan Cheng i != e; ++i) { 10655ef3a04b542c4e585276768fa9ca2af698ef5c87Evan Cheng const VNInfo *VNI = *i; 1066857c4e01f85601cf2084adb860616256ee47c177Lang Hames if (VNI->isUnused()) 10675ef3a04b542c4e585276768fa9ca2af698ef5c87Evan Cheng continue; // Dead val#. 10685ef3a04b542c4e585276768fa9ca2af698ef5c87Evan Cheng // Is the def for the val# rematerializable? 1069857c4e01f85601cf2084adb860616256ee47c177Lang Hames MachineInstr *ReMatDefMI = getInstructionFromIndex(VNI->def); 10706e2968c85c1e162ee5bc813769eab223e3df0f15Lang Hames if (!ReMatDefMI) 10716e2968c85c1e162ee5bc813769eab223e3df0f15Lang Hames return false; 10725ef3a04b542c4e585276768fa9ca2af698ef5c87Evan Cheng bool DefIsLoad = false; 1073d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng if (!ReMatDefMI || 1074dc37786595beedd0a68d8e2cbd91ae53ad58d133Evan Cheng !isReMaterializable(li, VNI, ReMatDefMI, SpillIs, DefIsLoad)) 1075f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng return false; 10765ef3a04b542c4e585276768fa9ca2af698ef5c87Evan Cheng isLoad |= DefIsLoad; 1077f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng } 1078f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng return true; 1079f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng} 1080f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng 1081ebf2750a70df4261d3e66144ea6bcb49d41f6efbJakob Stoklund OlesenMachineBasicBlock* 1082ebf2750a70df4261d3e66144ea6bcb49d41f6efbJakob Stoklund OlesenLiveIntervals::intervalIsInOneMBB(const LiveInterval &LI) const { 1083ebf2750a70df4261d3e66144ea6bcb49d41f6efbJakob Stoklund Olesen // A local live range must be fully contained inside the block, meaning it is 1084ebf2750a70df4261d3e66144ea6bcb49d41f6efbJakob Stoklund Olesen // defined and killed at instructions, not at block boundaries. It is not 1085ebf2750a70df4261d3e66144ea6bcb49d41f6efbJakob Stoklund Olesen // live in or or out of any block. 1086ebf2750a70df4261d3e66144ea6bcb49d41f6efbJakob Stoklund Olesen // 1087ebf2750a70df4261d3e66144ea6bcb49d41f6efbJakob Stoklund Olesen // It is technically possible to have a PHI-defined live range identical to a 1088ebf2750a70df4261d3e66144ea6bcb49d41f6efbJakob Stoklund Olesen // single block, but we are going to return false in that case. 1089ebf2750a70df4261d3e66144ea6bcb49d41f6efbJakob Stoklund Olesen 1090ebf2750a70df4261d3e66144ea6bcb49d41f6efbJakob Stoklund Olesen SlotIndex Start = LI.beginIndex(); 1091ebf2750a70df4261d3e66144ea6bcb49d41f6efbJakob Stoklund Olesen if (Start.isBlock()) 1092ebf2750a70df4261d3e66144ea6bcb49d41f6efbJakob Stoklund Olesen return NULL; 1093ebf2750a70df4261d3e66144ea6bcb49d41f6efbJakob Stoklund Olesen 1094ebf2750a70df4261d3e66144ea6bcb49d41f6efbJakob Stoklund Olesen SlotIndex Stop = LI.endIndex(); 1095ebf2750a70df4261d3e66144ea6bcb49d41f6efbJakob Stoklund Olesen if (Stop.isBlock()) 1096ebf2750a70df4261d3e66144ea6bcb49d41f6efbJakob Stoklund Olesen return NULL; 1097ebf2750a70df4261d3e66144ea6bcb49d41f6efbJakob Stoklund Olesen 1098ebf2750a70df4261d3e66144ea6bcb49d41f6efbJakob Stoklund Olesen // getMBBFromIndex doesn't need to search the MBB table when both indexes 1099ebf2750a70df4261d3e66144ea6bcb49d41f6efbJakob Stoklund Olesen // belong to proper instructions. 1100ebf2750a70df4261d3e66144ea6bcb49d41f6efbJakob Stoklund Olesen MachineBasicBlock *MBB1 = indexes_->getMBBFromIndex(Start); 1101ebf2750a70df4261d3e66144ea6bcb49d41f6efbJakob Stoklund Olesen MachineBasicBlock *MBB2 = indexes_->getMBBFromIndex(Stop); 1102ebf2750a70df4261d3e66144ea6bcb49d41f6efbJakob Stoklund Olesen return MBB1 == MBB2 ? MBB1 : NULL; 110381a038218171860ee4c382849c647d3dc841fe8bEvan Cheng} 110481a038218171860ee4c382849c647d3dc841fe8bEvan Cheng 1105e5d90416ee1a4f45eba80789a7a3cbc3d497a4cdJakob Stoklund Olesenfloat 1106e5d90416ee1a4f45eba80789a7a3cbc3d497a4cdJakob Stoklund OlesenLiveIntervals::getSpillWeight(bool isDef, bool isUse, unsigned loopDepth) { 1107e5d90416ee1a4f45eba80789a7a3cbc3d497a4cdJakob Stoklund Olesen // Limit the loop depth ridiculousness. 1108e5d90416ee1a4f45eba80789a7a3cbc3d497a4cdJakob Stoklund Olesen if (loopDepth > 200) 1109e5d90416ee1a4f45eba80789a7a3cbc3d497a4cdJakob Stoklund Olesen loopDepth = 200; 1110e5d90416ee1a4f45eba80789a7a3cbc3d497a4cdJakob Stoklund Olesen 1111e5d90416ee1a4f45eba80789a7a3cbc3d497a4cdJakob Stoklund Olesen // The loop depth is used to roughly estimate the number of times the 1112e5d90416ee1a4f45eba80789a7a3cbc3d497a4cdJakob Stoklund Olesen // instruction is executed. Something like 10^d is simple, but will quickly 1113e5d90416ee1a4f45eba80789a7a3cbc3d497a4cdJakob Stoklund Olesen // overflow a float. This expression behaves like 10^d for small d, but is 1114e5d90416ee1a4f45eba80789a7a3cbc3d497a4cdJakob Stoklund Olesen // more tempered for large d. At d=200 we get 6.7e33 which leaves a bit of 1115e5d90416ee1a4f45eba80789a7a3cbc3d497a4cdJakob Stoklund Olesen // headroom before overflow. 1116dc5198bac7e3f9b61617c8c46a1c28a84daa9325NAKAMURA Takumi // By the way, powf() might be unavailable here. For consistency, 1117dc5198bac7e3f9b61617c8c46a1c28a84daa9325NAKAMURA Takumi // We may take pow(double,double). 1118dc5198bac7e3f9b61617c8c46a1c28a84daa9325NAKAMURA Takumi float lc = std::pow(1 + (100.0 / (loopDepth + 10)), (double)loopDepth); 1119e5d90416ee1a4f45eba80789a7a3cbc3d497a4cdJakob Stoklund Olesen 1120e5d90416ee1a4f45eba80789a7a3cbc3d497a4cdJakob Stoklund Olesen return (isDef + isUse) * lc; 1121e5d90416ee1a4f45eba80789a7a3cbc3d497a4cdJakob Stoklund Olesen} 1122e5d90416ee1a4f45eba80789a7a3cbc3d497a4cdJakob Stoklund Olesen 1123c4dc132c8a787fc41b6a162121251234aa618965Owen AndersonLiveRange LiveIntervals::addLiveRangeToEndOfBlock(unsigned reg, 1124ffd1326ff8dfc652a8026c3faebf55bbba7c32c7Lang Hames MachineInstr* startInst) { 1125c4dc132c8a787fc41b6a162121251234aa618965Owen Anderson LiveInterval& Interval = getOrCreateInterval(reg); 1126c4dc132c8a787fc41b6a162121251234aa618965Owen Anderson VNInfo* VN = Interval.getNextValue( 11272debd48ca790ac01be6e12e094fdf4fdcadc8364Jakob Stoklund Olesen SlotIndex(getInstructionIndex(startInst).getRegSlot()), 11283b1088a2cc15a39c7a7b8dd95a56143f1dda6863Jakob Stoklund Olesen getVNInfoAllocator()); 1129857c4e01f85601cf2084adb860616256ee47c177Lang Hames VN->setHasPHIKill(true); 11308651125d2885f74546b6e2a556082111d5b75da3Lang Hames LiveRange LR( 11312debd48ca790ac01be6e12e094fdf4fdcadc8364Jakob Stoklund Olesen SlotIndex(getInstructionIndex(startInst).getRegSlot()), 113274ab5eeffbd70f2387338e3ee8195be9f73e6dd8Lang Hames getMBBEndIdx(startInst->getParent()), VN); 1133c4dc132c8a787fc41b6a162121251234aa618965Owen Anderson Interval.addRange(LR); 11341b2932024f098a6968645ac78d5848951d877c19Jakob Stoklund Olesen 1135c4dc132c8a787fc41b6a162121251234aa618965Owen Anderson return LR; 1136c4dc132c8a787fc41b6a162121251234aa618965Owen Anderson} 11373fd3a840c50fe4ede1b200be18990bc955c536fdJakob Stoklund Olesen 11383fd3a840c50fe4ede1b200be18990bc955c536fdJakob Stoklund Olesen 11393fd3a840c50fe4ede1b200be18990bc955c536fdJakob Stoklund Olesen//===----------------------------------------------------------------------===// 11403fd3a840c50fe4ede1b200be18990bc955c536fdJakob Stoklund Olesen// Register mask functions 11413fd3a840c50fe4ede1b200be18990bc955c536fdJakob Stoklund Olesen//===----------------------------------------------------------------------===// 11423fd3a840c50fe4ede1b200be18990bc955c536fdJakob Stoklund Olesen 11433fd3a840c50fe4ede1b200be18990bc955c536fdJakob Stoklund Olesenbool LiveIntervals::checkRegMaskInterference(LiveInterval &LI, 11443fd3a840c50fe4ede1b200be18990bc955c536fdJakob Stoklund Olesen BitVector &UsableRegs) { 11453fd3a840c50fe4ede1b200be18990bc955c536fdJakob Stoklund Olesen if (LI.empty()) 11463fd3a840c50fe4ede1b200be18990bc955c536fdJakob Stoklund Olesen return false; 11479f10ac63a3a2a74ac381a05d8ba0f7b1b455a6b6Jakob Stoklund Olesen LiveInterval::iterator LiveI = LI.begin(), LiveE = LI.end(); 11489f10ac63a3a2a74ac381a05d8ba0f7b1b455a6b6Jakob Stoklund Olesen 11499f10ac63a3a2a74ac381a05d8ba0f7b1b455a6b6Jakob Stoklund Olesen // Use a smaller arrays for local live ranges. 11509f10ac63a3a2a74ac381a05d8ba0f7b1b455a6b6Jakob Stoklund Olesen ArrayRef<SlotIndex> Slots; 11519f10ac63a3a2a74ac381a05d8ba0f7b1b455a6b6Jakob Stoklund Olesen ArrayRef<const uint32_t*> Bits; 11529f10ac63a3a2a74ac381a05d8ba0f7b1b455a6b6Jakob Stoklund Olesen if (MachineBasicBlock *MBB = intervalIsInOneMBB(LI)) { 11539f10ac63a3a2a74ac381a05d8ba0f7b1b455a6b6Jakob Stoklund Olesen Slots = getRegMaskSlotsInBlock(MBB->getNumber()); 11549f10ac63a3a2a74ac381a05d8ba0f7b1b455a6b6Jakob Stoklund Olesen Bits = getRegMaskBitsInBlock(MBB->getNumber()); 11559f10ac63a3a2a74ac381a05d8ba0f7b1b455a6b6Jakob Stoklund Olesen } else { 11569f10ac63a3a2a74ac381a05d8ba0f7b1b455a6b6Jakob Stoklund Olesen Slots = getRegMaskSlots(); 11579f10ac63a3a2a74ac381a05d8ba0f7b1b455a6b6Jakob Stoklund Olesen Bits = getRegMaskBits(); 11589f10ac63a3a2a74ac381a05d8ba0f7b1b455a6b6Jakob Stoklund Olesen } 11593fd3a840c50fe4ede1b200be18990bc955c536fdJakob Stoklund Olesen 11603fd3a840c50fe4ede1b200be18990bc955c536fdJakob Stoklund Olesen // We are going to enumerate all the register mask slots contained in LI. 11613fd3a840c50fe4ede1b200be18990bc955c536fdJakob Stoklund Olesen // Start with a binary search of RegMaskSlots to find a starting point. 11623fd3a840c50fe4ede1b200be18990bc955c536fdJakob Stoklund Olesen ArrayRef<SlotIndex>::iterator SlotI = 11633fd3a840c50fe4ede1b200be18990bc955c536fdJakob Stoklund Olesen std::lower_bound(Slots.begin(), Slots.end(), LiveI->start); 11643fd3a840c50fe4ede1b200be18990bc955c536fdJakob Stoklund Olesen ArrayRef<SlotIndex>::iterator SlotE = Slots.end(); 11653fd3a840c50fe4ede1b200be18990bc955c536fdJakob Stoklund Olesen 11663fd3a840c50fe4ede1b200be18990bc955c536fdJakob Stoklund Olesen // No slots in range, LI begins after the last call. 11673fd3a840c50fe4ede1b200be18990bc955c536fdJakob Stoklund Olesen if (SlotI == SlotE) 11683fd3a840c50fe4ede1b200be18990bc955c536fdJakob Stoklund Olesen return false; 11693fd3a840c50fe4ede1b200be18990bc955c536fdJakob Stoklund Olesen 11703fd3a840c50fe4ede1b200be18990bc955c536fdJakob Stoklund Olesen bool Found = false; 11713fd3a840c50fe4ede1b200be18990bc955c536fdJakob Stoklund Olesen for (;;) { 11723fd3a840c50fe4ede1b200be18990bc955c536fdJakob Stoklund Olesen assert(*SlotI >= LiveI->start); 11733fd3a840c50fe4ede1b200be18990bc955c536fdJakob Stoklund Olesen // Loop over all slots overlapping this segment. 11743fd3a840c50fe4ede1b200be18990bc955c536fdJakob Stoklund Olesen while (*SlotI < LiveI->end) { 11753fd3a840c50fe4ede1b200be18990bc955c536fdJakob Stoklund Olesen // *SlotI overlaps LI. Collect mask bits. 11763fd3a840c50fe4ede1b200be18990bc955c536fdJakob Stoklund Olesen if (!Found) { 11773fd3a840c50fe4ede1b200be18990bc955c536fdJakob Stoklund Olesen // This is the first overlap. Initialize UsableRegs to all ones. 11783fd3a840c50fe4ede1b200be18990bc955c536fdJakob Stoklund Olesen UsableRegs.clear(); 11793fd3a840c50fe4ede1b200be18990bc955c536fdJakob Stoklund Olesen UsableRegs.resize(tri_->getNumRegs(), true); 11803fd3a840c50fe4ede1b200be18990bc955c536fdJakob Stoklund Olesen Found = true; 11813fd3a840c50fe4ede1b200be18990bc955c536fdJakob Stoklund Olesen } 11823fd3a840c50fe4ede1b200be18990bc955c536fdJakob Stoklund Olesen // Remove usable registers clobbered by this mask. 11839f10ac63a3a2a74ac381a05d8ba0f7b1b455a6b6Jakob Stoklund Olesen UsableRegs.clearBitsNotInMask(Bits[SlotI-Slots.begin()]); 11843fd3a840c50fe4ede1b200be18990bc955c536fdJakob Stoklund Olesen if (++SlotI == SlotE) 11853fd3a840c50fe4ede1b200be18990bc955c536fdJakob Stoklund Olesen return Found; 11863fd3a840c50fe4ede1b200be18990bc955c536fdJakob Stoklund Olesen } 11873fd3a840c50fe4ede1b200be18990bc955c536fdJakob Stoklund Olesen // *SlotI is beyond the current LI segment. 11883fd3a840c50fe4ede1b200be18990bc955c536fdJakob Stoklund Olesen LiveI = LI.advanceTo(LiveI, *SlotI); 11893fd3a840c50fe4ede1b200be18990bc955c536fdJakob Stoklund Olesen if (LiveI == LiveE) 11903fd3a840c50fe4ede1b200be18990bc955c536fdJakob Stoklund Olesen return Found; 11913fd3a840c50fe4ede1b200be18990bc955c536fdJakob Stoklund Olesen // Advance SlotI until it overlaps. 11923fd3a840c50fe4ede1b200be18990bc955c536fdJakob Stoklund Olesen while (*SlotI < LiveI->start) 11933fd3a840c50fe4ede1b200be18990bc955c536fdJakob Stoklund Olesen if (++SlotI == SlotE) 11943fd3a840c50fe4ede1b200be18990bc955c536fdJakob Stoklund Olesen return Found; 11953fd3a840c50fe4ede1b200be18990bc955c536fdJakob Stoklund Olesen } 11963fd3a840c50fe4ede1b200be18990bc955c536fdJakob Stoklund Olesen} 1197