LiveIntervalAnalysis.cpp revision d70dbb5d627a0408eccf88033143efa62ee0e6c0
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 39bc165e436beb02443abea9736c1b77e2dd7828b6Evan Chengnamespace { 40bc165e436beb02443abea9736c1b77e2dd7828b6Evan Cheng // Hidden options for help debugging. 41bc165e436beb02443abea9736c1b77e2dd7828b6Evan Cheng cl::opt<bool> DisableReMat("disable-rematerialization", 42bc165e436beb02443abea9736c1b77e2dd7828b6Evan Cheng cl::init(false), cl::Hidden); 4381a038218171860ee4c382849c647d3dc841fe8bEvan Cheng 4481a038218171860ee4c382849c647d3dc841fe8bEvan Cheng cl::opt<bool> SplitAtBB("split-intervals-at-bb", 4533faddc35d5da8451f03edf27f90b901ba529c58Evan Cheng cl::init(true), cl::Hidden); 460cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng cl::opt<int> SplitLimit("split-limit", 470cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng cl::init(-1), cl::Hidden); 48bc165e436beb02443abea9736c1b77e2dd7828b6Evan Cheng} 49bc165e436beb02443abea9736c1b77e2dd7828b6Evan Cheng 50cd3245ac45c595da96bb768a55cddc356dff55feChris LattnerSTATISTIC(numIntervals, "Number of original intervals"); 51cd3245ac45c595da96bb768a55cddc356dff55feChris LattnerSTATISTIC(numIntervalsAfter, "Number of intervals after coalescing"); 520cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan ChengSTATISTIC(numFolds , "Number of loads/stores folded into instructions"); 530cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan ChengSTATISTIC(numSplits , "Number of intervals split"); 54cd3245ac45c595da96bb768a55cddc356dff55feChris Lattner 551997473cf72957d0e70322e2fe6fe2ab141c58a6Devang Patelchar LiveIntervals::ID = 0; 56ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenosnamespace { 575d8925c7c506a54ebdfb0bc93437ec9f602eaaa0Chris Lattner RegisterPass<LiveIntervals> X("liveintervals", "Live Interval Analysis"); 58d74ea2bbd8bb630331f35ead42d385249bd42af8Chris Lattner} 59ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos 60f7da2c7b0c6293c268881628fc351bed7763f1f4Chris Lattnervoid LiveIntervals::getAnalysisUsage(AnalysisUsage &AU) const { 612513330de8f8020d15d5bc96640a0957b7c733b9David Greene AU.addPreserved<LiveVariables>(); 621a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos AU.addRequired<LiveVariables>(); 6367d65bb69d5cad957cbb6d672dc0b4a19c211a42Bill Wendling AU.addPreservedID(MachineLoopInfoID); 6467d65bb69d5cad957cbb6d672dc0b4a19c211a42Bill Wendling AU.addPreservedID(MachineDominatorsID); 651a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos AU.addPreservedID(PHIEliminationID); 661a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos AU.addRequiredID(PHIEliminationID); 671a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos AU.addRequiredID(TwoAddressInstructionPassID); 681a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos MachineFunctionPass::getAnalysisUsage(AU); 69ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos} 70ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos 71f7da2c7b0c6293c268881628fc351bed7763f1f4Chris Lattnervoid LiveIntervals::releaseMemory() { 724ca980e7f9ce7b78955307c2d07001a24d3b6befEvan Cheng Idx2MBBMap.clear(); 731a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos mi2iMap_.clear(); 741a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos i2miMap_.clear(); 751a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos r2iMap_.clear(); 76dd199d29b781bc713462f1255b63d3f153bfd9e9Evan Cheng // Release VNInfo memroy regions after all VNInfo objects are dtor'd. 77dd199d29b781bc713462f1255b63d3f153bfd9e9Evan Cheng VNInfoAllocator.Reset(); 78549f27d3070195d6647b796841a5291b4549e8e0Evan Cheng for (unsigned i = 0, e = ClonedMIs.size(); i != e; ++i) 79549f27d3070195d6647b796841a5291b4549e8e0Evan Cheng delete ClonedMIs[i]; 80993141402f57b4d4cbb7f8a3113f19c61688f9b7Evan Cheng} 81993141402f57b4d4cbb7f8a3113f19c61688f9b7Evan Cheng 82ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos/// runOnMachineFunction - Register allocate the whole function 83ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos/// 84ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenosbool LiveIntervals::runOnMachineFunction(MachineFunction &fn) { 851a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos mf_ = &fn; 86d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng mri_ = &mf_->getRegInfo(); 871a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos tm_ = &fn.getTarget(); 886f0d024a534af18d9e60b3ea757376cd8a3a980eDan Gohman tri_ = tm_->getRegisterInfo(); 89f768bba43f5c036039851d2fcca8212edca18467Chris Lattner tii_ = tm_->getInstrInfo(); 901a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos lv_ = &getAnalysis<LiveVariables>(); 916f0d024a534af18d9e60b3ea757376cd8a3a980eDan Gohman allocatableRegs_ = tri_->getAllocatableSet(fn); 921a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos 93428b92eb83b457b71d29d1d4b7900d36a0ce9a53Chris Lattner // Number MachineInstrs and MachineBasicBlocks. 94428b92eb83b457b71d29d1d4b7900d36a0ce9a53Chris Lattner // Initialize MBB indexes to a sentinal. 95549f27d3070195d6647b796841a5291b4549e8e0Evan Cheng MBB2IdxMap.resize(mf_->getNumBlockIDs(), std::make_pair(~0U,~0U)); 96428b92eb83b457b71d29d1d4b7900d36a0ce9a53Chris Lattner 97428b92eb83b457b71d29d1d4b7900d36a0ce9a53Chris Lattner unsigned MIIndex = 0; 98428b92eb83b457b71d29d1d4b7900d36a0ce9a53Chris Lattner for (MachineFunction::iterator MBB = mf_->begin(), E = mf_->end(); 99428b92eb83b457b71d29d1d4b7900d36a0ce9a53Chris Lattner MBB != E; ++MBB) { 100549f27d3070195d6647b796841a5291b4549e8e0Evan Cheng unsigned StartIdx = MIIndex; 1010c9f92e1ff64ee56724eae444a0442b02f83d0a8Evan Cheng 102428b92eb83b457b71d29d1d4b7900d36a0ce9a53Chris Lattner for (MachineBasicBlock::iterator I = MBB->begin(), E = MBB->end(); 103428b92eb83b457b71d29d1d4b7900d36a0ce9a53Chris Lattner I != E; ++I) { 104428b92eb83b457b71d29d1d4b7900d36a0ce9a53Chris Lattner bool inserted = mi2iMap_.insert(std::make_pair(I, MIIndex)).second; 1051a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos assert(inserted && "multiple MachineInstr -> index mappings"); 106428b92eb83b457b71d29d1d4b7900d36a0ce9a53Chris Lattner i2miMap_.push_back(I); 107428b92eb83b457b71d29d1d4b7900d36a0ce9a53Chris Lattner MIIndex += InstrSlots::NUM; 1081a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos } 109549f27d3070195d6647b796841a5291b4549e8e0Evan Cheng 110549f27d3070195d6647b796841a5291b4549e8e0Evan Cheng // Set the MBB2IdxMap entry for this MBB. 111549f27d3070195d6647b796841a5291b4549e8e0Evan Cheng MBB2IdxMap[MBB->getNumber()] = std::make_pair(StartIdx, MIIndex - 1); 1124ca980e7f9ce7b78955307c2d07001a24d3b6befEvan Cheng Idx2MBBMap.push_back(std::make_pair(StartIdx, MBB)); 113428b92eb83b457b71d29d1d4b7900d36a0ce9a53Chris Lattner } 1144ca980e7f9ce7b78955307c2d07001a24d3b6befEvan Cheng std::sort(Idx2MBBMap.begin(), Idx2MBBMap.end(), Idx2MBBCompare()); 115ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos 1161a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos computeIntervals(); 117ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos 1181a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos numIntervals += getNumIntervals(); 119843b160a2040b3ec4d3452678450afa11704c473Alkis Evlogimenos 120bdc679d564e67a81792e463f6614b0088f975025Bill Wendling DOUT << "********** INTERVALS **********\n"; 121bdc679d564e67a81792e463f6614b0088f975025Bill Wendling for (iterator I = begin(), E = end(); I != E; ++I) { 1226f0d024a534af18d9e60b3ea757376cd8a3a980eDan Gohman I->second.print(DOUT, tri_); 123bdc679d564e67a81792e463f6614b0088f975025Bill Wendling DOUT << "\n"; 124bdc679d564e67a81792e463f6614b0088f975025Bill Wendling } 1257ac2d3146a196fa0120c579ecd2ddd69652ad230Chris Lattner 1261a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos numIntervalsAfter += getNumIntervals(); 12770ca358b7d540b6061236ddf757085042873c12cChris Lattner DEBUG(dump()); 1281a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos return true; 129ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos} 130ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos 13170ca358b7d540b6061236ddf757085042873c12cChris Lattner/// print - Implement the dump method. 132ce9653ce449f1409815547e1bf60abcd1332d2c9Reid Spencervoid LiveIntervals::print(std::ostream &O, const Module* ) const { 13370ca358b7d540b6061236ddf757085042873c12cChris Lattner O << "********** INTERVALS **********\n"; 1348e7a70976deee78a84099b916591d40f7a1cdc34Chris Lattner for (const_iterator I = begin(), E = end(); I != E; ++I) { 1356f0d024a534af18d9e60b3ea757376cd8a3a980eDan Gohman I->second.print(DOUT, tri_); 136bdc679d564e67a81792e463f6614b0088f975025Bill Wendling DOUT << "\n"; 1378e7a70976deee78a84099b916591d40f7a1cdc34Chris Lattner } 13870ca358b7d540b6061236ddf757085042873c12cChris Lattner 13970ca358b7d540b6061236ddf757085042873c12cChris Lattner O << "********** MACHINEINSTRS **********\n"; 14070ca358b7d540b6061236ddf757085042873c12cChris Lattner for (MachineFunction::iterator mbbi = mf_->begin(), mbbe = mf_->end(); 14170ca358b7d540b6061236ddf757085042873c12cChris Lattner mbbi != mbbe; ++mbbi) { 14270ca358b7d540b6061236ddf757085042873c12cChris Lattner O << ((Value*)mbbi->getBasicBlock())->getName() << ":\n"; 14370ca358b7d540b6061236ddf757085042873c12cChris Lattner for (MachineBasicBlock::iterator mii = mbbi->begin(), 14470ca358b7d540b6061236ddf757085042873c12cChris Lattner mie = mbbi->end(); mii != mie; ++mii) { 145477e4555de341c5de780de3720d6f115ec133c4eChris Lattner O << getInstructionIndex(mii) << '\t' << *mii; 14670ca358b7d540b6061236ddf757085042873c12cChris Lattner } 14770ca358b7d540b6061236ddf757085042873c12cChris Lattner } 14870ca358b7d540b6061236ddf757085042873c12cChris Lattner} 14970ca358b7d540b6061236ddf757085042873c12cChris Lattner 150c92da3882ee4e18153bb36fcdf33af393aba8259Evan Cheng/// conflictsWithPhysRegDef - Returns true if the specified register 151c92da3882ee4e18153bb36fcdf33af393aba8259Evan Cheng/// is defined during the duration of the specified interval. 152c92da3882ee4e18153bb36fcdf33af393aba8259Evan Chengbool LiveIntervals::conflictsWithPhysRegDef(const LiveInterval &li, 153c92da3882ee4e18153bb36fcdf33af393aba8259Evan Cheng VirtRegMap &vrm, unsigned reg) { 154c92da3882ee4e18153bb36fcdf33af393aba8259Evan Cheng for (LiveInterval::Ranges::const_iterator 155c92da3882ee4e18153bb36fcdf33af393aba8259Evan Cheng I = li.ranges.begin(), E = li.ranges.end(); I != E; ++I) { 156c92da3882ee4e18153bb36fcdf33af393aba8259Evan Cheng for (unsigned index = getBaseIndex(I->start), 157c92da3882ee4e18153bb36fcdf33af393aba8259Evan Cheng end = getBaseIndex(I->end-1) + InstrSlots::NUM; index != end; 158c92da3882ee4e18153bb36fcdf33af393aba8259Evan Cheng index += InstrSlots::NUM) { 159c92da3882ee4e18153bb36fcdf33af393aba8259Evan Cheng // skip deleted instructions 160c92da3882ee4e18153bb36fcdf33af393aba8259Evan Cheng while (index != end && !getInstructionFromIndex(index)) 161c92da3882ee4e18153bb36fcdf33af393aba8259Evan Cheng index += InstrSlots::NUM; 162c92da3882ee4e18153bb36fcdf33af393aba8259Evan Cheng if (index == end) break; 163c92da3882ee4e18153bb36fcdf33af393aba8259Evan Cheng 164c92da3882ee4e18153bb36fcdf33af393aba8259Evan Cheng MachineInstr *MI = getInstructionFromIndex(index); 1655d446265c740c17ed12e693423f0363296670d60Evan Cheng unsigned SrcReg, DstReg; 1665d446265c740c17ed12e693423f0363296670d60Evan Cheng if (tii_->isMoveInstr(*MI, SrcReg, DstReg)) 1675d446265c740c17ed12e693423f0363296670d60Evan Cheng if (SrcReg == li.reg || DstReg == li.reg) 1685d446265c740c17ed12e693423f0363296670d60Evan Cheng continue; 169c92da3882ee4e18153bb36fcdf33af393aba8259Evan Cheng for (unsigned i = 0; i != MI->getNumOperands(); ++i) { 170c92da3882ee4e18153bb36fcdf33af393aba8259Evan Cheng MachineOperand& mop = MI->getOperand(i); 1715d446265c740c17ed12e693423f0363296670d60Evan Cheng if (!mop.isRegister()) 172c92da3882ee4e18153bb36fcdf33af393aba8259Evan Cheng continue; 173c92da3882ee4e18153bb36fcdf33af393aba8259Evan Cheng unsigned PhysReg = mop.getReg(); 1745d446265c740c17ed12e693423f0363296670d60Evan Cheng if (PhysReg == 0 || PhysReg == li.reg) 175c92da3882ee4e18153bb36fcdf33af393aba8259Evan Cheng continue; 1766f0d024a534af18d9e60b3ea757376cd8a3a980eDan Gohman if (TargetRegisterInfo::isVirtualRegister(PhysReg)) { 1775d446265c740c17ed12e693423f0363296670d60Evan Cheng if (!vrm.hasPhys(PhysReg)) 1785d446265c740c17ed12e693423f0363296670d60Evan Cheng continue; 179c92da3882ee4e18153bb36fcdf33af393aba8259Evan Cheng PhysReg = vrm.getPhys(PhysReg); 1805d446265c740c17ed12e693423f0363296670d60Evan Cheng } 1816f0d024a534af18d9e60b3ea757376cd8a3a980eDan Gohman if (PhysReg && tri_->regsOverlap(PhysReg, reg)) 182c92da3882ee4e18153bb36fcdf33af393aba8259Evan Cheng return true; 183c92da3882ee4e18153bb36fcdf33af393aba8259Evan Cheng } 184c92da3882ee4e18153bb36fcdf33af393aba8259Evan Cheng } 185c92da3882ee4e18153bb36fcdf33af393aba8259Evan Cheng } 186c92da3882ee4e18153bb36fcdf33af393aba8259Evan Cheng 187c92da3882ee4e18153bb36fcdf33af393aba8259Evan Cheng return false; 188c92da3882ee4e18153bb36fcdf33af393aba8259Evan Cheng} 189c92da3882ee4e18153bb36fcdf33af393aba8259Evan Cheng 190be4f88a8b8bb3311e0dc4cde8533763d7923c3eaChris Lattnervoid LiveIntervals::printRegName(unsigned reg) const { 1916f0d024a534af18d9e60b3ea757376cd8a3a980eDan Gohman if (TargetRegisterInfo::isPhysicalRegister(reg)) 1926f0d024a534af18d9e60b3ea757376cd8a3a980eDan Gohman cerr << tri_->getName(reg); 1931a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos else 194e81561909d128c6e2d8033cb5465a49b2596b26aBill Wendling cerr << "%reg" << reg; 195ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos} 196ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos 197be4f88a8b8bb3311e0dc4cde8533763d7923c3eaChris Lattnervoid LiveIntervals::handleVirtualRegisterDef(MachineBasicBlock *mbb, 198ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos MachineBasicBlock::iterator mi, 1996b128bdc58a496e9f08e4d09416330320761baffChris Lattner unsigned MIIdx, 200be4f88a8b8bb3311e0dc4cde8533763d7923c3eaChris Lattner LiveInterval &interval) { 201bdc679d564e67a81792e463f6614b0088f975025Bill Wendling DOUT << "\t\tregister: "; DEBUG(printRegName(interval.reg)); 2021a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos LiveVariables::VarInfo& vi = lv_->getVarInfo(interval.reg); 2031a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos 204706515727c6d024015fffded2b3109a4f0ac5299Alkis Evlogimenos // Virtual registers may be defined multiple times (due to phi 205706515727c6d024015fffded2b3109a4f0ac5299Alkis Evlogimenos // elimination and 2-addr elimination). Much of what we do only has to be 206706515727c6d024015fffded2b3109a4f0ac5299Alkis Evlogimenos // done once for the vreg. We use an empty interval to detect the first 2071a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // time we see a vreg. 2081a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos if (interval.empty()) { 2091a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // Get the Idx of the defining instructions. 2106b128bdc58a496e9f08e4d09416330320761baffChris Lattner unsigned defIndex = getDefIndex(MIIdx); 2117ecb38be0a533e7b9c7d3b8e9b5c8a6fa5f6b349Evan Cheng VNInfo *ValNo; 212c8d044e4f779fdcfc5e7d592927740fd8f672a70Evan Cheng MachineInstr *CopyMI = NULL; 21391725b75852443923b419fd23215194cfc65dd88Chris Lattner unsigned SrcReg, DstReg; 214c8d044e4f779fdcfc5e7d592927740fd8f672a70Evan Cheng if (mi->getOpcode() == TargetInstrInfo::EXTRACT_SUBREG || 215c8d044e4f779fdcfc5e7d592927740fd8f672a70Evan Cheng tii_->isMoveInstr(*mi, SrcReg, DstReg)) 216c8d044e4f779fdcfc5e7d592927740fd8f672a70Evan Cheng CopyMI = mi; 217c8d044e4f779fdcfc5e7d592927740fd8f672a70Evan Cheng ValNo = interval.getNextValue(defIndex, CopyMI, VNInfoAllocator); 2187ecb38be0a533e7b9c7d3b8e9b5c8a6fa5f6b349Evan Cheng 2197ecb38be0a533e7b9c7d3b8e9b5c8a6fa5f6b349Evan Cheng assert(ValNo->id == 0 && "First value in interval is not 0?"); 2201a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos 2211a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // Loop over all of the blocks that the vreg is defined in. There are 2221a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // two cases we have to handle here. The most common case is a vreg 2231a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // whose lifetime is contained within a basic block. In this case there 2241a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // will be a single kill, in MBB, which comes after the definition. 2251a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos if (vi.Kills.size() == 1 && vi.Kills[0]->getParent() == mbb) { 2261a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // FIXME: what about dead vars? 2271a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos unsigned killIdx; 2281a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos if (vi.Kills[0] != mi) 2291a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos killIdx = getUseIndex(getInstructionIndex(vi.Kills[0]))+1; 2301a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos else 2311a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos killIdx = defIndex+1; 2321a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos 2331a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // If the kill happens after the definition, we have an intra-block 2341a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // live range. 2351a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos if (killIdx > defIndex) { 23661de82d8853a02fe39c47302432abb70a586704fEvan Cheng assert(vi.AliveBlocks.none() && 2371a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos "Shouldn't be alive across any blocks!"); 2387ecb38be0a533e7b9c7d3b8e9b5c8a6fa5f6b349Evan Cheng LiveRange LR(defIndex, killIdx, ValNo); 2391a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos interval.addRange(LR); 240bdc679d564e67a81792e463f6614b0088f975025Bill Wendling DOUT << " +" << LR << "\n"; 241f3bb2e65d12857f83b273f4ecab013680310bbbcEvan Cheng interval.addKill(ValNo, killIdx); 2421a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos return; 2431a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos } 2441a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos } 2456097d13b2a624048dbe02e39e2dfb23bfa269b64Chris Lattner 2461a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // The other case we handle is when a virtual register lives to the end 2471a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // of the defining block, potentially live across some blocks, then is 2481a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // live into some number of blocks, but gets killed. Start by adding a 2491a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // range that goes from this definition to the end of the defining block. 250d19e2901c1b79d287d01079659684f3a4951a69eAlkis Evlogimenos LiveRange NewLR(defIndex, 251d19e2901c1b79d287d01079659684f3a4951a69eAlkis Evlogimenos getInstructionIndex(&mbb->back()) + InstrSlots::NUM, 2527ecb38be0a533e7b9c7d3b8e9b5c8a6fa5f6b349Evan Cheng ValNo); 253bdc679d564e67a81792e463f6614b0088f975025Bill Wendling DOUT << " +" << NewLR; 2541a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos interval.addRange(NewLR); 2551a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos 2561a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // Iterate over all of the blocks that the variable is completely 2571a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // live in, adding [insrtIndex(begin), instrIndex(end)+4) to the 2581a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // live interval. 2591a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos for (unsigned i = 0, e = vi.AliveBlocks.size(); i != e; ++i) { 2601a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos if (vi.AliveBlocks[i]) { 261428b92eb83b457b71d29d1d4b7900d36a0ce9a53Chris Lattner MachineBasicBlock *MBB = mf_->getBlockNumbered(i); 262428b92eb83b457b71d29d1d4b7900d36a0ce9a53Chris Lattner if (!MBB->empty()) { 263428b92eb83b457b71d29d1d4b7900d36a0ce9a53Chris Lattner LiveRange LR(getMBBStartIdx(i), 264428b92eb83b457b71d29d1d4b7900d36a0ce9a53Chris Lattner getInstructionIndex(&MBB->back()) + InstrSlots::NUM, 2657ecb38be0a533e7b9c7d3b8e9b5c8a6fa5f6b349Evan Cheng ValNo); 2661a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos interval.addRange(LR); 267bdc679d564e67a81792e463f6614b0088f975025Bill Wendling DOUT << " +" << LR; 2681a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos } 2691a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos } 2701a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos } 2711a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos 2721a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // Finally, this virtual register is live from the start of any killing 2731a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // block to the 'use' slot of the killing instruction. 2741a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos for (unsigned i = 0, e = vi.Kills.size(); i != e; ++i) { 2751a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos MachineInstr *Kill = vi.Kills[i]; 2768df786012dc6b875f31ba4152e09c6e0098082eeEvan Cheng unsigned killIdx = getUseIndex(getInstructionIndex(Kill))+1; 277428b92eb83b457b71d29d1d4b7900d36a0ce9a53Chris Lattner LiveRange LR(getMBBStartIdx(Kill->getParent()), 2787ecb38be0a533e7b9c7d3b8e9b5c8a6fa5f6b349Evan Cheng killIdx, ValNo); 2791a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos interval.addRange(LR); 280f3bb2e65d12857f83b273f4ecab013680310bbbcEvan Cheng interval.addKill(ValNo, killIdx); 281bdc679d564e67a81792e463f6614b0088f975025Bill Wendling DOUT << " +" << LR; 2821a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos } 2831a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos 2841a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos } else { 2851a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // If this is the second time we see a virtual register definition, it 2861a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // must be due to phi elimination or two addr elimination. If this is 287bf105c842450d3308d024be203ddd533f37051ecEvan Cheng // the result of two address elimination, then the vreg is one of the 288bf105c842450d3308d024be203ddd533f37051ecEvan Cheng // def-and-use register operand. 28932dfbeada7292167bb488f36a71a5a6a519ddaffEvan Cheng if (mi->isRegReDefinedByTwoAddr(interval.reg)) { 2901a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // If this is a two-address definition, then we have already processed 2911a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // the live range. The only problem is that we didn't realize there 2921a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // are actually two values in the live interval. Because of this we 2931a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // need to take the LiveRegion that defines this register and split it 2941a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // into two values. 295a07cec9e24a286157541d2337cd66b24cd116586Evan Cheng assert(interval.containsOneValue()); 296a07cec9e24a286157541d2337cd66b24cd116586Evan Cheng unsigned DefIndex = getDefIndex(interval.getValNumInfo(0)->def); 2976b128bdc58a496e9f08e4d09416330320761baffChris Lattner unsigned RedefIndex = getDefIndex(MIIdx); 2981a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos 2994f8ff168de12eabdeb4b9437bf9402489ecf85cbEvan Cheng const LiveRange *OldLR = interval.getLiveRangeContaining(RedefIndex-1); 3007ecb38be0a533e7b9c7d3b8e9b5c8a6fa5f6b349Evan Cheng VNInfo *OldValNo = OldLR->valno; 3014f8ff168de12eabdeb4b9437bf9402489ecf85cbEvan Cheng 3021a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // Delete the initial value, which should be short and continuous, 303be4f88a8b8bb3311e0dc4cde8533763d7923c3eaChris Lattner // because the 2-addr copy must be in the same MBB as the redef. 3041a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos interval.removeRange(DefIndex, RedefIndex); 305706515727c6d024015fffded2b3109a4f0ac5299Alkis Evlogimenos 306be4f88a8b8bb3311e0dc4cde8533763d7923c3eaChris Lattner // Two-address vregs should always only be redefined once. This means 307be4f88a8b8bb3311e0dc4cde8533763d7923c3eaChris Lattner // that at this point, there should be exactly one value number in it. 308be4f88a8b8bb3311e0dc4cde8533763d7923c3eaChris Lattner assert(interval.containsOneValue() && "Unexpected 2-addr liveint!"); 309be4f88a8b8bb3311e0dc4cde8533763d7923c3eaChris Lattner 31091725b75852443923b419fd23215194cfc65dd88Chris Lattner // The new value number (#1) is defined by the instruction we claimed 31191725b75852443923b419fd23215194cfc65dd88Chris Lattner // defined value #0. 312c8d044e4f779fdcfc5e7d592927740fd8f672a70Evan Cheng VNInfo *ValNo = interval.getNextValue(OldValNo->def, OldValNo->copy, 313c8d044e4f779fdcfc5e7d592927740fd8f672a70Evan Cheng VNInfoAllocator); 314be4f88a8b8bb3311e0dc4cde8533763d7923c3eaChris Lattner 31591725b75852443923b419fd23215194cfc65dd88Chris Lattner // Value#0 is now defined by the 2-addr instruction. 316c8d044e4f779fdcfc5e7d592927740fd8f672a70Evan Cheng OldValNo->def = RedefIndex; 317c8d044e4f779fdcfc5e7d592927740fd8f672a70Evan Cheng OldValNo->copy = 0; 318be4f88a8b8bb3311e0dc4cde8533763d7923c3eaChris Lattner 319be4f88a8b8bb3311e0dc4cde8533763d7923c3eaChris Lattner // Add the new live interval which replaces the range for the input copy. 320be4f88a8b8bb3311e0dc4cde8533763d7923c3eaChris Lattner LiveRange LR(DefIndex, RedefIndex, ValNo); 321bdc679d564e67a81792e463f6614b0088f975025Bill Wendling DOUT << " replace range with " << LR; 3221a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos interval.addRange(LR); 323f3bb2e65d12857f83b273f4ecab013680310bbbcEvan Cheng interval.addKill(ValNo, RedefIndex); 3241a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos 3251a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // If this redefinition is dead, we need to add a dummy unit live 3261a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // range covering the def slot. 327ab4b66d4c279e8cd9e448687020fc838e7881dbcChris Lattner if (lv_->RegisterDefIsDead(mi, interval.reg)) 3287ecb38be0a533e7b9c7d3b8e9b5c8a6fa5f6b349Evan Cheng interval.addRange(LiveRange(RedefIndex, RedefIndex+1, OldValNo)); 3291a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos 33056fdd7af884a35673fb6dd3e01333960922c3ac2Evan Cheng DOUT << " RESULT: "; 3316f0d024a534af18d9e60b3ea757376cd8a3a980eDan Gohman interval.print(DOUT, tri_); 3321a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos 3331a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos } else { 3341a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // Otherwise, this must be because of phi elimination. If this is the 3351a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // first redefinition of the vreg that we have seen, go back and change 3361a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // the live range in the PHI block to be a different value number. 3371a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos if (interval.containsOneValue()) { 3381a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos assert(vi.Kills.size() == 1 && 3391a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos "PHI elimination vreg should have one kill, the PHI itself!"); 3401a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos 3411a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // Remove the old range that we now know has an incorrect number. 342f3bb2e65d12857f83b273f4ecab013680310bbbcEvan Cheng VNInfo *VNI = interval.getValNumInfo(0); 3431a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos MachineInstr *Killer = vi.Kills[0]; 344428b92eb83b457b71d29d1d4b7900d36a0ce9a53Chris Lattner unsigned Start = getMBBStartIdx(Killer->getParent()); 3451a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos unsigned End = getUseIndex(getInstructionIndex(Killer))+1; 34656fdd7af884a35673fb6dd3e01333960922c3ac2Evan Cheng DOUT << " Removing [" << Start << "," << End << "] from: "; 3476f0d024a534af18d9e60b3ea757376cd8a3a980eDan Gohman interval.print(DOUT, tri_); DOUT << "\n"; 3481a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos interval.removeRange(Start, End); 349c3fc7d9ec9b495c8a88cd854247105c296d3aabdEvan Cheng VNI->hasPHIKill = true; 3506f0d024a534af18d9e60b3ea757376cd8a3a980eDan Gohman DOUT << " RESULT: "; interval.print(DOUT, tri_); 3511a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos 352be4f88a8b8bb3311e0dc4cde8533763d7923c3eaChris Lattner // Replace the interval with one of a NEW value number. Note that this 353be4f88a8b8bb3311e0dc4cde8533763d7923c3eaChris Lattner // value number isn't actually defined by an instruction, weird huh? :) 354f3bb2e65d12857f83b273f4ecab013680310bbbcEvan Cheng LiveRange LR(Start, End, interval.getNextValue(~0, 0, VNInfoAllocator)); 355bdc679d564e67a81792e463f6614b0088f975025Bill Wendling DOUT << " replace range with " << LR; 3561a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos interval.addRange(LR); 357f3bb2e65d12857f83b273f4ecab013680310bbbcEvan Cheng interval.addKill(LR.valno, End); 3586f0d024a534af18d9e60b3ea757376cd8a3a980eDan Gohman DOUT << " RESULT: "; interval.print(DOUT, tri_); 3591a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos } 3601a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos 3611a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // In the case of PHI elimination, each variable definition is only 3621a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // live until the end of the block. We've already taken care of the 3631a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // rest of the live range. 3646b128bdc58a496e9f08e4d09416330320761baffChris Lattner unsigned defIndex = getDefIndex(MIIdx); 36591725b75852443923b419fd23215194cfc65dd88Chris Lattner 3667ecb38be0a533e7b9c7d3b8e9b5c8a6fa5f6b349Evan Cheng VNInfo *ValNo; 367c8d044e4f779fdcfc5e7d592927740fd8f672a70Evan Cheng MachineInstr *CopyMI = NULL; 36891725b75852443923b419fd23215194cfc65dd88Chris Lattner unsigned SrcReg, DstReg; 369c8d044e4f779fdcfc5e7d592927740fd8f672a70Evan Cheng if (mi->getOpcode() == TargetInstrInfo::EXTRACT_SUBREG || 370c8d044e4f779fdcfc5e7d592927740fd8f672a70Evan Cheng tii_->isMoveInstr(*mi, SrcReg, DstReg)) 371c8d044e4f779fdcfc5e7d592927740fd8f672a70Evan Cheng CopyMI = mi; 372c8d044e4f779fdcfc5e7d592927740fd8f672a70Evan Cheng ValNo = interval.getNextValue(defIndex, CopyMI, VNInfoAllocator); 37391725b75852443923b419fd23215194cfc65dd88Chris Lattner 37424c2e5cf7e926452ea5875d027ec0d24d9c19e39Evan Cheng unsigned killIndex = getInstructionIndex(&mbb->back()) + InstrSlots::NUM; 3757ecb38be0a533e7b9c7d3b8e9b5c8a6fa5f6b349Evan Cheng LiveRange LR(defIndex, killIndex, ValNo); 3761a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos interval.addRange(LR); 377c3fc7d9ec9b495c8a88cd854247105c296d3aabdEvan Cheng interval.addKill(ValNo, killIndex); 378c3fc7d9ec9b495c8a88cd854247105c296d3aabdEvan Cheng ValNo->hasPHIKill = true; 379bdc679d564e67a81792e463f6614b0088f975025Bill Wendling DOUT << " +" << LR; 380dd2cc65f34f9b7bfda1cd0c42becedfc361d46f8Alkis Evlogimenos } 3811a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos } 382ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos 383bdc679d564e67a81792e463f6614b0088f975025Bill Wendling DOUT << '\n'; 384ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos} 385ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos 386f35fef7060c465dd7b578bf6339a18e8a8911888Chris Lattnervoid LiveIntervals::handlePhysicalRegisterDef(MachineBasicBlock *MBB, 387ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos MachineBasicBlock::iterator mi, 3886b128bdc58a496e9f08e4d09416330320761baffChris Lattner unsigned MIIdx, 38991725b75852443923b419fd23215194cfc65dd88Chris Lattner LiveInterval &interval, 390c8d044e4f779fdcfc5e7d592927740fd8f672a70Evan Cheng MachineInstr *CopyMI) { 3911a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // A physical register cannot be live across basic block, so its 3921a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // lifetime must end somewhere in its defining basic block. 393bdc679d564e67a81792e463f6614b0088f975025Bill Wendling DOUT << "\t\tregister: "; DEBUG(printRegName(interval.reg)); 3941a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos 3956b128bdc58a496e9f08e4d09416330320761baffChris Lattner unsigned baseIndex = MIIdx; 3961a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos unsigned start = getDefIndex(baseIndex); 3971a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos unsigned end = start; 3981a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos 3991a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // If it is not used after definition, it is considered dead at 4001a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // the instruction defining it. Hence its interval is: 4011a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // [defSlot(def), defSlot(def)+1) 402ab4b66d4c279e8cd9e448687020fc838e7881dbcChris Lattner if (lv_->RegisterDefIsDead(mi, interval.reg)) { 403bdc679d564e67a81792e463f6614b0088f975025Bill Wendling DOUT << " dead"; 404ab4b66d4c279e8cd9e448687020fc838e7881dbcChris Lattner end = getDefIndex(start) + 1; 405ab4b66d4c279e8cd9e448687020fc838e7881dbcChris Lattner goto exit; 4061a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos } 407ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos 4081a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // If it is not dead on definition, it must be killed by a 4091a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // subsequent instruction. Hence its interval is: 4101a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // [defSlot(def), useSlot(kill)+1) 4115ab6f5fe666d0e3403d9b777324d1a1999118153Chris Lattner while (++mi != MBB->end()) { 4121a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos baseIndex += InstrSlots::NUM; 413ab4b66d4c279e8cd9e448687020fc838e7881dbcChris Lattner if (lv_->KillsRegister(mi, interval.reg)) { 414bdc679d564e67a81792e463f6614b0088f975025Bill Wendling DOUT << " killed"; 415ab4b66d4c279e8cd9e448687020fc838e7881dbcChris Lattner end = getUseIndex(baseIndex) + 1; 416ab4b66d4c279e8cd9e448687020fc838e7881dbcChris Lattner goto exit; 4179a1956ae6ad2d4892afbc9f1b97d645d220b6d4aEvan Cheng } else if (lv_->ModifiesRegister(mi, interval.reg)) { 4189a1956ae6ad2d4892afbc9f1b97d645d220b6d4aEvan Cheng // Another instruction redefines the register before it is ever read. 4199a1956ae6ad2d4892afbc9f1b97d645d220b6d4aEvan Cheng // Then the register is essentially dead at the instruction that defines 4209a1956ae6ad2d4892afbc9f1b97d645d220b6d4aEvan Cheng // it. Hence its interval is: 4219a1956ae6ad2d4892afbc9f1b97d645d220b6d4aEvan Cheng // [defSlot(def), defSlot(def)+1) 422bdc679d564e67a81792e463f6614b0088f975025Bill Wendling DOUT << " dead"; 4239a1956ae6ad2d4892afbc9f1b97d645d220b6d4aEvan Cheng end = getDefIndex(start) + 1; 4249a1956ae6ad2d4892afbc9f1b97d645d220b6d4aEvan Cheng goto exit; 425f35fef7060c465dd7b578bf6339a18e8a8911888Chris Lattner } 4261a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos } 4275ab6f5fe666d0e3403d9b777324d1a1999118153Chris Lattner 4285ab6f5fe666d0e3403d9b777324d1a1999118153Chris Lattner // The only case we should have a dead physreg here without a killing or 4295ab6f5fe666d0e3403d9b777324d1a1999118153Chris Lattner // instruction where we know it's dead is if it is live-in to the function 4305ab6f5fe666d0e3403d9b777324d1a1999118153Chris Lattner // and never used. 431c8d044e4f779fdcfc5e7d592927740fd8f672a70Evan Cheng assert(!CopyMI && "physreg was not killed in defining block!"); 4325ab6f5fe666d0e3403d9b777324d1a1999118153Chris Lattner end = getDefIndex(start) + 1; // It's dead. 43302ba13c9897ae2b19f9201e57460d7ee2b753a0bAlkis Evlogimenos 434ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenosexit: 4351a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos assert(start < end && "did not find end of interval?"); 436f768bba43f5c036039851d2fcca8212edca18467Chris Lattner 43724a3cc4c83e5edb25fadf7b8979a26b4451795c6Evan Cheng // Already exists? Extend old live interval. 43824a3cc4c83e5edb25fadf7b8979a26b4451795c6Evan Cheng LiveInterval::iterator OldLR = interval.FindLiveRangeContaining(start); 4397ecb38be0a533e7b9c7d3b8e9b5c8a6fa5f6b349Evan Cheng VNInfo *ValNo = (OldLR != interval.end()) 440c8d044e4f779fdcfc5e7d592927740fd8f672a70Evan Cheng ? OldLR->valno : interval.getNextValue(start, CopyMI, VNInfoAllocator); 4417ecb38be0a533e7b9c7d3b8e9b5c8a6fa5f6b349Evan Cheng LiveRange LR(start, end, ValNo); 4421a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos interval.addRange(LR); 443f3bb2e65d12857f83b273f4ecab013680310bbbcEvan Cheng interval.addKill(LR.valno, end); 444bdc679d564e67a81792e463f6614b0088f975025Bill Wendling DOUT << " +" << LR << '\n'; 445ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos} 446ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos 447f35fef7060c465dd7b578bf6339a18e8a8911888Chris Lattnervoid LiveIntervals::handleRegisterDef(MachineBasicBlock *MBB, 448f35fef7060c465dd7b578bf6339a18e8a8911888Chris Lattner MachineBasicBlock::iterator MI, 4496b128bdc58a496e9f08e4d09416330320761baffChris Lattner unsigned MIIdx, 450f35fef7060c465dd7b578bf6339a18e8a8911888Chris Lattner unsigned reg) { 4516f0d024a534af18d9e60b3ea757376cd8a3a980eDan Gohman if (TargetRegisterInfo::isVirtualRegister(reg)) 4526b128bdc58a496e9f08e4d09416330320761baffChris Lattner handleVirtualRegisterDef(MBB, MI, MIIdx, getOrCreateInterval(reg)); 4535327801fb87e3eda52a33f82e6211181030ecb93Alkis Evlogimenos else if (allocatableRegs_[reg]) { 454c8d044e4f779fdcfc5e7d592927740fd8f672a70Evan Cheng MachineInstr *CopyMI = NULL; 45591725b75852443923b419fd23215194cfc65dd88Chris Lattner unsigned SrcReg, DstReg; 456c8d044e4f779fdcfc5e7d592927740fd8f672a70Evan Cheng if (MI->getOpcode() == TargetInstrInfo::EXTRACT_SUBREG || 457c8d044e4f779fdcfc5e7d592927740fd8f672a70Evan Cheng tii_->isMoveInstr(*MI, SrcReg, DstReg)) 458c8d044e4f779fdcfc5e7d592927740fd8f672a70Evan Cheng CopyMI = MI; 459c8d044e4f779fdcfc5e7d592927740fd8f672a70Evan Cheng handlePhysicalRegisterDef(MBB, MI, MIIdx, getOrCreateInterval(reg), CopyMI); 46024a3cc4c83e5edb25fadf7b8979a26b4451795c6Evan Cheng // Def of a register also defines its sub-registers. 4616f0d024a534af18d9e60b3ea757376cd8a3a980eDan Gohman for (const unsigned* AS = tri_->getSubRegisters(reg); *AS; ++AS) 46224a3cc4c83e5edb25fadf7b8979a26b4451795c6Evan Cheng // Avoid processing some defs more than once. 46324a3cc4c83e5edb25fadf7b8979a26b4451795c6Evan Cheng if (!MI->findRegisterDefOperand(*AS)) 46424a3cc4c83e5edb25fadf7b8979a26b4451795c6Evan Cheng handlePhysicalRegisterDef(MBB, MI, MIIdx, getOrCreateInterval(*AS), 0); 465f35fef7060c465dd7b578bf6339a18e8a8911888Chris Lattner } 4664d46e1e521c0df1990ea50f8146d22bd77ea71a6Alkis Evlogimenos} 4674d46e1e521c0df1990ea50f8146d22bd77ea71a6Alkis Evlogimenos 468b371f457b0ea4a652a9f526ba4375c80ae542252Evan Chengvoid LiveIntervals::handleLiveInRegister(MachineBasicBlock *MBB, 4699b25b8ca24d6df2e097741dcc15016772ee4eda7Jim Laskey unsigned MIIdx, 47024a3cc4c83e5edb25fadf7b8979a26b4451795c6Evan Cheng LiveInterval &interval, bool isAlias) { 471b371f457b0ea4a652a9f526ba4375c80ae542252Evan Cheng DOUT << "\t\tlivein register: "; DEBUG(printRegName(interval.reg)); 472b371f457b0ea4a652a9f526ba4375c80ae542252Evan Cheng 473b371f457b0ea4a652a9f526ba4375c80ae542252Evan Cheng // Look for kills, if it reaches a def before it's killed, then it shouldn't 474b371f457b0ea4a652a9f526ba4375c80ae542252Evan Cheng // be considered a livein. 475b371f457b0ea4a652a9f526ba4375c80ae542252Evan Cheng MachineBasicBlock::iterator mi = MBB->begin(); 4769b25b8ca24d6df2e097741dcc15016772ee4eda7Jim Laskey unsigned baseIndex = MIIdx; 4779b25b8ca24d6df2e097741dcc15016772ee4eda7Jim Laskey unsigned start = baseIndex; 478b371f457b0ea4a652a9f526ba4375c80ae542252Evan Cheng unsigned end = start; 479b371f457b0ea4a652a9f526ba4375c80ae542252Evan Cheng while (mi != MBB->end()) { 480b371f457b0ea4a652a9f526ba4375c80ae542252Evan Cheng if (lv_->KillsRegister(mi, interval.reg)) { 481b371f457b0ea4a652a9f526ba4375c80ae542252Evan Cheng DOUT << " killed"; 482b371f457b0ea4a652a9f526ba4375c80ae542252Evan Cheng end = getUseIndex(baseIndex) + 1; 483b371f457b0ea4a652a9f526ba4375c80ae542252Evan Cheng goto exit; 484b371f457b0ea4a652a9f526ba4375c80ae542252Evan Cheng } else if (lv_->ModifiesRegister(mi, interval.reg)) { 485b371f457b0ea4a652a9f526ba4375c80ae542252Evan Cheng // Another instruction redefines the register before it is ever read. 486b371f457b0ea4a652a9f526ba4375c80ae542252Evan Cheng // Then the register is essentially dead at the instruction that defines 487b371f457b0ea4a652a9f526ba4375c80ae542252Evan Cheng // it. Hence its interval is: 488b371f457b0ea4a652a9f526ba4375c80ae542252Evan Cheng // [defSlot(def), defSlot(def)+1) 489b371f457b0ea4a652a9f526ba4375c80ae542252Evan Cheng DOUT << " dead"; 490b371f457b0ea4a652a9f526ba4375c80ae542252Evan Cheng end = getDefIndex(start) + 1; 491b371f457b0ea4a652a9f526ba4375c80ae542252Evan Cheng goto exit; 492b371f457b0ea4a652a9f526ba4375c80ae542252Evan Cheng } 493b371f457b0ea4a652a9f526ba4375c80ae542252Evan Cheng 494b371f457b0ea4a652a9f526ba4375c80ae542252Evan Cheng baseIndex += InstrSlots::NUM; 495b371f457b0ea4a652a9f526ba4375c80ae542252Evan Cheng ++mi; 496b371f457b0ea4a652a9f526ba4375c80ae542252Evan Cheng } 497b371f457b0ea4a652a9f526ba4375c80ae542252Evan Cheng 498b371f457b0ea4a652a9f526ba4375c80ae542252Evan Chengexit: 49975611fb4e6ab253be30ac29a2b15e9bf8c1d146eEvan Cheng // Live-in register might not be used at all. 50075611fb4e6ab253be30ac29a2b15e9bf8c1d146eEvan Cheng if (end == MIIdx) { 501292da949f6c87d6499425d64d37d7c5870ec57adEvan Cheng if (isAlias) { 502292da949f6c87d6499425d64d37d7c5870ec57adEvan Cheng DOUT << " dead"; 50375611fb4e6ab253be30ac29a2b15e9bf8c1d146eEvan Cheng end = getDefIndex(MIIdx) + 1; 504292da949f6c87d6499425d64d37d7c5870ec57adEvan Cheng } else { 505292da949f6c87d6499425d64d37d7c5870ec57adEvan Cheng DOUT << " live through"; 506292da949f6c87d6499425d64d37d7c5870ec57adEvan Cheng end = baseIndex; 507292da949f6c87d6499425d64d37d7c5870ec57adEvan Cheng } 50824a3cc4c83e5edb25fadf7b8979a26b4451795c6Evan Cheng } 50924a3cc4c83e5edb25fadf7b8979a26b4451795c6Evan Cheng 510f3bb2e65d12857f83b273f4ecab013680310bbbcEvan Cheng LiveRange LR(start, end, interval.getNextValue(start, 0, VNInfoAllocator)); 5119b25b8ca24d6df2e097741dcc15016772ee4eda7Jim Laskey interval.addRange(LR); 512f3bb2e65d12857f83b273f4ecab013680310bbbcEvan Cheng interval.addKill(LR.valno, end); 51324c2e5cf7e926452ea5875d027ec0d24d9c19e39Evan Cheng DOUT << " +" << LR << '\n'; 514b371f457b0ea4a652a9f526ba4375c80ae542252Evan Cheng} 515b371f457b0ea4a652a9f526ba4375c80ae542252Evan Cheng 516ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos/// computeIntervals - computes the live intervals for virtual 5174d46e1e521c0df1990ea50f8146d22bd77ea71a6Alkis Evlogimenos/// registers. for some ordering of the machine instructions [1,N] a 51808cec00588ec1a8fa85b208555f006d7396ae7a4Alkis Evlogimenos/// live interval is an interval [i, j) where 1 <= i <= j < N for 519ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos/// which a variable is live 520f7da2c7b0c6293c268881628fc351bed7763f1f4Chris Lattnervoid LiveIntervals::computeIntervals() { 521bdc679d564e67a81792e463f6614b0088f975025Bill Wendling DOUT << "********** COMPUTING LIVE INTERVALS **********\n" 522bdc679d564e67a81792e463f6614b0088f975025Bill Wendling << "********** Function: " 523bdc679d564e67a81792e463f6614b0088f975025Bill Wendling << ((Value*)mf_->getFunction())->getName() << '\n'; 5246b128bdc58a496e9f08e4d09416330320761baffChris Lattner // Track the index of the current machine instr. 5256b128bdc58a496e9f08e4d09416330320761baffChris Lattner unsigned MIIndex = 0; 526428b92eb83b457b71d29d1d4b7900d36a0ce9a53Chris Lattner for (MachineFunction::iterator MBBI = mf_->begin(), E = mf_->end(); 527428b92eb83b457b71d29d1d4b7900d36a0ce9a53Chris Lattner MBBI != E; ++MBBI) { 528428b92eb83b457b71d29d1d4b7900d36a0ce9a53Chris Lattner MachineBasicBlock *MBB = MBBI; 529bdc679d564e67a81792e463f6614b0088f975025Bill Wendling DOUT << ((Value*)MBB->getBasicBlock())->getName() << ":\n"; 5301a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos 531428b92eb83b457b71d29d1d4b7900d36a0ce9a53Chris Lattner MachineBasicBlock::iterator MI = MBB->begin(), miEnd = MBB->end(); 5320c9f92e1ff64ee56724eae444a0442b02f83d0a8Evan Cheng 533cb406c25973b4e88a6c10ad839ef1beeb3664715Dan Gohman // Create intervals for live-ins to this BB first. 534cb406c25973b4e88a6c10ad839ef1beeb3664715Dan Gohman for (MachineBasicBlock::const_livein_iterator LI = MBB->livein_begin(), 535cb406c25973b4e88a6c10ad839ef1beeb3664715Dan Gohman LE = MBB->livein_end(); LI != LE; ++LI) { 536cb406c25973b4e88a6c10ad839ef1beeb3664715Dan Gohman handleLiveInRegister(MBB, MIIndex, getOrCreateInterval(*LI)); 537cb406c25973b4e88a6c10ad839ef1beeb3664715Dan Gohman // Multiple live-ins can alias the same register. 5386f0d024a534af18d9e60b3ea757376cd8a3a980eDan Gohman for (const unsigned* AS = tri_->getSubRegisters(*LI); *AS; ++AS) 539cb406c25973b4e88a6c10ad839ef1beeb3664715Dan Gohman if (!hasInterval(*AS)) 540cb406c25973b4e88a6c10ad839ef1beeb3664715Dan Gohman handleLiveInRegister(MBB, MIIndex, getOrCreateInterval(*AS), 541cb406c25973b4e88a6c10ad839ef1beeb3664715Dan Gohman true); 542dffb2e83ed2546226d09c40aa43524e2392322daChris Lattner } 543dffb2e83ed2546226d09c40aa43524e2392322daChris Lattner 544428b92eb83b457b71d29d1d4b7900d36a0ce9a53Chris Lattner for (; MI != miEnd; ++MI) { 545bdc679d564e67a81792e463f6614b0088f975025Bill Wendling DOUT << MIIndex << "\t" << *MI; 5461a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos 547438f7bc67cf235ccee7e6f7ac7f4ae2186eb8020Evan Cheng // Handle defs. 548428b92eb83b457b71d29d1d4b7900d36a0ce9a53Chris Lattner for (int i = MI->getNumOperands() - 1; i >= 0; --i) { 549428b92eb83b457b71d29d1d4b7900d36a0ce9a53Chris Lattner MachineOperand &MO = MI->getOperand(i); 5501a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // handle register defs - build intervals 551428b92eb83b457b71d29d1d4b7900d36a0ce9a53Chris Lattner if (MO.isRegister() && MO.getReg() && MO.isDef()) 552428b92eb83b457b71d29d1d4b7900d36a0ce9a53Chris Lattner handleRegisterDef(MBB, MI, MIIndex, MO.getReg()); 5531a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos } 5546b128bdc58a496e9f08e4d09416330320761baffChris Lattner 5556b128bdc58a496e9f08e4d09416330320761baffChris Lattner MIIndex += InstrSlots::NUM; 556ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos } 5571a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos } 558ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos} 559b27ef248f579b354aab434f63c417ab1103e47e2Alkis Evlogimenos 5604ca980e7f9ce7b78955307c2d07001a24d3b6befEvan Chengbool LiveIntervals::findLiveInMBBs(const LiveRange &LR, 561a5bfc97da713ec9e185226d44e6adb4d3087b304Evan Cheng SmallVectorImpl<MachineBasicBlock*> &MBBs) const { 5624ca980e7f9ce7b78955307c2d07001a24d3b6befEvan Cheng std::vector<IdxMBBPair>::const_iterator I = 5634ca980e7f9ce7b78955307c2d07001a24d3b6befEvan Cheng std::lower_bound(Idx2MBBMap.begin(), Idx2MBBMap.end(), LR.start); 5644ca980e7f9ce7b78955307c2d07001a24d3b6befEvan Cheng 5654ca980e7f9ce7b78955307c2d07001a24d3b6befEvan Cheng bool ResVal = false; 5664ca980e7f9ce7b78955307c2d07001a24d3b6befEvan Cheng while (I != Idx2MBBMap.end()) { 5674ca980e7f9ce7b78955307c2d07001a24d3b6befEvan Cheng if (LR.end <= I->first) 5684ca980e7f9ce7b78955307c2d07001a24d3b6befEvan Cheng break; 5694ca980e7f9ce7b78955307c2d07001a24d3b6befEvan Cheng MBBs.push_back(I->second); 5704ca980e7f9ce7b78955307c2d07001a24d3b6befEvan Cheng ResVal = true; 5714ca980e7f9ce7b78955307c2d07001a24d3b6befEvan Cheng ++I; 5724ca980e7f9ce7b78955307c2d07001a24d3b6befEvan Cheng } 5734ca980e7f9ce7b78955307c2d07001a24d3b6befEvan Cheng return ResVal; 5744ca980e7f9ce7b78955307c2d07001a24d3b6befEvan Cheng} 5754ca980e7f9ce7b78955307c2d07001a24d3b6befEvan Cheng 5764ca980e7f9ce7b78955307c2d07001a24d3b6befEvan Cheng 577a1613db62fec94845aa8306232fb665273615badAlkis EvlogimenosLiveInterval LiveIntervals::createInterval(unsigned reg) { 5786f0d024a534af18d9e60b3ea757376cd8a3a980eDan Gohman float Weight = TargetRegisterInfo::isPhysicalRegister(reg) ? 5797902c75331fa8f38fc8380f5573d935c0d149ef5Jim Laskey HUGE_VALF : 0.0F; 580a1613db62fec94845aa8306232fb665273615badAlkis Evlogimenos return LiveInterval(reg, Weight); 5819a8b490735d216435862a3d52e669357f165550fAlkis Evlogimenos} 582f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng 583c8d044e4f779fdcfc5e7d592927740fd8f672a70Evan Cheng/// getVNInfoSourceReg - Helper function that parses the specified VNInfo 584c8d044e4f779fdcfc5e7d592927740fd8f672a70Evan Cheng/// copy field and returns the source register that defines it. 585c8d044e4f779fdcfc5e7d592927740fd8f672a70Evan Chengunsigned LiveIntervals::getVNInfoSourceReg(const VNInfo *VNI) const { 586c8d044e4f779fdcfc5e7d592927740fd8f672a70Evan Cheng if (!VNI->copy) 587c8d044e4f779fdcfc5e7d592927740fd8f672a70Evan Cheng return 0; 588c8d044e4f779fdcfc5e7d592927740fd8f672a70Evan Cheng 589c8d044e4f779fdcfc5e7d592927740fd8f672a70Evan Cheng if (VNI->copy->getOpcode() == TargetInstrInfo::EXTRACT_SUBREG) 590c8d044e4f779fdcfc5e7d592927740fd8f672a70Evan Cheng return VNI->copy->getOperand(1).getReg(); 591c8d044e4f779fdcfc5e7d592927740fd8f672a70Evan Cheng unsigned SrcReg, DstReg; 592c8d044e4f779fdcfc5e7d592927740fd8f672a70Evan Cheng if (tii_->isMoveInstr(*VNI->copy, SrcReg, DstReg)) 593c8d044e4f779fdcfc5e7d592927740fd8f672a70Evan Cheng return SrcReg; 594c8d044e4f779fdcfc5e7d592927740fd8f672a70Evan Cheng assert(0 && "Unrecognized copy instruction!"); 595c8d044e4f779fdcfc5e7d592927740fd8f672a70Evan Cheng return 0; 596c8d044e4f779fdcfc5e7d592927740fd8f672a70Evan Cheng} 597f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng 598f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng//===----------------------------------------------------------------------===// 599f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng// Register allocator hooks. 600f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng// 601f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng 602d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng/// getReMatImplicitUse - If the remat definition MI has one (for now, we only 603d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng/// allow one) virtual register operand, then its uses are implicitly using 604d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng/// the register. Returns the virtual register. 605d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Chengunsigned LiveIntervals::getReMatImplicitUse(const LiveInterval &li, 606d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng MachineInstr *MI) const { 607d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng unsigned RegOp = 0; 608d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) { 609d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng MachineOperand &MO = MI->getOperand(i); 610d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng if (!MO.isRegister() || !MO.isUse()) 611d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng continue; 612d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng unsigned Reg = MO.getReg(); 613d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng if (Reg == 0 || Reg == li.reg) 614d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng continue; 615d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng // FIXME: For now, only remat MI with at most one register operand. 616d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng assert(!RegOp && 617d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng "Can't rematerialize instruction with multiple register operand!"); 618d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng RegOp = MO.getReg(); 619d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng break; 620d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng } 621d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng return RegOp; 622d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng} 623d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng 624d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng/// isValNoAvailableAt - Return true if the val# of the specified interval 625d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng/// which reaches the given instruction also reaches the specified use index. 626d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Chengbool LiveIntervals::isValNoAvailableAt(const LiveInterval &li, MachineInstr *MI, 627d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng unsigned UseIdx) const { 628d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng unsigned Index = getInstructionIndex(MI); 629d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng VNInfo *ValNo = li.FindLiveRangeContaining(Index)->valno; 630d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng LiveInterval::const_iterator UI = li.FindLiveRangeContaining(UseIdx); 631d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng return UI != li.end() && UI->valno == ValNo; 632d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng} 633d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng 634f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng/// isReMaterializable - Returns true if the definition MI of the specified 635f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng/// val# of the specified interval is re-materializable. 636f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Chengbool LiveIntervals::isReMaterializable(const LiveInterval &li, 6375ef3a04b542c4e585276768fa9ca2af698ef5c87Evan Cheng const VNInfo *ValNo, MachineInstr *MI, 6385ef3a04b542c4e585276768fa9ca2af698ef5c87Evan Cheng bool &isLoad) { 639f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng if (DisableReMat) 640f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng return false; 641f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng 6425ef3a04b542c4e585276768fa9ca2af698ef5c87Evan Cheng isLoad = false; 643749c6f6b5ed301c84aac562e414486549d7b98ebChris Lattner const TargetInstrDesc &TID = MI->getDesc(); 644d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng if (TID.isImplicitDef()) 645d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng return true; 646d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng if (tii_->isTriviallyReMaterializable(MI)) { 647749c6f6b5ed301c84aac562e414486549d7b98ebChris Lattner isLoad = TID.isSimpleLoad(); 648d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng 649d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng unsigned ImpUse = getReMatImplicitUse(li, MI); 650d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng if (ImpUse) { 651d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng const LiveInterval &ImpLi = getInterval(ImpUse); 652d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng for (MachineRegisterInfo::use_iterator ri = mri_->use_begin(li.reg), 653d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng re = mri_->use_end(); ri != re; ++ri) { 654d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng MachineInstr *UseMI = &*ri; 655d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng unsigned UseIdx = getInstructionIndex(UseMI); 656d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng if (li.FindLiveRangeContaining(UseIdx)->valno != ValNo) 657d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng continue; 658d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng if (!canFoldMemoryOperand(UseMI, li.reg) && 659d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng !isValNoAvailableAt(ImpLi, MI, UseIdx)) 660d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng return false; 661d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng } 662d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng } 663f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng return true; 6645ef3a04b542c4e585276768fa9ca2af698ef5c87Evan Cheng } 665f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng 666f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng int FrameIdx = 0; 667f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng if (!tii_->isLoadFromStackSlot(MI, FrameIdx) || 6688480293f41c11c22762164449e41cd3adb0dd7d8Evan Cheng !mf_->getFrameInfo()->isImmutableObjectIndex(FrameIdx)) 669f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng return false; 670f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng 671f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng // This is a load from fixed stack slot. It can be rematerialized unless it's 672f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng // re-defined by a two-address instruction. 6735ef3a04b542c4e585276768fa9ca2af698ef5c87Evan Cheng isLoad = true; 674f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng for (LiveInterval::const_vni_iterator i = li.vni_begin(), e = li.vni_end(); 675f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng i != e; ++i) { 676f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng const VNInfo *VNI = *i; 677f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng if (VNI == ValNo) 678f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng continue; 679f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng unsigned DefIdx = VNI->def; 680f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng if (DefIdx == ~1U) 681f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng continue; // Dead val#. 682f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng MachineInstr *DefMI = (DefIdx == ~0u) 683f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng ? NULL : getInstructionFromIndex(DefIdx); 6845ef3a04b542c4e585276768fa9ca2af698ef5c87Evan Cheng if (DefMI && DefMI->isRegReDefinedByTwoAddr(li.reg)) { 6855ef3a04b542c4e585276768fa9ca2af698ef5c87Evan Cheng isLoad = false; 6865ef3a04b542c4e585276768fa9ca2af698ef5c87Evan Cheng return false; 6875ef3a04b542c4e585276768fa9ca2af698ef5c87Evan Cheng } 6885ef3a04b542c4e585276768fa9ca2af698ef5c87Evan Cheng } 6895ef3a04b542c4e585276768fa9ca2af698ef5c87Evan Cheng return true; 6905ef3a04b542c4e585276768fa9ca2af698ef5c87Evan Cheng} 6915ef3a04b542c4e585276768fa9ca2af698ef5c87Evan Cheng 6925ef3a04b542c4e585276768fa9ca2af698ef5c87Evan Cheng/// isReMaterializable - Returns true if every definition of MI of every 6935ef3a04b542c4e585276768fa9ca2af698ef5c87Evan Cheng/// val# of the specified interval is re-materializable. 6945ef3a04b542c4e585276768fa9ca2af698ef5c87Evan Chengbool LiveIntervals::isReMaterializable(const LiveInterval &li, bool &isLoad) { 6955ef3a04b542c4e585276768fa9ca2af698ef5c87Evan Cheng isLoad = false; 6965ef3a04b542c4e585276768fa9ca2af698ef5c87Evan Cheng for (LiveInterval::const_vni_iterator i = li.vni_begin(), e = li.vni_end(); 6975ef3a04b542c4e585276768fa9ca2af698ef5c87Evan Cheng i != e; ++i) { 6985ef3a04b542c4e585276768fa9ca2af698ef5c87Evan Cheng const VNInfo *VNI = *i; 6995ef3a04b542c4e585276768fa9ca2af698ef5c87Evan Cheng unsigned DefIdx = VNI->def; 7005ef3a04b542c4e585276768fa9ca2af698ef5c87Evan Cheng if (DefIdx == ~1U) 7015ef3a04b542c4e585276768fa9ca2af698ef5c87Evan Cheng continue; // Dead val#. 7025ef3a04b542c4e585276768fa9ca2af698ef5c87Evan Cheng // Is the def for the val# rematerializable? 7035ef3a04b542c4e585276768fa9ca2af698ef5c87Evan Cheng if (DefIdx == ~0u) 7045ef3a04b542c4e585276768fa9ca2af698ef5c87Evan Cheng return false; 7055ef3a04b542c4e585276768fa9ca2af698ef5c87Evan Cheng MachineInstr *ReMatDefMI = getInstructionFromIndex(DefIdx); 7065ef3a04b542c4e585276768fa9ca2af698ef5c87Evan Cheng bool DefIsLoad = false; 707d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng if (!ReMatDefMI || 708d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng !isReMaterializable(li, VNI, ReMatDefMI, DefIsLoad)) 709f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng return false; 7105ef3a04b542c4e585276768fa9ca2af698ef5c87Evan Cheng isLoad |= DefIsLoad; 711f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng } 712f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng return true; 713f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng} 714f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng 715f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng/// tryFoldMemoryOperand - Attempts to fold either a spill / restore from 716f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng/// slot / to reg or any rematerialized load into ith operand of specified 717f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng/// MI. If it is successul, MI is updated with the newly created MI and 718f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng/// returns true. 71981a038218171860ee4c382849c647d3dc841fe8bEvan Chengbool LiveIntervals::tryFoldMemoryOperand(MachineInstr* &MI, 720cddbb83ea82e98658d9f530c50a7b9d23249afc2Evan Cheng VirtRegMap &vrm, MachineInstr *DefMI, 721aee4af68ae2016afc5b4ec0c430e539c5810a766Evan Cheng unsigned InstrIdx, 722aee4af68ae2016afc5b4ec0c430e539c5810a766Evan Cheng SmallVector<unsigned, 2> &Ops, 723cddbb83ea82e98658d9f530c50a7b9d23249afc2Evan Cheng bool isSS, int Slot, unsigned Reg) { 724aee4af68ae2016afc5b4ec0c430e539c5810a766Evan Cheng unsigned MRInfo = 0; 725749c6f6b5ed301c84aac562e414486549d7b98ebChris Lattner const TargetInstrDesc &TID = MI->getDesc(); 7266e141fd04897e5eb4925bb6351297170ebd8a756Evan Cheng // If it is an implicit def instruction, just delete it. 727749c6f6b5ed301c84aac562e414486549d7b98ebChris Lattner if (TID.isImplicitDef()) { 7286e141fd04897e5eb4925bb6351297170ebd8a756Evan Cheng RemoveMachineInstrFromMaps(MI); 7296e141fd04897e5eb4925bb6351297170ebd8a756Evan Cheng vrm.RemoveMachineInstrFromMaps(MI); 7306e141fd04897e5eb4925bb6351297170ebd8a756Evan Cheng MI->eraseFromParent(); 7316e141fd04897e5eb4925bb6351297170ebd8a756Evan Cheng ++numFolds; 7326e141fd04897e5eb4925bb6351297170ebd8a756Evan Cheng return true; 7336e141fd04897e5eb4925bb6351297170ebd8a756Evan Cheng } 7346e141fd04897e5eb4925bb6351297170ebd8a756Evan Cheng 735aee4af68ae2016afc5b4ec0c430e539c5810a766Evan Cheng SmallVector<unsigned, 2> FoldOps; 736aee4af68ae2016afc5b4ec0c430e539c5810a766Evan Cheng for (unsigned i = 0, e = Ops.size(); i != e; ++i) { 737aee4af68ae2016afc5b4ec0c430e539c5810a766Evan Cheng unsigned OpIdx = Ops[i]; 738d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng MachineOperand &MO = MI->getOperand(OpIdx); 739aee4af68ae2016afc5b4ec0c430e539c5810a766Evan Cheng // FIXME: fold subreg use. 740d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng if (MO.getSubReg()) 741e62f97c094dba44e4c259d20135167fa91912eeaEvan Cheng return false; 742d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng if (MO.isDef()) 743aee4af68ae2016afc5b4ec0c430e539c5810a766Evan Cheng MRInfo |= (unsigned)VirtRegMap::isMod; 744aee4af68ae2016afc5b4ec0c430e539c5810a766Evan Cheng else { 745aee4af68ae2016afc5b4ec0c430e539c5810a766Evan Cheng // Filter out two-address use operand(s). 746d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng if (!MO.isImplicit() && 747d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng TID.getOperandConstraint(OpIdx, TOI::TIED_TO) != -1) { 748aee4af68ae2016afc5b4ec0c430e539c5810a766Evan Cheng MRInfo = VirtRegMap::isModRef; 749aee4af68ae2016afc5b4ec0c430e539c5810a766Evan Cheng continue; 750aee4af68ae2016afc5b4ec0c430e539c5810a766Evan Cheng } 751aee4af68ae2016afc5b4ec0c430e539c5810a766Evan Cheng MRInfo |= (unsigned)VirtRegMap::isRef; 752aee4af68ae2016afc5b4ec0c430e539c5810a766Evan Cheng } 753aee4af68ae2016afc5b4ec0c430e539c5810a766Evan Cheng FoldOps.push_back(OpIdx); 754e62f97c094dba44e4c259d20135167fa91912eeaEvan Cheng } 755cddbb83ea82e98658d9f530c50a7b9d23249afc2Evan Cheng 756f2f8c2ae07b7d9bdbf1b89781c573c7af2bd5e1bEvan Cheng MachineInstr *fmi = isSS ? tii_->foldMemoryOperand(*mf_, MI, FoldOps, Slot) 757f2f8c2ae07b7d9bdbf1b89781c573c7af2bd5e1bEvan Cheng : tii_->foldMemoryOperand(*mf_, MI, FoldOps, DefMI); 758f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng if (fmi) { 759f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng // Attempt to fold the memory reference into the instruction. If 760f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng // we can do this, we don't need to insert spill code. 761f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng if (lv_) 762f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng lv_->instructionChanged(MI, fmi); 76381a038218171860ee4c382849c647d3dc841fe8bEvan Cheng else 7646f0d024a534af18d9e60b3ea757376cd8a3a980eDan Gohman fmi->copyKillDeadInfo(MI, tri_); 765f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng MachineBasicBlock &MBB = *MI->getParent(); 7668480293f41c11c22762164449e41cd3adb0dd7d8Evan Cheng if (isSS && !mf_->getFrameInfo()->isImmutableObjectIndex(Slot)) 767aee4af68ae2016afc5b4ec0c430e539c5810a766Evan Cheng vrm.virtFolded(Reg, MI, fmi, (VirtRegMap::ModRef)MRInfo); 76881a038218171860ee4c382849c647d3dc841fe8bEvan Cheng vrm.transferSpillPts(MI, fmi); 7690cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng vrm.transferRestorePts(MI, fmi); 770f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng mi2iMap_.erase(MI); 771cddbb83ea82e98658d9f530c50a7b9d23249afc2Evan Cheng i2miMap_[InstrIdx /InstrSlots::NUM] = fmi; 772cddbb83ea82e98658d9f530c50a7b9d23249afc2Evan Cheng mi2iMap_[fmi] = InstrIdx; 773f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng MI = MBB.insert(MBB.erase(MI), fmi); 7740cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng ++numFolds; 775f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng return true; 776f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng } 777f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng return false; 778f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng} 779f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng 780018f9b020bb12b731b0a7081578e5f82fb35092dEvan Cheng/// canFoldMemoryOperand - Returns true if the specified load / store 781018f9b020bb12b731b0a7081578e5f82fb35092dEvan Cheng/// folding is possible. 782018f9b020bb12b731b0a7081578e5f82fb35092dEvan Chengbool LiveIntervals::canFoldMemoryOperand(MachineInstr *MI, 783018f9b020bb12b731b0a7081578e5f82fb35092dEvan Cheng SmallVector<unsigned, 2> &Ops) const { 784018f9b020bb12b731b0a7081578e5f82fb35092dEvan Cheng SmallVector<unsigned, 2> FoldOps; 785018f9b020bb12b731b0a7081578e5f82fb35092dEvan Cheng for (unsigned i = 0, e = Ops.size(); i != e; ++i) { 786018f9b020bb12b731b0a7081578e5f82fb35092dEvan Cheng unsigned OpIdx = Ops[i]; 787018f9b020bb12b731b0a7081578e5f82fb35092dEvan Cheng // FIXME: fold subreg use. 788018f9b020bb12b731b0a7081578e5f82fb35092dEvan Cheng if (MI->getOperand(OpIdx).getSubReg()) 789018f9b020bb12b731b0a7081578e5f82fb35092dEvan Cheng return false; 790018f9b020bb12b731b0a7081578e5f82fb35092dEvan Cheng FoldOps.push_back(OpIdx); 791018f9b020bb12b731b0a7081578e5f82fb35092dEvan Cheng } 792018f9b020bb12b731b0a7081578e5f82fb35092dEvan Cheng 7936425f8be7263e625c2d7484eb2fb8f6643824f49Owen Anderson return tii_->canFoldMemoryOperand(MI, FoldOps); 794018f9b020bb12b731b0a7081578e5f82fb35092dEvan Cheng} 795018f9b020bb12b731b0a7081578e5f82fb35092dEvan Cheng 796d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Chengbool LiveIntervals::canFoldMemoryOperand(MachineInstr *MI, unsigned Reg) const { 797d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng SmallVector<unsigned, 2> FoldOps; 798d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) { 799d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng MachineOperand& mop = MI->getOperand(i); 800d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng if (!mop.isRegister()) 801d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng continue; 802d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng unsigned UseReg = mop.getReg(); 803d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng if (UseReg != Reg) 804d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng continue; 805d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng // FIXME: fold subreg use. 806d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng if (mop.getSubReg()) 807d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng return false; 808d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng FoldOps.push_back(i); 809d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng } 810d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng return tii_->canFoldMemoryOperand(MI, FoldOps); 811d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng} 812d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng 81381a038218171860ee4c382849c647d3dc841fe8bEvan Chengbool LiveIntervals::intervalIsInOneMBB(const LiveInterval &li) const { 81481a038218171860ee4c382849c647d3dc841fe8bEvan Cheng SmallPtrSet<MachineBasicBlock*, 4> MBBs; 81581a038218171860ee4c382849c647d3dc841fe8bEvan Cheng for (LiveInterval::Ranges::const_iterator 81681a038218171860ee4c382849c647d3dc841fe8bEvan Cheng I = li.ranges.begin(), E = li.ranges.end(); I != E; ++I) { 81781a038218171860ee4c382849c647d3dc841fe8bEvan Cheng std::vector<IdxMBBPair>::const_iterator II = 81881a038218171860ee4c382849c647d3dc841fe8bEvan Cheng std::lower_bound(Idx2MBBMap.begin(), Idx2MBBMap.end(), I->start); 81981a038218171860ee4c382849c647d3dc841fe8bEvan Cheng if (II == Idx2MBBMap.end()) 82081a038218171860ee4c382849c647d3dc841fe8bEvan Cheng continue; 82181a038218171860ee4c382849c647d3dc841fe8bEvan Cheng if (I->end > II->first) // crossing a MBB. 82281a038218171860ee4c382849c647d3dc841fe8bEvan Cheng return false; 82381a038218171860ee4c382849c647d3dc841fe8bEvan Cheng MBBs.insert(II->second); 82481a038218171860ee4c382849c647d3dc841fe8bEvan Cheng if (MBBs.size() > 1) 82581a038218171860ee4c382849c647d3dc841fe8bEvan Cheng return false; 82681a038218171860ee4c382849c647d3dc841fe8bEvan Cheng } 82781a038218171860ee4c382849c647d3dc841fe8bEvan Cheng return true; 82881a038218171860ee4c382849c647d3dc841fe8bEvan Cheng} 82981a038218171860ee4c382849c647d3dc841fe8bEvan Cheng 830d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng/// rewriteImplicitOps - Rewrite implicit use operands of MI (i.e. uses of 831d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng/// interval on to-be re-materialized operands of MI) with new register. 832d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Chengvoid LiveIntervals::rewriteImplicitOps(const LiveInterval &li, 833d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng MachineInstr *MI, unsigned NewVReg, 834d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng VirtRegMap &vrm) { 835d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng // There is an implicit use. That means one of the other operand is 836d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng // being remat'ed and the remat'ed instruction has li.reg as an 837d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng // use operand. Make sure we rewrite that as well. 838d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) { 839d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng MachineOperand &MO = MI->getOperand(i); 840d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng if (!MO.isRegister()) 841d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng continue; 842d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng unsigned Reg = MO.getReg(); 843d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng if (Reg == 0 || TargetRegisterInfo::isPhysicalRegister(Reg)) 844d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng continue; 845d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng if (!vrm.isReMaterialized(Reg)) 846d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng continue; 847d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng MachineInstr *ReMatMI = vrm.getReMaterializedMI(Reg); 848d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng int OpIdx = ReMatMI->findRegisterUseOperandIdx(li.reg); 849d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng if (OpIdx != -1) 850d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng ReMatMI->getOperand(OpIdx).setReg(NewVReg); 851d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng } 852d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng} 853d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng 854f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng/// rewriteInstructionForSpills, rewriteInstructionsForSpills - Helper functions 855f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng/// for addIntervalsForSpills to rewrite uses / defs for the given live range. 856018f9b020bb12b731b0a7081578e5f82fb35092dEvan Chengbool LiveIntervals:: 857d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan ChengrewriteInstructionForSpills(const LiveInterval &li, const VNInfo *VNI, 858d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng bool TrySplit, unsigned index, unsigned end, MachineInstr *MI, 85981a038218171860ee4c382849c647d3dc841fe8bEvan Cheng MachineInstr *ReMatOrigDefMI, MachineInstr *ReMatDefMI, 860f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng unsigned Slot, int LdSlot, 861f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng bool isLoad, bool isLoadSS, bool DefIsReMat, bool CanDelete, 862d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng VirtRegMap &vrm, 863f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng const TargetRegisterClass* rc, 864f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng SmallVector<int, 4> &ReMatIds, 86522f07ffd27d1d721634d502c37267721d2e025cfEvan Cheng const MachineLoopInfo *loopInfo, 866d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng unsigned &NewVReg, bool &HasDef, bool &HasUse, 8671953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng std::map<unsigned,unsigned> &MBBVRegsMap, 868f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng std::vector<LiveInterval*> &NewLIs) { 869018f9b020bb12b731b0a7081578e5f82fb35092dEvan Cheng bool CanFold = false; 870f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng RestartInstruction: 871f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng for (unsigned i = 0; i != MI->getNumOperands(); ++i) { 872f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng MachineOperand& mop = MI->getOperand(i); 873f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng if (!mop.isRegister()) 874f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng continue; 875f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng unsigned Reg = mop.getReg(); 876f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng unsigned RegI = Reg; 8776f0d024a534af18d9e60b3ea757376cd8a3a980eDan Gohman if (Reg == 0 || TargetRegisterInfo::isPhysicalRegister(Reg)) 878f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng continue; 879f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng if (Reg != li.reg) 880f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng continue; 881f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng 882f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng bool TryFold = !DefIsReMat; 883cb3c330d39442130d0587208d673ce9c33c7008fEvan Cheng bool FoldSS = true; // Default behavior unless it's a remat. 884f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng int FoldSlot = Slot; 885f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng if (DefIsReMat) { 886f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng // If this is the rematerializable definition MI itself and 887f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng // all of its uses are rematerialized, simply delete it. 88881a038218171860ee4c382849c647d3dc841fe8bEvan Cheng if (MI == ReMatOrigDefMI && CanDelete) { 889cddbb83ea82e98658d9f530c50a7b9d23249afc2Evan Cheng DOUT << "\t\t\t\tErasing re-materlizable def: "; 890cddbb83ea82e98658d9f530c50a7b9d23249afc2Evan Cheng DOUT << MI << '\n'; 891d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng unsigned ImpUse = getReMatImplicitUse(li, MI); 892d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng if (ImpUse) { 893d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng // To be deleted MI has a virtual register operand, update the 894d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng // spill weight of the register interval. 895d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng unsigned loopDepth = loopInfo->getLoopDepth(MI->getParent()); 896d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng LiveInterval &ImpLi = getInterval(ImpUse); 897d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng ImpLi.weight -= getSpillWeight(false, true, loopDepth); 898d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng } 899f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng RemoveMachineInstrFromMaps(MI); 900cada245d06959831b90f8c29f92e77beda4b71cbEvan Cheng vrm.RemoveMachineInstrFromMaps(MI); 901f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng MI->eraseFromParent(); 902f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng break; 903f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng } 904f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng 905f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng // If def for this use can't be rematerialized, then try folding. 9060cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng // If def is rematerializable and it's a load, also try folding. 907cb3c330d39442130d0587208d673ce9c33c7008fEvan Cheng TryFold = !ReMatDefMI || (ReMatDefMI && (MI == ReMatOrigDefMI || isLoad)); 908f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng if (isLoad) { 909f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng // Try fold loads (from stack slot, constant pool, etc.) into uses. 910f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng FoldSS = isLoadSS; 911f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng FoldSlot = LdSlot; 912f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng } 913f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng } 914f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng 915f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng // Scan all of the operands of this instruction rewriting operands 916f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng // to use NewVReg instead of li.reg as appropriate. We do this for 917f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng // two reasons: 918f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng // 919f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng // 1. If the instr reads the same spilled vreg multiple times, we 920f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng // want to reuse the NewVReg. 921f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng // 2. If the instr is a two-addr instruction, we are required to 922f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng // keep the src/dst regs pinned. 923f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng // 924f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng // Keep track of whether we replace a use and/or def so that we can 925f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng // create the spill interval with the appropriate range. 926cddbb83ea82e98658d9f530c50a7b9d23249afc2Evan Cheng 92781a038218171860ee4c382849c647d3dc841fe8bEvan Cheng HasUse = mop.isUse(); 92881a038218171860ee4c382849c647d3dc841fe8bEvan Cheng HasDef = mop.isDef(); 929aee4af68ae2016afc5b4ec0c430e539c5810a766Evan Cheng SmallVector<unsigned, 2> Ops; 930aee4af68ae2016afc5b4ec0c430e539c5810a766Evan Cheng Ops.push_back(i); 931f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng for (unsigned j = i+1, e = MI->getNumOperands(); j != e; ++j) { 932aee4af68ae2016afc5b4ec0c430e539c5810a766Evan Cheng const MachineOperand &MOj = MI->getOperand(j); 933aee4af68ae2016afc5b4ec0c430e539c5810a766Evan Cheng if (!MOj.isRegister()) 934f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng continue; 935aee4af68ae2016afc5b4ec0c430e539c5810a766Evan Cheng unsigned RegJ = MOj.getReg(); 9366f0d024a534af18d9e60b3ea757376cd8a3a980eDan Gohman if (RegJ == 0 || TargetRegisterInfo::isPhysicalRegister(RegJ)) 937f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng continue; 938f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng if (RegJ == RegI) { 939aee4af68ae2016afc5b4ec0c430e539c5810a766Evan Cheng Ops.push_back(j); 940aee4af68ae2016afc5b4ec0c430e539c5810a766Evan Cheng HasUse |= MOj.isUse(); 941aee4af68ae2016afc5b4ec0c430e539c5810a766Evan Cheng HasDef |= MOj.isDef(); 942f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng } 943f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng } 944f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng 945018f9b020bb12b731b0a7081578e5f82fb35092dEvan Cheng if (TryFold) { 946018f9b020bb12b731b0a7081578e5f82fb35092dEvan Cheng // Do not fold load / store here if we are splitting. We'll find an 947018f9b020bb12b731b0a7081578e5f82fb35092dEvan Cheng // optimal point to insert a load / store later. 948018f9b020bb12b731b0a7081578e5f82fb35092dEvan Cheng if (!TrySplit) { 949018f9b020bb12b731b0a7081578e5f82fb35092dEvan Cheng if (tryFoldMemoryOperand(MI, vrm, ReMatDefMI, index, 950018f9b020bb12b731b0a7081578e5f82fb35092dEvan Cheng Ops, FoldSS, FoldSlot, Reg)) { 951018f9b020bb12b731b0a7081578e5f82fb35092dEvan Cheng // Folding the load/store can completely change the instruction in 952018f9b020bb12b731b0a7081578e5f82fb35092dEvan Cheng // unpredictable ways, rescan it from the beginning. 953018f9b020bb12b731b0a7081578e5f82fb35092dEvan Cheng HasUse = false; 954018f9b020bb12b731b0a7081578e5f82fb35092dEvan Cheng HasDef = false; 955018f9b020bb12b731b0a7081578e5f82fb35092dEvan Cheng CanFold = false; 956018f9b020bb12b731b0a7081578e5f82fb35092dEvan Cheng goto RestartInstruction; 957018f9b020bb12b731b0a7081578e5f82fb35092dEvan Cheng } 958018f9b020bb12b731b0a7081578e5f82fb35092dEvan Cheng } else { 959018f9b020bb12b731b0a7081578e5f82fb35092dEvan Cheng CanFold = canFoldMemoryOperand(MI, Ops); 960018f9b020bb12b731b0a7081578e5f82fb35092dEvan Cheng } 9616e141fd04897e5eb4925bb6351297170ebd8a756Evan Cheng } else 9626e141fd04897e5eb4925bb6351297170ebd8a756Evan Cheng CanFold = false; 963cddbb83ea82e98658d9f530c50a7b9d23249afc2Evan Cheng 964cddbb83ea82e98658d9f530c50a7b9d23249afc2Evan Cheng // Create a new virtual register for the spill interval. 965cddbb83ea82e98658d9f530c50a7b9d23249afc2Evan Cheng bool CreatedNewVReg = false; 966cddbb83ea82e98658d9f530c50a7b9d23249afc2Evan Cheng if (NewVReg == 0) { 967d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng NewVReg = mri_->createVirtualRegister(rc); 968cddbb83ea82e98658d9f530c50a7b9d23249afc2Evan Cheng vrm.grow(); 969cddbb83ea82e98658d9f530c50a7b9d23249afc2Evan Cheng CreatedNewVReg = true; 970cddbb83ea82e98658d9f530c50a7b9d23249afc2Evan Cheng } 971cddbb83ea82e98658d9f530c50a7b9d23249afc2Evan Cheng mop.setReg(NewVReg); 972d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng if (mop.isImplicit()) 973d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng rewriteImplicitOps(li, MI, NewVReg, vrm); 974cddbb83ea82e98658d9f530c50a7b9d23249afc2Evan Cheng 975cddbb83ea82e98658d9f530c50a7b9d23249afc2Evan Cheng // Reuse NewVReg for other reads. 976d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng for (unsigned j = 0, e = Ops.size(); j != e; ++j) { 977d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng MachineOperand &mopj = MI->getOperand(Ops[j]); 978d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng mopj.setReg(NewVReg); 979d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng if (mopj.isImplicit()) 980d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng rewriteImplicitOps(li, MI, NewVReg, vrm); 981d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng } 982cddbb83ea82e98658d9f530c50a7b9d23249afc2Evan Cheng 98381a038218171860ee4c382849c647d3dc841fe8bEvan Cheng if (CreatedNewVReg) { 98481a038218171860ee4c382849c647d3dc841fe8bEvan Cheng if (DefIsReMat) { 985d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng unsigned ImpUse = getReMatImplicitUse(li, ReMatDefMI); 986d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng if (ImpUse) { 987d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng // Re-matting an instruction with virtual register use. Add the 988d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng // register as an implicit use on the use MI and update the register 989d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng // interval's spill weight. 990d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng unsigned loopDepth = loopInfo->getLoopDepth(MI->getParent()); 991d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng LiveInterval &ImpLi = getInterval(ImpUse); 992d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng ImpLi.weight += getSpillWeight(false, true, loopDepth); 993d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng MI->addOperand(MachineOperand::CreateReg(ImpUse, false, true)); 994d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng } 99581a038218171860ee4c382849c647d3dc841fe8bEvan Cheng vrm.setVirtIsReMaterialized(NewVReg, ReMatDefMI/*, CanDelete*/); 996d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng if (ReMatIds[VNI->id] == VirtRegMap::MAX_STACK_SLOT) { 99781a038218171860ee4c382849c647d3dc841fe8bEvan Cheng // Each valnum may have its own remat id. 998d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng ReMatIds[VNI->id] = vrm.assignVirtReMatId(NewVReg); 99981a038218171860ee4c382849c647d3dc841fe8bEvan Cheng } else { 1000d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng vrm.assignVirtReMatId(NewVReg, ReMatIds[VNI->id]); 100181a038218171860ee4c382849c647d3dc841fe8bEvan Cheng } 100281a038218171860ee4c382849c647d3dc841fe8bEvan Cheng if (!CanDelete || (HasUse && HasDef)) { 100381a038218171860ee4c382849c647d3dc841fe8bEvan Cheng // If this is a two-addr instruction then its use operands are 100481a038218171860ee4c382849c647d3dc841fe8bEvan Cheng // rematerializable but its def is not. It should be assigned a 100581a038218171860ee4c382849c647d3dc841fe8bEvan Cheng // stack slot. 100681a038218171860ee4c382849c647d3dc841fe8bEvan Cheng vrm.assignVirt2StackSlot(NewVReg, Slot); 100781a038218171860ee4c382849c647d3dc841fe8bEvan Cheng } 1008f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng } else { 1009f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng vrm.assignVirt2StackSlot(NewVReg, Slot); 1010f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng } 1011cb3c330d39442130d0587208d673ce9c33c7008fEvan Cheng } else if (HasUse && HasDef && 1012cb3c330d39442130d0587208d673ce9c33c7008fEvan Cheng vrm.getStackSlot(NewVReg) == VirtRegMap::NO_STACK_SLOT) { 1013cb3c330d39442130d0587208d673ce9c33c7008fEvan Cheng // If this interval hasn't been assigned a stack slot (because earlier 1014cb3c330d39442130d0587208d673ce9c33c7008fEvan Cheng // def is a deleted remat def), do it now. 1015cb3c330d39442130d0587208d673ce9c33c7008fEvan Cheng assert(Slot != VirtRegMap::NO_STACK_SLOT); 1016cb3c330d39442130d0587208d673ce9c33c7008fEvan Cheng vrm.assignVirt2StackSlot(NewVReg, Slot); 1017f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng } 1018f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng 1019f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng // create a new register interval for this spill / remat. 1020f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng LiveInterval &nI = getOrCreateInterval(NewVReg); 102181a038218171860ee4c382849c647d3dc841fe8bEvan Cheng if (CreatedNewVReg) { 102281a038218171860ee4c382849c647d3dc841fe8bEvan Cheng NewLIs.push_back(&nI); 10231953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng MBBVRegsMap.insert(std::make_pair(MI->getParent()->getNumber(), NewVReg)); 102481a038218171860ee4c382849c647d3dc841fe8bEvan Cheng if (TrySplit) 102581a038218171860ee4c382849c647d3dc841fe8bEvan Cheng vrm.setIsSplitFromReg(NewVReg, li.reg); 102681a038218171860ee4c382849c647d3dc841fe8bEvan Cheng } 1027f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng 1028f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng if (HasUse) { 102981a038218171860ee4c382849c647d3dc841fe8bEvan Cheng if (CreatedNewVReg) { 103081a038218171860ee4c382849c647d3dc841fe8bEvan Cheng LiveRange LR(getLoadIndex(index), getUseIndex(index)+1, 103181a038218171860ee4c382849c647d3dc841fe8bEvan Cheng nI.getNextValue(~0U, 0, VNInfoAllocator)); 103281a038218171860ee4c382849c647d3dc841fe8bEvan Cheng DOUT << " +" << LR; 103381a038218171860ee4c382849c647d3dc841fe8bEvan Cheng nI.addRange(LR); 103481a038218171860ee4c382849c647d3dc841fe8bEvan Cheng } else { 103581a038218171860ee4c382849c647d3dc841fe8bEvan Cheng // Extend the split live interval to this def / use. 103681a038218171860ee4c382849c647d3dc841fe8bEvan Cheng unsigned End = getUseIndex(index)+1; 103781a038218171860ee4c382849c647d3dc841fe8bEvan Cheng LiveRange LR(nI.ranges[nI.ranges.size()-1].end, End, 103881a038218171860ee4c382849c647d3dc841fe8bEvan Cheng nI.getValNumInfo(nI.getNumValNums()-1)); 103981a038218171860ee4c382849c647d3dc841fe8bEvan Cheng DOUT << " +" << LR; 104081a038218171860ee4c382849c647d3dc841fe8bEvan Cheng nI.addRange(LR); 104181a038218171860ee4c382849c647d3dc841fe8bEvan Cheng } 1042f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng } 1043f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng if (HasDef) { 1044f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng LiveRange LR(getDefIndex(index), getStoreIndex(index), 1045f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng nI.getNextValue(~0U, 0, VNInfoAllocator)); 1046f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng DOUT << " +" << LR; 1047f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng nI.addRange(LR); 1048f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng } 104981a038218171860ee4c382849c647d3dc841fe8bEvan Cheng 1050f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng DOUT << "\t\t\t\tAdded new interval: "; 10516f0d024a534af18d9e60b3ea757376cd8a3a980eDan Gohman nI.print(DOUT, tri_); 1052f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng DOUT << '\n'; 1053f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng } 1054018f9b020bb12b731b0a7081578e5f82fb35092dEvan Cheng return CanFold; 1055f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng} 105681a038218171860ee4c382849c647d3dc841fe8bEvan Chengbool LiveIntervals::anyKillInMBBAfterIdx(const LiveInterval &li, 10570cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng const VNInfo *VNI, 10580cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng MachineBasicBlock *MBB, unsigned Idx) const { 105981a038218171860ee4c382849c647d3dc841fe8bEvan Cheng unsigned End = getMBBEndIdx(MBB); 10600cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng for (unsigned j = 0, ee = VNI->kills.size(); j != ee; ++j) { 10610cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng unsigned KillIdx = VNI->kills[j]; 10620cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng if (KillIdx > Idx && KillIdx < End) 10630cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng return true; 106481a038218171860ee4c382849c647d3dc841fe8bEvan Cheng } 106581a038218171860ee4c382849c647d3dc841fe8bEvan Cheng return false; 106681a038218171860ee4c382849c647d3dc841fe8bEvan Cheng} 106781a038218171860ee4c382849c647d3dc841fe8bEvan Cheng 10681953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Chengstatic const VNInfo *findDefinedVNInfo(const LiveInterval &li, unsigned DefIdx) { 10691953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng const VNInfo *VNI = NULL; 10701953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng for (LiveInterval::const_vni_iterator i = li.vni_begin(), 10711953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng e = li.vni_end(); i != e; ++i) 10721953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng if ((*i)->def == DefIdx) { 10731953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng VNI = *i; 10741953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng break; 10751953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng } 10761953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng return VNI; 10771953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng} 10781953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng 1079063284c001666c0a3906acbe0a26dc7cae5f081cEvan Cheng/// RewriteInfo - Keep track of machine instrs that will be rewritten 1080063284c001666c0a3906acbe0a26dc7cae5f081cEvan Cheng/// during spilling. 1081063284c001666c0a3906acbe0a26dc7cae5f081cEvan Chengstruct RewriteInfo { 1082063284c001666c0a3906acbe0a26dc7cae5f081cEvan Cheng unsigned Index; 1083063284c001666c0a3906acbe0a26dc7cae5f081cEvan Cheng MachineInstr *MI; 1084063284c001666c0a3906acbe0a26dc7cae5f081cEvan Cheng bool HasUse; 1085063284c001666c0a3906acbe0a26dc7cae5f081cEvan Cheng bool HasDef; 1086063284c001666c0a3906acbe0a26dc7cae5f081cEvan Cheng RewriteInfo(unsigned i, MachineInstr *mi, bool u, bool d) 1087063284c001666c0a3906acbe0a26dc7cae5f081cEvan Cheng : Index(i), MI(mi), HasUse(u), HasDef(d) {} 1088063284c001666c0a3906acbe0a26dc7cae5f081cEvan Cheng}; 1089063284c001666c0a3906acbe0a26dc7cae5f081cEvan Cheng 1090063284c001666c0a3906acbe0a26dc7cae5f081cEvan Chengstruct RewriteInfoCompare { 1091063284c001666c0a3906acbe0a26dc7cae5f081cEvan Cheng bool operator()(const RewriteInfo &LHS, const RewriteInfo &RHS) const { 1092063284c001666c0a3906acbe0a26dc7cae5f081cEvan Cheng return LHS.Index < RHS.Index; 1093063284c001666c0a3906acbe0a26dc7cae5f081cEvan Cheng } 1094063284c001666c0a3906acbe0a26dc7cae5f081cEvan Cheng}; 1095063284c001666c0a3906acbe0a26dc7cae5f081cEvan Cheng 1096f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Chengvoid LiveIntervals:: 109781a038218171860ee4c382849c647d3dc841fe8bEvan ChengrewriteInstructionsForSpills(const LiveInterval &li, bool TrySplit, 1098f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng LiveInterval::Ranges::const_iterator &I, 109981a038218171860ee4c382849c647d3dc841fe8bEvan Cheng MachineInstr *ReMatOrigDefMI, MachineInstr *ReMatDefMI, 1100f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng unsigned Slot, int LdSlot, 1101f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng bool isLoad, bool isLoadSS, bool DefIsReMat, bool CanDelete, 1102d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng VirtRegMap &vrm, 1103f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng const TargetRegisterClass* rc, 1104f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng SmallVector<int, 4> &ReMatIds, 110522f07ffd27d1d721634d502c37267721d2e025cfEvan Cheng const MachineLoopInfo *loopInfo, 110681a038218171860ee4c382849c647d3dc841fe8bEvan Cheng BitVector &SpillMBBs, 11071953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng std::map<unsigned, std::vector<SRInfo> > &SpillIdxes, 11080cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng BitVector &RestoreMBBs, 11091953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng std::map<unsigned, std::vector<SRInfo> > &RestoreIdxes, 11101953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng std::map<unsigned,unsigned> &MBBVRegsMap, 1111f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng std::vector<LiveInterval*> &NewLIs) { 1112018f9b020bb12b731b0a7081578e5f82fb35092dEvan Cheng bool AllCanFold = true; 111381a038218171860ee4c382849c647d3dc841fe8bEvan Cheng unsigned NewVReg = 0; 1114063284c001666c0a3906acbe0a26dc7cae5f081cEvan Cheng unsigned start = getBaseIndex(I->start); 1115f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng unsigned end = getBaseIndex(I->end-1) + InstrSlots::NUM; 1116f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng 1117063284c001666c0a3906acbe0a26dc7cae5f081cEvan Cheng // First collect all the def / use in this live range that will be rewritten. 1118063284c001666c0a3906acbe0a26dc7cae5f081cEvan Cheng // Make sure they are sorted according instruction index. 1119063284c001666c0a3906acbe0a26dc7cae5f081cEvan Cheng std::vector<RewriteInfo> RewriteMIs; 1120d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng for (MachineRegisterInfo::reg_iterator ri = mri_->reg_begin(li.reg), 1121d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng re = mri_->reg_end(); ri != re; ) { 1122063284c001666c0a3906acbe0a26dc7cae5f081cEvan Cheng MachineInstr *MI = &(*ri); 1123063284c001666c0a3906acbe0a26dc7cae5f081cEvan Cheng MachineOperand &O = ri.getOperand(); 1124063284c001666c0a3906acbe0a26dc7cae5f081cEvan Cheng ++ri; 1125063284c001666c0a3906acbe0a26dc7cae5f081cEvan Cheng unsigned index = getInstructionIndex(MI); 1126063284c001666c0a3906acbe0a26dc7cae5f081cEvan Cheng if (index < start || index >= end) 1127063284c001666c0a3906acbe0a26dc7cae5f081cEvan Cheng continue; 1128063284c001666c0a3906acbe0a26dc7cae5f081cEvan Cheng RewriteMIs.push_back(RewriteInfo(index, MI, O.isUse(), O.isDef())); 1129063284c001666c0a3906acbe0a26dc7cae5f081cEvan Cheng } 1130063284c001666c0a3906acbe0a26dc7cae5f081cEvan Cheng std::sort(RewriteMIs.begin(), RewriteMIs.end(), RewriteInfoCompare()); 1131063284c001666c0a3906acbe0a26dc7cae5f081cEvan Cheng 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. 1142063284c001666c0a3906acbe0a26dc7cae5f081cEvan Cheng while (i != e && RewriteMIs[i].MI == MI) { 1143063284c001666c0a3906acbe0a26dc7cae5f081cEvan Cheng assert(RewriteMIs[i].Index == index); 1144063284c001666c0a3906acbe0a26dc7cae5f081cEvan Cheng MIHasUse |= RewriteMIs[i].HasUse; 1145063284c001666c0a3906acbe0a26dc7cae5f081cEvan Cheng MIHasDef |= RewriteMIs[i].HasDef; 1146063284c001666c0a3906acbe0a26dc7cae5f081cEvan Cheng ++i; 1147063284c001666c0a3906acbe0a26dc7cae5f081cEvan Cheng } 114881a038218171860ee4c382849c647d3dc841fe8bEvan Cheng MachineBasicBlock *MBB = MI->getParent(); 1149063284c001666c0a3906acbe0a26dc7cae5f081cEvan Cheng unsigned MBBId = MBB->getNumber(); 1150018f9b020bb12b731b0a7081578e5f82fb35092dEvan Cheng unsigned ThisVReg = 0; 115170306f8348f27c61cfed5a60e2fceac0f29746a2Evan Cheng if (TrySplit) { 1152063284c001666c0a3906acbe0a26dc7cae5f081cEvan Cheng std::map<unsigned,unsigned>::const_iterator NVI = MBBVRegsMap.find(MBBId); 11531953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng if (NVI != MBBVRegsMap.end()) { 1154018f9b020bb12b731b0a7081578e5f82fb35092dEvan Cheng ThisVReg = NVI->second; 11551953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng // One common case: 11561953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng // x = use 11571953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng // ... 11581953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng // ... 11591953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng // def = ... 11601953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng // = use 11611953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng // It's better to start a new interval to avoid artifically 11621953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng // extend the new interval. 11631953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng if (MIHasDef && !MIHasUse) { 11641953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng MBBVRegsMap.erase(MBB->getNumber()); 1165018f9b020bb12b731b0a7081578e5f82fb35092dEvan Cheng ThisVReg = 0; 11661953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng } 11671953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng } 1168cada245d06959831b90f8c29f92e77beda4b71cbEvan Cheng } 1169018f9b020bb12b731b0a7081578e5f82fb35092dEvan Cheng 1170018f9b020bb12b731b0a7081578e5f82fb35092dEvan Cheng bool IsNew = ThisVReg == 0; 1171018f9b020bb12b731b0a7081578e5f82fb35092dEvan Cheng if (IsNew) { 1172018f9b020bb12b731b0a7081578e5f82fb35092dEvan Cheng // This ends the previous live interval. If all of its def / use 1173018f9b020bb12b731b0a7081578e5f82fb35092dEvan Cheng // can be folded, give it a low spill weight. 1174018f9b020bb12b731b0a7081578e5f82fb35092dEvan Cheng if (NewVReg && TrySplit && AllCanFold) { 1175018f9b020bb12b731b0a7081578e5f82fb35092dEvan Cheng LiveInterval &nI = getOrCreateInterval(NewVReg); 1176018f9b020bb12b731b0a7081578e5f82fb35092dEvan Cheng nI.weight /= 10.0F; 1177018f9b020bb12b731b0a7081578e5f82fb35092dEvan Cheng } 1178018f9b020bb12b731b0a7081578e5f82fb35092dEvan Cheng AllCanFold = true; 1179018f9b020bb12b731b0a7081578e5f82fb35092dEvan Cheng } 1180018f9b020bb12b731b0a7081578e5f82fb35092dEvan Cheng NewVReg = ThisVReg; 1181018f9b020bb12b731b0a7081578e5f82fb35092dEvan Cheng 118281a038218171860ee4c382849c647d3dc841fe8bEvan Cheng bool HasDef = false; 118381a038218171860ee4c382849c647d3dc841fe8bEvan Cheng bool HasUse = false; 1184d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng bool CanFold = rewriteInstructionForSpills(li, I->valno, TrySplit, 1185018f9b020bb12b731b0a7081578e5f82fb35092dEvan Cheng index, end, MI, ReMatOrigDefMI, ReMatDefMI, 1186018f9b020bb12b731b0a7081578e5f82fb35092dEvan Cheng Slot, LdSlot, isLoad, isLoadSS, DefIsReMat, 1187d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng CanDelete, vrm, rc, ReMatIds, loopInfo, NewVReg, 1188d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng HasDef, HasUse, MBBVRegsMap, NewLIs); 118981a038218171860ee4c382849c647d3dc841fe8bEvan Cheng if (!HasDef && !HasUse) 119081a038218171860ee4c382849c647d3dc841fe8bEvan Cheng continue; 119181a038218171860ee4c382849c647d3dc841fe8bEvan Cheng 1192018f9b020bb12b731b0a7081578e5f82fb35092dEvan Cheng AllCanFold &= CanFold; 1193018f9b020bb12b731b0a7081578e5f82fb35092dEvan Cheng 119481a038218171860ee4c382849c647d3dc841fe8bEvan Cheng // Update weight of spill interval. 119581a038218171860ee4c382849c647d3dc841fe8bEvan Cheng LiveInterval &nI = getOrCreateInterval(NewVReg); 119670306f8348f27c61cfed5a60e2fceac0f29746a2Evan Cheng if (!TrySplit) { 119781a038218171860ee4c382849c647d3dc841fe8bEvan Cheng // The spill weight is now infinity as it cannot be spilled again. 119881a038218171860ee4c382849c647d3dc841fe8bEvan Cheng nI.weight = HUGE_VALF; 11990cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng continue; 12000cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng } 12010cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng 12020cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng // Keep track of the last def and first use in each MBB. 12030cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng if (HasDef) { 12040cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng if (MI != ReMatOrigDefMI || !CanDelete) { 12050cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng bool HasKill = false; 12060cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng if (!HasUse) 12070cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng HasKill = anyKillInMBBAfterIdx(li, I->valno, MBB, getDefIndex(index)); 12080cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng else { 12091953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng // If this is a two-address code, then this index starts a new VNInfo. 12101953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng const VNInfo *VNI = findDefinedVNInfo(li, getDefIndex(index)); 12110cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng if (VNI) 12120cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng HasKill = anyKillInMBBAfterIdx(li, VNI, MBB, getDefIndex(index)); 121381a038218171860ee4c382849c647d3dc841fe8bEvan Cheng } 1214e3110d0825e6316fd2dd21d6a4e593295cd413f1Evan Cheng std::map<unsigned, std::vector<SRInfo> >::iterator SII = 1215e3110d0825e6316fd2dd21d6a4e593295cd413f1Evan Cheng SpillIdxes.find(MBBId); 12160cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng if (!HasKill) { 12171953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng if (SII == SpillIdxes.end()) { 12181953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng std::vector<SRInfo> S; 12191953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng S.push_back(SRInfo(index, NewVReg, true)); 12201953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng SpillIdxes.insert(std::make_pair(MBBId, S)); 12211953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng } else if (SII->second.back().vreg != NewVReg) { 12221953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng SII->second.push_back(SRInfo(index, NewVReg, true)); 12231953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng } else if ((int)index > SII->second.back().index) { 12240cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng // If there is an earlier def and this is a two-address 12250cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng // instruction, then it's not possible to fold the store (which 12260cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng // would also fold the load). 12271953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng SRInfo &Info = SII->second.back(); 12281953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng Info.index = index; 12291953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng Info.canFold = !HasUse; 123081a038218171860ee4c382849c647d3dc841fe8bEvan Cheng } 12310cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng SpillMBBs.set(MBBId); 1232e3110d0825e6316fd2dd21d6a4e593295cd413f1Evan Cheng } else if (SII != SpillIdxes.end() && 1233e3110d0825e6316fd2dd21d6a4e593295cd413f1Evan Cheng SII->second.back().vreg == NewVReg && 1234e3110d0825e6316fd2dd21d6a4e593295cd413f1Evan Cheng (int)index > SII->second.back().index) { 1235e3110d0825e6316fd2dd21d6a4e593295cd413f1Evan Cheng // There is an earlier def that's not killed (must be two-address). 1236e3110d0825e6316fd2dd21d6a4e593295cd413f1Evan Cheng // The spill is no longer needed. 1237e3110d0825e6316fd2dd21d6a4e593295cd413f1Evan Cheng SII->second.pop_back(); 1238e3110d0825e6316fd2dd21d6a4e593295cd413f1Evan Cheng if (SII->second.empty()) { 1239e3110d0825e6316fd2dd21d6a4e593295cd413f1Evan Cheng SpillIdxes.erase(MBBId); 1240e3110d0825e6316fd2dd21d6a4e593295cd413f1Evan Cheng SpillMBBs.reset(MBBId); 1241e3110d0825e6316fd2dd21d6a4e593295cd413f1Evan Cheng } 124281a038218171860ee4c382849c647d3dc841fe8bEvan Cheng } 124381a038218171860ee4c382849c647d3dc841fe8bEvan Cheng } 12440cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng } 124581a038218171860ee4c382849c647d3dc841fe8bEvan Cheng 12460cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng if (HasUse) { 12471953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng std::map<unsigned, std::vector<SRInfo> >::iterator SII = 12480cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng SpillIdxes.find(MBBId); 12491953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng if (SII != SpillIdxes.end() && 12501953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng SII->second.back().vreg == NewVReg && 12511953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng (int)index > SII->second.back().index) 12520cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng // Use(s) following the last def, it's not safe to fold the spill. 12531953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng SII->second.back().canFold = false; 12541953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng std::map<unsigned, std::vector<SRInfo> >::iterator RII = 12550cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng RestoreIdxes.find(MBBId); 12561953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng if (RII != RestoreIdxes.end() && RII->second.back().vreg == NewVReg) 12570cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng // If we are splitting live intervals, only fold if it's the first 12580cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng // use and there isn't another use later in the MBB. 12591953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng RII->second.back().canFold = false; 12600cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng else if (IsNew) { 12610cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng // Only need a reload if there isn't an earlier def / use. 12621953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng if (RII == RestoreIdxes.end()) { 12631953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng std::vector<SRInfo> Infos; 12641953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng Infos.push_back(SRInfo(index, NewVReg, true)); 12651953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng RestoreIdxes.insert(std::make_pair(MBBId, Infos)); 12661953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng } else { 12671953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng RII->second.push_back(SRInfo(index, NewVReg, true)); 12681953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng } 12690cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng RestoreMBBs.set(MBBId); 12700cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng } 127181a038218171860ee4c382849c647d3dc841fe8bEvan Cheng } 12720cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng 12730cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng // Update spill weight. 127422f07ffd27d1d721634d502c37267721d2e025cfEvan Cheng unsigned loopDepth = loopInfo->getLoopDepth(MBB); 12750cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng nI.weight += getSpillWeight(HasDef, HasUse, loopDepth); 1276f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng } 1277018f9b020bb12b731b0a7081578e5f82fb35092dEvan Cheng 1278018f9b020bb12b731b0a7081578e5f82fb35092dEvan Cheng if (NewVReg && TrySplit && AllCanFold) { 1279018f9b020bb12b731b0a7081578e5f82fb35092dEvan Cheng // If all of its def / use can be folded, give it a low spill weight. 1280018f9b020bb12b731b0a7081578e5f82fb35092dEvan Cheng LiveInterval &nI = getOrCreateInterval(NewVReg); 1281018f9b020bb12b731b0a7081578e5f82fb35092dEvan Cheng nI.weight /= 10.0F; 1282018f9b020bb12b731b0a7081578e5f82fb35092dEvan Cheng } 1283f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng} 1284f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng 12851953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Chengbool LiveIntervals::alsoFoldARestore(int Id, int index, unsigned vr, 12861953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng BitVector &RestoreMBBs, 12871953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng std::map<unsigned,std::vector<SRInfo> > &RestoreIdxes) { 12881953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng if (!RestoreMBBs[Id]) 12891953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng return false; 12901953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng std::vector<SRInfo> &Restores = RestoreIdxes[Id]; 12911953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng for (unsigned i = 0, e = Restores.size(); i != e; ++i) 12921953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng if (Restores[i].index == index && 12931953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng Restores[i].vreg == vr && 12941953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng Restores[i].canFold) 12951953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng return true; 12961953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng return false; 12971953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng} 12981953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng 12991953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Chengvoid LiveIntervals::eraseRestoreInfo(int Id, int index, unsigned vr, 13001953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng BitVector &RestoreMBBs, 13011953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng std::map<unsigned,std::vector<SRInfo> > &RestoreIdxes) { 13021953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng if (!RestoreMBBs[Id]) 13031953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng return; 13041953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng std::vector<SRInfo> &Restores = RestoreIdxes[Id]; 13051953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng for (unsigned i = 0, e = Restores.size(); i != e; ++i) 13061953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng if (Restores[i].index == index && Restores[i].vreg) 13071953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng Restores[i].index = -1; 13081953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng} 130981a038218171860ee4c382849c647d3dc841fe8bEvan Cheng 131081a038218171860ee4c382849c647d3dc841fe8bEvan Cheng 1311f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Chengstd::vector<LiveInterval*> LiveIntervals:: 131281a038218171860ee4c382849c647d3dc841fe8bEvan ChengaddIntervalsForSpills(const LiveInterval &li, 131322f07ffd27d1d721634d502c37267721d2e025cfEvan Cheng const MachineLoopInfo *loopInfo, VirtRegMap &vrm) { 1314f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng // Since this is called after the analysis is done we don't know if 1315f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng // LiveVariables is available 1316f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng lv_ = getAnalysisToUpdate<LiveVariables>(); 1317f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng 1318f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng assert(li.weight != HUGE_VALF && 1319f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng "attempt to spill already spilled interval!"); 1320f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng 1321f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng DOUT << "\t\t\t\tadding intervals for spills for interval: "; 13226f0d024a534af18d9e60b3ea757376cd8a3a980eDan Gohman li.print(DOUT, tri_); 1323f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng DOUT << '\n'; 1324f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng 132581a038218171860ee4c382849c647d3dc841fe8bEvan Cheng // Each bit specify whether it a spill is required in the MBB. 132681a038218171860ee4c382849c647d3dc841fe8bEvan Cheng BitVector SpillMBBs(mf_->getNumBlockIDs()); 13271953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng std::map<unsigned, std::vector<SRInfo> > SpillIdxes; 13280cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng BitVector RestoreMBBs(mf_->getNumBlockIDs()); 13291953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng std::map<unsigned, std::vector<SRInfo> > RestoreIdxes; 13301953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng std::map<unsigned,unsigned> MBBVRegsMap; 1331f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng std::vector<LiveInterval*> NewLIs; 1332d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng const TargetRegisterClass* rc = mri_->getRegClass(li.reg); 1333f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng 1334f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng unsigned NumValNums = li.getNumValNums(); 1335f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng SmallVector<MachineInstr*, 4> ReMatDefs; 1336f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng ReMatDefs.resize(NumValNums, NULL); 1337f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng SmallVector<MachineInstr*, 4> ReMatOrigDefs; 1338f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng ReMatOrigDefs.resize(NumValNums, NULL); 1339f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng SmallVector<int, 4> ReMatIds; 1340f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng ReMatIds.resize(NumValNums, VirtRegMap::MAX_STACK_SLOT); 1341f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng BitVector ReMatDelete(NumValNums); 1342f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng unsigned Slot = VirtRegMap::MAX_STACK_SLOT; 1343f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng 134481a038218171860ee4c382849c647d3dc841fe8bEvan Cheng // Spilling a split live interval. It cannot be split any further. Also, 134581a038218171860ee4c382849c647d3dc841fe8bEvan Cheng // it's also guaranteed to be a single val# / range interval. 134681a038218171860ee4c382849c647d3dc841fe8bEvan Cheng if (vrm.getPreSplitReg(li.reg)) { 134781a038218171860ee4c382849c647d3dc841fe8bEvan Cheng vrm.setIsSplitFromReg(li.reg, 0); 1348d120ffd26f2715c600b028d4eac9a3c41a9f4653Evan Cheng // Unset the split kill marker on the last use. 1349d120ffd26f2715c600b028d4eac9a3c41a9f4653Evan Cheng unsigned KillIdx = vrm.getKillPoint(li.reg); 1350d120ffd26f2715c600b028d4eac9a3c41a9f4653Evan Cheng if (KillIdx) { 1351d120ffd26f2715c600b028d4eac9a3c41a9f4653Evan Cheng MachineInstr *KillMI = getInstructionFromIndex(KillIdx); 1352d120ffd26f2715c600b028d4eac9a3c41a9f4653Evan Cheng assert(KillMI && "Last use disappeared?"); 1353d120ffd26f2715c600b028d4eac9a3c41a9f4653Evan Cheng int KillOp = KillMI->findRegisterUseOperandIdx(li.reg, true); 1354d120ffd26f2715c600b028d4eac9a3c41a9f4653Evan Cheng assert(KillOp != -1 && "Last use disappeared?"); 1355f73823000e2d5d6e1cf65bdf5a107297e18d35fbChris Lattner KillMI->getOperand(KillOp).setIsKill(false); 1356d120ffd26f2715c600b028d4eac9a3c41a9f4653Evan Cheng } 1357adf85906906ebf85c57c333e8209f37ef11a6c99Evan Cheng vrm.removeKillPoint(li.reg); 135881a038218171860ee4c382849c647d3dc841fe8bEvan Cheng bool DefIsReMat = vrm.isReMaterialized(li.reg); 135981a038218171860ee4c382849c647d3dc841fe8bEvan Cheng Slot = vrm.getStackSlot(li.reg); 136081a038218171860ee4c382849c647d3dc841fe8bEvan Cheng assert(Slot != VirtRegMap::MAX_STACK_SLOT); 136181a038218171860ee4c382849c647d3dc841fe8bEvan Cheng MachineInstr *ReMatDefMI = DefIsReMat ? 136281a038218171860ee4c382849c647d3dc841fe8bEvan Cheng vrm.getReMaterializedMI(li.reg) : NULL; 136381a038218171860ee4c382849c647d3dc841fe8bEvan Cheng int LdSlot = 0; 136481a038218171860ee4c382849c647d3dc841fe8bEvan Cheng bool isLoadSS = DefIsReMat && tii_->isLoadFromStackSlot(ReMatDefMI, LdSlot); 136581a038218171860ee4c382849c647d3dc841fe8bEvan Cheng bool isLoad = isLoadSS || 1366749c6f6b5ed301c84aac562e414486549d7b98ebChris Lattner (DefIsReMat && (ReMatDefMI->getDesc().isSimpleLoad())); 136781a038218171860ee4c382849c647d3dc841fe8bEvan Cheng bool IsFirstRange = true; 136881a038218171860ee4c382849c647d3dc841fe8bEvan Cheng for (LiveInterval::Ranges::const_iterator 136981a038218171860ee4c382849c647d3dc841fe8bEvan Cheng I = li.ranges.begin(), E = li.ranges.end(); I != E; ++I) { 137081a038218171860ee4c382849c647d3dc841fe8bEvan Cheng // If this is a split live interval with multiple ranges, it means there 137181a038218171860ee4c382849c647d3dc841fe8bEvan Cheng // are two-address instructions that re-defined the value. Only the 137281a038218171860ee4c382849c647d3dc841fe8bEvan Cheng // first def can be rematerialized! 137381a038218171860ee4c382849c647d3dc841fe8bEvan Cheng if (IsFirstRange) { 1374cb3c330d39442130d0587208d673ce9c33c7008fEvan Cheng // Note ReMatOrigDefMI has already been deleted. 137581a038218171860ee4c382849c647d3dc841fe8bEvan Cheng rewriteInstructionsForSpills(li, false, I, NULL, ReMatDefMI, 137681a038218171860ee4c382849c647d3dc841fe8bEvan Cheng Slot, LdSlot, isLoad, isLoadSS, DefIsReMat, 1377d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng false, vrm, rc, ReMatIds, loopInfo, 13780cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng SpillMBBs, SpillIdxes, RestoreMBBs, RestoreIdxes, 13791953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng MBBVRegsMap, NewLIs); 138081a038218171860ee4c382849c647d3dc841fe8bEvan Cheng } else { 138181a038218171860ee4c382849c647d3dc841fe8bEvan Cheng rewriteInstructionsForSpills(li, false, I, NULL, 0, 138281a038218171860ee4c382849c647d3dc841fe8bEvan Cheng Slot, 0, false, false, false, 1383d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng false, vrm, rc, ReMatIds, loopInfo, 13840cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng SpillMBBs, SpillIdxes, RestoreMBBs, RestoreIdxes, 13851953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng MBBVRegsMap, NewLIs); 138681a038218171860ee4c382849c647d3dc841fe8bEvan Cheng } 138781a038218171860ee4c382849c647d3dc841fe8bEvan Cheng IsFirstRange = false; 138881a038218171860ee4c382849c647d3dc841fe8bEvan Cheng } 138981a038218171860ee4c382849c647d3dc841fe8bEvan Cheng return NewLIs; 139081a038218171860ee4c382849c647d3dc841fe8bEvan Cheng } 139181a038218171860ee4c382849c647d3dc841fe8bEvan Cheng 139281a038218171860ee4c382849c647d3dc841fe8bEvan Cheng bool TrySplit = SplitAtBB && !intervalIsInOneMBB(li); 13930cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng if (SplitLimit != -1 && (int)numSplits >= SplitLimit) 13940cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng TrySplit = false; 13950cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng if (TrySplit) 13960cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng ++numSplits; 1397f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng bool NeedStackSlot = false; 1398f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng for (LiveInterval::const_vni_iterator i = li.vni_begin(), e = li.vni_end(); 1399f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng i != e; ++i) { 1400f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng const VNInfo *VNI = *i; 1401f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng unsigned VN = VNI->id; 1402f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng unsigned DefIdx = VNI->def; 1403f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng if (DefIdx == ~1U) 1404f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng continue; // Dead val#. 1405f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng // Is the def for the val# rematerializable? 140681a038218171860ee4c382849c647d3dc841fe8bEvan Cheng MachineInstr *ReMatDefMI = (DefIdx == ~0u) 140781a038218171860ee4c382849c647d3dc841fe8bEvan Cheng ? 0 : getInstructionFromIndex(DefIdx); 14085ef3a04b542c4e585276768fa9ca2af698ef5c87Evan Cheng bool dummy; 14095ef3a04b542c4e585276768fa9ca2af698ef5c87Evan Cheng if (ReMatDefMI && isReMaterializable(li, VNI, ReMatDefMI, dummy)) { 1410f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng // Remember how to remat the def of this val#. 141181a038218171860ee4c382849c647d3dc841fe8bEvan Cheng ReMatOrigDefs[VN] = ReMatDefMI; 1412f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng // Original def may be modified so we have to make a copy here. vrm must 1413f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng // delete these! 141481a038218171860ee4c382849c647d3dc841fe8bEvan Cheng ReMatDefs[VN] = ReMatDefMI = ReMatDefMI->clone(); 1415f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng 1416f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng bool CanDelete = true; 1417c3fc7d9ec9b495c8a88cd854247105c296d3aabdEvan Cheng if (VNI->hasPHIKill) { 1418c3fc7d9ec9b495c8a88cd854247105c296d3aabdEvan Cheng // A kill is a phi node, not all of its uses can be rematerialized. 1419f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng // It must not be deleted. 1420c3fc7d9ec9b495c8a88cd854247105c296d3aabdEvan Cheng CanDelete = false; 1421c3fc7d9ec9b495c8a88cd854247105c296d3aabdEvan Cheng // Need a stack slot if there is any live range where uses cannot be 1422c3fc7d9ec9b495c8a88cd854247105c296d3aabdEvan Cheng // rematerialized. 1423c3fc7d9ec9b495c8a88cd854247105c296d3aabdEvan Cheng NeedStackSlot = true; 1424f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng } 1425f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng if (CanDelete) 1426f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng ReMatDelete.set(VN); 1427f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng } else { 1428f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng // Need a stack slot if there is any live range where uses cannot be 1429f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng // rematerialized. 1430f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng NeedStackSlot = true; 1431f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng } 1432f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng } 1433f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng 1434f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng // One stack slot per live interval. 143581a038218171860ee4c382849c647d3dc841fe8bEvan Cheng if (NeedStackSlot && vrm.getPreSplitReg(li.reg) == 0) 1436f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng Slot = vrm.assignVirt2StackSlot(li.reg); 1437f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng 1438f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng // Create new intervals and rewrite defs and uses. 1439f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng for (LiveInterval::Ranges::const_iterator 1440f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng I = li.ranges.begin(), E = li.ranges.end(); I != E; ++I) { 144181a038218171860ee4c382849c647d3dc841fe8bEvan Cheng MachineInstr *ReMatDefMI = ReMatDefs[I->valno->id]; 144281a038218171860ee4c382849c647d3dc841fe8bEvan Cheng MachineInstr *ReMatOrigDefMI = ReMatOrigDefs[I->valno->id]; 144381a038218171860ee4c382849c647d3dc841fe8bEvan Cheng bool DefIsReMat = ReMatDefMI != NULL; 1444f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng bool CanDelete = ReMatDelete[I->valno->id]; 1445f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng int LdSlot = 0; 144681a038218171860ee4c382849c647d3dc841fe8bEvan Cheng bool isLoadSS = DefIsReMat && tii_->isLoadFromStackSlot(ReMatDefMI, LdSlot); 1447f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng bool isLoad = isLoadSS || 1448749c6f6b5ed301c84aac562e414486549d7b98ebChris Lattner (DefIsReMat && ReMatDefMI->getDesc().isSimpleLoad()); 144981a038218171860ee4c382849c647d3dc841fe8bEvan Cheng rewriteInstructionsForSpills(li, TrySplit, I, ReMatOrigDefMI, ReMatDefMI, 14500cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng Slot, LdSlot, isLoad, isLoadSS, DefIsReMat, 1451d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng CanDelete, vrm, rc, ReMatIds, loopInfo, 14520cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng SpillMBBs, SpillIdxes, RestoreMBBs, RestoreIdxes, 14531953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng MBBVRegsMap, NewLIs); 1454f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng } 1455f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng 14560cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng // Insert spills / restores if we are splitting. 14571953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng if (!TrySplit) 14581953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng return NewLIs; 14591953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng 1460b50bb8cf197709b3f49044740044c06d8f314564Evan Cheng SmallPtrSet<LiveInterval*, 4> AddedKill; 1461aee4af68ae2016afc5b4ec0c430e539c5810a766Evan Cheng SmallVector<unsigned, 2> Ops; 14621953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng if (NeedStackSlot) { 14631953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng int Id = SpillMBBs.find_first(); 14641953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng while (Id != -1) { 14651953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng std::vector<SRInfo> &spills = SpillIdxes[Id]; 14661953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng for (unsigned i = 0, e = spills.size(); i != e; ++i) { 14671953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng int index = spills[i].index; 14681953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng unsigned VReg = spills[i].vreg; 1469597d10d84fb6b34f7776121404d5ed802b21b2b6Evan Cheng LiveInterval &nI = getOrCreateInterval(VReg); 14700cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng bool isReMat = vrm.isReMaterialized(VReg); 14710cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng MachineInstr *MI = getInstructionFromIndex(index); 1472aee4af68ae2016afc5b4ec0c430e539c5810a766Evan Cheng bool CanFold = false; 1473aee4af68ae2016afc5b4ec0c430e539c5810a766Evan Cheng bool FoundUse = false; 1474aee4af68ae2016afc5b4ec0c430e539c5810a766Evan Cheng Ops.clear(); 1475cddbb83ea82e98658d9f530c50a7b9d23249afc2Evan Cheng if (spills[i].canFold) { 1476aee4af68ae2016afc5b4ec0c430e539c5810a766Evan Cheng CanFold = true; 14770cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng for (unsigned j = 0, ee = MI->getNumOperands(); j != ee; ++j) { 14780cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng MachineOperand &MO = MI->getOperand(j); 14790cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng if (!MO.isRegister() || MO.getReg() != VReg) 14800cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng continue; 1481aee4af68ae2016afc5b4ec0c430e539c5810a766Evan Cheng 1482aee4af68ae2016afc5b4ec0c430e539c5810a766Evan Cheng Ops.push_back(j); 1483aee4af68ae2016afc5b4ec0c430e539c5810a766Evan Cheng if (MO.isDef()) 1484cddbb83ea82e98658d9f530c50a7b9d23249afc2Evan Cheng continue; 1485aee4af68ae2016afc5b4ec0c430e539c5810a766Evan Cheng if (isReMat || 1486aee4af68ae2016afc5b4ec0c430e539c5810a766Evan Cheng (!FoundUse && !alsoFoldARestore(Id, index, VReg, 1487aee4af68ae2016afc5b4ec0c430e539c5810a766Evan Cheng RestoreMBBs, RestoreIdxes))) { 1488aee4af68ae2016afc5b4ec0c430e539c5810a766Evan Cheng // MI has two-address uses of the same register. If the use 1489aee4af68ae2016afc5b4ec0c430e539c5810a766Evan Cheng // isn't the first and only use in the BB, then we can't fold 1490aee4af68ae2016afc5b4ec0c430e539c5810a766Evan Cheng // it. FIXME: Move this to rewriteInstructionsForSpills. 1491aee4af68ae2016afc5b4ec0c430e539c5810a766Evan Cheng CanFold = false; 1492cddbb83ea82e98658d9f530c50a7b9d23249afc2Evan Cheng break; 1493cddbb83ea82e98658d9f530c50a7b9d23249afc2Evan Cheng } 1494aee4af68ae2016afc5b4ec0c430e539c5810a766Evan Cheng FoundUse = true; 14950cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng } 14960cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng } 14970cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng // Fold the store into the def if possible. 1498cddbb83ea82e98658d9f530c50a7b9d23249afc2Evan Cheng bool Folded = false; 1499aee4af68ae2016afc5b4ec0c430e539c5810a766Evan Cheng if (CanFold && !Ops.empty()) { 1500aee4af68ae2016afc5b4ec0c430e539c5810a766Evan Cheng if (tryFoldMemoryOperand(MI, vrm, NULL, index, Ops, true, Slot,VReg)){ 1501cddbb83ea82e98658d9f530c50a7b9d23249afc2Evan Cheng Folded = true; 1502f38d14f03e495ea98ae16bda6febbde276513294Evan Cheng if (FoundUse > 0) { 1503aee4af68ae2016afc5b4ec0c430e539c5810a766Evan Cheng // Also folded uses, do not issue a load. 1504aee4af68ae2016afc5b4ec0c430e539c5810a766Evan Cheng eraseRestoreInfo(Id, index, VReg, RestoreMBBs, RestoreIdxes); 1505f38d14f03e495ea98ae16bda6febbde276513294Evan Cheng nI.removeRange(getLoadIndex(index), getUseIndex(index)+1); 1506f38d14f03e495ea98ae16bda6febbde276513294Evan Cheng } 1507597d10d84fb6b34f7776121404d5ed802b21b2b6Evan Cheng nI.removeRange(getDefIndex(index), getStoreIndex(index)); 1508cddbb83ea82e98658d9f530c50a7b9d23249afc2Evan Cheng } 15090cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng } 15100cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng 1511aee4af68ae2016afc5b4ec0c430e539c5810a766Evan Cheng // Else tell the spiller to issue a spill. 1512b50bb8cf197709b3f49044740044c06d8f314564Evan Cheng if (!Folded) { 1513b50bb8cf197709b3f49044740044c06d8f314564Evan Cheng LiveRange *LR = &nI.ranges[nI.ranges.size()-1]; 1514b50bb8cf197709b3f49044740044c06d8f314564Evan Cheng bool isKill = LR->end == getStoreIndex(index); 1515b50bb8cf197709b3f49044740044c06d8f314564Evan Cheng vrm.addSpillPoint(VReg, isKill, MI); 1516b50bb8cf197709b3f49044740044c06d8f314564Evan Cheng if (isKill) 1517b50bb8cf197709b3f49044740044c06d8f314564Evan Cheng AddedKill.insert(&nI); 1518b50bb8cf197709b3f49044740044c06d8f314564Evan Cheng } 15190cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng } 15201953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng Id = SpillMBBs.find_next(Id); 15210cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng } 15221953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng } 15230cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng 15241953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng int Id = RestoreMBBs.find_first(); 15251953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng while (Id != -1) { 15261953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng std::vector<SRInfo> &restores = RestoreIdxes[Id]; 15271953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng for (unsigned i = 0, e = restores.size(); i != e; ++i) { 15281953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng int index = restores[i].index; 15291953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng if (index == -1) 15301953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng continue; 15311953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng unsigned VReg = restores[i].vreg; 1532597d10d84fb6b34f7776121404d5ed802b21b2b6Evan Cheng LiveInterval &nI = getOrCreateInterval(VReg); 153381a038218171860ee4c382849c647d3dc841fe8bEvan Cheng MachineInstr *MI = getInstructionFromIndex(index); 1534aee4af68ae2016afc5b4ec0c430e539c5810a766Evan Cheng bool CanFold = false; 1535aee4af68ae2016afc5b4ec0c430e539c5810a766Evan Cheng Ops.clear(); 1536cddbb83ea82e98658d9f530c50a7b9d23249afc2Evan Cheng if (restores[i].canFold) { 1537aee4af68ae2016afc5b4ec0c430e539c5810a766Evan Cheng CanFold = true; 153881a038218171860ee4c382849c647d3dc841fe8bEvan Cheng for (unsigned j = 0, ee = MI->getNumOperands(); j != ee; ++j) { 153981a038218171860ee4c382849c647d3dc841fe8bEvan Cheng MachineOperand &MO = MI->getOperand(j); 154081a038218171860ee4c382849c647d3dc841fe8bEvan Cheng if (!MO.isRegister() || MO.getReg() != VReg) 154181a038218171860ee4c382849c647d3dc841fe8bEvan Cheng continue; 1542aee4af68ae2016afc5b4ec0c430e539c5810a766Evan Cheng 15430cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng if (MO.isDef()) { 1544aee4af68ae2016afc5b4ec0c430e539c5810a766Evan Cheng // If this restore were to be folded, it would have been folded 1545aee4af68ae2016afc5b4ec0c430e539c5810a766Evan Cheng // already. 1546aee4af68ae2016afc5b4ec0c430e539c5810a766Evan Cheng CanFold = false; 154781a038218171860ee4c382849c647d3dc841fe8bEvan Cheng break; 154881a038218171860ee4c382849c647d3dc841fe8bEvan Cheng } 1549aee4af68ae2016afc5b4ec0c430e539c5810a766Evan Cheng Ops.push_back(j); 155081a038218171860ee4c382849c647d3dc841fe8bEvan Cheng } 155181a038218171860ee4c382849c647d3dc841fe8bEvan Cheng } 15520cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng 15530cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng // Fold the load into the use if possible. 1554cddbb83ea82e98658d9f530c50a7b9d23249afc2Evan Cheng bool Folded = false; 1555aee4af68ae2016afc5b4ec0c430e539c5810a766Evan Cheng if (CanFold && !Ops.empty()) { 1556aee4af68ae2016afc5b4ec0c430e539c5810a766Evan Cheng if (!vrm.isReMaterialized(VReg)) 1557aee4af68ae2016afc5b4ec0c430e539c5810a766Evan Cheng Folded = tryFoldMemoryOperand(MI, vrm, NULL,index,Ops,true,Slot,VReg); 1558aee4af68ae2016afc5b4ec0c430e539c5810a766Evan Cheng else { 15590cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng MachineInstr *ReMatDefMI = vrm.getReMaterializedMI(VReg); 15600cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng int LdSlot = 0; 15610cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng bool isLoadSS = tii_->isLoadFromStackSlot(ReMatDefMI, LdSlot); 15620cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng // If the rematerializable def is a load, also try to fold it. 1563749c6f6b5ed301c84aac562e414486549d7b98ebChris Lattner if (isLoadSS || ReMatDefMI->getDesc().isSimpleLoad()) 1564aee4af68ae2016afc5b4ec0c430e539c5810a766Evan Cheng Folded = tryFoldMemoryOperand(MI, vrm, ReMatDefMI, index, 1565aee4af68ae2016afc5b4ec0c430e539c5810a766Evan Cheng Ops, isLoadSS, LdSlot, VReg); 1566d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng unsigned ImpUse = getReMatImplicitUse(li, ReMatDefMI); 1567d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng if (ImpUse) { 1568d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng // Re-matting an instruction with virtual register use. Add the 1569d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng // register as an implicit use on the use MI and update the register 1570d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng // interval's spill weight. 1571d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng unsigned loopDepth = loopInfo->getLoopDepth(MI->getParent()); 1572d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng LiveInterval &ImpLi = getInterval(ImpUse); 1573d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng ImpLi.weight += getSpillWeight(false, true, loopDepth); 1574d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng MI->addOperand(MachineOperand::CreateReg(ImpUse, false, true)); 1575d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng } 1576aee4af68ae2016afc5b4ec0c430e539c5810a766Evan Cheng } 15770cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng } 15780cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng // If folding is not possible / failed, then tell the spiller to issue a 15790cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng // load / rematerialization for us. 1580597d10d84fb6b34f7776121404d5ed802b21b2b6Evan Cheng if (Folded) 1581597d10d84fb6b34f7776121404d5ed802b21b2b6Evan Cheng nI.removeRange(getLoadIndex(index), getUseIndex(index)+1); 1582b50bb8cf197709b3f49044740044c06d8f314564Evan Cheng else 15830cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng vrm.addRestorePoint(VReg, MI); 158481a038218171860ee4c382849c647d3dc841fe8bEvan Cheng } 15851953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng Id = RestoreMBBs.find_next(Id); 158681a038218171860ee4c382849c647d3dc841fe8bEvan Cheng } 158781a038218171860ee4c382849c647d3dc841fe8bEvan Cheng 1588b50bb8cf197709b3f49044740044c06d8f314564Evan Cheng // Finalize intervals: add kills, finalize spill weights, and filter out 1589b50bb8cf197709b3f49044740044c06d8f314564Evan Cheng // dead intervals. 1590597d10d84fb6b34f7776121404d5ed802b21b2b6Evan Cheng std::vector<LiveInterval*> RetNewLIs; 1591597d10d84fb6b34f7776121404d5ed802b21b2b6Evan Cheng for (unsigned i = 0, e = NewLIs.size(); i != e; ++i) { 1592597d10d84fb6b34f7776121404d5ed802b21b2b6Evan Cheng LiveInterval *LI = NewLIs[i]; 1593597d10d84fb6b34f7776121404d5ed802b21b2b6Evan Cheng if (!LI->empty()) { 1594597d10d84fb6b34f7776121404d5ed802b21b2b6Evan Cheng LI->weight /= LI->getSize(); 1595b50bb8cf197709b3f49044740044c06d8f314564Evan Cheng if (!AddedKill.count(LI)) { 1596b50bb8cf197709b3f49044740044c06d8f314564Evan Cheng LiveRange *LR = &LI->ranges[LI->ranges.size()-1]; 1597d120ffd26f2715c600b028d4eac9a3c41a9f4653Evan Cheng unsigned LastUseIdx = getBaseIndex(LR->end); 1598d120ffd26f2715c600b028d4eac9a3c41a9f4653Evan Cheng MachineInstr *LastUse = getInstructionFromIndex(LastUseIdx); 1599b50bb8cf197709b3f49044740044c06d8f314564Evan Cheng int UseIdx = LastUse->findRegisterUseOperandIdx(LI->reg); 1600b50bb8cf197709b3f49044740044c06d8f314564Evan Cheng assert(UseIdx != -1); 1601d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng if (LastUse->getOperand(UseIdx).isImplicit() || 1602d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng LastUse->getDesc().getOperandConstraint(UseIdx,TOI::TIED_TO) == -1){ 1603b50bb8cf197709b3f49044740044c06d8f314564Evan Cheng LastUse->getOperand(UseIdx).setIsKill(); 1604d120ffd26f2715c600b028d4eac9a3c41a9f4653Evan Cheng vrm.addKillPoint(LI->reg, LastUseIdx); 1605adf85906906ebf85c57c333e8209f37ef11a6c99Evan Cheng } 1606b50bb8cf197709b3f49044740044c06d8f314564Evan Cheng } 1607597d10d84fb6b34f7776121404d5ed802b21b2b6Evan Cheng RetNewLIs.push_back(LI); 1608597d10d84fb6b34f7776121404d5ed802b21b2b6Evan Cheng } 1609597d10d84fb6b34f7776121404d5ed802b21b2b6Evan Cheng } 161081a038218171860ee4c382849c647d3dc841fe8bEvan Cheng 1611597d10d84fb6b34f7776121404d5ed802b21b2b6Evan Cheng return RetNewLIs; 1612f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng} 1613