LiveIntervalAnalysis.cpp revision 741981adf3a2bc0c6652c9c4ec846250950f3e68
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 19063e6a488cb6c29983415221719d05fbf99e00193Jakob Stoklund Olesen // Make sure the first definition is not a partial redefinition. Add an 19163e6a488cb6c29983415221719d05fbf99e00193Jakob Stoklund Olesen // <imp-def> of the full register. 192b0e1bc7b99809e2b45726affd73f72c60c506ea0Jakob Stoklund Olesen // FIXME: LiveIntervals shouldn't modify the code like this. Whoever 193b0e1bc7b99809e2b45726affd73f72c60c506ea0Jakob Stoklund Olesen // created the machine instruction should annotate it with <undef> flags 194b0e1bc7b99809e2b45726affd73f72c60c506ea0Jakob Stoklund Olesen // as needed. Then we can simply assert here. The REG_SEQUENCE lowering 195b0e1bc7b99809e2b45726affd73f72c60c506ea0Jakob Stoklund Olesen // is the main suspect. 1967016cf66ee21ddf3f7823d4e332b2cb84953bebdJakob Stoklund Olesen if (MO.getSubReg()) { 19763e6a488cb6c29983415221719d05fbf99e00193Jakob Stoklund Olesen mi->addRegisterDefined(interval.reg); 1987016cf66ee21ddf3f7823d4e332b2cb84953bebdJakob Stoklund Olesen // Mark all defs of interval.reg on this instruction as reading <undef>. 1997016cf66ee21ddf3f7823d4e332b2cb84953bebdJakob Stoklund Olesen for (unsigned i = MOIdx, e = mi->getNumOperands(); i != e; ++i) { 2007016cf66ee21ddf3f7823d4e332b2cb84953bebdJakob Stoklund Olesen MachineOperand &MO2 = mi->getOperand(i); 2017016cf66ee21ddf3f7823d4e332b2cb84953bebdJakob Stoklund Olesen if (MO2.isReg() && MO2.getReg() == interval.reg && MO2.getSubReg()) 2027016cf66ee21ddf3f7823d4e332b2cb84953bebdJakob Stoklund Olesen MO2.setIsUndef(); 2037016cf66ee21ddf3f7823d4e332b2cb84953bebdJakob Stoklund Olesen } 2047016cf66ee21ddf3f7823d4e332b2cb84953bebdJakob Stoklund Olesen } 20563e6a488cb6c29983415221719d05fbf99e00193Jakob Stoklund Olesen 2063b1088a2cc15a39c7a7b8dd95a56143f1dda6863Jakob Stoklund Olesen VNInfo *ValNo = interval.getNextValue(defIndex, VNInfoAllocator); 2077ecb38be0a533e7b9c7d3b8e9b5c8a6fa5f6b349Evan Cheng assert(ValNo->id == 0 && "First value in interval is not 0?"); 2081a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos 2091a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // Loop over all of the blocks that the vreg is defined in. There are 2101a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // two cases we have to handle here. The most common case is a vreg 2111a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // whose lifetime is contained within a basic block. In this case there 2121a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // will be a single kill, in MBB, which comes after the definition. 2131a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos if (vi.Kills.size() == 1 && vi.Kills[0]->getParent() == mbb) { 2141a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // FIXME: what about dead vars? 215233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames SlotIndex killIdx; 2161a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos if (vi.Kills[0] != mi) 2172debd48ca790ac01be6e12e094fdf4fdcadc8364Jakob Stoklund Olesen killIdx = getInstructionIndex(vi.Kills[0]).getRegSlot(); 2181a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos else 2192debd48ca790ac01be6e12e094fdf4fdcadc8364Jakob Stoklund Olesen killIdx = defIndex.getDeadSlot(); 2201a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos 2211a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // If the kill happens after the definition, we have an intra-block 2221a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // live range. 2231a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos if (killIdx > defIndex) { 224493a3d015cbb2bcc18d9293a4dec3b35c7493818Jeffrey Yasskin assert(vi.AliveBlocks.empty() && 2251a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos "Shouldn't be alive across any blocks!"); 2267ecb38be0a533e7b9c7d3b8e9b5c8a6fa5f6b349Evan Cheng LiveRange LR(defIndex, killIdx, ValNo); 2271a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos interval.addRange(LR); 2288a34229dcf484739119857988772572ef0cad9f2David Greene DEBUG(dbgs() << " +" << LR << "\n"); 2291a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos return; 2301a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos } 2311a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos } 2326097d13b2a624048dbe02e39e2dfb23bfa269b64Chris Lattner 2331a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // The other case we handle is when a virtual register lives to the end 2341a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // of the defining block, potentially live across some blocks, then is 2351a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // live into some number of blocks, but gets killed. Start by adding a 2361a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // range that goes from this definition to the end of the defining block. 23774ab5eeffbd70f2387338e3ee8195be9f73e6dd8Lang Hames LiveRange NewLR(defIndex, getMBBEndIdx(mbb), ValNo); 2388a34229dcf484739119857988772572ef0cad9f2David Greene DEBUG(dbgs() << " +" << NewLR); 2391a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos interval.addRange(NewLR); 2401a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos 241dcfe5f30b5e262971f601a65bebcc0367fef56c5Jakob Stoklund Olesen bool PHIJoin = lv_->isPHIJoin(interval.reg); 242dcfe5f30b5e262971f601a65bebcc0367fef56c5Jakob Stoklund Olesen 243dcfe5f30b5e262971f601a65bebcc0367fef56c5Jakob Stoklund Olesen if (PHIJoin) { 244dcfe5f30b5e262971f601a65bebcc0367fef56c5Jakob Stoklund Olesen // A phi join register is killed at the end of the MBB and revived as a new 245dcfe5f30b5e262971f601a65bebcc0367fef56c5Jakob Stoklund Olesen // valno in the killing blocks. 246dcfe5f30b5e262971f601a65bebcc0367fef56c5Jakob Stoklund Olesen assert(vi.AliveBlocks.empty() && "Phi join can't pass through blocks"); 247dcfe5f30b5e262971f601a65bebcc0367fef56c5Jakob Stoklund Olesen DEBUG(dbgs() << " phi-join"); 248dcfe5f30b5e262971f601a65bebcc0367fef56c5Jakob Stoklund Olesen ValNo->setHasPHIKill(true); 249dcfe5f30b5e262971f601a65bebcc0367fef56c5Jakob Stoklund Olesen } else { 250dcfe5f30b5e262971f601a65bebcc0367fef56c5Jakob Stoklund Olesen // Iterate over all of the blocks that the variable is completely 251dcfe5f30b5e262971f601a65bebcc0367fef56c5Jakob Stoklund Olesen // live in, adding [insrtIndex(begin), instrIndex(end)+4) to the 252dcfe5f30b5e262971f601a65bebcc0367fef56c5Jakob Stoklund Olesen // live interval. 253dcfe5f30b5e262971f601a65bebcc0367fef56c5Jakob Stoklund Olesen for (SparseBitVector<>::iterator I = vi.AliveBlocks.begin(), 254dcfe5f30b5e262971f601a65bebcc0367fef56c5Jakob Stoklund Olesen E = vi.AliveBlocks.end(); I != E; ++I) { 255dcfe5f30b5e262971f601a65bebcc0367fef56c5Jakob Stoklund Olesen MachineBasicBlock *aliveBlock = mf_->getBlockNumbered(*I); 256dcfe5f30b5e262971f601a65bebcc0367fef56c5Jakob Stoklund Olesen LiveRange LR(getMBBStartIdx(aliveBlock), getMBBEndIdx(aliveBlock), ValNo); 257dcfe5f30b5e262971f601a65bebcc0367fef56c5Jakob Stoklund Olesen interval.addRange(LR); 258dcfe5f30b5e262971f601a65bebcc0367fef56c5Jakob Stoklund Olesen DEBUG(dbgs() << " +" << LR); 259dcfe5f30b5e262971f601a65bebcc0367fef56c5Jakob Stoklund Olesen } 2601a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos } 2611a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos 2621a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // Finally, this virtual register is live from the start of any killing 2631a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // block to the 'use' slot of the killing instruction. 2641a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos for (unsigned i = 0, e = vi.Kills.size(); i != e; ++i) { 2651a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos MachineInstr *Kill = vi.Kills[i]; 266dcfe5f30b5e262971f601a65bebcc0367fef56c5Jakob Stoklund Olesen SlotIndex Start = getMBBStartIdx(Kill->getParent()); 2672debd48ca790ac01be6e12e094fdf4fdcadc8364Jakob Stoklund Olesen SlotIndex killIdx = getInstructionIndex(Kill).getRegSlot(); 268dcfe5f30b5e262971f601a65bebcc0367fef56c5Jakob Stoklund Olesen 269dcfe5f30b5e262971f601a65bebcc0367fef56c5Jakob Stoklund Olesen // Create interval with one of a NEW value number. Note that this value 270dcfe5f30b5e262971f601a65bebcc0367fef56c5Jakob Stoklund Olesen // number isn't actually defined by an instruction, weird huh? :) 271dcfe5f30b5e262971f601a65bebcc0367fef56c5Jakob Stoklund Olesen if (PHIJoin) { 2726e2968c85c1e162ee5bc813769eab223e3df0f15Lang Hames assert(getInstructionFromIndex(Start) == 0 && 2736e2968c85c1e162ee5bc813769eab223e3df0f15Lang Hames "PHI def index points at actual instruction."); 2743b1088a2cc15a39c7a7b8dd95a56143f1dda6863Jakob Stoklund Olesen ValNo = interval.getNextValue(Start, VNInfoAllocator); 275dcfe5f30b5e262971f601a65bebcc0367fef56c5Jakob Stoklund Olesen ValNo->setIsPHIDef(true); 276dcfe5f30b5e262971f601a65bebcc0367fef56c5Jakob Stoklund Olesen } 277dcfe5f30b5e262971f601a65bebcc0367fef56c5Jakob Stoklund Olesen LiveRange LR(Start, killIdx, ValNo); 2781a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos interval.addRange(LR); 2798a34229dcf484739119857988772572ef0cad9f2David Greene DEBUG(dbgs() << " +" << LR); 2801a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos } 2811a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos 2821a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos } else { 2833749943648772743c9c0e852553e50e6700a0c1bEvan Cheng if (MultipleDefsBySameMI(*mi, MOIdx)) 284761fd4c1d97977c16de9f0cf921056a37b906304Nick Lewycky // Multiple defs of the same virtual register by the same instruction. 285761fd4c1d97977c16de9f0cf921056a37b906304Nick Lewycky // e.g. %reg1031:5<def>, %reg1031:6<def> = VLD1q16 %reg1024<kill>, ... 286afff40a62da19be15295c0f8ed5d4d450ccb45a5Evan Cheng // This is likely due to elimination of REG_SEQUENCE instructions. Return 287afff40a62da19be15295c0f8ed5d4d450ccb45a5Evan Cheng // here since there is nothing to do. 288afff40a62da19be15295c0f8ed5d4d450ccb45a5Evan Cheng return; 289afff40a62da19be15295c0f8ed5d4d450ccb45a5Evan Cheng 2901a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // If this is the second time we see a virtual register definition, it 2911a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // must be due to phi elimination or two addr elimination. If this is 292bf105c842450d3308d024be203ddd533f37051ecEvan Cheng // the result of two address elimination, then the vreg is one of the 293bf105c842450d3308d024be203ddd533f37051ecEvan Cheng // def-and-use register operand. 2943749943648772743c9c0e852553e50e6700a0c1bEvan Cheng 2953749943648772743c9c0e852553e50e6700a0c1bEvan Cheng // It may also be partial redef like this: 2961b2932024f098a6968645ac78d5848951d877c19Jakob Stoklund Olesen // 80 %reg1041:6<def> = VSHRNv4i16 %reg1034<kill>, 12, pred:14, pred:%reg0 2971b2932024f098a6968645ac78d5848951d877c19Jakob Stoklund Olesen // 120 %reg1041:5<def> = VSHRNv4i16 %reg1039<kill>, 12, pred:14, pred:%reg0 2983749943648772743c9c0e852553e50e6700a0c1bEvan Cheng bool PartReDef = isPartialRedef(MIIdx, MO, interval); 2993749943648772743c9c0e852553e50e6700a0c1bEvan Cheng if (PartReDef || mi->isRegTiedToUseOperand(MOIdx)) { 3001a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // If this is a two-address definition, then we have already processed 3011a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // the live range. The only problem is that we didn't realize there 3021a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // are actually two values in the live interval. Because of this we 3031a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // need to take the LiveRegion that defines this register and split it 3041a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // into two values. 305d14614e6777771f8fec3062bcaf2986c189ac84dJakob Stoklund Olesen SlotIndex RedefIndex = MIIdx.getRegSlot(MO.isEarlyClobber()); 3061a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos 30735f291d2c5f80e8e713704190230064311bbbbbeLang Hames const LiveRange *OldLR = 3082debd48ca790ac01be6e12e094fdf4fdcadc8364Jakob Stoklund Olesen interval.getLiveRangeContaining(RedefIndex.getRegSlot(true)); 3097ecb38be0a533e7b9c7d3b8e9b5c8a6fa5f6b349Evan Cheng VNInfo *OldValNo = OldLR->valno; 3102debd48ca790ac01be6e12e094fdf4fdcadc8364Jakob Stoklund Olesen SlotIndex DefIndex = OldValNo->def.getRegSlot(); 3114f8ff168de12eabdeb4b9437bf9402489ecf85cbEvan Cheng 312c66d0f2a9386cc7cb3237b8e3cace2b62a9c7dc8Jakob Stoklund Olesen // Delete the previous value, which should be short and continuous, 313be4f88a8b8bb3311e0dc4cde8533763d7923c3eaChris Lattner // because the 2-addr copy must be in the same MBB as the redef. 3141a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos interval.removeRange(DefIndex, RedefIndex); 315706515727c6d024015fffded2b3109a4f0ac5299Alkis Evlogimenos 31691725b75852443923b419fd23215194cfc65dd88Chris Lattner // The new value number (#1) is defined by the instruction we claimed 31791725b75852443923b419fd23215194cfc65dd88Chris Lattner // defined value #0. 3186e2968c85c1e162ee5bc813769eab223e3df0f15Lang Hames VNInfo *ValNo = interval.createValueCopy(OldValNo, VNInfoAllocator); 319857c4e01f85601cf2084adb860616256ee47c177Lang Hames 32091725b75852443923b419fd23215194cfc65dd88Chris Lattner // Value#0 is now defined by the 2-addr instruction. 3213b1088a2cc15a39c7a7b8dd95a56143f1dda6863Jakob Stoklund Olesen OldValNo->def = RedefIndex; 3221b2932024f098a6968645ac78d5848951d877c19Jakob Stoklund Olesen 323be4f88a8b8bb3311e0dc4cde8533763d7923c3eaChris Lattner // Add the new live interval which replaces the range for the input copy. 324be4f88a8b8bb3311e0dc4cde8533763d7923c3eaChris Lattner LiveRange LR(DefIndex, RedefIndex, ValNo); 3258a34229dcf484739119857988772572ef0cad9f2David Greene DEBUG(dbgs() << " replace range with " << LR); 3261a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos interval.addRange(LR); 3271a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos 3281a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // If this redefinition is dead, we need to add a dummy unit live 3291a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // range covering the def slot. 3306b098dee286cc6fe5a5a476464d92dec5602e406Owen Anderson if (MO.isDead()) 3312debd48ca790ac01be6e12e094fdf4fdcadc8364Jakob Stoklund Olesen interval.addRange(LiveRange(RedefIndex, RedefIndex.getDeadSlot(), 332233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames OldValNo)); 3331a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos 3348e6179fb134af929ee7c937c82d9dc1c9a104c5fBill Wendling DEBUG({ 3358a34229dcf484739119857988772572ef0cad9f2David Greene dbgs() << " RESULT: "; 3368a34229dcf484739119857988772572ef0cad9f2David Greene interval.print(dbgs(), tri_); 3378e6179fb134af929ee7c937c82d9dc1c9a104c5fBill Wendling }); 3383749943648772743c9c0e852553e50e6700a0c1bEvan Cheng } else if (lv_->isPHIJoin(interval.reg)) { 3391a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // In the case of PHI elimination, each variable definition is only 3401a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // live until the end of the block. We've already taken care of the 3411a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // rest of the live range. 342dcfe5f30b5e262971f601a65bebcc0367fef56c5Jakob Stoklund Olesen 3432debd48ca790ac01be6e12e094fdf4fdcadc8364Jakob Stoklund Olesen SlotIndex defIndex = MIIdx.getRegSlot(); 344fb11288109329cb736d9f49769581a0d0c23fe19Evan Cheng if (MO.isEarlyClobber()) 3452debd48ca790ac01be6e12e094fdf4fdcadc8364Jakob Stoklund Olesen defIndex = MIIdx.getRegSlot(true); 346752195e3c662c6b5db042cf897c984624720f3b8Evan Cheng 3473b1088a2cc15a39c7a7b8dd95a56143f1dda6863Jakob Stoklund Olesen VNInfo *ValNo = interval.getNextValue(defIndex, VNInfoAllocator); 3481b2932024f098a6968645ac78d5848951d877c19Jakob Stoklund Olesen 34974ab5eeffbd70f2387338e3ee8195be9f73e6dd8Lang Hames SlotIndex killIndex = getMBBEndIdx(mbb); 3507ecb38be0a533e7b9c7d3b8e9b5c8a6fa5f6b349Evan Cheng LiveRange LR(defIndex, killIndex, ValNo); 3511a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos interval.addRange(LR); 352857c4e01f85601cf2084adb860616256ee47c177Lang Hames ValNo->setHasPHIKill(true); 353dcfe5f30b5e262971f601a65bebcc0367fef56c5Jakob Stoklund Olesen DEBUG(dbgs() << " phi-join +" << LR); 3543749943648772743c9c0e852553e50e6700a0c1bEvan Cheng } else { 3553749943648772743c9c0e852553e50e6700a0c1bEvan Cheng llvm_unreachable("Multiply defined register"); 356dd2cc65f34f9b7bfda1cd0c42becedfc361d46f8Alkis Evlogimenos } 3571a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos } 358ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos 3598a34229dcf484739119857988772572ef0cad9f2David Greene DEBUG(dbgs() << '\n'); 360ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos} 361ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos 362af8b34dae90fd6d146a3b4a83b50751ed21f07c8Lang Hamesstatic bool isRegLiveIntoSuccessor(const MachineBasicBlock *MBB, unsigned Reg) { 363342c64c90418a97ec26303c27d1829edd994d9a9Lang Hames for (MachineBasicBlock::const_succ_iterator SI = MBB->succ_begin(), 364342c64c90418a97ec26303c27d1829edd994d9a9Lang Hames SE = MBB->succ_end(); 365342c64c90418a97ec26303c27d1829edd994d9a9Lang Hames SI != SE; ++SI) { 366342c64c90418a97ec26303c27d1829edd994d9a9Lang Hames const MachineBasicBlock* succ = *SI; 367342c64c90418a97ec26303c27d1829edd994d9a9Lang Hames if (succ->isLiveIn(Reg)) 368342c64c90418a97ec26303c27d1829edd994d9a9Lang Hames return true; 369342c64c90418a97ec26303c27d1829edd994d9a9Lang Hames } 370342c64c90418a97ec26303c27d1829edd994d9a9Lang Hames return false; 371342c64c90418a97ec26303c27d1829edd994d9a9Lang Hames} 372342c64c90418a97ec26303c27d1829edd994d9a9Lang Hames 373f35fef7060c465dd7b578bf6339a18e8a8911888Chris Lattnervoid LiveIntervals::handlePhysicalRegisterDef(MachineBasicBlock *MBB, 374ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos MachineBasicBlock::iterator mi, 375233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames SlotIndex MIIdx, 3766b098dee286cc6fe5a5a476464d92dec5602e406Owen Anderson MachineOperand& MO, 3773b1088a2cc15a39c7a7b8dd95a56143f1dda6863Jakob Stoklund Olesen LiveInterval &interval) { 3784314268128be6d54c9a7f0709680e5a5b40f3ab3Jakob Stoklund Olesen DEBUG(dbgs() << "\t\tregister: " << PrintReg(interval.reg, tri_)); 3791a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos 380233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames SlotIndex baseIndex = MIIdx; 381d14614e6777771f8fec3062bcaf2986c189ac84dJakob Stoklund Olesen SlotIndex start = baseIndex.getRegSlot(MO.isEarlyClobber()); 382233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames SlotIndex end = start; 3831a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos 3841a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // If it is not used after definition, it is considered dead at 3851a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // the instruction defining it. Hence its interval is: 3861a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // [defSlot(def), defSlot(def)+1) 38739faac2531268b8555475796c6071556670dc290Dale Johannesen // For earlyclobbers, the defSlot was pushed back one; the extra 38839faac2531268b8555475796c6071556670dc290Dale Johannesen // advance below compensates. 3896b098dee286cc6fe5a5a476464d92dec5602e406Owen Anderson if (MO.isDead()) { 3908a34229dcf484739119857988772572ef0cad9f2David Greene DEBUG(dbgs() << " dead"); 3912debd48ca790ac01be6e12e094fdf4fdcadc8364Jakob Stoklund Olesen end = start.getDeadSlot(); 392ab4b66d4c279e8cd9e448687020fc838e7881dbcChris Lattner goto exit; 3931a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos } 394ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos 3951a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // If it is not dead on definition, it must be killed by a 3961a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // subsequent instruction. Hence its interval is: 3971a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // [defSlot(def), useSlot(kill)+1) 398233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames baseIndex = baseIndex.getNextIndex(); 3995ab6f5fe666d0e3403d9b777324d1a1999118153Chris Lattner while (++mi != MBB->end()) { 400233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames 401bd63520161629385ff5a0b037eccc770d8d15289Dale Johannesen if (mi->isDebugValue()) 402bd63520161629385ff5a0b037eccc770d8d15289Dale Johannesen continue; 403233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames if (getInstructionFromIndex(baseIndex) == 0) 404233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames baseIndex = indexes_->getNextNonNullIndex(baseIndex); 405233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames 4066130f66eaae89f8878590796977678afa8448926Evan Cheng if (mi->killsRegister(interval.reg, tri_)) { 4078a34229dcf484739119857988772572ef0cad9f2David Greene DEBUG(dbgs() << " killed"); 4082debd48ca790ac01be6e12e094fdf4fdcadc8364Jakob Stoklund Olesen end = baseIndex.getRegSlot(); 409ab4b66d4c279e8cd9e448687020fc838e7881dbcChris Lattner goto exit; 410c45288e06bfe7d0b0e74eff350d280fa6c944373Evan Cheng } else { 4111015ba7018c87f48cc7bb45a564eb4a27241e76aEvan Cheng int DefIdx = mi->findRegisterDefOperandIdx(interval.reg,false,false,tri_); 412c45288e06bfe7d0b0e74eff350d280fa6c944373Evan Cheng if (DefIdx != -1) { 413c45288e06bfe7d0b0e74eff350d280fa6c944373Evan Cheng if (mi->isRegTiedToUseOperand(DefIdx)) { 414c45288e06bfe7d0b0e74eff350d280fa6c944373Evan Cheng // Two-address instruction. 4157e899cbb9127c02c58f6e774186a533b0d00681dJakob Stoklund Olesen end = baseIndex.getRegSlot(mi->getOperand(DefIdx).isEarlyClobber()); 416c45288e06bfe7d0b0e74eff350d280fa6c944373Evan Cheng } else { 417c45288e06bfe7d0b0e74eff350d280fa6c944373Evan Cheng // Another instruction redefines the register before it is ever read. 418bd63520161629385ff5a0b037eccc770d8d15289Dale Johannesen // Then the register is essentially dead at the instruction that 419bd63520161629385ff5a0b037eccc770d8d15289Dale Johannesen // defines it. Hence its interval is: 420c45288e06bfe7d0b0e74eff350d280fa6c944373Evan Cheng // [defSlot(def), defSlot(def)+1) 4218a34229dcf484739119857988772572ef0cad9f2David Greene DEBUG(dbgs() << " dead"); 4222debd48ca790ac01be6e12e094fdf4fdcadc8364Jakob Stoklund Olesen end = start.getDeadSlot(); 423c45288e06bfe7d0b0e74eff350d280fa6c944373Evan Cheng } 424c45288e06bfe7d0b0e74eff350d280fa6c944373Evan Cheng goto exit; 425c45288e06bfe7d0b0e74eff350d280fa6c944373Evan Cheng } 426f35fef7060c465dd7b578bf6339a18e8a8911888Chris Lattner } 4271b2932024f098a6968645ac78d5848951d877c19Jakob Stoklund Olesen 428233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames baseIndex = baseIndex.getNextIndex(); 4291a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos } 4301b2932024f098a6968645ac78d5848951d877c19Jakob Stoklund Olesen 431342c64c90418a97ec26303c27d1829edd994d9a9Lang Hames // If we get here the register *should* be live out. 432342c64c90418a97ec26303c27d1829edd994d9a9Lang Hames assert(!isAllocatable(interval.reg) && "Physregs shouldn't be live out!"); 43302ba13c9897ae2b19f9201e57460d7ee2b753a0bAlkis Evlogimenos 434342c64c90418a97ec26303c27d1829edd994d9a9Lang Hames // FIXME: We need saner rules for reserved regs. 435342c64c90418a97ec26303c27d1829edd994d9a9Lang Hames if (isReserved(interval.reg)) { 436342c64c90418a97ec26303c27d1829edd994d9a9Lang Hames end = start.getDeadSlot(); 437342c64c90418a97ec26303c27d1829edd994d9a9Lang Hames } else { 438342c64c90418a97ec26303c27d1829edd994d9a9Lang Hames // Unreserved, unallocable registers like EFLAGS can be live across basic 439342c64c90418a97ec26303c27d1829edd994d9a9Lang Hames // block boundaries. 440af8b34dae90fd6d146a3b4a83b50751ed21f07c8Lang Hames assert(isRegLiveIntoSuccessor(MBB, interval.reg) && 441af8b34dae90fd6d146a3b4a83b50751ed21f07c8Lang Hames "Unreserved reg not live-out?"); 442342c64c90418a97ec26303c27d1829edd994d9a9Lang Hames end = getMBBEndIdx(MBB); 443342c64c90418a97ec26303c27d1829edd994d9a9Lang Hames } 444ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenosexit: 4451a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos assert(start < end && "did not find end of interval?"); 446f768bba43f5c036039851d2fcca8212edca18467Chris Lattner 44724a3cc4c83e5edb25fadf7b8979a26b4451795c6Evan Cheng // Already exists? Extend old live interval. 44831cc3ec3308c8fafd9865388214ae11662a71af4Jakob Stoklund Olesen VNInfo *ValNo = interval.getVNInfoAt(start); 44931cc3ec3308c8fafd9865388214ae11662a71af4Jakob Stoklund Olesen bool Extend = ValNo != 0; 45031cc3ec3308c8fafd9865388214ae11662a71af4Jakob Stoklund Olesen if (!Extend) 4513b1088a2cc15a39c7a7b8dd95a56143f1dda6863Jakob Stoklund Olesen ValNo = interval.getNextValue(start, VNInfoAllocator); 4527ecb38be0a533e7b9c7d3b8e9b5c8a6fa5f6b349Evan Cheng LiveRange LR(start, end, ValNo); 4531a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos interval.addRange(LR); 4548a34229dcf484739119857988772572ef0cad9f2David Greene DEBUG(dbgs() << " +" << LR << '\n'); 455ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos} 456ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos 457f35fef7060c465dd7b578bf6339a18e8a8911888Chris Lattnervoid LiveIntervals::handleRegisterDef(MachineBasicBlock *MBB, 458f35fef7060c465dd7b578bf6339a18e8a8911888Chris Lattner MachineBasicBlock::iterator MI, 459233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames SlotIndex MIIdx, 460ef0732d25a9882c947984ae3f2afbef5463ba00fEvan Cheng MachineOperand& MO, 461ef0732d25a9882c947984ae3f2afbef5463ba00fEvan Cheng unsigned MOIdx) { 4626b098dee286cc6fe5a5a476464d92dec5602e406Owen Anderson if (TargetRegisterInfo::isVirtualRegister(MO.getReg())) 463ef0732d25a9882c947984ae3f2afbef5463ba00fEvan Cheng handleVirtualRegisterDef(MBB, MI, MIIdx, MO, MOIdx, 4646b098dee286cc6fe5a5a476464d92dec5602e406Owen Anderson getOrCreateInterval(MO.getReg())); 4653b1088a2cc15a39c7a7b8dd95a56143f1dda6863Jakob Stoklund Olesen else 466c45288e06bfe7d0b0e74eff350d280fa6c944373Evan Cheng handlePhysicalRegisterDef(MBB, MI, MIIdx, MO, 4673b1088a2cc15a39c7a7b8dd95a56143f1dda6863Jakob Stoklund Olesen getOrCreateInterval(MO.getReg())); 4684d46e1e521c0df1990ea50f8146d22bd77ea71a6Alkis Evlogimenos} 4694d46e1e521c0df1990ea50f8146d22bd77ea71a6Alkis Evlogimenos 470b371f457b0ea4a652a9f526ba4375c80ae542252Evan Chengvoid LiveIntervals::handleLiveInRegister(MachineBasicBlock *MBB, 471233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames SlotIndex MIIdx, 4724465b6f6b2ebd061f4f321e666b47d540651f686Lang Hames LiveInterval &interval) { 473342c64c90418a97ec26303c27d1829edd994d9a9Lang Hames assert(TargetRegisterInfo::isPhysicalRegister(interval.reg) && 474342c64c90418a97ec26303c27d1829edd994d9a9Lang Hames "Only physical registers can be live in."); 475342c64c90418a97ec26303c27d1829edd994d9a9Lang Hames assert((!isAllocatable(interval.reg) || MBB->getParent()->begin() || 476342c64c90418a97ec26303c27d1829edd994d9a9Lang Hames MBB->isLandingPad()) && 477342c64c90418a97ec26303c27d1829edd994d9a9Lang Hames "Allocatable live-ins only valid for entry blocks and landing pads."); 478342c64c90418a97ec26303c27d1829edd994d9a9Lang Hames 4794314268128be6d54c9a7f0709680e5a5b40f3ab3Jakob Stoklund Olesen DEBUG(dbgs() << "\t\tlivein register: " << PrintReg(interval.reg, tri_)); 480b371f457b0ea4a652a9f526ba4375c80ae542252Evan Cheng 481b371f457b0ea4a652a9f526ba4375c80ae542252Evan Cheng // Look for kills, if it reaches a def before it's killed, then it shouldn't 482b371f457b0ea4a652a9f526ba4375c80ae542252Evan Cheng // be considered a livein. 483b371f457b0ea4a652a9f526ba4375c80ae542252Evan Cheng MachineBasicBlock::iterator mi = MBB->begin(); 4844507f089d48c5adb454cd12b68333d5590ce05ddEvan Cheng MachineBasicBlock::iterator E = MBB->end(); 4854507f089d48c5adb454cd12b68333d5590ce05ddEvan Cheng // Skip over DBG_VALUE at the start of the MBB. 4864507f089d48c5adb454cd12b68333d5590ce05ddEvan Cheng if (mi != E && mi->isDebugValue()) { 4874507f089d48c5adb454cd12b68333d5590ce05ddEvan Cheng while (++mi != E && mi->isDebugValue()) 4884507f089d48c5adb454cd12b68333d5590ce05ddEvan Cheng ; 4894507f089d48c5adb454cd12b68333d5590ce05ddEvan Cheng if (mi == E) 4904507f089d48c5adb454cd12b68333d5590ce05ddEvan Cheng // MBB is empty except for DBG_VALUE's. 4914507f089d48c5adb454cd12b68333d5590ce05ddEvan Cheng return; 4924507f089d48c5adb454cd12b68333d5590ce05ddEvan Cheng } 4934507f089d48c5adb454cd12b68333d5590ce05ddEvan Cheng 494233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames SlotIndex baseIndex = MIIdx; 495233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames SlotIndex start = baseIndex; 496233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames if (getInstructionFromIndex(baseIndex) == 0) 497233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames baseIndex = indexes_->getNextNonNullIndex(baseIndex); 498233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames 499233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames SlotIndex end = baseIndex; 5000076c616e8abc2ecf36600a7ac20ec784420cdc4Evan Cheng bool SeenDefUse = false; 501b371f457b0ea4a652a9f526ba4375c80ae542252Evan Cheng 502bd63520161629385ff5a0b037eccc770d8d15289Dale Johannesen while (mi != E) { 5031d0aeabe3fce2ce6610e988b36582b47a7684f74Dale Johannesen if (mi->killsRegister(interval.reg, tri_)) { 5041d0aeabe3fce2ce6610e988b36582b47a7684f74Dale Johannesen DEBUG(dbgs() << " killed"); 5052debd48ca790ac01be6e12e094fdf4fdcadc8364Jakob Stoklund Olesen end = baseIndex.getRegSlot(); 5061d0aeabe3fce2ce6610e988b36582b47a7684f74Dale Johannesen SeenDefUse = true; 5071d0aeabe3fce2ce6610e988b36582b47a7684f74Dale Johannesen break; 5086b7913893bcd47f52eff71e39e50c42511c4ed36Jakob Stoklund Olesen } else if (mi->modifiesRegister(interval.reg, tri_)) { 5091d0aeabe3fce2ce6610e988b36582b47a7684f74Dale Johannesen // Another instruction redefines the register before it is ever read. 5101d0aeabe3fce2ce6610e988b36582b47a7684f74Dale Johannesen // Then the register is essentially dead at the instruction that defines 5111d0aeabe3fce2ce6610e988b36582b47a7684f74Dale Johannesen // it. Hence its interval is: 5121d0aeabe3fce2ce6610e988b36582b47a7684f74Dale Johannesen // [defSlot(def), defSlot(def)+1) 5131d0aeabe3fce2ce6610e988b36582b47a7684f74Dale Johannesen DEBUG(dbgs() << " dead"); 5142debd48ca790ac01be6e12e094fdf4fdcadc8364Jakob Stoklund Olesen end = start.getDeadSlot(); 5151d0aeabe3fce2ce6610e988b36582b47a7684f74Dale Johannesen SeenDefUse = true; 5161d0aeabe3fce2ce6610e988b36582b47a7684f74Dale Johannesen break; 517bd63520161629385ff5a0b037eccc770d8d15289Dale Johannesen } 5181d0aeabe3fce2ce6610e988b36582b47a7684f74Dale Johannesen 5194507f089d48c5adb454cd12b68333d5590ce05ddEvan Cheng while (++mi != E && mi->isDebugValue()) 5204507f089d48c5adb454cd12b68333d5590ce05ddEvan Cheng // Skip over DBG_VALUE. 5214507f089d48c5adb454cd12b68333d5590ce05ddEvan Cheng ; 5224507f089d48c5adb454cd12b68333d5590ce05ddEvan Cheng if (mi != E) 523233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames baseIndex = indexes_->getNextNonNullIndex(baseIndex); 524b371f457b0ea4a652a9f526ba4375c80ae542252Evan Cheng } 525b371f457b0ea4a652a9f526ba4375c80ae542252Evan Cheng 52675611fb4e6ab253be30ac29a2b15e9bf8c1d146eEvan Cheng // Live-in register might not be used at all. 5270076c616e8abc2ecf36600a7ac20ec784420cdc4Evan Cheng if (!SeenDefUse) { 528af8b34dae90fd6d146a3b4a83b50751ed21f07c8Lang Hames if (isAllocatable(interval.reg) || 529af8b34dae90fd6d146a3b4a83b50751ed21f07c8Lang Hames !isRegLiveIntoSuccessor(MBB, interval.reg)) { 530af8b34dae90fd6d146a3b4a83b50751ed21f07c8Lang Hames // Allocatable registers are never live through. 531af8b34dae90fd6d146a3b4a83b50751ed21f07c8Lang Hames // Non-allocatable registers that aren't live into any successors also 532af8b34dae90fd6d146a3b4a83b50751ed21f07c8Lang Hames // aren't live through. 533342c64c90418a97ec26303c27d1829edd994d9a9Lang Hames DEBUG(dbgs() << " dead"); 534f58e37f957191a3e41f605628c6169fbb1d4f922Lang Hames return; 535342c64c90418a97ec26303c27d1829edd994d9a9Lang Hames } else { 536af8b34dae90fd6d146a3b4a83b50751ed21f07c8Lang Hames // If we get here the register is non-allocatable and live into some 537af8b34dae90fd6d146a3b4a83b50751ed21f07c8Lang Hames // successor. We'll conservatively assume it's live-through. 538342c64c90418a97ec26303c27d1829edd994d9a9Lang Hames DEBUG(dbgs() << " live through"); 539342c64c90418a97ec26303c27d1829edd994d9a9Lang Hames end = getMBBEndIdx(MBB); 540342c64c90418a97ec26303c27d1829edd994d9a9Lang Hames } 54124a3cc4c83e5edb25fadf7b8979a26b4451795c6Evan Cheng } 54224a3cc4c83e5edb25fadf7b8979a26b4451795c6Evan Cheng 5436e2968c85c1e162ee5bc813769eab223e3df0f15Lang Hames SlotIndex defIdx = getMBBStartIdx(MBB); 5446e2968c85c1e162ee5bc813769eab223e3df0f15Lang Hames assert(getInstructionFromIndex(defIdx) == 0 && 5456e2968c85c1e162ee5bc813769eab223e3df0f15Lang Hames "PHI def index points at actual instruction."); 5463b1088a2cc15a39c7a7b8dd95a56143f1dda6863Jakob Stoklund Olesen VNInfo *vni = interval.getNextValue(defIdx, VNInfoAllocator); 547d21c31610c4a10e9e638f4221b5df89ea932e258Lang Hames vni->setIsPHIDef(true); 548d21c31610c4a10e9e638f4221b5df89ea932e258Lang Hames LiveRange LR(start, end, vni); 5493de23e6f6cf337451a0934159da494d645b93133Jakob Stoklund Olesen 5509b25b8ca24d6df2e097741dcc15016772ee4eda7Jim Laskey interval.addRange(LR); 5518a34229dcf484739119857988772572ef0cad9f2David Greene DEBUG(dbgs() << " +" << LR << '\n'); 552b371f457b0ea4a652a9f526ba4375c80ae542252Evan Cheng} 553b371f457b0ea4a652a9f526ba4375c80ae542252Evan Cheng 554ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos/// computeIntervals - computes the live intervals for virtual 5554d46e1e521c0df1990ea50f8146d22bd77ea71a6Alkis Evlogimenos/// registers. for some ordering of the machine instructions [1,N] a 55608cec00588ec1a8fa85b208555f006d7396ae7a4Alkis Evlogimenos/// live interval is an interval [i, j) where 1 <= i <= j < N for 557ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos/// which a variable is live 5581b2932024f098a6968645ac78d5848951d877c19Jakob Stoklund Olesenvoid LiveIntervals::computeIntervals() { 5598a34229dcf484739119857988772572ef0cad9f2David Greene DEBUG(dbgs() << "********** COMPUTING LIVE INTERVALS **********\n" 5608e6179fb134af929ee7c937c82d9dc1c9a104c5fBill Wendling << "********** Function: " 5618e6179fb134af929ee7c937c82d9dc1c9a104c5fBill Wendling << ((Value*)mf_->getFunction())->getName() << '\n'); 562d129d73b725e32d2fc0c87f392c239db8801e922Evan Cheng 56334e85d0307e3c17e5061622dccf8a20e5457b099Jakob Stoklund Olesen RegMaskBlocks.resize(mf_->getNumBlockIDs()); 56434e85d0307e3c17e5061622dccf8a20e5457b099Jakob Stoklund Olesen 565d129d73b725e32d2fc0c87f392c239db8801e922Evan Cheng SmallVector<unsigned, 8> UndefUses; 566428b92eb83b457b71d29d1d4b7900d36a0ce9a53Chris Lattner for (MachineFunction::iterator MBBI = mf_->begin(), E = mf_->end(); 567428b92eb83b457b71d29d1d4b7900d36a0ce9a53Chris Lattner MBBI != E; ++MBBI) { 568428b92eb83b457b71d29d1d4b7900d36a0ce9a53Chris Lattner MachineBasicBlock *MBB = MBBI; 56934e85d0307e3c17e5061622dccf8a20e5457b099Jakob Stoklund Olesen RegMaskBlocks[MBB->getNumber()].first = RegMaskSlots.size(); 57034e85d0307e3c17e5061622dccf8a20e5457b099Jakob Stoklund Olesen 57100a99a35840451a291eb61a192a750908a4073aeEvan Cheng if (MBB->empty()) 57200a99a35840451a291eb61a192a750908a4073aeEvan Cheng continue; 57300a99a35840451a291eb61a192a750908a4073aeEvan Cheng 574134eb73fc35e6ead3cfd3ed5024d0d7efa507441Owen Anderson // Track the index of the current machine instr. 575233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames SlotIndex MIIndex = getMBBStartIdx(MBB); 576ad98f795d0dba3db721139a8a74a98acdce0ff60Bob Wilson DEBUG(dbgs() << "BB#" << MBB->getNumber() 577ad98f795d0dba3db721139a8a74a98acdce0ff60Bob Wilson << ":\t\t# derived from " << MBB->getName() << "\n"); 5781a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos 579cb406c25973b4e88a6c10ad839ef1beeb3664715Dan Gohman // Create intervals for live-ins to this BB first. 58081bf03eb5cd68243eabb52505105aa5f4a831bf3Dan Gohman for (MachineBasicBlock::livein_iterator LI = MBB->livein_begin(), 581cb406c25973b4e88a6c10ad839ef1beeb3664715Dan Gohman LE = MBB->livein_end(); LI != LE; ++LI) { 582cb406c25973b4e88a6c10ad839ef1beeb3664715Dan Gohman handleLiveInRegister(MBB, MIIndex, getOrCreateInterval(*LI)); 583dffb2e83ed2546226d09c40aa43524e2392322daChris Lattner } 5841b2932024f098a6968645ac78d5848951d877c19Jakob Stoklund Olesen 58599500aeb7c9a05db57e228544a3f81de2faf24efOwen Anderson // Skip over empty initial indices. 586233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames if (getInstructionFromIndex(MIIndex) == 0) 587233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames MIIndex = indexes_->getNextNonNullIndex(MIIndex); 5881b2932024f098a6968645ac78d5848951d877c19Jakob Stoklund Olesen 5891caedd056dbc3eda1537ad8251323bd985819b80Dale Johannesen for (MachineBasicBlock::iterator MI = MBB->begin(), miEnd = MBB->end(); 5901caedd056dbc3eda1537ad8251323bd985819b80Dale Johannesen MI != miEnd; ++MI) { 5918a34229dcf484739119857988772572ef0cad9f2David Greene DEBUG(dbgs() << MIIndex << "\t" << *MI); 592518bb53485df640d7b7e3f6b0544099020c42aa7Chris Lattner if (MI->isDebugValue()) 5931caedd056dbc3eda1537ad8251323bd985819b80Dale Johannesen continue; 5943fd3a840c50fe4ede1b200be18990bc955c536fdJakob Stoklund Olesen assert(indexes_->getInstructionFromIndex(MIIndex) == MI && 5953fd3a840c50fe4ede1b200be18990bc955c536fdJakob Stoklund Olesen "Lost SlotIndex synchronization"); 5961a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos 597438f7bc67cf235ccee7e6f7ac7f4ae2186eb8020Evan Cheng // Handle defs. 598428b92eb83b457b71d29d1d4b7900d36a0ce9a53Chris Lattner for (int i = MI->getNumOperands() - 1; i >= 0; --i) { 599428b92eb83b457b71d29d1d4b7900d36a0ce9a53Chris Lattner MachineOperand &MO = MI->getOperand(i); 6003fd3a840c50fe4ede1b200be18990bc955c536fdJakob Stoklund Olesen 6013fd3a840c50fe4ede1b200be18990bc955c536fdJakob Stoklund Olesen // Collect register masks. 6023fd3a840c50fe4ede1b200be18990bc955c536fdJakob Stoklund Olesen if (MO.isRegMask()) { 6033fd3a840c50fe4ede1b200be18990bc955c536fdJakob Stoklund Olesen RegMaskSlots.push_back(MIIndex.getRegSlot()); 6043fd3a840c50fe4ede1b200be18990bc955c536fdJakob Stoklund Olesen RegMaskBits.push_back(MO.getRegMask()); 6053fd3a840c50fe4ede1b200be18990bc955c536fdJakob Stoklund Olesen continue; 6063fd3a840c50fe4ede1b200be18990bc955c536fdJakob Stoklund Olesen } 6073fd3a840c50fe4ede1b200be18990bc955c536fdJakob Stoklund Olesen 608d129d73b725e32d2fc0c87f392c239db8801e922Evan Cheng if (!MO.isReg() || !MO.getReg()) 609d129d73b725e32d2fc0c87f392c239db8801e922Evan Cheng continue; 610d129d73b725e32d2fc0c87f392c239db8801e922Evan Cheng 6111a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // handle register defs - build intervals 612d129d73b725e32d2fc0c87f392c239db8801e922Evan Cheng if (MO.isDef()) 613ef0732d25a9882c947984ae3f2afbef5463ba00fEvan Cheng handleRegisterDef(MBB, MI, MIIndex, MO, i); 614d129d73b725e32d2fc0c87f392c239db8801e922Evan Cheng else if (MO.isUndef()) 615d129d73b725e32d2fc0c87f392c239db8801e922Evan Cheng UndefUses.push_back(MO.getReg()); 6161a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos } 6171b2932024f098a6968645ac78d5848951d877c19Jakob Stoklund Olesen 618233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames // Move to the next instr slot. 619233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames MIIndex = indexes_->getNextNonNullIndex(MIIndex); 620ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos } 62134e85d0307e3c17e5061622dccf8a20e5457b099Jakob Stoklund Olesen 62234e85d0307e3c17e5061622dccf8a20e5457b099Jakob Stoklund Olesen // Compute the number of register mask instructions in this block. 62334e85d0307e3c17e5061622dccf8a20e5457b099Jakob Stoklund Olesen std::pair<unsigned, unsigned> &RMB = RegMaskBlocks[MBB->getNumber()]; 62434e85d0307e3c17e5061622dccf8a20e5457b099Jakob Stoklund Olesen RMB.second = RegMaskSlots.size() - RMB.first;; 6251a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos } 626d129d73b725e32d2fc0c87f392c239db8801e922Evan Cheng 627d129d73b725e32d2fc0c87f392c239db8801e922Evan Cheng // Create empty intervals for registers defined by implicit_def's (except 628d129d73b725e32d2fc0c87f392c239db8801e922Evan Cheng // for those implicit_def that define values which are liveout of their 629d129d73b725e32d2fc0c87f392c239db8801e922Evan Cheng // blocks. 630d129d73b725e32d2fc0c87f392c239db8801e922Evan Cheng for (unsigned i = 0, e = UndefUses.size(); i != e; ++i) { 631d129d73b725e32d2fc0c87f392c239db8801e922Evan Cheng unsigned UndefReg = UndefUses[i]; 632d129d73b725e32d2fc0c87f392c239db8801e922Evan Cheng (void)getOrCreateInterval(UndefReg); 633d129d73b725e32d2fc0c87f392c239db8801e922Evan Cheng } 634ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos} 635b27ef248f579b354aab434f63c417ab1103e47e2Alkis Evlogimenos 63603857b29d8271a23943254579e6cf7b7df4b1bd3Owen AndersonLiveInterval* LiveIntervals::createInterval(unsigned reg) { 6370a1fcce09230e9b4bd30a8f07447aa075dce7470Evan Cheng float Weight = TargetRegisterInfo::isPhysicalRegister(reg) ? HUGE_VALF : 0.0F; 63803857b29d8271a23943254579e6cf7b7df4b1bd3Owen Anderson return new LiveInterval(reg, Weight); 6399a8b490735d216435862a3d52e669357f165550fAlkis Evlogimenos} 640f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng 6410a1fcce09230e9b4bd30a8f07447aa075dce7470Evan Cheng/// dupInterval - Duplicate a live interval. The caller is responsible for 6420a1fcce09230e9b4bd30a8f07447aa075dce7470Evan Cheng/// managing the allocated memory. 6430a1fcce09230e9b4bd30a8f07447aa075dce7470Evan ChengLiveInterval* LiveIntervals::dupInterval(LiveInterval *li) { 6440a1fcce09230e9b4bd30a8f07447aa075dce7470Evan Cheng LiveInterval *NewLI = createInterval(li->reg); 64590f95f88c6ce09c6744777dc9d140c3c77203b92Evan Cheng NewLI->Copy(*li, mri_, getVNInfoAllocator()); 6460a1fcce09230e9b4bd30a8f07447aa075dce7470Evan Cheng return NewLI; 6470a1fcce09230e9b4bd30a8f07447aa075dce7470Evan Cheng} 6480a1fcce09230e9b4bd30a8f07447aa075dce7470Evan Cheng 64911513e5d1e1b40e6113668e4b4357596f33fa6c6Jakob Stoklund Olesen/// shrinkToUses - After removing some uses of a register, shrink its live 65011513e5d1e1b40e6113668e4b4357596f33fa6c6Jakob Stoklund Olesen/// range to just the remaining uses. This method does not compute reaching 65111513e5d1e1b40e6113668e4b4357596f33fa6c6Jakob Stoklund Olesen/// defs for new uses, and it doesn't remove dead defs. 6526a3dbd3b25bbc99bd1a233d6a74ddea3493ba6acJakob Stoklund Olesenbool LiveIntervals::shrinkToUses(LiveInterval *li, 6530d8ccaa5c8db820b5b93f37e51563148c57ba6b8Jakob Stoklund Olesen SmallVectorImpl<MachineInstr*> *dead) { 65411513e5d1e1b40e6113668e4b4357596f33fa6c6Jakob Stoklund Olesen DEBUG(dbgs() << "Shrink: " << *li << '\n'); 65511513e5d1e1b40e6113668e4b4357596f33fa6c6Jakob Stoklund Olesen assert(TargetRegisterInfo::isVirtualRegister(li->reg) 656567cdbab28077ea1801ebff3d4291d4006d88ca3Lang Hames && "Can only shrink virtual registers"); 65711513e5d1e1b40e6113668e4b4357596f33fa6c6Jakob Stoklund Olesen // Find all the values used, including PHI kills. 65811513e5d1e1b40e6113668e4b4357596f33fa6c6Jakob Stoklund Olesen SmallVector<std::pair<SlotIndex, VNInfo*>, 16> WorkList; 65911513e5d1e1b40e6113668e4b4357596f33fa6c6Jakob Stoklund Olesen 660031432f9ad24963282b7f71bd0592080f6229d20Jakob Stoklund Olesen // Blocks that have already been added to WorkList as live-out. 661031432f9ad24963282b7f71bd0592080f6229d20Jakob Stoklund Olesen SmallPtrSet<MachineBasicBlock*, 16> LiveOut; 662031432f9ad24963282b7f71bd0592080f6229d20Jakob Stoklund Olesen 66311513e5d1e1b40e6113668e4b4357596f33fa6c6Jakob Stoklund Olesen // Visit all instructions reading li->reg. 66411513e5d1e1b40e6113668e4b4357596f33fa6c6Jakob Stoklund Olesen for (MachineRegisterInfo::reg_iterator I = mri_->reg_begin(li->reg); 66511513e5d1e1b40e6113668e4b4357596f33fa6c6Jakob Stoklund Olesen MachineInstr *UseMI = I.skipInstruction();) { 66611513e5d1e1b40e6113668e4b4357596f33fa6c6Jakob Stoklund Olesen if (UseMI->isDebugValue() || !UseMI->readsVirtualRegister(li->reg)) 66711513e5d1e1b40e6113668e4b4357596f33fa6c6Jakob Stoklund Olesen continue; 6686c9cc21d85cdef79b971f710ace287f3a2f847a3Jakob Stoklund Olesen SlotIndex Idx = getInstructionIndex(UseMI).getRegSlot(); 669f054e198197122011fc80b673f35333bc3e58c98Jakob Stoklund Olesen // Note: This intentionally picks up the wrong VNI in case of an EC redef. 670f054e198197122011fc80b673f35333bc3e58c98Jakob Stoklund Olesen // See below. 671f054e198197122011fc80b673f35333bc3e58c98Jakob Stoklund Olesen VNInfo *VNI = li->getVNInfoBefore(Idx); 6729ef931e71c06a0390d6387859843be1d6d4daad6Jakob Stoklund Olesen if (!VNI) { 6739ef931e71c06a0390d6387859843be1d6d4daad6Jakob Stoklund Olesen // This shouldn't happen: readsVirtualRegister returns true, but there is 6749ef931e71c06a0390d6387859843be1d6d4daad6Jakob Stoklund Olesen // no live value. It is likely caused by a target getting <undef> flags 6759ef931e71c06a0390d6387859843be1d6d4daad6Jakob Stoklund Olesen // wrong. 6769ef931e71c06a0390d6387859843be1d6d4daad6Jakob Stoklund Olesen DEBUG(dbgs() << Idx << '\t' << *UseMI 6779ef931e71c06a0390d6387859843be1d6d4daad6Jakob Stoklund Olesen << "Warning: Instr claims to read non-existent value in " 6789ef931e71c06a0390d6387859843be1d6d4daad6Jakob Stoklund Olesen << *li << '\n'); 6799ef931e71c06a0390d6387859843be1d6d4daad6Jakob Stoklund Olesen continue; 6809ef931e71c06a0390d6387859843be1d6d4daad6Jakob Stoklund Olesen } 681f054e198197122011fc80b673f35333bc3e58c98Jakob Stoklund Olesen // Special case: An early-clobber tied operand reads and writes the 682f054e198197122011fc80b673f35333bc3e58c98Jakob Stoklund Olesen // register one slot early. The getVNInfoBefore call above would have 683f054e198197122011fc80b673f35333bc3e58c98Jakob Stoklund Olesen // picked up the value defined by UseMI. Adjust the kill slot and value. 684f054e198197122011fc80b673f35333bc3e58c98Jakob Stoklund Olesen if (SlotIndex::isSameInstr(VNI->def, Idx)) { 685f054e198197122011fc80b673f35333bc3e58c98Jakob Stoklund Olesen Idx = VNI->def; 6866c9cc21d85cdef79b971f710ace287f3a2f847a3Jakob Stoklund Olesen VNI = li->getVNInfoBefore(Idx); 68711513e5d1e1b40e6113668e4b4357596f33fa6c6Jakob Stoklund Olesen assert(VNI && "Early-clobber tied value not available"); 68811513e5d1e1b40e6113668e4b4357596f33fa6c6Jakob Stoklund Olesen } 68911513e5d1e1b40e6113668e4b4357596f33fa6c6Jakob Stoklund Olesen WorkList.push_back(std::make_pair(Idx, VNI)); 69011513e5d1e1b40e6113668e4b4357596f33fa6c6Jakob Stoklund Olesen } 69111513e5d1e1b40e6113668e4b4357596f33fa6c6Jakob Stoklund Olesen 69211513e5d1e1b40e6113668e4b4357596f33fa6c6Jakob Stoklund Olesen // Create a new live interval with only minimal live segments per def. 69311513e5d1e1b40e6113668e4b4357596f33fa6c6Jakob Stoklund Olesen LiveInterval NewLI(li->reg, 0); 69411513e5d1e1b40e6113668e4b4357596f33fa6c6Jakob Stoklund Olesen for (LiveInterval::vni_iterator I = li->vni_begin(), E = li->vni_end(); 69511513e5d1e1b40e6113668e4b4357596f33fa6c6Jakob Stoklund Olesen I != E; ++I) { 69611513e5d1e1b40e6113668e4b4357596f33fa6c6Jakob Stoklund Olesen VNInfo *VNI = *I; 69711513e5d1e1b40e6113668e4b4357596f33fa6c6Jakob Stoklund Olesen if (VNI->isUnused()) 69811513e5d1e1b40e6113668e4b4357596f33fa6c6Jakob Stoklund Olesen continue; 6991f81e316b042c02c841801a71e7439e166ffa2a0Jakob Stoklund Olesen NewLI.addRange(LiveRange(VNI->def, VNI->def.getDeadSlot(), VNI)); 70011513e5d1e1b40e6113668e4b4357596f33fa6c6Jakob Stoklund Olesen } 70111513e5d1e1b40e6113668e4b4357596f33fa6c6Jakob Stoklund Olesen 702e0ab24532cc11f082d722ab169080322b39afeceJakob Stoklund Olesen // Keep track of the PHIs that are in use. 703e0ab24532cc11f082d722ab169080322b39afeceJakob Stoklund Olesen SmallPtrSet<VNInfo*, 8> UsedPHIs; 704e0ab24532cc11f082d722ab169080322b39afeceJakob Stoklund Olesen 70511513e5d1e1b40e6113668e4b4357596f33fa6c6Jakob Stoklund Olesen // Extend intervals to reach all uses in WorkList. 70611513e5d1e1b40e6113668e4b4357596f33fa6c6Jakob Stoklund Olesen while (!WorkList.empty()) { 70711513e5d1e1b40e6113668e4b4357596f33fa6c6Jakob Stoklund Olesen SlotIndex Idx = WorkList.back().first; 70811513e5d1e1b40e6113668e4b4357596f33fa6c6Jakob Stoklund Olesen VNInfo *VNI = WorkList.back().second; 70911513e5d1e1b40e6113668e4b4357596f33fa6c6Jakob Stoklund Olesen WorkList.pop_back(); 7106c9cc21d85cdef79b971f710ace287f3a2f847a3Jakob Stoklund Olesen const MachineBasicBlock *MBB = getMBBFromIndex(Idx.getPrevSlot()); 71111513e5d1e1b40e6113668e4b4357596f33fa6c6Jakob Stoklund Olesen SlotIndex BlockStart = getMBBStartIdx(MBB); 712e0ab24532cc11f082d722ab169080322b39afeceJakob Stoklund Olesen 713e0ab24532cc11f082d722ab169080322b39afeceJakob Stoklund Olesen // Extend the live range for VNI to be live at Idx. 7146c9cc21d85cdef79b971f710ace287f3a2f847a3Jakob Stoklund Olesen if (VNInfo *ExtVNI = NewLI.extendInBlock(BlockStart, Idx)) { 7154b11a70f7a63dc4c051a96a90ed6687eb0595cdaNick Lewycky (void)ExtVNI; 716e0ab24532cc11f082d722ab169080322b39afeceJakob Stoklund Olesen assert(ExtVNI == VNI && "Unexpected existing value number"); 717e0ab24532cc11f082d722ab169080322b39afeceJakob Stoklund Olesen // Is this a PHIDef we haven't seen before? 718c29d9b3495a2d87af524ad5c4b62f46c4265d828Jakob Stoklund Olesen if (!VNI->isPHIDef() || VNI->def != BlockStart || !UsedPHIs.insert(VNI)) 719e0ab24532cc11f082d722ab169080322b39afeceJakob Stoklund Olesen continue; 720e0ab24532cc11f082d722ab169080322b39afeceJakob Stoklund Olesen // The PHI is live, make sure the predecessors are live-out. 721e0ab24532cc11f082d722ab169080322b39afeceJakob Stoklund Olesen for (MachineBasicBlock::const_pred_iterator PI = MBB->pred_begin(), 722e0ab24532cc11f082d722ab169080322b39afeceJakob Stoklund Olesen PE = MBB->pred_end(); PI != PE; ++PI) { 723031432f9ad24963282b7f71bd0592080f6229d20Jakob Stoklund Olesen if (!LiveOut.insert(*PI)) 724031432f9ad24963282b7f71bd0592080f6229d20Jakob Stoklund Olesen continue; 7256c9cc21d85cdef79b971f710ace287f3a2f847a3Jakob Stoklund Olesen SlotIndex Stop = getMBBEndIdx(*PI); 726e0ab24532cc11f082d722ab169080322b39afeceJakob Stoklund Olesen // A predecessor is not required to have a live-out value for a PHI. 7276c9cc21d85cdef79b971f710ace287f3a2f847a3Jakob Stoklund Olesen if (VNInfo *PVNI = li->getVNInfoBefore(Stop)) 728e0ab24532cc11f082d722ab169080322b39afeceJakob Stoklund Olesen WorkList.push_back(std::make_pair(Stop, PVNI)); 72911513e5d1e1b40e6113668e4b4357596f33fa6c6Jakob Stoklund Olesen } 73011513e5d1e1b40e6113668e4b4357596f33fa6c6Jakob Stoklund Olesen continue; 73111513e5d1e1b40e6113668e4b4357596f33fa6c6Jakob Stoklund Olesen } 73211513e5d1e1b40e6113668e4b4357596f33fa6c6Jakob Stoklund Olesen 73311513e5d1e1b40e6113668e4b4357596f33fa6c6Jakob Stoklund Olesen // VNI is live-in to MBB. 73411513e5d1e1b40e6113668e4b4357596f33fa6c6Jakob Stoklund Olesen DEBUG(dbgs() << " live-in at " << BlockStart << '\n'); 7356c9cc21d85cdef79b971f710ace287f3a2f847a3Jakob Stoklund Olesen NewLI.addRange(LiveRange(BlockStart, Idx, VNI)); 73611513e5d1e1b40e6113668e4b4357596f33fa6c6Jakob Stoklund Olesen 73711513e5d1e1b40e6113668e4b4357596f33fa6c6Jakob Stoklund Olesen // Make sure VNI is live-out from the predecessors. 73811513e5d1e1b40e6113668e4b4357596f33fa6c6Jakob Stoklund Olesen for (MachineBasicBlock::const_pred_iterator PI = MBB->pred_begin(), 73911513e5d1e1b40e6113668e4b4357596f33fa6c6Jakob Stoklund Olesen PE = MBB->pred_end(); PI != PE; ++PI) { 740031432f9ad24963282b7f71bd0592080f6229d20Jakob Stoklund Olesen if (!LiveOut.insert(*PI)) 741031432f9ad24963282b7f71bd0592080f6229d20Jakob Stoklund Olesen continue; 7426c9cc21d85cdef79b971f710ace287f3a2f847a3Jakob Stoklund Olesen SlotIndex Stop = getMBBEndIdx(*PI); 7436c9cc21d85cdef79b971f710ace287f3a2f847a3Jakob Stoklund Olesen assert(li->getVNInfoBefore(Stop) == VNI && 7446c9cc21d85cdef79b971f710ace287f3a2f847a3Jakob Stoklund Olesen "Wrong value out of predecessor"); 74511513e5d1e1b40e6113668e4b4357596f33fa6c6Jakob Stoklund Olesen WorkList.push_back(std::make_pair(Stop, VNI)); 74611513e5d1e1b40e6113668e4b4357596f33fa6c6Jakob Stoklund Olesen } 74711513e5d1e1b40e6113668e4b4357596f33fa6c6Jakob Stoklund Olesen } 74811513e5d1e1b40e6113668e4b4357596f33fa6c6Jakob Stoklund Olesen 74911513e5d1e1b40e6113668e4b4357596f33fa6c6Jakob Stoklund Olesen // Handle dead values. 7506a3dbd3b25bbc99bd1a233d6a74ddea3493ba6acJakob Stoklund Olesen bool CanSeparate = false; 75111513e5d1e1b40e6113668e4b4357596f33fa6c6Jakob Stoklund Olesen for (LiveInterval::vni_iterator I = li->vni_begin(), E = li->vni_end(); 75211513e5d1e1b40e6113668e4b4357596f33fa6c6Jakob Stoklund Olesen I != E; ++I) { 75311513e5d1e1b40e6113668e4b4357596f33fa6c6Jakob Stoklund Olesen VNInfo *VNI = *I; 75411513e5d1e1b40e6113668e4b4357596f33fa6c6Jakob Stoklund Olesen if (VNI->isUnused()) 75511513e5d1e1b40e6113668e4b4357596f33fa6c6Jakob Stoklund Olesen continue; 75611513e5d1e1b40e6113668e4b4357596f33fa6c6Jakob Stoklund Olesen LiveInterval::iterator LII = NewLI.FindLiveRangeContaining(VNI->def); 75711513e5d1e1b40e6113668e4b4357596f33fa6c6Jakob Stoklund Olesen assert(LII != NewLI.end() && "Missing live range for PHI"); 7581f81e316b042c02c841801a71e7439e166ffa2a0Jakob Stoklund Olesen if (LII->end != VNI->def.getDeadSlot()) 75911513e5d1e1b40e6113668e4b4357596f33fa6c6Jakob Stoklund Olesen continue; 760a4d347357ce04d9101130dca0df33cb62ea35a2fJakob Stoklund Olesen if (VNI->isPHIDef()) { 76111513e5d1e1b40e6113668e4b4357596f33fa6c6Jakob Stoklund Olesen // This is a dead PHI. Remove it. 76211513e5d1e1b40e6113668e4b4357596f33fa6c6Jakob Stoklund Olesen VNI->setIsUnused(true); 76311513e5d1e1b40e6113668e4b4357596f33fa6c6Jakob Stoklund Olesen NewLI.removeRange(*LII); 7646a3dbd3b25bbc99bd1a233d6a74ddea3493ba6acJakob Stoklund Olesen DEBUG(dbgs() << "Dead PHI at " << VNI->def << " may separate interval\n"); 7656a3dbd3b25bbc99bd1a233d6a74ddea3493ba6acJakob Stoklund Olesen CanSeparate = true; 76611513e5d1e1b40e6113668e4b4357596f33fa6c6Jakob Stoklund Olesen } else { 76711513e5d1e1b40e6113668e4b4357596f33fa6c6Jakob Stoklund Olesen // This is a dead def. Make sure the instruction knows. 76811513e5d1e1b40e6113668e4b4357596f33fa6c6Jakob Stoklund Olesen MachineInstr *MI = getInstructionFromIndex(VNI->def); 76911513e5d1e1b40e6113668e4b4357596f33fa6c6Jakob Stoklund Olesen assert(MI && "No instruction defining live value"); 77011513e5d1e1b40e6113668e4b4357596f33fa6c6Jakob Stoklund Olesen MI->addRegisterDead(li->reg, tri_); 7710d8ccaa5c8db820b5b93f37e51563148c57ba6b8Jakob Stoklund Olesen if (dead && MI->allDefsAreDead()) { 772c46570dc05851395829bef904bb6ddb1260400d1Jakob Stoklund Olesen DEBUG(dbgs() << "All defs dead: " << VNI->def << '\t' << *MI); 7730d8ccaa5c8db820b5b93f37e51563148c57ba6b8Jakob Stoklund Olesen dead->push_back(MI); 7740d8ccaa5c8db820b5b93f37e51563148c57ba6b8Jakob Stoklund Olesen } 77511513e5d1e1b40e6113668e4b4357596f33fa6c6Jakob Stoklund Olesen } 77611513e5d1e1b40e6113668e4b4357596f33fa6c6Jakob Stoklund Olesen } 77711513e5d1e1b40e6113668e4b4357596f33fa6c6Jakob Stoklund Olesen 77811513e5d1e1b40e6113668e4b4357596f33fa6c6Jakob Stoklund Olesen // Move the trimmed ranges back. 77911513e5d1e1b40e6113668e4b4357596f33fa6c6Jakob Stoklund Olesen li->ranges.swap(NewLI.ranges); 780c46570dc05851395829bef904bb6ddb1260400d1Jakob Stoklund Olesen DEBUG(dbgs() << "Shrunk: " << *li << '\n'); 7816a3dbd3b25bbc99bd1a233d6a74ddea3493ba6acJakob Stoklund Olesen return CanSeparate; 78211513e5d1e1b40e6113668e4b4357596f33fa6c6Jakob Stoklund Olesen} 78311513e5d1e1b40e6113668e4b4357596f33fa6c6Jakob Stoklund Olesen 78411513e5d1e1b40e6113668e4b4357596f33fa6c6Jakob Stoklund Olesen 785f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng//===----------------------------------------------------------------------===// 786f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng// Register allocator hooks. 787f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng// 788f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng 7898a61da8a689ee95874c833af4c7aa965fab5c0a9Jakob Stoklund Olesenvoid LiveIntervals::addKillFlags() { 7908a61da8a689ee95874c833af4c7aa965fab5c0a9Jakob Stoklund Olesen for (iterator I = begin(), E = end(); I != E; ++I) { 7918a61da8a689ee95874c833af4c7aa965fab5c0a9Jakob Stoklund Olesen unsigned Reg = I->first; 7928a61da8a689ee95874c833af4c7aa965fab5c0a9Jakob Stoklund Olesen if (TargetRegisterInfo::isPhysicalRegister(Reg)) 7938a61da8a689ee95874c833af4c7aa965fab5c0a9Jakob Stoklund Olesen continue; 7948a61da8a689ee95874c833af4c7aa965fab5c0a9Jakob Stoklund Olesen if (mri_->reg_nodbg_empty(Reg)) 7958a61da8a689ee95874c833af4c7aa965fab5c0a9Jakob Stoklund Olesen continue; 7968a61da8a689ee95874c833af4c7aa965fab5c0a9Jakob Stoklund Olesen LiveInterval *LI = I->second; 7978a61da8a689ee95874c833af4c7aa965fab5c0a9Jakob Stoklund Olesen 7988a61da8a689ee95874c833af4c7aa965fab5c0a9Jakob Stoklund Olesen // Every instruction that kills Reg corresponds to a live range end point. 7998a61da8a689ee95874c833af4c7aa965fab5c0a9Jakob Stoklund Olesen for (LiveInterval::iterator RI = LI->begin(), RE = LI->end(); RI != RE; 8008a61da8a689ee95874c833af4c7aa965fab5c0a9Jakob Stoklund Olesen ++RI) { 8012debd48ca790ac01be6e12e094fdf4fdcadc8364Jakob Stoklund Olesen // A block index indicates an MBB edge. 8022debd48ca790ac01be6e12e094fdf4fdcadc8364Jakob Stoklund Olesen if (RI->end.isBlock()) 8038a61da8a689ee95874c833af4c7aa965fab5c0a9Jakob Stoklund Olesen continue; 8048a61da8a689ee95874c833af4c7aa965fab5c0a9Jakob Stoklund Olesen MachineInstr *MI = getInstructionFromIndex(RI->end); 8058a61da8a689ee95874c833af4c7aa965fab5c0a9Jakob Stoklund Olesen if (!MI) 8068a61da8a689ee95874c833af4c7aa965fab5c0a9Jakob Stoklund Olesen continue; 8078a61da8a689ee95874c833af4c7aa965fab5c0a9Jakob Stoklund Olesen MI->addRegisterKilled(Reg, NULL); 8088a61da8a689ee95874c833af4c7aa965fab5c0a9Jakob Stoklund Olesen } 8098a61da8a689ee95874c833af4c7aa965fab5c0a9Jakob Stoklund Olesen } 8108a61da8a689ee95874c833af4c7aa965fab5c0a9Jakob Stoklund Olesen} 8118a61da8a689ee95874c833af4c7aa965fab5c0a9Jakob Stoklund Olesen 812d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng/// getReMatImplicitUse - If the remat definition MI has one (for now, we only 813d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng/// allow one) virtual register operand, then its uses are implicitly using 814d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng/// the register. Returns the virtual register. 815d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Chengunsigned LiveIntervals::getReMatImplicitUse(const LiveInterval &li, 816d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng MachineInstr *MI) const { 817d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng unsigned RegOp = 0; 818d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) { 819d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng MachineOperand &MO = MI->getOperand(i); 820d735b8019b0f297d7c14b55adcd887af24d8e602Dan Gohman if (!MO.isReg() || !MO.isUse()) 821d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng continue; 822d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng unsigned Reg = MO.getReg(); 823d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng if (Reg == 0 || Reg == li.reg) 824d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng continue; 8251b2932024f098a6968645ac78d5848951d877c19Jakob Stoklund Olesen 826cd339b71ff23327f2ef6a4c964ff3ceea20733bfLang Hames if (TargetRegisterInfo::isPhysicalRegister(Reg) && !isAllocatable(Reg)) 8271873d0c2257b18451c5bb35577f929d0723433a0Chris Lattner continue; 828d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng RegOp = MO.getReg(); 8296c76e80753cfc83dc6804fcd5d949c517dfe3434Lang Hames break; // Found vreg operand - leave the loop. 830d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng } 831d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng return RegOp; 832d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng} 833d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng 834d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng/// isValNoAvailableAt - Return true if the val# of the specified interval 835d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng/// which reaches the given instruction also reaches the specified use index. 836d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Chengbool LiveIntervals::isValNoAvailableAt(const LiveInterval &li, MachineInstr *MI, 837233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames SlotIndex UseIdx) const { 83831cc3ec3308c8fafd9865388214ae11662a71af4Jakob Stoklund Olesen VNInfo *UValNo = li.getVNInfoAt(UseIdx); 83931cc3ec3308c8fafd9865388214ae11662a71af4Jakob Stoklund Olesen return UValNo && UValNo == li.getVNInfoAt(getInstructionIndex(MI)); 840d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng} 841d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng 842f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng/// isReMaterializable - Returns true if the definition MI of the specified 843f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng/// val# of the specified interval is re-materializable. 844f4baeaf8485f01beda46d29fd55753199dc68070Andrew Trickbool 845f4baeaf8485f01beda46d29fd55753199dc68070Andrew TrickLiveIntervals::isReMaterializable(const LiveInterval &li, 846f4baeaf8485f01beda46d29fd55753199dc68070Andrew Trick const VNInfo *ValNo, MachineInstr *MI, 84738f6bd0fc8095ef79a89b3db15ff6dc734ac90e7Jakob Stoklund Olesen const SmallVectorImpl<LiveInterval*> *SpillIs, 848f4baeaf8485f01beda46d29fd55753199dc68070Andrew Trick bool &isLoad) { 849f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng if (DisableReMat) 850f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng return false; 851f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng 852a70dca156fa76d452f54829b5c5f962ddfd94ef2Dan Gohman if (!tii_->isTriviallyReMaterializable(MI, aa_)) 853a70dca156fa76d452f54829b5c5f962ddfd94ef2Dan Gohman return false; 854f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng 855a70dca156fa76d452f54829b5c5f962ddfd94ef2Dan Gohman // Target-specific code can mark an instruction as being rematerializable 856a70dca156fa76d452f54829b5c5f962ddfd94ef2Dan Gohman // if it has one virtual reg use, though it had better be something like 857a70dca156fa76d452f54829b5c5f962ddfd94ef2Dan Gohman // a PIC base register which is likely to be live everywhere. 8586d69ba8a6901c69d78488cbc41f8dbf080618fdeDan Gohman unsigned ImpUse = getReMatImplicitUse(li, MI); 8596d69ba8a6901c69d78488cbc41f8dbf080618fdeDan Gohman if (ImpUse) { 8606d69ba8a6901c69d78488cbc41f8dbf080618fdeDan Gohman const LiveInterval &ImpLi = getInterval(ImpUse); 86128a1e486907104b85c5787345914917d74f0cf77Evan Cheng for (MachineRegisterInfo::use_nodbg_iterator 86228a1e486907104b85c5787345914917d74f0cf77Evan Cheng ri = mri_->use_nodbg_begin(li.reg), re = mri_->use_nodbg_end(); 86328a1e486907104b85c5787345914917d74f0cf77Evan Cheng ri != re; ++ri) { 8646d69ba8a6901c69d78488cbc41f8dbf080618fdeDan Gohman MachineInstr *UseMI = &*ri; 865233a60ec40b41027ff429e2f2c27fa2be762f2e9Lang Hames SlotIndex UseIdx = getInstructionIndex(UseMI); 86631cc3ec3308c8fafd9865388214ae11662a71af4Jakob Stoklund Olesen if (li.getVNInfoAt(UseIdx) != ValNo) 8676d69ba8a6901c69d78488cbc41f8dbf080618fdeDan Gohman continue; 8686d69ba8a6901c69d78488cbc41f8dbf080618fdeDan Gohman if (!isValNoAvailableAt(ImpLi, MI, UseIdx)) 8696d69ba8a6901c69d78488cbc41f8dbf080618fdeDan Gohman return false; 8706d69ba8a6901c69d78488cbc41f8dbf080618fdeDan Gohman } 871dc37786595beedd0a68d8e2cbd91ae53ad58d133Evan Cheng 872dc37786595beedd0a68d8e2cbd91ae53ad58d133Evan Cheng // If a register operand of the re-materialized instruction is going to 873dc37786595beedd0a68d8e2cbd91ae53ad58d133Evan Cheng // be spilled next, then it's not legal to re-materialize this instruction. 87438f6bd0fc8095ef79a89b3db15ff6dc734ac90e7Jakob Stoklund Olesen if (SpillIs) 87538f6bd0fc8095ef79a89b3db15ff6dc734ac90e7Jakob Stoklund Olesen for (unsigned i = 0, e = SpillIs->size(); i != e; ++i) 87638f6bd0fc8095ef79a89b3db15ff6dc734ac90e7Jakob Stoklund Olesen if (ImpUse == (*SpillIs)[i]->reg) 87738f6bd0fc8095ef79a89b3db15ff6dc734ac90e7Jakob Stoklund Olesen return false; 8786d69ba8a6901c69d78488cbc41f8dbf080618fdeDan Gohman } 8796d69ba8a6901c69d78488cbc41f8dbf080618fdeDan Gohman return true; 8805ef3a04b542c4e585276768fa9ca2af698ef5c87Evan Cheng} 8815ef3a04b542c4e585276768fa9ca2af698ef5c87Evan Cheng 8825ef3a04b542c4e585276768fa9ca2af698ef5c87Evan Cheng/// isReMaterializable - Returns true if every definition of MI of every 8835ef3a04b542c4e585276768fa9ca2af698ef5c87Evan Cheng/// val# of the specified interval is re-materializable. 884f4baeaf8485f01beda46d29fd55753199dc68070Andrew Trickbool 885f4baeaf8485f01beda46d29fd55753199dc68070Andrew TrickLiveIntervals::isReMaterializable(const LiveInterval &li, 88638f6bd0fc8095ef79a89b3db15ff6dc734ac90e7Jakob Stoklund Olesen const SmallVectorImpl<LiveInterval*> *SpillIs, 887f4baeaf8485f01beda46d29fd55753199dc68070Andrew Trick bool &isLoad) { 8885ef3a04b542c4e585276768fa9ca2af698ef5c87Evan Cheng isLoad = false; 8895ef3a04b542c4e585276768fa9ca2af698ef5c87Evan Cheng for (LiveInterval::const_vni_iterator i = li.vni_begin(), e = li.vni_end(); 8905ef3a04b542c4e585276768fa9ca2af698ef5c87Evan Cheng i != e; ++i) { 8915ef3a04b542c4e585276768fa9ca2af698ef5c87Evan Cheng const VNInfo *VNI = *i; 892857c4e01f85601cf2084adb860616256ee47c177Lang Hames if (VNI->isUnused()) 8935ef3a04b542c4e585276768fa9ca2af698ef5c87Evan Cheng continue; // Dead val#. 8945ef3a04b542c4e585276768fa9ca2af698ef5c87Evan Cheng // Is the def for the val# rematerializable? 895857c4e01f85601cf2084adb860616256ee47c177Lang Hames MachineInstr *ReMatDefMI = getInstructionFromIndex(VNI->def); 8966e2968c85c1e162ee5bc813769eab223e3df0f15Lang Hames if (!ReMatDefMI) 8976e2968c85c1e162ee5bc813769eab223e3df0f15Lang Hames return false; 8985ef3a04b542c4e585276768fa9ca2af698ef5c87Evan Cheng bool DefIsLoad = false; 899d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng if (!ReMatDefMI || 900dc37786595beedd0a68d8e2cbd91ae53ad58d133Evan Cheng !isReMaterializable(li, VNI, ReMatDefMI, SpillIs, DefIsLoad)) 901f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng return false; 9025ef3a04b542c4e585276768fa9ca2af698ef5c87Evan Cheng isLoad |= DefIsLoad; 903f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng } 904f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng return true; 905f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng} 906f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng 907ebf2750a70df4261d3e66144ea6bcb49d41f6efbJakob Stoklund OlesenMachineBasicBlock* 908ebf2750a70df4261d3e66144ea6bcb49d41f6efbJakob Stoklund OlesenLiveIntervals::intervalIsInOneMBB(const LiveInterval &LI) const { 909ebf2750a70df4261d3e66144ea6bcb49d41f6efbJakob Stoklund Olesen // A local live range must be fully contained inside the block, meaning it is 910ebf2750a70df4261d3e66144ea6bcb49d41f6efbJakob Stoklund Olesen // defined and killed at instructions, not at block boundaries. It is not 911ebf2750a70df4261d3e66144ea6bcb49d41f6efbJakob Stoklund Olesen // live in or or out of any block. 912ebf2750a70df4261d3e66144ea6bcb49d41f6efbJakob Stoklund Olesen // 913ebf2750a70df4261d3e66144ea6bcb49d41f6efbJakob Stoklund Olesen // It is technically possible to have a PHI-defined live range identical to a 914ebf2750a70df4261d3e66144ea6bcb49d41f6efbJakob Stoklund Olesen // single block, but we are going to return false in that case. 915ebf2750a70df4261d3e66144ea6bcb49d41f6efbJakob Stoklund Olesen 916ebf2750a70df4261d3e66144ea6bcb49d41f6efbJakob Stoklund Olesen SlotIndex Start = LI.beginIndex(); 917ebf2750a70df4261d3e66144ea6bcb49d41f6efbJakob Stoklund Olesen if (Start.isBlock()) 918ebf2750a70df4261d3e66144ea6bcb49d41f6efbJakob Stoklund Olesen return NULL; 919ebf2750a70df4261d3e66144ea6bcb49d41f6efbJakob Stoklund Olesen 920ebf2750a70df4261d3e66144ea6bcb49d41f6efbJakob Stoklund Olesen SlotIndex Stop = LI.endIndex(); 921ebf2750a70df4261d3e66144ea6bcb49d41f6efbJakob Stoklund Olesen if (Stop.isBlock()) 922ebf2750a70df4261d3e66144ea6bcb49d41f6efbJakob Stoklund Olesen return NULL; 923ebf2750a70df4261d3e66144ea6bcb49d41f6efbJakob Stoklund Olesen 924ebf2750a70df4261d3e66144ea6bcb49d41f6efbJakob Stoklund Olesen // getMBBFromIndex doesn't need to search the MBB table when both indexes 925ebf2750a70df4261d3e66144ea6bcb49d41f6efbJakob Stoklund Olesen // belong to proper instructions. 926ebf2750a70df4261d3e66144ea6bcb49d41f6efbJakob Stoklund Olesen MachineBasicBlock *MBB1 = indexes_->getMBBFromIndex(Start); 927ebf2750a70df4261d3e66144ea6bcb49d41f6efbJakob Stoklund Olesen MachineBasicBlock *MBB2 = indexes_->getMBBFromIndex(Stop); 928ebf2750a70df4261d3e66144ea6bcb49d41f6efbJakob Stoklund Olesen return MBB1 == MBB2 ? MBB1 : NULL; 92981a038218171860ee4c382849c647d3dc841fe8bEvan Cheng} 93081a038218171860ee4c382849c647d3dc841fe8bEvan Cheng 931e5d90416ee1a4f45eba80789a7a3cbc3d497a4cdJakob Stoklund Olesenfloat 932e5d90416ee1a4f45eba80789a7a3cbc3d497a4cdJakob Stoklund OlesenLiveIntervals::getSpillWeight(bool isDef, bool isUse, unsigned loopDepth) { 933e5d90416ee1a4f45eba80789a7a3cbc3d497a4cdJakob Stoklund Olesen // Limit the loop depth ridiculousness. 934e5d90416ee1a4f45eba80789a7a3cbc3d497a4cdJakob Stoklund Olesen if (loopDepth > 200) 935e5d90416ee1a4f45eba80789a7a3cbc3d497a4cdJakob Stoklund Olesen loopDepth = 200; 936e5d90416ee1a4f45eba80789a7a3cbc3d497a4cdJakob Stoklund Olesen 937e5d90416ee1a4f45eba80789a7a3cbc3d497a4cdJakob Stoklund Olesen // The loop depth is used to roughly estimate the number of times the 938e5d90416ee1a4f45eba80789a7a3cbc3d497a4cdJakob Stoklund Olesen // instruction is executed. Something like 10^d is simple, but will quickly 939e5d90416ee1a4f45eba80789a7a3cbc3d497a4cdJakob Stoklund Olesen // overflow a float. This expression behaves like 10^d for small d, but is 940e5d90416ee1a4f45eba80789a7a3cbc3d497a4cdJakob Stoklund Olesen // more tempered for large d. At d=200 we get 6.7e33 which leaves a bit of 941e5d90416ee1a4f45eba80789a7a3cbc3d497a4cdJakob Stoklund Olesen // headroom before overflow. 942dc5198bac7e3f9b61617c8c46a1c28a84daa9325NAKAMURA Takumi // By the way, powf() might be unavailable here. For consistency, 943dc5198bac7e3f9b61617c8c46a1c28a84daa9325NAKAMURA Takumi // We may take pow(double,double). 944dc5198bac7e3f9b61617c8c46a1c28a84daa9325NAKAMURA Takumi float lc = std::pow(1 + (100.0 / (loopDepth + 10)), (double)loopDepth); 945e5d90416ee1a4f45eba80789a7a3cbc3d497a4cdJakob Stoklund Olesen 946e5d90416ee1a4f45eba80789a7a3cbc3d497a4cdJakob Stoklund Olesen return (isDef + isUse) * lc; 947e5d90416ee1a4f45eba80789a7a3cbc3d497a4cdJakob Stoklund Olesen} 948e5d90416ee1a4f45eba80789a7a3cbc3d497a4cdJakob Stoklund Olesen 949c4dc132c8a787fc41b6a162121251234aa618965Owen AndersonLiveRange LiveIntervals::addLiveRangeToEndOfBlock(unsigned reg, 950ffd1326ff8dfc652a8026c3faebf55bbba7c32c7Lang Hames MachineInstr* startInst) { 951c4dc132c8a787fc41b6a162121251234aa618965Owen Anderson LiveInterval& Interval = getOrCreateInterval(reg); 952c4dc132c8a787fc41b6a162121251234aa618965Owen Anderson VNInfo* VN = Interval.getNextValue( 9532debd48ca790ac01be6e12e094fdf4fdcadc8364Jakob Stoklund Olesen SlotIndex(getInstructionIndex(startInst).getRegSlot()), 9543b1088a2cc15a39c7a7b8dd95a56143f1dda6863Jakob Stoklund Olesen getVNInfoAllocator()); 955857c4e01f85601cf2084adb860616256ee47c177Lang Hames VN->setHasPHIKill(true); 9568651125d2885f74546b6e2a556082111d5b75da3Lang Hames LiveRange LR( 9572debd48ca790ac01be6e12e094fdf4fdcadc8364Jakob Stoklund Olesen SlotIndex(getInstructionIndex(startInst).getRegSlot()), 95874ab5eeffbd70f2387338e3ee8195be9f73e6dd8Lang Hames getMBBEndIdx(startInst->getParent()), VN); 959c4dc132c8a787fc41b6a162121251234aa618965Owen Anderson Interval.addRange(LR); 9601b2932024f098a6968645ac78d5848951d877c19Jakob Stoklund Olesen 961c4dc132c8a787fc41b6a162121251234aa618965Owen Anderson return LR; 962c4dc132c8a787fc41b6a162121251234aa618965Owen Anderson} 9633fd3a840c50fe4ede1b200be18990bc955c536fdJakob Stoklund Olesen 9643fd3a840c50fe4ede1b200be18990bc955c536fdJakob Stoklund Olesen 9653fd3a840c50fe4ede1b200be18990bc955c536fdJakob Stoklund Olesen//===----------------------------------------------------------------------===// 9663fd3a840c50fe4ede1b200be18990bc955c536fdJakob Stoklund Olesen// Register mask functions 9673fd3a840c50fe4ede1b200be18990bc955c536fdJakob Stoklund Olesen//===----------------------------------------------------------------------===// 9683fd3a840c50fe4ede1b200be18990bc955c536fdJakob Stoklund Olesen 9693fd3a840c50fe4ede1b200be18990bc955c536fdJakob Stoklund Olesenbool LiveIntervals::checkRegMaskInterference(LiveInterval &LI, 9703fd3a840c50fe4ede1b200be18990bc955c536fdJakob Stoklund Olesen BitVector &UsableRegs) { 9713fd3a840c50fe4ede1b200be18990bc955c536fdJakob Stoklund Olesen if (LI.empty()) 9723fd3a840c50fe4ede1b200be18990bc955c536fdJakob Stoklund Olesen return false; 9739f10ac63a3a2a74ac381a05d8ba0f7b1b455a6b6Jakob Stoklund Olesen LiveInterval::iterator LiveI = LI.begin(), LiveE = LI.end(); 9749f10ac63a3a2a74ac381a05d8ba0f7b1b455a6b6Jakob Stoklund Olesen 9759f10ac63a3a2a74ac381a05d8ba0f7b1b455a6b6Jakob Stoklund Olesen // Use a smaller arrays for local live ranges. 9769f10ac63a3a2a74ac381a05d8ba0f7b1b455a6b6Jakob Stoklund Olesen ArrayRef<SlotIndex> Slots; 9779f10ac63a3a2a74ac381a05d8ba0f7b1b455a6b6Jakob Stoklund Olesen ArrayRef<const uint32_t*> Bits; 9789f10ac63a3a2a74ac381a05d8ba0f7b1b455a6b6Jakob Stoklund Olesen if (MachineBasicBlock *MBB = intervalIsInOneMBB(LI)) { 9799f10ac63a3a2a74ac381a05d8ba0f7b1b455a6b6Jakob Stoklund Olesen Slots = getRegMaskSlotsInBlock(MBB->getNumber()); 9809f10ac63a3a2a74ac381a05d8ba0f7b1b455a6b6Jakob Stoklund Olesen Bits = getRegMaskBitsInBlock(MBB->getNumber()); 9819f10ac63a3a2a74ac381a05d8ba0f7b1b455a6b6Jakob Stoklund Olesen } else { 9829f10ac63a3a2a74ac381a05d8ba0f7b1b455a6b6Jakob Stoklund Olesen Slots = getRegMaskSlots(); 9839f10ac63a3a2a74ac381a05d8ba0f7b1b455a6b6Jakob Stoklund Olesen Bits = getRegMaskBits(); 9849f10ac63a3a2a74ac381a05d8ba0f7b1b455a6b6Jakob Stoklund Olesen } 9853fd3a840c50fe4ede1b200be18990bc955c536fdJakob Stoklund Olesen 9863fd3a840c50fe4ede1b200be18990bc955c536fdJakob Stoklund Olesen // We are going to enumerate all the register mask slots contained in LI. 9873fd3a840c50fe4ede1b200be18990bc955c536fdJakob Stoklund Olesen // Start with a binary search of RegMaskSlots to find a starting point. 9883fd3a840c50fe4ede1b200be18990bc955c536fdJakob Stoklund Olesen ArrayRef<SlotIndex>::iterator SlotI = 9893fd3a840c50fe4ede1b200be18990bc955c536fdJakob Stoklund Olesen std::lower_bound(Slots.begin(), Slots.end(), LiveI->start); 9903fd3a840c50fe4ede1b200be18990bc955c536fdJakob Stoklund Olesen ArrayRef<SlotIndex>::iterator SlotE = Slots.end(); 9913fd3a840c50fe4ede1b200be18990bc955c536fdJakob Stoklund Olesen 9923fd3a840c50fe4ede1b200be18990bc955c536fdJakob Stoklund Olesen // No slots in range, LI begins after the last call. 9933fd3a840c50fe4ede1b200be18990bc955c536fdJakob Stoklund Olesen if (SlotI == SlotE) 9943fd3a840c50fe4ede1b200be18990bc955c536fdJakob Stoklund Olesen return false; 9953fd3a840c50fe4ede1b200be18990bc955c536fdJakob Stoklund Olesen 9963fd3a840c50fe4ede1b200be18990bc955c536fdJakob Stoklund Olesen bool Found = false; 9973fd3a840c50fe4ede1b200be18990bc955c536fdJakob Stoklund Olesen for (;;) { 9983fd3a840c50fe4ede1b200be18990bc955c536fdJakob Stoklund Olesen assert(*SlotI >= LiveI->start); 9993fd3a840c50fe4ede1b200be18990bc955c536fdJakob Stoklund Olesen // Loop over all slots overlapping this segment. 10003fd3a840c50fe4ede1b200be18990bc955c536fdJakob Stoklund Olesen while (*SlotI < LiveI->end) { 10013fd3a840c50fe4ede1b200be18990bc955c536fdJakob Stoklund Olesen // *SlotI overlaps LI. Collect mask bits. 10023fd3a840c50fe4ede1b200be18990bc955c536fdJakob Stoklund Olesen if (!Found) { 10033fd3a840c50fe4ede1b200be18990bc955c536fdJakob Stoklund Olesen // This is the first overlap. Initialize UsableRegs to all ones. 10043fd3a840c50fe4ede1b200be18990bc955c536fdJakob Stoklund Olesen UsableRegs.clear(); 10053fd3a840c50fe4ede1b200be18990bc955c536fdJakob Stoklund Olesen UsableRegs.resize(tri_->getNumRegs(), true); 10063fd3a840c50fe4ede1b200be18990bc955c536fdJakob Stoklund Olesen Found = true; 10073fd3a840c50fe4ede1b200be18990bc955c536fdJakob Stoklund Olesen } 10083fd3a840c50fe4ede1b200be18990bc955c536fdJakob Stoklund Olesen // Remove usable registers clobbered by this mask. 10099f10ac63a3a2a74ac381a05d8ba0f7b1b455a6b6Jakob Stoklund Olesen UsableRegs.clearBitsNotInMask(Bits[SlotI-Slots.begin()]); 10103fd3a840c50fe4ede1b200be18990bc955c536fdJakob Stoklund Olesen if (++SlotI == SlotE) 10113fd3a840c50fe4ede1b200be18990bc955c536fdJakob Stoklund Olesen return Found; 10123fd3a840c50fe4ede1b200be18990bc955c536fdJakob Stoklund Olesen } 10133fd3a840c50fe4ede1b200be18990bc955c536fdJakob Stoklund Olesen // *SlotI is beyond the current LI segment. 10143fd3a840c50fe4ede1b200be18990bc955c536fdJakob Stoklund Olesen LiveI = LI.advanceTo(LiveI, *SlotI); 10153fd3a840c50fe4ede1b200be18990bc955c536fdJakob Stoklund Olesen if (LiveI == LiveE) 10163fd3a840c50fe4ede1b200be18990bc955c536fdJakob Stoklund Olesen return Found; 10173fd3a840c50fe4ede1b200be18990bc955c536fdJakob Stoklund Olesen // Advance SlotI until it overlaps. 10183fd3a840c50fe4ede1b200be18990bc955c536fdJakob Stoklund Olesen while (*SlotI < LiveI->start) 10193fd3a840c50fe4ede1b200be18990bc955c536fdJakob Stoklund Olesen if (++SlotI == SlotE) 10203fd3a840c50fe4ede1b200be18990bc955c536fdJakob Stoklund Olesen return Found; 10213fd3a840c50fe4ede1b200be18990bc955c536fdJakob Stoklund Olesen } 10223fd3a840c50fe4ede1b200be18990bc955c536fdJakob Stoklund Olesen} 10233dc7c5138d219048d69952bead22f75efb984fa3Lang Hames 10243dc7c5138d219048d69952bead22f75efb984fa3Lang Hames//===----------------------------------------------------------------------===// 10253dc7c5138d219048d69952bead22f75efb984fa3Lang Hames// IntervalUpdate class. 10263dc7c5138d219048d69952bead22f75efb984fa3Lang Hames//===----------------------------------------------------------------------===// 10273dc7c5138d219048d69952bead22f75efb984fa3Lang Hames 1028fd6d3217d3b577e704ff4826775b5938c23b9e73Lang Hames// HMEditor is a toolkit used by handleMove to trim or extend live intervals. 10293dc7c5138d219048d69952bead22f75efb984fa3Lang Hamesclass LiveIntervals::HMEditor { 10303dc7c5138d219048d69952bead22f75efb984fa3Lang Hamesprivate: 1031ecb50624d1e99596fdb289200cd1473cec84e097Lang Hames LiveIntervals& LIS; 1032ecb50624d1e99596fdb289200cd1473cec84e097Lang Hames const MachineRegisterInfo& MRI; 1033ecb50624d1e99596fdb289200cd1473cec84e097Lang Hames const TargetRegisterInfo& TRI; 1034ecb50624d1e99596fdb289200cd1473cec84e097Lang Hames SlotIndex NewIdx; 10353dc7c5138d219048d69952bead22f75efb984fa3Lang Hames 103655fed62c9eca0c8ebcaa6cc2fd65a173d37b3951Lang Hames typedef std::pair<LiveInterval*, LiveRange*> IntRangePair; 103755fed62c9eca0c8ebcaa6cc2fd65a173d37b3951Lang Hames typedef DenseSet<IntRangePair> RangeSet; 103855fed62c9eca0c8ebcaa6cc2fd65a173d37b3951Lang Hames 10396aceab139205255ac44182f51819b9b8716cf477Lang Hames struct RegRanges { 10406aceab139205255ac44182f51819b9b8716cf477Lang Hames LiveRange* Use; 10416aceab139205255ac44182f51819b9b8716cf477Lang Hames LiveRange* EC; 10426aceab139205255ac44182f51819b9b8716cf477Lang Hames LiveRange* Dead; 10436aceab139205255ac44182f51819b9b8716cf477Lang Hames LiveRange* Def; 10446aceab139205255ac44182f51819b9b8716cf477Lang Hames RegRanges() : Use(0), EC(0), Dead(0), Def(0) {} 10456aceab139205255ac44182f51819b9b8716cf477Lang Hames }; 10466aceab139205255ac44182f51819b9b8716cf477Lang Hames typedef DenseMap<unsigned, RegRanges> BundleRanges; 10476aceab139205255ac44182f51819b9b8716cf477Lang Hames 10483dc7c5138d219048d69952bead22f75efb984fa3Lang Hamespublic: 1049ecb50624d1e99596fdb289200cd1473cec84e097Lang Hames HMEditor(LiveIntervals& LIS, const MachineRegisterInfo& MRI, 1050ecb50624d1e99596fdb289200cd1473cec84e097Lang Hames const TargetRegisterInfo& TRI, SlotIndex NewIdx) 1051ecb50624d1e99596fdb289200cd1473cec84e097Lang Hames : LIS(LIS), MRI(MRI), TRI(TRI), NewIdx(NewIdx) {} 1052ecb50624d1e99596fdb289200cd1473cec84e097Lang Hames 105355fed62c9eca0c8ebcaa6cc2fd65a173d37b3951Lang Hames // Update intervals for all operands of MI from OldIdx to NewIdx. 105455fed62c9eca0c8ebcaa6cc2fd65a173d37b3951Lang Hames // This assumes that MI used to be at OldIdx, and now resides at 105555fed62c9eca0c8ebcaa6cc2fd65a173d37b3951Lang Hames // NewIdx. 10564586d257abf13b57d115d6bac9fb38ddc811acafLang Hames void moveAllRangesFrom(MachineInstr* MI, SlotIndex OldIdx) { 10576aceab139205255ac44182f51819b9b8716cf477Lang Hames assert(NewIdx != OldIdx && "No-op move? That's a bit strange."); 10586aceab139205255ac44182f51819b9b8716cf477Lang Hames 105955fed62c9eca0c8ebcaa6cc2fd65a173d37b3951Lang Hames // Collect the operands. 106055fed62c9eca0c8ebcaa6cc2fd65a173d37b3951Lang Hames RangeSet Entering, Internal, Exiting; 1061ac027144e8e22563c9bb057598c710aac57c072fLang Hames bool hasRegMaskOp = false; 1062ac027144e8e22563c9bb057598c710aac57c072fLang Hames collectRanges(MI, Entering, Internal, Exiting, hasRegMaskOp, OldIdx); 106355fed62c9eca0c8ebcaa6cc2fd65a173d37b3951Lang Hames 106455fed62c9eca0c8ebcaa6cc2fd65a173d37b3951Lang Hames moveAllEnteringFrom(OldIdx, Entering); 106555fed62c9eca0c8ebcaa6cc2fd65a173d37b3951Lang Hames moveAllInternalFrom(OldIdx, Internal); 106655fed62c9eca0c8ebcaa6cc2fd65a173d37b3951Lang Hames moveAllExitingFrom(OldIdx, Exiting); 10673dc7c5138d219048d69952bead22f75efb984fa3Lang Hames 1068ac027144e8e22563c9bb057598c710aac57c072fLang Hames if (hasRegMaskOp) 1069ac027144e8e22563c9bb057598c710aac57c072fLang Hames updateRegMaskSlots(OldIdx); 1070ac027144e8e22563c9bb057598c710aac57c072fLang Hames 107155fed62c9eca0c8ebcaa6cc2fd65a173d37b3951Lang Hames#ifndef NDEBUG 107255fed62c9eca0c8ebcaa6cc2fd65a173d37b3951Lang Hames LIValidator validator; 107355fed62c9eca0c8ebcaa6cc2fd65a173d37b3951Lang Hames std::for_each(Entering.begin(), Entering.end(), validator); 107455fed62c9eca0c8ebcaa6cc2fd65a173d37b3951Lang Hames std::for_each(Internal.begin(), Internal.end(), validator); 107555fed62c9eca0c8ebcaa6cc2fd65a173d37b3951Lang Hames std::for_each(Exiting.begin(), Exiting.end(), validator); 10766aceab139205255ac44182f51819b9b8716cf477Lang Hames assert(validator.rangesOk() && "moveAllOperandsFrom broke liveness."); 107755fed62c9eca0c8ebcaa6cc2fd65a173d37b3951Lang Hames#endif 107855fed62c9eca0c8ebcaa6cc2fd65a173d37b3951Lang Hames 10793dc7c5138d219048d69952bead22f75efb984fa3Lang Hames } 10803dc7c5138d219048d69952bead22f75efb984fa3Lang Hames 10814586d257abf13b57d115d6bac9fb38ddc811acafLang Hames // Update intervals for all operands of MI to refer to BundleStart's 10824586d257abf13b57d115d6bac9fb38ddc811acafLang Hames // SlotIndex. 10834586d257abf13b57d115d6bac9fb38ddc811acafLang Hames void moveAllRangesInto(MachineInstr* MI, MachineInstr* BundleStart) { 10846aceab139205255ac44182f51819b9b8716cf477Lang Hames if (MI == BundleStart) 10856aceab139205255ac44182f51819b9b8716cf477Lang Hames return; // Bundling instr with itself - nothing to do. 10866aceab139205255ac44182f51819b9b8716cf477Lang Hames 1087fd6d3217d3b577e704ff4826775b5938c23b9e73Lang Hames SlotIndex OldIdx = LIS.getSlotIndexes()->getInstructionIndex(MI); 1088fd6d3217d3b577e704ff4826775b5938c23b9e73Lang Hames assert(LIS.getSlotIndexes()->getInstructionFromIndex(OldIdx) == MI && 1089fd6d3217d3b577e704ff4826775b5938c23b9e73Lang Hames "SlotIndex <-> Instruction mapping broken for MI"); 1090fd6d3217d3b577e704ff4826775b5938c23b9e73Lang Hames 10914586d257abf13b57d115d6bac9fb38ddc811acafLang Hames // Collect all ranges already in the bundle. 10924586d257abf13b57d115d6bac9fb38ddc811acafLang Hames MachineBasicBlock::instr_iterator BII(BundleStart); 10936aceab139205255ac44182f51819b9b8716cf477Lang Hames RangeSet Entering, Internal, Exiting; 10946aceab139205255ac44182f51819b9b8716cf477Lang Hames bool hasRegMaskOp = false; 10954586d257abf13b57d115d6bac9fb38ddc811acafLang Hames collectRanges(BII, Entering, Internal, Exiting, hasRegMaskOp, NewIdx); 10964586d257abf13b57d115d6bac9fb38ddc811acafLang Hames assert(!hasRegMaskOp && "Can't have RegMask operand in bundle."); 10974586d257abf13b57d115d6bac9fb38ddc811acafLang Hames for (++BII; &*BII == MI || BII->isInsideBundle(); ++BII) { 10984586d257abf13b57d115d6bac9fb38ddc811acafLang Hames if (&*BII == MI) 10994586d257abf13b57d115d6bac9fb38ddc811acafLang Hames continue; 11004586d257abf13b57d115d6bac9fb38ddc811acafLang Hames collectRanges(BII, Entering, Internal, Exiting, hasRegMaskOp, NewIdx); 11014586d257abf13b57d115d6bac9fb38ddc811acafLang Hames assert(!hasRegMaskOp && "Can't have RegMask operand in bundle."); 11024586d257abf13b57d115d6bac9fb38ddc811acafLang Hames } 11034586d257abf13b57d115d6bac9fb38ddc811acafLang Hames 11044586d257abf13b57d115d6bac9fb38ddc811acafLang Hames BundleRanges BR = createBundleRanges(Entering, Internal, Exiting); 11054586d257abf13b57d115d6bac9fb38ddc811acafLang Hames 11066aceab139205255ac44182f51819b9b8716cf477Lang Hames collectRanges(MI, Entering, Internal, Exiting, hasRegMaskOp, OldIdx); 11074586d257abf13b57d115d6bac9fb38ddc811acafLang Hames assert(!hasRegMaskOp && "Can't have RegMask operand in bundle."); 11084586d257abf13b57d115d6bac9fb38ddc811acafLang Hames 11094586d257abf13b57d115d6bac9fb38ddc811acafLang Hames DEBUG(dbgs() << "Entering: " << Entering.size() << "\n"); 11104586d257abf13b57d115d6bac9fb38ddc811acafLang Hames DEBUG(dbgs() << "Internal: " << Internal.size() << "\n"); 11114586d257abf13b57d115d6bac9fb38ddc811acafLang Hames DEBUG(dbgs() << "Exiting: " << Exiting.size() << "\n"); 11126aceab139205255ac44182f51819b9b8716cf477Lang Hames 11136aceab139205255ac44182f51819b9b8716cf477Lang Hames moveAllEnteringFromInto(OldIdx, Entering, BR); 11146aceab139205255ac44182f51819b9b8716cf477Lang Hames moveAllInternalFromInto(OldIdx, Internal, BR); 11156aceab139205255ac44182f51819b9b8716cf477Lang Hames moveAllExitingFromInto(OldIdx, Exiting, BR); 11166aceab139205255ac44182f51819b9b8716cf477Lang Hames 11174586d257abf13b57d115d6bac9fb38ddc811acafLang Hames 11186aceab139205255ac44182f51819b9b8716cf477Lang Hames#ifndef NDEBUG 11196aceab139205255ac44182f51819b9b8716cf477Lang Hames LIValidator validator; 11206aceab139205255ac44182f51819b9b8716cf477Lang Hames std::for_each(Entering.begin(), Entering.end(), validator); 11216aceab139205255ac44182f51819b9b8716cf477Lang Hames std::for_each(Internal.begin(), Internal.end(), validator); 11226aceab139205255ac44182f51819b9b8716cf477Lang Hames std::for_each(Exiting.begin(), Exiting.end(), validator); 11236aceab139205255ac44182f51819b9b8716cf477Lang Hames assert(validator.rangesOk() && "moveAllOperandsInto broke liveness."); 11246aceab139205255ac44182f51819b9b8716cf477Lang Hames#endif 11256aceab139205255ac44182f51819b9b8716cf477Lang Hames } 11266aceab139205255ac44182f51819b9b8716cf477Lang Hames 112755fed62c9eca0c8ebcaa6cc2fd65a173d37b3951Lang Hamesprivate: 112855fed62c9eca0c8ebcaa6cc2fd65a173d37b3951Lang Hames 112955fed62c9eca0c8ebcaa6cc2fd65a173d37b3951Lang Hames#ifndef NDEBUG 113055fed62c9eca0c8ebcaa6cc2fd65a173d37b3951Lang Hames class LIValidator { 113155fed62c9eca0c8ebcaa6cc2fd65a173d37b3951Lang Hames private: 113255fed62c9eca0c8ebcaa6cc2fd65a173d37b3951Lang Hames DenseSet<const LiveInterval*> Checked, Bogus; 113355fed62c9eca0c8ebcaa6cc2fd65a173d37b3951Lang Hames public: 113455fed62c9eca0c8ebcaa6cc2fd65a173d37b3951Lang Hames void operator()(const IntRangePair& P) { 113555fed62c9eca0c8ebcaa6cc2fd65a173d37b3951Lang Hames const LiveInterval* LI = P.first; 113655fed62c9eca0c8ebcaa6cc2fd65a173d37b3951Lang Hames if (Checked.count(LI)) 113755fed62c9eca0c8ebcaa6cc2fd65a173d37b3951Lang Hames return; 113855fed62c9eca0c8ebcaa6cc2fd65a173d37b3951Lang Hames Checked.insert(LI); 113955fed62c9eca0c8ebcaa6cc2fd65a173d37b3951Lang Hames if (LI->empty()) 114055fed62c9eca0c8ebcaa6cc2fd65a173d37b3951Lang Hames return; 114155fed62c9eca0c8ebcaa6cc2fd65a173d37b3951Lang Hames SlotIndex LastEnd = LI->begin()->start; 114255fed62c9eca0c8ebcaa6cc2fd65a173d37b3951Lang Hames for (LiveInterval::const_iterator LRI = LI->begin(), LRE = LI->end(); 114355fed62c9eca0c8ebcaa6cc2fd65a173d37b3951Lang Hames LRI != LRE; ++LRI) { 114455fed62c9eca0c8ebcaa6cc2fd65a173d37b3951Lang Hames const LiveRange& LR = *LRI; 114555fed62c9eca0c8ebcaa6cc2fd65a173d37b3951Lang Hames if (LastEnd > LR.start || LR.start >= LR.end) 114655fed62c9eca0c8ebcaa6cc2fd65a173d37b3951Lang Hames Bogus.insert(LI); 114755fed62c9eca0c8ebcaa6cc2fd65a173d37b3951Lang Hames LastEnd = LR.end; 11483dc7c5138d219048d69952bead22f75efb984fa3Lang Hames } 11493dc7c5138d219048d69952bead22f75efb984fa3Lang Hames } 11503dc7c5138d219048d69952bead22f75efb984fa3Lang Hames 115155fed62c9eca0c8ebcaa6cc2fd65a173d37b3951Lang Hames bool rangesOk() const { 115255fed62c9eca0c8ebcaa6cc2fd65a173d37b3951Lang Hames return Bogus.empty(); 11533dc7c5138d219048d69952bead22f75efb984fa3Lang Hames } 115455fed62c9eca0c8ebcaa6cc2fd65a173d37b3951Lang Hames }; 115555fed62c9eca0c8ebcaa6cc2fd65a173d37b3951Lang Hames#endif 11563dc7c5138d219048d69952bead22f75efb984fa3Lang Hames 115755fed62c9eca0c8ebcaa6cc2fd65a173d37b3951Lang Hames // Collect IntRangePairs for all operands of MI that may need fixing. 115855fed62c9eca0c8ebcaa6cc2fd65a173d37b3951Lang Hames // Treat's MI's index as OldIdx (regardless of what it is in SlotIndexes' 115955fed62c9eca0c8ebcaa6cc2fd65a173d37b3951Lang Hames // maps). 116055fed62c9eca0c8ebcaa6cc2fd65a173d37b3951Lang Hames void collectRanges(MachineInstr* MI, RangeSet& Entering, RangeSet& Internal, 1161ac027144e8e22563c9bb057598c710aac57c072fLang Hames RangeSet& Exiting, bool& hasRegMaskOp, SlotIndex OldIdx) { 1162ac027144e8e22563c9bb057598c710aac57c072fLang Hames hasRegMaskOp = false; 1163ecb50624d1e99596fdb289200cd1473cec84e097Lang Hames for (MachineInstr::mop_iterator MOI = MI->operands_begin(), 1164ecb50624d1e99596fdb289200cd1473cec84e097Lang Hames MOE = MI->operands_end(); 1165ecb50624d1e99596fdb289200cd1473cec84e097Lang Hames MOI != MOE; ++MOI) { 1166ecb50624d1e99596fdb289200cd1473cec84e097Lang Hames const MachineOperand& MO = *MOI; 1167ac027144e8e22563c9bb057598c710aac57c072fLang Hames 1168ac027144e8e22563c9bb057598c710aac57c072fLang Hames if (MO.isRegMask()) { 1169ac027144e8e22563c9bb057598c710aac57c072fLang Hames hasRegMaskOp = true; 1170ac027144e8e22563c9bb057598c710aac57c072fLang Hames continue; 1171ac027144e8e22563c9bb057598c710aac57c072fLang Hames } 1172ac027144e8e22563c9bb057598c710aac57c072fLang Hames 1173ecb50624d1e99596fdb289200cd1473cec84e097Lang Hames if (!MO.isReg() || MO.getReg() == 0) 11743dc7c5138d219048d69952bead22f75efb984fa3Lang Hames continue; 11753dc7c5138d219048d69952bead22f75efb984fa3Lang Hames 1176ecb50624d1e99596fdb289200cd1473cec84e097Lang Hames unsigned Reg = MO.getReg(); 11773dc7c5138d219048d69952bead22f75efb984fa3Lang Hames 11783dc7c5138d219048d69952bead22f75efb984fa3Lang Hames // TODO: Currently we're skipping uses that are reserved or have no 11793dc7c5138d219048d69952bead22f75efb984fa3Lang Hames // interval, but we're not updating their kills. This should be 11803dc7c5138d219048d69952bead22f75efb984fa3Lang Hames // fixed. 1181ecb50624d1e99596fdb289200cd1473cec84e097Lang Hames if (!LIS.hasInterval(Reg) || 1182ecb50624d1e99596fdb289200cd1473cec84e097Lang Hames (TargetRegisterInfo::isPhysicalRegister(Reg) && LIS.isReserved(Reg))) 11833dc7c5138d219048d69952bead22f75efb984fa3Lang Hames continue; 11843dc7c5138d219048d69952bead22f75efb984fa3Lang Hames 118555fed62c9eca0c8ebcaa6cc2fd65a173d37b3951Lang Hames LiveInterval* LI = &LIS.getInterval(Reg); 118655fed62c9eca0c8ebcaa6cc2fd65a173d37b3951Lang Hames 118755fed62c9eca0c8ebcaa6cc2fd65a173d37b3951Lang Hames if (MO.readsReg()) { 118855fed62c9eca0c8ebcaa6cc2fd65a173d37b3951Lang Hames LiveRange* LR = LI->getLiveRangeContaining(OldIdx); 118955fed62c9eca0c8ebcaa6cc2fd65a173d37b3951Lang Hames if (LR != 0) 119055fed62c9eca0c8ebcaa6cc2fd65a173d37b3951Lang Hames Entering.insert(std::make_pair(LI, LR)); 11913dc7c5138d219048d69952bead22f75efb984fa3Lang Hames } 1192ecb50624d1e99596fdb289200cd1473cec84e097Lang Hames if (MO.isDef()) { 119355fed62c9eca0c8ebcaa6cc2fd65a173d37b3951Lang Hames if (MO.isEarlyClobber()) { 119455fed62c9eca0c8ebcaa6cc2fd65a173d37b3951Lang Hames LiveRange* LR = LI->getLiveRangeContaining(OldIdx.getRegSlot(true)); 119555fed62c9eca0c8ebcaa6cc2fd65a173d37b3951Lang Hames assert(LR != 0 && "No EC range?"); 119655fed62c9eca0c8ebcaa6cc2fd65a173d37b3951Lang Hames if (LR->end > OldIdx.getDeadSlot()) 119755fed62c9eca0c8ebcaa6cc2fd65a173d37b3951Lang Hames Exiting.insert(std::make_pair(LI, LR)); 119855fed62c9eca0c8ebcaa6cc2fd65a173d37b3951Lang Hames else 1199ac027144e8e22563c9bb057598c710aac57c072fLang Hames Internal.insert(std::make_pair(LI, LR)); 120055fed62c9eca0c8ebcaa6cc2fd65a173d37b3951Lang Hames } else if (MO.isDead()) { 120155fed62c9eca0c8ebcaa6cc2fd65a173d37b3951Lang Hames LiveRange* LR = LI->getLiveRangeContaining(OldIdx.getRegSlot()); 120255fed62c9eca0c8ebcaa6cc2fd65a173d37b3951Lang Hames assert(LR != 0 && "No dead-def range?"); 120355fed62c9eca0c8ebcaa6cc2fd65a173d37b3951Lang Hames Internal.insert(std::make_pair(LI, LR)); 12043dc7c5138d219048d69952bead22f75efb984fa3Lang Hames } else { 120555fed62c9eca0c8ebcaa6cc2fd65a173d37b3951Lang Hames LiveRange* LR = LI->getLiveRangeContaining(OldIdx.getDeadSlot()); 120655fed62c9eca0c8ebcaa6cc2fd65a173d37b3951Lang Hames assert(LR && LR->end > OldIdx.getDeadSlot() && 120755fed62c9eca0c8ebcaa6cc2fd65a173d37b3951Lang Hames "Non-dead-def should have live range exiting."); 120855fed62c9eca0c8ebcaa6cc2fd65a173d37b3951Lang Hames Exiting.insert(std::make_pair(LI, LR)); 12093dc7c5138d219048d69952bead22f75efb984fa3Lang Hames } 12103dc7c5138d219048d69952bead22f75efb984fa3Lang Hames } 12113dc7c5138d219048d69952bead22f75efb984fa3Lang Hames } 12123dc7c5138d219048d69952bead22f75efb984fa3Lang Hames } 12133dc7c5138d219048d69952bead22f75efb984fa3Lang Hames 12144586d257abf13b57d115d6bac9fb38ddc811acafLang Hames // Collect IntRangePairs for all operands of MI that may need fixing. 12154586d257abf13b57d115d6bac9fb38ddc811acafLang Hames void collectRangesInBundle(MachineInstr* MI, RangeSet& Entering, 12164586d257abf13b57d115d6bac9fb38ddc811acafLang Hames RangeSet& Exiting, SlotIndex MIStartIdx, 12174586d257abf13b57d115d6bac9fb38ddc811acafLang Hames SlotIndex MIEndIdx) { 12184586d257abf13b57d115d6bac9fb38ddc811acafLang Hames for (MachineInstr::mop_iterator MOI = MI->operands_begin(), 12194586d257abf13b57d115d6bac9fb38ddc811acafLang Hames MOE = MI->operands_end(); 12204586d257abf13b57d115d6bac9fb38ddc811acafLang Hames MOI != MOE; ++MOI) { 12214586d257abf13b57d115d6bac9fb38ddc811acafLang Hames const MachineOperand& MO = *MOI; 12224586d257abf13b57d115d6bac9fb38ddc811acafLang Hames assert(!MO.isRegMask() && "Can't have RegMasks in bundles."); 12234586d257abf13b57d115d6bac9fb38ddc811acafLang Hames if (!MO.isReg() || MO.getReg() == 0) 12244586d257abf13b57d115d6bac9fb38ddc811acafLang Hames continue; 12256aceab139205255ac44182f51819b9b8716cf477Lang Hames 12264586d257abf13b57d115d6bac9fb38ddc811acafLang Hames unsigned Reg = MO.getReg(); 12274586d257abf13b57d115d6bac9fb38ddc811acafLang Hames 12284586d257abf13b57d115d6bac9fb38ddc811acafLang Hames // TODO: Currently we're skipping uses that are reserved or have no 12294586d257abf13b57d115d6bac9fb38ddc811acafLang Hames // interval, but we're not updating their kills. This should be 12304586d257abf13b57d115d6bac9fb38ddc811acafLang Hames // fixed. 12314586d257abf13b57d115d6bac9fb38ddc811acafLang Hames if (!LIS.hasInterval(Reg) || 12324586d257abf13b57d115d6bac9fb38ddc811acafLang Hames (TargetRegisterInfo::isPhysicalRegister(Reg) && LIS.isReserved(Reg))) 12334586d257abf13b57d115d6bac9fb38ddc811acafLang Hames continue; 12344586d257abf13b57d115d6bac9fb38ddc811acafLang Hames 12354586d257abf13b57d115d6bac9fb38ddc811acafLang Hames LiveInterval* LI = &LIS.getInterval(Reg); 12364586d257abf13b57d115d6bac9fb38ddc811acafLang Hames 12374586d257abf13b57d115d6bac9fb38ddc811acafLang Hames if (MO.readsReg()) { 12384586d257abf13b57d115d6bac9fb38ddc811acafLang Hames LiveRange* LR = LI->getLiveRangeContaining(MIStartIdx); 12394586d257abf13b57d115d6bac9fb38ddc811acafLang Hames if (LR != 0) 12404586d257abf13b57d115d6bac9fb38ddc811acafLang Hames Entering.insert(std::make_pair(LI, LR)); 12414586d257abf13b57d115d6bac9fb38ddc811acafLang Hames } 12424586d257abf13b57d115d6bac9fb38ddc811acafLang Hames if (MO.isDef()) { 12434586d257abf13b57d115d6bac9fb38ddc811acafLang Hames assert(!MO.isEarlyClobber() && "Early clobbers not allowed in bundles."); 12444586d257abf13b57d115d6bac9fb38ddc811acafLang Hames assert(!MO.isDead() && "Dead-defs not allowed in bundles."); 12454586d257abf13b57d115d6bac9fb38ddc811acafLang Hames LiveRange* LR = LI->getLiveRangeContaining(MIEndIdx.getDeadSlot()); 12464586d257abf13b57d115d6bac9fb38ddc811acafLang Hames assert(LR != 0 && "Internal ranges not allowed in bundles."); 12474586d257abf13b57d115d6bac9fb38ddc811acafLang Hames Exiting.insert(std::make_pair(LI, LR)); 12484586d257abf13b57d115d6bac9fb38ddc811acafLang Hames } 12496aceab139205255ac44182f51819b9b8716cf477Lang Hames } 12504586d257abf13b57d115d6bac9fb38ddc811acafLang Hames } 12514586d257abf13b57d115d6bac9fb38ddc811acafLang Hames 12524586d257abf13b57d115d6bac9fb38ddc811acafLang Hames BundleRanges createBundleRanges(RangeSet& Entering, RangeSet& Internal, RangeSet& Exiting) { 12534586d257abf13b57d115d6bac9fb38ddc811acafLang Hames BundleRanges BR; 12546aceab139205255ac44182f51819b9b8716cf477Lang Hames 12556aceab139205255ac44182f51819b9b8716cf477Lang Hames for (RangeSet::iterator EI = Entering.begin(), EE = Entering.end(); 1256fd6d3217d3b577e704ff4826775b5938c23b9e73Lang Hames EI != EE; ++EI) { 12576aceab139205255ac44182f51819b9b8716cf477Lang Hames LiveInterval* LI = EI->first; 12586aceab139205255ac44182f51819b9b8716cf477Lang Hames LiveRange* LR = EI->second; 12596aceab139205255ac44182f51819b9b8716cf477Lang Hames BR[LI->reg].Use = LR; 12606aceab139205255ac44182f51819b9b8716cf477Lang Hames } 12616aceab139205255ac44182f51819b9b8716cf477Lang Hames 12626aceab139205255ac44182f51819b9b8716cf477Lang Hames for (RangeSet::iterator II = Internal.begin(), IE = Internal.end(); 1263fd6d3217d3b577e704ff4826775b5938c23b9e73Lang Hames II != IE; ++II) { 12646aceab139205255ac44182f51819b9b8716cf477Lang Hames LiveInterval* LI = II->first; 12656aceab139205255ac44182f51819b9b8716cf477Lang Hames LiveRange* LR = II->second; 12666aceab139205255ac44182f51819b9b8716cf477Lang Hames if (LR->end.isDead()) { 12676aceab139205255ac44182f51819b9b8716cf477Lang Hames BR[LI->reg].Dead = LR; 12686aceab139205255ac44182f51819b9b8716cf477Lang Hames } else { 12696aceab139205255ac44182f51819b9b8716cf477Lang Hames BR[LI->reg].EC = LR; 12706aceab139205255ac44182f51819b9b8716cf477Lang Hames } 12716aceab139205255ac44182f51819b9b8716cf477Lang Hames } 12726aceab139205255ac44182f51819b9b8716cf477Lang Hames 12736aceab139205255ac44182f51819b9b8716cf477Lang Hames for (RangeSet::iterator EI = Exiting.begin(), EE = Exiting.end(); 1274fd6d3217d3b577e704ff4826775b5938c23b9e73Lang Hames EI != EE; ++EI) { 12756aceab139205255ac44182f51819b9b8716cf477Lang Hames LiveInterval* LI = EI->first; 12766aceab139205255ac44182f51819b9b8716cf477Lang Hames LiveRange* LR = EI->second; 12776aceab139205255ac44182f51819b9b8716cf477Lang Hames BR[LI->reg].Def = LR; 12786aceab139205255ac44182f51819b9b8716cf477Lang Hames } 12796aceab139205255ac44182f51819b9b8716cf477Lang Hames 12806aceab139205255ac44182f51819b9b8716cf477Lang Hames return BR; 12816aceab139205255ac44182f51819b9b8716cf477Lang Hames } 12826aceab139205255ac44182f51819b9b8716cf477Lang Hames 1283ecb50624d1e99596fdb289200cd1473cec84e097Lang Hames void moveKillFlags(unsigned reg, SlotIndex OldIdx, SlotIndex newKillIdx) { 1284ecb50624d1e99596fdb289200cd1473cec84e097Lang Hames MachineInstr* OldKillMI = LIS.getInstructionFromIndex(OldIdx); 1285ecb50624d1e99596fdb289200cd1473cec84e097Lang Hames if (!OldKillMI->killsRegister(reg)) 12863dc7c5138d219048d69952bead22f75efb984fa3Lang Hames return; // Bail out if we don't have kill flags on the old register. 1287ecb50624d1e99596fdb289200cd1473cec84e097Lang Hames MachineInstr* NewKillMI = LIS.getInstructionFromIndex(newKillIdx); 1288ecb50624d1e99596fdb289200cd1473cec84e097Lang Hames assert(OldKillMI->killsRegister(reg) && "Old 'kill' instr isn't a kill."); 1289ecb50624d1e99596fdb289200cd1473cec84e097Lang Hames assert(!NewKillMI->killsRegister(reg) && "New kill instr is already a kill."); 1290ecb50624d1e99596fdb289200cd1473cec84e097Lang Hames OldKillMI->clearRegisterKills(reg, &TRI); 1291ecb50624d1e99596fdb289200cd1473cec84e097Lang Hames NewKillMI->addRegisterKilled(reg, &TRI); 12923dc7c5138d219048d69952bead22f75efb984fa3Lang Hames } 12933dc7c5138d219048d69952bead22f75efb984fa3Lang Hames 129455fed62c9eca0c8ebcaa6cc2fd65a173d37b3951Lang Hames void updateRegMaskSlots(SlotIndex OldIdx) { 129555fed62c9eca0c8ebcaa6cc2fd65a173d37b3951Lang Hames SmallVectorImpl<SlotIndex>::iterator RI = 129655fed62c9eca0c8ebcaa6cc2fd65a173d37b3951Lang Hames std::lower_bound(LIS.RegMaskSlots.begin(), LIS.RegMaskSlots.end(), 129755fed62c9eca0c8ebcaa6cc2fd65a173d37b3951Lang Hames OldIdx); 129855fed62c9eca0c8ebcaa6cc2fd65a173d37b3951Lang Hames assert(*RI == OldIdx && "No RegMask at OldIdx."); 129955fed62c9eca0c8ebcaa6cc2fd65a173d37b3951Lang Hames *RI = NewIdx; 130055fed62c9eca0c8ebcaa6cc2fd65a173d37b3951Lang Hames assert(*prior(RI) < *RI && *RI < *next(RI) && 130155fed62c9eca0c8ebcaa6cc2fd65a173d37b3951Lang Hames "RegSlots out of order. Did you move one call across another?"); 13023dc7c5138d219048d69952bead22f75efb984fa3Lang Hames } 13033dc7c5138d219048d69952bead22f75efb984fa3Lang Hames 130455fed62c9eca0c8ebcaa6cc2fd65a173d37b3951Lang Hames // Return the last use of reg between NewIdx and OldIdx. 130555fed62c9eca0c8ebcaa6cc2fd65a173d37b3951Lang Hames SlotIndex findLastUseBefore(unsigned Reg, SlotIndex OldIdx) { 130655fed62c9eca0c8ebcaa6cc2fd65a173d37b3951Lang Hames SlotIndex LastUse = NewIdx; 130755fed62c9eca0c8ebcaa6cc2fd65a173d37b3951Lang Hames for (MachineRegisterInfo::use_nodbg_iterator 130855fed62c9eca0c8ebcaa6cc2fd65a173d37b3951Lang Hames UI = MRI.use_nodbg_begin(Reg), 130955fed62c9eca0c8ebcaa6cc2fd65a173d37b3951Lang Hames UE = MRI.use_nodbg_end(); 1310038d2d5cede26b1ab63a732348b60ffc430dd7b0Lang Hames UI != UE; UI.skipInstruction()) { 131155fed62c9eca0c8ebcaa6cc2fd65a173d37b3951Lang Hames const MachineInstr* MI = &*UI; 131255fed62c9eca0c8ebcaa6cc2fd65a173d37b3951Lang Hames SlotIndex InstSlot = LIS.getSlotIndexes()->getInstructionIndex(MI); 131355fed62c9eca0c8ebcaa6cc2fd65a173d37b3951Lang Hames if (InstSlot > LastUse && InstSlot < OldIdx) 131455fed62c9eca0c8ebcaa6cc2fd65a173d37b3951Lang Hames LastUse = InstSlot; 13153dc7c5138d219048d69952bead22f75efb984fa3Lang Hames } 131655fed62c9eca0c8ebcaa6cc2fd65a173d37b3951Lang Hames return LastUse; 13173dc7c5138d219048d69952bead22f75efb984fa3Lang Hames } 13183dc7c5138d219048d69952bead22f75efb984fa3Lang Hames 131955fed62c9eca0c8ebcaa6cc2fd65a173d37b3951Lang Hames void moveEnteringUpFrom(SlotIndex OldIdx, IntRangePair& P) { 132055fed62c9eca0c8ebcaa6cc2fd65a173d37b3951Lang Hames LiveInterval* LI = P.first; 132155fed62c9eca0c8ebcaa6cc2fd65a173d37b3951Lang Hames LiveRange* LR = P.second; 132255fed62c9eca0c8ebcaa6cc2fd65a173d37b3951Lang Hames bool LiveThrough = LR->end > OldIdx.getRegSlot(); 132355fed62c9eca0c8ebcaa6cc2fd65a173d37b3951Lang Hames if (LiveThrough) 132455fed62c9eca0c8ebcaa6cc2fd65a173d37b3951Lang Hames return; 132555fed62c9eca0c8ebcaa6cc2fd65a173d37b3951Lang Hames SlotIndex LastUse = findLastUseBefore(LI->reg, OldIdx); 132655fed62c9eca0c8ebcaa6cc2fd65a173d37b3951Lang Hames if (LastUse != NewIdx) 132755fed62c9eca0c8ebcaa6cc2fd65a173d37b3951Lang Hames moveKillFlags(LI->reg, NewIdx, LastUse); 13286aceab139205255ac44182f51819b9b8716cf477Lang Hames LR->end = LastUse.getRegSlot(); 13293dc7c5138d219048d69952bead22f75efb984fa3Lang Hames } 13303dc7c5138d219048d69952bead22f75efb984fa3Lang Hames 133155fed62c9eca0c8ebcaa6cc2fd65a173d37b3951Lang Hames void moveEnteringDownFrom(SlotIndex OldIdx, IntRangePair& P) { 133255fed62c9eca0c8ebcaa6cc2fd65a173d37b3951Lang Hames LiveInterval* LI = P.first; 133355fed62c9eca0c8ebcaa6cc2fd65a173d37b3951Lang Hames LiveRange* LR = P.second; 13344a0b2d658ae9e296598f8c8ac36c7fe571a7eec5Lang Hames if (NewIdx > LR->end) { 13354a0b2d658ae9e296598f8c8ac36c7fe571a7eec5Lang Hames moveKillFlags(LI->reg, LR->end, NewIdx); 13364a0b2d658ae9e296598f8c8ac36c7fe571a7eec5Lang Hames LR->end = NewIdx.getRegSlot(); 13373dc7c5138d219048d69952bead22f75efb984fa3Lang Hames } 13383dc7c5138d219048d69952bead22f75efb984fa3Lang Hames } 13393dc7c5138d219048d69952bead22f75efb984fa3Lang Hames 134055fed62c9eca0c8ebcaa6cc2fd65a173d37b3951Lang Hames void moveAllEnteringFrom(SlotIndex OldIdx, RangeSet& Entering) { 134155fed62c9eca0c8ebcaa6cc2fd65a173d37b3951Lang Hames bool GoingUp = NewIdx < OldIdx; 134255fed62c9eca0c8ebcaa6cc2fd65a173d37b3951Lang Hames 134355fed62c9eca0c8ebcaa6cc2fd65a173d37b3951Lang Hames if (GoingUp) { 134455fed62c9eca0c8ebcaa6cc2fd65a173d37b3951Lang Hames for (RangeSet::iterator EI = Entering.begin(), EE = Entering.end(); 134555fed62c9eca0c8ebcaa6cc2fd65a173d37b3951Lang Hames EI != EE; ++EI) 134655fed62c9eca0c8ebcaa6cc2fd65a173d37b3951Lang Hames moveEnteringUpFrom(OldIdx, *EI); 134755fed62c9eca0c8ebcaa6cc2fd65a173d37b3951Lang Hames } else { 134855fed62c9eca0c8ebcaa6cc2fd65a173d37b3951Lang Hames for (RangeSet::iterator EI = Entering.begin(), EE = Entering.end(); 134955fed62c9eca0c8ebcaa6cc2fd65a173d37b3951Lang Hames EI != EE; ++EI) 135055fed62c9eca0c8ebcaa6cc2fd65a173d37b3951Lang Hames moveEnteringDownFrom(OldIdx, *EI); 13513dc7c5138d219048d69952bead22f75efb984fa3Lang Hames } 13523dc7c5138d219048d69952bead22f75efb984fa3Lang Hames } 1353fbc8dd306aa7699a866db278db08d842762b2dc2Lang Hames 135455fed62c9eca0c8ebcaa6cc2fd65a173d37b3951Lang Hames void moveInternalFrom(SlotIndex OldIdx, IntRangePair& P) { 135555fed62c9eca0c8ebcaa6cc2fd65a173d37b3951Lang Hames LiveInterval* LI = P.first; 135655fed62c9eca0c8ebcaa6cc2fd65a173d37b3951Lang Hames LiveRange* LR = P.second; 135755fed62c9eca0c8ebcaa6cc2fd65a173d37b3951Lang Hames assert(OldIdx < LR->start && LR->start < OldIdx.getDeadSlot() && 135855fed62c9eca0c8ebcaa6cc2fd65a173d37b3951Lang Hames LR->end <= OldIdx.getDeadSlot() && 135955fed62c9eca0c8ebcaa6cc2fd65a173d37b3951Lang Hames "Range should be internal to OldIdx."); 136055fed62c9eca0c8ebcaa6cc2fd65a173d37b3951Lang Hames LiveRange Tmp(*LR); 136155fed62c9eca0c8ebcaa6cc2fd65a173d37b3951Lang Hames Tmp.start = NewIdx.getRegSlot(LR->start.isEarlyClobber()); 136255fed62c9eca0c8ebcaa6cc2fd65a173d37b3951Lang Hames Tmp.valno->def = Tmp.start; 136355fed62c9eca0c8ebcaa6cc2fd65a173d37b3951Lang Hames Tmp.end = LR->end.isDead() ? NewIdx.getDeadSlot() : NewIdx.getRegSlot(); 136455fed62c9eca0c8ebcaa6cc2fd65a173d37b3951Lang Hames LI->removeRange(*LR); 136555fed62c9eca0c8ebcaa6cc2fd65a173d37b3951Lang Hames LI->addRange(Tmp); 136655fed62c9eca0c8ebcaa6cc2fd65a173d37b3951Lang Hames } 136755fed62c9eca0c8ebcaa6cc2fd65a173d37b3951Lang Hames 136855fed62c9eca0c8ebcaa6cc2fd65a173d37b3951Lang Hames void moveAllInternalFrom(SlotIndex OldIdx, RangeSet& Internal) { 136955fed62c9eca0c8ebcaa6cc2fd65a173d37b3951Lang Hames for (RangeSet::iterator II = Internal.begin(), IE = Internal.end(); 137055fed62c9eca0c8ebcaa6cc2fd65a173d37b3951Lang Hames II != IE; ++II) 137155fed62c9eca0c8ebcaa6cc2fd65a173d37b3951Lang Hames moveInternalFrom(OldIdx, *II); 1372fbc8dd306aa7699a866db278db08d842762b2dc2Lang Hames } 137355fed62c9eca0c8ebcaa6cc2fd65a173d37b3951Lang Hames 137455fed62c9eca0c8ebcaa6cc2fd65a173d37b3951Lang Hames void moveExitingFrom(SlotIndex OldIdx, IntRangePair& P) { 137555fed62c9eca0c8ebcaa6cc2fd65a173d37b3951Lang Hames LiveRange* LR = P.second; 137655fed62c9eca0c8ebcaa6cc2fd65a173d37b3951Lang Hames assert(OldIdx < LR->start && LR->start < OldIdx.getDeadSlot() && 137755fed62c9eca0c8ebcaa6cc2fd65a173d37b3951Lang Hames "Range should start in OldIdx."); 137855fed62c9eca0c8ebcaa6cc2fd65a173d37b3951Lang Hames assert(LR->end > OldIdx.getDeadSlot() && "Range should exit OldIdx."); 137955fed62c9eca0c8ebcaa6cc2fd65a173d37b3951Lang Hames SlotIndex NewStart = NewIdx.getRegSlot(LR->start.isEarlyClobber()); 138055fed62c9eca0c8ebcaa6cc2fd65a173d37b3951Lang Hames LR->start = NewStart; 138155fed62c9eca0c8ebcaa6cc2fd65a173d37b3951Lang Hames LR->valno->def = NewStart; 138255fed62c9eca0c8ebcaa6cc2fd65a173d37b3951Lang Hames } 138355fed62c9eca0c8ebcaa6cc2fd65a173d37b3951Lang Hames 138455fed62c9eca0c8ebcaa6cc2fd65a173d37b3951Lang Hames void moveAllExitingFrom(SlotIndex OldIdx, RangeSet& Exiting) { 138555fed62c9eca0c8ebcaa6cc2fd65a173d37b3951Lang Hames for (RangeSet::iterator EI = Exiting.begin(), EE = Exiting.end(); 138655fed62c9eca0c8ebcaa6cc2fd65a173d37b3951Lang Hames EI != EE; ++EI) 138755fed62c9eca0c8ebcaa6cc2fd65a173d37b3951Lang Hames moveExitingFrom(OldIdx, *EI); 138855fed62c9eca0c8ebcaa6cc2fd65a173d37b3951Lang Hames } 138955fed62c9eca0c8ebcaa6cc2fd65a173d37b3951Lang Hames 13906aceab139205255ac44182f51819b9b8716cf477Lang Hames void moveEnteringUpFromInto(SlotIndex OldIdx, IntRangePair& P, 13916aceab139205255ac44182f51819b9b8716cf477Lang Hames BundleRanges& BR) { 13926aceab139205255ac44182f51819b9b8716cf477Lang Hames LiveInterval* LI = P.first; 13936aceab139205255ac44182f51819b9b8716cf477Lang Hames LiveRange* LR = P.second; 13946aceab139205255ac44182f51819b9b8716cf477Lang Hames bool LiveThrough = LR->end > OldIdx.getRegSlot(); 13956aceab139205255ac44182f51819b9b8716cf477Lang Hames if (LiveThrough) { 13966aceab139205255ac44182f51819b9b8716cf477Lang Hames assert((LR->start < NewIdx || BR[LI->reg].Def == LR) && 13976aceab139205255ac44182f51819b9b8716cf477Lang Hames "Def in bundle should be def range."); 13986aceab139205255ac44182f51819b9b8716cf477Lang Hames assert((BR[LI->reg].Use == 0 || BR[LI->reg].Use == LR) && 13996aceab139205255ac44182f51819b9b8716cf477Lang Hames "If bundle has use for this reg it should be LR."); 14006aceab139205255ac44182f51819b9b8716cf477Lang Hames BR[LI->reg].Use = LR; 14016aceab139205255ac44182f51819b9b8716cf477Lang Hames return; 14026aceab139205255ac44182f51819b9b8716cf477Lang Hames } 14036aceab139205255ac44182f51819b9b8716cf477Lang Hames 14046aceab139205255ac44182f51819b9b8716cf477Lang Hames SlotIndex LastUse = findLastUseBefore(LI->reg, OldIdx); 1405fd6d3217d3b577e704ff4826775b5938c23b9e73Lang Hames moveKillFlags(LI->reg, OldIdx, LastUse); 14066aceab139205255ac44182f51819b9b8716cf477Lang Hames 14076aceab139205255ac44182f51819b9b8716cf477Lang Hames if (LR->start < NewIdx) { 14086aceab139205255ac44182f51819b9b8716cf477Lang Hames // Becoming a new entering range. 14096aceab139205255ac44182f51819b9b8716cf477Lang Hames assert(BR[LI->reg].Dead == 0 && BR[LI->reg].Def == 0 && 14106aceab139205255ac44182f51819b9b8716cf477Lang Hames "Bundle shouldn't be re-defining reg mid-range."); 14117db76e7ca39905bbe3cb79158af0a93ca66faff8Benjamin Kramer assert((BR[LI->reg].Use == 0 || BR[LI->reg].Use == LR) && 14126aceab139205255ac44182f51819b9b8716cf477Lang Hames "Bundle shouldn't have different use range for same reg."); 14136aceab139205255ac44182f51819b9b8716cf477Lang Hames LR->end = LastUse.getRegSlot(); 14146aceab139205255ac44182f51819b9b8716cf477Lang Hames BR[LI->reg].Use = LR; 14156aceab139205255ac44182f51819b9b8716cf477Lang Hames } else { 14166aceab139205255ac44182f51819b9b8716cf477Lang Hames // Becoming a new Dead-def. 14176aceab139205255ac44182f51819b9b8716cf477Lang Hames assert(LR->start == NewIdx.getRegSlot(LR->start.isEarlyClobber()) && 14186aceab139205255ac44182f51819b9b8716cf477Lang Hames "Live range starting at unexpected slot."); 14196aceab139205255ac44182f51819b9b8716cf477Lang Hames assert(BR[LI->reg].Def == LR && "Reg should have def range."); 14206aceab139205255ac44182f51819b9b8716cf477Lang Hames assert(BR[LI->reg].Dead == 0 && 14216aceab139205255ac44182f51819b9b8716cf477Lang Hames "Can't have def and dead def of same reg in a bundle."); 14226aceab139205255ac44182f51819b9b8716cf477Lang Hames LR->end = LastUse.getDeadSlot(); 14236aceab139205255ac44182f51819b9b8716cf477Lang Hames BR[LI->reg].Dead = BR[LI->reg].Def; 14246aceab139205255ac44182f51819b9b8716cf477Lang Hames BR[LI->reg].Def = 0; 14256aceab139205255ac44182f51819b9b8716cf477Lang Hames } 14266aceab139205255ac44182f51819b9b8716cf477Lang Hames } 14276aceab139205255ac44182f51819b9b8716cf477Lang Hames 14286aceab139205255ac44182f51819b9b8716cf477Lang Hames void moveEnteringDownFromInto(SlotIndex OldIdx, IntRangePair& P, 14296aceab139205255ac44182f51819b9b8716cf477Lang Hames BundleRanges& BR) { 14306aceab139205255ac44182f51819b9b8716cf477Lang Hames LiveInterval* LI = P.first; 14316aceab139205255ac44182f51819b9b8716cf477Lang Hames LiveRange* LR = P.second; 14326aceab139205255ac44182f51819b9b8716cf477Lang Hames if (NewIdx > LR->end) { 14336aceab139205255ac44182f51819b9b8716cf477Lang Hames // Range extended to bundle. Add to bundle uses. 14346aceab139205255ac44182f51819b9b8716cf477Lang Hames // Note: Currently adds kill flags to bundle start. 14356aceab139205255ac44182f51819b9b8716cf477Lang Hames assert(BR[LI->reg].Use == 0 && 14366aceab139205255ac44182f51819b9b8716cf477Lang Hames "Bundle already has use range for reg."); 14376aceab139205255ac44182f51819b9b8716cf477Lang Hames moveKillFlags(LI->reg, LR->end, NewIdx); 14386aceab139205255ac44182f51819b9b8716cf477Lang Hames LR->end = NewIdx.getRegSlot(); 14396aceab139205255ac44182f51819b9b8716cf477Lang Hames BR[LI->reg].Use = LR; 14406aceab139205255ac44182f51819b9b8716cf477Lang Hames } else { 14416aceab139205255ac44182f51819b9b8716cf477Lang Hames assert(BR[LI->reg].Use != 0 && 14426aceab139205255ac44182f51819b9b8716cf477Lang Hames "Bundle should already have a use range for reg."); 14436aceab139205255ac44182f51819b9b8716cf477Lang Hames } 14446aceab139205255ac44182f51819b9b8716cf477Lang Hames } 14456aceab139205255ac44182f51819b9b8716cf477Lang Hames 14466aceab139205255ac44182f51819b9b8716cf477Lang Hames void moveAllEnteringFromInto(SlotIndex OldIdx, RangeSet& Entering, 14476aceab139205255ac44182f51819b9b8716cf477Lang Hames BundleRanges& BR) { 14486aceab139205255ac44182f51819b9b8716cf477Lang Hames bool GoingUp = NewIdx < OldIdx; 14496aceab139205255ac44182f51819b9b8716cf477Lang Hames 14506aceab139205255ac44182f51819b9b8716cf477Lang Hames if (GoingUp) { 14516aceab139205255ac44182f51819b9b8716cf477Lang Hames for (RangeSet::iterator EI = Entering.begin(), EE = Entering.end(); 14526aceab139205255ac44182f51819b9b8716cf477Lang Hames EI != EE; ++EI) 14536aceab139205255ac44182f51819b9b8716cf477Lang Hames moveEnteringUpFromInto(OldIdx, *EI, BR); 14546aceab139205255ac44182f51819b9b8716cf477Lang Hames } else { 14556aceab139205255ac44182f51819b9b8716cf477Lang Hames for (RangeSet::iterator EI = Entering.begin(), EE = Entering.end(); 14566aceab139205255ac44182f51819b9b8716cf477Lang Hames EI != EE; ++EI) 14576aceab139205255ac44182f51819b9b8716cf477Lang Hames moveEnteringDownFromInto(OldIdx, *EI, BR); 14586aceab139205255ac44182f51819b9b8716cf477Lang Hames } 14596aceab139205255ac44182f51819b9b8716cf477Lang Hames } 14606aceab139205255ac44182f51819b9b8716cf477Lang Hames 14616aceab139205255ac44182f51819b9b8716cf477Lang Hames void moveInternalFromInto(SlotIndex OldIdx, IntRangePair& P, 14626aceab139205255ac44182f51819b9b8716cf477Lang Hames BundleRanges& BR) { 14636aceab139205255ac44182f51819b9b8716cf477Lang Hames // TODO: Sane rules for moving ranges into bundles. 14646aceab139205255ac44182f51819b9b8716cf477Lang Hames } 14656aceab139205255ac44182f51819b9b8716cf477Lang Hames 14666aceab139205255ac44182f51819b9b8716cf477Lang Hames void moveAllInternalFromInto(SlotIndex OldIdx, RangeSet& Internal, 14676aceab139205255ac44182f51819b9b8716cf477Lang Hames BundleRanges& BR) { 14686aceab139205255ac44182f51819b9b8716cf477Lang Hames for (RangeSet::iterator II = Internal.begin(), IE = Internal.end(); 14696aceab139205255ac44182f51819b9b8716cf477Lang Hames II != IE; ++II) 14706aceab139205255ac44182f51819b9b8716cf477Lang Hames moveInternalFromInto(OldIdx, *II, BR); 14716aceab139205255ac44182f51819b9b8716cf477Lang Hames } 14726aceab139205255ac44182f51819b9b8716cf477Lang Hames 14736aceab139205255ac44182f51819b9b8716cf477Lang Hames void moveExitingFromInto(SlotIndex OldIdx, IntRangePair& P, 14746aceab139205255ac44182f51819b9b8716cf477Lang Hames BundleRanges& BR) { 14756aceab139205255ac44182f51819b9b8716cf477Lang Hames LiveInterval* LI = P.first; 14766aceab139205255ac44182f51819b9b8716cf477Lang Hames LiveRange* LR = P.second; 14776aceab139205255ac44182f51819b9b8716cf477Lang Hames 14786aceab139205255ac44182f51819b9b8716cf477Lang Hames assert(LR->start.isRegister() && 14796aceab139205255ac44182f51819b9b8716cf477Lang Hames "Don't know how to merge exiting ECs into bundles yet."); 14806aceab139205255ac44182f51819b9b8716cf477Lang Hames 14816aceab139205255ac44182f51819b9b8716cf477Lang Hames if (LR->end > NewIdx.getDeadSlot()) { 14826aceab139205255ac44182f51819b9b8716cf477Lang Hames // This range is becoming an exiting range on the bundle. 14836aceab139205255ac44182f51819b9b8716cf477Lang Hames // If there was an old dead-def of this reg, delete it. 14846aceab139205255ac44182f51819b9b8716cf477Lang Hames if (BR[LI->reg].Dead != 0) { 14856aceab139205255ac44182f51819b9b8716cf477Lang Hames LI->removeRange(*BR[LI->reg].Dead); 14866aceab139205255ac44182f51819b9b8716cf477Lang Hames BR[LI->reg].Dead = 0; 14876aceab139205255ac44182f51819b9b8716cf477Lang Hames } 14886aceab139205255ac44182f51819b9b8716cf477Lang Hames assert(BR[LI->reg].Def == 0 && 14896aceab139205255ac44182f51819b9b8716cf477Lang Hames "Can't have two defs for the same variable exiting a bundle."); 14906aceab139205255ac44182f51819b9b8716cf477Lang Hames LR->start = NewIdx.getRegSlot(); 14916aceab139205255ac44182f51819b9b8716cf477Lang Hames LR->valno->def = LR->start; 14926aceab139205255ac44182f51819b9b8716cf477Lang Hames BR[LI->reg].Def = LR; 14936aceab139205255ac44182f51819b9b8716cf477Lang Hames } else { 14946aceab139205255ac44182f51819b9b8716cf477Lang Hames // This range is becoming internal to the bundle. 14956aceab139205255ac44182f51819b9b8716cf477Lang Hames assert(LR->end == NewIdx.getRegSlot() && 14966aceab139205255ac44182f51819b9b8716cf477Lang Hames "Can't bundle def whose kill is before the bundle"); 14976aceab139205255ac44182f51819b9b8716cf477Lang Hames if (BR[LI->reg].Dead || BR[LI->reg].Def) { 14986aceab139205255ac44182f51819b9b8716cf477Lang Hames // Already have a def for this. Just delete range. 14996aceab139205255ac44182f51819b9b8716cf477Lang Hames LI->removeRange(*LR); 15006aceab139205255ac44182f51819b9b8716cf477Lang Hames } else { 15016aceab139205255ac44182f51819b9b8716cf477Lang Hames // Make range dead, record. 15026aceab139205255ac44182f51819b9b8716cf477Lang Hames LR->end = NewIdx.getDeadSlot(); 15036aceab139205255ac44182f51819b9b8716cf477Lang Hames BR[LI->reg].Dead = LR; 15046aceab139205255ac44182f51819b9b8716cf477Lang Hames assert(BR[LI->reg].Use == LR && 15056aceab139205255ac44182f51819b9b8716cf477Lang Hames "Range becoming dead should currently be use."); 15066aceab139205255ac44182f51819b9b8716cf477Lang Hames } 15076aceab139205255ac44182f51819b9b8716cf477Lang Hames // In both cases the range is no longer a use on the bundle. 15086aceab139205255ac44182f51819b9b8716cf477Lang Hames BR[LI->reg].Use = 0; 15096aceab139205255ac44182f51819b9b8716cf477Lang Hames } 15106aceab139205255ac44182f51819b9b8716cf477Lang Hames } 15116aceab139205255ac44182f51819b9b8716cf477Lang Hames 15126aceab139205255ac44182f51819b9b8716cf477Lang Hames void moveAllExitingFromInto(SlotIndex OldIdx, RangeSet& Exiting, 15136aceab139205255ac44182f51819b9b8716cf477Lang Hames BundleRanges& BR) { 15146aceab139205255ac44182f51819b9b8716cf477Lang Hames for (RangeSet::iterator EI = Exiting.begin(), EE = Exiting.end(); 15156aceab139205255ac44182f51819b9b8716cf477Lang Hames EI != EE; ++EI) 15166aceab139205255ac44182f51819b9b8716cf477Lang Hames moveExitingFromInto(OldIdx, *EI, BR); 15176aceab139205255ac44182f51819b9b8716cf477Lang Hames } 15186aceab139205255ac44182f51819b9b8716cf477Lang Hames 15193dc7c5138d219048d69952bead22f75efb984fa3Lang Hames}; 15203dc7c5138d219048d69952bead22f75efb984fa3Lang Hames 1521ecb50624d1e99596fdb289200cd1473cec84e097Lang Hamesvoid LiveIntervals::handleMove(MachineInstr* MI) { 1522ecb50624d1e99596fdb289200cd1473cec84e097Lang Hames SlotIndex OldIndex = indexes_->getInstructionIndex(MI); 1523ecb50624d1e99596fdb289200cd1473cec84e097Lang Hames indexes_->removeMachineInstrFromMaps(MI); 1524ecb50624d1e99596fdb289200cd1473cec84e097Lang Hames SlotIndex NewIndex = MI->isInsideBundle() ? 1525741981adf3a2bc0c6652c9c4ec846250950f3e68Jakob Stoklund Olesen indexes_->getInstructionIndex(MI) : 1526ecb50624d1e99596fdb289200cd1473cec84e097Lang Hames indexes_->insertMachineInstrInMaps(MI); 1527ecb50624d1e99596fdb289200cd1473cec84e097Lang Hames assert(getMBBStartIdx(MI->getParent()) <= OldIndex && 1528ecb50624d1e99596fdb289200cd1473cec84e097Lang Hames OldIndex < getMBBEndIdx(MI->getParent()) && 15293dc7c5138d219048d69952bead22f75efb984fa3Lang Hames "Cannot handle moves across basic block boundaries."); 1530ecb50624d1e99596fdb289200cd1473cec84e097Lang Hames assert(!MI->isBundled() && "Can't handle bundled instructions yet."); 15313dc7c5138d219048d69952bead22f75efb984fa3Lang Hames 1532ecb50624d1e99596fdb289200cd1473cec84e097Lang Hames HMEditor HME(*this, *mri_, *tri_, NewIndex); 15334586d257abf13b57d115d6bac9fb38ddc811acafLang Hames HME.moveAllRangesFrom(MI, OldIndex); 15344586d257abf13b57d115d6bac9fb38ddc811acafLang Hames} 15354586d257abf13b57d115d6bac9fb38ddc811acafLang Hames 15364586d257abf13b57d115d6bac9fb38ddc811acafLang Hamesvoid LiveIntervals::handleMoveIntoBundle(MachineInstr* MI, MachineInstr* BundleStart) { 15374586d257abf13b57d115d6bac9fb38ddc811acafLang Hames SlotIndex NewIndex = indexes_->getInstructionIndex(BundleStart); 15384586d257abf13b57d115d6bac9fb38ddc811acafLang Hames HMEditor HME(*this, *mri_, *tri_, NewIndex); 15394586d257abf13b57d115d6bac9fb38ddc811acafLang Hames HME.moveAllRangesInto(MI, BundleStart); 15403dc7c5138d219048d69952bead22f75efb984fa3Lang Hames} 1541