LiveIntervalAnalysis.cpp revision b0a6f62c9b2e75fc509d84310a9795ffacbc6796
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 18ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos#define DEBUG_TYPE "liveintervals" 193c3fe462f7978b429ecdd71750c26be25c3d1335Chris Lattner#include "llvm/CodeGen/LiveIntervalAnalysis.h" 2008a6c7614be9793754b17930ba619e875aef9585Misha Brukman#include "VirtRegMap.h" 21015959ee38e4fd4a920f6b0065c50e524762f580Chris Lattner#include "llvm/Value.h" 22ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos#include "llvm/CodeGen/LiveVariables.h" 23ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos#include "llvm/CodeGen/MachineFrameInfo.h" 24ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos#include "llvm/CodeGen/MachineInstr.h" 2522f07ffd27d1d721634d502c37267721d2e025cfEvan Cheng#include "llvm/CodeGen/MachineLoopInfo.h" 2684bc5427d6883f73cfeae3da640acd011d35c006Chris Lattner#include "llvm/CodeGen/MachineRegisterInfo.h" 27ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos#include "llvm/CodeGen/Passes.h" 286f0d024a534af18d9e60b3ea757376cd8a3a980eDan Gohman#include "llvm/Target/TargetRegisterInfo.h" 29ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos#include "llvm/Target/TargetInstrInfo.h" 30ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos#include "llvm/Target/TargetMachine.h" 31551ccae044b0ff658fe629dd67edd5ffe75d10e8Reid Spencer#include "llvm/Support/CommandLine.h" 32551ccae044b0ff658fe629dd67edd5ffe75d10e8Reid Spencer#include "llvm/Support/Debug.h" 33551ccae044b0ff658fe629dd67edd5ffe75d10e8Reid Spencer#include "llvm/ADT/Statistic.h" 34551ccae044b0ff658fe629dd67edd5ffe75d10e8Reid Spencer#include "llvm/ADT/STLExtras.h" 3520aa474f8fbebde588edc101b90e834df28ce4ceAlkis Evlogimenos#include <algorithm> 3697af751deb9b26fd42fbcee082da9ccc4ded5b45Jeff Cohen#include <cmath> 37ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenosusing namespace llvm; 38ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos 39844731a7f1909f55935e3514c9e713a62d67662eDan Gohman// Hidden options for help debugging. 40844731a7f1909f55935e3514c9e713a62d67662eDan Gohmanstatic cl::opt<bool> DisableReMat("disable-rematerialization", 41844731a7f1909f55935e3514c9e713a62d67662eDan Gohman cl::init(false), cl::Hidden); 42844731a7f1909f55935e3514c9e713a62d67662eDan Gohman 43844731a7f1909f55935e3514c9e713a62d67662eDan Gohmanstatic cl::opt<bool> SplitAtBB("split-intervals-at-bb", 44844731a7f1909f55935e3514c9e713a62d67662eDan Gohman cl::init(true), cl::Hidden); 45844731a7f1909f55935e3514c9e713a62d67662eDan Gohmanstatic cl::opt<int> SplitLimit("split-limit", 46844731a7f1909f55935e3514c9e713a62d67662eDan Gohman cl::init(-1), cl::Hidden); 47bc165e436beb02443abea9736c1b77e2dd7828b6Evan Cheng 48cd3245ac45c595da96bb768a55cddc356dff55feChris LattnerSTATISTIC(numIntervals, "Number of original intervals"); 49cd3245ac45c595da96bb768a55cddc356dff55feChris LattnerSTATISTIC(numIntervalsAfter, "Number of intervals after coalescing"); 500cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan ChengSTATISTIC(numFolds , "Number of loads/stores folded into instructions"); 510cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan ChengSTATISTIC(numSplits , "Number of intervals split"); 52cd3245ac45c595da96bb768a55cddc356dff55feChris Lattner 531997473cf72957d0e70322e2fe6fe2ab141c58a6Devang Patelchar LiveIntervals::ID = 0; 54844731a7f1909f55935e3514c9e713a62d67662eDan Gohmanstatic RegisterPass<LiveIntervals> X("liveintervals", "Live Interval Analysis"); 55ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos 56f7da2c7b0c6293c268881628fc351bed7763f1f4Chris Lattnervoid LiveIntervals::getAnalysisUsage(AnalysisUsage &AU) const { 572513330de8f8020d15d5bc96640a0957b7c733b9David Greene AU.addPreserved<LiveVariables>(); 581a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos AU.addRequired<LiveVariables>(); 5967d65bb69d5cad957cbb6d672dc0b4a19c211a42Bill Wendling AU.addPreservedID(MachineLoopInfoID); 6067d65bb69d5cad957cbb6d672dc0b4a19c211a42Bill Wendling AU.addPreservedID(MachineDominatorsID); 611a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos AU.addPreservedID(PHIEliminationID); 621a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos AU.addRequiredID(PHIEliminationID); 631a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos AU.addRequiredID(TwoAddressInstructionPassID); 641a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos MachineFunctionPass::getAnalysisUsage(AU); 65ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos} 66ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos 67f7da2c7b0c6293c268881628fc351bed7763f1f4Chris Lattnervoid LiveIntervals::releaseMemory() { 684ca980e7f9ce7b78955307c2d07001a24d3b6befEvan Cheng Idx2MBBMap.clear(); 691a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos mi2iMap_.clear(); 701a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos i2miMap_.clear(); 711a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos r2iMap_.clear(); 72dd199d29b781bc713462f1255b63d3f153bfd9e9Evan Cheng // Release VNInfo memroy regions after all VNInfo objects are dtor'd. 73dd199d29b781bc713462f1255b63d3f153bfd9e9Evan Cheng VNInfoAllocator.Reset(); 74549f27d3070195d6647b796841a5291b4549e8e0Evan Cheng for (unsigned i = 0, e = ClonedMIs.size(); i != e; ++i) 75549f27d3070195d6647b796841a5291b4549e8e0Evan Cheng delete ClonedMIs[i]; 76993141402f57b4d4cbb7f8a3113f19c61688f9b7Evan Cheng} 77993141402f57b4d4cbb7f8a3113f19c61688f9b7Evan Cheng 78ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos/// runOnMachineFunction - Register allocate the whole function 79ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos/// 80ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenosbool LiveIntervals::runOnMachineFunction(MachineFunction &fn) { 811a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos mf_ = &fn; 82d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng mri_ = &mf_->getRegInfo(); 831a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos tm_ = &fn.getTarget(); 846f0d024a534af18d9e60b3ea757376cd8a3a980eDan Gohman tri_ = tm_->getRegisterInfo(); 85f768bba43f5c036039851d2fcca8212edca18467Chris Lattner tii_ = tm_->getInstrInfo(); 861a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos lv_ = &getAnalysis<LiveVariables>(); 876f0d024a534af18d9e60b3ea757376cd8a3a980eDan Gohman allocatableRegs_ = tri_->getAllocatableSet(fn); 881a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos 89428b92eb83b457b71d29d1d4b7900d36a0ce9a53Chris Lattner // Number MachineInstrs and MachineBasicBlocks. 90428b92eb83b457b71d29d1d4b7900d36a0ce9a53Chris Lattner // Initialize MBB indexes to a sentinal. 91549f27d3070195d6647b796841a5291b4549e8e0Evan Cheng MBB2IdxMap.resize(mf_->getNumBlockIDs(), std::make_pair(~0U,~0U)); 92428b92eb83b457b71d29d1d4b7900d36a0ce9a53Chris Lattner 93428b92eb83b457b71d29d1d4b7900d36a0ce9a53Chris Lattner unsigned MIIndex = 0; 94428b92eb83b457b71d29d1d4b7900d36a0ce9a53Chris Lattner for (MachineFunction::iterator MBB = mf_->begin(), E = mf_->end(); 95428b92eb83b457b71d29d1d4b7900d36a0ce9a53Chris Lattner MBB != E; ++MBB) { 96549f27d3070195d6647b796841a5291b4549e8e0Evan Cheng unsigned StartIdx = MIIndex; 970c9f92e1ff64ee56724eae444a0442b02f83d0a8Evan Cheng 98428b92eb83b457b71d29d1d4b7900d36a0ce9a53Chris Lattner for (MachineBasicBlock::iterator I = MBB->begin(), E = MBB->end(); 99428b92eb83b457b71d29d1d4b7900d36a0ce9a53Chris Lattner I != E; ++I) { 100428b92eb83b457b71d29d1d4b7900d36a0ce9a53Chris Lattner bool inserted = mi2iMap_.insert(std::make_pair(I, MIIndex)).second; 1011a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos assert(inserted && "multiple MachineInstr -> index mappings"); 102428b92eb83b457b71d29d1d4b7900d36a0ce9a53Chris Lattner i2miMap_.push_back(I); 103428b92eb83b457b71d29d1d4b7900d36a0ce9a53Chris Lattner MIIndex += InstrSlots::NUM; 1041a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos } 105549f27d3070195d6647b796841a5291b4549e8e0Evan Cheng 106549f27d3070195d6647b796841a5291b4549e8e0Evan Cheng // Set the MBB2IdxMap entry for this MBB. 10776249966eec8d318534b416f33f878c6bd01d1eeEvan Cheng MBB2IdxMap[MBB->getNumber()] = (StartIdx == MIIndex) 10876249966eec8d318534b416f33f878c6bd01d1eeEvan Cheng ? std::make_pair(StartIdx, StartIdx) // Empty MBB 10976249966eec8d318534b416f33f878c6bd01d1eeEvan Cheng : std::make_pair(StartIdx, MIIndex - 1); 1104ca980e7f9ce7b78955307c2d07001a24d3b6befEvan Cheng Idx2MBBMap.push_back(std::make_pair(StartIdx, MBB)); 111428b92eb83b457b71d29d1d4b7900d36a0ce9a53Chris Lattner } 1124ca980e7f9ce7b78955307c2d07001a24d3b6befEvan Cheng std::sort(Idx2MBBMap.begin(), Idx2MBBMap.end(), Idx2MBBCompare()); 113ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos 1141a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos computeIntervals(); 115ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos 1161a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos numIntervals += getNumIntervals(); 117843b160a2040b3ec4d3452678450afa11704c473Alkis Evlogimenos 118bdc679d564e67a81792e463f6614b0088f975025Bill Wendling DOUT << "********** INTERVALS **********\n"; 119bdc679d564e67a81792e463f6614b0088f975025Bill Wendling for (iterator I = begin(), E = end(); I != E; ++I) { 1206f0d024a534af18d9e60b3ea757376cd8a3a980eDan Gohman I->second.print(DOUT, tri_); 121bdc679d564e67a81792e463f6614b0088f975025Bill Wendling DOUT << "\n"; 122bdc679d564e67a81792e463f6614b0088f975025Bill Wendling } 1237ac2d3146a196fa0120c579ecd2ddd69652ad230Chris Lattner 1241a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos numIntervalsAfter += getNumIntervals(); 12570ca358b7d540b6061236ddf757085042873c12cChris Lattner DEBUG(dump()); 1261a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos return true; 127ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos} 128ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos 12970ca358b7d540b6061236ddf757085042873c12cChris Lattner/// print - Implement the dump method. 130ce9653ce449f1409815547e1bf60abcd1332d2c9Reid Spencervoid LiveIntervals::print(std::ostream &O, const Module* ) const { 13170ca358b7d540b6061236ddf757085042873c12cChris Lattner O << "********** INTERVALS **********\n"; 1328e7a70976deee78a84099b916591d40f7a1cdc34Chris Lattner for (const_iterator I = begin(), E = end(); I != E; ++I) { 1336f0d024a534af18d9e60b3ea757376cd8a3a980eDan Gohman I->second.print(DOUT, tri_); 134bdc679d564e67a81792e463f6614b0088f975025Bill Wendling DOUT << "\n"; 1358e7a70976deee78a84099b916591d40f7a1cdc34Chris Lattner } 13670ca358b7d540b6061236ddf757085042873c12cChris Lattner 13770ca358b7d540b6061236ddf757085042873c12cChris Lattner O << "********** MACHINEINSTRS **********\n"; 13870ca358b7d540b6061236ddf757085042873c12cChris Lattner for (MachineFunction::iterator mbbi = mf_->begin(), mbbe = mf_->end(); 13970ca358b7d540b6061236ddf757085042873c12cChris Lattner mbbi != mbbe; ++mbbi) { 14070ca358b7d540b6061236ddf757085042873c12cChris Lattner O << ((Value*)mbbi->getBasicBlock())->getName() << ":\n"; 14170ca358b7d540b6061236ddf757085042873c12cChris Lattner for (MachineBasicBlock::iterator mii = mbbi->begin(), 14270ca358b7d540b6061236ddf757085042873c12cChris Lattner mie = mbbi->end(); mii != mie; ++mii) { 143477e4555de341c5de780de3720d6f115ec133c4eChris Lattner O << getInstructionIndex(mii) << '\t' << *mii; 14470ca358b7d540b6061236ddf757085042873c12cChris Lattner } 14570ca358b7d540b6061236ddf757085042873c12cChris Lattner } 14670ca358b7d540b6061236ddf757085042873c12cChris Lattner} 14770ca358b7d540b6061236ddf757085042873c12cChris Lattner 148c92da3882ee4e18153bb36fcdf33af393aba8259Evan Cheng/// conflictsWithPhysRegDef - Returns true if the specified register 149c92da3882ee4e18153bb36fcdf33af393aba8259Evan Cheng/// is defined during the duration of the specified interval. 150c92da3882ee4e18153bb36fcdf33af393aba8259Evan Chengbool LiveIntervals::conflictsWithPhysRegDef(const LiveInterval &li, 151c92da3882ee4e18153bb36fcdf33af393aba8259Evan Cheng VirtRegMap &vrm, unsigned reg) { 152c92da3882ee4e18153bb36fcdf33af393aba8259Evan Cheng for (LiveInterval::Ranges::const_iterator 153c92da3882ee4e18153bb36fcdf33af393aba8259Evan Cheng I = li.ranges.begin(), E = li.ranges.end(); I != E; ++I) { 154c92da3882ee4e18153bb36fcdf33af393aba8259Evan Cheng for (unsigned index = getBaseIndex(I->start), 155c92da3882ee4e18153bb36fcdf33af393aba8259Evan Cheng end = getBaseIndex(I->end-1) + InstrSlots::NUM; index != end; 156c92da3882ee4e18153bb36fcdf33af393aba8259Evan Cheng index += InstrSlots::NUM) { 157c92da3882ee4e18153bb36fcdf33af393aba8259Evan Cheng // skip deleted instructions 158c92da3882ee4e18153bb36fcdf33af393aba8259Evan Cheng while (index != end && !getInstructionFromIndex(index)) 159c92da3882ee4e18153bb36fcdf33af393aba8259Evan Cheng index += InstrSlots::NUM; 160c92da3882ee4e18153bb36fcdf33af393aba8259Evan Cheng if (index == end) break; 161c92da3882ee4e18153bb36fcdf33af393aba8259Evan Cheng 162c92da3882ee4e18153bb36fcdf33af393aba8259Evan Cheng MachineInstr *MI = getInstructionFromIndex(index); 1635d446265c740c17ed12e693423f0363296670d60Evan Cheng unsigned SrcReg, DstReg; 1645d446265c740c17ed12e693423f0363296670d60Evan Cheng if (tii_->isMoveInstr(*MI, SrcReg, DstReg)) 1655d446265c740c17ed12e693423f0363296670d60Evan Cheng if (SrcReg == li.reg || DstReg == li.reg) 1665d446265c740c17ed12e693423f0363296670d60Evan Cheng continue; 167c92da3882ee4e18153bb36fcdf33af393aba8259Evan Cheng for (unsigned i = 0; i != MI->getNumOperands(); ++i) { 168c92da3882ee4e18153bb36fcdf33af393aba8259Evan Cheng MachineOperand& mop = MI->getOperand(i); 1695d446265c740c17ed12e693423f0363296670d60Evan Cheng if (!mop.isRegister()) 170c92da3882ee4e18153bb36fcdf33af393aba8259Evan Cheng continue; 171c92da3882ee4e18153bb36fcdf33af393aba8259Evan Cheng unsigned PhysReg = mop.getReg(); 1725d446265c740c17ed12e693423f0363296670d60Evan Cheng if (PhysReg == 0 || PhysReg == li.reg) 173c92da3882ee4e18153bb36fcdf33af393aba8259Evan Cheng continue; 1746f0d024a534af18d9e60b3ea757376cd8a3a980eDan Gohman if (TargetRegisterInfo::isVirtualRegister(PhysReg)) { 1755d446265c740c17ed12e693423f0363296670d60Evan Cheng if (!vrm.hasPhys(PhysReg)) 1765d446265c740c17ed12e693423f0363296670d60Evan Cheng continue; 177c92da3882ee4e18153bb36fcdf33af393aba8259Evan Cheng PhysReg = vrm.getPhys(PhysReg); 1785d446265c740c17ed12e693423f0363296670d60Evan Cheng } 1796f0d024a534af18d9e60b3ea757376cd8a3a980eDan Gohman if (PhysReg && tri_->regsOverlap(PhysReg, reg)) 180c92da3882ee4e18153bb36fcdf33af393aba8259Evan Cheng return true; 181c92da3882ee4e18153bb36fcdf33af393aba8259Evan Cheng } 182c92da3882ee4e18153bb36fcdf33af393aba8259Evan Cheng } 183c92da3882ee4e18153bb36fcdf33af393aba8259Evan Cheng } 184c92da3882ee4e18153bb36fcdf33af393aba8259Evan Cheng 185c92da3882ee4e18153bb36fcdf33af393aba8259Evan Cheng return false; 186c92da3882ee4e18153bb36fcdf33af393aba8259Evan Cheng} 187c92da3882ee4e18153bb36fcdf33af393aba8259Evan Cheng 188be4f88a8b8bb3311e0dc4cde8533763d7923c3eaChris Lattnervoid LiveIntervals::printRegName(unsigned reg) const { 1896f0d024a534af18d9e60b3ea757376cd8a3a980eDan Gohman if (TargetRegisterInfo::isPhysicalRegister(reg)) 190e6d088acc90e422451e098555d383d4d65b6ce6bBill Wendling cerr << tri_->getName(reg); 1911a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos else 192e81561909d128c6e2d8033cb5465a49b2596b26aBill Wendling cerr << "%reg" << reg; 193ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos} 194ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos 195be4f88a8b8bb3311e0dc4cde8533763d7923c3eaChris Lattnervoid LiveIntervals::handleVirtualRegisterDef(MachineBasicBlock *mbb, 196ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos MachineBasicBlock::iterator mi, 1976b128bdc58a496e9f08e4d09416330320761baffChris Lattner unsigned MIIdx, 198be4f88a8b8bb3311e0dc4cde8533763d7923c3eaChris Lattner LiveInterval &interval) { 199bdc679d564e67a81792e463f6614b0088f975025Bill Wendling DOUT << "\t\tregister: "; DEBUG(printRegName(interval.reg)); 2001a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos LiveVariables::VarInfo& vi = lv_->getVarInfo(interval.reg); 2011a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos 202419852ca8a01aecde4c0e20af6b7bd6450e70f87Evan Cheng if (mi->getOpcode() == TargetInstrInfo::IMPLICIT_DEF) { 203419852ca8a01aecde4c0e20af6b7bd6450e70f87Evan Cheng DOUT << "is a implicit_def\n"; 204419852ca8a01aecde4c0e20af6b7bd6450e70f87Evan Cheng return; 205419852ca8a01aecde4c0e20af6b7bd6450e70f87Evan Cheng } 206419852ca8a01aecde4c0e20af6b7bd6450e70f87Evan Cheng 207706515727c6d024015fffded2b3109a4f0ac5299Alkis Evlogimenos // Virtual registers may be defined multiple times (due to phi 208706515727c6d024015fffded2b3109a4f0ac5299Alkis Evlogimenos // elimination and 2-addr elimination). Much of what we do only has to be 209706515727c6d024015fffded2b3109a4f0ac5299Alkis Evlogimenos // done once for the vreg. We use an empty interval to detect the first 2101a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // time we see a vreg. 2111a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos if (interval.empty()) { 2121a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // Get the Idx of the defining instructions. 2136b128bdc58a496e9f08e4d09416330320761baffChris Lattner unsigned defIndex = getDefIndex(MIIdx); 2147ecb38be0a533e7b9c7d3b8e9b5c8a6fa5f6b349Evan Cheng VNInfo *ValNo; 215c8d044e4f779fdcfc5e7d592927740fd8f672a70Evan Cheng MachineInstr *CopyMI = NULL; 21691725b75852443923b419fd23215194cfc65dd88Chris Lattner unsigned SrcReg, DstReg; 217c8d044e4f779fdcfc5e7d592927740fd8f672a70Evan Cheng if (mi->getOpcode() == TargetInstrInfo::EXTRACT_SUBREG || 2187e073baedb8232b9519dbe15ea141ff98ccfe6aeEvan Cheng mi->getOpcode() == TargetInstrInfo::INSERT_SUBREG || 219c8d044e4f779fdcfc5e7d592927740fd8f672a70Evan Cheng tii_->isMoveInstr(*mi, SrcReg, DstReg)) 220c8d044e4f779fdcfc5e7d592927740fd8f672a70Evan Cheng CopyMI = mi; 221c8d044e4f779fdcfc5e7d592927740fd8f672a70Evan Cheng ValNo = interval.getNextValue(defIndex, CopyMI, VNInfoAllocator); 2227ecb38be0a533e7b9c7d3b8e9b5c8a6fa5f6b349Evan Cheng 2237ecb38be0a533e7b9c7d3b8e9b5c8a6fa5f6b349Evan Cheng assert(ValNo->id == 0 && "First value in interval is not 0?"); 2241a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos 2251a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // Loop over all of the blocks that the vreg is defined in. There are 2261a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // two cases we have to handle here. The most common case is a vreg 2271a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // whose lifetime is contained within a basic block. In this case there 2281a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // will be a single kill, in MBB, which comes after the definition. 2291a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos if (vi.Kills.size() == 1 && vi.Kills[0]->getParent() == mbb) { 2301a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // FIXME: what about dead vars? 2311a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos unsigned killIdx; 2321a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos if (vi.Kills[0] != mi) 2331a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos killIdx = getUseIndex(getInstructionIndex(vi.Kills[0]))+1; 2341a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos else 2351a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos killIdx = defIndex+1; 2361a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos 2371a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // If the kill happens after the definition, we have an intra-block 2381a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // live range. 2391a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos if (killIdx > defIndex) { 24061de82d8853a02fe39c47302432abb70a586704fEvan Cheng assert(vi.AliveBlocks.none() && 2411a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos "Shouldn't be alive across any blocks!"); 2427ecb38be0a533e7b9c7d3b8e9b5c8a6fa5f6b349Evan Cheng LiveRange LR(defIndex, killIdx, ValNo); 2431a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos interval.addRange(LR); 244bdc679d564e67a81792e463f6614b0088f975025Bill Wendling DOUT << " +" << LR << "\n"; 245f3bb2e65d12857f83b273f4ecab013680310bbbcEvan Cheng interval.addKill(ValNo, killIdx); 2461a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos return; 2471a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos } 2481a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos } 2496097d13b2a624048dbe02e39e2dfb23bfa269b64Chris Lattner 2501a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // The other case we handle is when a virtual register lives to the end 2511a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // of the defining block, potentially live across some blocks, then is 2521a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // live into some number of blocks, but gets killed. Start by adding a 2531a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // range that goes from this definition to the end of the defining block. 254d19e2901c1b79d287d01079659684f3a4951a69eAlkis Evlogimenos LiveRange NewLR(defIndex, 255d19e2901c1b79d287d01079659684f3a4951a69eAlkis Evlogimenos getInstructionIndex(&mbb->back()) + InstrSlots::NUM, 2567ecb38be0a533e7b9c7d3b8e9b5c8a6fa5f6b349Evan Cheng ValNo); 257bdc679d564e67a81792e463f6614b0088f975025Bill Wendling DOUT << " +" << NewLR; 2581a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos interval.addRange(NewLR); 2591a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos 2601a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // Iterate over all of the blocks that the variable is completely 2611a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // live in, adding [insrtIndex(begin), instrIndex(end)+4) to the 2621a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // live interval. 2631a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos for (unsigned i = 0, e = vi.AliveBlocks.size(); i != e; ++i) { 2641a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos if (vi.AliveBlocks[i]) { 265428b92eb83b457b71d29d1d4b7900d36a0ce9a53Chris Lattner MachineBasicBlock *MBB = mf_->getBlockNumbered(i); 266428b92eb83b457b71d29d1d4b7900d36a0ce9a53Chris Lattner if (!MBB->empty()) { 267428b92eb83b457b71d29d1d4b7900d36a0ce9a53Chris Lattner LiveRange LR(getMBBStartIdx(i), 268428b92eb83b457b71d29d1d4b7900d36a0ce9a53Chris Lattner getInstructionIndex(&MBB->back()) + InstrSlots::NUM, 2697ecb38be0a533e7b9c7d3b8e9b5c8a6fa5f6b349Evan Cheng ValNo); 2701a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos interval.addRange(LR); 271bdc679d564e67a81792e463f6614b0088f975025Bill Wendling DOUT << " +" << LR; 2721a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos } 2731a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos } 2741a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos } 2751a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos 2761a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // Finally, this virtual register is live from the start of any killing 2771a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // block to the 'use' slot of the killing instruction. 2781a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos for (unsigned i = 0, e = vi.Kills.size(); i != e; ++i) { 2791a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos MachineInstr *Kill = vi.Kills[i]; 2808df786012dc6b875f31ba4152e09c6e0098082eeEvan Cheng unsigned killIdx = getUseIndex(getInstructionIndex(Kill))+1; 281428b92eb83b457b71d29d1d4b7900d36a0ce9a53Chris Lattner LiveRange LR(getMBBStartIdx(Kill->getParent()), 2827ecb38be0a533e7b9c7d3b8e9b5c8a6fa5f6b349Evan Cheng killIdx, ValNo); 2831a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos interval.addRange(LR); 284f3bb2e65d12857f83b273f4ecab013680310bbbcEvan Cheng interval.addKill(ValNo, killIdx); 285bdc679d564e67a81792e463f6614b0088f975025Bill Wendling DOUT << " +" << LR; 2861a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos } 2871a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos 2881a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos } else { 2891a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // If this is the second time we see a virtual register definition, it 2901a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // must be due to phi elimination or two addr elimination. If this is 291bf105c842450d3308d024be203ddd533f37051ecEvan Cheng // the result of two address elimination, then the vreg is one of the 292bf105c842450d3308d024be203ddd533f37051ecEvan Cheng // def-and-use register operand. 29332dfbeada7292167bb488f36a71a5a6a519ddaffEvan Cheng if (mi->isRegReDefinedByTwoAddr(interval.reg)) { 2941a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // If this is a two-address definition, then we have already processed 2951a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // the live range. The only problem is that we didn't realize there 2961a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // are actually two values in the live interval. Because of this we 2971a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // need to take the LiveRegion that defines this register and split it 2981a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // into two values. 299a07cec9e24a286157541d2337cd66b24cd116586Evan Cheng assert(interval.containsOneValue()); 300a07cec9e24a286157541d2337cd66b24cd116586Evan Cheng unsigned DefIndex = getDefIndex(interval.getValNumInfo(0)->def); 3016b128bdc58a496e9f08e4d09416330320761baffChris Lattner unsigned RedefIndex = getDefIndex(MIIdx); 3021a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos 3034f8ff168de12eabdeb4b9437bf9402489ecf85cbEvan Cheng const LiveRange *OldLR = interval.getLiveRangeContaining(RedefIndex-1); 3047ecb38be0a533e7b9c7d3b8e9b5c8a6fa5f6b349Evan Cheng VNInfo *OldValNo = OldLR->valno; 3054f8ff168de12eabdeb4b9437bf9402489ecf85cbEvan Cheng 3061a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // Delete the initial value, which should be short and continuous, 307be4f88a8b8bb3311e0dc4cde8533763d7923c3eaChris Lattner // because the 2-addr copy must be in the same MBB as the redef. 3081a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos interval.removeRange(DefIndex, RedefIndex); 309706515727c6d024015fffded2b3109a4f0ac5299Alkis Evlogimenos 310be4f88a8b8bb3311e0dc4cde8533763d7923c3eaChris Lattner // Two-address vregs should always only be redefined once. This means 311be4f88a8b8bb3311e0dc4cde8533763d7923c3eaChris Lattner // that at this point, there should be exactly one value number in it. 312be4f88a8b8bb3311e0dc4cde8533763d7923c3eaChris Lattner assert(interval.containsOneValue() && "Unexpected 2-addr liveint!"); 313be4f88a8b8bb3311e0dc4cde8533763d7923c3eaChris Lattner 31491725b75852443923b419fd23215194cfc65dd88Chris Lattner // The new value number (#1) is defined by the instruction we claimed 31591725b75852443923b419fd23215194cfc65dd88Chris Lattner // defined value #0. 316c8d044e4f779fdcfc5e7d592927740fd8f672a70Evan Cheng VNInfo *ValNo = interval.getNextValue(OldValNo->def, OldValNo->copy, 317c8d044e4f779fdcfc5e7d592927740fd8f672a70Evan Cheng VNInfoAllocator); 318be4f88a8b8bb3311e0dc4cde8533763d7923c3eaChris Lattner 31991725b75852443923b419fd23215194cfc65dd88Chris Lattner // Value#0 is now defined by the 2-addr instruction. 320c8d044e4f779fdcfc5e7d592927740fd8f672a70Evan Cheng OldValNo->def = RedefIndex; 321c8d044e4f779fdcfc5e7d592927740fd8f672a70Evan Cheng OldValNo->copy = 0; 322be4f88a8b8bb3311e0dc4cde8533763d7923c3eaChris Lattner 323be4f88a8b8bb3311e0dc4cde8533763d7923c3eaChris Lattner // Add the new live interval which replaces the range for the input copy. 324be4f88a8b8bb3311e0dc4cde8533763d7923c3eaChris Lattner LiveRange LR(DefIndex, RedefIndex, ValNo); 325bdc679d564e67a81792e463f6614b0088f975025Bill Wendling DOUT << " replace range with " << LR; 3261a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos interval.addRange(LR); 327f3bb2e65d12857f83b273f4ecab013680310bbbcEvan Cheng interval.addKill(ValNo, RedefIndex); 3281a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos 3291a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // If this redefinition is dead, we need to add a dummy unit live 3301a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // range covering the def slot. 3316130f66eaae89f8878590796977678afa8448926Evan Cheng if (mi->registerDefIsDead(interval.reg, tri_)) 3327ecb38be0a533e7b9c7d3b8e9b5c8a6fa5f6b349Evan Cheng interval.addRange(LiveRange(RedefIndex, RedefIndex+1, OldValNo)); 3331a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos 33456fdd7af884a35673fb6dd3e01333960922c3ac2Evan Cheng DOUT << " RESULT: "; 3356f0d024a534af18d9e60b3ea757376cd8a3a980eDan Gohman interval.print(DOUT, tri_); 3361a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos 3371a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos } else { 3381a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // Otherwise, this must be because of phi elimination. If this is the 3391a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // first redefinition of the vreg that we have seen, go back and change 3401a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // the live range in the PHI block to be a different value number. 3411a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos if (interval.containsOneValue()) { 3421a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos assert(vi.Kills.size() == 1 && 3431a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos "PHI elimination vreg should have one kill, the PHI itself!"); 3441a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos 3451a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // Remove the old range that we now know has an incorrect number. 346f3bb2e65d12857f83b273f4ecab013680310bbbcEvan Cheng VNInfo *VNI = interval.getValNumInfo(0); 3471a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos MachineInstr *Killer = vi.Kills[0]; 348428b92eb83b457b71d29d1d4b7900d36a0ce9a53Chris Lattner unsigned Start = getMBBStartIdx(Killer->getParent()); 3491a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos unsigned End = getUseIndex(getInstructionIndex(Killer))+1; 35056fdd7af884a35673fb6dd3e01333960922c3ac2Evan Cheng DOUT << " Removing [" << Start << "," << End << "] from: "; 3516f0d024a534af18d9e60b3ea757376cd8a3a980eDan Gohman interval.print(DOUT, tri_); DOUT << "\n"; 3521a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos interval.removeRange(Start, End); 353c3fc7d9ec9b495c8a88cd854247105c296d3aabdEvan Cheng VNI->hasPHIKill = true; 3546f0d024a534af18d9e60b3ea757376cd8a3a980eDan Gohman DOUT << " RESULT: "; interval.print(DOUT, tri_); 3551a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos 356be4f88a8b8bb3311e0dc4cde8533763d7923c3eaChris Lattner // Replace the interval with one of a NEW value number. Note that this 357be4f88a8b8bb3311e0dc4cde8533763d7923c3eaChris Lattner // value number isn't actually defined by an instruction, weird huh? :) 358f3bb2e65d12857f83b273f4ecab013680310bbbcEvan Cheng LiveRange LR(Start, End, interval.getNextValue(~0, 0, VNInfoAllocator)); 359bdc679d564e67a81792e463f6614b0088f975025Bill Wendling DOUT << " replace range with " << LR; 3601a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos interval.addRange(LR); 361f3bb2e65d12857f83b273f4ecab013680310bbbcEvan Cheng interval.addKill(LR.valno, End); 3626f0d024a534af18d9e60b3ea757376cd8a3a980eDan Gohman DOUT << " RESULT: "; interval.print(DOUT, tri_); 3631a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos } 3641a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos 3651a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // In the case of PHI elimination, each variable definition is only 3661a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // live until the end of the block. We've already taken care of the 3671a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // rest of the live range. 3686b128bdc58a496e9f08e4d09416330320761baffChris Lattner unsigned defIndex = getDefIndex(MIIdx); 36991725b75852443923b419fd23215194cfc65dd88Chris Lattner 3707ecb38be0a533e7b9c7d3b8e9b5c8a6fa5f6b349Evan Cheng VNInfo *ValNo; 371c8d044e4f779fdcfc5e7d592927740fd8f672a70Evan Cheng MachineInstr *CopyMI = NULL; 37291725b75852443923b419fd23215194cfc65dd88Chris Lattner unsigned SrcReg, DstReg; 373c8d044e4f779fdcfc5e7d592927740fd8f672a70Evan Cheng if (mi->getOpcode() == TargetInstrInfo::EXTRACT_SUBREG || 3747e073baedb8232b9519dbe15ea141ff98ccfe6aeEvan Cheng mi->getOpcode() == TargetInstrInfo::INSERT_SUBREG || 375c8d044e4f779fdcfc5e7d592927740fd8f672a70Evan Cheng tii_->isMoveInstr(*mi, SrcReg, DstReg)) 376c8d044e4f779fdcfc5e7d592927740fd8f672a70Evan Cheng CopyMI = mi; 377c8d044e4f779fdcfc5e7d592927740fd8f672a70Evan Cheng ValNo = interval.getNextValue(defIndex, CopyMI, VNInfoAllocator); 37891725b75852443923b419fd23215194cfc65dd88Chris Lattner 37924c2e5cf7e926452ea5875d027ec0d24d9c19e39Evan Cheng unsigned killIndex = getInstructionIndex(&mbb->back()) + InstrSlots::NUM; 3807ecb38be0a533e7b9c7d3b8e9b5c8a6fa5f6b349Evan Cheng LiveRange LR(defIndex, killIndex, ValNo); 3811a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos interval.addRange(LR); 382c3fc7d9ec9b495c8a88cd854247105c296d3aabdEvan Cheng interval.addKill(ValNo, killIndex); 383c3fc7d9ec9b495c8a88cd854247105c296d3aabdEvan Cheng ValNo->hasPHIKill = true; 384bdc679d564e67a81792e463f6614b0088f975025Bill Wendling DOUT << " +" << LR; 385dd2cc65f34f9b7bfda1cd0c42becedfc361d46f8Alkis Evlogimenos } 3861a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos } 387ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos 388bdc679d564e67a81792e463f6614b0088f975025Bill Wendling DOUT << '\n'; 389ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos} 390ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos 391f35fef7060c465dd7b578bf6339a18e8a8911888Chris Lattnervoid LiveIntervals::handlePhysicalRegisterDef(MachineBasicBlock *MBB, 392ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos MachineBasicBlock::iterator mi, 3936b128bdc58a496e9f08e4d09416330320761baffChris Lattner unsigned MIIdx, 39491725b75852443923b419fd23215194cfc65dd88Chris Lattner LiveInterval &interval, 395c8d044e4f779fdcfc5e7d592927740fd8f672a70Evan Cheng MachineInstr *CopyMI) { 3961a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // A physical register cannot be live across basic block, so its 3971a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // lifetime must end somewhere in its defining basic block. 398bdc679d564e67a81792e463f6614b0088f975025Bill Wendling DOUT << "\t\tregister: "; DEBUG(printRegName(interval.reg)); 3991a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos 4006b128bdc58a496e9f08e4d09416330320761baffChris Lattner unsigned baseIndex = MIIdx; 4011a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos unsigned start = getDefIndex(baseIndex); 4021a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos unsigned end = start; 4031a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos 4041a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // If it is not used after definition, it is considered dead at 4051a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // the instruction defining it. Hence its interval is: 4061a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // [defSlot(def), defSlot(def)+1) 4076130f66eaae89f8878590796977678afa8448926Evan Cheng if (mi->registerDefIsDead(interval.reg, tri_)) { 408bdc679d564e67a81792e463f6614b0088f975025Bill Wendling DOUT << " dead"; 409ab4b66d4c279e8cd9e448687020fc838e7881dbcChris Lattner end = getDefIndex(start) + 1; 410ab4b66d4c279e8cd9e448687020fc838e7881dbcChris Lattner goto exit; 4111a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos } 412ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos 4131a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // If it is not dead on definition, it must be killed by a 4141a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // subsequent instruction. Hence its interval is: 4151a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // [defSlot(def), useSlot(kill)+1) 4165ab6f5fe666d0e3403d9b777324d1a1999118153Chris Lattner while (++mi != MBB->end()) { 4171a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos baseIndex += InstrSlots::NUM; 4186130f66eaae89f8878590796977678afa8448926Evan Cheng if (mi->killsRegister(interval.reg, tri_)) { 419bdc679d564e67a81792e463f6614b0088f975025Bill Wendling DOUT << " killed"; 420ab4b66d4c279e8cd9e448687020fc838e7881dbcChris Lattner end = getUseIndex(baseIndex) + 1; 421ab4b66d4c279e8cd9e448687020fc838e7881dbcChris Lattner goto exit; 4226130f66eaae89f8878590796977678afa8448926Evan Cheng } else if (mi->modifiesRegister(interval.reg, tri_)) { 4239a1956ae6ad2d4892afbc9f1b97d645d220b6d4aEvan Cheng // Another instruction redefines the register before it is ever read. 4249a1956ae6ad2d4892afbc9f1b97d645d220b6d4aEvan Cheng // Then the register is essentially dead at the instruction that defines 4259a1956ae6ad2d4892afbc9f1b97d645d220b6d4aEvan Cheng // it. Hence its interval is: 4269a1956ae6ad2d4892afbc9f1b97d645d220b6d4aEvan Cheng // [defSlot(def), defSlot(def)+1) 427bdc679d564e67a81792e463f6614b0088f975025Bill Wendling DOUT << " dead"; 4289a1956ae6ad2d4892afbc9f1b97d645d220b6d4aEvan Cheng end = getDefIndex(start) + 1; 4299a1956ae6ad2d4892afbc9f1b97d645d220b6d4aEvan Cheng goto exit; 430f35fef7060c465dd7b578bf6339a18e8a8911888Chris Lattner } 4311a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos } 4325ab6f5fe666d0e3403d9b777324d1a1999118153Chris Lattner 4335ab6f5fe666d0e3403d9b777324d1a1999118153Chris Lattner // The only case we should have a dead physreg here without a killing or 4345ab6f5fe666d0e3403d9b777324d1a1999118153Chris Lattner // instruction where we know it's dead is if it is live-in to the function 4355ab6f5fe666d0e3403d9b777324d1a1999118153Chris Lattner // and never used. 436c8d044e4f779fdcfc5e7d592927740fd8f672a70Evan Cheng assert(!CopyMI && "physreg was not killed in defining block!"); 4375ab6f5fe666d0e3403d9b777324d1a1999118153Chris Lattner end = getDefIndex(start) + 1; // It's dead. 43802ba13c9897ae2b19f9201e57460d7ee2b753a0bAlkis Evlogimenos 439ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenosexit: 4401a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos assert(start < end && "did not find end of interval?"); 441f768bba43f5c036039851d2fcca8212edca18467Chris Lattner 44224a3cc4c83e5edb25fadf7b8979a26b4451795c6Evan Cheng // Already exists? Extend old live interval. 44324a3cc4c83e5edb25fadf7b8979a26b4451795c6Evan Cheng LiveInterval::iterator OldLR = interval.FindLiveRangeContaining(start); 4447ecb38be0a533e7b9c7d3b8e9b5c8a6fa5f6b349Evan Cheng VNInfo *ValNo = (OldLR != interval.end()) 445c8d044e4f779fdcfc5e7d592927740fd8f672a70Evan Cheng ? OldLR->valno : interval.getNextValue(start, CopyMI, VNInfoAllocator); 4467ecb38be0a533e7b9c7d3b8e9b5c8a6fa5f6b349Evan Cheng LiveRange LR(start, end, ValNo); 4471a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos interval.addRange(LR); 448f3bb2e65d12857f83b273f4ecab013680310bbbcEvan Cheng interval.addKill(LR.valno, end); 449bdc679d564e67a81792e463f6614b0088f975025Bill Wendling DOUT << " +" << LR << '\n'; 450ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos} 451ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos 452f35fef7060c465dd7b578bf6339a18e8a8911888Chris Lattnervoid LiveIntervals::handleRegisterDef(MachineBasicBlock *MBB, 453f35fef7060c465dd7b578bf6339a18e8a8911888Chris Lattner MachineBasicBlock::iterator MI, 4546b128bdc58a496e9f08e4d09416330320761baffChris Lattner unsigned MIIdx, 455f35fef7060c465dd7b578bf6339a18e8a8911888Chris Lattner unsigned reg) { 4566f0d024a534af18d9e60b3ea757376cd8a3a980eDan Gohman if (TargetRegisterInfo::isVirtualRegister(reg)) 4576b128bdc58a496e9f08e4d09416330320761baffChris Lattner handleVirtualRegisterDef(MBB, MI, MIIdx, getOrCreateInterval(reg)); 4585327801fb87e3eda52a33f82e6211181030ecb93Alkis Evlogimenos else if (allocatableRegs_[reg]) { 459c8d044e4f779fdcfc5e7d592927740fd8f672a70Evan Cheng MachineInstr *CopyMI = NULL; 46091725b75852443923b419fd23215194cfc65dd88Chris Lattner unsigned SrcReg, DstReg; 461c8d044e4f779fdcfc5e7d592927740fd8f672a70Evan Cheng if (MI->getOpcode() == TargetInstrInfo::EXTRACT_SUBREG || 4627e073baedb8232b9519dbe15ea141ff98ccfe6aeEvan Cheng MI->getOpcode() == TargetInstrInfo::INSERT_SUBREG || 463c8d044e4f779fdcfc5e7d592927740fd8f672a70Evan Cheng tii_->isMoveInstr(*MI, SrcReg, DstReg)) 464c8d044e4f779fdcfc5e7d592927740fd8f672a70Evan Cheng CopyMI = MI; 465c8d044e4f779fdcfc5e7d592927740fd8f672a70Evan Cheng handlePhysicalRegisterDef(MBB, MI, MIIdx, getOrCreateInterval(reg), CopyMI); 46624a3cc4c83e5edb25fadf7b8979a26b4451795c6Evan Cheng // Def of a register also defines its sub-registers. 4676f0d024a534af18d9e60b3ea757376cd8a3a980eDan Gohman for (const unsigned* AS = tri_->getSubRegisters(reg); *AS; ++AS) 4686130f66eaae89f8878590796977678afa8448926Evan Cheng // If MI also modifies the sub-register explicitly, avoid processing it 4696130f66eaae89f8878590796977678afa8448926Evan Cheng // more than once. Do not pass in TRI here so it checks for exact match. 4706130f66eaae89f8878590796977678afa8448926Evan Cheng if (!MI->modifiesRegister(*AS)) 47124a3cc4c83e5edb25fadf7b8979a26b4451795c6Evan Cheng handlePhysicalRegisterDef(MBB, MI, MIIdx, getOrCreateInterval(*AS), 0); 472f35fef7060c465dd7b578bf6339a18e8a8911888Chris Lattner } 4734d46e1e521c0df1990ea50f8146d22bd77ea71a6Alkis Evlogimenos} 4744d46e1e521c0df1990ea50f8146d22bd77ea71a6Alkis Evlogimenos 475b371f457b0ea4a652a9f526ba4375c80ae542252Evan Chengvoid LiveIntervals::handleLiveInRegister(MachineBasicBlock *MBB, 4769b25b8ca24d6df2e097741dcc15016772ee4eda7Jim Laskey unsigned MIIdx, 47724a3cc4c83e5edb25fadf7b8979a26b4451795c6Evan Cheng LiveInterval &interval, bool isAlias) { 478b371f457b0ea4a652a9f526ba4375c80ae542252Evan Cheng DOUT << "\t\tlivein register: "; DEBUG(printRegName(interval.reg)); 479b371f457b0ea4a652a9f526ba4375c80ae542252Evan Cheng 480b371f457b0ea4a652a9f526ba4375c80ae542252Evan Cheng // Look for kills, if it reaches a def before it's killed, then it shouldn't 481b371f457b0ea4a652a9f526ba4375c80ae542252Evan Cheng // be considered a livein. 482b371f457b0ea4a652a9f526ba4375c80ae542252Evan Cheng MachineBasicBlock::iterator mi = MBB->begin(); 4839b25b8ca24d6df2e097741dcc15016772ee4eda7Jim Laskey unsigned baseIndex = MIIdx; 4849b25b8ca24d6df2e097741dcc15016772ee4eda7Jim Laskey unsigned start = baseIndex; 485b371f457b0ea4a652a9f526ba4375c80ae542252Evan Cheng unsigned end = start; 486b371f457b0ea4a652a9f526ba4375c80ae542252Evan Cheng while (mi != MBB->end()) { 4876130f66eaae89f8878590796977678afa8448926Evan Cheng if (mi->killsRegister(interval.reg, tri_)) { 488b371f457b0ea4a652a9f526ba4375c80ae542252Evan Cheng DOUT << " killed"; 489b371f457b0ea4a652a9f526ba4375c80ae542252Evan Cheng end = getUseIndex(baseIndex) + 1; 490b371f457b0ea4a652a9f526ba4375c80ae542252Evan Cheng goto exit; 4916130f66eaae89f8878590796977678afa8448926Evan Cheng } else if (mi->modifiesRegister(interval.reg, tri_)) { 492b371f457b0ea4a652a9f526ba4375c80ae542252Evan Cheng // Another instruction redefines the register before it is ever read. 493b371f457b0ea4a652a9f526ba4375c80ae542252Evan Cheng // Then the register is essentially dead at the instruction that defines 494b371f457b0ea4a652a9f526ba4375c80ae542252Evan Cheng // it. Hence its interval is: 495b371f457b0ea4a652a9f526ba4375c80ae542252Evan Cheng // [defSlot(def), defSlot(def)+1) 496b371f457b0ea4a652a9f526ba4375c80ae542252Evan Cheng DOUT << " dead"; 497b371f457b0ea4a652a9f526ba4375c80ae542252Evan Cheng end = getDefIndex(start) + 1; 498b371f457b0ea4a652a9f526ba4375c80ae542252Evan Cheng goto exit; 499b371f457b0ea4a652a9f526ba4375c80ae542252Evan Cheng } 500b371f457b0ea4a652a9f526ba4375c80ae542252Evan Cheng 501b371f457b0ea4a652a9f526ba4375c80ae542252Evan Cheng baseIndex += InstrSlots::NUM; 502b371f457b0ea4a652a9f526ba4375c80ae542252Evan Cheng ++mi; 503b371f457b0ea4a652a9f526ba4375c80ae542252Evan Cheng } 504b371f457b0ea4a652a9f526ba4375c80ae542252Evan Cheng 505b371f457b0ea4a652a9f526ba4375c80ae542252Evan Chengexit: 50675611fb4e6ab253be30ac29a2b15e9bf8c1d146eEvan Cheng // Live-in register might not be used at all. 50775611fb4e6ab253be30ac29a2b15e9bf8c1d146eEvan Cheng if (end == MIIdx) { 508292da949f6c87d6499425d64d37d7c5870ec57adEvan Cheng if (isAlias) { 509292da949f6c87d6499425d64d37d7c5870ec57adEvan Cheng DOUT << " dead"; 51075611fb4e6ab253be30ac29a2b15e9bf8c1d146eEvan Cheng end = getDefIndex(MIIdx) + 1; 511292da949f6c87d6499425d64d37d7c5870ec57adEvan Cheng } else { 512292da949f6c87d6499425d64d37d7c5870ec57adEvan Cheng DOUT << " live through"; 513292da949f6c87d6499425d64d37d7c5870ec57adEvan Cheng end = baseIndex; 514292da949f6c87d6499425d64d37d7c5870ec57adEvan Cheng } 51524a3cc4c83e5edb25fadf7b8979a26b4451795c6Evan Cheng } 51624a3cc4c83e5edb25fadf7b8979a26b4451795c6Evan Cheng 517f3bb2e65d12857f83b273f4ecab013680310bbbcEvan Cheng LiveRange LR(start, end, interval.getNextValue(start, 0, VNInfoAllocator)); 5189b25b8ca24d6df2e097741dcc15016772ee4eda7Jim Laskey interval.addRange(LR); 519f3bb2e65d12857f83b273f4ecab013680310bbbcEvan Cheng interval.addKill(LR.valno, end); 52024c2e5cf7e926452ea5875d027ec0d24d9c19e39Evan Cheng DOUT << " +" << LR << '\n'; 521b371f457b0ea4a652a9f526ba4375c80ae542252Evan Cheng} 522b371f457b0ea4a652a9f526ba4375c80ae542252Evan Cheng 523ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos/// computeIntervals - computes the live intervals for virtual 5244d46e1e521c0df1990ea50f8146d22bd77ea71a6Alkis Evlogimenos/// registers. for some ordering of the machine instructions [1,N] a 52508cec00588ec1a8fa85b208555f006d7396ae7a4Alkis Evlogimenos/// live interval is an interval [i, j) where 1 <= i <= j < N for 526ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos/// which a variable is live 527f7da2c7b0c6293c268881628fc351bed7763f1f4Chris Lattnervoid LiveIntervals::computeIntervals() { 528bdc679d564e67a81792e463f6614b0088f975025Bill Wendling DOUT << "********** COMPUTING LIVE INTERVALS **********\n" 529bdc679d564e67a81792e463f6614b0088f975025Bill Wendling << "********** Function: " 530bdc679d564e67a81792e463f6614b0088f975025Bill Wendling << ((Value*)mf_->getFunction())->getName() << '\n'; 5316b128bdc58a496e9f08e4d09416330320761baffChris Lattner // Track the index of the current machine instr. 5326b128bdc58a496e9f08e4d09416330320761baffChris Lattner unsigned MIIndex = 0; 533428b92eb83b457b71d29d1d4b7900d36a0ce9a53Chris Lattner for (MachineFunction::iterator MBBI = mf_->begin(), E = mf_->end(); 534428b92eb83b457b71d29d1d4b7900d36a0ce9a53Chris Lattner MBBI != E; ++MBBI) { 535428b92eb83b457b71d29d1d4b7900d36a0ce9a53Chris Lattner MachineBasicBlock *MBB = MBBI; 536bdc679d564e67a81792e463f6614b0088f975025Bill Wendling DOUT << ((Value*)MBB->getBasicBlock())->getName() << ":\n"; 5371a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos 538428b92eb83b457b71d29d1d4b7900d36a0ce9a53Chris Lattner MachineBasicBlock::iterator MI = MBB->begin(), miEnd = MBB->end(); 5390c9f92e1ff64ee56724eae444a0442b02f83d0a8Evan Cheng 540cb406c25973b4e88a6c10ad839ef1beeb3664715Dan Gohman // Create intervals for live-ins to this BB first. 541cb406c25973b4e88a6c10ad839ef1beeb3664715Dan Gohman for (MachineBasicBlock::const_livein_iterator LI = MBB->livein_begin(), 542cb406c25973b4e88a6c10ad839ef1beeb3664715Dan Gohman LE = MBB->livein_end(); LI != LE; ++LI) { 543cb406c25973b4e88a6c10ad839ef1beeb3664715Dan Gohman handleLiveInRegister(MBB, MIIndex, getOrCreateInterval(*LI)); 544cb406c25973b4e88a6c10ad839ef1beeb3664715Dan Gohman // Multiple live-ins can alias the same register. 5456f0d024a534af18d9e60b3ea757376cd8a3a980eDan Gohman for (const unsigned* AS = tri_->getSubRegisters(*LI); *AS; ++AS) 546cb406c25973b4e88a6c10ad839ef1beeb3664715Dan Gohman if (!hasInterval(*AS)) 547cb406c25973b4e88a6c10ad839ef1beeb3664715Dan Gohman handleLiveInRegister(MBB, MIIndex, getOrCreateInterval(*AS), 548cb406c25973b4e88a6c10ad839ef1beeb3664715Dan Gohman true); 549dffb2e83ed2546226d09c40aa43524e2392322daChris Lattner } 550dffb2e83ed2546226d09c40aa43524e2392322daChris Lattner 551428b92eb83b457b71d29d1d4b7900d36a0ce9a53Chris Lattner for (; MI != miEnd; ++MI) { 552bdc679d564e67a81792e463f6614b0088f975025Bill Wendling DOUT << MIIndex << "\t" << *MI; 5531a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos 554438f7bc67cf235ccee7e6f7ac7f4ae2186eb8020Evan Cheng // Handle defs. 555428b92eb83b457b71d29d1d4b7900d36a0ce9a53Chris Lattner for (int i = MI->getNumOperands() - 1; i >= 0; --i) { 556428b92eb83b457b71d29d1d4b7900d36a0ce9a53Chris Lattner MachineOperand &MO = MI->getOperand(i); 5571a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // handle register defs - build intervals 558428b92eb83b457b71d29d1d4b7900d36a0ce9a53Chris Lattner if (MO.isRegister() && MO.getReg() && MO.isDef()) 559428b92eb83b457b71d29d1d4b7900d36a0ce9a53Chris Lattner handleRegisterDef(MBB, MI, MIIndex, MO.getReg()); 5601a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos } 5616b128bdc58a496e9f08e4d09416330320761baffChris Lattner 5626b128bdc58a496e9f08e4d09416330320761baffChris Lattner MIIndex += InstrSlots::NUM; 563ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos } 5641a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos } 565ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos} 566b27ef248f579b354aab434f63c417ab1103e47e2Alkis Evlogimenos 5674ca980e7f9ce7b78955307c2d07001a24d3b6befEvan Chengbool LiveIntervals::findLiveInMBBs(const LiveRange &LR, 568a5bfc97da713ec9e185226d44e6adb4d3087b304Evan Cheng SmallVectorImpl<MachineBasicBlock*> &MBBs) const { 5694ca980e7f9ce7b78955307c2d07001a24d3b6befEvan Cheng std::vector<IdxMBBPair>::const_iterator I = 5704ca980e7f9ce7b78955307c2d07001a24d3b6befEvan Cheng std::lower_bound(Idx2MBBMap.begin(), Idx2MBBMap.end(), LR.start); 5714ca980e7f9ce7b78955307c2d07001a24d3b6befEvan Cheng 5724ca980e7f9ce7b78955307c2d07001a24d3b6befEvan Cheng bool ResVal = false; 5734ca980e7f9ce7b78955307c2d07001a24d3b6befEvan Cheng while (I != Idx2MBBMap.end()) { 5744ca980e7f9ce7b78955307c2d07001a24d3b6befEvan Cheng if (LR.end <= I->first) 5754ca980e7f9ce7b78955307c2d07001a24d3b6befEvan Cheng break; 5764ca980e7f9ce7b78955307c2d07001a24d3b6befEvan Cheng MBBs.push_back(I->second); 5774ca980e7f9ce7b78955307c2d07001a24d3b6befEvan Cheng ResVal = true; 5784ca980e7f9ce7b78955307c2d07001a24d3b6befEvan Cheng ++I; 5794ca980e7f9ce7b78955307c2d07001a24d3b6befEvan Cheng } 5804ca980e7f9ce7b78955307c2d07001a24d3b6befEvan Cheng return ResVal; 5814ca980e7f9ce7b78955307c2d07001a24d3b6befEvan Cheng} 5824ca980e7f9ce7b78955307c2d07001a24d3b6befEvan Cheng 5834ca980e7f9ce7b78955307c2d07001a24d3b6befEvan Cheng 584a1613db62fec94845aa8306232fb665273615badAlkis EvlogimenosLiveInterval LiveIntervals::createInterval(unsigned reg) { 5856f0d024a534af18d9e60b3ea757376cd8a3a980eDan Gohman float Weight = TargetRegisterInfo::isPhysicalRegister(reg) ? 5867902c75331fa8f38fc8380f5573d935c0d149ef5Jim Laskey HUGE_VALF : 0.0F; 587a1613db62fec94845aa8306232fb665273615badAlkis Evlogimenos return LiveInterval(reg, Weight); 5889a8b490735d216435862a3d52e669357f165550fAlkis Evlogimenos} 589f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng 590c8d044e4f779fdcfc5e7d592927740fd8f672a70Evan Cheng/// getVNInfoSourceReg - Helper function that parses the specified VNInfo 591c8d044e4f779fdcfc5e7d592927740fd8f672a70Evan Cheng/// copy field and returns the source register that defines it. 592c8d044e4f779fdcfc5e7d592927740fd8f672a70Evan Chengunsigned LiveIntervals::getVNInfoSourceReg(const VNInfo *VNI) const { 593c8d044e4f779fdcfc5e7d592927740fd8f672a70Evan Cheng if (!VNI->copy) 594c8d044e4f779fdcfc5e7d592927740fd8f672a70Evan Cheng return 0; 595c8d044e4f779fdcfc5e7d592927740fd8f672a70Evan Cheng 596c8d044e4f779fdcfc5e7d592927740fd8f672a70Evan Cheng if (VNI->copy->getOpcode() == TargetInstrInfo::EXTRACT_SUBREG) 597c8d044e4f779fdcfc5e7d592927740fd8f672a70Evan Cheng return VNI->copy->getOperand(1).getReg(); 5987e073baedb8232b9519dbe15ea141ff98ccfe6aeEvan Cheng if (VNI->copy->getOpcode() == TargetInstrInfo::INSERT_SUBREG) 5997e073baedb8232b9519dbe15ea141ff98ccfe6aeEvan Cheng return VNI->copy->getOperand(2).getReg(); 600c8d044e4f779fdcfc5e7d592927740fd8f672a70Evan Cheng unsigned SrcReg, DstReg; 601c8d044e4f779fdcfc5e7d592927740fd8f672a70Evan Cheng if (tii_->isMoveInstr(*VNI->copy, SrcReg, DstReg)) 602c8d044e4f779fdcfc5e7d592927740fd8f672a70Evan Cheng return SrcReg; 603c8d044e4f779fdcfc5e7d592927740fd8f672a70Evan Cheng assert(0 && "Unrecognized copy instruction!"); 604c8d044e4f779fdcfc5e7d592927740fd8f672a70Evan Cheng return 0; 605c8d044e4f779fdcfc5e7d592927740fd8f672a70Evan Cheng} 606f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng 607f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng//===----------------------------------------------------------------------===// 608f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng// Register allocator hooks. 609f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng// 610f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng 611d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng/// getReMatImplicitUse - If the remat definition MI has one (for now, we only 612d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng/// allow one) virtual register operand, then its uses are implicitly using 613d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng/// the register. Returns the virtual register. 614d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Chengunsigned LiveIntervals::getReMatImplicitUse(const LiveInterval &li, 615d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng MachineInstr *MI) const { 616d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng unsigned RegOp = 0; 617d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) { 618d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng MachineOperand &MO = MI->getOperand(i); 619d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng if (!MO.isRegister() || !MO.isUse()) 620d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng continue; 621d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng unsigned Reg = MO.getReg(); 622d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng if (Reg == 0 || Reg == li.reg) 623d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng continue; 624d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng // FIXME: For now, only remat MI with at most one register operand. 625d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng assert(!RegOp && 626d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng "Can't rematerialize instruction with multiple register operand!"); 627d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng RegOp = MO.getReg(); 628d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng break; 629d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng } 630d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng return RegOp; 631d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng} 632d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng 633d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng/// isValNoAvailableAt - Return true if the val# of the specified interval 634d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng/// which reaches the given instruction also reaches the specified use index. 635d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Chengbool LiveIntervals::isValNoAvailableAt(const LiveInterval &li, MachineInstr *MI, 636d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng unsigned UseIdx) const { 637d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng unsigned Index = getInstructionIndex(MI); 638d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng VNInfo *ValNo = li.FindLiveRangeContaining(Index)->valno; 639d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng LiveInterval::const_iterator UI = li.FindLiveRangeContaining(UseIdx); 640d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng return UI != li.end() && UI->valno == ValNo; 641d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng} 642d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng 643f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng/// isReMaterializable - Returns true if the definition MI of the specified 644f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng/// val# of the specified interval is re-materializable. 645f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Chengbool LiveIntervals::isReMaterializable(const LiveInterval &li, 6465ef3a04b542c4e585276768fa9ca2af698ef5c87Evan Cheng const VNInfo *ValNo, MachineInstr *MI, 6475ef3a04b542c4e585276768fa9ca2af698ef5c87Evan Cheng bool &isLoad) { 648f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng if (DisableReMat) 649f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng return false; 650f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng 6515ef3a04b542c4e585276768fa9ca2af698ef5c87Evan Cheng isLoad = false; 65220ccded7dec5b90e58f649f4fb95b166a642b8cbEvan Cheng if (MI->getOpcode() == TargetInstrInfo::IMPLICIT_DEF) 653d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng return true; 654dd3465eed17cdf226bdb465e604dfa851d36029dEvan Cheng 655dd3465eed17cdf226bdb465e604dfa851d36029dEvan Cheng int FrameIdx = 0; 656dd3465eed17cdf226bdb465e604dfa851d36029dEvan Cheng if (tii_->isLoadFromStackSlot(MI, FrameIdx) && 657249ded3fa8884f91fded869fb6e251b8aebb0376Evan Cheng mf_->getFrameInfo()->isImmutableObjectIndex(FrameIdx)) 65879a0c1e46c4f7d8a2a06f4ef3e2c54d883c7fe25Evan Cheng // FIXME: Let target specific isReallyTriviallyReMaterializable determines 65979a0c1e46c4f7d8a2a06f4ef3e2c54d883c7fe25Evan Cheng // this but remember this is not safe to fold into a two-address 66079a0c1e46c4f7d8a2a06f4ef3e2c54d883c7fe25Evan Cheng // instruction. 661249ded3fa8884f91fded869fb6e251b8aebb0376Evan Cheng // This is a load from fixed stack slot. It can be rematerialized. 662dd3465eed17cdf226bdb465e604dfa851d36029dEvan Cheng return true; 663dd3465eed17cdf226bdb465e604dfa851d36029dEvan Cheng 664d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng if (tii_->isTriviallyReMaterializable(MI)) { 66520ccded7dec5b90e58f649f4fb95b166a642b8cbEvan Cheng const TargetInstrDesc &TID = MI->getDesc(); 666749c6f6b5ed301c84aac562e414486549d7b98ebChris Lattner isLoad = TID.isSimpleLoad(); 667d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng 668d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng unsigned ImpUse = getReMatImplicitUse(li, MI); 669d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng if (ImpUse) { 670d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng const LiveInterval &ImpLi = getInterval(ImpUse); 671d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng for (MachineRegisterInfo::use_iterator ri = mri_->use_begin(li.reg), 672d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng re = mri_->use_end(); ri != re; ++ri) { 673d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng MachineInstr *UseMI = &*ri; 674d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng unsigned UseIdx = getInstructionIndex(UseMI); 675d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng if (li.FindLiveRangeContaining(UseIdx)->valno != ValNo) 676d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng continue; 677298bbe82cb390235f7b8ab4bd550feff909e0c3dEvan Cheng if (!isValNoAvailableAt(ImpLi, MI, UseIdx)) 678d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng return false; 679d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng } 680d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng } 681f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng return true; 6825ef3a04b542c4e585276768fa9ca2af698ef5c87Evan Cheng } 683f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng 684dd3465eed17cdf226bdb465e604dfa851d36029dEvan Cheng return false; 6855ef3a04b542c4e585276768fa9ca2af698ef5c87Evan Cheng} 6865ef3a04b542c4e585276768fa9ca2af698ef5c87Evan Cheng 6875ef3a04b542c4e585276768fa9ca2af698ef5c87Evan Cheng/// isReMaterializable - Returns true if every definition of MI of every 6885ef3a04b542c4e585276768fa9ca2af698ef5c87Evan Cheng/// val# of the specified interval is re-materializable. 6895ef3a04b542c4e585276768fa9ca2af698ef5c87Evan Chengbool LiveIntervals::isReMaterializable(const LiveInterval &li, bool &isLoad) { 6905ef3a04b542c4e585276768fa9ca2af698ef5c87Evan Cheng isLoad = false; 6915ef3a04b542c4e585276768fa9ca2af698ef5c87Evan Cheng for (LiveInterval::const_vni_iterator i = li.vni_begin(), e = li.vni_end(); 6925ef3a04b542c4e585276768fa9ca2af698ef5c87Evan Cheng i != e; ++i) { 6935ef3a04b542c4e585276768fa9ca2af698ef5c87Evan Cheng const VNInfo *VNI = *i; 6945ef3a04b542c4e585276768fa9ca2af698ef5c87Evan Cheng unsigned DefIdx = VNI->def; 6955ef3a04b542c4e585276768fa9ca2af698ef5c87Evan Cheng if (DefIdx == ~1U) 6965ef3a04b542c4e585276768fa9ca2af698ef5c87Evan Cheng continue; // Dead val#. 6975ef3a04b542c4e585276768fa9ca2af698ef5c87Evan Cheng // Is the def for the val# rematerializable? 6985ef3a04b542c4e585276768fa9ca2af698ef5c87Evan Cheng if (DefIdx == ~0u) 6995ef3a04b542c4e585276768fa9ca2af698ef5c87Evan Cheng return false; 7005ef3a04b542c4e585276768fa9ca2af698ef5c87Evan Cheng MachineInstr *ReMatDefMI = getInstructionFromIndex(DefIdx); 7015ef3a04b542c4e585276768fa9ca2af698ef5c87Evan Cheng bool DefIsLoad = false; 702d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng if (!ReMatDefMI || 703d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng !isReMaterializable(li, VNI, ReMatDefMI, DefIsLoad)) 704f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng return false; 7055ef3a04b542c4e585276768fa9ca2af698ef5c87Evan Cheng isLoad |= DefIsLoad; 706f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng } 707f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng return true; 708f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng} 709f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng 71079a0c1e46c4f7d8a2a06f4ef3e2c54d883c7fe25Evan Cheng/// FilterFoldedOps - Filter out two-address use operands. Return 71179a0c1e46c4f7d8a2a06f4ef3e2c54d883c7fe25Evan Cheng/// true if it finds any issue with the operands that ought to prevent 71279a0c1e46c4f7d8a2a06f4ef3e2c54d883c7fe25Evan Cheng/// folding. 71379a0c1e46c4f7d8a2a06f4ef3e2c54d883c7fe25Evan Chengstatic bool FilterFoldedOps(MachineInstr *MI, 71479a0c1e46c4f7d8a2a06f4ef3e2c54d883c7fe25Evan Cheng SmallVector<unsigned, 2> &Ops, 71579a0c1e46c4f7d8a2a06f4ef3e2c54d883c7fe25Evan Cheng unsigned &MRInfo, 71679a0c1e46c4f7d8a2a06f4ef3e2c54d883c7fe25Evan Cheng SmallVector<unsigned, 2> &FoldOps) { 717749c6f6b5ed301c84aac562e414486549d7b98ebChris Lattner const TargetInstrDesc &TID = MI->getDesc(); 7186e141fd04897e5eb4925bb6351297170ebd8a756Evan Cheng 71979a0c1e46c4f7d8a2a06f4ef3e2c54d883c7fe25Evan Cheng MRInfo = 0; 720aee4af68ae2016afc5b4ec0c430e539c5810a766Evan Cheng for (unsigned i = 0, e = Ops.size(); i != e; ++i) { 721aee4af68ae2016afc5b4ec0c430e539c5810a766Evan Cheng unsigned OpIdx = Ops[i]; 722d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng MachineOperand &MO = MI->getOperand(OpIdx); 723aee4af68ae2016afc5b4ec0c430e539c5810a766Evan Cheng // FIXME: fold subreg use. 724d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng if (MO.getSubReg()) 72579a0c1e46c4f7d8a2a06f4ef3e2c54d883c7fe25Evan Cheng return true; 726d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng if (MO.isDef()) 727aee4af68ae2016afc5b4ec0c430e539c5810a766Evan Cheng MRInfo |= (unsigned)VirtRegMap::isMod; 728aee4af68ae2016afc5b4ec0c430e539c5810a766Evan Cheng else { 729aee4af68ae2016afc5b4ec0c430e539c5810a766Evan Cheng // Filter out two-address use operand(s). 730d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng if (!MO.isImplicit() && 731d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng TID.getOperandConstraint(OpIdx, TOI::TIED_TO) != -1) { 732aee4af68ae2016afc5b4ec0c430e539c5810a766Evan Cheng MRInfo = VirtRegMap::isModRef; 733aee4af68ae2016afc5b4ec0c430e539c5810a766Evan Cheng continue; 734aee4af68ae2016afc5b4ec0c430e539c5810a766Evan Cheng } 735aee4af68ae2016afc5b4ec0c430e539c5810a766Evan Cheng MRInfo |= (unsigned)VirtRegMap::isRef; 736aee4af68ae2016afc5b4ec0c430e539c5810a766Evan Cheng } 737aee4af68ae2016afc5b4ec0c430e539c5810a766Evan Cheng FoldOps.push_back(OpIdx); 738e62f97c094dba44e4c259d20135167fa91912eeaEvan Cheng } 73979a0c1e46c4f7d8a2a06f4ef3e2c54d883c7fe25Evan Cheng return false; 74079a0c1e46c4f7d8a2a06f4ef3e2c54d883c7fe25Evan Cheng} 74179a0c1e46c4f7d8a2a06f4ef3e2c54d883c7fe25Evan Cheng 74279a0c1e46c4f7d8a2a06f4ef3e2c54d883c7fe25Evan Cheng 74379a0c1e46c4f7d8a2a06f4ef3e2c54d883c7fe25Evan Cheng/// tryFoldMemoryOperand - Attempts to fold either a spill / restore from 74479a0c1e46c4f7d8a2a06f4ef3e2c54d883c7fe25Evan Cheng/// slot / to reg or any rematerialized load into ith operand of specified 74579a0c1e46c4f7d8a2a06f4ef3e2c54d883c7fe25Evan Cheng/// MI. If it is successul, MI is updated with the newly created MI and 74679a0c1e46c4f7d8a2a06f4ef3e2c54d883c7fe25Evan Cheng/// returns true. 74779a0c1e46c4f7d8a2a06f4ef3e2c54d883c7fe25Evan Chengbool LiveIntervals::tryFoldMemoryOperand(MachineInstr* &MI, 74879a0c1e46c4f7d8a2a06f4ef3e2c54d883c7fe25Evan Cheng VirtRegMap &vrm, MachineInstr *DefMI, 74979a0c1e46c4f7d8a2a06f4ef3e2c54d883c7fe25Evan Cheng unsigned InstrIdx, 75079a0c1e46c4f7d8a2a06f4ef3e2c54d883c7fe25Evan Cheng SmallVector<unsigned, 2> &Ops, 75179a0c1e46c4f7d8a2a06f4ef3e2c54d883c7fe25Evan Cheng bool isSS, int Slot, unsigned Reg) { 75279a0c1e46c4f7d8a2a06f4ef3e2c54d883c7fe25Evan Cheng // If it is an implicit def instruction, just delete it. 75320ccded7dec5b90e58f649f4fb95b166a642b8cbEvan Cheng if (MI->getOpcode() == TargetInstrInfo::IMPLICIT_DEF) { 75479a0c1e46c4f7d8a2a06f4ef3e2c54d883c7fe25Evan Cheng RemoveMachineInstrFromMaps(MI); 75579a0c1e46c4f7d8a2a06f4ef3e2c54d883c7fe25Evan Cheng vrm.RemoveMachineInstrFromMaps(MI); 75679a0c1e46c4f7d8a2a06f4ef3e2c54d883c7fe25Evan Cheng MI->eraseFromParent(); 75779a0c1e46c4f7d8a2a06f4ef3e2c54d883c7fe25Evan Cheng ++numFolds; 75879a0c1e46c4f7d8a2a06f4ef3e2c54d883c7fe25Evan Cheng return true; 75979a0c1e46c4f7d8a2a06f4ef3e2c54d883c7fe25Evan Cheng } 76079a0c1e46c4f7d8a2a06f4ef3e2c54d883c7fe25Evan Cheng 76179a0c1e46c4f7d8a2a06f4ef3e2c54d883c7fe25Evan Cheng // Filter the list of operand indexes that are to be folded. Abort if 76279a0c1e46c4f7d8a2a06f4ef3e2c54d883c7fe25Evan Cheng // any operand will prevent folding. 76379a0c1e46c4f7d8a2a06f4ef3e2c54d883c7fe25Evan Cheng unsigned MRInfo = 0; 76479a0c1e46c4f7d8a2a06f4ef3e2c54d883c7fe25Evan Cheng SmallVector<unsigned, 2> FoldOps; 76579a0c1e46c4f7d8a2a06f4ef3e2c54d883c7fe25Evan Cheng if (FilterFoldedOps(MI, Ops, MRInfo, FoldOps)) 76679a0c1e46c4f7d8a2a06f4ef3e2c54d883c7fe25Evan Cheng return false; 767cddbb83ea82e98658d9f530c50a7b9d23249afc2Evan Cheng 768427f4c106ac14dcf323dc1bbaf1b8040da03c3c7Evan Cheng // The only time it's safe to fold into a two address instruction is when 769427f4c106ac14dcf323dc1bbaf1b8040da03c3c7Evan Cheng // it's folding reload and spill from / into a spill stack slot. 770427f4c106ac14dcf323dc1bbaf1b8040da03c3c7Evan Cheng if (DefMI && (MRInfo & VirtRegMap::isMod)) 771249ded3fa8884f91fded869fb6e251b8aebb0376Evan Cheng return false; 772249ded3fa8884f91fded869fb6e251b8aebb0376Evan Cheng 773f2f8c2ae07b7d9bdbf1b89781c573c7af2bd5e1bEvan Cheng MachineInstr *fmi = isSS ? tii_->foldMemoryOperand(*mf_, MI, FoldOps, Slot) 774f2f8c2ae07b7d9bdbf1b89781c573c7af2bd5e1bEvan Cheng : tii_->foldMemoryOperand(*mf_, MI, FoldOps, DefMI); 775f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng if (fmi) { 776d36531249a9a9500e516148e7e72d4c0a7a4d0eeEvan Cheng // Remember this instruction uses the spill slot. 777d36531249a9a9500e516148e7e72d4c0a7a4d0eeEvan Cheng if (isSS) vrm.addSpillSlotUse(Slot, fmi); 778d36531249a9a9500e516148e7e72d4c0a7a4d0eeEvan Cheng 779f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng // Attempt to fold the memory reference into the instruction. If 780f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng // we can do this, we don't need to insert spill code. 781f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng if (lv_) 782f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng lv_->instructionChanged(MI, fmi); 78381a038218171860ee4c382849c647d3dc841fe8bEvan Cheng else 7846f0d024a534af18d9e60b3ea757376cd8a3a980eDan Gohman fmi->copyKillDeadInfo(MI, tri_); 785f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng MachineBasicBlock &MBB = *MI->getParent(); 7868480293f41c11c22762164449e41cd3adb0dd7d8Evan Cheng if (isSS && !mf_->getFrameInfo()->isImmutableObjectIndex(Slot)) 787aee4af68ae2016afc5b4ec0c430e539c5810a766Evan Cheng vrm.virtFolded(Reg, MI, fmi, (VirtRegMap::ModRef)MRInfo); 78881a038218171860ee4c382849c647d3dc841fe8bEvan Cheng vrm.transferSpillPts(MI, fmi); 7890cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng vrm.transferRestorePts(MI, fmi); 790c1f53c742620dd4f2460685477303002bba8a8d8Evan Cheng vrm.transferEmergencySpills(MI, fmi); 791f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng mi2iMap_.erase(MI); 792cddbb83ea82e98658d9f530c50a7b9d23249afc2Evan Cheng i2miMap_[InstrIdx /InstrSlots::NUM] = fmi; 793cddbb83ea82e98658d9f530c50a7b9d23249afc2Evan Cheng mi2iMap_[fmi] = InstrIdx; 794f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng MI = MBB.insert(MBB.erase(MI), fmi); 7950cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng ++numFolds; 796f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng return true; 797f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng } 798f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng return false; 799f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng} 800f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng 801018f9b020bb12b731b0a7081578e5f82fb35092dEvan Cheng/// canFoldMemoryOperand - Returns true if the specified load / store 802018f9b020bb12b731b0a7081578e5f82fb35092dEvan Cheng/// folding is possible. 803018f9b020bb12b731b0a7081578e5f82fb35092dEvan Chengbool LiveIntervals::canFoldMemoryOperand(MachineInstr *MI, 80479a0c1e46c4f7d8a2a06f4ef3e2c54d883c7fe25Evan Cheng SmallVector<unsigned, 2> &Ops, 8053c75ba858b4e2070993cc1241ba74ead17f647d6Evan Cheng bool ReMat) const { 80679a0c1e46c4f7d8a2a06f4ef3e2c54d883c7fe25Evan Cheng // Filter the list of operand indexes that are to be folded. Abort if 80779a0c1e46c4f7d8a2a06f4ef3e2c54d883c7fe25Evan Cheng // any operand will prevent folding. 80879a0c1e46c4f7d8a2a06f4ef3e2c54d883c7fe25Evan Cheng unsigned MRInfo = 0; 809018f9b020bb12b731b0a7081578e5f82fb35092dEvan Cheng SmallVector<unsigned, 2> FoldOps; 81079a0c1e46c4f7d8a2a06f4ef3e2c54d883c7fe25Evan Cheng if (FilterFoldedOps(MI, Ops, MRInfo, FoldOps)) 81179a0c1e46c4f7d8a2a06f4ef3e2c54d883c7fe25Evan Cheng return false; 812018f9b020bb12b731b0a7081578e5f82fb35092dEvan Cheng 8133c75ba858b4e2070993cc1241ba74ead17f647d6Evan Cheng // It's only legal to remat for a use, not a def. 8143c75ba858b4e2070993cc1241ba74ead17f647d6Evan Cheng if (ReMat && (MRInfo & VirtRegMap::isMod)) 81579a0c1e46c4f7d8a2a06f4ef3e2c54d883c7fe25Evan Cheng return false; 816018f9b020bb12b731b0a7081578e5f82fb35092dEvan Cheng 817d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng return tii_->canFoldMemoryOperand(MI, FoldOps); 818d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng} 819d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng 82081a038218171860ee4c382849c647d3dc841fe8bEvan Chengbool LiveIntervals::intervalIsInOneMBB(const LiveInterval &li) const { 82181a038218171860ee4c382849c647d3dc841fe8bEvan Cheng SmallPtrSet<MachineBasicBlock*, 4> MBBs; 82281a038218171860ee4c382849c647d3dc841fe8bEvan Cheng for (LiveInterval::Ranges::const_iterator 82381a038218171860ee4c382849c647d3dc841fe8bEvan Cheng I = li.ranges.begin(), E = li.ranges.end(); I != E; ++I) { 82481a038218171860ee4c382849c647d3dc841fe8bEvan Cheng std::vector<IdxMBBPair>::const_iterator II = 82581a038218171860ee4c382849c647d3dc841fe8bEvan Cheng std::lower_bound(Idx2MBBMap.begin(), Idx2MBBMap.end(), I->start); 82681a038218171860ee4c382849c647d3dc841fe8bEvan Cheng if (II == Idx2MBBMap.end()) 82781a038218171860ee4c382849c647d3dc841fe8bEvan Cheng continue; 82881a038218171860ee4c382849c647d3dc841fe8bEvan Cheng if (I->end > II->first) // crossing a MBB. 82981a038218171860ee4c382849c647d3dc841fe8bEvan Cheng return false; 83081a038218171860ee4c382849c647d3dc841fe8bEvan Cheng MBBs.insert(II->second); 83181a038218171860ee4c382849c647d3dc841fe8bEvan Cheng if (MBBs.size() > 1) 83281a038218171860ee4c382849c647d3dc841fe8bEvan Cheng return false; 83381a038218171860ee4c382849c647d3dc841fe8bEvan Cheng } 83481a038218171860ee4c382849c647d3dc841fe8bEvan Cheng return true; 83581a038218171860ee4c382849c647d3dc841fe8bEvan Cheng} 83681a038218171860ee4c382849c647d3dc841fe8bEvan Cheng 837d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng/// rewriteImplicitOps - Rewrite implicit use operands of MI (i.e. uses of 838d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng/// interval on to-be re-materialized operands of MI) with new register. 839d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Chengvoid LiveIntervals::rewriteImplicitOps(const LiveInterval &li, 840d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng MachineInstr *MI, unsigned NewVReg, 841d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng VirtRegMap &vrm) { 842d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng // There is an implicit use. That means one of the other operand is 843d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng // being remat'ed and the remat'ed instruction has li.reg as an 844d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng // use operand. Make sure we rewrite that as well. 845d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) { 846d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng MachineOperand &MO = MI->getOperand(i); 847d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng if (!MO.isRegister()) 848d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng continue; 849d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng unsigned Reg = MO.getReg(); 850d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng if (Reg == 0 || TargetRegisterInfo::isPhysicalRegister(Reg)) 851d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng continue; 852d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng if (!vrm.isReMaterialized(Reg)) 853d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng continue; 854d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng MachineInstr *ReMatMI = vrm.getReMaterializedMI(Reg); 8556130f66eaae89f8878590796977678afa8448926Evan Cheng MachineOperand *UseMO = ReMatMI->findRegisterUseOperand(li.reg); 8566130f66eaae89f8878590796977678afa8448926Evan Cheng if (UseMO) 8576130f66eaae89f8878590796977678afa8448926Evan Cheng UseMO->setReg(NewVReg); 858d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng } 859d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng} 860d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng 861f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng/// rewriteInstructionForSpills, rewriteInstructionsForSpills - Helper functions 862f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng/// for addIntervalsForSpills to rewrite uses / defs for the given live range. 863018f9b020bb12b731b0a7081578e5f82fb35092dEvan Chengbool LiveIntervals:: 864d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan ChengrewriteInstructionForSpills(const LiveInterval &li, const VNInfo *VNI, 865d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng bool TrySplit, unsigned index, unsigned end, MachineInstr *MI, 86681a038218171860ee4c382849c647d3dc841fe8bEvan Cheng MachineInstr *ReMatOrigDefMI, MachineInstr *ReMatDefMI, 867f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng unsigned Slot, int LdSlot, 868f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng bool isLoad, bool isLoadSS, bool DefIsReMat, bool CanDelete, 869d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng VirtRegMap &vrm, 870f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng const TargetRegisterClass* rc, 871f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng SmallVector<int, 4> &ReMatIds, 87222f07ffd27d1d721634d502c37267721d2e025cfEvan Cheng const MachineLoopInfo *loopInfo, 873313d4b809326f3e04814f94e5b8ae05649d8e0f6Evan Cheng unsigned &NewVReg, unsigned ImpUse, bool &HasDef, bool &HasUse, 8741953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng std::map<unsigned,unsigned> &MBBVRegsMap, 875f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng std::vector<LiveInterval*> &NewLIs) { 876018f9b020bb12b731b0a7081578e5f82fb35092dEvan Cheng bool CanFold = false; 877f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng RestartInstruction: 878f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng for (unsigned i = 0; i != MI->getNumOperands(); ++i) { 879f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng MachineOperand& mop = MI->getOperand(i); 880f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng if (!mop.isRegister()) 881f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng continue; 882f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng unsigned Reg = mop.getReg(); 883f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng unsigned RegI = Reg; 8846f0d024a534af18d9e60b3ea757376cd8a3a980eDan Gohman if (Reg == 0 || TargetRegisterInfo::isPhysicalRegister(Reg)) 885f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng continue; 886f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng if (Reg != li.reg) 887f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng continue; 888f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng 889f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng bool TryFold = !DefIsReMat; 890cb3c330d39442130d0587208d673ce9c33c7008fEvan Cheng bool FoldSS = true; // Default behavior unless it's a remat. 891f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng int FoldSlot = Slot; 892f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng if (DefIsReMat) { 893f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng // If this is the rematerializable definition MI itself and 894f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng // all of its uses are rematerialized, simply delete it. 89581a038218171860ee4c382849c647d3dc841fe8bEvan Cheng if (MI == ReMatOrigDefMI && CanDelete) { 896cddbb83ea82e98658d9f530c50a7b9d23249afc2Evan Cheng DOUT << "\t\t\t\tErasing re-materlizable def: "; 897cddbb83ea82e98658d9f530c50a7b9d23249afc2Evan Cheng DOUT << MI << '\n'; 898f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng RemoveMachineInstrFromMaps(MI); 899cada245d06959831b90f8c29f92e77beda4b71cbEvan Cheng vrm.RemoveMachineInstrFromMaps(MI); 900f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng MI->eraseFromParent(); 901f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng break; 902f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng } 903f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng 904f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng // If def for this use can't be rematerialized, then try folding. 9050cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng // If def is rematerializable and it's a load, also try folding. 906cb3c330d39442130d0587208d673ce9c33c7008fEvan Cheng TryFold = !ReMatDefMI || (ReMatDefMI && (MI == ReMatOrigDefMI || isLoad)); 907f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng if (isLoad) { 908f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng // Try fold loads (from stack slot, constant pool, etc.) into uses. 909f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng FoldSS = isLoadSS; 910f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng FoldSlot = LdSlot; 911f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng } 912f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng } 913f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng 914f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng // Scan all of the operands of this instruction rewriting operands 915f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng // to use NewVReg instead of li.reg as appropriate. We do this for 916f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng // two reasons: 917f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng // 918f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng // 1. If the instr reads the same spilled vreg multiple times, we 919f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng // want to reuse the NewVReg. 920f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng // 2. If the instr is a two-addr instruction, we are required to 921f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng // keep the src/dst regs pinned. 922f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng // 923f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng // Keep track of whether we replace a use and/or def so that we can 924f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng // create the spill interval with the appropriate range. 925cddbb83ea82e98658d9f530c50a7b9d23249afc2Evan Cheng 92681a038218171860ee4c382849c647d3dc841fe8bEvan Cheng HasUse = mop.isUse(); 92781a038218171860ee4c382849c647d3dc841fe8bEvan Cheng HasDef = mop.isDef(); 928aee4af68ae2016afc5b4ec0c430e539c5810a766Evan Cheng SmallVector<unsigned, 2> Ops; 929aee4af68ae2016afc5b4ec0c430e539c5810a766Evan Cheng Ops.push_back(i); 930f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng for (unsigned j = i+1, e = MI->getNumOperands(); j != e; ++j) { 931aee4af68ae2016afc5b4ec0c430e539c5810a766Evan Cheng const MachineOperand &MOj = MI->getOperand(j); 932aee4af68ae2016afc5b4ec0c430e539c5810a766Evan Cheng if (!MOj.isRegister()) 933f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng continue; 934aee4af68ae2016afc5b4ec0c430e539c5810a766Evan Cheng unsigned RegJ = MOj.getReg(); 9356f0d024a534af18d9e60b3ea757376cd8a3a980eDan Gohman if (RegJ == 0 || TargetRegisterInfo::isPhysicalRegister(RegJ)) 936f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng continue; 937f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng if (RegJ == RegI) { 938aee4af68ae2016afc5b4ec0c430e539c5810a766Evan Cheng Ops.push_back(j); 939aee4af68ae2016afc5b4ec0c430e539c5810a766Evan Cheng HasUse |= MOj.isUse(); 940aee4af68ae2016afc5b4ec0c430e539c5810a766Evan Cheng HasDef |= MOj.isDef(); 941f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng } 942f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng } 943f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng 944018f9b020bb12b731b0a7081578e5f82fb35092dEvan Cheng if (TryFold) { 945018f9b020bb12b731b0a7081578e5f82fb35092dEvan Cheng // Do not fold load / store here if we are splitting. We'll find an 946018f9b020bb12b731b0a7081578e5f82fb35092dEvan Cheng // optimal point to insert a load / store later. 947018f9b020bb12b731b0a7081578e5f82fb35092dEvan Cheng if (!TrySplit) { 948018f9b020bb12b731b0a7081578e5f82fb35092dEvan Cheng if (tryFoldMemoryOperand(MI, vrm, ReMatDefMI, index, 949018f9b020bb12b731b0a7081578e5f82fb35092dEvan Cheng Ops, FoldSS, FoldSlot, Reg)) { 950018f9b020bb12b731b0a7081578e5f82fb35092dEvan Cheng // Folding the load/store can completely change the instruction in 951018f9b020bb12b731b0a7081578e5f82fb35092dEvan Cheng // unpredictable ways, rescan it from the beginning. 952018f9b020bb12b731b0a7081578e5f82fb35092dEvan Cheng HasUse = false; 953018f9b020bb12b731b0a7081578e5f82fb35092dEvan Cheng HasDef = false; 954018f9b020bb12b731b0a7081578e5f82fb35092dEvan Cheng CanFold = false; 9557e073baedb8232b9519dbe15ea141ff98ccfe6aeEvan Cheng if (isRemoved(MI)) 9567e073baedb8232b9519dbe15ea141ff98ccfe6aeEvan Cheng break; 957018f9b020bb12b731b0a7081578e5f82fb35092dEvan Cheng goto RestartInstruction; 958018f9b020bb12b731b0a7081578e5f82fb35092dEvan Cheng } 959018f9b020bb12b731b0a7081578e5f82fb35092dEvan Cheng } else { 9603c75ba858b4e2070993cc1241ba74ead17f647d6Evan Cheng CanFold = canFoldMemoryOperand(MI, Ops, DefIsReMat); 961018f9b020bb12b731b0a7081578e5f82fb35092dEvan Cheng } 9626e141fd04897e5eb4925bb6351297170ebd8a756Evan Cheng } else 9636e141fd04897e5eb4925bb6351297170ebd8a756Evan Cheng CanFold = false; 964cddbb83ea82e98658d9f530c50a7b9d23249afc2Evan Cheng 965cddbb83ea82e98658d9f530c50a7b9d23249afc2Evan Cheng // Create a new virtual register for the spill interval. 966cddbb83ea82e98658d9f530c50a7b9d23249afc2Evan Cheng bool CreatedNewVReg = false; 967cddbb83ea82e98658d9f530c50a7b9d23249afc2Evan Cheng if (NewVReg == 0) { 968d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng NewVReg = mri_->createVirtualRegister(rc); 969cddbb83ea82e98658d9f530c50a7b9d23249afc2Evan Cheng vrm.grow(); 970cddbb83ea82e98658d9f530c50a7b9d23249afc2Evan Cheng CreatedNewVReg = true; 971cddbb83ea82e98658d9f530c50a7b9d23249afc2Evan Cheng } 972cddbb83ea82e98658d9f530c50a7b9d23249afc2Evan Cheng mop.setReg(NewVReg); 973d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng if (mop.isImplicit()) 974d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng rewriteImplicitOps(li, MI, NewVReg, vrm); 975cddbb83ea82e98658d9f530c50a7b9d23249afc2Evan Cheng 976cddbb83ea82e98658d9f530c50a7b9d23249afc2Evan Cheng // Reuse NewVReg for other reads. 977d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng for (unsigned j = 0, e = Ops.size(); j != e; ++j) { 978d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng MachineOperand &mopj = MI->getOperand(Ops[j]); 979d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng mopj.setReg(NewVReg); 980d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng if (mopj.isImplicit()) 981d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng rewriteImplicitOps(li, MI, NewVReg, vrm); 982d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng } 983cddbb83ea82e98658d9f530c50a7b9d23249afc2Evan Cheng 98481a038218171860ee4c382849c647d3dc841fe8bEvan Cheng if (CreatedNewVReg) { 98581a038218171860ee4c382849c647d3dc841fe8bEvan Cheng if (DefIsReMat) { 98681a038218171860ee4c382849c647d3dc841fe8bEvan Cheng vrm.setVirtIsReMaterialized(NewVReg, ReMatDefMI/*, CanDelete*/); 987d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng if (ReMatIds[VNI->id] == VirtRegMap::MAX_STACK_SLOT) { 98881a038218171860ee4c382849c647d3dc841fe8bEvan Cheng // Each valnum may have its own remat id. 989d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng ReMatIds[VNI->id] = vrm.assignVirtReMatId(NewVReg); 99081a038218171860ee4c382849c647d3dc841fe8bEvan Cheng } else { 991d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng vrm.assignVirtReMatId(NewVReg, ReMatIds[VNI->id]); 99281a038218171860ee4c382849c647d3dc841fe8bEvan Cheng } 99381a038218171860ee4c382849c647d3dc841fe8bEvan Cheng if (!CanDelete || (HasUse && HasDef)) { 99481a038218171860ee4c382849c647d3dc841fe8bEvan Cheng // If this is a two-addr instruction then its use operands are 99581a038218171860ee4c382849c647d3dc841fe8bEvan Cheng // rematerializable but its def is not. It should be assigned a 99681a038218171860ee4c382849c647d3dc841fe8bEvan Cheng // stack slot. 99781a038218171860ee4c382849c647d3dc841fe8bEvan Cheng vrm.assignVirt2StackSlot(NewVReg, Slot); 99881a038218171860ee4c382849c647d3dc841fe8bEvan Cheng } 999f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng } else { 1000f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng vrm.assignVirt2StackSlot(NewVReg, Slot); 1001f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng } 1002cb3c330d39442130d0587208d673ce9c33c7008fEvan Cheng } else if (HasUse && HasDef && 1003cb3c330d39442130d0587208d673ce9c33c7008fEvan Cheng vrm.getStackSlot(NewVReg) == VirtRegMap::NO_STACK_SLOT) { 1004cb3c330d39442130d0587208d673ce9c33c7008fEvan Cheng // If this interval hasn't been assigned a stack slot (because earlier 1005cb3c330d39442130d0587208d673ce9c33c7008fEvan Cheng // def is a deleted remat def), do it now. 1006cb3c330d39442130d0587208d673ce9c33c7008fEvan Cheng assert(Slot != VirtRegMap::NO_STACK_SLOT); 1007cb3c330d39442130d0587208d673ce9c33c7008fEvan Cheng vrm.assignVirt2StackSlot(NewVReg, Slot); 1008f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng } 1009f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng 1010313d4b809326f3e04814f94e5b8ae05649d8e0f6Evan Cheng // Re-matting an instruction with virtual register use. Add the 1011313d4b809326f3e04814f94e5b8ae05649d8e0f6Evan Cheng // register as an implicit use on the use MI. 1012313d4b809326f3e04814f94e5b8ae05649d8e0f6Evan Cheng if (DefIsReMat && ImpUse) 1013313d4b809326f3e04814f94e5b8ae05649d8e0f6Evan Cheng MI->addOperand(MachineOperand::CreateReg(ImpUse, false, true)); 1014313d4b809326f3e04814f94e5b8ae05649d8e0f6Evan Cheng 1015f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng // create a new register interval for this spill / remat. 1016f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng LiveInterval &nI = getOrCreateInterval(NewVReg); 101781a038218171860ee4c382849c647d3dc841fe8bEvan Cheng if (CreatedNewVReg) { 101881a038218171860ee4c382849c647d3dc841fe8bEvan Cheng NewLIs.push_back(&nI); 10191953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng MBBVRegsMap.insert(std::make_pair(MI->getParent()->getNumber(), NewVReg)); 102081a038218171860ee4c382849c647d3dc841fe8bEvan Cheng if (TrySplit) 102181a038218171860ee4c382849c647d3dc841fe8bEvan Cheng vrm.setIsSplitFromReg(NewVReg, li.reg); 102281a038218171860ee4c382849c647d3dc841fe8bEvan Cheng } 1023f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng 1024f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng if (HasUse) { 102581a038218171860ee4c382849c647d3dc841fe8bEvan Cheng if (CreatedNewVReg) { 102681a038218171860ee4c382849c647d3dc841fe8bEvan Cheng LiveRange LR(getLoadIndex(index), getUseIndex(index)+1, 102781a038218171860ee4c382849c647d3dc841fe8bEvan Cheng nI.getNextValue(~0U, 0, VNInfoAllocator)); 102881a038218171860ee4c382849c647d3dc841fe8bEvan Cheng DOUT << " +" << LR; 102981a038218171860ee4c382849c647d3dc841fe8bEvan Cheng nI.addRange(LR); 103081a038218171860ee4c382849c647d3dc841fe8bEvan Cheng } else { 103181a038218171860ee4c382849c647d3dc841fe8bEvan Cheng // Extend the split live interval to this def / use. 103281a038218171860ee4c382849c647d3dc841fe8bEvan Cheng unsigned End = getUseIndex(index)+1; 103381a038218171860ee4c382849c647d3dc841fe8bEvan Cheng LiveRange LR(nI.ranges[nI.ranges.size()-1].end, End, 103481a038218171860ee4c382849c647d3dc841fe8bEvan Cheng nI.getValNumInfo(nI.getNumValNums()-1)); 103581a038218171860ee4c382849c647d3dc841fe8bEvan Cheng DOUT << " +" << LR; 103681a038218171860ee4c382849c647d3dc841fe8bEvan Cheng nI.addRange(LR); 103781a038218171860ee4c382849c647d3dc841fe8bEvan Cheng } 1038f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng } 1039f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng if (HasDef) { 1040f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng LiveRange LR(getDefIndex(index), getStoreIndex(index), 1041f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng nI.getNextValue(~0U, 0, VNInfoAllocator)); 1042f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng DOUT << " +" << LR; 1043f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng nI.addRange(LR); 1044f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng } 104581a038218171860ee4c382849c647d3dc841fe8bEvan Cheng 1046f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng DOUT << "\t\t\t\tAdded new interval: "; 10476f0d024a534af18d9e60b3ea757376cd8a3a980eDan Gohman nI.print(DOUT, tri_); 1048f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng DOUT << '\n'; 1049f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng } 1050018f9b020bb12b731b0a7081578e5f82fb35092dEvan Cheng return CanFold; 1051f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng} 105281a038218171860ee4c382849c647d3dc841fe8bEvan Chengbool LiveIntervals::anyKillInMBBAfterIdx(const LiveInterval &li, 10530cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng const VNInfo *VNI, 10540cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng MachineBasicBlock *MBB, unsigned Idx) const { 105581a038218171860ee4c382849c647d3dc841fe8bEvan Cheng unsigned End = getMBBEndIdx(MBB); 10560cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng for (unsigned j = 0, ee = VNI->kills.size(); j != ee; ++j) { 10570cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng unsigned KillIdx = VNI->kills[j]; 10580cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng if (KillIdx > Idx && KillIdx < End) 10590cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng return true; 106081a038218171860ee4c382849c647d3dc841fe8bEvan Cheng } 106181a038218171860ee4c382849c647d3dc841fe8bEvan Cheng return false; 106281a038218171860ee4c382849c647d3dc841fe8bEvan Cheng} 106381a038218171860ee4c382849c647d3dc841fe8bEvan Cheng 10641953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Chengstatic const VNInfo *findDefinedVNInfo(const LiveInterval &li, unsigned DefIdx) { 10651953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng const VNInfo *VNI = NULL; 10661953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng for (LiveInterval::const_vni_iterator i = li.vni_begin(), 10671953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng e = li.vni_end(); i != e; ++i) 10681953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng if ((*i)->def == DefIdx) { 10691953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng VNI = *i; 10701953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng break; 10711953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng } 10721953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng return VNI; 10731953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng} 10741953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng 1075063284c001666c0a3906acbe0a26dc7cae5f081cEvan Cheng/// RewriteInfo - Keep track of machine instrs that will be rewritten 1076063284c001666c0a3906acbe0a26dc7cae5f081cEvan Cheng/// during spilling. 1077844731a7f1909f55935e3514c9e713a62d67662eDan Gohmannamespace { 1078844731a7f1909f55935e3514c9e713a62d67662eDan Gohman struct RewriteInfo { 1079844731a7f1909f55935e3514c9e713a62d67662eDan Gohman unsigned Index; 1080844731a7f1909f55935e3514c9e713a62d67662eDan Gohman MachineInstr *MI; 1081844731a7f1909f55935e3514c9e713a62d67662eDan Gohman bool HasUse; 1082844731a7f1909f55935e3514c9e713a62d67662eDan Gohman bool HasDef; 1083844731a7f1909f55935e3514c9e713a62d67662eDan Gohman RewriteInfo(unsigned i, MachineInstr *mi, bool u, bool d) 1084844731a7f1909f55935e3514c9e713a62d67662eDan Gohman : Index(i), MI(mi), HasUse(u), HasDef(d) {} 1085844731a7f1909f55935e3514c9e713a62d67662eDan Gohman }; 1086844731a7f1909f55935e3514c9e713a62d67662eDan Gohman 1087844731a7f1909f55935e3514c9e713a62d67662eDan Gohman struct RewriteInfoCompare { 1088844731a7f1909f55935e3514c9e713a62d67662eDan Gohman bool operator()(const RewriteInfo &LHS, const RewriteInfo &RHS) const { 1089844731a7f1909f55935e3514c9e713a62d67662eDan Gohman return LHS.Index < RHS.Index; 1090844731a7f1909f55935e3514c9e713a62d67662eDan Gohman } 1091844731a7f1909f55935e3514c9e713a62d67662eDan Gohman }; 1092844731a7f1909f55935e3514c9e713a62d67662eDan Gohman} 1093063284c001666c0a3906acbe0a26dc7cae5f081cEvan Cheng 1094f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Chengvoid LiveIntervals:: 109581a038218171860ee4c382849c647d3dc841fe8bEvan ChengrewriteInstructionsForSpills(const LiveInterval &li, bool TrySplit, 1096f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng LiveInterval::Ranges::const_iterator &I, 109781a038218171860ee4c382849c647d3dc841fe8bEvan Cheng MachineInstr *ReMatOrigDefMI, MachineInstr *ReMatDefMI, 1098f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng unsigned Slot, int LdSlot, 1099f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng bool isLoad, bool isLoadSS, bool DefIsReMat, bool CanDelete, 1100d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng VirtRegMap &vrm, 1101f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng const TargetRegisterClass* rc, 1102f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng SmallVector<int, 4> &ReMatIds, 110322f07ffd27d1d721634d502c37267721d2e025cfEvan Cheng const MachineLoopInfo *loopInfo, 110481a038218171860ee4c382849c647d3dc841fe8bEvan Cheng BitVector &SpillMBBs, 11051953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng std::map<unsigned, std::vector<SRInfo> > &SpillIdxes, 11060cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng BitVector &RestoreMBBs, 11071953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng std::map<unsigned, std::vector<SRInfo> > &RestoreIdxes, 11081953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng std::map<unsigned,unsigned> &MBBVRegsMap, 1109f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng std::vector<LiveInterval*> &NewLIs) { 1110018f9b020bb12b731b0a7081578e5f82fb35092dEvan Cheng bool AllCanFold = true; 111181a038218171860ee4c382849c647d3dc841fe8bEvan Cheng unsigned NewVReg = 0; 1112063284c001666c0a3906acbe0a26dc7cae5f081cEvan Cheng unsigned start = getBaseIndex(I->start); 1113f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng unsigned end = getBaseIndex(I->end-1) + InstrSlots::NUM; 1114f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng 1115063284c001666c0a3906acbe0a26dc7cae5f081cEvan Cheng // First collect all the def / use in this live range that will be rewritten. 11167e073baedb8232b9519dbe15ea141ff98ccfe6aeEvan Cheng // Make sure they are sorted according to instruction index. 1117063284c001666c0a3906acbe0a26dc7cae5f081cEvan Cheng std::vector<RewriteInfo> RewriteMIs; 1118d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng for (MachineRegisterInfo::reg_iterator ri = mri_->reg_begin(li.reg), 1119d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng re = mri_->reg_end(); ri != re; ) { 1120419852ca8a01aecde4c0e20af6b7bd6450e70f87Evan Cheng MachineInstr *MI = &*ri; 1121063284c001666c0a3906acbe0a26dc7cae5f081cEvan Cheng MachineOperand &O = ri.getOperand(); 1122063284c001666c0a3906acbe0a26dc7cae5f081cEvan Cheng ++ri; 112324d2f8a212f08bf21360122cc00acf2657af91f9Evan Cheng assert(!O.isImplicit() && "Spilling register that's used as implicit use?"); 1124063284c001666c0a3906acbe0a26dc7cae5f081cEvan Cheng unsigned index = getInstructionIndex(MI); 1125063284c001666c0a3906acbe0a26dc7cae5f081cEvan Cheng if (index < start || index >= end) 1126063284c001666c0a3906acbe0a26dc7cae5f081cEvan Cheng continue; 1127063284c001666c0a3906acbe0a26dc7cae5f081cEvan Cheng RewriteMIs.push_back(RewriteInfo(index, MI, O.isUse(), O.isDef())); 1128063284c001666c0a3906acbe0a26dc7cae5f081cEvan Cheng } 1129063284c001666c0a3906acbe0a26dc7cae5f081cEvan Cheng std::sort(RewriteMIs.begin(), RewriteMIs.end(), RewriteInfoCompare()); 1130063284c001666c0a3906acbe0a26dc7cae5f081cEvan Cheng 1131313d4b809326f3e04814f94e5b8ae05649d8e0f6Evan Cheng unsigned ImpUse = DefIsReMat ? getReMatImplicitUse(li, ReMatDefMI) : 0; 1132063284c001666c0a3906acbe0a26dc7cae5f081cEvan Cheng // Now rewrite the defs and uses. 1133063284c001666c0a3906acbe0a26dc7cae5f081cEvan Cheng for (unsigned i = 0, e = RewriteMIs.size(); i != e; ) { 1134063284c001666c0a3906acbe0a26dc7cae5f081cEvan Cheng RewriteInfo &rwi = RewriteMIs[i]; 1135063284c001666c0a3906acbe0a26dc7cae5f081cEvan Cheng ++i; 1136063284c001666c0a3906acbe0a26dc7cae5f081cEvan Cheng unsigned index = rwi.Index; 1137063284c001666c0a3906acbe0a26dc7cae5f081cEvan Cheng bool MIHasUse = rwi.HasUse; 1138063284c001666c0a3906acbe0a26dc7cae5f081cEvan Cheng bool MIHasDef = rwi.HasDef; 1139063284c001666c0a3906acbe0a26dc7cae5f081cEvan Cheng MachineInstr *MI = rwi.MI; 1140063284c001666c0a3906acbe0a26dc7cae5f081cEvan Cheng // If MI def and/or use the same register multiple times, then there 1141063284c001666c0a3906acbe0a26dc7cae5f081cEvan Cheng // are multiple entries. 1142313d4b809326f3e04814f94e5b8ae05649d8e0f6Evan Cheng unsigned NumUses = MIHasUse; 1143063284c001666c0a3906acbe0a26dc7cae5f081cEvan Cheng while (i != e && RewriteMIs[i].MI == MI) { 1144063284c001666c0a3906acbe0a26dc7cae5f081cEvan Cheng assert(RewriteMIs[i].Index == index); 1145313d4b809326f3e04814f94e5b8ae05649d8e0f6Evan Cheng bool isUse = RewriteMIs[i].HasUse; 1146313d4b809326f3e04814f94e5b8ae05649d8e0f6Evan Cheng if (isUse) ++NumUses; 1147313d4b809326f3e04814f94e5b8ae05649d8e0f6Evan Cheng MIHasUse |= isUse; 1148063284c001666c0a3906acbe0a26dc7cae5f081cEvan Cheng MIHasDef |= RewriteMIs[i].HasDef; 1149063284c001666c0a3906acbe0a26dc7cae5f081cEvan Cheng ++i; 1150063284c001666c0a3906acbe0a26dc7cae5f081cEvan Cheng } 115181a038218171860ee4c382849c647d3dc841fe8bEvan Cheng MachineBasicBlock *MBB = MI->getParent(); 1152313d4b809326f3e04814f94e5b8ae05649d8e0f6Evan Cheng 1153313d4b809326f3e04814f94e5b8ae05649d8e0f6Evan Cheng if (ImpUse && MI != ReMatDefMI) { 1154313d4b809326f3e04814f94e5b8ae05649d8e0f6Evan Cheng // Re-matting an instruction with virtual register use. Update the 115524d2f8a212f08bf21360122cc00acf2657af91f9Evan Cheng // register interval's spill weight to HUGE_VALF to prevent it from 115624d2f8a212f08bf21360122cc00acf2657af91f9Evan Cheng // being spilled. 1157313d4b809326f3e04814f94e5b8ae05649d8e0f6Evan Cheng LiveInterval &ImpLi = getInterval(ImpUse); 115824d2f8a212f08bf21360122cc00acf2657af91f9Evan Cheng ImpLi.weight = HUGE_VALF; 1159313d4b809326f3e04814f94e5b8ae05649d8e0f6Evan Cheng } 1160313d4b809326f3e04814f94e5b8ae05649d8e0f6Evan Cheng 1161063284c001666c0a3906acbe0a26dc7cae5f081cEvan Cheng unsigned MBBId = MBB->getNumber(); 1162018f9b020bb12b731b0a7081578e5f82fb35092dEvan Cheng unsigned ThisVReg = 0; 116370306f8348f27c61cfed5a60e2fceac0f29746a2Evan Cheng if (TrySplit) { 1164063284c001666c0a3906acbe0a26dc7cae5f081cEvan Cheng std::map<unsigned,unsigned>::const_iterator NVI = MBBVRegsMap.find(MBBId); 11651953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng if (NVI != MBBVRegsMap.end()) { 1166018f9b020bb12b731b0a7081578e5f82fb35092dEvan Cheng ThisVReg = NVI->second; 11671953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng // One common case: 11681953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng // x = use 11691953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng // ... 11701953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng // ... 11711953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng // def = ... 11721953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng // = use 11731953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng // It's better to start a new interval to avoid artifically 11741953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng // extend the new interval. 11751953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng if (MIHasDef && !MIHasUse) { 11761953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng MBBVRegsMap.erase(MBB->getNumber()); 1177018f9b020bb12b731b0a7081578e5f82fb35092dEvan Cheng ThisVReg = 0; 11781953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng } 11791953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng } 1180cada245d06959831b90f8c29f92e77beda4b71cbEvan Cheng } 1181018f9b020bb12b731b0a7081578e5f82fb35092dEvan Cheng 1182018f9b020bb12b731b0a7081578e5f82fb35092dEvan Cheng bool IsNew = ThisVReg == 0; 1183018f9b020bb12b731b0a7081578e5f82fb35092dEvan Cheng if (IsNew) { 1184018f9b020bb12b731b0a7081578e5f82fb35092dEvan Cheng // This ends the previous live interval. If all of its def / use 1185018f9b020bb12b731b0a7081578e5f82fb35092dEvan Cheng // can be folded, give it a low spill weight. 1186018f9b020bb12b731b0a7081578e5f82fb35092dEvan Cheng if (NewVReg && TrySplit && AllCanFold) { 1187018f9b020bb12b731b0a7081578e5f82fb35092dEvan Cheng LiveInterval &nI = getOrCreateInterval(NewVReg); 1188018f9b020bb12b731b0a7081578e5f82fb35092dEvan Cheng nI.weight /= 10.0F; 1189018f9b020bb12b731b0a7081578e5f82fb35092dEvan Cheng } 1190018f9b020bb12b731b0a7081578e5f82fb35092dEvan Cheng AllCanFold = true; 1191018f9b020bb12b731b0a7081578e5f82fb35092dEvan Cheng } 1192018f9b020bb12b731b0a7081578e5f82fb35092dEvan Cheng NewVReg = ThisVReg; 1193018f9b020bb12b731b0a7081578e5f82fb35092dEvan Cheng 119481a038218171860ee4c382849c647d3dc841fe8bEvan Cheng bool HasDef = false; 119581a038218171860ee4c382849c647d3dc841fe8bEvan Cheng bool HasUse = false; 1196d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng bool CanFold = rewriteInstructionForSpills(li, I->valno, TrySplit, 1197018f9b020bb12b731b0a7081578e5f82fb35092dEvan Cheng index, end, MI, ReMatOrigDefMI, ReMatDefMI, 1198018f9b020bb12b731b0a7081578e5f82fb35092dEvan Cheng Slot, LdSlot, isLoad, isLoadSS, DefIsReMat, 1199d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng CanDelete, vrm, rc, ReMatIds, loopInfo, NewVReg, 1200313d4b809326f3e04814f94e5b8ae05649d8e0f6Evan Cheng ImpUse, HasDef, HasUse, MBBVRegsMap, NewLIs); 120181a038218171860ee4c382849c647d3dc841fe8bEvan Cheng if (!HasDef && !HasUse) 120281a038218171860ee4c382849c647d3dc841fe8bEvan Cheng continue; 120381a038218171860ee4c382849c647d3dc841fe8bEvan Cheng 1204018f9b020bb12b731b0a7081578e5f82fb35092dEvan Cheng AllCanFold &= CanFold; 1205018f9b020bb12b731b0a7081578e5f82fb35092dEvan Cheng 120681a038218171860ee4c382849c647d3dc841fe8bEvan Cheng // Update weight of spill interval. 120781a038218171860ee4c382849c647d3dc841fe8bEvan Cheng LiveInterval &nI = getOrCreateInterval(NewVReg); 120870306f8348f27c61cfed5a60e2fceac0f29746a2Evan Cheng if (!TrySplit) { 120981a038218171860ee4c382849c647d3dc841fe8bEvan Cheng // The spill weight is now infinity as it cannot be spilled again. 121081a038218171860ee4c382849c647d3dc841fe8bEvan Cheng nI.weight = HUGE_VALF; 12110cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng continue; 12120cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng } 12130cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng 12140cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng // Keep track of the last def and first use in each MBB. 12150cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng if (HasDef) { 12160cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng if (MI != ReMatOrigDefMI || !CanDelete) { 12170cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng bool HasKill = false; 12180cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng if (!HasUse) 12190cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng HasKill = anyKillInMBBAfterIdx(li, I->valno, MBB, getDefIndex(index)); 12200cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng else { 12211953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng // If this is a two-address code, then this index starts a new VNInfo. 12221953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng const VNInfo *VNI = findDefinedVNInfo(li, getDefIndex(index)); 12230cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng if (VNI) 12240cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng HasKill = anyKillInMBBAfterIdx(li, VNI, MBB, getDefIndex(index)); 122581a038218171860ee4c382849c647d3dc841fe8bEvan Cheng } 1226e3110d0825e6316fd2dd21d6a4e593295cd413f1Evan Cheng std::map<unsigned, std::vector<SRInfo> >::iterator SII = 1227e3110d0825e6316fd2dd21d6a4e593295cd413f1Evan Cheng SpillIdxes.find(MBBId); 12280cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng if (!HasKill) { 12291953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng if (SII == SpillIdxes.end()) { 12301953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng std::vector<SRInfo> S; 12311953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng S.push_back(SRInfo(index, NewVReg, true)); 12321953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng SpillIdxes.insert(std::make_pair(MBBId, S)); 12331953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng } else if (SII->second.back().vreg != NewVReg) { 12341953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng SII->second.push_back(SRInfo(index, NewVReg, true)); 12351953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng } else if ((int)index > SII->second.back().index) { 12360cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng // If there is an earlier def and this is a two-address 12370cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng // instruction, then it's not possible to fold the store (which 12380cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng // would also fold the load). 12391953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng SRInfo &Info = SII->second.back(); 12401953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng Info.index = index; 12411953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng Info.canFold = !HasUse; 124281a038218171860ee4c382849c647d3dc841fe8bEvan Cheng } 12430cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng SpillMBBs.set(MBBId); 1244e3110d0825e6316fd2dd21d6a4e593295cd413f1Evan Cheng } else if (SII != SpillIdxes.end() && 1245e3110d0825e6316fd2dd21d6a4e593295cd413f1Evan Cheng SII->second.back().vreg == NewVReg && 1246e3110d0825e6316fd2dd21d6a4e593295cd413f1Evan Cheng (int)index > SII->second.back().index) { 1247e3110d0825e6316fd2dd21d6a4e593295cd413f1Evan Cheng // There is an earlier def that's not killed (must be two-address). 1248e3110d0825e6316fd2dd21d6a4e593295cd413f1Evan Cheng // The spill is no longer needed. 1249e3110d0825e6316fd2dd21d6a4e593295cd413f1Evan Cheng SII->second.pop_back(); 1250e3110d0825e6316fd2dd21d6a4e593295cd413f1Evan Cheng if (SII->second.empty()) { 1251e3110d0825e6316fd2dd21d6a4e593295cd413f1Evan Cheng SpillIdxes.erase(MBBId); 1252e3110d0825e6316fd2dd21d6a4e593295cd413f1Evan Cheng SpillMBBs.reset(MBBId); 1253e3110d0825e6316fd2dd21d6a4e593295cd413f1Evan Cheng } 125481a038218171860ee4c382849c647d3dc841fe8bEvan Cheng } 125581a038218171860ee4c382849c647d3dc841fe8bEvan Cheng } 12560cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng } 125781a038218171860ee4c382849c647d3dc841fe8bEvan Cheng 12580cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng if (HasUse) { 12591953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng std::map<unsigned, std::vector<SRInfo> >::iterator SII = 12600cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng SpillIdxes.find(MBBId); 12611953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng if (SII != SpillIdxes.end() && 12621953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng SII->second.back().vreg == NewVReg && 12631953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng (int)index > SII->second.back().index) 12640cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng // Use(s) following the last def, it's not safe to fold the spill. 12651953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng SII->second.back().canFold = false; 12661953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng std::map<unsigned, std::vector<SRInfo> >::iterator RII = 12670cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng RestoreIdxes.find(MBBId); 12681953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng if (RII != RestoreIdxes.end() && RII->second.back().vreg == NewVReg) 12690cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng // If we are splitting live intervals, only fold if it's the first 12700cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng // use and there isn't another use later in the MBB. 12711953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng RII->second.back().canFold = false; 12720cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng else if (IsNew) { 12730cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng // Only need a reload if there isn't an earlier def / use. 12741953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng if (RII == RestoreIdxes.end()) { 12751953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng std::vector<SRInfo> Infos; 12761953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng Infos.push_back(SRInfo(index, NewVReg, true)); 12771953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng RestoreIdxes.insert(std::make_pair(MBBId, Infos)); 12781953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng } else { 12791953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng RII->second.push_back(SRInfo(index, NewVReg, true)); 12801953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng } 12810cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng RestoreMBBs.set(MBBId); 12820cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng } 128381a038218171860ee4c382849c647d3dc841fe8bEvan Cheng } 12840cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng 12850cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng // Update spill weight. 128622f07ffd27d1d721634d502c37267721d2e025cfEvan Cheng unsigned loopDepth = loopInfo->getLoopDepth(MBB); 12870cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng nI.weight += getSpillWeight(HasDef, HasUse, loopDepth); 1288f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng } 1289018f9b020bb12b731b0a7081578e5f82fb35092dEvan Cheng 1290018f9b020bb12b731b0a7081578e5f82fb35092dEvan Cheng if (NewVReg && TrySplit && AllCanFold) { 1291018f9b020bb12b731b0a7081578e5f82fb35092dEvan Cheng // If all of its def / use can be folded, give it a low spill weight. 1292018f9b020bb12b731b0a7081578e5f82fb35092dEvan Cheng LiveInterval &nI = getOrCreateInterval(NewVReg); 1293018f9b020bb12b731b0a7081578e5f82fb35092dEvan Cheng nI.weight /= 10.0F; 1294018f9b020bb12b731b0a7081578e5f82fb35092dEvan Cheng } 1295f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng} 1296f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng 12971953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Chengbool LiveIntervals::alsoFoldARestore(int Id, int index, unsigned vr, 12981953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng BitVector &RestoreMBBs, 12991953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng std::map<unsigned,std::vector<SRInfo> > &RestoreIdxes) { 13001953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng if (!RestoreMBBs[Id]) 13011953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng return false; 13021953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng std::vector<SRInfo> &Restores = RestoreIdxes[Id]; 13031953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng for (unsigned i = 0, e = Restores.size(); i != e; ++i) 13041953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng if (Restores[i].index == index && 13051953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng Restores[i].vreg == vr && 13061953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng Restores[i].canFold) 13071953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng return true; 13081953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng return false; 13091953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng} 13101953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng 13111953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Chengvoid LiveIntervals::eraseRestoreInfo(int Id, int index, unsigned vr, 13121953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng BitVector &RestoreMBBs, 13131953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng std::map<unsigned,std::vector<SRInfo> > &RestoreIdxes) { 13141953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng if (!RestoreMBBs[Id]) 13151953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng return; 13161953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng std::vector<SRInfo> &Restores = RestoreIdxes[Id]; 13171953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng for (unsigned i = 0, e = Restores.size(); i != e; ++i) 13181953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng if (Restores[i].index == index && Restores[i].vreg) 13191953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng Restores[i].index = -1; 13201953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng} 132181a038218171860ee4c382849c647d3dc841fe8bEvan Cheng 13224cce6b4c7882ef0cc993d931b90bf33985c96110Evan Cheng/// handleSpilledImpDefs - Remove IMPLICIT_DEF instructions which are being 13234cce6b4c7882ef0cc993d931b90bf33985c96110Evan Cheng/// spilled and create empty intervals for their uses. 13244cce6b4c7882ef0cc993d931b90bf33985c96110Evan Chengvoid 13254cce6b4c7882ef0cc993d931b90bf33985c96110Evan ChengLiveIntervals::handleSpilledImpDefs(const LiveInterval &li, VirtRegMap &vrm, 13264cce6b4c7882ef0cc993d931b90bf33985c96110Evan Cheng const TargetRegisterClass* rc, 13274cce6b4c7882ef0cc993d931b90bf33985c96110Evan Cheng std::vector<LiveInterval*> &NewLIs) { 1328419852ca8a01aecde4c0e20af6b7bd6450e70f87Evan Cheng for (MachineRegisterInfo::reg_iterator ri = mri_->reg_begin(li.reg), 1329419852ca8a01aecde4c0e20af6b7bd6450e70f87Evan Cheng re = mri_->reg_end(); ri != re; ) { 13304cce6b4c7882ef0cc993d931b90bf33985c96110Evan Cheng MachineOperand &O = ri.getOperand(); 1331419852ca8a01aecde4c0e20af6b7bd6450e70f87Evan Cheng MachineInstr *MI = &*ri; 1332419852ca8a01aecde4c0e20af6b7bd6450e70f87Evan Cheng ++ri; 13334cce6b4c7882ef0cc993d931b90bf33985c96110Evan Cheng if (O.isDef()) { 13344cce6b4c7882ef0cc993d931b90bf33985c96110Evan Cheng assert(MI->getOpcode() == TargetInstrInfo::IMPLICIT_DEF && 13354cce6b4c7882ef0cc993d931b90bf33985c96110Evan Cheng "Register def was not rewritten?"); 13364cce6b4c7882ef0cc993d931b90bf33985c96110Evan Cheng RemoveMachineInstrFromMaps(MI); 13374cce6b4c7882ef0cc993d931b90bf33985c96110Evan Cheng vrm.RemoveMachineInstrFromMaps(MI); 13384cce6b4c7882ef0cc993d931b90bf33985c96110Evan Cheng MI->eraseFromParent(); 13394cce6b4c7882ef0cc993d931b90bf33985c96110Evan Cheng } else { 13404cce6b4c7882ef0cc993d931b90bf33985c96110Evan Cheng // This must be an use of an implicit_def so it's not part of the live 13414cce6b4c7882ef0cc993d931b90bf33985c96110Evan Cheng // interval. Create a new empty live interval for it. 13424cce6b4c7882ef0cc993d931b90bf33985c96110Evan Cheng // FIXME: Can we simply erase some of the instructions? e.g. Stores? 13434cce6b4c7882ef0cc993d931b90bf33985c96110Evan Cheng unsigned NewVReg = mri_->createVirtualRegister(rc); 13444cce6b4c7882ef0cc993d931b90bf33985c96110Evan Cheng vrm.grow(); 13454cce6b4c7882ef0cc993d931b90bf33985c96110Evan Cheng vrm.setIsImplicitlyDefined(NewVReg); 13464cce6b4c7882ef0cc993d931b90bf33985c96110Evan Cheng NewLIs.push_back(&getOrCreateInterval(NewVReg)); 13474cce6b4c7882ef0cc993d931b90bf33985c96110Evan Cheng for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) { 13484cce6b4c7882ef0cc993d931b90bf33985c96110Evan Cheng MachineOperand &MO = MI->getOperand(i); 13494cce6b4c7882ef0cc993d931b90bf33985c96110Evan Cheng if (MO.isReg() && MO.getReg() == li.reg) 13504cce6b4c7882ef0cc993d931b90bf33985c96110Evan Cheng MO.setReg(NewVReg); 13514cce6b4c7882ef0cc993d931b90bf33985c96110Evan Cheng } 13524cce6b4c7882ef0cc993d931b90bf33985c96110Evan Cheng } 1353419852ca8a01aecde4c0e20af6b7bd6450e70f87Evan Cheng } 1354419852ca8a01aecde4c0e20af6b7bd6450e70f87Evan Cheng} 1355419852ca8a01aecde4c0e20af6b7bd6450e70f87Evan Cheng 135681a038218171860ee4c382849c647d3dc841fe8bEvan Cheng 1357f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Chengstd::vector<LiveInterval*> LiveIntervals:: 135881a038218171860ee4c382849c647d3dc841fe8bEvan ChengaddIntervalsForSpills(const LiveInterval &li, 135922f07ffd27d1d721634d502c37267721d2e025cfEvan Cheng const MachineLoopInfo *loopInfo, VirtRegMap &vrm) { 1360f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng // Since this is called after the analysis is done we don't know if 1361f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng // LiveVariables is available 1362f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng lv_ = getAnalysisToUpdate<LiveVariables>(); 1363f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng 1364f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng assert(li.weight != HUGE_VALF && 1365f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng "attempt to spill already spilled interval!"); 1366f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng 1367f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng DOUT << "\t\t\t\tadding intervals for spills for interval: "; 13686f0d024a534af18d9e60b3ea757376cd8a3a980eDan Gohman li.print(DOUT, tri_); 1369f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng DOUT << '\n'; 1370f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng 137181a038218171860ee4c382849c647d3dc841fe8bEvan Cheng // Each bit specify whether it a spill is required in the MBB. 137281a038218171860ee4c382849c647d3dc841fe8bEvan Cheng BitVector SpillMBBs(mf_->getNumBlockIDs()); 13731953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng std::map<unsigned, std::vector<SRInfo> > SpillIdxes; 13740cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng BitVector RestoreMBBs(mf_->getNumBlockIDs()); 13751953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng std::map<unsigned, std::vector<SRInfo> > RestoreIdxes; 13761953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng std::map<unsigned,unsigned> MBBVRegsMap; 1377f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng std::vector<LiveInterval*> NewLIs; 1378d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng const TargetRegisterClass* rc = mri_->getRegClass(li.reg); 1379f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng 1380f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng unsigned NumValNums = li.getNumValNums(); 1381f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng SmallVector<MachineInstr*, 4> ReMatDefs; 1382f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng ReMatDefs.resize(NumValNums, NULL); 1383f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng SmallVector<MachineInstr*, 4> ReMatOrigDefs; 1384f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng ReMatOrigDefs.resize(NumValNums, NULL); 1385f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng SmallVector<int, 4> ReMatIds; 1386f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng ReMatIds.resize(NumValNums, VirtRegMap::MAX_STACK_SLOT); 1387f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng BitVector ReMatDelete(NumValNums); 1388f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng unsigned Slot = VirtRegMap::MAX_STACK_SLOT; 1389f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng 139081a038218171860ee4c382849c647d3dc841fe8bEvan Cheng // Spilling a split live interval. It cannot be split any further. Also, 139181a038218171860ee4c382849c647d3dc841fe8bEvan Cheng // it's also guaranteed to be a single val# / range interval. 139281a038218171860ee4c382849c647d3dc841fe8bEvan Cheng if (vrm.getPreSplitReg(li.reg)) { 139381a038218171860ee4c382849c647d3dc841fe8bEvan Cheng vrm.setIsSplitFromReg(li.reg, 0); 1394d120ffd26f2715c600b028d4eac9a3c41a9f4653Evan Cheng // Unset the split kill marker on the last use. 1395d120ffd26f2715c600b028d4eac9a3c41a9f4653Evan Cheng unsigned KillIdx = vrm.getKillPoint(li.reg); 1396d120ffd26f2715c600b028d4eac9a3c41a9f4653Evan Cheng if (KillIdx) { 1397d120ffd26f2715c600b028d4eac9a3c41a9f4653Evan Cheng MachineInstr *KillMI = getInstructionFromIndex(KillIdx); 1398d120ffd26f2715c600b028d4eac9a3c41a9f4653Evan Cheng assert(KillMI && "Last use disappeared?"); 1399d120ffd26f2715c600b028d4eac9a3c41a9f4653Evan Cheng int KillOp = KillMI->findRegisterUseOperandIdx(li.reg, true); 1400d120ffd26f2715c600b028d4eac9a3c41a9f4653Evan Cheng assert(KillOp != -1 && "Last use disappeared?"); 1401f73823000e2d5d6e1cf65bdf5a107297e18d35fbChris Lattner KillMI->getOperand(KillOp).setIsKill(false); 1402d120ffd26f2715c600b028d4eac9a3c41a9f4653Evan Cheng } 1403adf85906906ebf85c57c333e8209f37ef11a6c99Evan Cheng vrm.removeKillPoint(li.reg); 140481a038218171860ee4c382849c647d3dc841fe8bEvan Cheng bool DefIsReMat = vrm.isReMaterialized(li.reg); 140581a038218171860ee4c382849c647d3dc841fe8bEvan Cheng Slot = vrm.getStackSlot(li.reg); 140681a038218171860ee4c382849c647d3dc841fe8bEvan Cheng assert(Slot != VirtRegMap::MAX_STACK_SLOT); 140781a038218171860ee4c382849c647d3dc841fe8bEvan Cheng MachineInstr *ReMatDefMI = DefIsReMat ? 140881a038218171860ee4c382849c647d3dc841fe8bEvan Cheng vrm.getReMaterializedMI(li.reg) : NULL; 140981a038218171860ee4c382849c647d3dc841fe8bEvan Cheng int LdSlot = 0; 141081a038218171860ee4c382849c647d3dc841fe8bEvan Cheng bool isLoadSS = DefIsReMat && tii_->isLoadFromStackSlot(ReMatDefMI, LdSlot); 141181a038218171860ee4c382849c647d3dc841fe8bEvan Cheng bool isLoad = isLoadSS || 1412749c6f6b5ed301c84aac562e414486549d7b98ebChris Lattner (DefIsReMat && (ReMatDefMI->getDesc().isSimpleLoad())); 141381a038218171860ee4c382849c647d3dc841fe8bEvan Cheng bool IsFirstRange = true; 141481a038218171860ee4c382849c647d3dc841fe8bEvan Cheng for (LiveInterval::Ranges::const_iterator 141581a038218171860ee4c382849c647d3dc841fe8bEvan Cheng I = li.ranges.begin(), E = li.ranges.end(); I != E; ++I) { 141681a038218171860ee4c382849c647d3dc841fe8bEvan Cheng // If this is a split live interval with multiple ranges, it means there 141781a038218171860ee4c382849c647d3dc841fe8bEvan Cheng // are two-address instructions that re-defined the value. Only the 141881a038218171860ee4c382849c647d3dc841fe8bEvan Cheng // first def can be rematerialized! 141981a038218171860ee4c382849c647d3dc841fe8bEvan Cheng if (IsFirstRange) { 1420cb3c330d39442130d0587208d673ce9c33c7008fEvan Cheng // Note ReMatOrigDefMI has already been deleted. 142181a038218171860ee4c382849c647d3dc841fe8bEvan Cheng rewriteInstructionsForSpills(li, false, I, NULL, ReMatDefMI, 142281a038218171860ee4c382849c647d3dc841fe8bEvan Cheng Slot, LdSlot, isLoad, isLoadSS, DefIsReMat, 1423d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng false, vrm, rc, ReMatIds, loopInfo, 14240cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng SpillMBBs, SpillIdxes, RestoreMBBs, RestoreIdxes, 14251953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng MBBVRegsMap, NewLIs); 142681a038218171860ee4c382849c647d3dc841fe8bEvan Cheng } else { 142781a038218171860ee4c382849c647d3dc841fe8bEvan Cheng rewriteInstructionsForSpills(li, false, I, NULL, 0, 142881a038218171860ee4c382849c647d3dc841fe8bEvan Cheng Slot, 0, false, false, false, 1429d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng false, vrm, rc, ReMatIds, loopInfo, 14300cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng SpillMBBs, SpillIdxes, RestoreMBBs, RestoreIdxes, 14311953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng MBBVRegsMap, NewLIs); 143281a038218171860ee4c382849c647d3dc841fe8bEvan Cheng } 143381a038218171860ee4c382849c647d3dc841fe8bEvan Cheng IsFirstRange = false; 143481a038218171860ee4c382849c647d3dc841fe8bEvan Cheng } 1435419852ca8a01aecde4c0e20af6b7bd6450e70f87Evan Cheng 14364cce6b4c7882ef0cc993d931b90bf33985c96110Evan Cheng handleSpilledImpDefs(li, vrm, rc, NewLIs); 143781a038218171860ee4c382849c647d3dc841fe8bEvan Cheng return NewLIs; 143881a038218171860ee4c382849c647d3dc841fe8bEvan Cheng } 143981a038218171860ee4c382849c647d3dc841fe8bEvan Cheng 144081a038218171860ee4c382849c647d3dc841fe8bEvan Cheng bool TrySplit = SplitAtBB && !intervalIsInOneMBB(li); 14410cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng if (SplitLimit != -1 && (int)numSplits >= SplitLimit) 14420cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng TrySplit = false; 14430cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng if (TrySplit) 14440cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng ++numSplits; 1445f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng bool NeedStackSlot = false; 1446f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng for (LiveInterval::const_vni_iterator i = li.vni_begin(), e = li.vni_end(); 1447f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng i != e; ++i) { 1448f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng const VNInfo *VNI = *i; 1449f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng unsigned VN = VNI->id; 1450f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng unsigned DefIdx = VNI->def; 1451f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng if (DefIdx == ~1U) 1452f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng continue; // Dead val#. 1453f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng // Is the def for the val# rematerializable? 145481a038218171860ee4c382849c647d3dc841fe8bEvan Cheng MachineInstr *ReMatDefMI = (DefIdx == ~0u) 145581a038218171860ee4c382849c647d3dc841fe8bEvan Cheng ? 0 : getInstructionFromIndex(DefIdx); 14565ef3a04b542c4e585276768fa9ca2af698ef5c87Evan Cheng bool dummy; 14575ef3a04b542c4e585276768fa9ca2af698ef5c87Evan Cheng if (ReMatDefMI && isReMaterializable(li, VNI, ReMatDefMI, dummy)) { 1458f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng // Remember how to remat the def of this val#. 145981a038218171860ee4c382849c647d3dc841fe8bEvan Cheng ReMatOrigDefs[VN] = ReMatDefMI; 1460f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng // Original def may be modified so we have to make a copy here. vrm must 1461f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng // delete these! 146281a038218171860ee4c382849c647d3dc841fe8bEvan Cheng ReMatDefs[VN] = ReMatDefMI = ReMatDefMI->clone(); 1463f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng 1464f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng bool CanDelete = true; 1465c3fc7d9ec9b495c8a88cd854247105c296d3aabdEvan Cheng if (VNI->hasPHIKill) { 1466c3fc7d9ec9b495c8a88cd854247105c296d3aabdEvan Cheng // A kill is a phi node, not all of its uses can be rematerialized. 1467f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng // It must not be deleted. 1468c3fc7d9ec9b495c8a88cd854247105c296d3aabdEvan Cheng CanDelete = false; 1469c3fc7d9ec9b495c8a88cd854247105c296d3aabdEvan Cheng // Need a stack slot if there is any live range where uses cannot be 1470c3fc7d9ec9b495c8a88cd854247105c296d3aabdEvan Cheng // rematerialized. 1471c3fc7d9ec9b495c8a88cd854247105c296d3aabdEvan Cheng NeedStackSlot = true; 1472f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng } 1473f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng if (CanDelete) 1474f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng ReMatDelete.set(VN); 1475f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng } else { 1476f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng // Need a stack slot if there is any live range where uses cannot be 1477f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng // rematerialized. 1478f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng NeedStackSlot = true; 1479f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng } 1480f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng } 1481f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng 1482f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng // One stack slot per live interval. 148381a038218171860ee4c382849c647d3dc841fe8bEvan Cheng if (NeedStackSlot && vrm.getPreSplitReg(li.reg) == 0) 1484f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng Slot = vrm.assignVirt2StackSlot(li.reg); 1485f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng 1486f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng // Create new intervals and rewrite defs and uses. 1487f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng for (LiveInterval::Ranges::const_iterator 1488f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng I = li.ranges.begin(), E = li.ranges.end(); I != E; ++I) { 148981a038218171860ee4c382849c647d3dc841fe8bEvan Cheng MachineInstr *ReMatDefMI = ReMatDefs[I->valno->id]; 149081a038218171860ee4c382849c647d3dc841fe8bEvan Cheng MachineInstr *ReMatOrigDefMI = ReMatOrigDefs[I->valno->id]; 149181a038218171860ee4c382849c647d3dc841fe8bEvan Cheng bool DefIsReMat = ReMatDefMI != NULL; 1492f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng bool CanDelete = ReMatDelete[I->valno->id]; 1493f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng int LdSlot = 0; 149481a038218171860ee4c382849c647d3dc841fe8bEvan Cheng bool isLoadSS = DefIsReMat && tii_->isLoadFromStackSlot(ReMatDefMI, LdSlot); 1495f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng bool isLoad = isLoadSS || 1496749c6f6b5ed301c84aac562e414486549d7b98ebChris Lattner (DefIsReMat && ReMatDefMI->getDesc().isSimpleLoad()); 149781a038218171860ee4c382849c647d3dc841fe8bEvan Cheng rewriteInstructionsForSpills(li, TrySplit, I, ReMatOrigDefMI, ReMatDefMI, 14980cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng Slot, LdSlot, isLoad, isLoadSS, DefIsReMat, 1499d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng CanDelete, vrm, rc, ReMatIds, loopInfo, 15000cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng SpillMBBs, SpillIdxes, RestoreMBBs, RestoreIdxes, 15011953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng MBBVRegsMap, NewLIs); 1502f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng } 1503f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng 15040cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng // Insert spills / restores if we are splitting. 1505419852ca8a01aecde4c0e20af6b7bd6450e70f87Evan Cheng if (!TrySplit) { 15064cce6b4c7882ef0cc993d931b90bf33985c96110Evan Cheng handleSpilledImpDefs(li, vrm, rc, NewLIs); 15071953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng return NewLIs; 1508419852ca8a01aecde4c0e20af6b7bd6450e70f87Evan Cheng } 15091953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng 1510b50bb8cf197709b3f49044740044c06d8f314564Evan Cheng SmallPtrSet<LiveInterval*, 4> AddedKill; 1511aee4af68ae2016afc5b4ec0c430e539c5810a766Evan Cheng SmallVector<unsigned, 2> Ops; 15121953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng if (NeedStackSlot) { 15131953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng int Id = SpillMBBs.find_first(); 15141953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng while (Id != -1) { 15151953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng std::vector<SRInfo> &spills = SpillIdxes[Id]; 15161953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng for (unsigned i = 0, e = spills.size(); i != e; ++i) { 15171953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng int index = spills[i].index; 15181953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng unsigned VReg = spills[i].vreg; 1519597d10d84fb6b34f7776121404d5ed802b21b2b6Evan Cheng LiveInterval &nI = getOrCreateInterval(VReg); 15200cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng bool isReMat = vrm.isReMaterialized(VReg); 15210cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng MachineInstr *MI = getInstructionFromIndex(index); 1522aee4af68ae2016afc5b4ec0c430e539c5810a766Evan Cheng bool CanFold = false; 1523aee4af68ae2016afc5b4ec0c430e539c5810a766Evan Cheng bool FoundUse = false; 1524aee4af68ae2016afc5b4ec0c430e539c5810a766Evan Cheng Ops.clear(); 1525cddbb83ea82e98658d9f530c50a7b9d23249afc2Evan Cheng if (spills[i].canFold) { 1526aee4af68ae2016afc5b4ec0c430e539c5810a766Evan Cheng CanFold = true; 15270cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng for (unsigned j = 0, ee = MI->getNumOperands(); j != ee; ++j) { 15280cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng MachineOperand &MO = MI->getOperand(j); 15290cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng if (!MO.isRegister() || MO.getReg() != VReg) 15300cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng continue; 1531aee4af68ae2016afc5b4ec0c430e539c5810a766Evan Cheng 1532aee4af68ae2016afc5b4ec0c430e539c5810a766Evan Cheng Ops.push_back(j); 1533aee4af68ae2016afc5b4ec0c430e539c5810a766Evan Cheng if (MO.isDef()) 1534cddbb83ea82e98658d9f530c50a7b9d23249afc2Evan Cheng continue; 1535aee4af68ae2016afc5b4ec0c430e539c5810a766Evan Cheng if (isReMat || 1536aee4af68ae2016afc5b4ec0c430e539c5810a766Evan Cheng (!FoundUse && !alsoFoldARestore(Id, index, VReg, 1537aee4af68ae2016afc5b4ec0c430e539c5810a766Evan Cheng RestoreMBBs, RestoreIdxes))) { 1538aee4af68ae2016afc5b4ec0c430e539c5810a766Evan Cheng // MI has two-address uses of the same register. If the use 1539aee4af68ae2016afc5b4ec0c430e539c5810a766Evan Cheng // isn't the first and only use in the BB, then we can't fold 1540aee4af68ae2016afc5b4ec0c430e539c5810a766Evan Cheng // it. FIXME: Move this to rewriteInstructionsForSpills. 1541aee4af68ae2016afc5b4ec0c430e539c5810a766Evan Cheng CanFold = false; 1542cddbb83ea82e98658d9f530c50a7b9d23249afc2Evan Cheng break; 1543cddbb83ea82e98658d9f530c50a7b9d23249afc2Evan Cheng } 1544aee4af68ae2016afc5b4ec0c430e539c5810a766Evan Cheng FoundUse = true; 15450cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng } 15460cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng } 15470cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng // Fold the store into the def if possible. 1548cddbb83ea82e98658d9f530c50a7b9d23249afc2Evan Cheng bool Folded = false; 1549aee4af68ae2016afc5b4ec0c430e539c5810a766Evan Cheng if (CanFold && !Ops.empty()) { 1550aee4af68ae2016afc5b4ec0c430e539c5810a766Evan Cheng if (tryFoldMemoryOperand(MI, vrm, NULL, index, Ops, true, Slot,VReg)){ 1551cddbb83ea82e98658d9f530c50a7b9d23249afc2Evan Cheng Folded = true; 1552f38d14f03e495ea98ae16bda6febbde276513294Evan Cheng if (FoundUse > 0) { 1553aee4af68ae2016afc5b4ec0c430e539c5810a766Evan Cheng // Also folded uses, do not issue a load. 1554aee4af68ae2016afc5b4ec0c430e539c5810a766Evan Cheng eraseRestoreInfo(Id, index, VReg, RestoreMBBs, RestoreIdxes); 1555f38d14f03e495ea98ae16bda6febbde276513294Evan Cheng nI.removeRange(getLoadIndex(index), getUseIndex(index)+1); 1556f38d14f03e495ea98ae16bda6febbde276513294Evan Cheng } 1557597d10d84fb6b34f7776121404d5ed802b21b2b6Evan Cheng nI.removeRange(getDefIndex(index), getStoreIndex(index)); 1558cddbb83ea82e98658d9f530c50a7b9d23249afc2Evan Cheng } 15590cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng } 15600cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng 15617e073baedb8232b9519dbe15ea141ff98ccfe6aeEvan Cheng // Otherwise tell the spiller to issue a spill. 1562b50bb8cf197709b3f49044740044c06d8f314564Evan Cheng if (!Folded) { 1563b50bb8cf197709b3f49044740044c06d8f314564Evan Cheng LiveRange *LR = &nI.ranges[nI.ranges.size()-1]; 1564b50bb8cf197709b3f49044740044c06d8f314564Evan Cheng bool isKill = LR->end == getStoreIndex(index); 1565b0a6f62c9b2e75fc509d84310a9795ffacbc6796Evan Cheng if (!MI->registerDefIsDead(nI.reg)) 1566b0a6f62c9b2e75fc509d84310a9795ffacbc6796Evan Cheng // No need to spill a dead def. 1567b0a6f62c9b2e75fc509d84310a9795ffacbc6796Evan Cheng vrm.addSpillPoint(VReg, isKill, MI); 1568b50bb8cf197709b3f49044740044c06d8f314564Evan Cheng if (isKill) 1569b50bb8cf197709b3f49044740044c06d8f314564Evan Cheng AddedKill.insert(&nI); 1570b50bb8cf197709b3f49044740044c06d8f314564Evan Cheng } 15710cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng } 15721953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng Id = SpillMBBs.find_next(Id); 15730cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng } 15741953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng } 15750cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng 15761953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng int Id = RestoreMBBs.find_first(); 15771953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng while (Id != -1) { 15781953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng std::vector<SRInfo> &restores = RestoreIdxes[Id]; 15791953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng for (unsigned i = 0, e = restores.size(); i != e; ++i) { 15801953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng int index = restores[i].index; 15811953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng if (index == -1) 15821953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng continue; 15831953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng unsigned VReg = restores[i].vreg; 1584597d10d84fb6b34f7776121404d5ed802b21b2b6Evan Cheng LiveInterval &nI = getOrCreateInterval(VReg); 158581a038218171860ee4c382849c647d3dc841fe8bEvan Cheng MachineInstr *MI = getInstructionFromIndex(index); 1586aee4af68ae2016afc5b4ec0c430e539c5810a766Evan Cheng bool CanFold = false; 1587aee4af68ae2016afc5b4ec0c430e539c5810a766Evan Cheng Ops.clear(); 1588cddbb83ea82e98658d9f530c50a7b9d23249afc2Evan Cheng if (restores[i].canFold) { 1589aee4af68ae2016afc5b4ec0c430e539c5810a766Evan Cheng CanFold = true; 159081a038218171860ee4c382849c647d3dc841fe8bEvan Cheng for (unsigned j = 0, ee = MI->getNumOperands(); j != ee; ++j) { 159181a038218171860ee4c382849c647d3dc841fe8bEvan Cheng MachineOperand &MO = MI->getOperand(j); 159281a038218171860ee4c382849c647d3dc841fe8bEvan Cheng if (!MO.isRegister() || MO.getReg() != VReg) 159381a038218171860ee4c382849c647d3dc841fe8bEvan Cheng continue; 1594aee4af68ae2016afc5b4ec0c430e539c5810a766Evan Cheng 15950cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng if (MO.isDef()) { 1596aee4af68ae2016afc5b4ec0c430e539c5810a766Evan Cheng // If this restore were to be folded, it would have been folded 1597aee4af68ae2016afc5b4ec0c430e539c5810a766Evan Cheng // already. 1598aee4af68ae2016afc5b4ec0c430e539c5810a766Evan Cheng CanFold = false; 159981a038218171860ee4c382849c647d3dc841fe8bEvan Cheng break; 160081a038218171860ee4c382849c647d3dc841fe8bEvan Cheng } 1601aee4af68ae2016afc5b4ec0c430e539c5810a766Evan Cheng Ops.push_back(j); 160281a038218171860ee4c382849c647d3dc841fe8bEvan Cheng } 160381a038218171860ee4c382849c647d3dc841fe8bEvan Cheng } 16040cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng 16050cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng // Fold the load into the use if possible. 1606cddbb83ea82e98658d9f530c50a7b9d23249afc2Evan Cheng bool Folded = false; 1607aee4af68ae2016afc5b4ec0c430e539c5810a766Evan Cheng if (CanFold && !Ops.empty()) { 1608aee4af68ae2016afc5b4ec0c430e539c5810a766Evan Cheng if (!vrm.isReMaterialized(VReg)) 1609aee4af68ae2016afc5b4ec0c430e539c5810a766Evan Cheng Folded = tryFoldMemoryOperand(MI, vrm, NULL,index,Ops,true,Slot,VReg); 1610aee4af68ae2016afc5b4ec0c430e539c5810a766Evan Cheng else { 16110cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng MachineInstr *ReMatDefMI = vrm.getReMaterializedMI(VReg); 16120cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng int LdSlot = 0; 16130cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng bool isLoadSS = tii_->isLoadFromStackSlot(ReMatDefMI, LdSlot); 16140cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng // If the rematerializable def is a load, also try to fold it. 1615749c6f6b5ed301c84aac562e414486549d7b98ebChris Lattner if (isLoadSS || ReMatDefMI->getDesc().isSimpleLoad()) 1616aee4af68ae2016afc5b4ec0c430e539c5810a766Evan Cheng Folded = tryFoldMemoryOperand(MI, vrm, ReMatDefMI, index, 1617aee4af68ae2016afc5b4ec0c430e539c5810a766Evan Cheng Ops, isLoadSS, LdSlot, VReg); 1618d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng unsigned ImpUse = getReMatImplicitUse(li, ReMatDefMI); 1619d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng if (ImpUse) { 1620d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng // Re-matting an instruction with virtual register use. Add the 1621d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng // register as an implicit use on the use MI and update the register 162224d2f8a212f08bf21360122cc00acf2657af91f9Evan Cheng // interval's spill weight to HUGE_VALF to prevent it from being 162324d2f8a212f08bf21360122cc00acf2657af91f9Evan Cheng // spilled. 1624d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng LiveInterval &ImpLi = getInterval(ImpUse); 162524d2f8a212f08bf21360122cc00acf2657af91f9Evan Cheng ImpLi.weight = HUGE_VALF; 1626d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng MI->addOperand(MachineOperand::CreateReg(ImpUse, false, true)); 1627d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng } 1628aee4af68ae2016afc5b4ec0c430e539c5810a766Evan Cheng } 16290cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng } 16300cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng // If folding is not possible / failed, then tell the spiller to issue a 16310cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng // load / rematerialization for us. 1632597d10d84fb6b34f7776121404d5ed802b21b2b6Evan Cheng if (Folded) 1633597d10d84fb6b34f7776121404d5ed802b21b2b6Evan Cheng nI.removeRange(getLoadIndex(index), getUseIndex(index)+1); 1634b50bb8cf197709b3f49044740044c06d8f314564Evan Cheng else 16350cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng vrm.addRestorePoint(VReg, MI); 163681a038218171860ee4c382849c647d3dc841fe8bEvan Cheng } 16371953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng Id = RestoreMBBs.find_next(Id); 163881a038218171860ee4c382849c647d3dc841fe8bEvan Cheng } 163981a038218171860ee4c382849c647d3dc841fe8bEvan Cheng 1640b50bb8cf197709b3f49044740044c06d8f314564Evan Cheng // Finalize intervals: add kills, finalize spill weights, and filter out 1641b50bb8cf197709b3f49044740044c06d8f314564Evan Cheng // dead intervals. 1642597d10d84fb6b34f7776121404d5ed802b21b2b6Evan Cheng std::vector<LiveInterval*> RetNewLIs; 1643597d10d84fb6b34f7776121404d5ed802b21b2b6Evan Cheng for (unsigned i = 0, e = NewLIs.size(); i != e; ++i) { 1644597d10d84fb6b34f7776121404d5ed802b21b2b6Evan Cheng LiveInterval *LI = NewLIs[i]; 1645597d10d84fb6b34f7776121404d5ed802b21b2b6Evan Cheng if (!LI->empty()) { 1646597d10d84fb6b34f7776121404d5ed802b21b2b6Evan Cheng LI->weight /= LI->getSize(); 1647b50bb8cf197709b3f49044740044c06d8f314564Evan Cheng if (!AddedKill.count(LI)) { 1648b50bb8cf197709b3f49044740044c06d8f314564Evan Cheng LiveRange *LR = &LI->ranges[LI->ranges.size()-1]; 1649d120ffd26f2715c600b028d4eac9a3c41a9f4653Evan Cheng unsigned LastUseIdx = getBaseIndex(LR->end); 1650d120ffd26f2715c600b028d4eac9a3c41a9f4653Evan Cheng MachineInstr *LastUse = getInstructionFromIndex(LastUseIdx); 16516130f66eaae89f8878590796977678afa8448926Evan Cheng int UseIdx = LastUse->findRegisterUseOperandIdx(LI->reg, false); 1652b50bb8cf197709b3f49044740044c06d8f314564Evan Cheng assert(UseIdx != -1); 1653d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng if (LastUse->getOperand(UseIdx).isImplicit() || 1654d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng LastUse->getDesc().getOperandConstraint(UseIdx,TOI::TIED_TO) == -1){ 1655b50bb8cf197709b3f49044740044c06d8f314564Evan Cheng LastUse->getOperand(UseIdx).setIsKill(); 1656d120ffd26f2715c600b028d4eac9a3c41a9f4653Evan Cheng vrm.addKillPoint(LI->reg, LastUseIdx); 1657adf85906906ebf85c57c333e8209f37ef11a6c99Evan Cheng } 1658b50bb8cf197709b3f49044740044c06d8f314564Evan Cheng } 1659597d10d84fb6b34f7776121404d5ed802b21b2b6Evan Cheng RetNewLIs.push_back(LI); 1660597d10d84fb6b34f7776121404d5ed802b21b2b6Evan Cheng } 1661597d10d84fb6b34f7776121404d5ed802b21b2b6Evan Cheng } 166281a038218171860ee4c382849c647d3dc841fe8bEvan Cheng 16634cce6b4c7882ef0cc993d931b90bf33985c96110Evan Cheng handleSpilledImpDefs(li, vrm, rc, RetNewLIs); 1664597d10d84fb6b34f7776121404d5ed802b21b2b6Evan Cheng return RetNewLIs; 1665f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng} 1666676dd7c80b6f91178452535ac45ca58feb23cc42Evan Cheng 1667676dd7c80b6f91178452535ac45ca58feb23cc42Evan Cheng/// hasAllocatableSuperReg - Return true if the specified physical register has 1668676dd7c80b6f91178452535ac45ca58feb23cc42Evan Cheng/// any super register that's allocatable. 1669676dd7c80b6f91178452535ac45ca58feb23cc42Evan Chengbool LiveIntervals::hasAllocatableSuperReg(unsigned Reg) const { 1670676dd7c80b6f91178452535ac45ca58feb23cc42Evan Cheng for (const unsigned* AS = tri_->getSuperRegisters(Reg); *AS; ++AS) 1671676dd7c80b6f91178452535ac45ca58feb23cc42Evan Cheng if (allocatableRegs_[*AS] && hasInterval(*AS)) 1672676dd7c80b6f91178452535ac45ca58feb23cc42Evan Cheng return true; 1673676dd7c80b6f91178452535ac45ca58feb23cc42Evan Cheng return false; 1674676dd7c80b6f91178452535ac45ca58feb23cc42Evan Cheng} 1675676dd7c80b6f91178452535ac45ca58feb23cc42Evan Cheng 1676676dd7c80b6f91178452535ac45ca58feb23cc42Evan Cheng/// getRepresentativeReg - Find the largest super register of the specified 1677676dd7c80b6f91178452535ac45ca58feb23cc42Evan Cheng/// physical register. 1678676dd7c80b6f91178452535ac45ca58feb23cc42Evan Chengunsigned LiveIntervals::getRepresentativeReg(unsigned Reg) const { 1679676dd7c80b6f91178452535ac45ca58feb23cc42Evan Cheng // Find the largest super-register that is allocatable. 1680676dd7c80b6f91178452535ac45ca58feb23cc42Evan Cheng unsigned BestReg = Reg; 1681676dd7c80b6f91178452535ac45ca58feb23cc42Evan Cheng for (const unsigned* AS = tri_->getSuperRegisters(Reg); *AS; ++AS) { 1682676dd7c80b6f91178452535ac45ca58feb23cc42Evan Cheng unsigned SuperReg = *AS; 1683676dd7c80b6f91178452535ac45ca58feb23cc42Evan Cheng if (!hasAllocatableSuperReg(SuperReg) && hasInterval(SuperReg)) { 1684676dd7c80b6f91178452535ac45ca58feb23cc42Evan Cheng BestReg = SuperReg; 1685676dd7c80b6f91178452535ac45ca58feb23cc42Evan Cheng break; 1686676dd7c80b6f91178452535ac45ca58feb23cc42Evan Cheng } 1687676dd7c80b6f91178452535ac45ca58feb23cc42Evan Cheng } 1688676dd7c80b6f91178452535ac45ca58feb23cc42Evan Cheng return BestReg; 1689676dd7c80b6f91178452535ac45ca58feb23cc42Evan Cheng} 1690676dd7c80b6f91178452535ac45ca58feb23cc42Evan Cheng 1691676dd7c80b6f91178452535ac45ca58feb23cc42Evan Cheng/// getNumConflictsWithPhysReg - Return the number of uses and defs of the 1692676dd7c80b6f91178452535ac45ca58feb23cc42Evan Cheng/// specified interval that conflicts with the specified physical register. 1693676dd7c80b6f91178452535ac45ca58feb23cc42Evan Chengunsigned LiveIntervals::getNumConflictsWithPhysReg(const LiveInterval &li, 1694676dd7c80b6f91178452535ac45ca58feb23cc42Evan Cheng unsigned PhysReg) const { 1695676dd7c80b6f91178452535ac45ca58feb23cc42Evan Cheng unsigned NumConflicts = 0; 1696676dd7c80b6f91178452535ac45ca58feb23cc42Evan Cheng const LiveInterval &pli = getInterval(getRepresentativeReg(PhysReg)); 1697676dd7c80b6f91178452535ac45ca58feb23cc42Evan Cheng for (MachineRegisterInfo::reg_iterator I = mri_->reg_begin(li.reg), 1698676dd7c80b6f91178452535ac45ca58feb23cc42Evan Cheng E = mri_->reg_end(); I != E; ++I) { 1699676dd7c80b6f91178452535ac45ca58feb23cc42Evan Cheng MachineOperand &O = I.getOperand(); 1700676dd7c80b6f91178452535ac45ca58feb23cc42Evan Cheng MachineInstr *MI = O.getParent(); 1701676dd7c80b6f91178452535ac45ca58feb23cc42Evan Cheng unsigned Index = getInstructionIndex(MI); 1702676dd7c80b6f91178452535ac45ca58feb23cc42Evan Cheng if (pli.liveAt(Index)) 1703676dd7c80b6f91178452535ac45ca58feb23cc42Evan Cheng ++NumConflicts; 1704676dd7c80b6f91178452535ac45ca58feb23cc42Evan Cheng } 1705676dd7c80b6f91178452535ac45ca58feb23cc42Evan Cheng return NumConflicts; 1706676dd7c80b6f91178452535ac45ca58feb23cc42Evan Cheng} 1707676dd7c80b6f91178452535ac45ca58feb23cc42Evan Cheng 1708676dd7c80b6f91178452535ac45ca58feb23cc42Evan Cheng/// spillPhysRegAroundRegDefsUses - Spill the specified physical register 1709676dd7c80b6f91178452535ac45ca58feb23cc42Evan Cheng/// around all defs and uses of the specified interval. 1710676dd7c80b6f91178452535ac45ca58feb23cc42Evan Chengvoid LiveIntervals::spillPhysRegAroundRegDefsUses(const LiveInterval &li, 1711676dd7c80b6f91178452535ac45ca58feb23cc42Evan Cheng unsigned PhysReg, VirtRegMap &vrm) { 1712676dd7c80b6f91178452535ac45ca58feb23cc42Evan Cheng unsigned SpillReg = getRepresentativeReg(PhysReg); 1713676dd7c80b6f91178452535ac45ca58feb23cc42Evan Cheng 1714676dd7c80b6f91178452535ac45ca58feb23cc42Evan Cheng for (const unsigned *AS = tri_->getAliasSet(PhysReg); *AS; ++AS) 1715676dd7c80b6f91178452535ac45ca58feb23cc42Evan Cheng // If there are registers which alias PhysReg, but which are not a 1716676dd7c80b6f91178452535ac45ca58feb23cc42Evan Cheng // sub-register of the chosen representative super register. Assert 1717676dd7c80b6f91178452535ac45ca58feb23cc42Evan Cheng // since we can't handle it yet. 1718676dd7c80b6f91178452535ac45ca58feb23cc42Evan Cheng assert(*AS == SpillReg || !allocatableRegs_[*AS] || 1719676dd7c80b6f91178452535ac45ca58feb23cc42Evan Cheng tri_->isSuperRegister(*AS, SpillReg)); 1720676dd7c80b6f91178452535ac45ca58feb23cc42Evan Cheng 1721676dd7c80b6f91178452535ac45ca58feb23cc42Evan Cheng LiveInterval &pli = getInterval(SpillReg); 1722676dd7c80b6f91178452535ac45ca58feb23cc42Evan Cheng SmallPtrSet<MachineInstr*, 8> SeenMIs; 1723676dd7c80b6f91178452535ac45ca58feb23cc42Evan Cheng for (MachineRegisterInfo::reg_iterator I = mri_->reg_begin(li.reg), 1724676dd7c80b6f91178452535ac45ca58feb23cc42Evan Cheng E = mri_->reg_end(); I != E; ++I) { 1725676dd7c80b6f91178452535ac45ca58feb23cc42Evan Cheng MachineOperand &O = I.getOperand(); 1726676dd7c80b6f91178452535ac45ca58feb23cc42Evan Cheng MachineInstr *MI = O.getParent(); 1727676dd7c80b6f91178452535ac45ca58feb23cc42Evan Cheng if (SeenMIs.count(MI)) 1728676dd7c80b6f91178452535ac45ca58feb23cc42Evan Cheng continue; 1729676dd7c80b6f91178452535ac45ca58feb23cc42Evan Cheng SeenMIs.insert(MI); 1730676dd7c80b6f91178452535ac45ca58feb23cc42Evan Cheng unsigned Index = getInstructionIndex(MI); 1731676dd7c80b6f91178452535ac45ca58feb23cc42Evan Cheng if (pli.liveAt(Index)) { 1732676dd7c80b6f91178452535ac45ca58feb23cc42Evan Cheng vrm.addEmergencySpill(SpillReg, MI); 1733676dd7c80b6f91178452535ac45ca58feb23cc42Evan Cheng pli.removeRange(getLoadIndex(Index), getStoreIndex(Index)+1); 1734676dd7c80b6f91178452535ac45ca58feb23cc42Evan Cheng for (const unsigned* AS = tri_->getSubRegisters(SpillReg); *AS; ++AS) { 1735676dd7c80b6f91178452535ac45ca58feb23cc42Evan Cheng if (!hasInterval(*AS)) 1736676dd7c80b6f91178452535ac45ca58feb23cc42Evan Cheng continue; 1737676dd7c80b6f91178452535ac45ca58feb23cc42Evan Cheng LiveInterval &spli = getInterval(*AS); 1738676dd7c80b6f91178452535ac45ca58feb23cc42Evan Cheng if (spli.liveAt(Index)) 1739676dd7c80b6f91178452535ac45ca58feb23cc42Evan Cheng spli.removeRange(getLoadIndex(Index), getStoreIndex(Index)+1); 1740676dd7c80b6f91178452535ac45ca58feb23cc42Evan Cheng } 1741676dd7c80b6f91178452535ac45ca58feb23cc42Evan Cheng } 1742676dd7c80b6f91178452535ac45ca58feb23cc42Evan Cheng } 1743676dd7c80b6f91178452535ac45ca58feb23cc42Evan Cheng} 1744