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" 2484bc5427d6883f73cfeae3da640acd011d35c006Chris Lattner#include "llvm/CodeGen/MachineRegisterInfo.h" 25ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos#include "llvm/CodeGen/Passes.h" 266f0d024a534af18d9e60b3ea757376cd8a3a980eDan Gohman#include "llvm/Target/TargetRegisterInfo.h" 27ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos#include "llvm/Target/TargetInstrInfo.h" 28ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos#include "llvm/Target/TargetMachine.h" 29551ccae044b0ff658fe629dd67edd5ffe75d10e8Reid Spencer#include "llvm/Support/CommandLine.h" 30551ccae044b0ff658fe629dd67edd5ffe75d10e8Reid Spencer#include "llvm/Support/Debug.h" 317d696d80409aad20bb5da0fc4eccab941dd371d4Torok Edwin#include "llvm/Support/ErrorHandling.h" 327d696d80409aad20bb5da0fc4eccab941dd371d4Torok Edwin#include "llvm/Support/raw_ostream.h" 33d35576b3c026cb323c4c240f0b20cf56089a1e5bAndrew Trick#include "llvm/ADT/DenseSet.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) 528dd26253f54247e77e5accfdd70e7b4bf27b39c2Andrew TrickINITIALIZE_PASS_DEPENDENCY(MachineDominatorTree) 532ab36d350293c77fc8941ce1023e4899df7e3a82Owen AndersonINITIALIZE_PASS_DEPENDENCY(SlotIndexes) 542ab36d350293c77fc8941ce1023e4899df7e3a82Owen AndersonINITIALIZE_PASS_END(LiveIntervals, "liveintervals", 55ce665bd2e2b581ab0858d1afe359192bac96b868Owen Anderson "Live Interval Analysis", false, false) 56ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos 57f7da2c7b0c6293c268881628fc351bed7763f1f4Chris Lattnervoid LiveIntervals::getAnalysisUsage(AnalysisUsage &AU) const { 58845012e6d31799c7fbd1193fa1af8ee2d12e9231Dan Gohman AU.setPreservesCFG(); 596d69ba8a6901c69d78488cbc41f8dbf080618fdeDan Gohman AU.addRequired<AliasAnalysis>(); 606d69ba8a6901c69d78488cbc41f8dbf080618fdeDan Gohman AU.addPreserved<AliasAnalysis>(); 611a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos AU.addRequired<LiveVariables>(); 62148341cc9b60d7d88be9c07a2b32b436e0cd301dEvan Cheng AU.addPreserved<LiveVariables>(); 63d35576b3c026cb323c4c240f0b20cf56089a1e5bAndrew Trick AU.addPreservedID(MachineLoopInfoID); 6467d65bb69d5cad957cbb6d672dc0b4a19c211a42Bill Wendling AU.addPreservedID(MachineDominatorsID); 65233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames AU.addPreserved<SlotIndexes>(); 66233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames AU.addRequiredTransitive<SlotIndexes>(); 671a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos MachineFunctionPass::getAnalysisUsage(AU); 68ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos} 69ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos 70f7da2c7b0c6293c268881628fc351bed7763f1f4Chris Lattnervoid LiveIntervals::releaseMemory() { 7103857b29d8271a23943254579e6cf7b7df4b1bd3Owen Anderson // Free the live intervals themselves. 7220e2839cb975a2d4ee931e1ea4c4660a36ef0177Owen Anderson for (DenseMap<unsigned, LiveInterval*>::iterator I = r2iMap_.begin(), 73d6a6b3b7563a3f54ba48d465fc03ee10bbccb7a8Bob Wilson E = r2iMap_.end(); I != E; ++I) 7403857b29d8271a23943254579e6cf7b7df4b1bd3Owen Anderson delete I->second; 751b2932024f098a6968645ac78d5848951d877c19Jakob Stoklund Olesen 761a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos r2iMap_.clear(); 773fd3a840c50fe4ede1b200be18990bc955c536fdJakob Stoklund Olesen RegMaskSlots.clear(); 783fd3a840c50fe4ede1b200be18990bc955c536fdJakob Stoklund Olesen RegMaskBits.clear(); 7934e85d0307e3c17e5061622dccf8a20e5457b099Jakob Stoklund Olesen RegMaskBlocks.clear(); 80ffd1326ff8dfc652a8026c3faebf55bbba7c32c7Lang Hames 81ce9a20b808ba48adf72e0c0615f903a65e9f9eb8Benjamin Kramer // Release VNInfo memory regions, VNInfo objects don't need to be dtor'd. 82ce9a20b808ba48adf72e0c0615f903a65e9f9eb8Benjamin Kramer VNInfoAllocator.Reset(); 83993141402f57b4d4cbb7f8a3113f19c61688f9b7Evan Cheng} 84993141402f57b4d4cbb7f8a3113f19c61688f9b7Evan Cheng 8580b3ce65e294a28b88c882d44a5e749a2924c9e3Owen Anderson/// runOnMachineFunction - Register allocate the whole function 8680b3ce65e294a28b88c882d44a5e749a2924c9e3Owen Anderson/// 8780b3ce65e294a28b88c882d44a5e749a2924c9e3Owen Andersonbool LiveIntervals::runOnMachineFunction(MachineFunction &fn) { 8880b3ce65e294a28b88c882d44a5e749a2924c9e3Owen Anderson mf_ = &fn; 8980b3ce65e294a28b88c882d44a5e749a2924c9e3Owen Anderson mri_ = &mf_->getRegInfo(); 9080b3ce65e294a28b88c882d44a5e749a2924c9e3Owen Anderson tm_ = &fn.getTarget(); 9180b3ce65e294a28b88c882d44a5e749a2924c9e3Owen Anderson tri_ = tm_->getRegisterInfo(); 9280b3ce65e294a28b88c882d44a5e749a2924c9e3Owen Anderson tii_ = tm_->getInstrInfo(); 936d69ba8a6901c69d78488cbc41f8dbf080618fdeDan Gohman aa_ = &getAnalysis<AliasAnalysis>(); 9480b3ce65e294a28b88c882d44a5e749a2924c9e3Owen Anderson lv_ = &getAnalysis<LiveVariables>(); 95233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames indexes_ = &getAnalysis<SlotIndexes>(); 9680b3ce65e294a28b88c882d44a5e749a2924c9e3Owen Anderson allocatableRegs_ = tri_->getAllocatableSet(fn); 97342c64c90418a97ec26303c27d1829edd994d9a9Lang Hames reservedRegs_ = tri_->getReservedRegs(fn); 98ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos 991a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos computeIntervals(); 100ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos 1011a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos numIntervals += getNumIntervals(); 102843b160a2040b3ec4d3452678450afa11704c473Alkis Evlogimenos 10370ca358b7d540b6061236ddf757085042873c12cChris Lattner DEBUG(dump()); 1041a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos return true; 105ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos} 106ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos 10770ca358b7d540b6061236ddf757085042873c12cChris Lattner/// print - Implement the dump method. 10845cfe545ec8177262dabc70580ce05feaa1c3880Chris Lattnervoid LiveIntervals::print(raw_ostream &OS, const Module* ) const { 109705e07f578e2b3af47ddab610feb4e7f2d3063a5Chris Lattner OS << "********** INTERVALS **********\n"; 110f658af5484855b37c6c651e9e5e671982d39af26Jakob Stoklund Olesen 111f658af5484855b37c6c651e9e5e671982d39af26Jakob Stoklund Olesen // Dump the physregs. 112f658af5484855b37c6c651e9e5e671982d39af26Jakob Stoklund Olesen for (unsigned Reg = 1, RegE = tri_->getNumRegs(); Reg != RegE; ++Reg) 113f658af5484855b37c6c651e9e5e671982d39af26Jakob Stoklund Olesen if (const LiveInterval *LI = r2iMap_.lookup(Reg)) { 114f658af5484855b37c6c651e9e5e671982d39af26Jakob Stoklund Olesen LI->print(OS, tri_); 115f658af5484855b37c6c651e9e5e671982d39af26Jakob Stoklund Olesen OS << '\n'; 116f658af5484855b37c6c651e9e5e671982d39af26Jakob Stoklund Olesen } 117f658af5484855b37c6c651e9e5e671982d39af26Jakob Stoklund Olesen 118f658af5484855b37c6c651e9e5e671982d39af26Jakob Stoklund Olesen // Dump the virtregs. 119f658af5484855b37c6c651e9e5e671982d39af26Jakob Stoklund Olesen for (unsigned Reg = 0, RegE = mri_->getNumVirtRegs(); Reg != RegE; ++Reg) 120f658af5484855b37c6c651e9e5e671982d39af26Jakob Stoklund Olesen if (const LiveInterval *LI = 121f658af5484855b37c6c651e9e5e671982d39af26Jakob Stoklund Olesen r2iMap_.lookup(TargetRegisterInfo::index2VirtReg(Reg))) { 122f658af5484855b37c6c651e9e5e671982d39af26Jakob Stoklund Olesen LI->print(OS, tri_); 123f658af5484855b37c6c651e9e5e671982d39af26Jakob Stoklund Olesen OS << '\n'; 124f658af5484855b37c6c651e9e5e671982d39af26Jakob Stoklund Olesen } 12570ca358b7d540b6061236ddf757085042873c12cChris Lattner 126752195e3c662c6b5db042cf897c984624720f3b8Evan Cheng printInstrs(OS); 127752195e3c662c6b5db042cf897c984624720f3b8Evan Cheng} 128752195e3c662c6b5db042cf897c984624720f3b8Evan Cheng 129752195e3c662c6b5db042cf897c984624720f3b8Evan Chengvoid LiveIntervals::printInstrs(raw_ostream &OS) const { 130705e07f578e2b3af47ddab610feb4e7f2d3063a5Chris Lattner OS << "********** MACHINEINSTRS **********\n"; 131f4a1e1a69f0727762a73ef0d551e3bbd16b7c04eJakob Stoklund Olesen mf_->print(OS, indexes_); 13270ca358b7d540b6061236ddf757085042873c12cChris Lattner} 13370ca358b7d540b6061236ddf757085042873c12cChris Lattner 134752195e3c662c6b5db042cf897c984624720f3b8Evan Chengvoid LiveIntervals::dumpInstrs() const { 1358a34229dcf484739119857988772572ef0cad9f2David Greene printInstrs(dbgs()); 136752195e3c662c6b5db042cf897c984624720f3b8Evan Cheng} 137752195e3c662c6b5db042cf897c984624720f3b8Evan Cheng 138afff40a62da19be15295c0f8ed5d4d450ccb45a5Evan Chengstatic 1393749943648772743c9c0e852553e50e6700a0c1bEvan Chengbool MultipleDefsBySameMI(const MachineInstr &MI, unsigned MOIdx) { 140afff40a62da19be15295c0f8ed5d4d450ccb45a5Evan Cheng unsigned Reg = MI.getOperand(MOIdx).getReg(); 141afff40a62da19be15295c0f8ed5d4d450ccb45a5Evan Cheng for (unsigned i = MOIdx+1, e = MI.getNumOperands(); i < e; ++i) { 142afff40a62da19be15295c0f8ed5d4d450ccb45a5Evan Cheng const MachineOperand &MO = MI.getOperand(i); 143afff40a62da19be15295c0f8ed5d4d450ccb45a5Evan Cheng if (!MO.isReg()) 144afff40a62da19be15295c0f8ed5d4d450ccb45a5Evan Cheng continue; 145afff40a62da19be15295c0f8ed5d4d450ccb45a5Evan Cheng if (MO.getReg() == Reg && MO.isDef()) { 146afff40a62da19be15295c0f8ed5d4d450ccb45a5Evan Cheng assert(MI.getOperand(MOIdx).getSubReg() != MO.getSubReg() && 147afff40a62da19be15295c0f8ed5d4d450ccb45a5Evan Cheng MI.getOperand(MOIdx).getSubReg() && 148ed2185e171a86b8c0e166803fd4066383a6cff08Jakob Stoklund Olesen (MO.getSubReg() || MO.isImplicit())); 149afff40a62da19be15295c0f8ed5d4d450ccb45a5Evan Cheng return true; 150afff40a62da19be15295c0f8ed5d4d450ccb45a5Evan Cheng } 151afff40a62da19be15295c0f8ed5d4d450ccb45a5Evan Cheng } 152afff40a62da19be15295c0f8ed5d4d450ccb45a5Evan Cheng return false; 153afff40a62da19be15295c0f8ed5d4d450ccb45a5Evan Cheng} 154afff40a62da19be15295c0f8ed5d4d450ccb45a5Evan Cheng 1553749943648772743c9c0e852553e50e6700a0c1bEvan Cheng/// isPartialRedef - Return true if the specified def at the specific index is 1563749943648772743c9c0e852553e50e6700a0c1bEvan Cheng/// partially re-defining the specified live interval. A common case of this is 1571b2932024f098a6968645ac78d5848951d877c19Jakob Stoklund Olesen/// a definition of the sub-register. 1583749943648772743c9c0e852553e50e6700a0c1bEvan Chengbool LiveIntervals::isPartialRedef(SlotIndex MIIdx, MachineOperand &MO, 1593749943648772743c9c0e852553e50e6700a0c1bEvan Cheng LiveInterval &interval) { 1603749943648772743c9c0e852553e50e6700a0c1bEvan Cheng if (!MO.getSubReg() || MO.isEarlyClobber()) 1613749943648772743c9c0e852553e50e6700a0c1bEvan Cheng return false; 1623749943648772743c9c0e852553e50e6700a0c1bEvan Cheng 1632debd48ca790ac01be6e12e094fdf4fdcadc8364Jakob Stoklund Olesen SlotIndex RedefIndex = MIIdx.getRegSlot(); 1643749943648772743c9c0e852553e50e6700a0c1bEvan Cheng const LiveRange *OldLR = 1652debd48ca790ac01be6e12e094fdf4fdcadc8364Jakob Stoklund Olesen interval.getLiveRangeContaining(RedefIndex.getRegSlot(true)); 1666e2968c85c1e162ee5bc813769eab223e3df0f15Lang Hames MachineInstr *DefMI = getInstructionFromIndex(OldLR->valno->def); 1676e2968c85c1e162ee5bc813769eab223e3df0f15Lang Hames if (DefMI != 0) { 1683749943648772743c9c0e852553e50e6700a0c1bEvan Cheng return DefMI->findRegisterDefOperandIdx(interval.reg) != -1; 1693749943648772743c9c0e852553e50e6700a0c1bEvan Cheng } 1703749943648772743c9c0e852553e50e6700a0c1bEvan Cheng return false; 1713749943648772743c9c0e852553e50e6700a0c1bEvan Cheng} 1723749943648772743c9c0e852553e50e6700a0c1bEvan Cheng 173be4f88a8b8bb3311e0dc4cde8533763d7923c3eaChris Lattnervoid LiveIntervals::handleVirtualRegisterDef(MachineBasicBlock *mbb, 174ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos MachineBasicBlock::iterator mi, 175233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames SlotIndex MIIdx, 1768651125d2885f74546b6e2a556082111d5b75da3Lang Hames MachineOperand& MO, 177ef0732d25a9882c947984ae3f2afbef5463ba00fEvan Cheng unsigned MOIdx, 178be4f88a8b8bb3311e0dc4cde8533763d7923c3eaChris Lattner LiveInterval &interval) { 1794314268128be6d54c9a7f0709680e5a5b40f3ab3Jakob Stoklund Olesen DEBUG(dbgs() << "\t\tregister: " << PrintReg(interval.reg, tri_)); 180419852ca8a01aecde4c0e20af6b7bd6450e70f87Evan Cheng 181706515727c6d024015fffded2b3109a4f0ac5299Alkis Evlogimenos // Virtual registers may be defined multiple times (due to phi 182706515727c6d024015fffded2b3109a4f0ac5299Alkis Evlogimenos // elimination and 2-addr elimination). Much of what we do only has to be 183706515727c6d024015fffded2b3109a4f0ac5299Alkis Evlogimenos // done once for the vreg. We use an empty interval to detect the first 1841a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // time we see a vreg. 185d129d73b725e32d2fc0c87f392c239db8801e922Evan Cheng LiveVariables::VarInfo& vi = lv_->getVarInfo(interval.reg); 1861a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos if (interval.empty()) { 1871a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // Get the Idx of the defining instructions. 188d14614e6777771f8fec3062bcaf2986c189ac84dJakob Stoklund Olesen SlotIndex defIndex = MIIdx.getRegSlot(MO.isEarlyClobber()); 18963e6a488cb6c29983415221719d05fbf99e00193Jakob Stoklund Olesen 19092b7df07afc90ea5ecc1d9c4ede80a3a3468c577Jakob Stoklund Olesen // Make sure the first definition is not a partial redefinition. 19192b7df07afc90ea5ecc1d9c4ede80a3a3468c577Jakob Stoklund Olesen assert(!MO.readsReg() && "First def cannot also read virtual register " 19292b7df07afc90ea5ecc1d9c4ede80a3a3468c577Jakob Stoklund Olesen "missing <undef> flag?"); 19363e6a488cb6c29983415221719d05fbf99e00193Jakob Stoklund Olesen 1943b1088a2cc15a39c7a7b8dd95a56143f1dda6863Jakob Stoklund Olesen VNInfo *ValNo = interval.getNextValue(defIndex, VNInfoAllocator); 1957ecb38be0a533e7b9c7d3b8e9b5c8a6fa5f6b349Evan Cheng assert(ValNo->id == 0 && "First value in interval is not 0?"); 1961a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos 1971a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // Loop over all of the blocks that the vreg is defined in. There are 1981a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // two cases we have to handle here. The most common case is a vreg 1991a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // whose lifetime is contained within a basic block. In this case there 2001a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // will be a single kill, in MBB, which comes after the definition. 2011a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos if (vi.Kills.size() == 1 && vi.Kills[0]->getParent() == mbb) { 2021a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // FIXME: what about dead vars? 203233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames SlotIndex killIdx; 2041a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos if (vi.Kills[0] != mi) 2052debd48ca790ac01be6e12e094fdf4fdcadc8364Jakob Stoklund Olesen killIdx = getInstructionIndex(vi.Kills[0]).getRegSlot(); 2061a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos else 2072debd48ca790ac01be6e12e094fdf4fdcadc8364Jakob Stoklund Olesen killIdx = defIndex.getDeadSlot(); 2081a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos 2091a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // If the kill happens after the definition, we have an intra-block 2101a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // live range. 2111a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos if (killIdx > defIndex) { 212493a3d015cbb2bcc18d9293a4dec3b35c7493818Jeffrey Yasskin assert(vi.AliveBlocks.empty() && 2131a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos "Shouldn't be alive across any blocks!"); 2147ecb38be0a533e7b9c7d3b8e9b5c8a6fa5f6b349Evan Cheng LiveRange LR(defIndex, killIdx, ValNo); 2151a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos interval.addRange(LR); 2168a34229dcf484739119857988772572ef0cad9f2David Greene DEBUG(dbgs() << " +" << LR << "\n"); 2171a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos return; 2181a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos } 2191a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos } 2206097d13b2a624048dbe02e39e2dfb23bfa269b64Chris Lattner 2211a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // The other case we handle is when a virtual register lives to the end 2221a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // of the defining block, potentially live across some blocks, then is 2231a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // live into some number of blocks, but gets killed. Start by adding a 2241a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // range that goes from this definition to the end of the defining block. 22574ab5eeffbd70f2387338e3ee8195be9f73e6dd8Lang Hames LiveRange NewLR(defIndex, getMBBEndIdx(mbb), ValNo); 2268a34229dcf484739119857988772572ef0cad9f2David Greene DEBUG(dbgs() << " +" << NewLR); 2271a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos interval.addRange(NewLR); 2281a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos 229dcfe5f30b5e262971f601a65bebcc0367fef56c5Jakob Stoklund Olesen bool PHIJoin = lv_->isPHIJoin(interval.reg); 230dcfe5f30b5e262971f601a65bebcc0367fef56c5Jakob Stoklund Olesen 231dcfe5f30b5e262971f601a65bebcc0367fef56c5Jakob Stoklund Olesen if (PHIJoin) { 232dcfe5f30b5e262971f601a65bebcc0367fef56c5Jakob Stoklund Olesen // A phi join register is killed at the end of the MBB and revived as a new 233dcfe5f30b5e262971f601a65bebcc0367fef56c5Jakob Stoklund Olesen // valno in the killing blocks. 234dcfe5f30b5e262971f601a65bebcc0367fef56c5Jakob Stoklund Olesen assert(vi.AliveBlocks.empty() && "Phi join can't pass through blocks"); 235dcfe5f30b5e262971f601a65bebcc0367fef56c5Jakob Stoklund Olesen DEBUG(dbgs() << " phi-join"); 236dcfe5f30b5e262971f601a65bebcc0367fef56c5Jakob Stoklund Olesen ValNo->setHasPHIKill(true); 237dcfe5f30b5e262971f601a65bebcc0367fef56c5Jakob Stoklund Olesen } else { 238dcfe5f30b5e262971f601a65bebcc0367fef56c5Jakob Stoklund Olesen // Iterate over all of the blocks that the variable is completely 239dcfe5f30b5e262971f601a65bebcc0367fef56c5Jakob Stoklund Olesen // live in, adding [insrtIndex(begin), instrIndex(end)+4) to the 240dcfe5f30b5e262971f601a65bebcc0367fef56c5Jakob Stoklund Olesen // live interval. 241dcfe5f30b5e262971f601a65bebcc0367fef56c5Jakob Stoklund Olesen for (SparseBitVector<>::iterator I = vi.AliveBlocks.begin(), 242dcfe5f30b5e262971f601a65bebcc0367fef56c5Jakob Stoklund Olesen E = vi.AliveBlocks.end(); I != E; ++I) { 243dcfe5f30b5e262971f601a65bebcc0367fef56c5Jakob Stoklund Olesen MachineBasicBlock *aliveBlock = mf_->getBlockNumbered(*I); 244dcfe5f30b5e262971f601a65bebcc0367fef56c5Jakob Stoklund Olesen LiveRange LR(getMBBStartIdx(aliveBlock), getMBBEndIdx(aliveBlock), ValNo); 245dcfe5f30b5e262971f601a65bebcc0367fef56c5Jakob Stoklund Olesen interval.addRange(LR); 246dcfe5f30b5e262971f601a65bebcc0367fef56c5Jakob Stoklund Olesen DEBUG(dbgs() << " +" << LR); 247dcfe5f30b5e262971f601a65bebcc0367fef56c5Jakob Stoklund Olesen } 2481a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos } 2491a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos 2501a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // Finally, this virtual register is live from the start of any killing 2511a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // block to the 'use' slot of the killing instruction. 2521a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos for (unsigned i = 0, e = vi.Kills.size(); i != e; ++i) { 2531a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos MachineInstr *Kill = vi.Kills[i]; 254dcfe5f30b5e262971f601a65bebcc0367fef56c5Jakob Stoklund Olesen SlotIndex Start = getMBBStartIdx(Kill->getParent()); 2552debd48ca790ac01be6e12e094fdf4fdcadc8364Jakob Stoklund Olesen SlotIndex killIdx = getInstructionIndex(Kill).getRegSlot(); 256dcfe5f30b5e262971f601a65bebcc0367fef56c5Jakob Stoklund Olesen 257dcfe5f30b5e262971f601a65bebcc0367fef56c5Jakob Stoklund Olesen // Create interval with one of a NEW value number. Note that this value 258dcfe5f30b5e262971f601a65bebcc0367fef56c5Jakob Stoklund Olesen // number isn't actually defined by an instruction, weird huh? :) 259dcfe5f30b5e262971f601a65bebcc0367fef56c5Jakob Stoklund Olesen if (PHIJoin) { 2606e2968c85c1e162ee5bc813769eab223e3df0f15Lang Hames assert(getInstructionFromIndex(Start) == 0 && 2616e2968c85c1e162ee5bc813769eab223e3df0f15Lang Hames "PHI def index points at actual instruction."); 2623b1088a2cc15a39c7a7b8dd95a56143f1dda6863Jakob Stoklund Olesen ValNo = interval.getNextValue(Start, VNInfoAllocator); 263dcfe5f30b5e262971f601a65bebcc0367fef56c5Jakob Stoklund Olesen ValNo->setIsPHIDef(true); 264dcfe5f30b5e262971f601a65bebcc0367fef56c5Jakob Stoklund Olesen } 265dcfe5f30b5e262971f601a65bebcc0367fef56c5Jakob Stoklund Olesen LiveRange LR(Start, killIdx, ValNo); 2661a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos interval.addRange(LR); 2678a34229dcf484739119857988772572ef0cad9f2David Greene DEBUG(dbgs() << " +" << LR); 2681a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos } 2691a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos 2701a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos } else { 2713749943648772743c9c0e852553e50e6700a0c1bEvan Cheng if (MultipleDefsBySameMI(*mi, MOIdx)) 272761fd4c1d97977c16de9f0cf921056a37b906304Nick Lewycky // Multiple defs of the same virtual register by the same instruction. 273761fd4c1d97977c16de9f0cf921056a37b906304Nick Lewycky // e.g. %reg1031:5<def>, %reg1031:6<def> = VLD1q16 %reg1024<kill>, ... 274afff40a62da19be15295c0f8ed5d4d450ccb45a5Evan Cheng // This is likely due to elimination of REG_SEQUENCE instructions. Return 275afff40a62da19be15295c0f8ed5d4d450ccb45a5Evan Cheng // here since there is nothing to do. 276afff40a62da19be15295c0f8ed5d4d450ccb45a5Evan Cheng return; 277afff40a62da19be15295c0f8ed5d4d450ccb45a5Evan Cheng 2781a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // If this is the second time we see a virtual register definition, it 2791a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // must be due to phi elimination or two addr elimination. If this is 280bf105c842450d3308d024be203ddd533f37051ecEvan Cheng // the result of two address elimination, then the vreg is one of the 281bf105c842450d3308d024be203ddd533f37051ecEvan Cheng // def-and-use register operand. 2823749943648772743c9c0e852553e50e6700a0c1bEvan Cheng 2833749943648772743c9c0e852553e50e6700a0c1bEvan Cheng // It may also be partial redef like this: 2841b2932024f098a6968645ac78d5848951d877c19Jakob Stoklund Olesen // 80 %reg1041:6<def> = VSHRNv4i16 %reg1034<kill>, 12, pred:14, pred:%reg0 2851b2932024f098a6968645ac78d5848951d877c19Jakob Stoklund Olesen // 120 %reg1041:5<def> = VSHRNv4i16 %reg1039<kill>, 12, pred:14, pred:%reg0 2863749943648772743c9c0e852553e50e6700a0c1bEvan Cheng bool PartReDef = isPartialRedef(MIIdx, MO, interval); 2873749943648772743c9c0e852553e50e6700a0c1bEvan Cheng if (PartReDef || mi->isRegTiedToUseOperand(MOIdx)) { 2881a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // If this is a two-address definition, then we have already processed 2891a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // the live range. The only problem is that we didn't realize there 2901a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // are actually two values in the live interval. Because of this we 2911a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // need to take the LiveRegion that defines this register and split it 2921a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // into two values. 293d14614e6777771f8fec3062bcaf2986c189ac84dJakob Stoklund Olesen SlotIndex RedefIndex = MIIdx.getRegSlot(MO.isEarlyClobber()); 2941a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos 29535f291d2c5f80e8e713704190230064311bbbbbeLang Hames const LiveRange *OldLR = 2962debd48ca790ac01be6e12e094fdf4fdcadc8364Jakob Stoklund Olesen interval.getLiveRangeContaining(RedefIndex.getRegSlot(true)); 2977ecb38be0a533e7b9c7d3b8e9b5c8a6fa5f6b349Evan Cheng VNInfo *OldValNo = OldLR->valno; 2982debd48ca790ac01be6e12e094fdf4fdcadc8364Jakob Stoklund Olesen SlotIndex DefIndex = OldValNo->def.getRegSlot(); 2994f8ff168de12eabdeb4b9437bf9402489ecf85cbEvan Cheng 300c66d0f2a9386cc7cb3237b8e3cace2b62a9c7dc8Jakob Stoklund Olesen // Delete the previous value, which should be short and continuous, 301be4f88a8b8bb3311e0dc4cde8533763d7923c3eaChris Lattner // because the 2-addr copy must be in the same MBB as the redef. 3021a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos interval.removeRange(DefIndex, RedefIndex); 303706515727c6d024015fffded2b3109a4f0ac5299Alkis Evlogimenos 30491725b75852443923b419fd23215194cfc65dd88Chris Lattner // The new value number (#1) is defined by the instruction we claimed 30591725b75852443923b419fd23215194cfc65dd88Chris Lattner // defined value #0. 3066e2968c85c1e162ee5bc813769eab223e3df0f15Lang Hames VNInfo *ValNo = interval.createValueCopy(OldValNo, VNInfoAllocator); 307857c4e01f85601cf2084adb860616256ee47c177Lang Hames 30891725b75852443923b419fd23215194cfc65dd88Chris Lattner // Value#0 is now defined by the 2-addr instruction. 3093b1088a2cc15a39c7a7b8dd95a56143f1dda6863Jakob Stoklund Olesen OldValNo->def = RedefIndex; 3101b2932024f098a6968645ac78d5848951d877c19Jakob Stoklund Olesen 311be4f88a8b8bb3311e0dc4cde8533763d7923c3eaChris Lattner // Add the new live interval which replaces the range for the input copy. 312be4f88a8b8bb3311e0dc4cde8533763d7923c3eaChris Lattner LiveRange LR(DefIndex, RedefIndex, ValNo); 3138a34229dcf484739119857988772572ef0cad9f2David Greene DEBUG(dbgs() << " replace range with " << LR); 3141a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos interval.addRange(LR); 3151a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos 3161a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // If this redefinition is dead, we need to add a dummy unit live 3171a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // range covering the def slot. 3186b098dee286cc6fe5a5a476464d92dec5602e406Owen Anderson if (MO.isDead()) 3192debd48ca790ac01be6e12e094fdf4fdcadc8364Jakob Stoklund Olesen interval.addRange(LiveRange(RedefIndex, RedefIndex.getDeadSlot(), 320233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames OldValNo)); 3211a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos 3228e6179fb134af929ee7c937c82d9dc1c9a104c5fBill Wendling DEBUG({ 3238a34229dcf484739119857988772572ef0cad9f2David Greene dbgs() << " RESULT: "; 3248a34229dcf484739119857988772572ef0cad9f2David Greene interval.print(dbgs(), tri_); 3258e6179fb134af929ee7c937c82d9dc1c9a104c5fBill Wendling }); 3263749943648772743c9c0e852553e50e6700a0c1bEvan Cheng } else if (lv_->isPHIJoin(interval.reg)) { 3271a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // In the case of PHI elimination, each variable definition is only 3281a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // live until the end of the block. We've already taken care of the 3291a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // rest of the live range. 330dcfe5f30b5e262971f601a65bebcc0367fef56c5Jakob Stoklund Olesen 3312debd48ca790ac01be6e12e094fdf4fdcadc8364Jakob Stoklund Olesen SlotIndex defIndex = MIIdx.getRegSlot(); 332fb11288109329cb736d9f49769581a0d0c23fe19Evan Cheng if (MO.isEarlyClobber()) 3332debd48ca790ac01be6e12e094fdf4fdcadc8364Jakob Stoklund Olesen defIndex = MIIdx.getRegSlot(true); 334752195e3c662c6b5db042cf897c984624720f3b8Evan Cheng 3353b1088a2cc15a39c7a7b8dd95a56143f1dda6863Jakob Stoklund Olesen VNInfo *ValNo = interval.getNextValue(defIndex, VNInfoAllocator); 3361b2932024f098a6968645ac78d5848951d877c19Jakob Stoklund Olesen 33774ab5eeffbd70f2387338e3ee8195be9f73e6dd8Lang Hames SlotIndex killIndex = getMBBEndIdx(mbb); 3387ecb38be0a533e7b9c7d3b8e9b5c8a6fa5f6b349Evan Cheng LiveRange LR(defIndex, killIndex, ValNo); 3391a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos interval.addRange(LR); 340857c4e01f85601cf2084adb860616256ee47c177Lang Hames ValNo->setHasPHIKill(true); 341dcfe5f30b5e262971f601a65bebcc0367fef56c5Jakob Stoklund Olesen DEBUG(dbgs() << " phi-join +" << LR); 3423749943648772743c9c0e852553e50e6700a0c1bEvan Cheng } else { 3433749943648772743c9c0e852553e50e6700a0c1bEvan Cheng llvm_unreachable("Multiply defined register"); 344dd2cc65f34f9b7bfda1cd0c42becedfc361d46f8Alkis Evlogimenos } 3451a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos } 346ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos 3478a34229dcf484739119857988772572ef0cad9f2David Greene DEBUG(dbgs() << '\n'); 348ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos} 349ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos 350af8b34dae90fd6d146a3b4a83b50751ed21f07c8Lang Hamesstatic bool isRegLiveIntoSuccessor(const MachineBasicBlock *MBB, unsigned Reg) { 351342c64c90418a97ec26303c27d1829edd994d9a9Lang Hames for (MachineBasicBlock::const_succ_iterator SI = MBB->succ_begin(), 352342c64c90418a97ec26303c27d1829edd994d9a9Lang Hames SE = MBB->succ_end(); 353342c64c90418a97ec26303c27d1829edd994d9a9Lang Hames SI != SE; ++SI) { 354342c64c90418a97ec26303c27d1829edd994d9a9Lang Hames const MachineBasicBlock* succ = *SI; 355342c64c90418a97ec26303c27d1829edd994d9a9Lang Hames if (succ->isLiveIn(Reg)) 356342c64c90418a97ec26303c27d1829edd994d9a9Lang Hames return true; 357342c64c90418a97ec26303c27d1829edd994d9a9Lang Hames } 358342c64c90418a97ec26303c27d1829edd994d9a9Lang Hames return false; 359342c64c90418a97ec26303c27d1829edd994d9a9Lang Hames} 360342c64c90418a97ec26303c27d1829edd994d9a9Lang Hames 361f35fef7060c465dd7b578bf6339a18e8a8911888Chris Lattnervoid LiveIntervals::handlePhysicalRegisterDef(MachineBasicBlock *MBB, 362ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos MachineBasicBlock::iterator mi, 363233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames SlotIndex MIIdx, 3646b098dee286cc6fe5a5a476464d92dec5602e406Owen Anderson MachineOperand& MO, 3653b1088a2cc15a39c7a7b8dd95a56143f1dda6863Jakob Stoklund Olesen LiveInterval &interval) { 3664314268128be6d54c9a7f0709680e5a5b40f3ab3Jakob Stoklund Olesen DEBUG(dbgs() << "\t\tregister: " << PrintReg(interval.reg, tri_)); 3671a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos 368233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames SlotIndex baseIndex = MIIdx; 369d14614e6777771f8fec3062bcaf2986c189ac84dJakob Stoklund Olesen SlotIndex start = baseIndex.getRegSlot(MO.isEarlyClobber()); 370233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames SlotIndex end = start; 3711a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos 3721a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // If it is not used after definition, it is considered dead at 3731a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // the instruction defining it. Hence its interval is: 3741a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // [defSlot(def), defSlot(def)+1) 37539faac2531268b8555475796c6071556670dc290Dale Johannesen // For earlyclobbers, the defSlot was pushed back one; the extra 37639faac2531268b8555475796c6071556670dc290Dale Johannesen // advance below compensates. 3776b098dee286cc6fe5a5a476464d92dec5602e406Owen Anderson if (MO.isDead()) { 3788a34229dcf484739119857988772572ef0cad9f2David Greene DEBUG(dbgs() << " dead"); 3792debd48ca790ac01be6e12e094fdf4fdcadc8364Jakob Stoklund Olesen end = start.getDeadSlot(); 380ab4b66d4c279e8cd9e448687020fc838e7881dbcChris Lattner goto exit; 3811a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos } 382ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos 3831a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // If it is not dead on definition, it must be killed by a 3841a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // subsequent instruction. Hence its interval is: 3851a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // [defSlot(def), useSlot(kill)+1) 386233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames baseIndex = baseIndex.getNextIndex(); 3875ab6f5fe666d0e3403d9b777324d1a1999118153Chris Lattner while (++mi != MBB->end()) { 388233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames 389bd63520161629385ff5a0b037eccc770d8d15289Dale Johannesen if (mi->isDebugValue()) 390bd63520161629385ff5a0b037eccc770d8d15289Dale Johannesen continue; 391233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames if (getInstructionFromIndex(baseIndex) == 0) 392233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames baseIndex = indexes_->getNextNonNullIndex(baseIndex); 393233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames 3946130f66eaae89f8878590796977678afa8448926Evan Cheng if (mi->killsRegister(interval.reg, tri_)) { 3958a34229dcf484739119857988772572ef0cad9f2David Greene DEBUG(dbgs() << " killed"); 3962debd48ca790ac01be6e12e094fdf4fdcadc8364Jakob Stoklund Olesen end = baseIndex.getRegSlot(); 397ab4b66d4c279e8cd9e448687020fc838e7881dbcChris Lattner goto exit; 398c45288e06bfe7d0b0e74eff350d280fa6c944373Evan Cheng } else { 3991015ba7018c87f48cc7bb45a564eb4a27241e76aEvan Cheng int DefIdx = mi->findRegisterDefOperandIdx(interval.reg,false,false,tri_); 400c45288e06bfe7d0b0e74eff350d280fa6c944373Evan Cheng if (DefIdx != -1) { 401c45288e06bfe7d0b0e74eff350d280fa6c944373Evan Cheng if (mi->isRegTiedToUseOperand(DefIdx)) { 402c45288e06bfe7d0b0e74eff350d280fa6c944373Evan Cheng // Two-address instruction. 4037e899cbb9127c02c58f6e774186a533b0d00681dJakob Stoklund Olesen end = baseIndex.getRegSlot(mi->getOperand(DefIdx).isEarlyClobber()); 404c45288e06bfe7d0b0e74eff350d280fa6c944373Evan Cheng } else { 405c45288e06bfe7d0b0e74eff350d280fa6c944373Evan Cheng // Another instruction redefines the register before it is ever read. 406bd63520161629385ff5a0b037eccc770d8d15289Dale Johannesen // Then the register is essentially dead at the instruction that 407bd63520161629385ff5a0b037eccc770d8d15289Dale Johannesen // defines it. Hence its interval is: 408c45288e06bfe7d0b0e74eff350d280fa6c944373Evan Cheng // [defSlot(def), defSlot(def)+1) 4098a34229dcf484739119857988772572ef0cad9f2David Greene DEBUG(dbgs() << " dead"); 4102debd48ca790ac01be6e12e094fdf4fdcadc8364Jakob Stoklund Olesen end = start.getDeadSlot(); 411c45288e06bfe7d0b0e74eff350d280fa6c944373Evan Cheng } 412c45288e06bfe7d0b0e74eff350d280fa6c944373Evan Cheng goto exit; 413c45288e06bfe7d0b0e74eff350d280fa6c944373Evan Cheng } 414f35fef7060c465dd7b578bf6339a18e8a8911888Chris Lattner } 4151b2932024f098a6968645ac78d5848951d877c19Jakob Stoklund Olesen 416233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames baseIndex = baseIndex.getNextIndex(); 4171a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos } 4181b2932024f098a6968645ac78d5848951d877c19Jakob Stoklund Olesen 419342c64c90418a97ec26303c27d1829edd994d9a9Lang Hames // If we get here the register *should* be live out. 420342c64c90418a97ec26303c27d1829edd994d9a9Lang Hames assert(!isAllocatable(interval.reg) && "Physregs shouldn't be live out!"); 42102ba13c9897ae2b19f9201e57460d7ee2b753a0bAlkis Evlogimenos 422342c64c90418a97ec26303c27d1829edd994d9a9Lang Hames // FIXME: We need saner rules for reserved regs. 423342c64c90418a97ec26303c27d1829edd994d9a9Lang Hames if (isReserved(interval.reg)) { 424342c64c90418a97ec26303c27d1829edd994d9a9Lang Hames end = start.getDeadSlot(); 425342c64c90418a97ec26303c27d1829edd994d9a9Lang Hames } else { 426342c64c90418a97ec26303c27d1829edd994d9a9Lang Hames // Unreserved, unallocable registers like EFLAGS can be live across basic 427342c64c90418a97ec26303c27d1829edd994d9a9Lang Hames // block boundaries. 428af8b34dae90fd6d146a3b4a83b50751ed21f07c8Lang Hames assert(isRegLiveIntoSuccessor(MBB, interval.reg) && 429af8b34dae90fd6d146a3b4a83b50751ed21f07c8Lang Hames "Unreserved reg not live-out?"); 430342c64c90418a97ec26303c27d1829edd994d9a9Lang Hames end = getMBBEndIdx(MBB); 431342c64c90418a97ec26303c27d1829edd994d9a9Lang Hames } 432ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenosexit: 4331a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos assert(start < end && "did not find end of interval?"); 434f768bba43f5c036039851d2fcca8212edca18467Chris Lattner 43524a3cc4c83e5edb25fadf7b8979a26b4451795c6Evan Cheng // Already exists? Extend old live interval. 43631cc3ec3308c8fafd9865388214ae11662a71af4Jakob Stoklund Olesen VNInfo *ValNo = interval.getVNInfoAt(start); 43731cc3ec3308c8fafd9865388214ae11662a71af4Jakob Stoklund Olesen bool Extend = ValNo != 0; 43831cc3ec3308c8fafd9865388214ae11662a71af4Jakob Stoklund Olesen if (!Extend) 4393b1088a2cc15a39c7a7b8dd95a56143f1dda6863Jakob Stoklund Olesen ValNo = interval.getNextValue(start, VNInfoAllocator); 4407ecb38be0a533e7b9c7d3b8e9b5c8a6fa5f6b349Evan Cheng LiveRange LR(start, end, ValNo); 4411a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos interval.addRange(LR); 4428a34229dcf484739119857988772572ef0cad9f2David Greene DEBUG(dbgs() << " +" << LR << '\n'); 443ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos} 444ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos 445f35fef7060c465dd7b578bf6339a18e8a8911888Chris Lattnervoid LiveIntervals::handleRegisterDef(MachineBasicBlock *MBB, 446f35fef7060c465dd7b578bf6339a18e8a8911888Chris Lattner MachineBasicBlock::iterator MI, 447233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames SlotIndex MIIdx, 448ef0732d25a9882c947984ae3f2afbef5463ba00fEvan Cheng MachineOperand& MO, 449ef0732d25a9882c947984ae3f2afbef5463ba00fEvan Cheng unsigned MOIdx) { 4506b098dee286cc6fe5a5a476464d92dec5602e406Owen Anderson if (TargetRegisterInfo::isVirtualRegister(MO.getReg())) 451ef0732d25a9882c947984ae3f2afbef5463ba00fEvan Cheng handleVirtualRegisterDef(MBB, MI, MIIdx, MO, MOIdx, 4526b098dee286cc6fe5a5a476464d92dec5602e406Owen Anderson getOrCreateInterval(MO.getReg())); 4533b1088a2cc15a39c7a7b8dd95a56143f1dda6863Jakob Stoklund Olesen else 454c45288e06bfe7d0b0e74eff350d280fa6c944373Evan Cheng handlePhysicalRegisterDef(MBB, MI, MIIdx, MO, 4553b1088a2cc15a39c7a7b8dd95a56143f1dda6863Jakob Stoklund Olesen getOrCreateInterval(MO.getReg())); 4564d46e1e521c0df1990ea50f8146d22bd77ea71a6Alkis Evlogimenos} 4574d46e1e521c0df1990ea50f8146d22bd77ea71a6Alkis Evlogimenos 458b371f457b0ea4a652a9f526ba4375c80ae542252Evan Chengvoid LiveIntervals::handleLiveInRegister(MachineBasicBlock *MBB, 459233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames SlotIndex MIIdx, 4604465b6f6b2ebd061f4f321e666b47d540651f686Lang Hames LiveInterval &interval) { 461342c64c90418a97ec26303c27d1829edd994d9a9Lang Hames assert(TargetRegisterInfo::isPhysicalRegister(interval.reg) && 462342c64c90418a97ec26303c27d1829edd994d9a9Lang Hames "Only physical registers can be live in."); 463342c64c90418a97ec26303c27d1829edd994d9a9Lang Hames assert((!isAllocatable(interval.reg) || MBB->getParent()->begin() || 464342c64c90418a97ec26303c27d1829edd994d9a9Lang Hames MBB->isLandingPad()) && 465342c64c90418a97ec26303c27d1829edd994d9a9Lang Hames "Allocatable live-ins only valid for entry blocks and landing pads."); 466342c64c90418a97ec26303c27d1829edd994d9a9Lang Hames 4674314268128be6d54c9a7f0709680e5a5b40f3ab3Jakob Stoklund Olesen DEBUG(dbgs() << "\t\tlivein register: " << PrintReg(interval.reg, tri_)); 468b371f457b0ea4a652a9f526ba4375c80ae542252Evan Cheng 469b371f457b0ea4a652a9f526ba4375c80ae542252Evan Cheng // Look for kills, if it reaches a def before it's killed, then it shouldn't 470b371f457b0ea4a652a9f526ba4375c80ae542252Evan Cheng // be considered a livein. 471b371f457b0ea4a652a9f526ba4375c80ae542252Evan Cheng MachineBasicBlock::iterator mi = MBB->begin(); 4724507f089d48c5adb454cd12b68333d5590ce05ddEvan Cheng MachineBasicBlock::iterator E = MBB->end(); 4734507f089d48c5adb454cd12b68333d5590ce05ddEvan Cheng // Skip over DBG_VALUE at the start of the MBB. 4744507f089d48c5adb454cd12b68333d5590ce05ddEvan Cheng if (mi != E && mi->isDebugValue()) { 4754507f089d48c5adb454cd12b68333d5590ce05ddEvan Cheng while (++mi != E && mi->isDebugValue()) 4764507f089d48c5adb454cd12b68333d5590ce05ddEvan Cheng ; 4774507f089d48c5adb454cd12b68333d5590ce05ddEvan Cheng if (mi == E) 4784507f089d48c5adb454cd12b68333d5590ce05ddEvan Cheng // MBB is empty except for DBG_VALUE's. 4794507f089d48c5adb454cd12b68333d5590ce05ddEvan Cheng return; 4804507f089d48c5adb454cd12b68333d5590ce05ddEvan Cheng } 4814507f089d48c5adb454cd12b68333d5590ce05ddEvan Cheng 482233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames SlotIndex baseIndex = MIIdx; 483233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames SlotIndex start = baseIndex; 484233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames if (getInstructionFromIndex(baseIndex) == 0) 485233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames baseIndex = indexes_->getNextNonNullIndex(baseIndex); 486233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames 487233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames SlotIndex end = baseIndex; 4880076c616e8abc2ecf36600a7ac20ec784420cdc4Evan Cheng bool SeenDefUse = false; 489b371f457b0ea4a652a9f526ba4375c80ae542252Evan Cheng 490bd63520161629385ff5a0b037eccc770d8d15289Dale Johannesen while (mi != E) { 4911d0aeabe3fce2ce6610e988b36582b47a7684f74Dale Johannesen if (mi->killsRegister(interval.reg, tri_)) { 4921d0aeabe3fce2ce6610e988b36582b47a7684f74Dale Johannesen DEBUG(dbgs() << " killed"); 4932debd48ca790ac01be6e12e094fdf4fdcadc8364Jakob Stoklund Olesen end = baseIndex.getRegSlot(); 4941d0aeabe3fce2ce6610e988b36582b47a7684f74Dale Johannesen SeenDefUse = true; 4951d0aeabe3fce2ce6610e988b36582b47a7684f74Dale Johannesen break; 4966b7913893bcd47f52eff71e39e50c42511c4ed36Jakob Stoklund Olesen } else if (mi->modifiesRegister(interval.reg, tri_)) { 4971d0aeabe3fce2ce6610e988b36582b47a7684f74Dale Johannesen // Another instruction redefines the register before it is ever read. 4981d0aeabe3fce2ce6610e988b36582b47a7684f74Dale Johannesen // Then the register is essentially dead at the instruction that defines 4991d0aeabe3fce2ce6610e988b36582b47a7684f74Dale Johannesen // it. Hence its interval is: 5001d0aeabe3fce2ce6610e988b36582b47a7684f74Dale Johannesen // [defSlot(def), defSlot(def)+1) 5011d0aeabe3fce2ce6610e988b36582b47a7684f74Dale Johannesen DEBUG(dbgs() << " dead"); 5022debd48ca790ac01be6e12e094fdf4fdcadc8364Jakob Stoklund Olesen end = start.getDeadSlot(); 5031d0aeabe3fce2ce6610e988b36582b47a7684f74Dale Johannesen SeenDefUse = true; 5041d0aeabe3fce2ce6610e988b36582b47a7684f74Dale Johannesen break; 505bd63520161629385ff5a0b037eccc770d8d15289Dale Johannesen } 5061d0aeabe3fce2ce6610e988b36582b47a7684f74Dale Johannesen 5074507f089d48c5adb454cd12b68333d5590ce05ddEvan Cheng while (++mi != E && mi->isDebugValue()) 5084507f089d48c5adb454cd12b68333d5590ce05ddEvan Cheng // Skip over DBG_VALUE. 5094507f089d48c5adb454cd12b68333d5590ce05ddEvan Cheng ; 5104507f089d48c5adb454cd12b68333d5590ce05ddEvan Cheng if (mi != E) 511233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames baseIndex = indexes_->getNextNonNullIndex(baseIndex); 512b371f457b0ea4a652a9f526ba4375c80ae542252Evan Cheng } 513b371f457b0ea4a652a9f526ba4375c80ae542252Evan Cheng 51475611fb4e6ab253be30ac29a2b15e9bf8c1d146eEvan Cheng // Live-in register might not be used at all. 5150076c616e8abc2ecf36600a7ac20ec784420cdc4Evan Cheng if (!SeenDefUse) { 516af8b34dae90fd6d146a3b4a83b50751ed21f07c8Lang Hames if (isAllocatable(interval.reg) || 517af8b34dae90fd6d146a3b4a83b50751ed21f07c8Lang Hames !isRegLiveIntoSuccessor(MBB, interval.reg)) { 518af8b34dae90fd6d146a3b4a83b50751ed21f07c8Lang Hames // Allocatable registers are never live through. 519af8b34dae90fd6d146a3b4a83b50751ed21f07c8Lang Hames // Non-allocatable registers that aren't live into any successors also 520af8b34dae90fd6d146a3b4a83b50751ed21f07c8Lang Hames // aren't live through. 521342c64c90418a97ec26303c27d1829edd994d9a9Lang Hames DEBUG(dbgs() << " dead"); 522f58e37f957191a3e41f605628c6169fbb1d4f922Lang Hames return; 523342c64c90418a97ec26303c27d1829edd994d9a9Lang Hames } else { 524af8b34dae90fd6d146a3b4a83b50751ed21f07c8Lang Hames // If we get here the register is non-allocatable and live into some 525af8b34dae90fd6d146a3b4a83b50751ed21f07c8Lang Hames // successor. We'll conservatively assume it's live-through. 526342c64c90418a97ec26303c27d1829edd994d9a9Lang Hames DEBUG(dbgs() << " live through"); 527342c64c90418a97ec26303c27d1829edd994d9a9Lang Hames end = getMBBEndIdx(MBB); 528342c64c90418a97ec26303c27d1829edd994d9a9Lang Hames } 52924a3cc4c83e5edb25fadf7b8979a26b4451795c6Evan Cheng } 53024a3cc4c83e5edb25fadf7b8979a26b4451795c6Evan Cheng 5316e2968c85c1e162ee5bc813769eab223e3df0f15Lang Hames SlotIndex defIdx = getMBBStartIdx(MBB); 5326e2968c85c1e162ee5bc813769eab223e3df0f15Lang Hames assert(getInstructionFromIndex(defIdx) == 0 && 5336e2968c85c1e162ee5bc813769eab223e3df0f15Lang Hames "PHI def index points at actual instruction."); 5343b1088a2cc15a39c7a7b8dd95a56143f1dda6863Jakob Stoklund Olesen VNInfo *vni = interval.getNextValue(defIdx, VNInfoAllocator); 535d21c31610c4a10e9e638f4221b5df89ea932e258Lang Hames vni->setIsPHIDef(true); 536d21c31610c4a10e9e638f4221b5df89ea932e258Lang Hames LiveRange LR(start, end, vni); 5373de23e6f6cf337451a0934159da494d645b93133Jakob Stoklund Olesen 5389b25b8ca24d6df2e097741dcc15016772ee4eda7Jim Laskey interval.addRange(LR); 5398a34229dcf484739119857988772572ef0cad9f2David Greene DEBUG(dbgs() << " +" << LR << '\n'); 540b371f457b0ea4a652a9f526ba4375c80ae542252Evan Cheng} 541b371f457b0ea4a652a9f526ba4375c80ae542252Evan Cheng 542ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos/// computeIntervals - computes the live intervals for virtual 5434d46e1e521c0df1990ea50f8146d22bd77ea71a6Alkis Evlogimenos/// registers. for some ordering of the machine instructions [1,N] a 54408cec00588ec1a8fa85b208555f006d7396ae7a4Alkis Evlogimenos/// live interval is an interval [i, j) where 1 <= i <= j < N for 545ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos/// which a variable is live 5461b2932024f098a6968645ac78d5848951d877c19Jakob Stoklund Olesenvoid LiveIntervals::computeIntervals() { 5478a34229dcf484739119857988772572ef0cad9f2David Greene DEBUG(dbgs() << "********** COMPUTING LIVE INTERVALS **********\n" 5488e6179fb134af929ee7c937c82d9dc1c9a104c5fBill Wendling << "********** Function: " 5498e6179fb134af929ee7c937c82d9dc1c9a104c5fBill Wendling << ((Value*)mf_->getFunction())->getName() << '\n'); 550d129d73b725e32d2fc0c87f392c239db8801e922Evan Cheng 55134e85d0307e3c17e5061622dccf8a20e5457b099Jakob Stoklund Olesen RegMaskBlocks.resize(mf_->getNumBlockIDs()); 55234e85d0307e3c17e5061622dccf8a20e5457b099Jakob Stoklund Olesen 553d129d73b725e32d2fc0c87f392c239db8801e922Evan Cheng SmallVector<unsigned, 8> UndefUses; 554428b92eb83b457b71d29d1d4b7900d36a0ce9a53Chris Lattner for (MachineFunction::iterator MBBI = mf_->begin(), E = mf_->end(); 555428b92eb83b457b71d29d1d4b7900d36a0ce9a53Chris Lattner MBBI != E; ++MBBI) { 556428b92eb83b457b71d29d1d4b7900d36a0ce9a53Chris Lattner MachineBasicBlock *MBB = MBBI; 55734e85d0307e3c17e5061622dccf8a20e5457b099Jakob Stoklund Olesen RegMaskBlocks[MBB->getNumber()].first = RegMaskSlots.size(); 55834e85d0307e3c17e5061622dccf8a20e5457b099Jakob Stoklund Olesen 55900a99a35840451a291eb61a192a750908a4073aeEvan Cheng if (MBB->empty()) 56000a99a35840451a291eb61a192a750908a4073aeEvan Cheng continue; 56100a99a35840451a291eb61a192a750908a4073aeEvan Cheng 562134eb73fc35e6ead3cfd3ed5024d0d7efa507441Owen Anderson // Track the index of the current machine instr. 563233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames SlotIndex MIIndex = getMBBStartIdx(MBB); 564ad98f795d0dba3db721139a8a74a98acdce0ff60Bob Wilson DEBUG(dbgs() << "BB#" << MBB->getNumber() 565ad98f795d0dba3db721139a8a74a98acdce0ff60Bob Wilson << ":\t\t# derived from " << MBB->getName() << "\n"); 5661a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos 567cb406c25973b4e88a6c10ad839ef1beeb3664715Dan Gohman // Create intervals for live-ins to this BB first. 56881bf03eb5cd68243eabb52505105aa5f4a831bf3Dan Gohman for (MachineBasicBlock::livein_iterator LI = MBB->livein_begin(), 569cb406c25973b4e88a6c10ad839ef1beeb3664715Dan Gohman LE = MBB->livein_end(); LI != LE; ++LI) { 570cb406c25973b4e88a6c10ad839ef1beeb3664715Dan Gohman handleLiveInRegister(MBB, MIIndex, getOrCreateInterval(*LI)); 571dffb2e83ed2546226d09c40aa43524e2392322daChris Lattner } 5721b2932024f098a6968645ac78d5848951d877c19Jakob Stoklund Olesen 57399500aeb7c9a05db57e228544a3f81de2faf24efOwen Anderson // Skip over empty initial indices. 574233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames if (getInstructionFromIndex(MIIndex) == 0) 575233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames MIIndex = indexes_->getNextNonNullIndex(MIIndex); 5761b2932024f098a6968645ac78d5848951d877c19Jakob Stoklund Olesen 5771caedd056dbc3eda1537ad8251323bd985819b80Dale Johannesen for (MachineBasicBlock::iterator MI = MBB->begin(), miEnd = MBB->end(); 5781caedd056dbc3eda1537ad8251323bd985819b80Dale Johannesen MI != miEnd; ++MI) { 5798a34229dcf484739119857988772572ef0cad9f2David Greene DEBUG(dbgs() << MIIndex << "\t" << *MI); 580518bb53485df640d7b7e3f6b0544099020c42aa7Chris Lattner if (MI->isDebugValue()) 5811caedd056dbc3eda1537ad8251323bd985819b80Dale Johannesen continue; 5823fd3a840c50fe4ede1b200be18990bc955c536fdJakob Stoklund Olesen assert(indexes_->getInstructionFromIndex(MIIndex) == MI && 5833fd3a840c50fe4ede1b200be18990bc955c536fdJakob Stoklund Olesen "Lost SlotIndex synchronization"); 5841a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos 585438f7bc67cf235ccee7e6f7ac7f4ae2186eb8020Evan Cheng // Handle defs. 586428b92eb83b457b71d29d1d4b7900d36a0ce9a53Chris Lattner for (int i = MI->getNumOperands() - 1; i >= 0; --i) { 587428b92eb83b457b71d29d1d4b7900d36a0ce9a53Chris Lattner MachineOperand &MO = MI->getOperand(i); 5883fd3a840c50fe4ede1b200be18990bc955c536fdJakob Stoklund Olesen 5893fd3a840c50fe4ede1b200be18990bc955c536fdJakob Stoklund Olesen // Collect register masks. 5903fd3a840c50fe4ede1b200be18990bc955c536fdJakob Stoklund Olesen if (MO.isRegMask()) { 5913fd3a840c50fe4ede1b200be18990bc955c536fdJakob Stoklund Olesen RegMaskSlots.push_back(MIIndex.getRegSlot()); 5923fd3a840c50fe4ede1b200be18990bc955c536fdJakob Stoklund Olesen RegMaskBits.push_back(MO.getRegMask()); 5933fd3a840c50fe4ede1b200be18990bc955c536fdJakob Stoklund Olesen continue; 5943fd3a840c50fe4ede1b200be18990bc955c536fdJakob Stoklund Olesen } 5953fd3a840c50fe4ede1b200be18990bc955c536fdJakob Stoklund Olesen 596d129d73b725e32d2fc0c87f392c239db8801e922Evan Cheng if (!MO.isReg() || !MO.getReg()) 597d129d73b725e32d2fc0c87f392c239db8801e922Evan Cheng continue; 598d129d73b725e32d2fc0c87f392c239db8801e922Evan Cheng 5991a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // handle register defs - build intervals 600d129d73b725e32d2fc0c87f392c239db8801e922Evan Cheng if (MO.isDef()) 601ef0732d25a9882c947984ae3f2afbef5463ba00fEvan Cheng handleRegisterDef(MBB, MI, MIIndex, MO, i); 602d129d73b725e32d2fc0c87f392c239db8801e922Evan Cheng else if (MO.isUndef()) 603d129d73b725e32d2fc0c87f392c239db8801e922Evan Cheng UndefUses.push_back(MO.getReg()); 6041a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos } 6051b2932024f098a6968645ac78d5848951d877c19Jakob Stoklund Olesen 606233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames // Move to the next instr slot. 607233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames MIIndex = indexes_->getNextNonNullIndex(MIIndex); 608ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos } 60934e85d0307e3c17e5061622dccf8a20e5457b099Jakob Stoklund Olesen 61034e85d0307e3c17e5061622dccf8a20e5457b099Jakob Stoklund Olesen // Compute the number of register mask instructions in this block. 61134e85d0307e3c17e5061622dccf8a20e5457b099Jakob Stoklund Olesen std::pair<unsigned, unsigned> &RMB = RegMaskBlocks[MBB->getNumber()]; 61234e85d0307e3c17e5061622dccf8a20e5457b099Jakob Stoklund Olesen RMB.second = RegMaskSlots.size() - RMB.first;; 6131a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos } 614d129d73b725e32d2fc0c87f392c239db8801e922Evan Cheng 615d129d73b725e32d2fc0c87f392c239db8801e922Evan Cheng // Create empty intervals for registers defined by implicit_def's (except 616d129d73b725e32d2fc0c87f392c239db8801e922Evan Cheng // for those implicit_def that define values which are liveout of their 617d129d73b725e32d2fc0c87f392c239db8801e922Evan Cheng // blocks. 618d129d73b725e32d2fc0c87f392c239db8801e922Evan Cheng for (unsigned i = 0, e = UndefUses.size(); i != e; ++i) { 619d129d73b725e32d2fc0c87f392c239db8801e922Evan Cheng unsigned UndefReg = UndefUses[i]; 620d129d73b725e32d2fc0c87f392c239db8801e922Evan Cheng (void)getOrCreateInterval(UndefReg); 621d129d73b725e32d2fc0c87f392c239db8801e922Evan Cheng } 622ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos} 623b27ef248f579b354aab434f63c417ab1103e47e2Alkis Evlogimenos 62403857b29d8271a23943254579e6cf7b7df4b1bd3Owen AndersonLiveInterval* LiveIntervals::createInterval(unsigned reg) { 6250a1fcce09230e9b4bd30a8f07447aa075dce7470Evan Cheng float Weight = TargetRegisterInfo::isPhysicalRegister(reg) ? HUGE_VALF : 0.0F; 62603857b29d8271a23943254579e6cf7b7df4b1bd3Owen Anderson return new LiveInterval(reg, Weight); 6279a8b490735d216435862a3d52e669357f165550fAlkis Evlogimenos} 628f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng 6290a1fcce09230e9b4bd30a8f07447aa075dce7470Evan Cheng/// dupInterval - Duplicate a live interval. The caller is responsible for 6300a1fcce09230e9b4bd30a8f07447aa075dce7470Evan Cheng/// managing the allocated memory. 6310a1fcce09230e9b4bd30a8f07447aa075dce7470Evan ChengLiveInterval* LiveIntervals::dupInterval(LiveInterval *li) { 6320a1fcce09230e9b4bd30a8f07447aa075dce7470Evan Cheng LiveInterval *NewLI = createInterval(li->reg); 63390f95f88c6ce09c6744777dc9d140c3c77203b92Evan Cheng NewLI->Copy(*li, mri_, getVNInfoAllocator()); 6340a1fcce09230e9b4bd30a8f07447aa075dce7470Evan Cheng return NewLI; 6350a1fcce09230e9b4bd30a8f07447aa075dce7470Evan Cheng} 6360a1fcce09230e9b4bd30a8f07447aa075dce7470Evan Cheng 63711513e5d1e1b40e6113668e4b4357596f33fa6c6Jakob Stoklund Olesen/// shrinkToUses - After removing some uses of a register, shrink its live 63811513e5d1e1b40e6113668e4b4357596f33fa6c6Jakob Stoklund Olesen/// range to just the remaining uses. This method does not compute reaching 63911513e5d1e1b40e6113668e4b4357596f33fa6c6Jakob Stoklund Olesen/// defs for new uses, and it doesn't remove dead defs. 6406a3dbd3b25bbc99bd1a233d6a74ddea3493ba6acJakob Stoklund Olesenbool LiveIntervals::shrinkToUses(LiveInterval *li, 6410d8ccaa5c8db820b5b93f37e51563148c57ba6b8Jakob Stoklund Olesen SmallVectorImpl<MachineInstr*> *dead) { 64211513e5d1e1b40e6113668e4b4357596f33fa6c6Jakob Stoklund Olesen DEBUG(dbgs() << "Shrink: " << *li << '\n'); 64311513e5d1e1b40e6113668e4b4357596f33fa6c6Jakob Stoklund Olesen assert(TargetRegisterInfo::isVirtualRegister(li->reg) 644567cdbab28077ea1801ebff3d4291d4006d88ca3Lang Hames && "Can only shrink virtual registers"); 64511513e5d1e1b40e6113668e4b4357596f33fa6c6Jakob Stoklund Olesen // Find all the values used, including PHI kills. 64611513e5d1e1b40e6113668e4b4357596f33fa6c6Jakob Stoklund Olesen SmallVector<std::pair<SlotIndex, VNInfo*>, 16> WorkList; 64711513e5d1e1b40e6113668e4b4357596f33fa6c6Jakob Stoklund Olesen 648031432f9ad24963282b7f71bd0592080f6229d20Jakob Stoklund Olesen // Blocks that have already been added to WorkList as live-out. 649031432f9ad24963282b7f71bd0592080f6229d20Jakob Stoklund Olesen SmallPtrSet<MachineBasicBlock*, 16> LiveOut; 650031432f9ad24963282b7f71bd0592080f6229d20Jakob Stoklund Olesen 65111513e5d1e1b40e6113668e4b4357596f33fa6c6Jakob Stoklund Olesen // Visit all instructions reading li->reg. 65211513e5d1e1b40e6113668e4b4357596f33fa6c6Jakob Stoklund Olesen for (MachineRegisterInfo::reg_iterator I = mri_->reg_begin(li->reg); 65311513e5d1e1b40e6113668e4b4357596f33fa6c6Jakob Stoklund Olesen MachineInstr *UseMI = I.skipInstruction();) { 65411513e5d1e1b40e6113668e4b4357596f33fa6c6Jakob Stoklund Olesen if (UseMI->isDebugValue() || !UseMI->readsVirtualRegister(li->reg)) 65511513e5d1e1b40e6113668e4b4357596f33fa6c6Jakob Stoklund Olesen continue; 6566c9cc21d85cdef79b971f710ace287f3a2f847a3Jakob Stoklund Olesen SlotIndex Idx = getInstructionIndex(UseMI).getRegSlot(); 657f054e198197122011fc80b673f35333bc3e58c98Jakob Stoklund Olesen // Note: This intentionally picks up the wrong VNI in case of an EC redef. 658f054e198197122011fc80b673f35333bc3e58c98Jakob Stoklund Olesen // See below. 659f054e198197122011fc80b673f35333bc3e58c98Jakob Stoklund Olesen VNInfo *VNI = li->getVNInfoBefore(Idx); 6609ef931e71c06a0390d6387859843be1d6d4daad6Jakob Stoklund Olesen if (!VNI) { 6619ef931e71c06a0390d6387859843be1d6d4daad6Jakob Stoklund Olesen // This shouldn't happen: readsVirtualRegister returns true, but there is 6629ef931e71c06a0390d6387859843be1d6d4daad6Jakob Stoklund Olesen // no live value. It is likely caused by a target getting <undef> flags 6639ef931e71c06a0390d6387859843be1d6d4daad6Jakob Stoklund Olesen // wrong. 6649ef931e71c06a0390d6387859843be1d6d4daad6Jakob Stoklund Olesen DEBUG(dbgs() << Idx << '\t' << *UseMI 6659ef931e71c06a0390d6387859843be1d6d4daad6Jakob Stoklund Olesen << "Warning: Instr claims to read non-existent value in " 6669ef931e71c06a0390d6387859843be1d6d4daad6Jakob Stoklund Olesen << *li << '\n'); 6679ef931e71c06a0390d6387859843be1d6d4daad6Jakob Stoklund Olesen continue; 6689ef931e71c06a0390d6387859843be1d6d4daad6Jakob Stoklund Olesen } 669f054e198197122011fc80b673f35333bc3e58c98Jakob Stoklund Olesen // Special case: An early-clobber tied operand reads and writes the 670f054e198197122011fc80b673f35333bc3e58c98Jakob Stoklund Olesen // register one slot early. The getVNInfoBefore call above would have 671f054e198197122011fc80b673f35333bc3e58c98Jakob Stoklund Olesen // picked up the value defined by UseMI. Adjust the kill slot and value. 672f054e198197122011fc80b673f35333bc3e58c98Jakob Stoklund Olesen if (SlotIndex::isSameInstr(VNI->def, Idx)) { 673f054e198197122011fc80b673f35333bc3e58c98Jakob Stoklund Olesen Idx = VNI->def; 6746c9cc21d85cdef79b971f710ace287f3a2f847a3Jakob Stoklund Olesen VNI = li->getVNInfoBefore(Idx); 67511513e5d1e1b40e6113668e4b4357596f33fa6c6Jakob Stoklund Olesen assert(VNI && "Early-clobber tied value not available"); 67611513e5d1e1b40e6113668e4b4357596f33fa6c6Jakob Stoklund Olesen } 67711513e5d1e1b40e6113668e4b4357596f33fa6c6Jakob Stoklund Olesen WorkList.push_back(std::make_pair(Idx, VNI)); 67811513e5d1e1b40e6113668e4b4357596f33fa6c6Jakob Stoklund Olesen } 67911513e5d1e1b40e6113668e4b4357596f33fa6c6Jakob Stoklund Olesen 68011513e5d1e1b40e6113668e4b4357596f33fa6c6Jakob Stoklund Olesen // Create a new live interval with only minimal live segments per def. 68111513e5d1e1b40e6113668e4b4357596f33fa6c6Jakob Stoklund Olesen LiveInterval NewLI(li->reg, 0); 68211513e5d1e1b40e6113668e4b4357596f33fa6c6Jakob Stoklund Olesen for (LiveInterval::vni_iterator I = li->vni_begin(), E = li->vni_end(); 68311513e5d1e1b40e6113668e4b4357596f33fa6c6Jakob Stoklund Olesen I != E; ++I) { 68411513e5d1e1b40e6113668e4b4357596f33fa6c6Jakob Stoklund Olesen VNInfo *VNI = *I; 68511513e5d1e1b40e6113668e4b4357596f33fa6c6Jakob Stoklund Olesen if (VNI->isUnused()) 68611513e5d1e1b40e6113668e4b4357596f33fa6c6Jakob Stoklund Olesen continue; 6871f81e316b042c02c841801a71e7439e166ffa2a0Jakob Stoklund Olesen NewLI.addRange(LiveRange(VNI->def, VNI->def.getDeadSlot(), VNI)); 68811513e5d1e1b40e6113668e4b4357596f33fa6c6Jakob Stoklund Olesen } 68911513e5d1e1b40e6113668e4b4357596f33fa6c6Jakob Stoklund Olesen 690e0ab24532cc11f082d722ab169080322b39afeceJakob Stoklund Olesen // Keep track of the PHIs that are in use. 691e0ab24532cc11f082d722ab169080322b39afeceJakob Stoklund Olesen SmallPtrSet<VNInfo*, 8> UsedPHIs; 692e0ab24532cc11f082d722ab169080322b39afeceJakob Stoklund Olesen 69311513e5d1e1b40e6113668e4b4357596f33fa6c6Jakob Stoklund Olesen // Extend intervals to reach all uses in WorkList. 69411513e5d1e1b40e6113668e4b4357596f33fa6c6Jakob Stoklund Olesen while (!WorkList.empty()) { 69511513e5d1e1b40e6113668e4b4357596f33fa6c6Jakob Stoklund Olesen SlotIndex Idx = WorkList.back().first; 69611513e5d1e1b40e6113668e4b4357596f33fa6c6Jakob Stoklund Olesen VNInfo *VNI = WorkList.back().second; 69711513e5d1e1b40e6113668e4b4357596f33fa6c6Jakob Stoklund Olesen WorkList.pop_back(); 6986c9cc21d85cdef79b971f710ace287f3a2f847a3Jakob Stoklund Olesen const MachineBasicBlock *MBB = getMBBFromIndex(Idx.getPrevSlot()); 69911513e5d1e1b40e6113668e4b4357596f33fa6c6Jakob Stoklund Olesen SlotIndex BlockStart = getMBBStartIdx(MBB); 700e0ab24532cc11f082d722ab169080322b39afeceJakob Stoklund Olesen 701e0ab24532cc11f082d722ab169080322b39afeceJakob Stoklund Olesen // Extend the live range for VNI to be live at Idx. 7026c9cc21d85cdef79b971f710ace287f3a2f847a3Jakob Stoklund Olesen if (VNInfo *ExtVNI = NewLI.extendInBlock(BlockStart, Idx)) { 7034b11a70f7a63dc4c051a96a90ed6687eb0595cdaNick Lewycky (void)ExtVNI; 704e0ab24532cc11f082d722ab169080322b39afeceJakob Stoklund Olesen assert(ExtVNI == VNI && "Unexpected existing value number"); 705e0ab24532cc11f082d722ab169080322b39afeceJakob Stoklund Olesen // Is this a PHIDef we haven't seen before? 706c29d9b3495a2d87af524ad5c4b62f46c4265d828Jakob Stoklund Olesen if (!VNI->isPHIDef() || VNI->def != BlockStart || !UsedPHIs.insert(VNI)) 707e0ab24532cc11f082d722ab169080322b39afeceJakob Stoklund Olesen continue; 708e0ab24532cc11f082d722ab169080322b39afeceJakob Stoklund Olesen // The PHI is live, make sure the predecessors are live-out. 709e0ab24532cc11f082d722ab169080322b39afeceJakob Stoklund Olesen for (MachineBasicBlock::const_pred_iterator PI = MBB->pred_begin(), 710e0ab24532cc11f082d722ab169080322b39afeceJakob Stoklund Olesen PE = MBB->pred_end(); PI != PE; ++PI) { 711031432f9ad24963282b7f71bd0592080f6229d20Jakob Stoklund Olesen if (!LiveOut.insert(*PI)) 712031432f9ad24963282b7f71bd0592080f6229d20Jakob Stoklund Olesen continue; 7136c9cc21d85cdef79b971f710ace287f3a2f847a3Jakob Stoklund Olesen SlotIndex Stop = getMBBEndIdx(*PI); 714e0ab24532cc11f082d722ab169080322b39afeceJakob Stoklund Olesen // A predecessor is not required to have a live-out value for a PHI. 7156c9cc21d85cdef79b971f710ace287f3a2f847a3Jakob Stoklund Olesen if (VNInfo *PVNI = li->getVNInfoBefore(Stop)) 716e0ab24532cc11f082d722ab169080322b39afeceJakob Stoklund Olesen WorkList.push_back(std::make_pair(Stop, PVNI)); 71711513e5d1e1b40e6113668e4b4357596f33fa6c6Jakob Stoklund Olesen } 71811513e5d1e1b40e6113668e4b4357596f33fa6c6Jakob Stoklund Olesen continue; 71911513e5d1e1b40e6113668e4b4357596f33fa6c6Jakob Stoklund Olesen } 72011513e5d1e1b40e6113668e4b4357596f33fa6c6Jakob Stoklund Olesen 72111513e5d1e1b40e6113668e4b4357596f33fa6c6Jakob Stoklund Olesen // VNI is live-in to MBB. 72211513e5d1e1b40e6113668e4b4357596f33fa6c6Jakob Stoklund Olesen DEBUG(dbgs() << " live-in at " << BlockStart << '\n'); 7236c9cc21d85cdef79b971f710ace287f3a2f847a3Jakob Stoklund Olesen NewLI.addRange(LiveRange(BlockStart, Idx, VNI)); 72411513e5d1e1b40e6113668e4b4357596f33fa6c6Jakob Stoklund Olesen 72511513e5d1e1b40e6113668e4b4357596f33fa6c6Jakob Stoklund Olesen // Make sure VNI is live-out from the predecessors. 72611513e5d1e1b40e6113668e4b4357596f33fa6c6Jakob Stoklund Olesen for (MachineBasicBlock::const_pred_iterator PI = MBB->pred_begin(), 72711513e5d1e1b40e6113668e4b4357596f33fa6c6Jakob Stoklund Olesen PE = MBB->pred_end(); PI != PE; ++PI) { 728031432f9ad24963282b7f71bd0592080f6229d20Jakob Stoklund Olesen if (!LiveOut.insert(*PI)) 729031432f9ad24963282b7f71bd0592080f6229d20Jakob Stoklund Olesen continue; 7306c9cc21d85cdef79b971f710ace287f3a2f847a3Jakob Stoklund Olesen SlotIndex Stop = getMBBEndIdx(*PI); 7316c9cc21d85cdef79b971f710ace287f3a2f847a3Jakob Stoklund Olesen assert(li->getVNInfoBefore(Stop) == VNI && 7326c9cc21d85cdef79b971f710ace287f3a2f847a3Jakob Stoklund Olesen "Wrong value out of predecessor"); 73311513e5d1e1b40e6113668e4b4357596f33fa6c6Jakob Stoklund Olesen WorkList.push_back(std::make_pair(Stop, VNI)); 73411513e5d1e1b40e6113668e4b4357596f33fa6c6Jakob Stoklund Olesen } 73511513e5d1e1b40e6113668e4b4357596f33fa6c6Jakob Stoklund Olesen } 73611513e5d1e1b40e6113668e4b4357596f33fa6c6Jakob Stoklund Olesen 73711513e5d1e1b40e6113668e4b4357596f33fa6c6Jakob Stoklund Olesen // Handle dead values. 7386a3dbd3b25bbc99bd1a233d6a74ddea3493ba6acJakob Stoklund Olesen bool CanSeparate = false; 73911513e5d1e1b40e6113668e4b4357596f33fa6c6Jakob Stoklund Olesen for (LiveInterval::vni_iterator I = li->vni_begin(), E = li->vni_end(); 74011513e5d1e1b40e6113668e4b4357596f33fa6c6Jakob Stoklund Olesen I != E; ++I) { 74111513e5d1e1b40e6113668e4b4357596f33fa6c6Jakob Stoklund Olesen VNInfo *VNI = *I; 74211513e5d1e1b40e6113668e4b4357596f33fa6c6Jakob Stoklund Olesen if (VNI->isUnused()) 74311513e5d1e1b40e6113668e4b4357596f33fa6c6Jakob Stoklund Olesen continue; 74411513e5d1e1b40e6113668e4b4357596f33fa6c6Jakob Stoklund Olesen LiveInterval::iterator LII = NewLI.FindLiveRangeContaining(VNI->def); 74511513e5d1e1b40e6113668e4b4357596f33fa6c6Jakob Stoklund Olesen assert(LII != NewLI.end() && "Missing live range for PHI"); 7461f81e316b042c02c841801a71e7439e166ffa2a0Jakob Stoklund Olesen if (LII->end != VNI->def.getDeadSlot()) 74711513e5d1e1b40e6113668e4b4357596f33fa6c6Jakob Stoklund Olesen continue; 748a4d347357ce04d9101130dca0df33cb62ea35a2fJakob Stoklund Olesen if (VNI->isPHIDef()) { 74911513e5d1e1b40e6113668e4b4357596f33fa6c6Jakob Stoklund Olesen // This is a dead PHI. Remove it. 75011513e5d1e1b40e6113668e4b4357596f33fa6c6Jakob Stoklund Olesen VNI->setIsUnused(true); 75111513e5d1e1b40e6113668e4b4357596f33fa6c6Jakob Stoklund Olesen NewLI.removeRange(*LII); 7526a3dbd3b25bbc99bd1a233d6a74ddea3493ba6acJakob Stoklund Olesen DEBUG(dbgs() << "Dead PHI at " << VNI->def << " may separate interval\n"); 7536a3dbd3b25bbc99bd1a233d6a74ddea3493ba6acJakob Stoklund Olesen CanSeparate = true; 75411513e5d1e1b40e6113668e4b4357596f33fa6c6Jakob Stoklund Olesen } else { 75511513e5d1e1b40e6113668e4b4357596f33fa6c6Jakob Stoklund Olesen // This is a dead def. Make sure the instruction knows. 75611513e5d1e1b40e6113668e4b4357596f33fa6c6Jakob Stoklund Olesen MachineInstr *MI = getInstructionFromIndex(VNI->def); 75711513e5d1e1b40e6113668e4b4357596f33fa6c6Jakob Stoklund Olesen assert(MI && "No instruction defining live value"); 75811513e5d1e1b40e6113668e4b4357596f33fa6c6Jakob Stoklund Olesen MI->addRegisterDead(li->reg, tri_); 7590d8ccaa5c8db820b5b93f37e51563148c57ba6b8Jakob Stoklund Olesen if (dead && MI->allDefsAreDead()) { 760c46570dc05851395829bef904bb6ddb1260400d1Jakob Stoklund Olesen DEBUG(dbgs() << "All defs dead: " << VNI->def << '\t' << *MI); 7610d8ccaa5c8db820b5b93f37e51563148c57ba6b8Jakob Stoklund Olesen dead->push_back(MI); 7620d8ccaa5c8db820b5b93f37e51563148c57ba6b8Jakob Stoklund Olesen } 76311513e5d1e1b40e6113668e4b4357596f33fa6c6Jakob Stoklund Olesen } 76411513e5d1e1b40e6113668e4b4357596f33fa6c6Jakob Stoklund Olesen } 76511513e5d1e1b40e6113668e4b4357596f33fa6c6Jakob Stoklund Olesen 76611513e5d1e1b40e6113668e4b4357596f33fa6c6Jakob Stoklund Olesen // Move the trimmed ranges back. 76711513e5d1e1b40e6113668e4b4357596f33fa6c6Jakob Stoklund Olesen li->ranges.swap(NewLI.ranges); 768c46570dc05851395829bef904bb6ddb1260400d1Jakob Stoklund Olesen DEBUG(dbgs() << "Shrunk: " << *li << '\n'); 7696a3dbd3b25bbc99bd1a233d6a74ddea3493ba6acJakob Stoklund Olesen return CanSeparate; 77011513e5d1e1b40e6113668e4b4357596f33fa6c6Jakob Stoklund Olesen} 77111513e5d1e1b40e6113668e4b4357596f33fa6c6Jakob Stoklund Olesen 77211513e5d1e1b40e6113668e4b4357596f33fa6c6Jakob Stoklund Olesen 773f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng//===----------------------------------------------------------------------===// 774f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng// Register allocator hooks. 775f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng// 776f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng 7778a61da8a689ee95874c833af4c7aa965fab5c0a9Jakob Stoklund Olesenvoid LiveIntervals::addKillFlags() { 7788a61da8a689ee95874c833af4c7aa965fab5c0a9Jakob Stoklund Olesen for (iterator I = begin(), E = end(); I != E; ++I) { 7798a61da8a689ee95874c833af4c7aa965fab5c0a9Jakob Stoklund Olesen unsigned Reg = I->first; 7808a61da8a689ee95874c833af4c7aa965fab5c0a9Jakob Stoklund Olesen if (TargetRegisterInfo::isPhysicalRegister(Reg)) 7818a61da8a689ee95874c833af4c7aa965fab5c0a9Jakob Stoklund Olesen continue; 7828a61da8a689ee95874c833af4c7aa965fab5c0a9Jakob Stoklund Olesen if (mri_->reg_nodbg_empty(Reg)) 7838a61da8a689ee95874c833af4c7aa965fab5c0a9Jakob Stoklund Olesen continue; 7848a61da8a689ee95874c833af4c7aa965fab5c0a9Jakob Stoklund Olesen LiveInterval *LI = I->second; 7858a61da8a689ee95874c833af4c7aa965fab5c0a9Jakob Stoklund Olesen 7868a61da8a689ee95874c833af4c7aa965fab5c0a9Jakob Stoklund Olesen // Every instruction that kills Reg corresponds to a live range end point. 7878a61da8a689ee95874c833af4c7aa965fab5c0a9Jakob Stoklund Olesen for (LiveInterval::iterator RI = LI->begin(), RE = LI->end(); RI != RE; 7888a61da8a689ee95874c833af4c7aa965fab5c0a9Jakob Stoklund Olesen ++RI) { 7892debd48ca790ac01be6e12e094fdf4fdcadc8364Jakob Stoklund Olesen // A block index indicates an MBB edge. 7902debd48ca790ac01be6e12e094fdf4fdcadc8364Jakob Stoklund Olesen if (RI->end.isBlock()) 7918a61da8a689ee95874c833af4c7aa965fab5c0a9Jakob Stoklund Olesen continue; 7928a61da8a689ee95874c833af4c7aa965fab5c0a9Jakob Stoklund Olesen MachineInstr *MI = getInstructionFromIndex(RI->end); 7938a61da8a689ee95874c833af4c7aa965fab5c0a9Jakob Stoklund Olesen if (!MI) 7948a61da8a689ee95874c833af4c7aa965fab5c0a9Jakob Stoklund Olesen continue; 7958a61da8a689ee95874c833af4c7aa965fab5c0a9Jakob Stoklund Olesen MI->addRegisterKilled(Reg, NULL); 7968a61da8a689ee95874c833af4c7aa965fab5c0a9Jakob Stoklund Olesen } 7978a61da8a689ee95874c833af4c7aa965fab5c0a9Jakob Stoklund Olesen } 7988a61da8a689ee95874c833af4c7aa965fab5c0a9Jakob Stoklund Olesen} 7998a61da8a689ee95874c833af4c7aa965fab5c0a9Jakob Stoklund Olesen 800d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng/// getReMatImplicitUse - If the remat definition MI has one (for now, we only 801d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng/// allow one) virtual register operand, then its uses are implicitly using 802d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng/// the register. Returns the virtual register. 803d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Chengunsigned LiveIntervals::getReMatImplicitUse(const LiveInterval &li, 804d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng MachineInstr *MI) const { 805d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng unsigned RegOp = 0; 806d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) { 807d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng MachineOperand &MO = MI->getOperand(i); 808d735b8019b0f297d7c14b55adcd887af24d8e602Dan Gohman if (!MO.isReg() || !MO.isUse()) 809d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng continue; 810d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng unsigned Reg = MO.getReg(); 811d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng if (Reg == 0 || Reg == li.reg) 812d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng continue; 8131b2932024f098a6968645ac78d5848951d877c19Jakob Stoklund Olesen 814cd339b71ff23327f2ef6a4c964ff3ceea20733bfLang Hames if (TargetRegisterInfo::isPhysicalRegister(Reg) && !isAllocatable(Reg)) 8151873d0c2257b18451c5bb35577f929d0723433a0Chris Lattner continue; 816d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng RegOp = MO.getReg(); 8176c76e80753cfc83dc6804fcd5d949c517dfe3434Lang Hames break; // Found vreg operand - leave the loop. 818d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng } 819d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng return RegOp; 820d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng} 821d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng 822d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng/// isValNoAvailableAt - Return true if the val# of the specified interval 823d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng/// which reaches the given instruction also reaches the specified use index. 824d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Chengbool LiveIntervals::isValNoAvailableAt(const LiveInterval &li, MachineInstr *MI, 825233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames SlotIndex UseIdx) const { 82631cc3ec3308c8fafd9865388214ae11662a71af4Jakob Stoklund Olesen VNInfo *UValNo = li.getVNInfoAt(UseIdx); 82731cc3ec3308c8fafd9865388214ae11662a71af4Jakob Stoklund Olesen return UValNo && UValNo == li.getVNInfoAt(getInstructionIndex(MI)); 828d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng} 829d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng 830f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng/// isReMaterializable - Returns true if the definition MI of the specified 831f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng/// val# of the specified interval is re-materializable. 832f4baeaf8485f01beda46d29fd55753199dc68070Andrew Trickbool 833f4baeaf8485f01beda46d29fd55753199dc68070Andrew TrickLiveIntervals::isReMaterializable(const LiveInterval &li, 834f4baeaf8485f01beda46d29fd55753199dc68070Andrew Trick const VNInfo *ValNo, MachineInstr *MI, 83538f6bd0fc8095ef79a89b3db15ff6dc734ac90e7Jakob Stoklund Olesen const SmallVectorImpl<LiveInterval*> *SpillIs, 836f4baeaf8485f01beda46d29fd55753199dc68070Andrew Trick bool &isLoad) { 837f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng if (DisableReMat) 838f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng return false; 839f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng 840a70dca156fa76d452f54829b5c5f962ddfd94ef2Dan Gohman if (!tii_->isTriviallyReMaterializable(MI, aa_)) 841a70dca156fa76d452f54829b5c5f962ddfd94ef2Dan Gohman return false; 842f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng 843a70dca156fa76d452f54829b5c5f962ddfd94ef2Dan Gohman // Target-specific code can mark an instruction as being rematerializable 844a70dca156fa76d452f54829b5c5f962ddfd94ef2Dan Gohman // if it has one virtual reg use, though it had better be something like 845a70dca156fa76d452f54829b5c5f962ddfd94ef2Dan Gohman // a PIC base register which is likely to be live everywhere. 8466d69ba8a6901c69d78488cbc41f8dbf080618fdeDan Gohman unsigned ImpUse = getReMatImplicitUse(li, MI); 8476d69ba8a6901c69d78488cbc41f8dbf080618fdeDan Gohman if (ImpUse) { 8486d69ba8a6901c69d78488cbc41f8dbf080618fdeDan Gohman const LiveInterval &ImpLi = getInterval(ImpUse); 84928a1e486907104b85c5787345914917d74f0cf77Evan Cheng for (MachineRegisterInfo::use_nodbg_iterator 85028a1e486907104b85c5787345914917d74f0cf77Evan Cheng ri = mri_->use_nodbg_begin(li.reg), re = mri_->use_nodbg_end(); 85128a1e486907104b85c5787345914917d74f0cf77Evan Cheng ri != re; ++ri) { 8526d69ba8a6901c69d78488cbc41f8dbf080618fdeDan Gohman MachineInstr *UseMI = &*ri; 853233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames SlotIndex UseIdx = getInstructionIndex(UseMI); 85431cc3ec3308c8fafd9865388214ae11662a71af4Jakob Stoklund Olesen if (li.getVNInfoAt(UseIdx) != ValNo) 8556d69ba8a6901c69d78488cbc41f8dbf080618fdeDan Gohman continue; 8566d69ba8a6901c69d78488cbc41f8dbf080618fdeDan Gohman if (!isValNoAvailableAt(ImpLi, MI, UseIdx)) 8576d69ba8a6901c69d78488cbc41f8dbf080618fdeDan Gohman return false; 8586d69ba8a6901c69d78488cbc41f8dbf080618fdeDan Gohman } 859dc37786595beedd0a68d8e2cbd91ae53ad58d133Evan Cheng 860dc37786595beedd0a68d8e2cbd91ae53ad58d133Evan Cheng // If a register operand of the re-materialized instruction is going to 861dc37786595beedd0a68d8e2cbd91ae53ad58d133Evan Cheng // be spilled next, then it's not legal to re-materialize this instruction. 86238f6bd0fc8095ef79a89b3db15ff6dc734ac90e7Jakob Stoklund Olesen if (SpillIs) 86338f6bd0fc8095ef79a89b3db15ff6dc734ac90e7Jakob Stoklund Olesen for (unsigned i = 0, e = SpillIs->size(); i != e; ++i) 86438f6bd0fc8095ef79a89b3db15ff6dc734ac90e7Jakob Stoklund Olesen if (ImpUse == (*SpillIs)[i]->reg) 86538f6bd0fc8095ef79a89b3db15ff6dc734ac90e7Jakob Stoklund Olesen return false; 8666d69ba8a6901c69d78488cbc41f8dbf080618fdeDan Gohman } 8676d69ba8a6901c69d78488cbc41f8dbf080618fdeDan Gohman return true; 8685ef3a04b542c4e585276768fa9ca2af698ef5c87Evan Cheng} 8695ef3a04b542c4e585276768fa9ca2af698ef5c87Evan Cheng 8705ef3a04b542c4e585276768fa9ca2af698ef5c87Evan Cheng/// isReMaterializable - Returns true if every definition of MI of every 8715ef3a04b542c4e585276768fa9ca2af698ef5c87Evan Cheng/// val# of the specified interval is re-materializable. 872f4baeaf8485f01beda46d29fd55753199dc68070Andrew Trickbool 873f4baeaf8485f01beda46d29fd55753199dc68070Andrew TrickLiveIntervals::isReMaterializable(const LiveInterval &li, 87438f6bd0fc8095ef79a89b3db15ff6dc734ac90e7Jakob Stoklund Olesen const SmallVectorImpl<LiveInterval*> *SpillIs, 875f4baeaf8485f01beda46d29fd55753199dc68070Andrew Trick bool &isLoad) { 8765ef3a04b542c4e585276768fa9ca2af698ef5c87Evan Cheng isLoad = false; 8775ef3a04b542c4e585276768fa9ca2af698ef5c87Evan Cheng for (LiveInterval::const_vni_iterator i = li.vni_begin(), e = li.vni_end(); 8785ef3a04b542c4e585276768fa9ca2af698ef5c87Evan Cheng i != e; ++i) { 8795ef3a04b542c4e585276768fa9ca2af698ef5c87Evan Cheng const VNInfo *VNI = *i; 880857c4e01f85601cf2084adb860616256ee47c177Lang Hames if (VNI->isUnused()) 8815ef3a04b542c4e585276768fa9ca2af698ef5c87Evan Cheng continue; // Dead val#. 8825ef3a04b542c4e585276768fa9ca2af698ef5c87Evan Cheng // Is the def for the val# rematerializable? 883857c4e01f85601cf2084adb860616256ee47c177Lang Hames MachineInstr *ReMatDefMI = getInstructionFromIndex(VNI->def); 8846e2968c85c1e162ee5bc813769eab223e3df0f15Lang Hames if (!ReMatDefMI) 8856e2968c85c1e162ee5bc813769eab223e3df0f15Lang Hames return false; 8865ef3a04b542c4e585276768fa9ca2af698ef5c87Evan Cheng bool DefIsLoad = false; 887d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng if (!ReMatDefMI || 888dc37786595beedd0a68d8e2cbd91ae53ad58d133Evan Cheng !isReMaterializable(li, VNI, ReMatDefMI, SpillIs, DefIsLoad)) 889f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng return false; 8905ef3a04b542c4e585276768fa9ca2af698ef5c87Evan Cheng isLoad |= DefIsLoad; 891f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng } 892f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng return true; 893f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng} 894f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng 895ebf2750a70df4261d3e66144ea6bcb49d41f6efbJakob Stoklund OlesenMachineBasicBlock* 896ebf2750a70df4261d3e66144ea6bcb49d41f6efbJakob Stoklund OlesenLiveIntervals::intervalIsInOneMBB(const LiveInterval &LI) const { 897ebf2750a70df4261d3e66144ea6bcb49d41f6efbJakob Stoklund Olesen // A local live range must be fully contained inside the block, meaning it is 898ebf2750a70df4261d3e66144ea6bcb49d41f6efbJakob Stoklund Olesen // defined and killed at instructions, not at block boundaries. It is not 899ebf2750a70df4261d3e66144ea6bcb49d41f6efbJakob Stoklund Olesen // live in or or out of any block. 900ebf2750a70df4261d3e66144ea6bcb49d41f6efbJakob Stoklund Olesen // 901ebf2750a70df4261d3e66144ea6bcb49d41f6efbJakob Stoklund Olesen // It is technically possible to have a PHI-defined live range identical to a 902ebf2750a70df4261d3e66144ea6bcb49d41f6efbJakob Stoklund Olesen // single block, but we are going to return false in that case. 903ebf2750a70df4261d3e66144ea6bcb49d41f6efbJakob Stoklund Olesen 904ebf2750a70df4261d3e66144ea6bcb49d41f6efbJakob Stoklund Olesen SlotIndex Start = LI.beginIndex(); 905ebf2750a70df4261d3e66144ea6bcb49d41f6efbJakob Stoklund Olesen if (Start.isBlock()) 906ebf2750a70df4261d3e66144ea6bcb49d41f6efbJakob Stoklund Olesen return NULL; 907ebf2750a70df4261d3e66144ea6bcb49d41f6efbJakob Stoklund Olesen 908ebf2750a70df4261d3e66144ea6bcb49d41f6efbJakob Stoklund Olesen SlotIndex Stop = LI.endIndex(); 909ebf2750a70df4261d3e66144ea6bcb49d41f6efbJakob Stoklund Olesen if (Stop.isBlock()) 910ebf2750a70df4261d3e66144ea6bcb49d41f6efbJakob Stoklund Olesen return NULL; 911ebf2750a70df4261d3e66144ea6bcb49d41f6efbJakob Stoklund Olesen 912ebf2750a70df4261d3e66144ea6bcb49d41f6efbJakob Stoklund Olesen // getMBBFromIndex doesn't need to search the MBB table when both indexes 913ebf2750a70df4261d3e66144ea6bcb49d41f6efbJakob Stoklund Olesen // belong to proper instructions. 914ebf2750a70df4261d3e66144ea6bcb49d41f6efbJakob Stoklund Olesen MachineBasicBlock *MBB1 = indexes_->getMBBFromIndex(Start); 915ebf2750a70df4261d3e66144ea6bcb49d41f6efbJakob Stoklund Olesen MachineBasicBlock *MBB2 = indexes_->getMBBFromIndex(Stop); 916ebf2750a70df4261d3e66144ea6bcb49d41f6efbJakob Stoklund Olesen return MBB1 == MBB2 ? MBB1 : NULL; 91781a038218171860ee4c382849c647d3dc841fe8bEvan Cheng} 91881a038218171860ee4c382849c647d3dc841fe8bEvan Cheng 919e5d90416ee1a4f45eba80789a7a3cbc3d497a4cdJakob Stoklund Olesenfloat 920e5d90416ee1a4f45eba80789a7a3cbc3d497a4cdJakob Stoklund OlesenLiveIntervals::getSpillWeight(bool isDef, bool isUse, unsigned loopDepth) { 921e5d90416ee1a4f45eba80789a7a3cbc3d497a4cdJakob Stoklund Olesen // Limit the loop depth ridiculousness. 922e5d90416ee1a4f45eba80789a7a3cbc3d497a4cdJakob Stoklund Olesen if (loopDepth > 200) 923e5d90416ee1a4f45eba80789a7a3cbc3d497a4cdJakob Stoklund Olesen loopDepth = 200; 924e5d90416ee1a4f45eba80789a7a3cbc3d497a4cdJakob Stoklund Olesen 925e5d90416ee1a4f45eba80789a7a3cbc3d497a4cdJakob Stoklund Olesen // The loop depth is used to roughly estimate the number of times the 926e5d90416ee1a4f45eba80789a7a3cbc3d497a4cdJakob Stoklund Olesen // instruction is executed. Something like 10^d is simple, but will quickly 927e5d90416ee1a4f45eba80789a7a3cbc3d497a4cdJakob Stoklund Olesen // overflow a float. This expression behaves like 10^d for small d, but is 928e5d90416ee1a4f45eba80789a7a3cbc3d497a4cdJakob Stoklund Olesen // more tempered for large d. At d=200 we get 6.7e33 which leaves a bit of 929e5d90416ee1a4f45eba80789a7a3cbc3d497a4cdJakob Stoklund Olesen // headroom before overflow. 930dc5198bac7e3f9b61617c8c46a1c28a84daa9325NAKAMURA Takumi // By the way, powf() might be unavailable here. For consistency, 931dc5198bac7e3f9b61617c8c46a1c28a84daa9325NAKAMURA Takumi // We may take pow(double,double). 932dc5198bac7e3f9b61617c8c46a1c28a84daa9325NAKAMURA Takumi float lc = std::pow(1 + (100.0 / (loopDepth + 10)), (double)loopDepth); 933e5d90416ee1a4f45eba80789a7a3cbc3d497a4cdJakob Stoklund Olesen 934e5d90416ee1a4f45eba80789a7a3cbc3d497a4cdJakob Stoklund Olesen return (isDef + isUse) * lc; 935e5d90416ee1a4f45eba80789a7a3cbc3d497a4cdJakob Stoklund Olesen} 936e5d90416ee1a4f45eba80789a7a3cbc3d497a4cdJakob Stoklund Olesen 937c4dc132c8a787fc41b6a162121251234aa618965Owen AndersonLiveRange LiveIntervals::addLiveRangeToEndOfBlock(unsigned reg, 938ffd1326ff8dfc652a8026c3faebf55bbba7c32c7Lang Hames MachineInstr* startInst) { 939c4dc132c8a787fc41b6a162121251234aa618965Owen Anderson LiveInterval& Interval = getOrCreateInterval(reg); 940c4dc132c8a787fc41b6a162121251234aa618965Owen Anderson VNInfo* VN = Interval.getNextValue( 9412debd48ca790ac01be6e12e094fdf4fdcadc8364Jakob Stoklund Olesen SlotIndex(getInstructionIndex(startInst).getRegSlot()), 9423b1088a2cc15a39c7a7b8dd95a56143f1dda6863Jakob Stoklund Olesen getVNInfoAllocator()); 943857c4e01f85601cf2084adb860616256ee47c177Lang Hames VN->setHasPHIKill(true); 9448651125d2885f74546b6e2a556082111d5b75da3Lang Hames LiveRange LR( 9452debd48ca790ac01be6e12e094fdf4fdcadc8364Jakob Stoklund Olesen SlotIndex(getInstructionIndex(startInst).getRegSlot()), 94674ab5eeffbd70f2387338e3ee8195be9f73e6dd8Lang Hames getMBBEndIdx(startInst->getParent()), VN); 947c4dc132c8a787fc41b6a162121251234aa618965Owen Anderson Interval.addRange(LR); 9481b2932024f098a6968645ac78d5848951d877c19Jakob Stoklund Olesen 949c4dc132c8a787fc41b6a162121251234aa618965Owen Anderson return LR; 950c4dc132c8a787fc41b6a162121251234aa618965Owen Anderson} 9513fd3a840c50fe4ede1b200be18990bc955c536fdJakob Stoklund Olesen 9523fd3a840c50fe4ede1b200be18990bc955c536fdJakob Stoklund Olesen 9533fd3a840c50fe4ede1b200be18990bc955c536fdJakob Stoklund Olesen//===----------------------------------------------------------------------===// 9543fd3a840c50fe4ede1b200be18990bc955c536fdJakob Stoklund Olesen// Register mask functions 9553fd3a840c50fe4ede1b200be18990bc955c536fdJakob Stoklund Olesen//===----------------------------------------------------------------------===// 9563fd3a840c50fe4ede1b200be18990bc955c536fdJakob Stoklund Olesen 9573fd3a840c50fe4ede1b200be18990bc955c536fdJakob Stoklund Olesenbool LiveIntervals::checkRegMaskInterference(LiveInterval &LI, 9583fd3a840c50fe4ede1b200be18990bc955c536fdJakob Stoklund Olesen BitVector &UsableRegs) { 9593fd3a840c50fe4ede1b200be18990bc955c536fdJakob Stoklund Olesen if (LI.empty()) 9603fd3a840c50fe4ede1b200be18990bc955c536fdJakob Stoklund Olesen return false; 9619f10ac63a3a2a74ac381a05d8ba0f7b1b455a6b6Jakob Stoklund Olesen LiveInterval::iterator LiveI = LI.begin(), LiveE = LI.end(); 9629f10ac63a3a2a74ac381a05d8ba0f7b1b455a6b6Jakob Stoklund Olesen 9639f10ac63a3a2a74ac381a05d8ba0f7b1b455a6b6Jakob Stoklund Olesen // Use a smaller arrays for local live ranges. 9649f10ac63a3a2a74ac381a05d8ba0f7b1b455a6b6Jakob Stoklund Olesen ArrayRef<SlotIndex> Slots; 9659f10ac63a3a2a74ac381a05d8ba0f7b1b455a6b6Jakob Stoklund Olesen ArrayRef<const uint32_t*> Bits; 9669f10ac63a3a2a74ac381a05d8ba0f7b1b455a6b6Jakob Stoklund Olesen if (MachineBasicBlock *MBB = intervalIsInOneMBB(LI)) { 9679f10ac63a3a2a74ac381a05d8ba0f7b1b455a6b6Jakob Stoklund Olesen Slots = getRegMaskSlotsInBlock(MBB->getNumber()); 9689f10ac63a3a2a74ac381a05d8ba0f7b1b455a6b6Jakob Stoklund Olesen Bits = getRegMaskBitsInBlock(MBB->getNumber()); 9699f10ac63a3a2a74ac381a05d8ba0f7b1b455a6b6Jakob Stoklund Olesen } else { 9709f10ac63a3a2a74ac381a05d8ba0f7b1b455a6b6Jakob Stoklund Olesen Slots = getRegMaskSlots(); 9719f10ac63a3a2a74ac381a05d8ba0f7b1b455a6b6Jakob Stoklund Olesen Bits = getRegMaskBits(); 9729f10ac63a3a2a74ac381a05d8ba0f7b1b455a6b6Jakob Stoklund Olesen } 9733fd3a840c50fe4ede1b200be18990bc955c536fdJakob Stoklund Olesen 9743fd3a840c50fe4ede1b200be18990bc955c536fdJakob Stoklund Olesen // We are going to enumerate all the register mask slots contained in LI. 9753fd3a840c50fe4ede1b200be18990bc955c536fdJakob Stoklund Olesen // Start with a binary search of RegMaskSlots to find a starting point. 9763fd3a840c50fe4ede1b200be18990bc955c536fdJakob Stoklund Olesen ArrayRef<SlotIndex>::iterator SlotI = 9773fd3a840c50fe4ede1b200be18990bc955c536fdJakob Stoklund Olesen std::lower_bound(Slots.begin(), Slots.end(), LiveI->start); 9783fd3a840c50fe4ede1b200be18990bc955c536fdJakob Stoklund Olesen ArrayRef<SlotIndex>::iterator SlotE = Slots.end(); 9793fd3a840c50fe4ede1b200be18990bc955c536fdJakob Stoklund Olesen 9803fd3a840c50fe4ede1b200be18990bc955c536fdJakob Stoklund Olesen // No slots in range, LI begins after the last call. 9813fd3a840c50fe4ede1b200be18990bc955c536fdJakob Stoklund Olesen if (SlotI == SlotE) 9823fd3a840c50fe4ede1b200be18990bc955c536fdJakob Stoklund Olesen return false; 9833fd3a840c50fe4ede1b200be18990bc955c536fdJakob Stoklund Olesen 9843fd3a840c50fe4ede1b200be18990bc955c536fdJakob Stoklund Olesen bool Found = false; 9853fd3a840c50fe4ede1b200be18990bc955c536fdJakob Stoklund Olesen for (;;) { 9863fd3a840c50fe4ede1b200be18990bc955c536fdJakob Stoklund Olesen assert(*SlotI >= LiveI->start); 9873fd3a840c50fe4ede1b200be18990bc955c536fdJakob Stoklund Olesen // Loop over all slots overlapping this segment. 9883fd3a840c50fe4ede1b200be18990bc955c536fdJakob Stoklund Olesen while (*SlotI < LiveI->end) { 9893fd3a840c50fe4ede1b200be18990bc955c536fdJakob Stoklund Olesen // *SlotI overlaps LI. Collect mask bits. 9903fd3a840c50fe4ede1b200be18990bc955c536fdJakob Stoklund Olesen if (!Found) { 9913fd3a840c50fe4ede1b200be18990bc955c536fdJakob Stoklund Olesen // This is the first overlap. Initialize UsableRegs to all ones. 9923fd3a840c50fe4ede1b200be18990bc955c536fdJakob Stoklund Olesen UsableRegs.clear(); 9933fd3a840c50fe4ede1b200be18990bc955c536fdJakob Stoklund Olesen UsableRegs.resize(tri_->getNumRegs(), true); 9943fd3a840c50fe4ede1b200be18990bc955c536fdJakob Stoklund Olesen Found = true; 9953fd3a840c50fe4ede1b200be18990bc955c536fdJakob Stoklund Olesen } 9963fd3a840c50fe4ede1b200be18990bc955c536fdJakob Stoklund Olesen // Remove usable registers clobbered by this mask. 9979f10ac63a3a2a74ac381a05d8ba0f7b1b455a6b6Jakob Stoklund Olesen UsableRegs.clearBitsNotInMask(Bits[SlotI-Slots.begin()]); 9983fd3a840c50fe4ede1b200be18990bc955c536fdJakob Stoklund Olesen if (++SlotI == SlotE) 9993fd3a840c50fe4ede1b200be18990bc955c536fdJakob Stoklund Olesen return Found; 10003fd3a840c50fe4ede1b200be18990bc955c536fdJakob Stoklund Olesen } 10013fd3a840c50fe4ede1b200be18990bc955c536fdJakob Stoklund Olesen // *SlotI is beyond the current LI segment. 10023fd3a840c50fe4ede1b200be18990bc955c536fdJakob Stoklund Olesen LiveI = LI.advanceTo(LiveI, *SlotI); 10033fd3a840c50fe4ede1b200be18990bc955c536fdJakob Stoklund Olesen if (LiveI == LiveE) 10043fd3a840c50fe4ede1b200be18990bc955c536fdJakob Stoklund Olesen return Found; 10053fd3a840c50fe4ede1b200be18990bc955c536fdJakob Stoklund Olesen // Advance SlotI until it overlaps. 10063fd3a840c50fe4ede1b200be18990bc955c536fdJakob Stoklund Olesen while (*SlotI < LiveI->start) 10073fd3a840c50fe4ede1b200be18990bc955c536fdJakob Stoklund Olesen if (++SlotI == SlotE) 10083fd3a840c50fe4ede1b200be18990bc955c536fdJakob Stoklund Olesen return Found; 10093fd3a840c50fe4ede1b200be18990bc955c536fdJakob Stoklund Olesen } 10103fd3a840c50fe4ede1b200be18990bc955c536fdJakob Stoklund Olesen} 10113dc7c5138d219048d69952bead22f75efb984fa3Lang Hames 10123dc7c5138d219048d69952bead22f75efb984fa3Lang Hames//===----------------------------------------------------------------------===// 10133dc7c5138d219048d69952bead22f75efb984fa3Lang Hames// IntervalUpdate class. 10143dc7c5138d219048d69952bead22f75efb984fa3Lang Hames//===----------------------------------------------------------------------===// 10153dc7c5138d219048d69952bead22f75efb984fa3Lang Hames 1016fd6d3217d3b577e704ff4826775b5938c23b9e73Lang Hames// HMEditor is a toolkit used by handleMove to trim or extend live intervals. 10173dc7c5138d219048d69952bead22f75efb984fa3Lang Hamesclass LiveIntervals::HMEditor { 10183dc7c5138d219048d69952bead22f75efb984fa3Lang Hamesprivate: 1019ecb50624d1e99596fdb289200cd1473cec84e097Lang Hames LiveIntervals& LIS; 1020ecb50624d1e99596fdb289200cd1473cec84e097Lang Hames const MachineRegisterInfo& MRI; 1021ecb50624d1e99596fdb289200cd1473cec84e097Lang Hames const TargetRegisterInfo& TRI; 1022ecb50624d1e99596fdb289200cd1473cec84e097Lang Hames SlotIndex NewIdx; 10233dc7c5138d219048d69952bead22f75efb984fa3Lang Hames 102455fed62c9eca0c8ebcaa6cc2fd65a173d37b3951Lang Hames typedef std::pair<LiveInterval*, LiveRange*> IntRangePair; 102555fed62c9eca0c8ebcaa6cc2fd65a173d37b3951Lang Hames typedef DenseSet<IntRangePair> RangeSet; 102655fed62c9eca0c8ebcaa6cc2fd65a173d37b3951Lang Hames 10276aceab139205255ac44182f51819b9b8716cf477Lang Hames struct RegRanges { 10286aceab139205255ac44182f51819b9b8716cf477Lang Hames LiveRange* Use; 10296aceab139205255ac44182f51819b9b8716cf477Lang Hames LiveRange* EC; 10306aceab139205255ac44182f51819b9b8716cf477Lang Hames LiveRange* Dead; 10316aceab139205255ac44182f51819b9b8716cf477Lang Hames LiveRange* Def; 10326aceab139205255ac44182f51819b9b8716cf477Lang Hames RegRanges() : Use(0), EC(0), Dead(0), Def(0) {} 10336aceab139205255ac44182f51819b9b8716cf477Lang Hames }; 10346aceab139205255ac44182f51819b9b8716cf477Lang Hames typedef DenseMap<unsigned, RegRanges> BundleRanges; 10356aceab139205255ac44182f51819b9b8716cf477Lang Hames 10363dc7c5138d219048d69952bead22f75efb984fa3Lang Hamespublic: 1037ecb50624d1e99596fdb289200cd1473cec84e097Lang Hames HMEditor(LiveIntervals& LIS, const MachineRegisterInfo& MRI, 1038ecb50624d1e99596fdb289200cd1473cec84e097Lang Hames const TargetRegisterInfo& TRI, SlotIndex NewIdx) 1039ecb50624d1e99596fdb289200cd1473cec84e097Lang Hames : LIS(LIS), MRI(MRI), TRI(TRI), NewIdx(NewIdx) {} 1040ecb50624d1e99596fdb289200cd1473cec84e097Lang Hames 104155fed62c9eca0c8ebcaa6cc2fd65a173d37b3951Lang Hames // Update intervals for all operands of MI from OldIdx to NewIdx. 104255fed62c9eca0c8ebcaa6cc2fd65a173d37b3951Lang Hames // This assumes that MI used to be at OldIdx, and now resides at 104355fed62c9eca0c8ebcaa6cc2fd65a173d37b3951Lang Hames // NewIdx. 10444586d257abf13b57d115d6bac9fb38ddc811acafLang Hames void moveAllRangesFrom(MachineInstr* MI, SlotIndex OldIdx) { 10456aceab139205255ac44182f51819b9b8716cf477Lang Hames assert(NewIdx != OldIdx && "No-op move? That's a bit strange."); 10466aceab139205255ac44182f51819b9b8716cf477Lang Hames 104755fed62c9eca0c8ebcaa6cc2fd65a173d37b3951Lang Hames // Collect the operands. 104855fed62c9eca0c8ebcaa6cc2fd65a173d37b3951Lang Hames RangeSet Entering, Internal, Exiting; 1049ac027144e8e22563c9bb057598c710aac57c072fLang Hames bool hasRegMaskOp = false; 1050ac027144e8e22563c9bb057598c710aac57c072fLang Hames collectRanges(MI, Entering, Internal, Exiting, hasRegMaskOp, OldIdx); 105155fed62c9eca0c8ebcaa6cc2fd65a173d37b3951Lang Hames 1052f70af52a8fc735a84aa8d63b84dd56abd0b9e77cAndrew Trick // To keep the LiveRanges valid within an interval, move the ranges closest 1053f70af52a8fc735a84aa8d63b84dd56abd0b9e77cAndrew Trick // to the destination first. This prevents ranges from overlapping, to that 1054f70af52a8fc735a84aa8d63b84dd56abd0b9e77cAndrew Trick // APIs like removeRange still work. 1055f70af52a8fc735a84aa8d63b84dd56abd0b9e77cAndrew Trick if (NewIdx < OldIdx) { 1056f70af52a8fc735a84aa8d63b84dd56abd0b9e77cAndrew Trick moveAllEnteringFrom(OldIdx, Entering); 1057f70af52a8fc735a84aa8d63b84dd56abd0b9e77cAndrew Trick moveAllInternalFrom(OldIdx, Internal); 1058f70af52a8fc735a84aa8d63b84dd56abd0b9e77cAndrew Trick moveAllExitingFrom(OldIdx, Exiting); 1059f70af52a8fc735a84aa8d63b84dd56abd0b9e77cAndrew Trick } 1060f70af52a8fc735a84aa8d63b84dd56abd0b9e77cAndrew Trick else { 1061f70af52a8fc735a84aa8d63b84dd56abd0b9e77cAndrew Trick moveAllExitingFrom(OldIdx, Exiting); 1062f70af52a8fc735a84aa8d63b84dd56abd0b9e77cAndrew Trick moveAllInternalFrom(OldIdx, Internal); 1063f70af52a8fc735a84aa8d63b84dd56abd0b9e77cAndrew Trick moveAllEnteringFrom(OldIdx, Entering); 1064f70af52a8fc735a84aa8d63b84dd56abd0b9e77cAndrew Trick } 10653dc7c5138d219048d69952bead22f75efb984fa3Lang Hames 1066ac027144e8e22563c9bb057598c710aac57c072fLang Hames if (hasRegMaskOp) 1067ac027144e8e22563c9bb057598c710aac57c072fLang Hames updateRegMaskSlots(OldIdx); 1068ac027144e8e22563c9bb057598c710aac57c072fLang Hames 106955fed62c9eca0c8ebcaa6cc2fd65a173d37b3951Lang Hames#ifndef NDEBUG 107055fed62c9eca0c8ebcaa6cc2fd65a173d37b3951Lang Hames LIValidator validator; 1071722b6f18536a1b23a03bfb55440f098da0a7762dPete Cooper validator = std::for_each(Entering.begin(), Entering.end(), validator); 1072722b6f18536a1b23a03bfb55440f098da0a7762dPete Cooper validator = std::for_each(Internal.begin(), Internal.end(), validator); 1073722b6f18536a1b23a03bfb55440f098da0a7762dPete Cooper validator = std::for_each(Exiting.begin(), Exiting.end(), validator); 10746aceab139205255ac44182f51819b9b8716cf477Lang Hames assert(validator.rangesOk() && "moveAllOperandsFrom broke liveness."); 107555fed62c9eca0c8ebcaa6cc2fd65a173d37b3951Lang Hames#endif 107655fed62c9eca0c8ebcaa6cc2fd65a173d37b3951Lang Hames 10773dc7c5138d219048d69952bead22f75efb984fa3Lang Hames } 10783dc7c5138d219048d69952bead22f75efb984fa3Lang Hames 10794586d257abf13b57d115d6bac9fb38ddc811acafLang Hames // Update intervals for all operands of MI to refer to BundleStart's 10804586d257abf13b57d115d6bac9fb38ddc811acafLang Hames // SlotIndex. 10814586d257abf13b57d115d6bac9fb38ddc811acafLang Hames void moveAllRangesInto(MachineInstr* MI, MachineInstr* BundleStart) { 10826aceab139205255ac44182f51819b9b8716cf477Lang Hames if (MI == BundleStart) 10836aceab139205255ac44182f51819b9b8716cf477Lang Hames return; // Bundling instr with itself - nothing to do. 10846aceab139205255ac44182f51819b9b8716cf477Lang Hames 1085fd6d3217d3b577e704ff4826775b5938c23b9e73Lang Hames SlotIndex OldIdx = LIS.getSlotIndexes()->getInstructionIndex(MI); 1086fd6d3217d3b577e704ff4826775b5938c23b9e73Lang Hames assert(LIS.getSlotIndexes()->getInstructionFromIndex(OldIdx) == MI && 1087fd6d3217d3b577e704ff4826775b5938c23b9e73Lang Hames "SlotIndex <-> Instruction mapping broken for MI"); 1088fd6d3217d3b577e704ff4826775b5938c23b9e73Lang Hames 10894586d257abf13b57d115d6bac9fb38ddc811acafLang Hames // Collect all ranges already in the bundle. 10904586d257abf13b57d115d6bac9fb38ddc811acafLang Hames MachineBasicBlock::instr_iterator BII(BundleStart); 10916aceab139205255ac44182f51819b9b8716cf477Lang Hames RangeSet Entering, Internal, Exiting; 10926aceab139205255ac44182f51819b9b8716cf477Lang Hames bool hasRegMaskOp = false; 10934586d257abf13b57d115d6bac9fb38ddc811acafLang Hames collectRanges(BII, Entering, Internal, Exiting, hasRegMaskOp, NewIdx); 10944586d257abf13b57d115d6bac9fb38ddc811acafLang Hames assert(!hasRegMaskOp && "Can't have RegMask operand in bundle."); 10954586d257abf13b57d115d6bac9fb38ddc811acafLang Hames for (++BII; &*BII == MI || BII->isInsideBundle(); ++BII) { 10964586d257abf13b57d115d6bac9fb38ddc811acafLang Hames if (&*BII == MI) 10974586d257abf13b57d115d6bac9fb38ddc811acafLang Hames continue; 10984586d257abf13b57d115d6bac9fb38ddc811acafLang Hames collectRanges(BII, Entering, Internal, Exiting, hasRegMaskOp, NewIdx); 10994586d257abf13b57d115d6bac9fb38ddc811acafLang Hames assert(!hasRegMaskOp && "Can't have RegMask operand in bundle."); 11004586d257abf13b57d115d6bac9fb38ddc811acafLang Hames } 11014586d257abf13b57d115d6bac9fb38ddc811acafLang Hames 11024586d257abf13b57d115d6bac9fb38ddc811acafLang Hames BundleRanges BR = createBundleRanges(Entering, Internal, Exiting); 11034586d257abf13b57d115d6bac9fb38ddc811acafLang Hames 11046aceab139205255ac44182f51819b9b8716cf477Lang Hames collectRanges(MI, Entering, Internal, Exiting, hasRegMaskOp, OldIdx); 11054586d257abf13b57d115d6bac9fb38ddc811acafLang Hames assert(!hasRegMaskOp && "Can't have RegMask operand in bundle."); 11064586d257abf13b57d115d6bac9fb38ddc811acafLang Hames 11074586d257abf13b57d115d6bac9fb38ddc811acafLang Hames DEBUG(dbgs() << "Entering: " << Entering.size() << "\n"); 11084586d257abf13b57d115d6bac9fb38ddc811acafLang Hames DEBUG(dbgs() << "Internal: " << Internal.size() << "\n"); 11094586d257abf13b57d115d6bac9fb38ddc811acafLang Hames DEBUG(dbgs() << "Exiting: " << Exiting.size() << "\n"); 11106aceab139205255ac44182f51819b9b8716cf477Lang Hames 11116aceab139205255ac44182f51819b9b8716cf477Lang Hames moveAllEnteringFromInto(OldIdx, Entering, BR); 11126aceab139205255ac44182f51819b9b8716cf477Lang Hames moveAllInternalFromInto(OldIdx, Internal, BR); 11136aceab139205255ac44182f51819b9b8716cf477Lang Hames moveAllExitingFromInto(OldIdx, Exiting, BR); 11146aceab139205255ac44182f51819b9b8716cf477Lang Hames 11154586d257abf13b57d115d6bac9fb38ddc811acafLang Hames 11166aceab139205255ac44182f51819b9b8716cf477Lang Hames#ifndef NDEBUG 11176aceab139205255ac44182f51819b9b8716cf477Lang Hames LIValidator validator; 1118722b6f18536a1b23a03bfb55440f098da0a7762dPete Cooper validator = std::for_each(Entering.begin(), Entering.end(), validator); 1119722b6f18536a1b23a03bfb55440f098da0a7762dPete Cooper validator = std::for_each(Internal.begin(), Internal.end(), validator); 1120722b6f18536a1b23a03bfb55440f098da0a7762dPete Cooper validator = std::for_each(Exiting.begin(), Exiting.end(), validator); 11216aceab139205255ac44182f51819b9b8716cf477Lang Hames assert(validator.rangesOk() && "moveAllOperandsInto broke liveness."); 11226aceab139205255ac44182f51819b9b8716cf477Lang Hames#endif 11236aceab139205255ac44182f51819b9b8716cf477Lang Hames } 11246aceab139205255ac44182f51819b9b8716cf477Lang Hames 112555fed62c9eca0c8ebcaa6cc2fd65a173d37b3951Lang Hamesprivate: 112655fed62c9eca0c8ebcaa6cc2fd65a173d37b3951Lang Hames 112755fed62c9eca0c8ebcaa6cc2fd65a173d37b3951Lang Hames#ifndef NDEBUG 112855fed62c9eca0c8ebcaa6cc2fd65a173d37b3951Lang Hames class LIValidator { 112955fed62c9eca0c8ebcaa6cc2fd65a173d37b3951Lang Hames private: 113055fed62c9eca0c8ebcaa6cc2fd65a173d37b3951Lang Hames DenseSet<const LiveInterval*> Checked, Bogus; 113155fed62c9eca0c8ebcaa6cc2fd65a173d37b3951Lang Hames public: 113255fed62c9eca0c8ebcaa6cc2fd65a173d37b3951Lang Hames void operator()(const IntRangePair& P) { 113355fed62c9eca0c8ebcaa6cc2fd65a173d37b3951Lang Hames const LiveInterval* LI = P.first; 113455fed62c9eca0c8ebcaa6cc2fd65a173d37b3951Lang Hames if (Checked.count(LI)) 113555fed62c9eca0c8ebcaa6cc2fd65a173d37b3951Lang Hames return; 113655fed62c9eca0c8ebcaa6cc2fd65a173d37b3951Lang Hames Checked.insert(LI); 113755fed62c9eca0c8ebcaa6cc2fd65a173d37b3951Lang Hames if (LI->empty()) 113855fed62c9eca0c8ebcaa6cc2fd65a173d37b3951Lang Hames return; 113955fed62c9eca0c8ebcaa6cc2fd65a173d37b3951Lang Hames SlotIndex LastEnd = LI->begin()->start; 114055fed62c9eca0c8ebcaa6cc2fd65a173d37b3951Lang Hames for (LiveInterval::const_iterator LRI = LI->begin(), LRE = LI->end(); 114155fed62c9eca0c8ebcaa6cc2fd65a173d37b3951Lang Hames LRI != LRE; ++LRI) { 114255fed62c9eca0c8ebcaa6cc2fd65a173d37b3951Lang Hames const LiveRange& LR = *LRI; 114355fed62c9eca0c8ebcaa6cc2fd65a173d37b3951Lang Hames if (LastEnd > LR.start || LR.start >= LR.end) 114455fed62c9eca0c8ebcaa6cc2fd65a173d37b3951Lang Hames Bogus.insert(LI); 114555fed62c9eca0c8ebcaa6cc2fd65a173d37b3951Lang Hames LastEnd = LR.end; 11463dc7c5138d219048d69952bead22f75efb984fa3Lang Hames } 11473dc7c5138d219048d69952bead22f75efb984fa3Lang Hames } 11483dc7c5138d219048d69952bead22f75efb984fa3Lang Hames 114955fed62c9eca0c8ebcaa6cc2fd65a173d37b3951Lang Hames bool rangesOk() const { 115055fed62c9eca0c8ebcaa6cc2fd65a173d37b3951Lang Hames return Bogus.empty(); 11513dc7c5138d219048d69952bead22f75efb984fa3Lang Hames } 115255fed62c9eca0c8ebcaa6cc2fd65a173d37b3951Lang Hames }; 115355fed62c9eca0c8ebcaa6cc2fd65a173d37b3951Lang Hames#endif 11543dc7c5138d219048d69952bead22f75efb984fa3Lang Hames 115555fed62c9eca0c8ebcaa6cc2fd65a173d37b3951Lang Hames // Collect IntRangePairs for all operands of MI that may need fixing. 115655fed62c9eca0c8ebcaa6cc2fd65a173d37b3951Lang Hames // Treat's MI's index as OldIdx (regardless of what it is in SlotIndexes' 115755fed62c9eca0c8ebcaa6cc2fd65a173d37b3951Lang Hames // maps). 115855fed62c9eca0c8ebcaa6cc2fd65a173d37b3951Lang Hames void collectRanges(MachineInstr* MI, RangeSet& Entering, RangeSet& Internal, 1159ac027144e8e22563c9bb057598c710aac57c072fLang Hames RangeSet& Exiting, bool& hasRegMaskOp, SlotIndex OldIdx) { 1160ac027144e8e22563c9bb057598c710aac57c072fLang Hames hasRegMaskOp = false; 1161ecb50624d1e99596fdb289200cd1473cec84e097Lang Hames for (MachineInstr::mop_iterator MOI = MI->operands_begin(), 1162ecb50624d1e99596fdb289200cd1473cec84e097Lang Hames MOE = MI->operands_end(); 1163ecb50624d1e99596fdb289200cd1473cec84e097Lang Hames MOI != MOE; ++MOI) { 1164ecb50624d1e99596fdb289200cd1473cec84e097Lang Hames const MachineOperand& MO = *MOI; 1165ac027144e8e22563c9bb057598c710aac57c072fLang Hames 1166ac027144e8e22563c9bb057598c710aac57c072fLang Hames if (MO.isRegMask()) { 1167ac027144e8e22563c9bb057598c710aac57c072fLang Hames hasRegMaskOp = true; 1168ac027144e8e22563c9bb057598c710aac57c072fLang Hames continue; 1169ac027144e8e22563c9bb057598c710aac57c072fLang Hames } 1170ac027144e8e22563c9bb057598c710aac57c072fLang Hames 1171ecb50624d1e99596fdb289200cd1473cec84e097Lang Hames if (!MO.isReg() || MO.getReg() == 0) 11723dc7c5138d219048d69952bead22f75efb984fa3Lang Hames continue; 11733dc7c5138d219048d69952bead22f75efb984fa3Lang Hames 1174ecb50624d1e99596fdb289200cd1473cec84e097Lang Hames unsigned Reg = MO.getReg(); 11753dc7c5138d219048d69952bead22f75efb984fa3Lang Hames 11763dc7c5138d219048d69952bead22f75efb984fa3Lang Hames // TODO: Currently we're skipping uses that are reserved or have no 11773dc7c5138d219048d69952bead22f75efb984fa3Lang Hames // interval, but we're not updating their kills. This should be 11783dc7c5138d219048d69952bead22f75efb984fa3Lang Hames // fixed. 1179ecb50624d1e99596fdb289200cd1473cec84e097Lang Hames if (!LIS.hasInterval(Reg) || 1180ecb50624d1e99596fdb289200cd1473cec84e097Lang Hames (TargetRegisterInfo::isPhysicalRegister(Reg) && LIS.isReserved(Reg))) 11813dc7c5138d219048d69952bead22f75efb984fa3Lang Hames continue; 11823dc7c5138d219048d69952bead22f75efb984fa3Lang Hames 118355fed62c9eca0c8ebcaa6cc2fd65a173d37b3951Lang Hames LiveInterval* LI = &LIS.getInterval(Reg); 118455fed62c9eca0c8ebcaa6cc2fd65a173d37b3951Lang Hames 118555fed62c9eca0c8ebcaa6cc2fd65a173d37b3951Lang Hames if (MO.readsReg()) { 118655fed62c9eca0c8ebcaa6cc2fd65a173d37b3951Lang Hames LiveRange* LR = LI->getLiveRangeContaining(OldIdx); 118755fed62c9eca0c8ebcaa6cc2fd65a173d37b3951Lang Hames if (LR != 0) 118855fed62c9eca0c8ebcaa6cc2fd65a173d37b3951Lang Hames Entering.insert(std::make_pair(LI, LR)); 11893dc7c5138d219048d69952bead22f75efb984fa3Lang Hames } 1190ecb50624d1e99596fdb289200cd1473cec84e097Lang Hames if (MO.isDef()) { 119155fed62c9eca0c8ebcaa6cc2fd65a173d37b3951Lang Hames if (MO.isEarlyClobber()) { 119255fed62c9eca0c8ebcaa6cc2fd65a173d37b3951Lang Hames LiveRange* LR = LI->getLiveRangeContaining(OldIdx.getRegSlot(true)); 119355fed62c9eca0c8ebcaa6cc2fd65a173d37b3951Lang Hames assert(LR != 0 && "No EC range?"); 119455fed62c9eca0c8ebcaa6cc2fd65a173d37b3951Lang Hames if (LR->end > OldIdx.getDeadSlot()) 119555fed62c9eca0c8ebcaa6cc2fd65a173d37b3951Lang Hames Exiting.insert(std::make_pair(LI, LR)); 119655fed62c9eca0c8ebcaa6cc2fd65a173d37b3951Lang Hames else 1197ac027144e8e22563c9bb057598c710aac57c072fLang Hames Internal.insert(std::make_pair(LI, LR)); 119855fed62c9eca0c8ebcaa6cc2fd65a173d37b3951Lang Hames } else if (MO.isDead()) { 119955fed62c9eca0c8ebcaa6cc2fd65a173d37b3951Lang Hames LiveRange* LR = LI->getLiveRangeContaining(OldIdx.getRegSlot()); 120055fed62c9eca0c8ebcaa6cc2fd65a173d37b3951Lang Hames assert(LR != 0 && "No dead-def range?"); 120155fed62c9eca0c8ebcaa6cc2fd65a173d37b3951Lang Hames Internal.insert(std::make_pair(LI, LR)); 12023dc7c5138d219048d69952bead22f75efb984fa3Lang Hames } else { 120355fed62c9eca0c8ebcaa6cc2fd65a173d37b3951Lang Hames LiveRange* LR = LI->getLiveRangeContaining(OldIdx.getDeadSlot()); 120455fed62c9eca0c8ebcaa6cc2fd65a173d37b3951Lang Hames assert(LR && LR->end > OldIdx.getDeadSlot() && 120555fed62c9eca0c8ebcaa6cc2fd65a173d37b3951Lang Hames "Non-dead-def should have live range exiting."); 120655fed62c9eca0c8ebcaa6cc2fd65a173d37b3951Lang Hames Exiting.insert(std::make_pair(LI, LR)); 12073dc7c5138d219048d69952bead22f75efb984fa3Lang Hames } 12083dc7c5138d219048d69952bead22f75efb984fa3Lang Hames } 12093dc7c5138d219048d69952bead22f75efb984fa3Lang Hames } 12103dc7c5138d219048d69952bead22f75efb984fa3Lang Hames } 12113dc7c5138d219048d69952bead22f75efb984fa3Lang Hames 12124586d257abf13b57d115d6bac9fb38ddc811acafLang Hames // Collect IntRangePairs for all operands of MI that may need fixing. 12134586d257abf13b57d115d6bac9fb38ddc811acafLang Hames void collectRangesInBundle(MachineInstr* MI, RangeSet& Entering, 12144586d257abf13b57d115d6bac9fb38ddc811acafLang Hames RangeSet& Exiting, SlotIndex MIStartIdx, 12154586d257abf13b57d115d6bac9fb38ddc811acafLang Hames SlotIndex MIEndIdx) { 12164586d257abf13b57d115d6bac9fb38ddc811acafLang Hames for (MachineInstr::mop_iterator MOI = MI->operands_begin(), 12174586d257abf13b57d115d6bac9fb38ddc811acafLang Hames MOE = MI->operands_end(); 12184586d257abf13b57d115d6bac9fb38ddc811acafLang Hames MOI != MOE; ++MOI) { 12194586d257abf13b57d115d6bac9fb38ddc811acafLang Hames const MachineOperand& MO = *MOI; 12204586d257abf13b57d115d6bac9fb38ddc811acafLang Hames assert(!MO.isRegMask() && "Can't have RegMasks in bundles."); 12214586d257abf13b57d115d6bac9fb38ddc811acafLang Hames if (!MO.isReg() || MO.getReg() == 0) 12224586d257abf13b57d115d6bac9fb38ddc811acafLang Hames continue; 12236aceab139205255ac44182f51819b9b8716cf477Lang Hames 12244586d257abf13b57d115d6bac9fb38ddc811acafLang Hames unsigned Reg = MO.getReg(); 12254586d257abf13b57d115d6bac9fb38ddc811acafLang Hames 12264586d257abf13b57d115d6bac9fb38ddc811acafLang Hames // TODO: Currently we're skipping uses that are reserved or have no 12274586d257abf13b57d115d6bac9fb38ddc811acafLang Hames // interval, but we're not updating their kills. This should be 12284586d257abf13b57d115d6bac9fb38ddc811acafLang Hames // fixed. 12294586d257abf13b57d115d6bac9fb38ddc811acafLang Hames if (!LIS.hasInterval(Reg) || 12304586d257abf13b57d115d6bac9fb38ddc811acafLang Hames (TargetRegisterInfo::isPhysicalRegister(Reg) && LIS.isReserved(Reg))) 12314586d257abf13b57d115d6bac9fb38ddc811acafLang Hames continue; 12324586d257abf13b57d115d6bac9fb38ddc811acafLang Hames 12334586d257abf13b57d115d6bac9fb38ddc811acafLang Hames LiveInterval* LI = &LIS.getInterval(Reg); 12344586d257abf13b57d115d6bac9fb38ddc811acafLang Hames 12354586d257abf13b57d115d6bac9fb38ddc811acafLang Hames if (MO.readsReg()) { 12364586d257abf13b57d115d6bac9fb38ddc811acafLang Hames LiveRange* LR = LI->getLiveRangeContaining(MIStartIdx); 12374586d257abf13b57d115d6bac9fb38ddc811acafLang Hames if (LR != 0) 12384586d257abf13b57d115d6bac9fb38ddc811acafLang Hames Entering.insert(std::make_pair(LI, LR)); 12394586d257abf13b57d115d6bac9fb38ddc811acafLang Hames } 12404586d257abf13b57d115d6bac9fb38ddc811acafLang Hames if (MO.isDef()) { 12414586d257abf13b57d115d6bac9fb38ddc811acafLang Hames assert(!MO.isEarlyClobber() && "Early clobbers not allowed in bundles."); 12424586d257abf13b57d115d6bac9fb38ddc811acafLang Hames assert(!MO.isDead() && "Dead-defs not allowed in bundles."); 12434586d257abf13b57d115d6bac9fb38ddc811acafLang Hames LiveRange* LR = LI->getLiveRangeContaining(MIEndIdx.getDeadSlot()); 12444586d257abf13b57d115d6bac9fb38ddc811acafLang Hames assert(LR != 0 && "Internal ranges not allowed in bundles."); 12454586d257abf13b57d115d6bac9fb38ddc811acafLang Hames Exiting.insert(std::make_pair(LI, LR)); 12464586d257abf13b57d115d6bac9fb38ddc811acafLang Hames } 12476aceab139205255ac44182f51819b9b8716cf477Lang Hames } 12484586d257abf13b57d115d6bac9fb38ddc811acafLang Hames } 12494586d257abf13b57d115d6bac9fb38ddc811acafLang Hames 12504586d257abf13b57d115d6bac9fb38ddc811acafLang Hames BundleRanges createBundleRanges(RangeSet& Entering, RangeSet& Internal, RangeSet& Exiting) { 12514586d257abf13b57d115d6bac9fb38ddc811acafLang Hames BundleRanges BR; 12526aceab139205255ac44182f51819b9b8716cf477Lang Hames 12536aceab139205255ac44182f51819b9b8716cf477Lang Hames for (RangeSet::iterator EI = Entering.begin(), EE = Entering.end(); 1254fd6d3217d3b577e704ff4826775b5938c23b9e73Lang Hames EI != EE; ++EI) { 12556aceab139205255ac44182f51819b9b8716cf477Lang Hames LiveInterval* LI = EI->first; 12566aceab139205255ac44182f51819b9b8716cf477Lang Hames LiveRange* LR = EI->second; 12576aceab139205255ac44182f51819b9b8716cf477Lang Hames BR[LI->reg].Use = LR; 12586aceab139205255ac44182f51819b9b8716cf477Lang Hames } 12596aceab139205255ac44182f51819b9b8716cf477Lang Hames 12606aceab139205255ac44182f51819b9b8716cf477Lang Hames for (RangeSet::iterator II = Internal.begin(), IE = Internal.end(); 1261fd6d3217d3b577e704ff4826775b5938c23b9e73Lang Hames II != IE; ++II) { 12626aceab139205255ac44182f51819b9b8716cf477Lang Hames LiveInterval* LI = II->first; 12636aceab139205255ac44182f51819b9b8716cf477Lang Hames LiveRange* LR = II->second; 12646aceab139205255ac44182f51819b9b8716cf477Lang Hames if (LR->end.isDead()) { 12656aceab139205255ac44182f51819b9b8716cf477Lang Hames BR[LI->reg].Dead = LR; 12666aceab139205255ac44182f51819b9b8716cf477Lang Hames } else { 12676aceab139205255ac44182f51819b9b8716cf477Lang Hames BR[LI->reg].EC = LR; 12686aceab139205255ac44182f51819b9b8716cf477Lang Hames } 12696aceab139205255ac44182f51819b9b8716cf477Lang Hames } 12706aceab139205255ac44182f51819b9b8716cf477Lang Hames 12716aceab139205255ac44182f51819b9b8716cf477Lang Hames for (RangeSet::iterator EI = Exiting.begin(), EE = Exiting.end(); 1272fd6d3217d3b577e704ff4826775b5938c23b9e73Lang Hames EI != EE; ++EI) { 12736aceab139205255ac44182f51819b9b8716cf477Lang Hames LiveInterval* LI = EI->first; 12746aceab139205255ac44182f51819b9b8716cf477Lang Hames LiveRange* LR = EI->second; 12756aceab139205255ac44182f51819b9b8716cf477Lang Hames BR[LI->reg].Def = LR; 12766aceab139205255ac44182f51819b9b8716cf477Lang Hames } 12776aceab139205255ac44182f51819b9b8716cf477Lang Hames 12786aceab139205255ac44182f51819b9b8716cf477Lang Hames return BR; 12796aceab139205255ac44182f51819b9b8716cf477Lang Hames } 12806aceab139205255ac44182f51819b9b8716cf477Lang Hames 1281ecb50624d1e99596fdb289200cd1473cec84e097Lang Hames void moveKillFlags(unsigned reg, SlotIndex OldIdx, SlotIndex newKillIdx) { 1282ecb50624d1e99596fdb289200cd1473cec84e097Lang Hames MachineInstr* OldKillMI = LIS.getInstructionFromIndex(OldIdx); 1283ecb50624d1e99596fdb289200cd1473cec84e097Lang Hames if (!OldKillMI->killsRegister(reg)) 12843dc7c5138d219048d69952bead22f75efb984fa3Lang Hames return; // Bail out if we don't have kill flags on the old register. 1285ecb50624d1e99596fdb289200cd1473cec84e097Lang Hames MachineInstr* NewKillMI = LIS.getInstructionFromIndex(newKillIdx); 1286ecb50624d1e99596fdb289200cd1473cec84e097Lang Hames assert(OldKillMI->killsRegister(reg) && "Old 'kill' instr isn't a kill."); 1287ecb50624d1e99596fdb289200cd1473cec84e097Lang Hames assert(!NewKillMI->killsRegister(reg) && "New kill instr is already a kill."); 1288ecb50624d1e99596fdb289200cd1473cec84e097Lang Hames OldKillMI->clearRegisterKills(reg, &TRI); 1289ecb50624d1e99596fdb289200cd1473cec84e097Lang Hames NewKillMI->addRegisterKilled(reg, &TRI); 12903dc7c5138d219048d69952bead22f75efb984fa3Lang Hames } 12913dc7c5138d219048d69952bead22f75efb984fa3Lang Hames 129255fed62c9eca0c8ebcaa6cc2fd65a173d37b3951Lang Hames void updateRegMaskSlots(SlotIndex OldIdx) { 129355fed62c9eca0c8ebcaa6cc2fd65a173d37b3951Lang Hames SmallVectorImpl<SlotIndex>::iterator RI = 129455fed62c9eca0c8ebcaa6cc2fd65a173d37b3951Lang Hames std::lower_bound(LIS.RegMaskSlots.begin(), LIS.RegMaskSlots.end(), 129555fed62c9eca0c8ebcaa6cc2fd65a173d37b3951Lang Hames OldIdx); 129655fed62c9eca0c8ebcaa6cc2fd65a173d37b3951Lang Hames assert(*RI == OldIdx && "No RegMask at OldIdx."); 129755fed62c9eca0c8ebcaa6cc2fd65a173d37b3951Lang Hames *RI = NewIdx; 129855fed62c9eca0c8ebcaa6cc2fd65a173d37b3951Lang Hames assert(*prior(RI) < *RI && *RI < *next(RI) && 129955fed62c9eca0c8ebcaa6cc2fd65a173d37b3951Lang Hames "RegSlots out of order. Did you move one call across another?"); 13003dc7c5138d219048d69952bead22f75efb984fa3Lang Hames } 13013dc7c5138d219048d69952bead22f75efb984fa3Lang Hames 130255fed62c9eca0c8ebcaa6cc2fd65a173d37b3951Lang Hames // Return the last use of reg between NewIdx and OldIdx. 130355fed62c9eca0c8ebcaa6cc2fd65a173d37b3951Lang Hames SlotIndex findLastUseBefore(unsigned Reg, SlotIndex OldIdx) { 130455fed62c9eca0c8ebcaa6cc2fd65a173d37b3951Lang Hames SlotIndex LastUse = NewIdx; 130555fed62c9eca0c8ebcaa6cc2fd65a173d37b3951Lang Hames for (MachineRegisterInfo::use_nodbg_iterator 130655fed62c9eca0c8ebcaa6cc2fd65a173d37b3951Lang Hames UI = MRI.use_nodbg_begin(Reg), 130755fed62c9eca0c8ebcaa6cc2fd65a173d37b3951Lang Hames UE = MRI.use_nodbg_end(); 1308038d2d5cede26b1ab63a732348b60ffc430dd7b0Lang Hames UI != UE; UI.skipInstruction()) { 130955fed62c9eca0c8ebcaa6cc2fd65a173d37b3951Lang Hames const MachineInstr* MI = &*UI; 131055fed62c9eca0c8ebcaa6cc2fd65a173d37b3951Lang Hames SlotIndex InstSlot = LIS.getSlotIndexes()->getInstructionIndex(MI); 131155fed62c9eca0c8ebcaa6cc2fd65a173d37b3951Lang Hames if (InstSlot > LastUse && InstSlot < OldIdx) 131255fed62c9eca0c8ebcaa6cc2fd65a173d37b3951Lang Hames LastUse = InstSlot; 13133dc7c5138d219048d69952bead22f75efb984fa3Lang Hames } 131455fed62c9eca0c8ebcaa6cc2fd65a173d37b3951Lang Hames return LastUse; 13153dc7c5138d219048d69952bead22f75efb984fa3Lang Hames } 13163dc7c5138d219048d69952bead22f75efb984fa3Lang Hames 131755fed62c9eca0c8ebcaa6cc2fd65a173d37b3951Lang Hames void moveEnteringUpFrom(SlotIndex OldIdx, IntRangePair& P) { 131855fed62c9eca0c8ebcaa6cc2fd65a173d37b3951Lang Hames LiveInterval* LI = P.first; 131955fed62c9eca0c8ebcaa6cc2fd65a173d37b3951Lang Hames LiveRange* LR = P.second; 132055fed62c9eca0c8ebcaa6cc2fd65a173d37b3951Lang Hames bool LiveThrough = LR->end > OldIdx.getRegSlot(); 132155fed62c9eca0c8ebcaa6cc2fd65a173d37b3951Lang Hames if (LiveThrough) 132255fed62c9eca0c8ebcaa6cc2fd65a173d37b3951Lang Hames return; 132355fed62c9eca0c8ebcaa6cc2fd65a173d37b3951Lang Hames SlotIndex LastUse = findLastUseBefore(LI->reg, OldIdx); 132455fed62c9eca0c8ebcaa6cc2fd65a173d37b3951Lang Hames if (LastUse != NewIdx) 132555fed62c9eca0c8ebcaa6cc2fd65a173d37b3951Lang Hames moveKillFlags(LI->reg, NewIdx, LastUse); 13266aceab139205255ac44182f51819b9b8716cf477Lang Hames LR->end = LastUse.getRegSlot(); 13273dc7c5138d219048d69952bead22f75efb984fa3Lang Hames } 13283dc7c5138d219048d69952bead22f75efb984fa3Lang Hames 132955fed62c9eca0c8ebcaa6cc2fd65a173d37b3951Lang Hames void moveEnteringDownFrom(SlotIndex OldIdx, IntRangePair& P) { 133055fed62c9eca0c8ebcaa6cc2fd65a173d37b3951Lang Hames LiveInterval* LI = P.first; 133155fed62c9eca0c8ebcaa6cc2fd65a173d37b3951Lang Hames LiveRange* LR = P.second; 1332e0b51ab8d3484b5b526a942f26c4db8082fed1e1Andrew Trick // Extend the LiveRange if NewIdx is past the end. 13334a0b2d658ae9e296598f8c8ac36c7fe571a7eec5Lang Hames if (NewIdx > LR->end) { 1334e0b51ab8d3484b5b526a942f26c4db8082fed1e1Andrew Trick // Move kill flags if OldIdx was not originally the end 1335e0b51ab8d3484b5b526a942f26c4db8082fed1e1Andrew Trick // (otherwise LR->end points to an invalid slot). 1336e0b51ab8d3484b5b526a942f26c4db8082fed1e1Andrew Trick if (LR->end.getRegSlot() != OldIdx.getRegSlot()) { 1337e0b51ab8d3484b5b526a942f26c4db8082fed1e1Andrew Trick assert(LR->end > OldIdx && "LiveRange does not cover original slot"); 1338e0b51ab8d3484b5b526a942f26c4db8082fed1e1Andrew Trick moveKillFlags(LI->reg, LR->end, NewIdx); 1339e0b51ab8d3484b5b526a942f26c4db8082fed1e1Andrew Trick } 13404a0b2d658ae9e296598f8c8ac36c7fe571a7eec5Lang Hames LR->end = NewIdx.getRegSlot(); 13413dc7c5138d219048d69952bead22f75efb984fa3Lang Hames } 13423dc7c5138d219048d69952bead22f75efb984fa3Lang Hames } 13433dc7c5138d219048d69952bead22f75efb984fa3Lang Hames 134455fed62c9eca0c8ebcaa6cc2fd65a173d37b3951Lang Hames void moveAllEnteringFrom(SlotIndex OldIdx, RangeSet& Entering) { 134555fed62c9eca0c8ebcaa6cc2fd65a173d37b3951Lang Hames bool GoingUp = NewIdx < OldIdx; 134655fed62c9eca0c8ebcaa6cc2fd65a173d37b3951Lang Hames 134755fed62c9eca0c8ebcaa6cc2fd65a173d37b3951Lang Hames if (GoingUp) { 134855fed62c9eca0c8ebcaa6cc2fd65a173d37b3951Lang Hames for (RangeSet::iterator EI = Entering.begin(), EE = Entering.end(); 134955fed62c9eca0c8ebcaa6cc2fd65a173d37b3951Lang Hames EI != EE; ++EI) 135055fed62c9eca0c8ebcaa6cc2fd65a173d37b3951Lang Hames moveEnteringUpFrom(OldIdx, *EI); 135155fed62c9eca0c8ebcaa6cc2fd65a173d37b3951Lang Hames } else { 135255fed62c9eca0c8ebcaa6cc2fd65a173d37b3951Lang Hames for (RangeSet::iterator EI = Entering.begin(), EE = Entering.end(); 135355fed62c9eca0c8ebcaa6cc2fd65a173d37b3951Lang Hames EI != EE; ++EI) 135455fed62c9eca0c8ebcaa6cc2fd65a173d37b3951Lang Hames moveEnteringDownFrom(OldIdx, *EI); 13553dc7c5138d219048d69952bead22f75efb984fa3Lang Hames } 13563dc7c5138d219048d69952bead22f75efb984fa3Lang Hames } 1357fbc8dd306aa7699a866db278db08d842762b2dc2Lang Hames 135855fed62c9eca0c8ebcaa6cc2fd65a173d37b3951Lang Hames void moveInternalFrom(SlotIndex OldIdx, IntRangePair& P) { 135955fed62c9eca0c8ebcaa6cc2fd65a173d37b3951Lang Hames LiveInterval* LI = P.first; 136055fed62c9eca0c8ebcaa6cc2fd65a173d37b3951Lang Hames LiveRange* LR = P.second; 136155fed62c9eca0c8ebcaa6cc2fd65a173d37b3951Lang Hames assert(OldIdx < LR->start && LR->start < OldIdx.getDeadSlot() && 136255fed62c9eca0c8ebcaa6cc2fd65a173d37b3951Lang Hames LR->end <= OldIdx.getDeadSlot() && 136355fed62c9eca0c8ebcaa6cc2fd65a173d37b3951Lang Hames "Range should be internal to OldIdx."); 136455fed62c9eca0c8ebcaa6cc2fd65a173d37b3951Lang Hames LiveRange Tmp(*LR); 136555fed62c9eca0c8ebcaa6cc2fd65a173d37b3951Lang Hames Tmp.start = NewIdx.getRegSlot(LR->start.isEarlyClobber()); 136655fed62c9eca0c8ebcaa6cc2fd65a173d37b3951Lang Hames Tmp.valno->def = Tmp.start; 136755fed62c9eca0c8ebcaa6cc2fd65a173d37b3951Lang Hames Tmp.end = LR->end.isDead() ? NewIdx.getDeadSlot() : NewIdx.getRegSlot(); 136855fed62c9eca0c8ebcaa6cc2fd65a173d37b3951Lang Hames LI->removeRange(*LR); 136955fed62c9eca0c8ebcaa6cc2fd65a173d37b3951Lang Hames LI->addRange(Tmp); 137055fed62c9eca0c8ebcaa6cc2fd65a173d37b3951Lang Hames } 137155fed62c9eca0c8ebcaa6cc2fd65a173d37b3951Lang Hames 137255fed62c9eca0c8ebcaa6cc2fd65a173d37b3951Lang Hames void moveAllInternalFrom(SlotIndex OldIdx, RangeSet& Internal) { 137355fed62c9eca0c8ebcaa6cc2fd65a173d37b3951Lang Hames for (RangeSet::iterator II = Internal.begin(), IE = Internal.end(); 137455fed62c9eca0c8ebcaa6cc2fd65a173d37b3951Lang Hames II != IE; ++II) 137555fed62c9eca0c8ebcaa6cc2fd65a173d37b3951Lang Hames moveInternalFrom(OldIdx, *II); 1376fbc8dd306aa7699a866db278db08d842762b2dc2Lang Hames } 137755fed62c9eca0c8ebcaa6cc2fd65a173d37b3951Lang Hames 137855fed62c9eca0c8ebcaa6cc2fd65a173d37b3951Lang Hames void moveExitingFrom(SlotIndex OldIdx, IntRangePair& P) { 137955fed62c9eca0c8ebcaa6cc2fd65a173d37b3951Lang Hames LiveRange* LR = P.second; 138055fed62c9eca0c8ebcaa6cc2fd65a173d37b3951Lang Hames assert(OldIdx < LR->start && LR->start < OldIdx.getDeadSlot() && 138155fed62c9eca0c8ebcaa6cc2fd65a173d37b3951Lang Hames "Range should start in OldIdx."); 138255fed62c9eca0c8ebcaa6cc2fd65a173d37b3951Lang Hames assert(LR->end > OldIdx.getDeadSlot() && "Range should exit OldIdx."); 138355fed62c9eca0c8ebcaa6cc2fd65a173d37b3951Lang Hames SlotIndex NewStart = NewIdx.getRegSlot(LR->start.isEarlyClobber()); 138455fed62c9eca0c8ebcaa6cc2fd65a173d37b3951Lang Hames LR->start = NewStart; 138555fed62c9eca0c8ebcaa6cc2fd65a173d37b3951Lang Hames LR->valno->def = NewStart; 138655fed62c9eca0c8ebcaa6cc2fd65a173d37b3951Lang Hames } 138755fed62c9eca0c8ebcaa6cc2fd65a173d37b3951Lang Hames 138855fed62c9eca0c8ebcaa6cc2fd65a173d37b3951Lang Hames void moveAllExitingFrom(SlotIndex OldIdx, RangeSet& Exiting) { 138955fed62c9eca0c8ebcaa6cc2fd65a173d37b3951Lang Hames for (RangeSet::iterator EI = Exiting.begin(), EE = Exiting.end(); 139055fed62c9eca0c8ebcaa6cc2fd65a173d37b3951Lang Hames EI != EE; ++EI) 139155fed62c9eca0c8ebcaa6cc2fd65a173d37b3951Lang Hames moveExitingFrom(OldIdx, *EI); 139255fed62c9eca0c8ebcaa6cc2fd65a173d37b3951Lang Hames } 139355fed62c9eca0c8ebcaa6cc2fd65a173d37b3951Lang Hames 13946aceab139205255ac44182f51819b9b8716cf477Lang Hames void moveEnteringUpFromInto(SlotIndex OldIdx, IntRangePair& P, 13956aceab139205255ac44182f51819b9b8716cf477Lang Hames BundleRanges& BR) { 13966aceab139205255ac44182f51819b9b8716cf477Lang Hames LiveInterval* LI = P.first; 13976aceab139205255ac44182f51819b9b8716cf477Lang Hames LiveRange* LR = P.second; 13986aceab139205255ac44182f51819b9b8716cf477Lang Hames bool LiveThrough = LR->end > OldIdx.getRegSlot(); 13996aceab139205255ac44182f51819b9b8716cf477Lang Hames if (LiveThrough) { 14006aceab139205255ac44182f51819b9b8716cf477Lang Hames assert((LR->start < NewIdx || BR[LI->reg].Def == LR) && 14016aceab139205255ac44182f51819b9b8716cf477Lang Hames "Def in bundle should be def range."); 14026aceab139205255ac44182f51819b9b8716cf477Lang Hames assert((BR[LI->reg].Use == 0 || BR[LI->reg].Use == LR) && 14036aceab139205255ac44182f51819b9b8716cf477Lang Hames "If bundle has use for this reg it should be LR."); 14046aceab139205255ac44182f51819b9b8716cf477Lang Hames BR[LI->reg].Use = LR; 14056aceab139205255ac44182f51819b9b8716cf477Lang Hames return; 14066aceab139205255ac44182f51819b9b8716cf477Lang Hames } 14076aceab139205255ac44182f51819b9b8716cf477Lang Hames 14086aceab139205255ac44182f51819b9b8716cf477Lang Hames SlotIndex LastUse = findLastUseBefore(LI->reg, OldIdx); 1409fd6d3217d3b577e704ff4826775b5938c23b9e73Lang Hames moveKillFlags(LI->reg, OldIdx, LastUse); 14106aceab139205255ac44182f51819b9b8716cf477Lang Hames 14116aceab139205255ac44182f51819b9b8716cf477Lang Hames if (LR->start < NewIdx) { 14126aceab139205255ac44182f51819b9b8716cf477Lang Hames // Becoming a new entering range. 14136aceab139205255ac44182f51819b9b8716cf477Lang Hames assert(BR[LI->reg].Dead == 0 && BR[LI->reg].Def == 0 && 14146aceab139205255ac44182f51819b9b8716cf477Lang Hames "Bundle shouldn't be re-defining reg mid-range."); 14157db76e7ca39905bbe3cb79158af0a93ca66faff8Benjamin Kramer assert((BR[LI->reg].Use == 0 || BR[LI->reg].Use == LR) && 14166aceab139205255ac44182f51819b9b8716cf477Lang Hames "Bundle shouldn't have different use range for same reg."); 14176aceab139205255ac44182f51819b9b8716cf477Lang Hames LR->end = LastUse.getRegSlot(); 14186aceab139205255ac44182f51819b9b8716cf477Lang Hames BR[LI->reg].Use = LR; 14196aceab139205255ac44182f51819b9b8716cf477Lang Hames } else { 14206aceab139205255ac44182f51819b9b8716cf477Lang Hames // Becoming a new Dead-def. 14216aceab139205255ac44182f51819b9b8716cf477Lang Hames assert(LR->start == NewIdx.getRegSlot(LR->start.isEarlyClobber()) && 14226aceab139205255ac44182f51819b9b8716cf477Lang Hames "Live range starting at unexpected slot."); 14236aceab139205255ac44182f51819b9b8716cf477Lang Hames assert(BR[LI->reg].Def == LR && "Reg should have def range."); 14246aceab139205255ac44182f51819b9b8716cf477Lang Hames assert(BR[LI->reg].Dead == 0 && 14256aceab139205255ac44182f51819b9b8716cf477Lang Hames "Can't have def and dead def of same reg in a bundle."); 14266aceab139205255ac44182f51819b9b8716cf477Lang Hames LR->end = LastUse.getDeadSlot(); 14276aceab139205255ac44182f51819b9b8716cf477Lang Hames BR[LI->reg].Dead = BR[LI->reg].Def; 14286aceab139205255ac44182f51819b9b8716cf477Lang Hames BR[LI->reg].Def = 0; 14296aceab139205255ac44182f51819b9b8716cf477Lang Hames } 14306aceab139205255ac44182f51819b9b8716cf477Lang Hames } 14316aceab139205255ac44182f51819b9b8716cf477Lang Hames 14326aceab139205255ac44182f51819b9b8716cf477Lang Hames void moveEnteringDownFromInto(SlotIndex OldIdx, IntRangePair& P, 14336aceab139205255ac44182f51819b9b8716cf477Lang Hames BundleRanges& BR) { 14346aceab139205255ac44182f51819b9b8716cf477Lang Hames LiveInterval* LI = P.first; 14356aceab139205255ac44182f51819b9b8716cf477Lang Hames LiveRange* LR = P.second; 14366aceab139205255ac44182f51819b9b8716cf477Lang Hames if (NewIdx > LR->end) { 14376aceab139205255ac44182f51819b9b8716cf477Lang Hames // Range extended to bundle. Add to bundle uses. 14386aceab139205255ac44182f51819b9b8716cf477Lang Hames // Note: Currently adds kill flags to bundle start. 14396aceab139205255ac44182f51819b9b8716cf477Lang Hames assert(BR[LI->reg].Use == 0 && 14406aceab139205255ac44182f51819b9b8716cf477Lang Hames "Bundle already has use range for reg."); 14416aceab139205255ac44182f51819b9b8716cf477Lang Hames moveKillFlags(LI->reg, LR->end, NewIdx); 14426aceab139205255ac44182f51819b9b8716cf477Lang Hames LR->end = NewIdx.getRegSlot(); 14436aceab139205255ac44182f51819b9b8716cf477Lang Hames BR[LI->reg].Use = LR; 14446aceab139205255ac44182f51819b9b8716cf477Lang Hames } else { 14456aceab139205255ac44182f51819b9b8716cf477Lang Hames assert(BR[LI->reg].Use != 0 && 14466aceab139205255ac44182f51819b9b8716cf477Lang Hames "Bundle should already have a use range for reg."); 14476aceab139205255ac44182f51819b9b8716cf477Lang Hames } 14486aceab139205255ac44182f51819b9b8716cf477Lang Hames } 14496aceab139205255ac44182f51819b9b8716cf477Lang Hames 14506aceab139205255ac44182f51819b9b8716cf477Lang Hames void moveAllEnteringFromInto(SlotIndex OldIdx, RangeSet& Entering, 14516aceab139205255ac44182f51819b9b8716cf477Lang Hames BundleRanges& BR) { 14526aceab139205255ac44182f51819b9b8716cf477Lang Hames bool GoingUp = NewIdx < OldIdx; 14536aceab139205255ac44182f51819b9b8716cf477Lang Hames 14546aceab139205255ac44182f51819b9b8716cf477Lang Hames if (GoingUp) { 14556aceab139205255ac44182f51819b9b8716cf477Lang Hames for (RangeSet::iterator EI = Entering.begin(), EE = Entering.end(); 14566aceab139205255ac44182f51819b9b8716cf477Lang Hames EI != EE; ++EI) 14576aceab139205255ac44182f51819b9b8716cf477Lang Hames moveEnteringUpFromInto(OldIdx, *EI, BR); 14586aceab139205255ac44182f51819b9b8716cf477Lang Hames } else { 14596aceab139205255ac44182f51819b9b8716cf477Lang Hames for (RangeSet::iterator EI = Entering.begin(), EE = Entering.end(); 14606aceab139205255ac44182f51819b9b8716cf477Lang Hames EI != EE; ++EI) 14616aceab139205255ac44182f51819b9b8716cf477Lang Hames moveEnteringDownFromInto(OldIdx, *EI, BR); 14626aceab139205255ac44182f51819b9b8716cf477Lang Hames } 14636aceab139205255ac44182f51819b9b8716cf477Lang Hames } 14646aceab139205255ac44182f51819b9b8716cf477Lang Hames 14656aceab139205255ac44182f51819b9b8716cf477Lang Hames void moveInternalFromInto(SlotIndex OldIdx, IntRangePair& P, 14666aceab139205255ac44182f51819b9b8716cf477Lang Hames BundleRanges& BR) { 14676aceab139205255ac44182f51819b9b8716cf477Lang Hames // TODO: Sane rules for moving ranges into bundles. 14686aceab139205255ac44182f51819b9b8716cf477Lang Hames } 14696aceab139205255ac44182f51819b9b8716cf477Lang Hames 14706aceab139205255ac44182f51819b9b8716cf477Lang Hames void moveAllInternalFromInto(SlotIndex OldIdx, RangeSet& Internal, 14716aceab139205255ac44182f51819b9b8716cf477Lang Hames BundleRanges& BR) { 14726aceab139205255ac44182f51819b9b8716cf477Lang Hames for (RangeSet::iterator II = Internal.begin(), IE = Internal.end(); 14736aceab139205255ac44182f51819b9b8716cf477Lang Hames II != IE; ++II) 14746aceab139205255ac44182f51819b9b8716cf477Lang Hames moveInternalFromInto(OldIdx, *II, BR); 14756aceab139205255ac44182f51819b9b8716cf477Lang Hames } 14766aceab139205255ac44182f51819b9b8716cf477Lang Hames 14776aceab139205255ac44182f51819b9b8716cf477Lang Hames void moveExitingFromInto(SlotIndex OldIdx, IntRangePair& P, 14786aceab139205255ac44182f51819b9b8716cf477Lang Hames BundleRanges& BR) { 14796aceab139205255ac44182f51819b9b8716cf477Lang Hames LiveInterval* LI = P.first; 14806aceab139205255ac44182f51819b9b8716cf477Lang Hames LiveRange* LR = P.second; 14816aceab139205255ac44182f51819b9b8716cf477Lang Hames 14826aceab139205255ac44182f51819b9b8716cf477Lang Hames assert(LR->start.isRegister() && 14836aceab139205255ac44182f51819b9b8716cf477Lang Hames "Don't know how to merge exiting ECs into bundles yet."); 14846aceab139205255ac44182f51819b9b8716cf477Lang Hames 14856aceab139205255ac44182f51819b9b8716cf477Lang Hames if (LR->end > NewIdx.getDeadSlot()) { 14866aceab139205255ac44182f51819b9b8716cf477Lang Hames // This range is becoming an exiting range on the bundle. 14876aceab139205255ac44182f51819b9b8716cf477Lang Hames // If there was an old dead-def of this reg, delete it. 14886aceab139205255ac44182f51819b9b8716cf477Lang Hames if (BR[LI->reg].Dead != 0) { 14896aceab139205255ac44182f51819b9b8716cf477Lang Hames LI->removeRange(*BR[LI->reg].Dead); 14906aceab139205255ac44182f51819b9b8716cf477Lang Hames BR[LI->reg].Dead = 0; 14916aceab139205255ac44182f51819b9b8716cf477Lang Hames } 14926aceab139205255ac44182f51819b9b8716cf477Lang Hames assert(BR[LI->reg].Def == 0 && 14936aceab139205255ac44182f51819b9b8716cf477Lang Hames "Can't have two defs for the same variable exiting a bundle."); 14946aceab139205255ac44182f51819b9b8716cf477Lang Hames LR->start = NewIdx.getRegSlot(); 14956aceab139205255ac44182f51819b9b8716cf477Lang Hames LR->valno->def = LR->start; 14966aceab139205255ac44182f51819b9b8716cf477Lang Hames BR[LI->reg].Def = LR; 14976aceab139205255ac44182f51819b9b8716cf477Lang Hames } else { 14986aceab139205255ac44182f51819b9b8716cf477Lang Hames // This range is becoming internal to the bundle. 14996aceab139205255ac44182f51819b9b8716cf477Lang Hames assert(LR->end == NewIdx.getRegSlot() && 15006aceab139205255ac44182f51819b9b8716cf477Lang Hames "Can't bundle def whose kill is before the bundle"); 15016aceab139205255ac44182f51819b9b8716cf477Lang Hames if (BR[LI->reg].Dead || BR[LI->reg].Def) { 15026aceab139205255ac44182f51819b9b8716cf477Lang Hames // Already have a def for this. Just delete range. 15036aceab139205255ac44182f51819b9b8716cf477Lang Hames LI->removeRange(*LR); 15046aceab139205255ac44182f51819b9b8716cf477Lang Hames } else { 15056aceab139205255ac44182f51819b9b8716cf477Lang Hames // Make range dead, record. 15066aceab139205255ac44182f51819b9b8716cf477Lang Hames LR->end = NewIdx.getDeadSlot(); 15076aceab139205255ac44182f51819b9b8716cf477Lang Hames BR[LI->reg].Dead = LR; 15086aceab139205255ac44182f51819b9b8716cf477Lang Hames assert(BR[LI->reg].Use == LR && 15096aceab139205255ac44182f51819b9b8716cf477Lang Hames "Range becoming dead should currently be use."); 15106aceab139205255ac44182f51819b9b8716cf477Lang Hames } 15116aceab139205255ac44182f51819b9b8716cf477Lang Hames // In both cases the range is no longer a use on the bundle. 15126aceab139205255ac44182f51819b9b8716cf477Lang Hames BR[LI->reg].Use = 0; 15136aceab139205255ac44182f51819b9b8716cf477Lang Hames } 15146aceab139205255ac44182f51819b9b8716cf477Lang Hames } 15156aceab139205255ac44182f51819b9b8716cf477Lang Hames 15166aceab139205255ac44182f51819b9b8716cf477Lang Hames void moveAllExitingFromInto(SlotIndex OldIdx, RangeSet& Exiting, 15176aceab139205255ac44182f51819b9b8716cf477Lang Hames BundleRanges& BR) { 15186aceab139205255ac44182f51819b9b8716cf477Lang Hames for (RangeSet::iterator EI = Exiting.begin(), EE = Exiting.end(); 15196aceab139205255ac44182f51819b9b8716cf477Lang Hames EI != EE; ++EI) 15206aceab139205255ac44182f51819b9b8716cf477Lang Hames moveExitingFromInto(OldIdx, *EI, BR); 15216aceab139205255ac44182f51819b9b8716cf477Lang Hames } 15226aceab139205255ac44182f51819b9b8716cf477Lang Hames 15233dc7c5138d219048d69952bead22f75efb984fa3Lang Hames}; 15243dc7c5138d219048d69952bead22f75efb984fa3Lang Hames 1525ecb50624d1e99596fdb289200cd1473cec84e097Lang Hamesvoid LiveIntervals::handleMove(MachineInstr* MI) { 1526ecb50624d1e99596fdb289200cd1473cec84e097Lang Hames SlotIndex OldIndex = indexes_->getInstructionIndex(MI); 1527ecb50624d1e99596fdb289200cd1473cec84e097Lang Hames indexes_->removeMachineInstrFromMaps(MI); 1528ecb50624d1e99596fdb289200cd1473cec84e097Lang Hames SlotIndex NewIndex = MI->isInsideBundle() ? 1529741981adf3a2bc0c6652c9c4ec846250950f3e68Jakob Stoklund Olesen indexes_->getInstructionIndex(MI) : 1530ecb50624d1e99596fdb289200cd1473cec84e097Lang Hames indexes_->insertMachineInstrInMaps(MI); 1531ecb50624d1e99596fdb289200cd1473cec84e097Lang Hames assert(getMBBStartIdx(MI->getParent()) <= OldIndex && 1532ecb50624d1e99596fdb289200cd1473cec84e097Lang Hames OldIndex < getMBBEndIdx(MI->getParent()) && 15333dc7c5138d219048d69952bead22f75efb984fa3Lang Hames "Cannot handle moves across basic block boundaries."); 1534ecb50624d1e99596fdb289200cd1473cec84e097Lang Hames assert(!MI->isBundled() && "Can't handle bundled instructions yet."); 15353dc7c5138d219048d69952bead22f75efb984fa3Lang Hames 1536ecb50624d1e99596fdb289200cd1473cec84e097Lang Hames HMEditor HME(*this, *mri_, *tri_, NewIndex); 15374586d257abf13b57d115d6bac9fb38ddc811acafLang Hames HME.moveAllRangesFrom(MI, OldIndex); 15384586d257abf13b57d115d6bac9fb38ddc811acafLang Hames} 15394586d257abf13b57d115d6bac9fb38ddc811acafLang Hames 15404586d257abf13b57d115d6bac9fb38ddc811acafLang Hamesvoid LiveIntervals::handleMoveIntoBundle(MachineInstr* MI, MachineInstr* BundleStart) { 15414586d257abf13b57d115d6bac9fb38ddc811acafLang Hames SlotIndex NewIndex = indexes_->getInstructionIndex(BundleStart); 15424586d257abf13b57d115d6bac9fb38ddc811acafLang Hames HMEditor HME(*this, *mri_, *tri_, NewIndex); 15434586d257abf13b57d115d6bac9fb38ddc811acafLang Hames HME.moveAllRangesInto(MI, BundleStart); 15443dc7c5138d219048d69952bead22f75efb984fa3Lang Hames} 1545