LiveIntervalAnalysis.cpp revision 6130f66eaae89f8878590796977678afa8448926
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)) 192e6d088acc90e422451e098555d383d4d65b6ce6bBill Wendling 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. 3276130f66eaae89f8878590796977678afa8448926Evan Cheng if (mi->registerDefIsDead(interval.reg, tri_)) 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) 4026130f66eaae89f8878590796977678afa8448926Evan Cheng if (mi->registerDefIsDead(interval.reg, tri_)) { 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; 4136130f66eaae89f8878590796977678afa8448926Evan Cheng if (mi->killsRegister(interval.reg, tri_)) { 414bdc679d564e67a81792e463f6614b0088f975025Bill Wendling DOUT << " killed"; 415ab4b66d4c279e8cd9e448687020fc838e7881dbcChris Lattner end = getUseIndex(baseIndex) + 1; 416ab4b66d4c279e8cd9e448687020fc838e7881dbcChris Lattner goto exit; 4176130f66eaae89f8878590796977678afa8448926Evan Cheng } else if (mi->modifiesRegister(interval.reg, tri_)) { 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) 4626130f66eaae89f8878590796977678afa8448926Evan Cheng // If MI also modifies the sub-register explicitly, avoid processing it 4636130f66eaae89f8878590796977678afa8448926Evan Cheng // more than once. Do not pass in TRI here so it checks for exact match. 4646130f66eaae89f8878590796977678afa8448926Evan Cheng if (!MI->modifiesRegister(*AS)) 46524a3cc4c83e5edb25fadf7b8979a26b4451795c6Evan Cheng handlePhysicalRegisterDef(MBB, MI, MIIdx, getOrCreateInterval(*AS), 0); 466f35fef7060c465dd7b578bf6339a18e8a8911888Chris Lattner } 4674d46e1e521c0df1990ea50f8146d22bd77ea71a6Alkis Evlogimenos} 4684d46e1e521c0df1990ea50f8146d22bd77ea71a6Alkis Evlogimenos 469b371f457b0ea4a652a9f526ba4375c80ae542252Evan Chengvoid LiveIntervals::handleLiveInRegister(MachineBasicBlock *MBB, 4709b25b8ca24d6df2e097741dcc15016772ee4eda7Jim Laskey unsigned MIIdx, 47124a3cc4c83e5edb25fadf7b8979a26b4451795c6Evan Cheng LiveInterval &interval, bool isAlias) { 472b371f457b0ea4a652a9f526ba4375c80ae542252Evan Cheng DOUT << "\t\tlivein register: "; DEBUG(printRegName(interval.reg)); 473b371f457b0ea4a652a9f526ba4375c80ae542252Evan Cheng 474b371f457b0ea4a652a9f526ba4375c80ae542252Evan Cheng // Look for kills, if it reaches a def before it's killed, then it shouldn't 475b371f457b0ea4a652a9f526ba4375c80ae542252Evan Cheng // be considered a livein. 476b371f457b0ea4a652a9f526ba4375c80ae542252Evan Cheng MachineBasicBlock::iterator mi = MBB->begin(); 4779b25b8ca24d6df2e097741dcc15016772ee4eda7Jim Laskey unsigned baseIndex = MIIdx; 4789b25b8ca24d6df2e097741dcc15016772ee4eda7Jim Laskey unsigned start = baseIndex; 479b371f457b0ea4a652a9f526ba4375c80ae542252Evan Cheng unsigned end = start; 480b371f457b0ea4a652a9f526ba4375c80ae542252Evan Cheng while (mi != MBB->end()) { 4816130f66eaae89f8878590796977678afa8448926Evan Cheng if (mi->killsRegister(interval.reg, tri_)) { 482b371f457b0ea4a652a9f526ba4375c80ae542252Evan Cheng DOUT << " killed"; 483b371f457b0ea4a652a9f526ba4375c80ae542252Evan Cheng end = getUseIndex(baseIndex) + 1; 484b371f457b0ea4a652a9f526ba4375c80ae542252Evan Cheng goto exit; 4856130f66eaae89f8878590796977678afa8448926Evan Cheng } else if (mi->modifiesRegister(interval.reg, tri_)) { 486b371f457b0ea4a652a9f526ba4375c80ae542252Evan Cheng // Another instruction redefines the register before it is ever read. 487b371f457b0ea4a652a9f526ba4375c80ae542252Evan Cheng // Then the register is essentially dead at the instruction that defines 488b371f457b0ea4a652a9f526ba4375c80ae542252Evan Cheng // it. Hence its interval is: 489b371f457b0ea4a652a9f526ba4375c80ae542252Evan Cheng // [defSlot(def), defSlot(def)+1) 490b371f457b0ea4a652a9f526ba4375c80ae542252Evan Cheng DOUT << " dead"; 491b371f457b0ea4a652a9f526ba4375c80ae542252Evan Cheng end = getDefIndex(start) + 1; 492b371f457b0ea4a652a9f526ba4375c80ae542252Evan Cheng goto exit; 493b371f457b0ea4a652a9f526ba4375c80ae542252Evan Cheng } 494b371f457b0ea4a652a9f526ba4375c80ae542252Evan Cheng 495b371f457b0ea4a652a9f526ba4375c80ae542252Evan Cheng baseIndex += InstrSlots::NUM; 496b371f457b0ea4a652a9f526ba4375c80ae542252Evan Cheng ++mi; 497b371f457b0ea4a652a9f526ba4375c80ae542252Evan Cheng } 498b371f457b0ea4a652a9f526ba4375c80ae542252Evan Cheng 499b371f457b0ea4a652a9f526ba4375c80ae542252Evan Chengexit: 50075611fb4e6ab253be30ac29a2b15e9bf8c1d146eEvan Cheng // Live-in register might not be used at all. 50175611fb4e6ab253be30ac29a2b15e9bf8c1d146eEvan Cheng if (end == MIIdx) { 502292da949f6c87d6499425d64d37d7c5870ec57adEvan Cheng if (isAlias) { 503292da949f6c87d6499425d64d37d7c5870ec57adEvan Cheng DOUT << " dead"; 50475611fb4e6ab253be30ac29a2b15e9bf8c1d146eEvan Cheng end = getDefIndex(MIIdx) + 1; 505292da949f6c87d6499425d64d37d7c5870ec57adEvan Cheng } else { 506292da949f6c87d6499425d64d37d7c5870ec57adEvan Cheng DOUT << " live through"; 507292da949f6c87d6499425d64d37d7c5870ec57adEvan Cheng end = baseIndex; 508292da949f6c87d6499425d64d37d7c5870ec57adEvan Cheng } 50924a3cc4c83e5edb25fadf7b8979a26b4451795c6Evan Cheng } 51024a3cc4c83e5edb25fadf7b8979a26b4451795c6Evan Cheng 511f3bb2e65d12857f83b273f4ecab013680310bbbcEvan Cheng LiveRange LR(start, end, interval.getNextValue(start, 0, VNInfoAllocator)); 5129b25b8ca24d6df2e097741dcc15016772ee4eda7Jim Laskey interval.addRange(LR); 513f3bb2e65d12857f83b273f4ecab013680310bbbcEvan Cheng interval.addKill(LR.valno, end); 51424c2e5cf7e926452ea5875d027ec0d24d9c19e39Evan Cheng DOUT << " +" << LR << '\n'; 515b371f457b0ea4a652a9f526ba4375c80ae542252Evan Cheng} 516b371f457b0ea4a652a9f526ba4375c80ae542252Evan Cheng 517ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos/// computeIntervals - computes the live intervals for virtual 5184d46e1e521c0df1990ea50f8146d22bd77ea71a6Alkis Evlogimenos/// registers. for some ordering of the machine instructions [1,N] a 51908cec00588ec1a8fa85b208555f006d7396ae7a4Alkis Evlogimenos/// live interval is an interval [i, j) where 1 <= i <= j < N for 520ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos/// which a variable is live 521f7da2c7b0c6293c268881628fc351bed7763f1f4Chris Lattnervoid LiveIntervals::computeIntervals() { 522bdc679d564e67a81792e463f6614b0088f975025Bill Wendling DOUT << "********** COMPUTING LIVE INTERVALS **********\n" 523bdc679d564e67a81792e463f6614b0088f975025Bill Wendling << "********** Function: " 524bdc679d564e67a81792e463f6614b0088f975025Bill Wendling << ((Value*)mf_->getFunction())->getName() << '\n'; 5256b128bdc58a496e9f08e4d09416330320761baffChris Lattner // Track the index of the current machine instr. 5266b128bdc58a496e9f08e4d09416330320761baffChris Lattner unsigned MIIndex = 0; 527428b92eb83b457b71d29d1d4b7900d36a0ce9a53Chris Lattner for (MachineFunction::iterator MBBI = mf_->begin(), E = mf_->end(); 528428b92eb83b457b71d29d1d4b7900d36a0ce9a53Chris Lattner MBBI != E; ++MBBI) { 529428b92eb83b457b71d29d1d4b7900d36a0ce9a53Chris Lattner MachineBasicBlock *MBB = MBBI; 530bdc679d564e67a81792e463f6614b0088f975025Bill Wendling DOUT << ((Value*)MBB->getBasicBlock())->getName() << ":\n"; 5311a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos 532428b92eb83b457b71d29d1d4b7900d36a0ce9a53Chris Lattner MachineBasicBlock::iterator MI = MBB->begin(), miEnd = MBB->end(); 5330c9f92e1ff64ee56724eae444a0442b02f83d0a8Evan Cheng 534cb406c25973b4e88a6c10ad839ef1beeb3664715Dan Gohman // Create intervals for live-ins to this BB first. 535cb406c25973b4e88a6c10ad839ef1beeb3664715Dan Gohman for (MachineBasicBlock::const_livein_iterator LI = MBB->livein_begin(), 536cb406c25973b4e88a6c10ad839ef1beeb3664715Dan Gohman LE = MBB->livein_end(); LI != LE; ++LI) { 537cb406c25973b4e88a6c10ad839ef1beeb3664715Dan Gohman handleLiveInRegister(MBB, MIIndex, getOrCreateInterval(*LI)); 538cb406c25973b4e88a6c10ad839ef1beeb3664715Dan Gohman // Multiple live-ins can alias the same register. 5396f0d024a534af18d9e60b3ea757376cd8a3a980eDan Gohman for (const unsigned* AS = tri_->getSubRegisters(*LI); *AS; ++AS) 540cb406c25973b4e88a6c10ad839ef1beeb3664715Dan Gohman if (!hasInterval(*AS)) 541cb406c25973b4e88a6c10ad839ef1beeb3664715Dan Gohman handleLiveInRegister(MBB, MIIndex, getOrCreateInterval(*AS), 542cb406c25973b4e88a6c10ad839ef1beeb3664715Dan Gohman true); 543dffb2e83ed2546226d09c40aa43524e2392322daChris Lattner } 544dffb2e83ed2546226d09c40aa43524e2392322daChris Lattner 545428b92eb83b457b71d29d1d4b7900d36a0ce9a53Chris Lattner for (; MI != miEnd; ++MI) { 546bdc679d564e67a81792e463f6614b0088f975025Bill Wendling DOUT << MIIndex << "\t" << *MI; 5471a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos 548438f7bc67cf235ccee7e6f7ac7f4ae2186eb8020Evan Cheng // Handle defs. 549428b92eb83b457b71d29d1d4b7900d36a0ce9a53Chris Lattner for (int i = MI->getNumOperands() - 1; i >= 0; --i) { 550428b92eb83b457b71d29d1d4b7900d36a0ce9a53Chris Lattner MachineOperand &MO = MI->getOperand(i); 5511a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // handle register defs - build intervals 552428b92eb83b457b71d29d1d4b7900d36a0ce9a53Chris Lattner if (MO.isRegister() && MO.getReg() && MO.isDef()) 553428b92eb83b457b71d29d1d4b7900d36a0ce9a53Chris Lattner handleRegisterDef(MBB, MI, MIIndex, MO.getReg()); 5541a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos } 5556b128bdc58a496e9f08e4d09416330320761baffChris Lattner 5566b128bdc58a496e9f08e4d09416330320761baffChris Lattner MIIndex += InstrSlots::NUM; 557ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos } 5581a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos } 559ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos} 560b27ef248f579b354aab434f63c417ab1103e47e2Alkis Evlogimenos 5614ca980e7f9ce7b78955307c2d07001a24d3b6befEvan Chengbool LiveIntervals::findLiveInMBBs(const LiveRange &LR, 562a5bfc97da713ec9e185226d44e6adb4d3087b304Evan Cheng SmallVectorImpl<MachineBasicBlock*> &MBBs) const { 5634ca980e7f9ce7b78955307c2d07001a24d3b6befEvan Cheng std::vector<IdxMBBPair>::const_iterator I = 5644ca980e7f9ce7b78955307c2d07001a24d3b6befEvan Cheng std::lower_bound(Idx2MBBMap.begin(), Idx2MBBMap.end(), LR.start); 5654ca980e7f9ce7b78955307c2d07001a24d3b6befEvan Cheng 5664ca980e7f9ce7b78955307c2d07001a24d3b6befEvan Cheng bool ResVal = false; 5674ca980e7f9ce7b78955307c2d07001a24d3b6befEvan Cheng while (I != Idx2MBBMap.end()) { 5684ca980e7f9ce7b78955307c2d07001a24d3b6befEvan Cheng if (LR.end <= I->first) 5694ca980e7f9ce7b78955307c2d07001a24d3b6befEvan Cheng break; 5704ca980e7f9ce7b78955307c2d07001a24d3b6befEvan Cheng MBBs.push_back(I->second); 5714ca980e7f9ce7b78955307c2d07001a24d3b6befEvan Cheng ResVal = true; 5724ca980e7f9ce7b78955307c2d07001a24d3b6befEvan Cheng ++I; 5734ca980e7f9ce7b78955307c2d07001a24d3b6befEvan Cheng } 5744ca980e7f9ce7b78955307c2d07001a24d3b6befEvan Cheng return ResVal; 5754ca980e7f9ce7b78955307c2d07001a24d3b6befEvan Cheng} 5764ca980e7f9ce7b78955307c2d07001a24d3b6befEvan Cheng 5774ca980e7f9ce7b78955307c2d07001a24d3b6befEvan Cheng 578a1613db62fec94845aa8306232fb665273615badAlkis EvlogimenosLiveInterval LiveIntervals::createInterval(unsigned reg) { 5796f0d024a534af18d9e60b3ea757376cd8a3a980eDan Gohman float Weight = TargetRegisterInfo::isPhysicalRegister(reg) ? 5807902c75331fa8f38fc8380f5573d935c0d149ef5Jim Laskey HUGE_VALF : 0.0F; 581a1613db62fec94845aa8306232fb665273615badAlkis Evlogimenos return LiveInterval(reg, Weight); 5829a8b490735d216435862a3d52e669357f165550fAlkis Evlogimenos} 583f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng 584c8d044e4f779fdcfc5e7d592927740fd8f672a70Evan Cheng/// getVNInfoSourceReg - Helper function that parses the specified VNInfo 585c8d044e4f779fdcfc5e7d592927740fd8f672a70Evan Cheng/// copy field and returns the source register that defines it. 586c8d044e4f779fdcfc5e7d592927740fd8f672a70Evan Chengunsigned LiveIntervals::getVNInfoSourceReg(const VNInfo *VNI) const { 587c8d044e4f779fdcfc5e7d592927740fd8f672a70Evan Cheng if (!VNI->copy) 588c8d044e4f779fdcfc5e7d592927740fd8f672a70Evan Cheng return 0; 589c8d044e4f779fdcfc5e7d592927740fd8f672a70Evan Cheng 590c8d044e4f779fdcfc5e7d592927740fd8f672a70Evan Cheng if (VNI->copy->getOpcode() == TargetInstrInfo::EXTRACT_SUBREG) 591c8d044e4f779fdcfc5e7d592927740fd8f672a70Evan Cheng return VNI->copy->getOperand(1).getReg(); 592c8d044e4f779fdcfc5e7d592927740fd8f672a70Evan Cheng unsigned SrcReg, DstReg; 593c8d044e4f779fdcfc5e7d592927740fd8f672a70Evan Cheng if (tii_->isMoveInstr(*VNI->copy, SrcReg, DstReg)) 594c8d044e4f779fdcfc5e7d592927740fd8f672a70Evan Cheng return SrcReg; 595c8d044e4f779fdcfc5e7d592927740fd8f672a70Evan Cheng assert(0 && "Unrecognized copy instruction!"); 596c8d044e4f779fdcfc5e7d592927740fd8f672a70Evan Cheng return 0; 597c8d044e4f779fdcfc5e7d592927740fd8f672a70Evan Cheng} 598f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng 599f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng//===----------------------------------------------------------------------===// 600f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng// Register allocator hooks. 601f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng// 602f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng 603d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng/// getReMatImplicitUse - If the remat definition MI has one (for now, we only 604d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng/// allow one) virtual register operand, then its uses are implicitly using 605d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng/// the register. Returns the virtual register. 606d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Chengunsigned LiveIntervals::getReMatImplicitUse(const LiveInterval &li, 607d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng MachineInstr *MI) const { 608d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng unsigned RegOp = 0; 609d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) { 610d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng MachineOperand &MO = MI->getOperand(i); 611d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng if (!MO.isRegister() || !MO.isUse()) 612d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng continue; 613d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng unsigned Reg = MO.getReg(); 614d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng if (Reg == 0 || Reg == li.reg) 615d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng continue; 616d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng // FIXME: For now, only remat MI with at most one register operand. 617d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng assert(!RegOp && 618d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng "Can't rematerialize instruction with multiple register operand!"); 619d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng RegOp = MO.getReg(); 620d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng break; 621d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng } 622d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng return RegOp; 623d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng} 624d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng 625d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng/// isValNoAvailableAt - Return true if the val# of the specified interval 626d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng/// which reaches the given instruction also reaches the specified use index. 627d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Chengbool LiveIntervals::isValNoAvailableAt(const LiveInterval &li, MachineInstr *MI, 628d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng unsigned UseIdx) const { 629d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng unsigned Index = getInstructionIndex(MI); 630d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng VNInfo *ValNo = li.FindLiveRangeContaining(Index)->valno; 631d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng LiveInterval::const_iterator UI = li.FindLiveRangeContaining(UseIdx); 632d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng return UI != li.end() && UI->valno == ValNo; 633d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng} 634d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng 635f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng/// isReMaterializable - Returns true if the definition MI of the specified 636f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng/// val# of the specified interval is re-materializable. 637f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Chengbool LiveIntervals::isReMaterializable(const LiveInterval &li, 6385ef3a04b542c4e585276768fa9ca2af698ef5c87Evan Cheng const VNInfo *ValNo, MachineInstr *MI, 6395ef3a04b542c4e585276768fa9ca2af698ef5c87Evan Cheng bool &isLoad) { 640f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng if (DisableReMat) 641f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng return false; 642f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng 6435ef3a04b542c4e585276768fa9ca2af698ef5c87Evan Cheng isLoad = false; 644749c6f6b5ed301c84aac562e414486549d7b98ebChris Lattner const TargetInstrDesc &TID = MI->getDesc(); 645d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng if (TID.isImplicitDef()) 646d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng return true; 647dd3465eed17cdf226bdb465e604dfa851d36029dEvan Cheng 648dd3465eed17cdf226bdb465e604dfa851d36029dEvan Cheng int FrameIdx = 0; 649dd3465eed17cdf226bdb465e604dfa851d36029dEvan Cheng if (tii_->isLoadFromStackSlot(MI, FrameIdx) && 650249ded3fa8884f91fded869fb6e251b8aebb0376Evan Cheng mf_->getFrameInfo()->isImmutableObjectIndex(FrameIdx)) 65179a0c1e46c4f7d8a2a06f4ef3e2c54d883c7fe25Evan Cheng // FIXME: Let target specific isReallyTriviallyReMaterializable determines 65279a0c1e46c4f7d8a2a06f4ef3e2c54d883c7fe25Evan Cheng // this but remember this is not safe to fold into a two-address 65379a0c1e46c4f7d8a2a06f4ef3e2c54d883c7fe25Evan Cheng // instruction. 654249ded3fa8884f91fded869fb6e251b8aebb0376Evan Cheng // This is a load from fixed stack slot. It can be rematerialized. 655dd3465eed17cdf226bdb465e604dfa851d36029dEvan Cheng return true; 656dd3465eed17cdf226bdb465e604dfa851d36029dEvan Cheng 657d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng if (tii_->isTriviallyReMaterializable(MI)) { 658749c6f6b5ed301c84aac562e414486549d7b98ebChris Lattner isLoad = TID.isSimpleLoad(); 659d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng 660d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng unsigned ImpUse = getReMatImplicitUse(li, MI); 661d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng if (ImpUse) { 662d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng const LiveInterval &ImpLi = getInterval(ImpUse); 663d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng for (MachineRegisterInfo::use_iterator ri = mri_->use_begin(li.reg), 664d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng re = mri_->use_end(); ri != re; ++ri) { 665d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng MachineInstr *UseMI = &*ri; 666d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng unsigned UseIdx = getInstructionIndex(UseMI); 667d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng if (li.FindLiveRangeContaining(UseIdx)->valno != ValNo) 668d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng continue; 669298bbe82cb390235f7b8ab4bd550feff909e0c3dEvan Cheng if (!isValNoAvailableAt(ImpLi, MI, UseIdx)) 670d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng return false; 671d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng } 672d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng } 673f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng return true; 6745ef3a04b542c4e585276768fa9ca2af698ef5c87Evan Cheng } 675f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng 676dd3465eed17cdf226bdb465e604dfa851d36029dEvan Cheng return false; 6775ef3a04b542c4e585276768fa9ca2af698ef5c87Evan Cheng} 6785ef3a04b542c4e585276768fa9ca2af698ef5c87Evan Cheng 6795ef3a04b542c4e585276768fa9ca2af698ef5c87Evan Cheng/// isReMaterializable - Returns true if every definition of MI of every 6805ef3a04b542c4e585276768fa9ca2af698ef5c87Evan Cheng/// val# of the specified interval is re-materializable. 6815ef3a04b542c4e585276768fa9ca2af698ef5c87Evan Chengbool LiveIntervals::isReMaterializable(const LiveInterval &li, bool &isLoad) { 6825ef3a04b542c4e585276768fa9ca2af698ef5c87Evan Cheng isLoad = false; 6835ef3a04b542c4e585276768fa9ca2af698ef5c87Evan Cheng for (LiveInterval::const_vni_iterator i = li.vni_begin(), e = li.vni_end(); 6845ef3a04b542c4e585276768fa9ca2af698ef5c87Evan Cheng i != e; ++i) { 6855ef3a04b542c4e585276768fa9ca2af698ef5c87Evan Cheng const VNInfo *VNI = *i; 6865ef3a04b542c4e585276768fa9ca2af698ef5c87Evan Cheng unsigned DefIdx = VNI->def; 6875ef3a04b542c4e585276768fa9ca2af698ef5c87Evan Cheng if (DefIdx == ~1U) 6885ef3a04b542c4e585276768fa9ca2af698ef5c87Evan Cheng continue; // Dead val#. 6895ef3a04b542c4e585276768fa9ca2af698ef5c87Evan Cheng // Is the def for the val# rematerializable? 6905ef3a04b542c4e585276768fa9ca2af698ef5c87Evan Cheng if (DefIdx == ~0u) 6915ef3a04b542c4e585276768fa9ca2af698ef5c87Evan Cheng return false; 6925ef3a04b542c4e585276768fa9ca2af698ef5c87Evan Cheng MachineInstr *ReMatDefMI = getInstructionFromIndex(DefIdx); 6935ef3a04b542c4e585276768fa9ca2af698ef5c87Evan Cheng bool DefIsLoad = false; 694d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng if (!ReMatDefMI || 695d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng !isReMaterializable(li, VNI, ReMatDefMI, DefIsLoad)) 696f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng return false; 6975ef3a04b542c4e585276768fa9ca2af698ef5c87Evan Cheng isLoad |= DefIsLoad; 698f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng } 699f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng return true; 700f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng} 701f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng 70279a0c1e46c4f7d8a2a06f4ef3e2c54d883c7fe25Evan Cheng/// FilterFoldedOps - Filter out two-address use operands. Return 70379a0c1e46c4f7d8a2a06f4ef3e2c54d883c7fe25Evan Cheng/// true if it finds any issue with the operands that ought to prevent 70479a0c1e46c4f7d8a2a06f4ef3e2c54d883c7fe25Evan Cheng/// folding. 70579a0c1e46c4f7d8a2a06f4ef3e2c54d883c7fe25Evan Chengstatic bool FilterFoldedOps(MachineInstr *MI, 70679a0c1e46c4f7d8a2a06f4ef3e2c54d883c7fe25Evan Cheng SmallVector<unsigned, 2> &Ops, 70779a0c1e46c4f7d8a2a06f4ef3e2c54d883c7fe25Evan Cheng unsigned &MRInfo, 70879a0c1e46c4f7d8a2a06f4ef3e2c54d883c7fe25Evan Cheng SmallVector<unsigned, 2> &FoldOps) { 709749c6f6b5ed301c84aac562e414486549d7b98ebChris Lattner const TargetInstrDesc &TID = MI->getDesc(); 7106e141fd04897e5eb4925bb6351297170ebd8a756Evan Cheng 71179a0c1e46c4f7d8a2a06f4ef3e2c54d883c7fe25Evan Cheng MRInfo = 0; 712aee4af68ae2016afc5b4ec0c430e539c5810a766Evan Cheng for (unsigned i = 0, e = Ops.size(); i != e; ++i) { 713aee4af68ae2016afc5b4ec0c430e539c5810a766Evan Cheng unsigned OpIdx = Ops[i]; 714d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng MachineOperand &MO = MI->getOperand(OpIdx); 715aee4af68ae2016afc5b4ec0c430e539c5810a766Evan Cheng // FIXME: fold subreg use. 716d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng if (MO.getSubReg()) 71779a0c1e46c4f7d8a2a06f4ef3e2c54d883c7fe25Evan Cheng return true; 718d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng if (MO.isDef()) 719aee4af68ae2016afc5b4ec0c430e539c5810a766Evan Cheng MRInfo |= (unsigned)VirtRegMap::isMod; 720aee4af68ae2016afc5b4ec0c430e539c5810a766Evan Cheng else { 721aee4af68ae2016afc5b4ec0c430e539c5810a766Evan Cheng // Filter out two-address use operand(s). 722d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng if (!MO.isImplicit() && 723d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng TID.getOperandConstraint(OpIdx, TOI::TIED_TO) != -1) { 724aee4af68ae2016afc5b4ec0c430e539c5810a766Evan Cheng MRInfo = VirtRegMap::isModRef; 725aee4af68ae2016afc5b4ec0c430e539c5810a766Evan Cheng continue; 726aee4af68ae2016afc5b4ec0c430e539c5810a766Evan Cheng } 727aee4af68ae2016afc5b4ec0c430e539c5810a766Evan Cheng MRInfo |= (unsigned)VirtRegMap::isRef; 728aee4af68ae2016afc5b4ec0c430e539c5810a766Evan Cheng } 729aee4af68ae2016afc5b4ec0c430e539c5810a766Evan Cheng FoldOps.push_back(OpIdx); 730e62f97c094dba44e4c259d20135167fa91912eeaEvan Cheng } 73179a0c1e46c4f7d8a2a06f4ef3e2c54d883c7fe25Evan Cheng return false; 73279a0c1e46c4f7d8a2a06f4ef3e2c54d883c7fe25Evan Cheng} 73379a0c1e46c4f7d8a2a06f4ef3e2c54d883c7fe25Evan Cheng 73479a0c1e46c4f7d8a2a06f4ef3e2c54d883c7fe25Evan Cheng 73579a0c1e46c4f7d8a2a06f4ef3e2c54d883c7fe25Evan Cheng/// tryFoldMemoryOperand - Attempts to fold either a spill / restore from 73679a0c1e46c4f7d8a2a06f4ef3e2c54d883c7fe25Evan Cheng/// slot / to reg or any rematerialized load into ith operand of specified 73779a0c1e46c4f7d8a2a06f4ef3e2c54d883c7fe25Evan Cheng/// MI. If it is successul, MI is updated with the newly created MI and 73879a0c1e46c4f7d8a2a06f4ef3e2c54d883c7fe25Evan Cheng/// returns true. 73979a0c1e46c4f7d8a2a06f4ef3e2c54d883c7fe25Evan Chengbool LiveIntervals::tryFoldMemoryOperand(MachineInstr* &MI, 74079a0c1e46c4f7d8a2a06f4ef3e2c54d883c7fe25Evan Cheng VirtRegMap &vrm, MachineInstr *DefMI, 74179a0c1e46c4f7d8a2a06f4ef3e2c54d883c7fe25Evan Cheng unsigned InstrIdx, 74279a0c1e46c4f7d8a2a06f4ef3e2c54d883c7fe25Evan Cheng SmallVector<unsigned, 2> &Ops, 74379a0c1e46c4f7d8a2a06f4ef3e2c54d883c7fe25Evan Cheng bool isSS, int Slot, unsigned Reg) { 74479a0c1e46c4f7d8a2a06f4ef3e2c54d883c7fe25Evan Cheng const TargetInstrDesc &TID = MI->getDesc(); 74579a0c1e46c4f7d8a2a06f4ef3e2c54d883c7fe25Evan Cheng // If it is an implicit def instruction, just delete it. 74679a0c1e46c4f7d8a2a06f4ef3e2c54d883c7fe25Evan Cheng if (TID.isImplicitDef()) { 74779a0c1e46c4f7d8a2a06f4ef3e2c54d883c7fe25Evan Cheng RemoveMachineInstrFromMaps(MI); 74879a0c1e46c4f7d8a2a06f4ef3e2c54d883c7fe25Evan Cheng vrm.RemoveMachineInstrFromMaps(MI); 74979a0c1e46c4f7d8a2a06f4ef3e2c54d883c7fe25Evan Cheng MI->eraseFromParent(); 75079a0c1e46c4f7d8a2a06f4ef3e2c54d883c7fe25Evan Cheng ++numFolds; 75179a0c1e46c4f7d8a2a06f4ef3e2c54d883c7fe25Evan Cheng return true; 75279a0c1e46c4f7d8a2a06f4ef3e2c54d883c7fe25Evan Cheng } 75379a0c1e46c4f7d8a2a06f4ef3e2c54d883c7fe25Evan Cheng 75479a0c1e46c4f7d8a2a06f4ef3e2c54d883c7fe25Evan Cheng // Filter the list of operand indexes that are to be folded. Abort if 75579a0c1e46c4f7d8a2a06f4ef3e2c54d883c7fe25Evan Cheng // any operand will prevent folding. 75679a0c1e46c4f7d8a2a06f4ef3e2c54d883c7fe25Evan Cheng unsigned MRInfo = 0; 75779a0c1e46c4f7d8a2a06f4ef3e2c54d883c7fe25Evan Cheng SmallVector<unsigned, 2> FoldOps; 75879a0c1e46c4f7d8a2a06f4ef3e2c54d883c7fe25Evan Cheng if (FilterFoldedOps(MI, Ops, MRInfo, FoldOps)) 75979a0c1e46c4f7d8a2a06f4ef3e2c54d883c7fe25Evan Cheng return false; 760cddbb83ea82e98658d9f530c50a7b9d23249afc2Evan Cheng 761249ded3fa8884f91fded869fb6e251b8aebb0376Evan Cheng // Can't fold a load from fixed stack slot into a two address instruction. 762249ded3fa8884f91fded869fb6e251b8aebb0376Evan Cheng if (isSS && DefMI && (MRInfo & VirtRegMap::isMod)) 763249ded3fa8884f91fded869fb6e251b8aebb0376Evan Cheng return false; 764249ded3fa8884f91fded869fb6e251b8aebb0376Evan Cheng 765f2f8c2ae07b7d9bdbf1b89781c573c7af2bd5e1bEvan Cheng MachineInstr *fmi = isSS ? tii_->foldMemoryOperand(*mf_, MI, FoldOps, Slot) 766f2f8c2ae07b7d9bdbf1b89781c573c7af2bd5e1bEvan Cheng : tii_->foldMemoryOperand(*mf_, MI, FoldOps, DefMI); 767f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng if (fmi) { 768d36531249a9a9500e516148e7e72d4c0a7a4d0eeEvan Cheng // Remember this instruction uses the spill slot. 769d36531249a9a9500e516148e7e72d4c0a7a4d0eeEvan Cheng if (isSS) vrm.addSpillSlotUse(Slot, fmi); 770d36531249a9a9500e516148e7e72d4c0a7a4d0eeEvan Cheng 771f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng // Attempt to fold the memory reference into the instruction. If 772f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng // we can do this, we don't need to insert spill code. 773f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng if (lv_) 774f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng lv_->instructionChanged(MI, fmi); 77581a038218171860ee4c382849c647d3dc841fe8bEvan Cheng else 7766f0d024a534af18d9e60b3ea757376cd8a3a980eDan Gohman fmi->copyKillDeadInfo(MI, tri_); 777f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng MachineBasicBlock &MBB = *MI->getParent(); 7788480293f41c11c22762164449e41cd3adb0dd7d8Evan Cheng if (isSS && !mf_->getFrameInfo()->isImmutableObjectIndex(Slot)) 779aee4af68ae2016afc5b4ec0c430e539c5810a766Evan Cheng vrm.virtFolded(Reg, MI, fmi, (VirtRegMap::ModRef)MRInfo); 78081a038218171860ee4c382849c647d3dc841fe8bEvan Cheng vrm.transferSpillPts(MI, fmi); 7810cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng vrm.transferRestorePts(MI, fmi); 782f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng mi2iMap_.erase(MI); 783cddbb83ea82e98658d9f530c50a7b9d23249afc2Evan Cheng i2miMap_[InstrIdx /InstrSlots::NUM] = fmi; 784cddbb83ea82e98658d9f530c50a7b9d23249afc2Evan Cheng mi2iMap_[fmi] = InstrIdx; 785f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng MI = MBB.insert(MBB.erase(MI), fmi); 7860cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng ++numFolds; 787f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng return true; 788f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng } 789f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng return false; 790f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng} 791f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng 792018f9b020bb12b731b0a7081578e5f82fb35092dEvan Cheng/// canFoldMemoryOperand - Returns true if the specified load / store 793018f9b020bb12b731b0a7081578e5f82fb35092dEvan Cheng/// folding is possible. 794018f9b020bb12b731b0a7081578e5f82fb35092dEvan Chengbool LiveIntervals::canFoldMemoryOperand(MachineInstr *MI, 79579a0c1e46c4f7d8a2a06f4ef3e2c54d883c7fe25Evan Cheng SmallVector<unsigned, 2> &Ops, 796e83a27516cf5b6cc92ead99c17bbd77bca7ae06bEvan Cheng bool ReMatLoad) const { 79779a0c1e46c4f7d8a2a06f4ef3e2c54d883c7fe25Evan Cheng // Filter the list of operand indexes that are to be folded. Abort if 79879a0c1e46c4f7d8a2a06f4ef3e2c54d883c7fe25Evan Cheng // any operand will prevent folding. 79979a0c1e46c4f7d8a2a06f4ef3e2c54d883c7fe25Evan Cheng unsigned MRInfo = 0; 800018f9b020bb12b731b0a7081578e5f82fb35092dEvan Cheng SmallVector<unsigned, 2> FoldOps; 80179a0c1e46c4f7d8a2a06f4ef3e2c54d883c7fe25Evan Cheng if (FilterFoldedOps(MI, Ops, MRInfo, FoldOps)) 80279a0c1e46c4f7d8a2a06f4ef3e2c54d883c7fe25Evan Cheng return false; 803018f9b020bb12b731b0a7081578e5f82fb35092dEvan Cheng 804e83a27516cf5b6cc92ead99c17bbd77bca7ae06bEvan Cheng // Can't fold a remat'ed load into a two address instruction. 805e83a27516cf5b6cc92ead99c17bbd77bca7ae06bEvan Cheng if (ReMatLoad && (MRInfo & VirtRegMap::isMod)) 80679a0c1e46c4f7d8a2a06f4ef3e2c54d883c7fe25Evan Cheng return false; 807018f9b020bb12b731b0a7081578e5f82fb35092dEvan Cheng 808d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng return tii_->canFoldMemoryOperand(MI, FoldOps); 809d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng} 810d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng 81181a038218171860ee4c382849c647d3dc841fe8bEvan Chengbool LiveIntervals::intervalIsInOneMBB(const LiveInterval &li) const { 81281a038218171860ee4c382849c647d3dc841fe8bEvan Cheng SmallPtrSet<MachineBasicBlock*, 4> MBBs; 81381a038218171860ee4c382849c647d3dc841fe8bEvan Cheng for (LiveInterval::Ranges::const_iterator 81481a038218171860ee4c382849c647d3dc841fe8bEvan Cheng I = li.ranges.begin(), E = li.ranges.end(); I != E; ++I) { 81581a038218171860ee4c382849c647d3dc841fe8bEvan Cheng std::vector<IdxMBBPair>::const_iterator II = 81681a038218171860ee4c382849c647d3dc841fe8bEvan Cheng std::lower_bound(Idx2MBBMap.begin(), Idx2MBBMap.end(), I->start); 81781a038218171860ee4c382849c647d3dc841fe8bEvan Cheng if (II == Idx2MBBMap.end()) 81881a038218171860ee4c382849c647d3dc841fe8bEvan Cheng continue; 81981a038218171860ee4c382849c647d3dc841fe8bEvan Cheng if (I->end > II->first) // crossing a MBB. 82081a038218171860ee4c382849c647d3dc841fe8bEvan Cheng return false; 82181a038218171860ee4c382849c647d3dc841fe8bEvan Cheng MBBs.insert(II->second); 82281a038218171860ee4c382849c647d3dc841fe8bEvan Cheng if (MBBs.size() > 1) 82381a038218171860ee4c382849c647d3dc841fe8bEvan Cheng return false; 82481a038218171860ee4c382849c647d3dc841fe8bEvan Cheng } 82581a038218171860ee4c382849c647d3dc841fe8bEvan Cheng return true; 82681a038218171860ee4c382849c647d3dc841fe8bEvan Cheng} 82781a038218171860ee4c382849c647d3dc841fe8bEvan Cheng 828d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng/// rewriteImplicitOps - Rewrite implicit use operands of MI (i.e. uses of 829d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng/// interval on to-be re-materialized operands of MI) with new register. 830d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Chengvoid LiveIntervals::rewriteImplicitOps(const LiveInterval &li, 831d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng MachineInstr *MI, unsigned NewVReg, 832d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng VirtRegMap &vrm) { 833d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng // There is an implicit use. That means one of the other operand is 834d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng // being remat'ed and the remat'ed instruction has li.reg as an 835d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng // use operand. Make sure we rewrite that as well. 836d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) { 837d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng MachineOperand &MO = MI->getOperand(i); 838d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng if (!MO.isRegister()) 839d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng continue; 840d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng unsigned Reg = MO.getReg(); 841d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng if (Reg == 0 || TargetRegisterInfo::isPhysicalRegister(Reg)) 842d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng continue; 843d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng if (!vrm.isReMaterialized(Reg)) 844d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng continue; 845d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng MachineInstr *ReMatMI = vrm.getReMaterializedMI(Reg); 8466130f66eaae89f8878590796977678afa8448926Evan Cheng MachineOperand *UseMO = ReMatMI->findRegisterUseOperand(li.reg); 8476130f66eaae89f8878590796977678afa8448926Evan Cheng if (UseMO) 8486130f66eaae89f8878590796977678afa8448926Evan Cheng UseMO->setReg(NewVReg); 849d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng } 850d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng} 851d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng 852f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng/// rewriteInstructionForSpills, rewriteInstructionsForSpills - Helper functions 853f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng/// for addIntervalsForSpills to rewrite uses / defs for the given live range. 854018f9b020bb12b731b0a7081578e5f82fb35092dEvan Chengbool LiveIntervals:: 855d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan ChengrewriteInstructionForSpills(const LiveInterval &li, const VNInfo *VNI, 856d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng bool TrySplit, unsigned index, unsigned end, MachineInstr *MI, 85781a038218171860ee4c382849c647d3dc841fe8bEvan Cheng MachineInstr *ReMatOrigDefMI, MachineInstr *ReMatDefMI, 858f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng unsigned Slot, int LdSlot, 859f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng bool isLoad, bool isLoadSS, bool DefIsReMat, bool CanDelete, 860d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng VirtRegMap &vrm, 861f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng const TargetRegisterClass* rc, 862f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng SmallVector<int, 4> &ReMatIds, 86322f07ffd27d1d721634d502c37267721d2e025cfEvan Cheng const MachineLoopInfo *loopInfo, 864313d4b809326f3e04814f94e5b8ae05649d8e0f6Evan Cheng unsigned &NewVReg, unsigned ImpUse, bool &HasDef, bool &HasUse, 8651953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng std::map<unsigned,unsigned> &MBBVRegsMap, 866f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng std::vector<LiveInterval*> &NewLIs) { 867018f9b020bb12b731b0a7081578e5f82fb35092dEvan Cheng bool CanFold = false; 868f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng RestartInstruction: 869f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng for (unsigned i = 0; i != MI->getNumOperands(); ++i) { 870f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng MachineOperand& mop = MI->getOperand(i); 871f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng if (!mop.isRegister()) 872f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng continue; 873f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng unsigned Reg = mop.getReg(); 874f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng unsigned RegI = Reg; 8756f0d024a534af18d9e60b3ea757376cd8a3a980eDan Gohman if (Reg == 0 || TargetRegisterInfo::isPhysicalRegister(Reg)) 876f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng continue; 877f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng if (Reg != li.reg) 878f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng continue; 879f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng 880f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng bool TryFold = !DefIsReMat; 881cb3c330d39442130d0587208d673ce9c33c7008fEvan Cheng bool FoldSS = true; // Default behavior unless it's a remat. 882f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng int FoldSlot = Slot; 883f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng if (DefIsReMat) { 884f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng // If this is the rematerializable definition MI itself and 885f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng // all of its uses are rematerialized, simply delete it. 88681a038218171860ee4c382849c647d3dc841fe8bEvan Cheng if (MI == ReMatOrigDefMI && CanDelete) { 887cddbb83ea82e98658d9f530c50a7b9d23249afc2Evan Cheng DOUT << "\t\t\t\tErasing re-materlizable def: "; 888cddbb83ea82e98658d9f530c50a7b9d23249afc2Evan Cheng DOUT << MI << '\n'; 889d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng unsigned ImpUse = getReMatImplicitUse(li, MI); 890d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng if (ImpUse) { 891d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng // To be deleted MI has a virtual register operand, update the 892d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng // spill weight of the register interval. 893d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng unsigned loopDepth = loopInfo->getLoopDepth(MI->getParent()); 894d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng LiveInterval &ImpLi = getInterval(ImpUse); 895313d4b809326f3e04814f94e5b8ae05649d8e0f6Evan Cheng ImpLi.weight -= 896313d4b809326f3e04814f94e5b8ae05649d8e0f6Evan Cheng getSpillWeight(false, true, loopDepth) / ImpLi.getSize(); 897d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng } 898f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng RemoveMachineInstrFromMaps(MI); 899cada245d06959831b90f8c29f92e77beda4b71cbEvan Cheng vrm.RemoveMachineInstrFromMaps(MI); 900f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng MI->eraseFromParent(); 901f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng break; 902f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng } 903f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng 904f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng // If def for this use can't be rematerialized, then try folding. 9050cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng // If def is rematerializable and it's a load, also try folding. 906cb3c330d39442130d0587208d673ce9c33c7008fEvan Cheng TryFold = !ReMatDefMI || (ReMatDefMI && (MI == ReMatOrigDefMI || isLoad)); 907f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng if (isLoad) { 908f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng // Try fold loads (from stack slot, constant pool, etc.) into uses. 909f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng FoldSS = isLoadSS; 910f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng FoldSlot = LdSlot; 911f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng } 912f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng } 913f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng 914f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng // Scan all of the operands of this instruction rewriting operands 915f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng // to use NewVReg instead of li.reg as appropriate. We do this for 916f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng // two reasons: 917f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng // 918f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng // 1. If the instr reads the same spilled vreg multiple times, we 919f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng // want to reuse the NewVReg. 920f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng // 2. If the instr is a two-addr instruction, we are required to 921f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng // keep the src/dst regs pinned. 922f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng // 923f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng // Keep track of whether we replace a use and/or def so that we can 924f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng // create the spill interval with the appropriate range. 925cddbb83ea82e98658d9f530c50a7b9d23249afc2Evan Cheng 92681a038218171860ee4c382849c647d3dc841fe8bEvan Cheng HasUse = mop.isUse(); 92781a038218171860ee4c382849c647d3dc841fe8bEvan Cheng HasDef = mop.isDef(); 928aee4af68ae2016afc5b4ec0c430e539c5810a766Evan Cheng SmallVector<unsigned, 2> Ops; 929aee4af68ae2016afc5b4ec0c430e539c5810a766Evan Cheng Ops.push_back(i); 930f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng for (unsigned j = i+1, e = MI->getNumOperands(); j != e; ++j) { 931aee4af68ae2016afc5b4ec0c430e539c5810a766Evan Cheng const MachineOperand &MOj = MI->getOperand(j); 932aee4af68ae2016afc5b4ec0c430e539c5810a766Evan Cheng if (!MOj.isRegister()) 933f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng continue; 934aee4af68ae2016afc5b4ec0c430e539c5810a766Evan Cheng unsigned RegJ = MOj.getReg(); 9356f0d024a534af18d9e60b3ea757376cd8a3a980eDan Gohman if (RegJ == 0 || TargetRegisterInfo::isPhysicalRegister(RegJ)) 936f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng continue; 937f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng if (RegJ == RegI) { 938aee4af68ae2016afc5b4ec0c430e539c5810a766Evan Cheng Ops.push_back(j); 939aee4af68ae2016afc5b4ec0c430e539c5810a766Evan Cheng HasUse |= MOj.isUse(); 940aee4af68ae2016afc5b4ec0c430e539c5810a766Evan Cheng HasDef |= MOj.isDef(); 941f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng } 942f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng } 943f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng 944018f9b020bb12b731b0a7081578e5f82fb35092dEvan Cheng if (TryFold) { 945018f9b020bb12b731b0a7081578e5f82fb35092dEvan Cheng // Do not fold load / store here if we are splitting. We'll find an 946018f9b020bb12b731b0a7081578e5f82fb35092dEvan Cheng // optimal point to insert a load / store later. 947018f9b020bb12b731b0a7081578e5f82fb35092dEvan Cheng if (!TrySplit) { 948018f9b020bb12b731b0a7081578e5f82fb35092dEvan Cheng if (tryFoldMemoryOperand(MI, vrm, ReMatDefMI, index, 949018f9b020bb12b731b0a7081578e5f82fb35092dEvan Cheng Ops, FoldSS, FoldSlot, Reg)) { 950018f9b020bb12b731b0a7081578e5f82fb35092dEvan Cheng // Folding the load/store can completely change the instruction in 951018f9b020bb12b731b0a7081578e5f82fb35092dEvan Cheng // unpredictable ways, rescan it from the beginning. 952018f9b020bb12b731b0a7081578e5f82fb35092dEvan Cheng HasUse = false; 953018f9b020bb12b731b0a7081578e5f82fb35092dEvan Cheng HasDef = false; 954018f9b020bb12b731b0a7081578e5f82fb35092dEvan Cheng CanFold = false; 955018f9b020bb12b731b0a7081578e5f82fb35092dEvan Cheng goto RestartInstruction; 956018f9b020bb12b731b0a7081578e5f82fb35092dEvan Cheng } 957018f9b020bb12b731b0a7081578e5f82fb35092dEvan Cheng } else { 958e83a27516cf5b6cc92ead99c17bbd77bca7ae06bEvan Cheng CanFold = canFoldMemoryOperand(MI, Ops, DefIsReMat && isLoad); 959018f9b020bb12b731b0a7081578e5f82fb35092dEvan Cheng } 9606e141fd04897e5eb4925bb6351297170ebd8a756Evan Cheng } else 9616e141fd04897e5eb4925bb6351297170ebd8a756Evan Cheng CanFold = false; 962cddbb83ea82e98658d9f530c50a7b9d23249afc2Evan Cheng 963cddbb83ea82e98658d9f530c50a7b9d23249afc2Evan Cheng // Create a new virtual register for the spill interval. 964cddbb83ea82e98658d9f530c50a7b9d23249afc2Evan Cheng bool CreatedNewVReg = false; 965cddbb83ea82e98658d9f530c50a7b9d23249afc2Evan Cheng if (NewVReg == 0) { 966d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng NewVReg = mri_->createVirtualRegister(rc); 967cddbb83ea82e98658d9f530c50a7b9d23249afc2Evan Cheng vrm.grow(); 968cddbb83ea82e98658d9f530c50a7b9d23249afc2Evan Cheng CreatedNewVReg = true; 969cddbb83ea82e98658d9f530c50a7b9d23249afc2Evan Cheng } 970cddbb83ea82e98658d9f530c50a7b9d23249afc2Evan Cheng mop.setReg(NewVReg); 971d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng if (mop.isImplicit()) 972d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng rewriteImplicitOps(li, MI, NewVReg, vrm); 973cddbb83ea82e98658d9f530c50a7b9d23249afc2Evan Cheng 974cddbb83ea82e98658d9f530c50a7b9d23249afc2Evan Cheng // Reuse NewVReg for other reads. 975d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng for (unsigned j = 0, e = Ops.size(); j != e; ++j) { 976d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng MachineOperand &mopj = MI->getOperand(Ops[j]); 977d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng mopj.setReg(NewVReg); 978d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng if (mopj.isImplicit()) 979d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng rewriteImplicitOps(li, MI, NewVReg, vrm); 980d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng } 981cddbb83ea82e98658d9f530c50a7b9d23249afc2Evan Cheng 98281a038218171860ee4c382849c647d3dc841fe8bEvan Cheng if (CreatedNewVReg) { 98381a038218171860ee4c382849c647d3dc841fe8bEvan Cheng if (DefIsReMat) { 98481a038218171860ee4c382849c647d3dc841fe8bEvan Cheng vrm.setVirtIsReMaterialized(NewVReg, ReMatDefMI/*, CanDelete*/); 985d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng if (ReMatIds[VNI->id] == VirtRegMap::MAX_STACK_SLOT) { 98681a038218171860ee4c382849c647d3dc841fe8bEvan Cheng // Each valnum may have its own remat id. 987d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng ReMatIds[VNI->id] = vrm.assignVirtReMatId(NewVReg); 98881a038218171860ee4c382849c647d3dc841fe8bEvan Cheng } else { 989d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng vrm.assignVirtReMatId(NewVReg, ReMatIds[VNI->id]); 99081a038218171860ee4c382849c647d3dc841fe8bEvan Cheng } 99181a038218171860ee4c382849c647d3dc841fe8bEvan Cheng if (!CanDelete || (HasUse && HasDef)) { 99281a038218171860ee4c382849c647d3dc841fe8bEvan Cheng // If this is a two-addr instruction then its use operands are 99381a038218171860ee4c382849c647d3dc841fe8bEvan Cheng // rematerializable but its def is not. It should be assigned a 99481a038218171860ee4c382849c647d3dc841fe8bEvan Cheng // stack slot. 99581a038218171860ee4c382849c647d3dc841fe8bEvan Cheng vrm.assignVirt2StackSlot(NewVReg, Slot); 99681a038218171860ee4c382849c647d3dc841fe8bEvan Cheng } 997f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng } else { 998f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng vrm.assignVirt2StackSlot(NewVReg, Slot); 999f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng } 1000cb3c330d39442130d0587208d673ce9c33c7008fEvan Cheng } else if (HasUse && HasDef && 1001cb3c330d39442130d0587208d673ce9c33c7008fEvan Cheng vrm.getStackSlot(NewVReg) == VirtRegMap::NO_STACK_SLOT) { 1002cb3c330d39442130d0587208d673ce9c33c7008fEvan Cheng // If this interval hasn't been assigned a stack slot (because earlier 1003cb3c330d39442130d0587208d673ce9c33c7008fEvan Cheng // def is a deleted remat def), do it now. 1004cb3c330d39442130d0587208d673ce9c33c7008fEvan Cheng assert(Slot != VirtRegMap::NO_STACK_SLOT); 1005cb3c330d39442130d0587208d673ce9c33c7008fEvan Cheng vrm.assignVirt2StackSlot(NewVReg, Slot); 1006f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng } 1007f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng 1008313d4b809326f3e04814f94e5b8ae05649d8e0f6Evan Cheng // Re-matting an instruction with virtual register use. Add the 1009313d4b809326f3e04814f94e5b8ae05649d8e0f6Evan Cheng // register as an implicit use on the use MI. 1010313d4b809326f3e04814f94e5b8ae05649d8e0f6Evan Cheng if (DefIsReMat && ImpUse) 1011313d4b809326f3e04814f94e5b8ae05649d8e0f6Evan Cheng MI->addOperand(MachineOperand::CreateReg(ImpUse, false, true)); 1012313d4b809326f3e04814f94e5b8ae05649d8e0f6Evan Cheng 1013f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng // create a new register interval for this spill / remat. 1014f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng LiveInterval &nI = getOrCreateInterval(NewVReg); 101581a038218171860ee4c382849c647d3dc841fe8bEvan Cheng if (CreatedNewVReg) { 101681a038218171860ee4c382849c647d3dc841fe8bEvan Cheng NewLIs.push_back(&nI); 10171953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng MBBVRegsMap.insert(std::make_pair(MI->getParent()->getNumber(), NewVReg)); 101881a038218171860ee4c382849c647d3dc841fe8bEvan Cheng if (TrySplit) 101981a038218171860ee4c382849c647d3dc841fe8bEvan Cheng vrm.setIsSplitFromReg(NewVReg, li.reg); 102081a038218171860ee4c382849c647d3dc841fe8bEvan Cheng } 1021f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng 1022f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng if (HasUse) { 102381a038218171860ee4c382849c647d3dc841fe8bEvan Cheng if (CreatedNewVReg) { 102481a038218171860ee4c382849c647d3dc841fe8bEvan Cheng LiveRange LR(getLoadIndex(index), getUseIndex(index)+1, 102581a038218171860ee4c382849c647d3dc841fe8bEvan Cheng nI.getNextValue(~0U, 0, VNInfoAllocator)); 102681a038218171860ee4c382849c647d3dc841fe8bEvan Cheng DOUT << " +" << LR; 102781a038218171860ee4c382849c647d3dc841fe8bEvan Cheng nI.addRange(LR); 102881a038218171860ee4c382849c647d3dc841fe8bEvan Cheng } else { 102981a038218171860ee4c382849c647d3dc841fe8bEvan Cheng // Extend the split live interval to this def / use. 103081a038218171860ee4c382849c647d3dc841fe8bEvan Cheng unsigned End = getUseIndex(index)+1; 103181a038218171860ee4c382849c647d3dc841fe8bEvan Cheng LiveRange LR(nI.ranges[nI.ranges.size()-1].end, End, 103281a038218171860ee4c382849c647d3dc841fe8bEvan Cheng nI.getValNumInfo(nI.getNumValNums()-1)); 103381a038218171860ee4c382849c647d3dc841fe8bEvan Cheng DOUT << " +" << LR; 103481a038218171860ee4c382849c647d3dc841fe8bEvan Cheng nI.addRange(LR); 103581a038218171860ee4c382849c647d3dc841fe8bEvan Cheng } 1036f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng } 1037f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng if (HasDef) { 1038f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng LiveRange LR(getDefIndex(index), getStoreIndex(index), 1039f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng nI.getNextValue(~0U, 0, VNInfoAllocator)); 1040f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng DOUT << " +" << LR; 1041f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng nI.addRange(LR); 1042f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng } 104381a038218171860ee4c382849c647d3dc841fe8bEvan Cheng 1044f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng DOUT << "\t\t\t\tAdded new interval: "; 10456f0d024a534af18d9e60b3ea757376cd8a3a980eDan Gohman nI.print(DOUT, tri_); 1046f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng DOUT << '\n'; 1047f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng } 1048018f9b020bb12b731b0a7081578e5f82fb35092dEvan Cheng return CanFold; 1049f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng} 105081a038218171860ee4c382849c647d3dc841fe8bEvan Chengbool LiveIntervals::anyKillInMBBAfterIdx(const LiveInterval &li, 10510cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng const VNInfo *VNI, 10520cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng MachineBasicBlock *MBB, unsigned Idx) const { 105381a038218171860ee4c382849c647d3dc841fe8bEvan Cheng unsigned End = getMBBEndIdx(MBB); 10540cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng for (unsigned j = 0, ee = VNI->kills.size(); j != ee; ++j) { 10550cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng unsigned KillIdx = VNI->kills[j]; 10560cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng if (KillIdx > Idx && KillIdx < End) 10570cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng return true; 105881a038218171860ee4c382849c647d3dc841fe8bEvan Cheng } 105981a038218171860ee4c382849c647d3dc841fe8bEvan Cheng return false; 106081a038218171860ee4c382849c647d3dc841fe8bEvan Cheng} 106181a038218171860ee4c382849c647d3dc841fe8bEvan Cheng 10621953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Chengstatic const VNInfo *findDefinedVNInfo(const LiveInterval &li, unsigned DefIdx) { 10631953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng const VNInfo *VNI = NULL; 10641953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng for (LiveInterval::const_vni_iterator i = li.vni_begin(), 10651953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng e = li.vni_end(); i != e; ++i) 10661953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng if ((*i)->def == DefIdx) { 10671953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng VNI = *i; 10681953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng break; 10691953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng } 10701953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng return VNI; 10711953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng} 10721953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng 1073063284c001666c0a3906acbe0a26dc7cae5f081cEvan Cheng/// RewriteInfo - Keep track of machine instrs that will be rewritten 1074063284c001666c0a3906acbe0a26dc7cae5f081cEvan Cheng/// during spilling. 1075063284c001666c0a3906acbe0a26dc7cae5f081cEvan Chengstruct RewriteInfo { 1076063284c001666c0a3906acbe0a26dc7cae5f081cEvan Cheng unsigned Index; 1077063284c001666c0a3906acbe0a26dc7cae5f081cEvan Cheng MachineInstr *MI; 1078063284c001666c0a3906acbe0a26dc7cae5f081cEvan Cheng bool HasUse; 1079063284c001666c0a3906acbe0a26dc7cae5f081cEvan Cheng bool HasDef; 1080063284c001666c0a3906acbe0a26dc7cae5f081cEvan Cheng RewriteInfo(unsigned i, MachineInstr *mi, bool u, bool d) 1081063284c001666c0a3906acbe0a26dc7cae5f081cEvan Cheng : Index(i), MI(mi), HasUse(u), HasDef(d) {} 1082063284c001666c0a3906acbe0a26dc7cae5f081cEvan Cheng}; 1083063284c001666c0a3906acbe0a26dc7cae5f081cEvan Cheng 1084063284c001666c0a3906acbe0a26dc7cae5f081cEvan Chengstruct RewriteInfoCompare { 1085063284c001666c0a3906acbe0a26dc7cae5f081cEvan Cheng bool operator()(const RewriteInfo &LHS, const RewriteInfo &RHS) const { 1086063284c001666c0a3906acbe0a26dc7cae5f081cEvan Cheng return LHS.Index < RHS.Index; 1087063284c001666c0a3906acbe0a26dc7cae5f081cEvan Cheng } 1088063284c001666c0a3906acbe0a26dc7cae5f081cEvan Cheng}; 1089063284c001666c0a3906acbe0a26dc7cae5f081cEvan Cheng 1090f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Chengvoid LiveIntervals:: 109181a038218171860ee4c382849c647d3dc841fe8bEvan ChengrewriteInstructionsForSpills(const LiveInterval &li, bool TrySplit, 1092f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng LiveInterval::Ranges::const_iterator &I, 109381a038218171860ee4c382849c647d3dc841fe8bEvan Cheng MachineInstr *ReMatOrigDefMI, MachineInstr *ReMatDefMI, 1094f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng unsigned Slot, int LdSlot, 1095f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng bool isLoad, bool isLoadSS, bool DefIsReMat, bool CanDelete, 1096d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng VirtRegMap &vrm, 1097f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng const TargetRegisterClass* rc, 1098f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng SmallVector<int, 4> &ReMatIds, 109922f07ffd27d1d721634d502c37267721d2e025cfEvan Cheng const MachineLoopInfo *loopInfo, 110081a038218171860ee4c382849c647d3dc841fe8bEvan Cheng BitVector &SpillMBBs, 11011953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng std::map<unsigned, std::vector<SRInfo> > &SpillIdxes, 11020cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng BitVector &RestoreMBBs, 11031953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng std::map<unsigned, std::vector<SRInfo> > &RestoreIdxes, 11041953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng std::map<unsigned,unsigned> &MBBVRegsMap, 1105f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng std::vector<LiveInterval*> &NewLIs) { 1106018f9b020bb12b731b0a7081578e5f82fb35092dEvan Cheng bool AllCanFold = true; 110781a038218171860ee4c382849c647d3dc841fe8bEvan Cheng unsigned NewVReg = 0; 1108063284c001666c0a3906acbe0a26dc7cae5f081cEvan Cheng unsigned start = getBaseIndex(I->start); 1109f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng unsigned end = getBaseIndex(I->end-1) + InstrSlots::NUM; 1110f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng 1111063284c001666c0a3906acbe0a26dc7cae5f081cEvan Cheng // First collect all the def / use in this live range that will be rewritten. 1112063284c001666c0a3906acbe0a26dc7cae5f081cEvan Cheng // Make sure they are sorted according instruction index. 1113063284c001666c0a3906acbe0a26dc7cae5f081cEvan Cheng std::vector<RewriteInfo> RewriteMIs; 1114d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng for (MachineRegisterInfo::reg_iterator ri = mri_->reg_begin(li.reg), 1115d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng re = mri_->reg_end(); ri != re; ) { 1116063284c001666c0a3906acbe0a26dc7cae5f081cEvan Cheng MachineInstr *MI = &(*ri); 1117063284c001666c0a3906acbe0a26dc7cae5f081cEvan Cheng MachineOperand &O = ri.getOperand(); 1118063284c001666c0a3906acbe0a26dc7cae5f081cEvan Cheng ++ri; 1119063284c001666c0a3906acbe0a26dc7cae5f081cEvan Cheng unsigned index = getInstructionIndex(MI); 1120063284c001666c0a3906acbe0a26dc7cae5f081cEvan Cheng if (index < start || index >= end) 1121063284c001666c0a3906acbe0a26dc7cae5f081cEvan Cheng continue; 1122063284c001666c0a3906acbe0a26dc7cae5f081cEvan Cheng RewriteMIs.push_back(RewriteInfo(index, MI, O.isUse(), O.isDef())); 1123063284c001666c0a3906acbe0a26dc7cae5f081cEvan Cheng } 1124063284c001666c0a3906acbe0a26dc7cae5f081cEvan Cheng std::sort(RewriteMIs.begin(), RewriteMIs.end(), RewriteInfoCompare()); 1125063284c001666c0a3906acbe0a26dc7cae5f081cEvan Cheng 1126313d4b809326f3e04814f94e5b8ae05649d8e0f6Evan Cheng unsigned ImpUse = DefIsReMat ? getReMatImplicitUse(li, ReMatDefMI) : 0; 1127063284c001666c0a3906acbe0a26dc7cae5f081cEvan Cheng // Now rewrite the defs and uses. 1128063284c001666c0a3906acbe0a26dc7cae5f081cEvan Cheng for (unsigned i = 0, e = RewriteMIs.size(); i != e; ) { 1129063284c001666c0a3906acbe0a26dc7cae5f081cEvan Cheng RewriteInfo &rwi = RewriteMIs[i]; 1130063284c001666c0a3906acbe0a26dc7cae5f081cEvan Cheng ++i; 1131063284c001666c0a3906acbe0a26dc7cae5f081cEvan Cheng unsigned index = rwi.Index; 1132063284c001666c0a3906acbe0a26dc7cae5f081cEvan Cheng bool MIHasUse = rwi.HasUse; 1133063284c001666c0a3906acbe0a26dc7cae5f081cEvan Cheng bool MIHasDef = rwi.HasDef; 1134063284c001666c0a3906acbe0a26dc7cae5f081cEvan Cheng MachineInstr *MI = rwi.MI; 1135063284c001666c0a3906acbe0a26dc7cae5f081cEvan Cheng // If MI def and/or use the same register multiple times, then there 1136063284c001666c0a3906acbe0a26dc7cae5f081cEvan Cheng // are multiple entries. 1137313d4b809326f3e04814f94e5b8ae05649d8e0f6Evan Cheng unsigned NumUses = MIHasUse; 1138063284c001666c0a3906acbe0a26dc7cae5f081cEvan Cheng while (i != e && RewriteMIs[i].MI == MI) { 1139063284c001666c0a3906acbe0a26dc7cae5f081cEvan Cheng assert(RewriteMIs[i].Index == index); 1140313d4b809326f3e04814f94e5b8ae05649d8e0f6Evan Cheng bool isUse = RewriteMIs[i].HasUse; 1141313d4b809326f3e04814f94e5b8ae05649d8e0f6Evan Cheng if (isUse) ++NumUses; 1142313d4b809326f3e04814f94e5b8ae05649d8e0f6Evan Cheng MIHasUse |= isUse; 1143063284c001666c0a3906acbe0a26dc7cae5f081cEvan Cheng MIHasDef |= RewriteMIs[i].HasDef; 1144063284c001666c0a3906acbe0a26dc7cae5f081cEvan Cheng ++i; 1145063284c001666c0a3906acbe0a26dc7cae5f081cEvan Cheng } 114681a038218171860ee4c382849c647d3dc841fe8bEvan Cheng MachineBasicBlock *MBB = MI->getParent(); 1147313d4b809326f3e04814f94e5b8ae05649d8e0f6Evan Cheng 1148313d4b809326f3e04814f94e5b8ae05649d8e0f6Evan Cheng if (ImpUse && MI != ReMatDefMI) { 1149313d4b809326f3e04814f94e5b8ae05649d8e0f6Evan Cheng // Re-matting an instruction with virtual register use. Update the 1150313d4b809326f3e04814f94e5b8ae05649d8e0f6Evan Cheng // register interval's spill weight. 1151313d4b809326f3e04814f94e5b8ae05649d8e0f6Evan Cheng unsigned loopDepth = loopInfo->getLoopDepth(MI->getParent()); 1152313d4b809326f3e04814f94e5b8ae05649d8e0f6Evan Cheng LiveInterval &ImpLi = getInterval(ImpUse); 1153313d4b809326f3e04814f94e5b8ae05649d8e0f6Evan Cheng ImpLi.weight += 1154313d4b809326f3e04814f94e5b8ae05649d8e0f6Evan Cheng getSpillWeight(false, true, loopDepth) * NumUses / ImpLi.getSize(); 1155313d4b809326f3e04814f94e5b8ae05649d8e0f6Evan Cheng } 1156313d4b809326f3e04814f94e5b8ae05649d8e0f6Evan Cheng 1157063284c001666c0a3906acbe0a26dc7cae5f081cEvan Cheng unsigned MBBId = MBB->getNumber(); 1158018f9b020bb12b731b0a7081578e5f82fb35092dEvan Cheng unsigned ThisVReg = 0; 115970306f8348f27c61cfed5a60e2fceac0f29746a2Evan Cheng if (TrySplit) { 1160063284c001666c0a3906acbe0a26dc7cae5f081cEvan Cheng std::map<unsigned,unsigned>::const_iterator NVI = MBBVRegsMap.find(MBBId); 11611953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng if (NVI != MBBVRegsMap.end()) { 1162018f9b020bb12b731b0a7081578e5f82fb35092dEvan Cheng ThisVReg = NVI->second; 11631953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng // One common case: 11641953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng // x = use 11651953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng // ... 11661953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng // ... 11671953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng // def = ... 11681953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng // = use 11691953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng // It's better to start a new interval to avoid artifically 11701953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng // extend the new interval. 11711953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng if (MIHasDef && !MIHasUse) { 11721953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng MBBVRegsMap.erase(MBB->getNumber()); 1173018f9b020bb12b731b0a7081578e5f82fb35092dEvan Cheng ThisVReg = 0; 11741953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng } 11751953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng } 1176cada245d06959831b90f8c29f92e77beda4b71cbEvan Cheng } 1177018f9b020bb12b731b0a7081578e5f82fb35092dEvan Cheng 1178018f9b020bb12b731b0a7081578e5f82fb35092dEvan Cheng bool IsNew = ThisVReg == 0; 1179018f9b020bb12b731b0a7081578e5f82fb35092dEvan Cheng if (IsNew) { 1180018f9b020bb12b731b0a7081578e5f82fb35092dEvan Cheng // This ends the previous live interval. If all of its def / use 1181018f9b020bb12b731b0a7081578e5f82fb35092dEvan Cheng // can be folded, give it a low spill weight. 1182018f9b020bb12b731b0a7081578e5f82fb35092dEvan Cheng if (NewVReg && TrySplit && AllCanFold) { 1183018f9b020bb12b731b0a7081578e5f82fb35092dEvan Cheng LiveInterval &nI = getOrCreateInterval(NewVReg); 1184018f9b020bb12b731b0a7081578e5f82fb35092dEvan Cheng nI.weight /= 10.0F; 1185018f9b020bb12b731b0a7081578e5f82fb35092dEvan Cheng } 1186018f9b020bb12b731b0a7081578e5f82fb35092dEvan Cheng AllCanFold = true; 1187018f9b020bb12b731b0a7081578e5f82fb35092dEvan Cheng } 1188018f9b020bb12b731b0a7081578e5f82fb35092dEvan Cheng NewVReg = ThisVReg; 1189018f9b020bb12b731b0a7081578e5f82fb35092dEvan Cheng 119081a038218171860ee4c382849c647d3dc841fe8bEvan Cheng bool HasDef = false; 119181a038218171860ee4c382849c647d3dc841fe8bEvan Cheng bool HasUse = false; 1192d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng bool CanFold = rewriteInstructionForSpills(li, I->valno, TrySplit, 1193018f9b020bb12b731b0a7081578e5f82fb35092dEvan Cheng index, end, MI, ReMatOrigDefMI, ReMatDefMI, 1194018f9b020bb12b731b0a7081578e5f82fb35092dEvan Cheng Slot, LdSlot, isLoad, isLoadSS, DefIsReMat, 1195d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng CanDelete, vrm, rc, ReMatIds, loopInfo, NewVReg, 1196313d4b809326f3e04814f94e5b8ae05649d8e0f6Evan Cheng ImpUse, HasDef, HasUse, MBBVRegsMap, NewLIs); 119781a038218171860ee4c382849c647d3dc841fe8bEvan Cheng if (!HasDef && !HasUse) 119881a038218171860ee4c382849c647d3dc841fe8bEvan Cheng continue; 119981a038218171860ee4c382849c647d3dc841fe8bEvan Cheng 1200018f9b020bb12b731b0a7081578e5f82fb35092dEvan Cheng AllCanFold &= CanFold; 1201018f9b020bb12b731b0a7081578e5f82fb35092dEvan Cheng 120281a038218171860ee4c382849c647d3dc841fe8bEvan Cheng // Update weight of spill interval. 120381a038218171860ee4c382849c647d3dc841fe8bEvan Cheng LiveInterval &nI = getOrCreateInterval(NewVReg); 120470306f8348f27c61cfed5a60e2fceac0f29746a2Evan Cheng if (!TrySplit) { 120581a038218171860ee4c382849c647d3dc841fe8bEvan Cheng // The spill weight is now infinity as it cannot be spilled again. 120681a038218171860ee4c382849c647d3dc841fe8bEvan Cheng nI.weight = HUGE_VALF; 12070cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng continue; 12080cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng } 12090cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng 12100cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng // Keep track of the last def and first use in each MBB. 12110cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng if (HasDef) { 12120cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng if (MI != ReMatOrigDefMI || !CanDelete) { 12130cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng bool HasKill = false; 12140cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng if (!HasUse) 12150cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng HasKill = anyKillInMBBAfterIdx(li, I->valno, MBB, getDefIndex(index)); 12160cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng else { 12171953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng // If this is a two-address code, then this index starts a new VNInfo. 12181953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng const VNInfo *VNI = findDefinedVNInfo(li, getDefIndex(index)); 12190cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng if (VNI) 12200cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng HasKill = anyKillInMBBAfterIdx(li, VNI, MBB, getDefIndex(index)); 122181a038218171860ee4c382849c647d3dc841fe8bEvan Cheng } 1222e3110d0825e6316fd2dd21d6a4e593295cd413f1Evan Cheng std::map<unsigned, std::vector<SRInfo> >::iterator SII = 1223e3110d0825e6316fd2dd21d6a4e593295cd413f1Evan Cheng SpillIdxes.find(MBBId); 12240cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng if (!HasKill) { 12251953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng if (SII == SpillIdxes.end()) { 12261953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng std::vector<SRInfo> S; 12271953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng S.push_back(SRInfo(index, NewVReg, true)); 12281953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng SpillIdxes.insert(std::make_pair(MBBId, S)); 12291953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng } else if (SII->second.back().vreg != NewVReg) { 12301953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng SII->second.push_back(SRInfo(index, NewVReg, true)); 12311953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng } else if ((int)index > SII->second.back().index) { 12320cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng // If there is an earlier def and this is a two-address 12330cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng // instruction, then it's not possible to fold the store (which 12340cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng // would also fold the load). 12351953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng SRInfo &Info = SII->second.back(); 12361953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng Info.index = index; 12371953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng Info.canFold = !HasUse; 123881a038218171860ee4c382849c647d3dc841fe8bEvan Cheng } 12390cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng SpillMBBs.set(MBBId); 1240e3110d0825e6316fd2dd21d6a4e593295cd413f1Evan Cheng } else if (SII != SpillIdxes.end() && 1241e3110d0825e6316fd2dd21d6a4e593295cd413f1Evan Cheng SII->second.back().vreg == NewVReg && 1242e3110d0825e6316fd2dd21d6a4e593295cd413f1Evan Cheng (int)index > SII->second.back().index) { 1243e3110d0825e6316fd2dd21d6a4e593295cd413f1Evan Cheng // There is an earlier def that's not killed (must be two-address). 1244e3110d0825e6316fd2dd21d6a4e593295cd413f1Evan Cheng // The spill is no longer needed. 1245e3110d0825e6316fd2dd21d6a4e593295cd413f1Evan Cheng SII->second.pop_back(); 1246e3110d0825e6316fd2dd21d6a4e593295cd413f1Evan Cheng if (SII->second.empty()) { 1247e3110d0825e6316fd2dd21d6a4e593295cd413f1Evan Cheng SpillIdxes.erase(MBBId); 1248e3110d0825e6316fd2dd21d6a4e593295cd413f1Evan Cheng SpillMBBs.reset(MBBId); 1249e3110d0825e6316fd2dd21d6a4e593295cd413f1Evan Cheng } 125081a038218171860ee4c382849c647d3dc841fe8bEvan Cheng } 125181a038218171860ee4c382849c647d3dc841fe8bEvan Cheng } 12520cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng } 125381a038218171860ee4c382849c647d3dc841fe8bEvan Cheng 12540cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng if (HasUse) { 12551953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng std::map<unsigned, std::vector<SRInfo> >::iterator SII = 12560cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng SpillIdxes.find(MBBId); 12571953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng if (SII != SpillIdxes.end() && 12581953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng SII->second.back().vreg == NewVReg && 12591953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng (int)index > SII->second.back().index) 12600cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng // Use(s) following the last def, it's not safe to fold the spill. 12611953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng SII->second.back().canFold = false; 12621953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng std::map<unsigned, std::vector<SRInfo> >::iterator RII = 12630cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng RestoreIdxes.find(MBBId); 12641953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng if (RII != RestoreIdxes.end() && RII->second.back().vreg == NewVReg) 12650cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng // If we are splitting live intervals, only fold if it's the first 12660cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng // use and there isn't another use later in the MBB. 12671953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng RII->second.back().canFold = false; 12680cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng else if (IsNew) { 12690cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng // Only need a reload if there isn't an earlier def / use. 12701953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng if (RII == RestoreIdxes.end()) { 12711953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng std::vector<SRInfo> Infos; 12721953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng Infos.push_back(SRInfo(index, NewVReg, true)); 12731953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng RestoreIdxes.insert(std::make_pair(MBBId, Infos)); 12741953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng } else { 12751953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng RII->second.push_back(SRInfo(index, NewVReg, true)); 12761953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng } 12770cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng RestoreMBBs.set(MBBId); 12780cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng } 127981a038218171860ee4c382849c647d3dc841fe8bEvan Cheng } 12800cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng 12810cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng // Update spill weight. 128222f07ffd27d1d721634d502c37267721d2e025cfEvan Cheng unsigned loopDepth = loopInfo->getLoopDepth(MBB); 12830cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng nI.weight += getSpillWeight(HasDef, HasUse, loopDepth); 1284f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng } 1285018f9b020bb12b731b0a7081578e5f82fb35092dEvan Cheng 1286018f9b020bb12b731b0a7081578e5f82fb35092dEvan Cheng if (NewVReg && TrySplit && AllCanFold) { 1287018f9b020bb12b731b0a7081578e5f82fb35092dEvan Cheng // If all of its def / use can be folded, give it a low spill weight. 1288018f9b020bb12b731b0a7081578e5f82fb35092dEvan Cheng LiveInterval &nI = getOrCreateInterval(NewVReg); 1289018f9b020bb12b731b0a7081578e5f82fb35092dEvan Cheng nI.weight /= 10.0F; 1290018f9b020bb12b731b0a7081578e5f82fb35092dEvan Cheng } 1291f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng} 1292f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng 12931953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Chengbool LiveIntervals::alsoFoldARestore(int Id, int index, unsigned vr, 12941953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng BitVector &RestoreMBBs, 12951953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng std::map<unsigned,std::vector<SRInfo> > &RestoreIdxes) { 12961953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng if (!RestoreMBBs[Id]) 12971953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng return false; 12981953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng std::vector<SRInfo> &Restores = RestoreIdxes[Id]; 12991953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng for (unsigned i = 0, e = Restores.size(); i != e; ++i) 13001953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng if (Restores[i].index == index && 13011953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng Restores[i].vreg == vr && 13021953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng Restores[i].canFold) 13031953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng return true; 13041953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng return false; 13051953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng} 13061953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng 13071953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Chengvoid LiveIntervals::eraseRestoreInfo(int Id, int index, unsigned vr, 13081953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng BitVector &RestoreMBBs, 13091953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng std::map<unsigned,std::vector<SRInfo> > &RestoreIdxes) { 13101953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng if (!RestoreMBBs[Id]) 13111953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng return; 13121953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng std::vector<SRInfo> &Restores = RestoreIdxes[Id]; 13131953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng for (unsigned i = 0, e = Restores.size(); i != e; ++i) 13141953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng if (Restores[i].index == index && Restores[i].vreg) 13151953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng Restores[i].index = -1; 13161953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng} 131781a038218171860ee4c382849c647d3dc841fe8bEvan Cheng 131881a038218171860ee4c382849c647d3dc841fe8bEvan Cheng 1319f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Chengstd::vector<LiveInterval*> LiveIntervals:: 132081a038218171860ee4c382849c647d3dc841fe8bEvan ChengaddIntervalsForSpills(const LiveInterval &li, 132122f07ffd27d1d721634d502c37267721d2e025cfEvan Cheng const MachineLoopInfo *loopInfo, VirtRegMap &vrm) { 1322f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng // Since this is called after the analysis is done we don't know if 1323f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng // LiveVariables is available 1324f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng lv_ = getAnalysisToUpdate<LiveVariables>(); 1325f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng 1326f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng assert(li.weight != HUGE_VALF && 1327f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng "attempt to spill already spilled interval!"); 1328f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng 1329f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng DOUT << "\t\t\t\tadding intervals for spills for interval: "; 13306f0d024a534af18d9e60b3ea757376cd8a3a980eDan Gohman li.print(DOUT, tri_); 1331f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng DOUT << '\n'; 1332f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng 133381a038218171860ee4c382849c647d3dc841fe8bEvan Cheng // Each bit specify whether it a spill is required in the MBB. 133481a038218171860ee4c382849c647d3dc841fe8bEvan Cheng BitVector SpillMBBs(mf_->getNumBlockIDs()); 13351953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng std::map<unsigned, std::vector<SRInfo> > SpillIdxes; 13360cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng BitVector RestoreMBBs(mf_->getNumBlockIDs()); 13371953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng std::map<unsigned, std::vector<SRInfo> > RestoreIdxes; 13381953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng std::map<unsigned,unsigned> MBBVRegsMap; 1339f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng std::vector<LiveInterval*> NewLIs; 1340d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng const TargetRegisterClass* rc = mri_->getRegClass(li.reg); 1341f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng 1342f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng unsigned NumValNums = li.getNumValNums(); 1343f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng SmallVector<MachineInstr*, 4> ReMatDefs; 1344f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng ReMatDefs.resize(NumValNums, NULL); 1345f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng SmallVector<MachineInstr*, 4> ReMatOrigDefs; 1346f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng ReMatOrigDefs.resize(NumValNums, NULL); 1347f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng SmallVector<int, 4> ReMatIds; 1348f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng ReMatIds.resize(NumValNums, VirtRegMap::MAX_STACK_SLOT); 1349f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng BitVector ReMatDelete(NumValNums); 1350f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng unsigned Slot = VirtRegMap::MAX_STACK_SLOT; 1351f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng 135281a038218171860ee4c382849c647d3dc841fe8bEvan Cheng // Spilling a split live interval. It cannot be split any further. Also, 135381a038218171860ee4c382849c647d3dc841fe8bEvan Cheng // it's also guaranteed to be a single val# / range interval. 135481a038218171860ee4c382849c647d3dc841fe8bEvan Cheng if (vrm.getPreSplitReg(li.reg)) { 135581a038218171860ee4c382849c647d3dc841fe8bEvan Cheng vrm.setIsSplitFromReg(li.reg, 0); 1356d120ffd26f2715c600b028d4eac9a3c41a9f4653Evan Cheng // Unset the split kill marker on the last use. 1357d120ffd26f2715c600b028d4eac9a3c41a9f4653Evan Cheng unsigned KillIdx = vrm.getKillPoint(li.reg); 1358d120ffd26f2715c600b028d4eac9a3c41a9f4653Evan Cheng if (KillIdx) { 1359d120ffd26f2715c600b028d4eac9a3c41a9f4653Evan Cheng MachineInstr *KillMI = getInstructionFromIndex(KillIdx); 1360d120ffd26f2715c600b028d4eac9a3c41a9f4653Evan Cheng assert(KillMI && "Last use disappeared?"); 1361d120ffd26f2715c600b028d4eac9a3c41a9f4653Evan Cheng int KillOp = KillMI->findRegisterUseOperandIdx(li.reg, true); 1362d120ffd26f2715c600b028d4eac9a3c41a9f4653Evan Cheng assert(KillOp != -1 && "Last use disappeared?"); 1363f73823000e2d5d6e1cf65bdf5a107297e18d35fbChris Lattner KillMI->getOperand(KillOp).setIsKill(false); 1364d120ffd26f2715c600b028d4eac9a3c41a9f4653Evan Cheng } 1365adf85906906ebf85c57c333e8209f37ef11a6c99Evan Cheng vrm.removeKillPoint(li.reg); 136681a038218171860ee4c382849c647d3dc841fe8bEvan Cheng bool DefIsReMat = vrm.isReMaterialized(li.reg); 136781a038218171860ee4c382849c647d3dc841fe8bEvan Cheng Slot = vrm.getStackSlot(li.reg); 136881a038218171860ee4c382849c647d3dc841fe8bEvan Cheng assert(Slot != VirtRegMap::MAX_STACK_SLOT); 136981a038218171860ee4c382849c647d3dc841fe8bEvan Cheng MachineInstr *ReMatDefMI = DefIsReMat ? 137081a038218171860ee4c382849c647d3dc841fe8bEvan Cheng vrm.getReMaterializedMI(li.reg) : NULL; 137181a038218171860ee4c382849c647d3dc841fe8bEvan Cheng int LdSlot = 0; 137281a038218171860ee4c382849c647d3dc841fe8bEvan Cheng bool isLoadSS = DefIsReMat && tii_->isLoadFromStackSlot(ReMatDefMI, LdSlot); 137381a038218171860ee4c382849c647d3dc841fe8bEvan Cheng bool isLoad = isLoadSS || 1374749c6f6b5ed301c84aac562e414486549d7b98ebChris Lattner (DefIsReMat && (ReMatDefMI->getDesc().isSimpleLoad())); 137581a038218171860ee4c382849c647d3dc841fe8bEvan Cheng bool IsFirstRange = true; 137681a038218171860ee4c382849c647d3dc841fe8bEvan Cheng for (LiveInterval::Ranges::const_iterator 137781a038218171860ee4c382849c647d3dc841fe8bEvan Cheng I = li.ranges.begin(), E = li.ranges.end(); I != E; ++I) { 137881a038218171860ee4c382849c647d3dc841fe8bEvan Cheng // If this is a split live interval with multiple ranges, it means there 137981a038218171860ee4c382849c647d3dc841fe8bEvan Cheng // are two-address instructions that re-defined the value. Only the 138081a038218171860ee4c382849c647d3dc841fe8bEvan Cheng // first def can be rematerialized! 138181a038218171860ee4c382849c647d3dc841fe8bEvan Cheng if (IsFirstRange) { 1382cb3c330d39442130d0587208d673ce9c33c7008fEvan Cheng // Note ReMatOrigDefMI has already been deleted. 138381a038218171860ee4c382849c647d3dc841fe8bEvan Cheng rewriteInstructionsForSpills(li, false, I, NULL, ReMatDefMI, 138481a038218171860ee4c382849c647d3dc841fe8bEvan Cheng Slot, LdSlot, isLoad, isLoadSS, DefIsReMat, 1385d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng false, vrm, rc, ReMatIds, loopInfo, 13860cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng SpillMBBs, SpillIdxes, RestoreMBBs, RestoreIdxes, 13871953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng MBBVRegsMap, NewLIs); 138881a038218171860ee4c382849c647d3dc841fe8bEvan Cheng } else { 138981a038218171860ee4c382849c647d3dc841fe8bEvan Cheng rewriteInstructionsForSpills(li, false, I, NULL, 0, 139081a038218171860ee4c382849c647d3dc841fe8bEvan Cheng Slot, 0, false, false, false, 1391d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng false, vrm, rc, ReMatIds, loopInfo, 13920cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng SpillMBBs, SpillIdxes, RestoreMBBs, RestoreIdxes, 13931953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng MBBVRegsMap, NewLIs); 139481a038218171860ee4c382849c647d3dc841fe8bEvan Cheng } 139581a038218171860ee4c382849c647d3dc841fe8bEvan Cheng IsFirstRange = false; 139681a038218171860ee4c382849c647d3dc841fe8bEvan Cheng } 139781a038218171860ee4c382849c647d3dc841fe8bEvan Cheng return NewLIs; 139881a038218171860ee4c382849c647d3dc841fe8bEvan Cheng } 139981a038218171860ee4c382849c647d3dc841fe8bEvan Cheng 140081a038218171860ee4c382849c647d3dc841fe8bEvan Cheng bool TrySplit = SplitAtBB && !intervalIsInOneMBB(li); 14010cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng if (SplitLimit != -1 && (int)numSplits >= SplitLimit) 14020cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng TrySplit = false; 14030cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng if (TrySplit) 14040cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng ++numSplits; 1405f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng bool NeedStackSlot = false; 1406f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng for (LiveInterval::const_vni_iterator i = li.vni_begin(), e = li.vni_end(); 1407f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng i != e; ++i) { 1408f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng const VNInfo *VNI = *i; 1409f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng unsigned VN = VNI->id; 1410f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng unsigned DefIdx = VNI->def; 1411f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng if (DefIdx == ~1U) 1412f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng continue; // Dead val#. 1413f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng // Is the def for the val# rematerializable? 141481a038218171860ee4c382849c647d3dc841fe8bEvan Cheng MachineInstr *ReMatDefMI = (DefIdx == ~0u) 141581a038218171860ee4c382849c647d3dc841fe8bEvan Cheng ? 0 : getInstructionFromIndex(DefIdx); 14165ef3a04b542c4e585276768fa9ca2af698ef5c87Evan Cheng bool dummy; 14175ef3a04b542c4e585276768fa9ca2af698ef5c87Evan Cheng if (ReMatDefMI && isReMaterializable(li, VNI, ReMatDefMI, dummy)) { 1418f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng // Remember how to remat the def of this val#. 141981a038218171860ee4c382849c647d3dc841fe8bEvan Cheng ReMatOrigDefs[VN] = ReMatDefMI; 1420f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng // Original def may be modified so we have to make a copy here. vrm must 1421f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng // delete these! 142281a038218171860ee4c382849c647d3dc841fe8bEvan Cheng ReMatDefs[VN] = ReMatDefMI = ReMatDefMI->clone(); 1423f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng 1424f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng bool CanDelete = true; 1425c3fc7d9ec9b495c8a88cd854247105c296d3aabdEvan Cheng if (VNI->hasPHIKill) { 1426c3fc7d9ec9b495c8a88cd854247105c296d3aabdEvan Cheng // A kill is a phi node, not all of its uses can be rematerialized. 1427f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng // It must not be deleted. 1428c3fc7d9ec9b495c8a88cd854247105c296d3aabdEvan Cheng CanDelete = false; 1429c3fc7d9ec9b495c8a88cd854247105c296d3aabdEvan Cheng // Need a stack slot if there is any live range where uses cannot be 1430c3fc7d9ec9b495c8a88cd854247105c296d3aabdEvan Cheng // rematerialized. 1431c3fc7d9ec9b495c8a88cd854247105c296d3aabdEvan Cheng NeedStackSlot = true; 1432f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng } 1433f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng if (CanDelete) 1434f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng ReMatDelete.set(VN); 1435f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng } else { 1436f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng // Need a stack slot if there is any live range where uses cannot be 1437f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng // rematerialized. 1438f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng NeedStackSlot = true; 1439f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng } 1440f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng } 1441f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng 1442f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng // One stack slot per live interval. 144381a038218171860ee4c382849c647d3dc841fe8bEvan Cheng if (NeedStackSlot && vrm.getPreSplitReg(li.reg) == 0) 1444f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng Slot = vrm.assignVirt2StackSlot(li.reg); 1445f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng 1446f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng // Create new intervals and rewrite defs and uses. 1447f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng for (LiveInterval::Ranges::const_iterator 1448f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng I = li.ranges.begin(), E = li.ranges.end(); I != E; ++I) { 144981a038218171860ee4c382849c647d3dc841fe8bEvan Cheng MachineInstr *ReMatDefMI = ReMatDefs[I->valno->id]; 145081a038218171860ee4c382849c647d3dc841fe8bEvan Cheng MachineInstr *ReMatOrigDefMI = ReMatOrigDefs[I->valno->id]; 145181a038218171860ee4c382849c647d3dc841fe8bEvan Cheng bool DefIsReMat = ReMatDefMI != NULL; 1452f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng bool CanDelete = ReMatDelete[I->valno->id]; 1453f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng int LdSlot = 0; 145481a038218171860ee4c382849c647d3dc841fe8bEvan Cheng bool isLoadSS = DefIsReMat && tii_->isLoadFromStackSlot(ReMatDefMI, LdSlot); 1455f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng bool isLoad = isLoadSS || 1456749c6f6b5ed301c84aac562e414486549d7b98ebChris Lattner (DefIsReMat && ReMatDefMI->getDesc().isSimpleLoad()); 145781a038218171860ee4c382849c647d3dc841fe8bEvan Cheng rewriteInstructionsForSpills(li, TrySplit, I, ReMatOrigDefMI, ReMatDefMI, 14580cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng Slot, LdSlot, isLoad, isLoadSS, DefIsReMat, 1459d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng CanDelete, vrm, rc, ReMatIds, loopInfo, 14600cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng SpillMBBs, SpillIdxes, RestoreMBBs, RestoreIdxes, 14611953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng MBBVRegsMap, NewLIs); 1462f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng } 1463f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng 14640cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng // Insert spills / restores if we are splitting. 14651953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng if (!TrySplit) 14661953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng return NewLIs; 14671953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng 1468b50bb8cf197709b3f49044740044c06d8f314564Evan Cheng SmallPtrSet<LiveInterval*, 4> AddedKill; 1469aee4af68ae2016afc5b4ec0c430e539c5810a766Evan Cheng SmallVector<unsigned, 2> Ops; 14701953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng if (NeedStackSlot) { 14711953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng int Id = SpillMBBs.find_first(); 14721953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng while (Id != -1) { 14731953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng std::vector<SRInfo> &spills = SpillIdxes[Id]; 14741953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng for (unsigned i = 0, e = spills.size(); i != e; ++i) { 14751953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng int index = spills[i].index; 14761953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng unsigned VReg = spills[i].vreg; 1477597d10d84fb6b34f7776121404d5ed802b21b2b6Evan Cheng LiveInterval &nI = getOrCreateInterval(VReg); 14780cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng bool isReMat = vrm.isReMaterialized(VReg); 14790cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng MachineInstr *MI = getInstructionFromIndex(index); 1480aee4af68ae2016afc5b4ec0c430e539c5810a766Evan Cheng bool CanFold = false; 1481aee4af68ae2016afc5b4ec0c430e539c5810a766Evan Cheng bool FoundUse = false; 1482aee4af68ae2016afc5b4ec0c430e539c5810a766Evan Cheng Ops.clear(); 1483cddbb83ea82e98658d9f530c50a7b9d23249afc2Evan Cheng if (spills[i].canFold) { 1484aee4af68ae2016afc5b4ec0c430e539c5810a766Evan Cheng CanFold = true; 14850cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng for (unsigned j = 0, ee = MI->getNumOperands(); j != ee; ++j) { 14860cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng MachineOperand &MO = MI->getOperand(j); 14870cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng if (!MO.isRegister() || MO.getReg() != VReg) 14880cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng continue; 1489aee4af68ae2016afc5b4ec0c430e539c5810a766Evan Cheng 1490aee4af68ae2016afc5b4ec0c430e539c5810a766Evan Cheng Ops.push_back(j); 1491aee4af68ae2016afc5b4ec0c430e539c5810a766Evan Cheng if (MO.isDef()) 1492cddbb83ea82e98658d9f530c50a7b9d23249afc2Evan Cheng continue; 1493aee4af68ae2016afc5b4ec0c430e539c5810a766Evan Cheng if (isReMat || 1494aee4af68ae2016afc5b4ec0c430e539c5810a766Evan Cheng (!FoundUse && !alsoFoldARestore(Id, index, VReg, 1495aee4af68ae2016afc5b4ec0c430e539c5810a766Evan Cheng RestoreMBBs, RestoreIdxes))) { 1496aee4af68ae2016afc5b4ec0c430e539c5810a766Evan Cheng // MI has two-address uses of the same register. If the use 1497aee4af68ae2016afc5b4ec0c430e539c5810a766Evan Cheng // isn't the first and only use in the BB, then we can't fold 1498aee4af68ae2016afc5b4ec0c430e539c5810a766Evan Cheng // it. FIXME: Move this to rewriteInstructionsForSpills. 1499aee4af68ae2016afc5b4ec0c430e539c5810a766Evan Cheng CanFold = false; 1500cddbb83ea82e98658d9f530c50a7b9d23249afc2Evan Cheng break; 1501cddbb83ea82e98658d9f530c50a7b9d23249afc2Evan Cheng } 1502aee4af68ae2016afc5b4ec0c430e539c5810a766Evan Cheng FoundUse = true; 15030cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng } 15040cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng } 15050cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng // Fold the store into the def if possible. 1506cddbb83ea82e98658d9f530c50a7b9d23249afc2Evan Cheng bool Folded = false; 1507aee4af68ae2016afc5b4ec0c430e539c5810a766Evan Cheng if (CanFold && !Ops.empty()) { 1508aee4af68ae2016afc5b4ec0c430e539c5810a766Evan Cheng if (tryFoldMemoryOperand(MI, vrm, NULL, index, Ops, true, Slot,VReg)){ 1509cddbb83ea82e98658d9f530c50a7b9d23249afc2Evan Cheng Folded = true; 1510f38d14f03e495ea98ae16bda6febbde276513294Evan Cheng if (FoundUse > 0) { 1511aee4af68ae2016afc5b4ec0c430e539c5810a766Evan Cheng // Also folded uses, do not issue a load. 1512aee4af68ae2016afc5b4ec0c430e539c5810a766Evan Cheng eraseRestoreInfo(Id, index, VReg, RestoreMBBs, RestoreIdxes); 1513f38d14f03e495ea98ae16bda6febbde276513294Evan Cheng nI.removeRange(getLoadIndex(index), getUseIndex(index)+1); 1514f38d14f03e495ea98ae16bda6febbde276513294Evan Cheng } 1515597d10d84fb6b34f7776121404d5ed802b21b2b6Evan Cheng nI.removeRange(getDefIndex(index), getStoreIndex(index)); 1516cddbb83ea82e98658d9f530c50a7b9d23249afc2Evan Cheng } 15170cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng } 15180cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng 1519aee4af68ae2016afc5b4ec0c430e539c5810a766Evan Cheng // Else tell the spiller to issue a spill. 1520b50bb8cf197709b3f49044740044c06d8f314564Evan Cheng if (!Folded) { 1521b50bb8cf197709b3f49044740044c06d8f314564Evan Cheng LiveRange *LR = &nI.ranges[nI.ranges.size()-1]; 1522b50bb8cf197709b3f49044740044c06d8f314564Evan Cheng bool isKill = LR->end == getStoreIndex(index); 1523b50bb8cf197709b3f49044740044c06d8f314564Evan Cheng vrm.addSpillPoint(VReg, isKill, MI); 1524b50bb8cf197709b3f49044740044c06d8f314564Evan Cheng if (isKill) 1525b50bb8cf197709b3f49044740044c06d8f314564Evan Cheng AddedKill.insert(&nI); 1526b50bb8cf197709b3f49044740044c06d8f314564Evan Cheng } 15270cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng } 15281953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng Id = SpillMBBs.find_next(Id); 15290cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng } 15301953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng } 15310cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng 15321953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng int Id = RestoreMBBs.find_first(); 15331953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng while (Id != -1) { 15341953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng std::vector<SRInfo> &restores = RestoreIdxes[Id]; 15351953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng for (unsigned i = 0, e = restores.size(); i != e; ++i) { 15361953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng int index = restores[i].index; 15371953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng if (index == -1) 15381953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng continue; 15391953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng unsigned VReg = restores[i].vreg; 1540597d10d84fb6b34f7776121404d5ed802b21b2b6Evan Cheng LiveInterval &nI = getOrCreateInterval(VReg); 154181a038218171860ee4c382849c647d3dc841fe8bEvan Cheng MachineInstr *MI = getInstructionFromIndex(index); 1542aee4af68ae2016afc5b4ec0c430e539c5810a766Evan Cheng bool CanFold = false; 1543aee4af68ae2016afc5b4ec0c430e539c5810a766Evan Cheng Ops.clear(); 1544cddbb83ea82e98658d9f530c50a7b9d23249afc2Evan Cheng if (restores[i].canFold) { 1545aee4af68ae2016afc5b4ec0c430e539c5810a766Evan Cheng CanFold = true; 154681a038218171860ee4c382849c647d3dc841fe8bEvan Cheng for (unsigned j = 0, ee = MI->getNumOperands(); j != ee; ++j) { 154781a038218171860ee4c382849c647d3dc841fe8bEvan Cheng MachineOperand &MO = MI->getOperand(j); 154881a038218171860ee4c382849c647d3dc841fe8bEvan Cheng if (!MO.isRegister() || MO.getReg() != VReg) 154981a038218171860ee4c382849c647d3dc841fe8bEvan Cheng continue; 1550aee4af68ae2016afc5b4ec0c430e539c5810a766Evan Cheng 15510cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng if (MO.isDef()) { 1552aee4af68ae2016afc5b4ec0c430e539c5810a766Evan Cheng // If this restore were to be folded, it would have been folded 1553aee4af68ae2016afc5b4ec0c430e539c5810a766Evan Cheng // already. 1554aee4af68ae2016afc5b4ec0c430e539c5810a766Evan Cheng CanFold = false; 155581a038218171860ee4c382849c647d3dc841fe8bEvan Cheng break; 155681a038218171860ee4c382849c647d3dc841fe8bEvan Cheng } 1557aee4af68ae2016afc5b4ec0c430e539c5810a766Evan Cheng Ops.push_back(j); 155881a038218171860ee4c382849c647d3dc841fe8bEvan Cheng } 155981a038218171860ee4c382849c647d3dc841fe8bEvan Cheng } 15600cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng 15610cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng // Fold the load into the use if possible. 1562cddbb83ea82e98658d9f530c50a7b9d23249afc2Evan Cheng bool Folded = false; 1563aee4af68ae2016afc5b4ec0c430e539c5810a766Evan Cheng if (CanFold && !Ops.empty()) { 1564aee4af68ae2016afc5b4ec0c430e539c5810a766Evan Cheng if (!vrm.isReMaterialized(VReg)) 1565aee4af68ae2016afc5b4ec0c430e539c5810a766Evan Cheng Folded = tryFoldMemoryOperand(MI, vrm, NULL,index,Ops,true,Slot,VReg); 1566aee4af68ae2016afc5b4ec0c430e539c5810a766Evan Cheng else { 15670cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng MachineInstr *ReMatDefMI = vrm.getReMaterializedMI(VReg); 15680cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng int LdSlot = 0; 15690cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng bool isLoadSS = tii_->isLoadFromStackSlot(ReMatDefMI, LdSlot); 15700cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng // If the rematerializable def is a load, also try to fold it. 1571749c6f6b5ed301c84aac562e414486549d7b98ebChris Lattner if (isLoadSS || ReMatDefMI->getDesc().isSimpleLoad()) 1572aee4af68ae2016afc5b4ec0c430e539c5810a766Evan Cheng Folded = tryFoldMemoryOperand(MI, vrm, ReMatDefMI, index, 1573aee4af68ae2016afc5b4ec0c430e539c5810a766Evan Cheng Ops, isLoadSS, LdSlot, VReg); 1574d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng unsigned ImpUse = getReMatImplicitUse(li, ReMatDefMI); 1575d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng if (ImpUse) { 1576d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng // Re-matting an instruction with virtual register use. Add the 1577d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng // register as an implicit use on the use MI and update the register 1578d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng // interval's spill weight. 1579d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng unsigned loopDepth = loopInfo->getLoopDepth(MI->getParent()); 1580d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng LiveInterval &ImpLi = getInterval(ImpUse); 1581313d4b809326f3e04814f94e5b8ae05649d8e0f6Evan Cheng ImpLi.weight += 1582313d4b809326f3e04814f94e5b8ae05649d8e0f6Evan Cheng getSpillWeight(false, true, loopDepth) / ImpLi.getSize(); 1583313d4b809326f3e04814f94e5b8ae05649d8e0f6Evan Cheng 1584d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng MI->addOperand(MachineOperand::CreateReg(ImpUse, false, true)); 1585d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng } 1586aee4af68ae2016afc5b4ec0c430e539c5810a766Evan Cheng } 15870cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng } 15880cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng // If folding is not possible / failed, then tell the spiller to issue a 15890cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng // load / rematerialization for us. 1590597d10d84fb6b34f7776121404d5ed802b21b2b6Evan Cheng if (Folded) 1591597d10d84fb6b34f7776121404d5ed802b21b2b6Evan Cheng nI.removeRange(getLoadIndex(index), getUseIndex(index)+1); 1592b50bb8cf197709b3f49044740044c06d8f314564Evan Cheng else 15930cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng vrm.addRestorePoint(VReg, MI); 159481a038218171860ee4c382849c647d3dc841fe8bEvan Cheng } 15951953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng Id = RestoreMBBs.find_next(Id); 159681a038218171860ee4c382849c647d3dc841fe8bEvan Cheng } 159781a038218171860ee4c382849c647d3dc841fe8bEvan Cheng 1598b50bb8cf197709b3f49044740044c06d8f314564Evan Cheng // Finalize intervals: add kills, finalize spill weights, and filter out 1599b50bb8cf197709b3f49044740044c06d8f314564Evan Cheng // dead intervals. 1600597d10d84fb6b34f7776121404d5ed802b21b2b6Evan Cheng std::vector<LiveInterval*> RetNewLIs; 1601597d10d84fb6b34f7776121404d5ed802b21b2b6Evan Cheng for (unsigned i = 0, e = NewLIs.size(); i != e; ++i) { 1602597d10d84fb6b34f7776121404d5ed802b21b2b6Evan Cheng LiveInterval *LI = NewLIs[i]; 1603597d10d84fb6b34f7776121404d5ed802b21b2b6Evan Cheng if (!LI->empty()) { 1604597d10d84fb6b34f7776121404d5ed802b21b2b6Evan Cheng LI->weight /= LI->getSize(); 1605b50bb8cf197709b3f49044740044c06d8f314564Evan Cheng if (!AddedKill.count(LI)) { 1606b50bb8cf197709b3f49044740044c06d8f314564Evan Cheng LiveRange *LR = &LI->ranges[LI->ranges.size()-1]; 1607d120ffd26f2715c600b028d4eac9a3c41a9f4653Evan Cheng unsigned LastUseIdx = getBaseIndex(LR->end); 1608d120ffd26f2715c600b028d4eac9a3c41a9f4653Evan Cheng MachineInstr *LastUse = getInstructionFromIndex(LastUseIdx); 16096130f66eaae89f8878590796977678afa8448926Evan Cheng int UseIdx = LastUse->findRegisterUseOperandIdx(LI->reg, false); 1610b50bb8cf197709b3f49044740044c06d8f314564Evan Cheng assert(UseIdx != -1); 1611d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng if (LastUse->getOperand(UseIdx).isImplicit() || 1612d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng LastUse->getDesc().getOperandConstraint(UseIdx,TOI::TIED_TO) == -1){ 1613b50bb8cf197709b3f49044740044c06d8f314564Evan Cheng LastUse->getOperand(UseIdx).setIsKill(); 1614d120ffd26f2715c600b028d4eac9a3c41a9f4653Evan Cheng vrm.addKillPoint(LI->reg, LastUseIdx); 1615adf85906906ebf85c57c333e8209f37ef11a6c99Evan Cheng } 1616b50bb8cf197709b3f49044740044c06d8f314564Evan Cheng } 1617597d10d84fb6b34f7776121404d5ed802b21b2b6Evan Cheng RetNewLIs.push_back(LI); 1618597d10d84fb6b34f7776121404d5ed802b21b2b6Evan Cheng } 1619597d10d84fb6b34f7776121404d5ed802b21b2b6Evan Cheng } 162081a038218171860ee4c382849c647d3dc841fe8bEvan Cheng 1621597d10d84fb6b34f7776121404d5ed802b21b2b6Evan Cheng return RetNewLIs; 1622f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng} 1623