LiveIntervalAnalysis.cpp revision 9382b9310f008a3347e565d76aadda6a97351de9
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" 226d69ba8a6901c69d78488cbc41f8dbf080618fdeDan Gohman#include "llvm/Analysis/AliasAnalysis.h" 23ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos#include "llvm/CodeGen/LiveVariables.h" 24ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos#include "llvm/CodeGen/MachineFrameInfo.h" 25ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos#include "llvm/CodeGen/MachineInstr.h" 2622f07ffd27d1d721634d502c37267721d2e025cfEvan Cheng#include "llvm/CodeGen/MachineLoopInfo.h" 2784bc5427d6883f73cfeae3da640acd011d35c006Chris Lattner#include "llvm/CodeGen/MachineRegisterInfo.h" 28ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos#include "llvm/CodeGen/Passes.h" 296d69ba8a6901c69d78488cbc41f8dbf080618fdeDan Gohman#include "llvm/CodeGen/PseudoSourceValue.h" 306f0d024a534af18d9e60b3ea757376cd8a3a980eDan Gohman#include "llvm/Target/TargetRegisterInfo.h" 31ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos#include "llvm/Target/TargetInstrInfo.h" 32ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos#include "llvm/Target/TargetMachine.h" 33551ccae044b0ff658fe629dd67edd5ffe75d10e8Reid Spencer#include "llvm/Support/CommandLine.h" 34551ccae044b0ff658fe629dd67edd5ffe75d10e8Reid Spencer#include "llvm/Support/Debug.h" 35551ccae044b0ff658fe629dd67edd5ffe75d10e8Reid Spencer#include "llvm/ADT/Statistic.h" 36551ccae044b0ff658fe629dd67edd5ffe75d10e8Reid Spencer#include "llvm/ADT/STLExtras.h" 3720aa474f8fbebde588edc101b90e834df28ce4ceAlkis Evlogimenos#include <algorithm> 3897af751deb9b26fd42fbcee082da9ccc4ded5b45Jeff Cohen#include <cmath> 39ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenosusing namespace llvm; 40ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos 41844731a7f1909f55935e3514c9e713a62d67662eDan Gohman// Hidden options for help debugging. 42844731a7f1909f55935e3514c9e713a62d67662eDan Gohmanstatic cl::opt<bool> DisableReMat("disable-rematerialization", 43844731a7f1909f55935e3514c9e713a62d67662eDan Gohman cl::init(false), cl::Hidden); 44844731a7f1909f55935e3514c9e713a62d67662eDan Gohman 45844731a7f1909f55935e3514c9e713a62d67662eDan Gohmanstatic cl::opt<bool> SplitAtBB("split-intervals-at-bb", 46844731a7f1909f55935e3514c9e713a62d67662eDan Gohman cl::init(true), cl::Hidden); 47844731a7f1909f55935e3514c9e713a62d67662eDan Gohmanstatic cl::opt<int> SplitLimit("split-limit", 48844731a7f1909f55935e3514c9e713a62d67662eDan Gohman cl::init(-1), cl::Hidden); 49bc165e436beb02443abea9736c1b77e2dd7828b6Evan Cheng 504c8f87038ddc0fbcce751f0e2e7c0e564abca096Dan Gohmanstatic cl::opt<bool> EnableAggressiveRemat("aggressive-remat", cl::Hidden); 514c8f87038ddc0fbcce751f0e2e7c0e564abca096Dan Gohman 52cd3245ac45c595da96bb768a55cddc356dff55feChris LattnerSTATISTIC(numIntervals, "Number of original intervals"); 53cd3245ac45c595da96bb768a55cddc356dff55feChris LattnerSTATISTIC(numIntervalsAfter, "Number of intervals after coalescing"); 540cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan ChengSTATISTIC(numFolds , "Number of loads/stores folded into instructions"); 550cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan ChengSTATISTIC(numSplits , "Number of intervals split"); 56cd3245ac45c595da96bb768a55cddc356dff55feChris Lattner 571997473cf72957d0e70322e2fe6fe2ab141c58a6Devang Patelchar LiveIntervals::ID = 0; 58844731a7f1909f55935e3514c9e713a62d67662eDan Gohmanstatic RegisterPass<LiveIntervals> X("liveintervals", "Live Interval Analysis"); 59ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos 60f7da2c7b0c6293c268881628fc351bed7763f1f4Chris Lattnervoid LiveIntervals::getAnalysisUsage(AnalysisUsage &AU) const { 616d69ba8a6901c69d78488cbc41f8dbf080618fdeDan Gohman AU.addRequired<AliasAnalysis>(); 626d69ba8a6901c69d78488cbc41f8dbf080618fdeDan Gohman AU.addPreserved<AliasAnalysis>(); 632513330de8f8020d15d5bc96640a0957b7c733b9David Greene AU.addPreserved<LiveVariables>(); 641a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos AU.addRequired<LiveVariables>(); 6567d65bb69d5cad957cbb6d672dc0b4a19c211a42Bill Wendling AU.addPreservedID(MachineLoopInfoID); 6667d65bb69d5cad957cbb6d672dc0b4a19c211a42Bill Wendling AU.addPreservedID(MachineDominatorsID); 67fcc6350ac9b99d6590f5256d26bfa489b4531fb3Owen Anderson AU.addPreservedID(PHIEliminationID); 68fcc6350ac9b99d6590f5256d26bfa489b4531fb3Owen Anderson AU.addRequiredID(PHIEliminationID); 691a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos AU.addRequiredID(TwoAddressInstructionPassID); 701a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos MachineFunctionPass::getAnalysisUsage(AU); 71ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos} 72ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos 73f7da2c7b0c6293c268881628fc351bed7763f1f4Chris Lattnervoid LiveIntervals::releaseMemory() { 743f32d65912b4da23793dab618d981be2ce11c331Evan Cheng MBB2IdxMap.clear(); 754ca980e7f9ce7b78955307c2d07001a24d3b6befEvan Cheng Idx2MBBMap.clear(); 761a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos mi2iMap_.clear(); 771a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos i2miMap_.clear(); 781a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos r2iMap_.clear(); 79dd199d29b781bc713462f1255b63d3f153bfd9e9Evan Cheng // Release VNInfo memroy regions after all VNInfo objects are dtor'd. 80dd199d29b781bc713462f1255b63d3f153bfd9e9Evan Cheng VNInfoAllocator.Reset(); 811ed9922794cda9dbe295e74674b909287e544632Evan Cheng while (!ClonedMIs.empty()) { 821ed9922794cda9dbe295e74674b909287e544632Evan Cheng MachineInstr *MI = ClonedMIs.back(); 831ed9922794cda9dbe295e74674b909287e544632Evan Cheng ClonedMIs.pop_back(); 841ed9922794cda9dbe295e74674b909287e544632Evan Cheng mf_->DeleteMachineInstr(MI); 851ed9922794cda9dbe295e74674b909287e544632Evan Cheng } 86993141402f57b4d4cbb7f8a3113f19c61688f9b7Evan Cheng} 87993141402f57b4d4cbb7f8a3113f19c61688f9b7Evan Cheng 8880b3ce65e294a28b88c882d44a5e749a2924c9e3Owen Andersonvoid LiveIntervals::computeNumbering() { 8980b3ce65e294a28b88c882d44a5e749a2924c9e3Owen Anderson Index2MiMap OldI2MI = i2miMap_; 907fbad27cfb7298c707e50af10609d463900d7211Owen Anderson std::vector<IdxMBBPair> OldI2MBB = Idx2MBBMap; 9180b3ce65e294a28b88c882d44a5e749a2924c9e3Owen Anderson 9280b3ce65e294a28b88c882d44a5e749a2924c9e3Owen Anderson Idx2MBBMap.clear(); 9380b3ce65e294a28b88c882d44a5e749a2924c9e3Owen Anderson MBB2IdxMap.clear(); 9480b3ce65e294a28b88c882d44a5e749a2924c9e3Owen Anderson mi2iMap_.clear(); 9580b3ce65e294a28b88c882d44a5e749a2924c9e3Owen Anderson i2miMap_.clear(); 9680b3ce65e294a28b88c882d44a5e749a2924c9e3Owen Anderson 97a1566f2e12ce87a5bca30bc0189a0cdbb40136a4Owen Anderson FunctionSize = 0; 98a1566f2e12ce87a5bca30bc0189a0cdbb40136a4Owen Anderson 99428b92eb83b457b71d29d1d4b7900d36a0ce9a53Chris Lattner // Number MachineInstrs and MachineBasicBlocks. 100428b92eb83b457b71d29d1d4b7900d36a0ce9a53Chris Lattner // Initialize MBB indexes to a sentinal. 101549f27d3070195d6647b796841a5291b4549e8e0Evan Cheng MBB2IdxMap.resize(mf_->getNumBlockIDs(), std::make_pair(~0U,~0U)); 102428b92eb83b457b71d29d1d4b7900d36a0ce9a53Chris Lattner 103428b92eb83b457b71d29d1d4b7900d36a0ce9a53Chris Lattner unsigned MIIndex = 0; 104428b92eb83b457b71d29d1d4b7900d36a0ce9a53Chris Lattner for (MachineFunction::iterator MBB = mf_->begin(), E = mf_->end(); 105428b92eb83b457b71d29d1d4b7900d36a0ce9a53Chris Lattner MBB != E; ++MBB) { 106549f27d3070195d6647b796841a5291b4549e8e0Evan Cheng unsigned StartIdx = MIIndex; 1070c9f92e1ff64ee56724eae444a0442b02f83d0a8Evan Cheng 1087fbad27cfb7298c707e50af10609d463900d7211Owen Anderson // Insert an empty slot at the beginning of each block. 1097fbad27cfb7298c707e50af10609d463900d7211Owen Anderson MIIndex += InstrSlots::NUM; 1107fbad27cfb7298c707e50af10609d463900d7211Owen Anderson i2miMap_.push_back(0); 1117fbad27cfb7298c707e50af10609d463900d7211Owen Anderson 112428b92eb83b457b71d29d1d4b7900d36a0ce9a53Chris Lattner for (MachineBasicBlock::iterator I = MBB->begin(), E = MBB->end(); 113428b92eb83b457b71d29d1d4b7900d36a0ce9a53Chris Lattner I != E; ++I) { 114428b92eb83b457b71d29d1d4b7900d36a0ce9a53Chris Lattner bool inserted = mi2iMap_.insert(std::make_pair(I, MIIndex)).second; 1151a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos assert(inserted && "multiple MachineInstr -> index mappings"); 116428b92eb83b457b71d29d1d4b7900d36a0ce9a53Chris Lattner i2miMap_.push_back(I); 117428b92eb83b457b71d29d1d4b7900d36a0ce9a53Chris Lattner MIIndex += InstrSlots::NUM; 118a1566f2e12ce87a5bca30bc0189a0cdbb40136a4Owen Anderson FunctionSize++; 1197fbad27cfb7298c707e50af10609d463900d7211Owen Anderson 1207fbad27cfb7298c707e50af10609d463900d7211Owen Anderson // Insert an empty slot after every instruction. 1211fbb4545d41e65191ae66a7302276fa5424518c5Owen Anderson MIIndex += InstrSlots::NUM; 1221fbb4545d41e65191ae66a7302276fa5424518c5Owen Anderson i2miMap_.push_back(0); 123355780128986e375c7ac2a75025ac129bb8280bfOwen Anderson } 1247fbad27cfb7298c707e50af10609d463900d7211Owen Anderson 1251fbb4545d41e65191ae66a7302276fa5424518c5Owen Anderson // Set the MBB2IdxMap entry for this MBB. 1261fbb4545d41e65191ae66a7302276fa5424518c5Owen Anderson MBB2IdxMap[MBB->getNumber()] = std::make_pair(StartIdx, MIIndex - 1); 1271fbb4545d41e65191ae66a7302276fa5424518c5Owen Anderson Idx2MBBMap.push_back(std::make_pair(StartIdx, MBB)); 128428b92eb83b457b71d29d1d4b7900d36a0ce9a53Chris Lattner } 1294ca980e7f9ce7b78955307c2d07001a24d3b6befEvan Cheng std::sort(Idx2MBBMap.begin(), Idx2MBBMap.end(), Idx2MBBCompare()); 13080b3ce65e294a28b88c882d44a5e749a2924c9e3Owen Anderson 13180b3ce65e294a28b88c882d44a5e749a2924c9e3Owen Anderson if (!OldI2MI.empty()) 1327fbad27cfb7298c707e50af10609d463900d7211Owen Anderson for (iterator OI = begin(), OE = end(); OI != OE; ++OI) 1337fbad27cfb7298c707e50af10609d463900d7211Owen Anderson for (LiveInterval::iterator LI = OI->second.begin(), 1347fbad27cfb7298c707e50af10609d463900d7211Owen Anderson LE = OI->second.end(); LI != LE; ++LI) { 1357eec0c243320fb2629554681547d7384ea9d0c53Owen Anderson 1367eec0c243320fb2629554681547d7384ea9d0c53Owen Anderson // Remap the start index of the live range to the corresponding new 1377eec0c243320fb2629554681547d7384ea9d0c53Owen Anderson // number, or our best guess at what it _should_ correspond to if the 1387eec0c243320fb2629554681547d7384ea9d0c53Owen Anderson // original instruction has been erased. This is either the following 1397eec0c243320fb2629554681547d7384ea9d0c53Owen Anderson // instruction or its predecessor. 1407fbad27cfb7298c707e50af10609d463900d7211Owen Anderson unsigned index = LI->start / InstrSlots::NUM; 1414b5b209679f866d3ac6372f963aa7e9906f9a08bOwen Anderson unsigned offset = LI->start % InstrSlots::NUM; 1420a7615af25542d5e7d824b520f94094cdc8a2179Owen Anderson if (offset == InstrSlots::LOAD) { 1437fbad27cfb7298c707e50af10609d463900d7211Owen Anderson std::vector<IdxMBBPair>::const_iterator I = 144d7dcbecdbcf5d7a1efc5ed65ddcc26bb8c20c1e6Owen Anderson std::lower_bound(OldI2MBB.begin(), OldI2MBB.end(), LI->start); 1457fbad27cfb7298c707e50af10609d463900d7211Owen Anderson // Take the pair containing the index 1467fbad27cfb7298c707e50af10609d463900d7211Owen Anderson std::vector<IdxMBBPair>::const_iterator J = 147a0c032f9b2eeae3a436850eaca54de4c6a5f23b6Owen Anderson (I == OldI2MBB.end() && OldI2MBB.size()>0) ? (I-1): I; 1487eec0c243320fb2629554681547d7384ea9d0c53Owen Anderson 1497fbad27cfb7298c707e50af10609d463900d7211Owen Anderson LI->start = getMBBStartIdx(J->second); 1507fbad27cfb7298c707e50af10609d463900d7211Owen Anderson } else { 1517fbad27cfb7298c707e50af10609d463900d7211Owen Anderson LI->start = mi2iMap_[OldI2MI[index]] + offset; 1527eec0c243320fb2629554681547d7384ea9d0c53Owen Anderson } 1534b5b209679f866d3ac6372f963aa7e9906f9a08bOwen Anderson 1547eec0c243320fb2629554681547d7384ea9d0c53Owen Anderson // Remap the ending index in the same way that we remapped the start, 1557eec0c243320fb2629554681547d7384ea9d0c53Owen Anderson // except for the final step where we always map to the immediately 1567eec0c243320fb2629554681547d7384ea9d0c53Owen Anderson // following instruction. 157d7dcbecdbcf5d7a1efc5ed65ddcc26bb8c20c1e6Owen Anderson index = (LI->end - 1) / InstrSlots::NUM; 1587fbad27cfb7298c707e50af10609d463900d7211Owen Anderson offset = LI->end % InstrSlots::NUM; 1599382b9310f008a3347e565d76aadda6a97351de9Owen Anderson if (offset == InstrSlots::LOAD) { 1609382b9310f008a3347e565d76aadda6a97351de9Owen Anderson // VReg dies at end of block. 1617fbad27cfb7298c707e50af10609d463900d7211Owen Anderson std::vector<IdxMBBPair>::const_iterator I = 162d7dcbecdbcf5d7a1efc5ed65ddcc26bb8c20c1e6Owen Anderson std::lower_bound(OldI2MBB.begin(), OldI2MBB.end(), LI->end); 1639382b9310f008a3347e565d76aadda6a97351de9Owen Anderson --I; 1647fbad27cfb7298c707e50af10609d463900d7211Owen Anderson 1659382b9310f008a3347e565d76aadda6a97351de9Owen Anderson LI->end = getMBBEndIdx(I->second) + 1; 1664b5b209679f866d3ac6372f963aa7e9906f9a08bOwen Anderson } else { 167d7dcbecdbcf5d7a1efc5ed65ddcc26bb8c20c1e6Owen Anderson unsigned idx = index; 1688d0cc0af5a4b4c08eb74b6e36761651b63816d06Owen Anderson while (index < OldI2MI.size() && !OldI2MI[index]) ++index; 1698d0cc0af5a4b4c08eb74b6e36761651b63816d06Owen Anderson 1708d0cc0af5a4b4c08eb74b6e36761651b63816d06Owen Anderson if (index != OldI2MI.size()) 1718d0cc0af5a4b4c08eb74b6e36761651b63816d06Owen Anderson LI->end = mi2iMap_[OldI2MI[index]] + (idx == index ? offset : 0); 1728d0cc0af5a4b4c08eb74b6e36761651b63816d06Owen Anderson else 1738d0cc0af5a4b4c08eb74b6e36761651b63816d06Owen Anderson LI->end = InstrSlots::NUM * i2miMap_.size(); 1744b5b209679f866d3ac6372f963aa7e9906f9a08bOwen Anderson } 175745825f431920662e97bdab5c1bcfac62e48c52fOwen Anderson 1767eec0c243320fb2629554681547d7384ea9d0c53Owen Anderson // Remap the VNInfo def index, which works the same as the 1777eec0c243320fb2629554681547d7384ea9d0c53Owen Anderson // start indices above. 178745825f431920662e97bdab5c1bcfac62e48c52fOwen Anderson VNInfo* vni = LI->valno; 1790a7615af25542d5e7d824b520f94094cdc8a2179Owen Anderson index = vni->def / InstrSlots::NUM; 1800a7615af25542d5e7d824b520f94094cdc8a2179Owen Anderson offset = vni->def % InstrSlots::NUM; 1810a7615af25542d5e7d824b520f94094cdc8a2179Owen Anderson if (offset == InstrSlots::LOAD) { 1820a7615af25542d5e7d824b520f94094cdc8a2179Owen Anderson std::vector<IdxMBBPair>::const_iterator I = 1830a7615af25542d5e7d824b520f94094cdc8a2179Owen Anderson std::lower_bound(OldI2MBB.begin(), OldI2MBB.end(), vni->def); 1840a7615af25542d5e7d824b520f94094cdc8a2179Owen Anderson // Take the pair containing the index 1850a7615af25542d5e7d824b520f94094cdc8a2179Owen Anderson std::vector<IdxMBBPair>::const_iterator J = 186a0c032f9b2eeae3a436850eaca54de4c6a5f23b6Owen Anderson (I == OldI2MBB.end() && OldI2MBB.size()>0) ? (I-1): I; 1877eec0c243320fb2629554681547d7384ea9d0c53Owen Anderson 1880a7615af25542d5e7d824b520f94094cdc8a2179Owen Anderson vni->def = getMBBStartIdx(J->second); 1897fbad27cfb7298c707e50af10609d463900d7211Owen Anderson 1900a7615af25542d5e7d824b520f94094cdc8a2179Owen Anderson } else { 1910a7615af25542d5e7d824b520f94094cdc8a2179Owen Anderson vni->def = mi2iMap_[OldI2MI[index]] + offset; 1927eec0c243320fb2629554681547d7384ea9d0c53Owen Anderson } 193745825f431920662e97bdab5c1bcfac62e48c52fOwen Anderson 1947eec0c243320fb2629554681547d7384ea9d0c53Owen Anderson // Remap the VNInfo kill indices, which works the same as 1957eec0c243320fb2629554681547d7384ea9d0c53Owen Anderson // the end indices above. 1964b5b209679f866d3ac6372f963aa7e9906f9a08bOwen Anderson for (size_t i = 0; i < vni->kills.size(); ++i) { 1979382b9310f008a3347e565d76aadda6a97351de9Owen Anderson // PHI kills don't need to be remapped. 1989382b9310f008a3347e565d76aadda6a97351de9Owen Anderson if (!vni->kills[i]) continue; 1999382b9310f008a3347e565d76aadda6a97351de9Owen Anderson 200d7dcbecdbcf5d7a1efc5ed65ddcc26bb8c20c1e6Owen Anderson index = (vni->kills[i]-1) / InstrSlots::NUM; 2014b5b209679f866d3ac6372f963aa7e9906f9a08bOwen Anderson offset = vni->kills[i] % InstrSlots::NUM; 2029382b9310f008a3347e565d76aadda6a97351de9Owen Anderson if (offset == InstrSlots::LOAD) { 2037fbad27cfb7298c707e50af10609d463900d7211Owen Anderson std::vector<IdxMBBPair>::const_iterator I = 204d7dcbecdbcf5d7a1efc5ed65ddcc26bb8c20c1e6Owen Anderson std::lower_bound(OldI2MBB.begin(), OldI2MBB.end(), vni->kills[i]); 2059382b9310f008a3347e565d76aadda6a97351de9Owen Anderson --I; 2067fbad27cfb7298c707e50af10609d463900d7211Owen Anderson 2079382b9310f008a3347e565d76aadda6a97351de9Owen Anderson vni->kills[i] = getMBBEndIdx(I->second) + 1; 2087fbad27cfb7298c707e50af10609d463900d7211Owen Anderson } else { 209d7dcbecdbcf5d7a1efc5ed65ddcc26bb8c20c1e6Owen Anderson unsigned idx = index; 210d7dcbecdbcf5d7a1efc5ed65ddcc26bb8c20c1e6Owen Anderson while (!OldI2MI[index]) ++index; 2118d0cc0af5a4b4c08eb74b6e36761651b63816d06Owen Anderson while (index < OldI2MI.size() && !OldI2MI[index]) ++index; 2128d0cc0af5a4b4c08eb74b6e36761651b63816d06Owen Anderson 2138d0cc0af5a4b4c08eb74b6e36761651b63816d06Owen Anderson if (index != OldI2MI.size()) 2148d0cc0af5a4b4c08eb74b6e36761651b63816d06Owen Anderson vni->kills[i] = mi2iMap_[OldI2MI[index]] + 2158d0cc0af5a4b4c08eb74b6e36761651b63816d06Owen Anderson (idx == index ? offset : 0); 2168d0cc0af5a4b4c08eb74b6e36761651b63816d06Owen Anderson else 2178d0cc0af5a4b4c08eb74b6e36761651b63816d06Owen Anderson vni->kills[i] = InstrSlots::NUM * i2miMap_.size(); 2187eec0c243320fb2629554681547d7384ea9d0c53Owen Anderson } 2194b5b209679f866d3ac6372f963aa7e9906f9a08bOwen Anderson } 22080b3ce65e294a28b88c882d44a5e749a2924c9e3Owen Anderson } 22180b3ce65e294a28b88c882d44a5e749a2924c9e3Owen Anderson} 22280b3ce65e294a28b88c882d44a5e749a2924c9e3Owen Anderson 22380b3ce65e294a28b88c882d44a5e749a2924c9e3Owen Anderson/// runOnMachineFunction - Register allocate the whole function 22480b3ce65e294a28b88c882d44a5e749a2924c9e3Owen Anderson/// 22580b3ce65e294a28b88c882d44a5e749a2924c9e3Owen Andersonbool LiveIntervals::runOnMachineFunction(MachineFunction &fn) { 22680b3ce65e294a28b88c882d44a5e749a2924c9e3Owen Anderson mf_ = &fn; 22780b3ce65e294a28b88c882d44a5e749a2924c9e3Owen Anderson mri_ = &mf_->getRegInfo(); 22880b3ce65e294a28b88c882d44a5e749a2924c9e3Owen Anderson tm_ = &fn.getTarget(); 22980b3ce65e294a28b88c882d44a5e749a2924c9e3Owen Anderson tri_ = tm_->getRegisterInfo(); 23080b3ce65e294a28b88c882d44a5e749a2924c9e3Owen Anderson tii_ = tm_->getInstrInfo(); 2316d69ba8a6901c69d78488cbc41f8dbf080618fdeDan Gohman aa_ = &getAnalysis<AliasAnalysis>(); 23280b3ce65e294a28b88c882d44a5e749a2924c9e3Owen Anderson lv_ = &getAnalysis<LiveVariables>(); 23380b3ce65e294a28b88c882d44a5e749a2924c9e3Owen Anderson allocatableRegs_ = tri_->getAllocatableSet(fn); 234ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos 23580b3ce65e294a28b88c882d44a5e749a2924c9e3Owen Anderson computeNumbering(); 2361a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos computeIntervals(); 237ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos 2381a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos numIntervals += getNumIntervals(); 239843b160a2040b3ec4d3452678450afa11704c473Alkis Evlogimenos 240bdc679d564e67a81792e463f6614b0088f975025Bill Wendling DOUT << "********** INTERVALS **********\n"; 241bdc679d564e67a81792e463f6614b0088f975025Bill Wendling for (iterator I = begin(), E = end(); I != E; ++I) { 2426f0d024a534af18d9e60b3ea757376cd8a3a980eDan Gohman I->second.print(DOUT, tri_); 243bdc679d564e67a81792e463f6614b0088f975025Bill Wendling DOUT << "\n"; 244bdc679d564e67a81792e463f6614b0088f975025Bill Wendling } 2457ac2d3146a196fa0120c579ecd2ddd69652ad230Chris Lattner 2461a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos numIntervalsAfter += getNumIntervals(); 24770ca358b7d540b6061236ddf757085042873c12cChris Lattner DEBUG(dump()); 2481a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos return true; 249ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos} 250ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos 25170ca358b7d540b6061236ddf757085042873c12cChris Lattner/// print - Implement the dump method. 252ce9653ce449f1409815547e1bf60abcd1332d2c9Reid Spencervoid LiveIntervals::print(std::ostream &O, const Module* ) const { 25370ca358b7d540b6061236ddf757085042873c12cChris Lattner O << "********** INTERVALS **********\n"; 2548e7a70976deee78a84099b916591d40f7a1cdc34Chris Lattner for (const_iterator I = begin(), E = end(); I != E; ++I) { 2553f32d65912b4da23793dab618d981be2ce11c331Evan Cheng I->second.print(O, tri_); 2563f32d65912b4da23793dab618d981be2ce11c331Evan Cheng O << "\n"; 2578e7a70976deee78a84099b916591d40f7a1cdc34Chris Lattner } 25870ca358b7d540b6061236ddf757085042873c12cChris Lattner 25970ca358b7d540b6061236ddf757085042873c12cChris Lattner O << "********** MACHINEINSTRS **********\n"; 26070ca358b7d540b6061236ddf757085042873c12cChris Lattner for (MachineFunction::iterator mbbi = mf_->begin(), mbbe = mf_->end(); 26170ca358b7d540b6061236ddf757085042873c12cChris Lattner mbbi != mbbe; ++mbbi) { 26270ca358b7d540b6061236ddf757085042873c12cChris Lattner O << ((Value*)mbbi->getBasicBlock())->getName() << ":\n"; 26370ca358b7d540b6061236ddf757085042873c12cChris Lattner for (MachineBasicBlock::iterator mii = mbbi->begin(), 26470ca358b7d540b6061236ddf757085042873c12cChris Lattner mie = mbbi->end(); mii != mie; ++mii) { 265477e4555de341c5de780de3720d6f115ec133c4eChris Lattner O << getInstructionIndex(mii) << '\t' << *mii; 26670ca358b7d540b6061236ddf757085042873c12cChris Lattner } 26770ca358b7d540b6061236ddf757085042873c12cChris Lattner } 26870ca358b7d540b6061236ddf757085042873c12cChris Lattner} 26970ca358b7d540b6061236ddf757085042873c12cChris Lattner 270c92da3882ee4e18153bb36fcdf33af393aba8259Evan Cheng/// conflictsWithPhysRegDef - Returns true if the specified register 271c92da3882ee4e18153bb36fcdf33af393aba8259Evan Cheng/// is defined during the duration of the specified interval. 272c92da3882ee4e18153bb36fcdf33af393aba8259Evan Chengbool LiveIntervals::conflictsWithPhysRegDef(const LiveInterval &li, 273c92da3882ee4e18153bb36fcdf33af393aba8259Evan Cheng VirtRegMap &vrm, unsigned reg) { 274c92da3882ee4e18153bb36fcdf33af393aba8259Evan Cheng for (LiveInterval::Ranges::const_iterator 275c92da3882ee4e18153bb36fcdf33af393aba8259Evan Cheng I = li.ranges.begin(), E = li.ranges.end(); I != E; ++I) { 276c92da3882ee4e18153bb36fcdf33af393aba8259Evan Cheng for (unsigned index = getBaseIndex(I->start), 277c92da3882ee4e18153bb36fcdf33af393aba8259Evan Cheng end = getBaseIndex(I->end-1) + InstrSlots::NUM; index != end; 278c92da3882ee4e18153bb36fcdf33af393aba8259Evan Cheng index += InstrSlots::NUM) { 279c92da3882ee4e18153bb36fcdf33af393aba8259Evan Cheng // skip deleted instructions 280c92da3882ee4e18153bb36fcdf33af393aba8259Evan Cheng while (index != end && !getInstructionFromIndex(index)) 281c92da3882ee4e18153bb36fcdf33af393aba8259Evan Cheng index += InstrSlots::NUM; 282c92da3882ee4e18153bb36fcdf33af393aba8259Evan Cheng if (index == end) break; 283c92da3882ee4e18153bb36fcdf33af393aba8259Evan Cheng 284c92da3882ee4e18153bb36fcdf33af393aba8259Evan Cheng MachineInstr *MI = getInstructionFromIndex(index); 2855d446265c740c17ed12e693423f0363296670d60Evan Cheng unsigned SrcReg, DstReg; 2865d446265c740c17ed12e693423f0363296670d60Evan Cheng if (tii_->isMoveInstr(*MI, SrcReg, DstReg)) 2875d446265c740c17ed12e693423f0363296670d60Evan Cheng if (SrcReg == li.reg || DstReg == li.reg) 2885d446265c740c17ed12e693423f0363296670d60Evan Cheng continue; 289c92da3882ee4e18153bb36fcdf33af393aba8259Evan Cheng for (unsigned i = 0; i != MI->getNumOperands(); ++i) { 290c92da3882ee4e18153bb36fcdf33af393aba8259Evan Cheng MachineOperand& mop = MI->getOperand(i); 2915d446265c740c17ed12e693423f0363296670d60Evan Cheng if (!mop.isRegister()) 292c92da3882ee4e18153bb36fcdf33af393aba8259Evan Cheng continue; 293c92da3882ee4e18153bb36fcdf33af393aba8259Evan Cheng unsigned PhysReg = mop.getReg(); 2945d446265c740c17ed12e693423f0363296670d60Evan Cheng if (PhysReg == 0 || PhysReg == li.reg) 295c92da3882ee4e18153bb36fcdf33af393aba8259Evan Cheng continue; 2966f0d024a534af18d9e60b3ea757376cd8a3a980eDan Gohman if (TargetRegisterInfo::isVirtualRegister(PhysReg)) { 2975d446265c740c17ed12e693423f0363296670d60Evan Cheng if (!vrm.hasPhys(PhysReg)) 2985d446265c740c17ed12e693423f0363296670d60Evan Cheng continue; 299c92da3882ee4e18153bb36fcdf33af393aba8259Evan Cheng PhysReg = vrm.getPhys(PhysReg); 3005d446265c740c17ed12e693423f0363296670d60Evan Cheng } 3016f0d024a534af18d9e60b3ea757376cd8a3a980eDan Gohman if (PhysReg && tri_->regsOverlap(PhysReg, reg)) 302c92da3882ee4e18153bb36fcdf33af393aba8259Evan Cheng return true; 303c92da3882ee4e18153bb36fcdf33af393aba8259Evan Cheng } 304c92da3882ee4e18153bb36fcdf33af393aba8259Evan Cheng } 305c92da3882ee4e18153bb36fcdf33af393aba8259Evan Cheng } 306c92da3882ee4e18153bb36fcdf33af393aba8259Evan Cheng 307c92da3882ee4e18153bb36fcdf33af393aba8259Evan Cheng return false; 308c92da3882ee4e18153bb36fcdf33af393aba8259Evan Cheng} 309c92da3882ee4e18153bb36fcdf33af393aba8259Evan Cheng 310be4f88a8b8bb3311e0dc4cde8533763d7923c3eaChris Lattnervoid LiveIntervals::printRegName(unsigned reg) const { 3116f0d024a534af18d9e60b3ea757376cd8a3a980eDan Gohman if (TargetRegisterInfo::isPhysicalRegister(reg)) 312e6d088acc90e422451e098555d383d4d65b6ce6bBill Wendling cerr << tri_->getName(reg); 3131a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos else 314e81561909d128c6e2d8033cb5465a49b2596b26aBill Wendling cerr << "%reg" << reg; 315ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos} 316ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos 317be4f88a8b8bb3311e0dc4cde8533763d7923c3eaChris Lattnervoid LiveIntervals::handleVirtualRegisterDef(MachineBasicBlock *mbb, 318ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos MachineBasicBlock::iterator mi, 3196b098dee286cc6fe5a5a476464d92dec5602e406Owen Anderson unsigned MIIdx, MachineOperand& MO, 320ef0732d25a9882c947984ae3f2afbef5463ba00fEvan Cheng unsigned MOIdx, 321be4f88a8b8bb3311e0dc4cde8533763d7923c3eaChris Lattner LiveInterval &interval) { 322bdc679d564e67a81792e463f6614b0088f975025Bill Wendling DOUT << "\t\tregister: "; DEBUG(printRegName(interval.reg)); 3231a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos LiveVariables::VarInfo& vi = lv_->getVarInfo(interval.reg); 3241a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos 325419852ca8a01aecde4c0e20af6b7bd6450e70f87Evan Cheng if (mi->getOpcode() == TargetInstrInfo::IMPLICIT_DEF) { 326419852ca8a01aecde4c0e20af6b7bd6450e70f87Evan Cheng DOUT << "is a implicit_def\n"; 327419852ca8a01aecde4c0e20af6b7bd6450e70f87Evan Cheng return; 328419852ca8a01aecde4c0e20af6b7bd6450e70f87Evan Cheng } 329419852ca8a01aecde4c0e20af6b7bd6450e70f87Evan Cheng 330706515727c6d024015fffded2b3109a4f0ac5299Alkis Evlogimenos // Virtual registers may be defined multiple times (due to phi 331706515727c6d024015fffded2b3109a4f0ac5299Alkis Evlogimenos // elimination and 2-addr elimination). Much of what we do only has to be 332706515727c6d024015fffded2b3109a4f0ac5299Alkis Evlogimenos // done once for the vreg. We use an empty interval to detect the first 3331a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // time we see a vreg. 3341a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos if (interval.empty()) { 3351a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // Get the Idx of the defining instructions. 3366b128bdc58a496e9f08e4d09416330320761baffChris Lattner unsigned defIndex = getDefIndex(MIIdx); 3377ecb38be0a533e7b9c7d3b8e9b5c8a6fa5f6b349Evan Cheng VNInfo *ValNo; 338c8d044e4f779fdcfc5e7d592927740fd8f672a70Evan Cheng MachineInstr *CopyMI = NULL; 33991725b75852443923b419fd23215194cfc65dd88Chris Lattner unsigned SrcReg, DstReg; 340c8d044e4f779fdcfc5e7d592927740fd8f672a70Evan Cheng if (mi->getOpcode() == TargetInstrInfo::EXTRACT_SUBREG || 3417e073baedb8232b9519dbe15ea141ff98ccfe6aeEvan Cheng mi->getOpcode() == TargetInstrInfo::INSERT_SUBREG || 342c8d044e4f779fdcfc5e7d592927740fd8f672a70Evan Cheng tii_->isMoveInstr(*mi, SrcReg, DstReg)) 343c8d044e4f779fdcfc5e7d592927740fd8f672a70Evan Cheng CopyMI = mi; 344c8d044e4f779fdcfc5e7d592927740fd8f672a70Evan Cheng ValNo = interval.getNextValue(defIndex, CopyMI, VNInfoAllocator); 3457ecb38be0a533e7b9c7d3b8e9b5c8a6fa5f6b349Evan Cheng 3467ecb38be0a533e7b9c7d3b8e9b5c8a6fa5f6b349Evan Cheng assert(ValNo->id == 0 && "First value in interval is not 0?"); 3471a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos 3481a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // Loop over all of the blocks that the vreg is defined in. There are 3491a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // two cases we have to handle here. The most common case is a vreg 3501a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // whose lifetime is contained within a basic block. In this case there 3511a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // will be a single kill, in MBB, which comes after the definition. 3521a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos if (vi.Kills.size() == 1 && vi.Kills[0]->getParent() == mbb) { 3531a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // FIXME: what about dead vars? 3541a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos unsigned killIdx; 3551a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos if (vi.Kills[0] != mi) 3561a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos killIdx = getUseIndex(getInstructionIndex(vi.Kills[0]))+1; 3571a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos else 3581a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos killIdx = defIndex+1; 3591a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos 3601a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // If the kill happens after the definition, we have an intra-block 3611a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // live range. 3621a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos if (killIdx > defIndex) { 36361de82d8853a02fe39c47302432abb70a586704fEvan Cheng assert(vi.AliveBlocks.none() && 3641a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos "Shouldn't be alive across any blocks!"); 3657ecb38be0a533e7b9c7d3b8e9b5c8a6fa5f6b349Evan Cheng LiveRange LR(defIndex, killIdx, ValNo); 3661a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos interval.addRange(LR); 367bdc679d564e67a81792e463f6614b0088f975025Bill Wendling DOUT << " +" << LR << "\n"; 368f3bb2e65d12857f83b273f4ecab013680310bbbcEvan Cheng interval.addKill(ValNo, killIdx); 3691a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos return; 3701a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos } 3711a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos } 3726097d13b2a624048dbe02e39e2dfb23bfa269b64Chris Lattner 3731a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // The other case we handle is when a virtual register lives to the end 3741a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // of the defining block, potentially live across some blocks, then is 3751a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // live into some number of blocks, but gets killed. Start by adding a 3761a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // range that goes from this definition to the end of the defining block. 3777fbad27cfb7298c707e50af10609d463900d7211Owen Anderson LiveRange NewLR(defIndex, getMBBEndIdx(mbb)+1, ValNo); 378bdc679d564e67a81792e463f6614b0088f975025Bill Wendling DOUT << " +" << NewLR; 3791a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos interval.addRange(NewLR); 3801a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos 3811a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // Iterate over all of the blocks that the variable is completely 3821a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // live in, adding [insrtIndex(begin), instrIndex(end)+4) to the 3831a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // live interval. 3841a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos for (unsigned i = 0, e = vi.AliveBlocks.size(); i != e; ++i) { 3851a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos if (vi.AliveBlocks[i]) { 38631ec841be1f51a60f5b655aa2a008eb68e48c07aOwen Anderson LiveRange LR(getMBBStartIdx(i), 387f26e8557deccd5fb28b56548ca5f7ea25aee31c6Evan Cheng getMBBEndIdx(i)+1, // MBB ends at -1. 38831ec841be1f51a60f5b655aa2a008eb68e48c07aOwen Anderson ValNo); 38931ec841be1f51a60f5b655aa2a008eb68e48c07aOwen Anderson interval.addRange(LR); 39031ec841be1f51a60f5b655aa2a008eb68e48c07aOwen Anderson DOUT << " +" << LR; 3911a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos } 3921a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos } 3931a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos 3941a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // Finally, this virtual register is live from the start of any killing 3951a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // block to the 'use' slot of the killing instruction. 3961a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos for (unsigned i = 0, e = vi.Kills.size(); i != e; ++i) { 3971a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos MachineInstr *Kill = vi.Kills[i]; 3988df786012dc6b875f31ba4152e09c6e0098082eeEvan Cheng unsigned killIdx = getUseIndex(getInstructionIndex(Kill))+1; 399428b92eb83b457b71d29d1d4b7900d36a0ce9a53Chris Lattner LiveRange LR(getMBBStartIdx(Kill->getParent()), 4007ecb38be0a533e7b9c7d3b8e9b5c8a6fa5f6b349Evan Cheng killIdx, ValNo); 4011a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos interval.addRange(LR); 402f3bb2e65d12857f83b273f4ecab013680310bbbcEvan Cheng interval.addKill(ValNo, killIdx); 403bdc679d564e67a81792e463f6614b0088f975025Bill Wendling DOUT << " +" << LR; 4041a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos } 4051a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos 4061a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos } else { 4071a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // If this is the second time we see a virtual register definition, it 4081a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // must be due to phi elimination or two addr elimination. If this is 409bf105c842450d3308d024be203ddd533f37051ecEvan Cheng // the result of two address elimination, then the vreg is one of the 410bf105c842450d3308d024be203ddd533f37051ecEvan Cheng // def-and-use register operand. 411ef0732d25a9882c947984ae3f2afbef5463ba00fEvan Cheng if (mi->isRegReDefinedByTwoAddr(interval.reg, MOIdx)) { 4121a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // If this is a two-address definition, then we have already processed 4131a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // the live range. The only problem is that we didn't realize there 4141a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // are actually two values in the live interval. Because of this we 4151a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // need to take the LiveRegion that defines this register and split it 4161a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // into two values. 417a07cec9e24a286157541d2337cd66b24cd116586Evan Cheng assert(interval.containsOneValue()); 418a07cec9e24a286157541d2337cd66b24cd116586Evan Cheng unsigned DefIndex = getDefIndex(interval.getValNumInfo(0)->def); 4196b128bdc58a496e9f08e4d09416330320761baffChris Lattner unsigned RedefIndex = getDefIndex(MIIdx); 4201a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos 4214f8ff168de12eabdeb4b9437bf9402489ecf85cbEvan Cheng const LiveRange *OldLR = interval.getLiveRangeContaining(RedefIndex-1); 4227ecb38be0a533e7b9c7d3b8e9b5c8a6fa5f6b349Evan Cheng VNInfo *OldValNo = OldLR->valno; 4234f8ff168de12eabdeb4b9437bf9402489ecf85cbEvan Cheng 4241a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // Delete the initial value, which should be short and continuous, 425be4f88a8b8bb3311e0dc4cde8533763d7923c3eaChris Lattner // because the 2-addr copy must be in the same MBB as the redef. 4261a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos interval.removeRange(DefIndex, RedefIndex); 427706515727c6d024015fffded2b3109a4f0ac5299Alkis Evlogimenos 428be4f88a8b8bb3311e0dc4cde8533763d7923c3eaChris Lattner // Two-address vregs should always only be redefined once. This means 429be4f88a8b8bb3311e0dc4cde8533763d7923c3eaChris Lattner // that at this point, there should be exactly one value number in it. 430be4f88a8b8bb3311e0dc4cde8533763d7923c3eaChris Lattner assert(interval.containsOneValue() && "Unexpected 2-addr liveint!"); 431be4f88a8b8bb3311e0dc4cde8533763d7923c3eaChris Lattner 43291725b75852443923b419fd23215194cfc65dd88Chris Lattner // The new value number (#1) is defined by the instruction we claimed 43391725b75852443923b419fd23215194cfc65dd88Chris Lattner // defined value #0. 434c8d044e4f779fdcfc5e7d592927740fd8f672a70Evan Cheng VNInfo *ValNo = interval.getNextValue(OldValNo->def, OldValNo->copy, 435c8d044e4f779fdcfc5e7d592927740fd8f672a70Evan Cheng VNInfoAllocator); 436be4f88a8b8bb3311e0dc4cde8533763d7923c3eaChris Lattner 43791725b75852443923b419fd23215194cfc65dd88Chris Lattner // Value#0 is now defined by the 2-addr instruction. 438c8d044e4f779fdcfc5e7d592927740fd8f672a70Evan Cheng OldValNo->def = RedefIndex; 439c8d044e4f779fdcfc5e7d592927740fd8f672a70Evan Cheng OldValNo->copy = 0; 440be4f88a8b8bb3311e0dc4cde8533763d7923c3eaChris Lattner 441be4f88a8b8bb3311e0dc4cde8533763d7923c3eaChris Lattner // Add the new live interval which replaces the range for the input copy. 442be4f88a8b8bb3311e0dc4cde8533763d7923c3eaChris Lattner LiveRange LR(DefIndex, RedefIndex, ValNo); 443bdc679d564e67a81792e463f6614b0088f975025Bill Wendling DOUT << " replace range with " << LR; 4441a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos interval.addRange(LR); 445f3bb2e65d12857f83b273f4ecab013680310bbbcEvan Cheng interval.addKill(ValNo, RedefIndex); 4461a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos 4471a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // If this redefinition is dead, we need to add a dummy unit live 4481a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // range covering the def slot. 4496b098dee286cc6fe5a5a476464d92dec5602e406Owen Anderson if (MO.isDead()) 4507ecb38be0a533e7b9c7d3b8e9b5c8a6fa5f6b349Evan Cheng interval.addRange(LiveRange(RedefIndex, RedefIndex+1, OldValNo)); 4511a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos 45256fdd7af884a35673fb6dd3e01333960922c3ac2Evan Cheng DOUT << " RESULT: "; 4536f0d024a534af18d9e60b3ea757376cd8a3a980eDan Gohman interval.print(DOUT, tri_); 4541a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos 4551a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos } else { 4561a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // Otherwise, this must be because of phi elimination. If this is the 4571a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // first redefinition of the vreg that we have seen, go back and change 4581a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // the live range in the PHI block to be a different value number. 4591a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos if (interval.containsOneValue()) { 4601a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos assert(vi.Kills.size() == 1 && 4611a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos "PHI elimination vreg should have one kill, the PHI itself!"); 4621a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos 4631a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // Remove the old range that we now know has an incorrect number. 464f3bb2e65d12857f83b273f4ecab013680310bbbcEvan Cheng VNInfo *VNI = interval.getValNumInfo(0); 4651a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos MachineInstr *Killer = vi.Kills[0]; 466428b92eb83b457b71d29d1d4b7900d36a0ce9a53Chris Lattner unsigned Start = getMBBStartIdx(Killer->getParent()); 4671a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos unsigned End = getUseIndex(getInstructionIndex(Killer))+1; 46856fdd7af884a35673fb6dd3e01333960922c3ac2Evan Cheng DOUT << " Removing [" << Start << "," << End << "] from: "; 4696f0d024a534af18d9e60b3ea757376cd8a3a980eDan Gohman interval.print(DOUT, tri_); DOUT << "\n"; 4701a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos interval.removeRange(Start, End); 471c3fc7d9ec9b495c8a88cd854247105c296d3aabdEvan Cheng VNI->hasPHIKill = true; 4726f0d024a534af18d9e60b3ea757376cd8a3a980eDan Gohman DOUT << " RESULT: "; interval.print(DOUT, tri_); 4731a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos 474be4f88a8b8bb3311e0dc4cde8533763d7923c3eaChris Lattner // Replace the interval with one of a NEW value number. Note that this 475be4f88a8b8bb3311e0dc4cde8533763d7923c3eaChris Lattner // value number isn't actually defined by an instruction, weird huh? :) 476f3bb2e65d12857f83b273f4ecab013680310bbbcEvan Cheng LiveRange LR(Start, End, interval.getNextValue(~0, 0, VNInfoAllocator)); 477bdc679d564e67a81792e463f6614b0088f975025Bill Wendling DOUT << " replace range with " << LR; 4781a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos interval.addRange(LR); 479f3bb2e65d12857f83b273f4ecab013680310bbbcEvan Cheng interval.addKill(LR.valno, End); 4806f0d024a534af18d9e60b3ea757376cd8a3a980eDan Gohman DOUT << " RESULT: "; interval.print(DOUT, tri_); 4811a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos } 4821a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos 4831a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // In the case of PHI elimination, each variable definition is only 4841a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // live until the end of the block. We've already taken care of the 4851a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // rest of the live range. 4866b128bdc58a496e9f08e4d09416330320761baffChris Lattner unsigned defIndex = getDefIndex(MIIdx); 48791725b75852443923b419fd23215194cfc65dd88Chris Lattner 4887ecb38be0a533e7b9c7d3b8e9b5c8a6fa5f6b349Evan Cheng VNInfo *ValNo; 489c8d044e4f779fdcfc5e7d592927740fd8f672a70Evan Cheng MachineInstr *CopyMI = NULL; 49091725b75852443923b419fd23215194cfc65dd88Chris Lattner unsigned SrcReg, DstReg; 491c8d044e4f779fdcfc5e7d592927740fd8f672a70Evan Cheng if (mi->getOpcode() == TargetInstrInfo::EXTRACT_SUBREG || 4927e073baedb8232b9519dbe15ea141ff98ccfe6aeEvan Cheng mi->getOpcode() == TargetInstrInfo::INSERT_SUBREG || 493c8d044e4f779fdcfc5e7d592927740fd8f672a70Evan Cheng tii_->isMoveInstr(*mi, SrcReg, DstReg)) 494c8d044e4f779fdcfc5e7d592927740fd8f672a70Evan Cheng CopyMI = mi; 495c8d044e4f779fdcfc5e7d592927740fd8f672a70Evan Cheng ValNo = interval.getNextValue(defIndex, CopyMI, VNInfoAllocator); 49691725b75852443923b419fd23215194cfc65dd88Chris Lattner 4977fbad27cfb7298c707e50af10609d463900d7211Owen Anderson unsigned killIndex = getMBBEndIdx(mbb) + 1; 4987ecb38be0a533e7b9c7d3b8e9b5c8a6fa5f6b349Evan Cheng LiveRange LR(defIndex, killIndex, ValNo); 4991a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos interval.addRange(LR); 500c3fc7d9ec9b495c8a88cd854247105c296d3aabdEvan Cheng interval.addKill(ValNo, killIndex); 501c3fc7d9ec9b495c8a88cd854247105c296d3aabdEvan Cheng ValNo->hasPHIKill = true; 502bdc679d564e67a81792e463f6614b0088f975025Bill Wendling DOUT << " +" << LR; 503dd2cc65f34f9b7bfda1cd0c42becedfc361d46f8Alkis Evlogimenos } 5041a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos } 505ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos 506bdc679d564e67a81792e463f6614b0088f975025Bill Wendling DOUT << '\n'; 507ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos} 508ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos 509f35fef7060c465dd7b578bf6339a18e8a8911888Chris Lattnervoid LiveIntervals::handlePhysicalRegisterDef(MachineBasicBlock *MBB, 510ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos MachineBasicBlock::iterator mi, 5116b128bdc58a496e9f08e4d09416330320761baffChris Lattner unsigned MIIdx, 5126b098dee286cc6fe5a5a476464d92dec5602e406Owen Anderson MachineOperand& MO, 51391725b75852443923b419fd23215194cfc65dd88Chris Lattner LiveInterval &interval, 514c8d044e4f779fdcfc5e7d592927740fd8f672a70Evan Cheng MachineInstr *CopyMI) { 5151a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // A physical register cannot be live across basic block, so its 5161a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // lifetime must end somewhere in its defining basic block. 517bdc679d564e67a81792e463f6614b0088f975025Bill Wendling DOUT << "\t\tregister: "; DEBUG(printRegName(interval.reg)); 5181a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos 5196b128bdc58a496e9f08e4d09416330320761baffChris Lattner unsigned baseIndex = MIIdx; 5201a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos unsigned start = getDefIndex(baseIndex); 5211a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos unsigned end = start; 5221a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos 5231a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // If it is not used after definition, it is considered dead at 5241a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // the instruction defining it. Hence its interval is: 5251a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // [defSlot(def), defSlot(def)+1) 5266b098dee286cc6fe5a5a476464d92dec5602e406Owen Anderson if (MO.isDead()) { 527bdc679d564e67a81792e463f6614b0088f975025Bill Wendling DOUT << " dead"; 528ab4b66d4c279e8cd9e448687020fc838e7881dbcChris Lattner end = getDefIndex(start) + 1; 529ab4b66d4c279e8cd9e448687020fc838e7881dbcChris Lattner goto exit; 5301a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos } 531ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos 5321a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // If it is not dead on definition, it must be killed by a 5331a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // subsequent instruction. Hence its interval is: 5341a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // [defSlot(def), useSlot(kill)+1) 5357fbad27cfb7298c707e50af10609d463900d7211Owen Anderson baseIndex += InstrSlots::NUM; 5365ab6f5fe666d0e3403d9b777324d1a1999118153Chris Lattner while (++mi != MBB->end()) { 5377fbad27cfb7298c707e50af10609d463900d7211Owen Anderson while (baseIndex / InstrSlots::NUM < i2miMap_.size() && 5387fbad27cfb7298c707e50af10609d463900d7211Owen Anderson getInstructionFromIndex(baseIndex) == 0) 5397fbad27cfb7298c707e50af10609d463900d7211Owen Anderson baseIndex += InstrSlots::NUM; 5406130f66eaae89f8878590796977678afa8448926Evan Cheng if (mi->killsRegister(interval.reg, tri_)) { 541bdc679d564e67a81792e463f6614b0088f975025Bill Wendling DOUT << " killed"; 542ab4b66d4c279e8cd9e448687020fc838e7881dbcChris Lattner end = getUseIndex(baseIndex) + 1; 543ab4b66d4c279e8cd9e448687020fc838e7881dbcChris Lattner goto exit; 5446130f66eaae89f8878590796977678afa8448926Evan Cheng } else if (mi->modifiesRegister(interval.reg, tri_)) { 5459a1956ae6ad2d4892afbc9f1b97d645d220b6d4aEvan Cheng // Another instruction redefines the register before it is ever read. 5469a1956ae6ad2d4892afbc9f1b97d645d220b6d4aEvan Cheng // Then the register is essentially dead at the instruction that defines 5479a1956ae6ad2d4892afbc9f1b97d645d220b6d4aEvan Cheng // it. Hence its interval is: 5489a1956ae6ad2d4892afbc9f1b97d645d220b6d4aEvan Cheng // [defSlot(def), defSlot(def)+1) 549bdc679d564e67a81792e463f6614b0088f975025Bill Wendling DOUT << " dead"; 5509a1956ae6ad2d4892afbc9f1b97d645d220b6d4aEvan Cheng end = getDefIndex(start) + 1; 5519a1956ae6ad2d4892afbc9f1b97d645d220b6d4aEvan Cheng goto exit; 552f35fef7060c465dd7b578bf6339a18e8a8911888Chris Lattner } 5537fbad27cfb7298c707e50af10609d463900d7211Owen Anderson 5547fbad27cfb7298c707e50af10609d463900d7211Owen Anderson baseIndex += InstrSlots::NUM; 5551a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos } 5565ab6f5fe666d0e3403d9b777324d1a1999118153Chris Lattner 5575ab6f5fe666d0e3403d9b777324d1a1999118153Chris Lattner // The only case we should have a dead physreg here without a killing or 5585ab6f5fe666d0e3403d9b777324d1a1999118153Chris Lattner // instruction where we know it's dead is if it is live-in to the function 5595ab6f5fe666d0e3403d9b777324d1a1999118153Chris Lattner // and never used. 560c8d044e4f779fdcfc5e7d592927740fd8f672a70Evan Cheng assert(!CopyMI && "physreg was not killed in defining block!"); 5615ab6f5fe666d0e3403d9b777324d1a1999118153Chris Lattner end = getDefIndex(start) + 1; // It's dead. 56202ba13c9897ae2b19f9201e57460d7ee2b753a0bAlkis Evlogimenos 563ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenosexit: 5641a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos assert(start < end && "did not find end of interval?"); 565f768bba43f5c036039851d2fcca8212edca18467Chris Lattner 56624a3cc4c83e5edb25fadf7b8979a26b4451795c6Evan Cheng // Already exists? Extend old live interval. 56724a3cc4c83e5edb25fadf7b8979a26b4451795c6Evan Cheng LiveInterval::iterator OldLR = interval.FindLiveRangeContaining(start); 5687ecb38be0a533e7b9c7d3b8e9b5c8a6fa5f6b349Evan Cheng VNInfo *ValNo = (OldLR != interval.end()) 569c8d044e4f779fdcfc5e7d592927740fd8f672a70Evan Cheng ? OldLR->valno : interval.getNextValue(start, CopyMI, VNInfoAllocator); 5707ecb38be0a533e7b9c7d3b8e9b5c8a6fa5f6b349Evan Cheng LiveRange LR(start, end, ValNo); 5711a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos interval.addRange(LR); 572f3bb2e65d12857f83b273f4ecab013680310bbbcEvan Cheng interval.addKill(LR.valno, end); 573bdc679d564e67a81792e463f6614b0088f975025Bill Wendling DOUT << " +" << LR << '\n'; 574ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos} 575ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos 576f35fef7060c465dd7b578bf6339a18e8a8911888Chris Lattnervoid LiveIntervals::handleRegisterDef(MachineBasicBlock *MBB, 577f35fef7060c465dd7b578bf6339a18e8a8911888Chris Lattner MachineBasicBlock::iterator MI, 5786b128bdc58a496e9f08e4d09416330320761baffChris Lattner unsigned MIIdx, 579ef0732d25a9882c947984ae3f2afbef5463ba00fEvan Cheng MachineOperand& MO, 580ef0732d25a9882c947984ae3f2afbef5463ba00fEvan Cheng unsigned MOIdx) { 5816b098dee286cc6fe5a5a476464d92dec5602e406Owen Anderson if (TargetRegisterInfo::isVirtualRegister(MO.getReg())) 582ef0732d25a9882c947984ae3f2afbef5463ba00fEvan Cheng handleVirtualRegisterDef(MBB, MI, MIIdx, MO, MOIdx, 5836b098dee286cc6fe5a5a476464d92dec5602e406Owen Anderson getOrCreateInterval(MO.getReg())); 5846b098dee286cc6fe5a5a476464d92dec5602e406Owen Anderson else if (allocatableRegs_[MO.getReg()]) { 585c8d044e4f779fdcfc5e7d592927740fd8f672a70Evan Cheng MachineInstr *CopyMI = NULL; 58691725b75852443923b419fd23215194cfc65dd88Chris Lattner unsigned SrcReg, DstReg; 587c8d044e4f779fdcfc5e7d592927740fd8f672a70Evan Cheng if (MI->getOpcode() == TargetInstrInfo::EXTRACT_SUBREG || 5887e073baedb8232b9519dbe15ea141ff98ccfe6aeEvan Cheng MI->getOpcode() == TargetInstrInfo::INSERT_SUBREG || 589c8d044e4f779fdcfc5e7d592927740fd8f672a70Evan Cheng tii_->isMoveInstr(*MI, SrcReg, DstReg)) 590c8d044e4f779fdcfc5e7d592927740fd8f672a70Evan Cheng CopyMI = MI; 5916b098dee286cc6fe5a5a476464d92dec5602e406Owen Anderson handlePhysicalRegisterDef(MBB, MI, MIIdx, MO, 5926b098dee286cc6fe5a5a476464d92dec5602e406Owen Anderson getOrCreateInterval(MO.getReg()), CopyMI); 59324a3cc4c83e5edb25fadf7b8979a26b4451795c6Evan Cheng // Def of a register also defines its sub-registers. 5946b098dee286cc6fe5a5a476464d92dec5602e406Owen Anderson for (const unsigned* AS = tri_->getSubRegisters(MO.getReg()); *AS; ++AS) 5956130f66eaae89f8878590796977678afa8448926Evan Cheng // If MI also modifies the sub-register explicitly, avoid processing it 5966130f66eaae89f8878590796977678afa8448926Evan Cheng // more than once. Do not pass in TRI here so it checks for exact match. 5976130f66eaae89f8878590796977678afa8448926Evan Cheng if (!MI->modifiesRegister(*AS)) 5986b098dee286cc6fe5a5a476464d92dec5602e406Owen Anderson handlePhysicalRegisterDef(MBB, MI, MIIdx, MO, 5996b098dee286cc6fe5a5a476464d92dec5602e406Owen Anderson getOrCreateInterval(*AS), 0); 600f35fef7060c465dd7b578bf6339a18e8a8911888Chris Lattner } 6014d46e1e521c0df1990ea50f8146d22bd77ea71a6Alkis Evlogimenos} 6024d46e1e521c0df1990ea50f8146d22bd77ea71a6Alkis Evlogimenos 603b371f457b0ea4a652a9f526ba4375c80ae542252Evan Chengvoid LiveIntervals::handleLiveInRegister(MachineBasicBlock *MBB, 6049b25b8ca24d6df2e097741dcc15016772ee4eda7Jim Laskey unsigned MIIdx, 60524a3cc4c83e5edb25fadf7b8979a26b4451795c6Evan Cheng LiveInterval &interval, bool isAlias) { 606b371f457b0ea4a652a9f526ba4375c80ae542252Evan Cheng DOUT << "\t\tlivein register: "; DEBUG(printRegName(interval.reg)); 607b371f457b0ea4a652a9f526ba4375c80ae542252Evan Cheng 608b371f457b0ea4a652a9f526ba4375c80ae542252Evan Cheng // Look for kills, if it reaches a def before it's killed, then it shouldn't 609b371f457b0ea4a652a9f526ba4375c80ae542252Evan Cheng // be considered a livein. 610b371f457b0ea4a652a9f526ba4375c80ae542252Evan Cheng MachineBasicBlock::iterator mi = MBB->begin(); 6119b25b8ca24d6df2e097741dcc15016772ee4eda7Jim Laskey unsigned baseIndex = MIIdx; 6129b25b8ca24d6df2e097741dcc15016772ee4eda7Jim Laskey unsigned start = baseIndex; 613b371f457b0ea4a652a9f526ba4375c80ae542252Evan Cheng unsigned end = start; 614b371f457b0ea4a652a9f526ba4375c80ae542252Evan Cheng while (mi != MBB->end()) { 6156130f66eaae89f8878590796977678afa8448926Evan Cheng if (mi->killsRegister(interval.reg, tri_)) { 616b371f457b0ea4a652a9f526ba4375c80ae542252Evan Cheng DOUT << " killed"; 617b371f457b0ea4a652a9f526ba4375c80ae542252Evan Cheng end = getUseIndex(baseIndex) + 1; 618b371f457b0ea4a652a9f526ba4375c80ae542252Evan Cheng goto exit; 6196130f66eaae89f8878590796977678afa8448926Evan Cheng } else if (mi->modifiesRegister(interval.reg, tri_)) { 620b371f457b0ea4a652a9f526ba4375c80ae542252Evan Cheng // Another instruction redefines the register before it is ever read. 621b371f457b0ea4a652a9f526ba4375c80ae542252Evan Cheng // Then the register is essentially dead at the instruction that defines 622b371f457b0ea4a652a9f526ba4375c80ae542252Evan Cheng // it. Hence its interval is: 623b371f457b0ea4a652a9f526ba4375c80ae542252Evan Cheng // [defSlot(def), defSlot(def)+1) 624b371f457b0ea4a652a9f526ba4375c80ae542252Evan Cheng DOUT << " dead"; 625b371f457b0ea4a652a9f526ba4375c80ae542252Evan Cheng end = getDefIndex(start) + 1; 626b371f457b0ea4a652a9f526ba4375c80ae542252Evan Cheng goto exit; 627b371f457b0ea4a652a9f526ba4375c80ae542252Evan Cheng } 628b371f457b0ea4a652a9f526ba4375c80ae542252Evan Cheng 629b371f457b0ea4a652a9f526ba4375c80ae542252Evan Cheng baseIndex += InstrSlots::NUM; 6307fbad27cfb7298c707e50af10609d463900d7211Owen Anderson while (baseIndex / InstrSlots::NUM < i2miMap_.size() && 6317fbad27cfb7298c707e50af10609d463900d7211Owen Anderson getInstructionFromIndex(baseIndex) == 0) 6327fbad27cfb7298c707e50af10609d463900d7211Owen Anderson baseIndex += InstrSlots::NUM; 633b371f457b0ea4a652a9f526ba4375c80ae542252Evan Cheng ++mi; 634b371f457b0ea4a652a9f526ba4375c80ae542252Evan Cheng } 635b371f457b0ea4a652a9f526ba4375c80ae542252Evan Cheng 636b371f457b0ea4a652a9f526ba4375c80ae542252Evan Chengexit: 63775611fb4e6ab253be30ac29a2b15e9bf8c1d146eEvan Cheng // Live-in register might not be used at all. 63875611fb4e6ab253be30ac29a2b15e9bf8c1d146eEvan Cheng if (end == MIIdx) { 639292da949f6c87d6499425d64d37d7c5870ec57adEvan Cheng if (isAlias) { 640292da949f6c87d6499425d64d37d7c5870ec57adEvan Cheng DOUT << " dead"; 64175611fb4e6ab253be30ac29a2b15e9bf8c1d146eEvan Cheng end = getDefIndex(MIIdx) + 1; 642292da949f6c87d6499425d64d37d7c5870ec57adEvan Cheng } else { 643292da949f6c87d6499425d64d37d7c5870ec57adEvan Cheng DOUT << " live through"; 644292da949f6c87d6499425d64d37d7c5870ec57adEvan Cheng end = baseIndex; 645292da949f6c87d6499425d64d37d7c5870ec57adEvan Cheng } 64624a3cc4c83e5edb25fadf7b8979a26b4451795c6Evan Cheng } 64724a3cc4c83e5edb25fadf7b8979a26b4451795c6Evan Cheng 648f3bb2e65d12857f83b273f4ecab013680310bbbcEvan Cheng LiveRange LR(start, end, interval.getNextValue(start, 0, VNInfoAllocator)); 6499b25b8ca24d6df2e097741dcc15016772ee4eda7Jim Laskey interval.addRange(LR); 650f3bb2e65d12857f83b273f4ecab013680310bbbcEvan Cheng interval.addKill(LR.valno, end); 65124c2e5cf7e926452ea5875d027ec0d24d9c19e39Evan Cheng DOUT << " +" << LR << '\n'; 652b371f457b0ea4a652a9f526ba4375c80ae542252Evan Cheng} 653b371f457b0ea4a652a9f526ba4375c80ae542252Evan Cheng 654ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos/// computeIntervals - computes the live intervals for virtual 6554d46e1e521c0df1990ea50f8146d22bd77ea71a6Alkis Evlogimenos/// registers. for some ordering of the machine instructions [1,N] a 65608cec00588ec1a8fa85b208555f006d7396ae7a4Alkis Evlogimenos/// live interval is an interval [i, j) where 1 <= i <= j < N for 657ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos/// which a variable is live 658f7da2c7b0c6293c268881628fc351bed7763f1f4Chris Lattnervoid LiveIntervals::computeIntervals() { 659bdc679d564e67a81792e463f6614b0088f975025Bill Wendling DOUT << "********** COMPUTING LIVE INTERVALS **********\n" 660bdc679d564e67a81792e463f6614b0088f975025Bill Wendling << "********** Function: " 661bdc679d564e67a81792e463f6614b0088f975025Bill Wendling << ((Value*)mf_->getFunction())->getName() << '\n'; 6626b128bdc58a496e9f08e4d09416330320761baffChris Lattner // Track the index of the current machine instr. 6636b128bdc58a496e9f08e4d09416330320761baffChris Lattner unsigned MIIndex = 0; 6647fbad27cfb7298c707e50af10609d463900d7211Owen Anderson 6657fbad27cfb7298c707e50af10609d463900d7211Owen Anderson // Skip over empty initial indices. 6667fbad27cfb7298c707e50af10609d463900d7211Owen Anderson while (MIIndex / InstrSlots::NUM < i2miMap_.size() && 6677fbad27cfb7298c707e50af10609d463900d7211Owen Anderson getInstructionFromIndex(MIIndex) == 0) 6687fbad27cfb7298c707e50af10609d463900d7211Owen Anderson MIIndex += InstrSlots::NUM; 6697fbad27cfb7298c707e50af10609d463900d7211Owen Anderson 670428b92eb83b457b71d29d1d4b7900d36a0ce9a53Chris Lattner for (MachineFunction::iterator MBBI = mf_->begin(), E = mf_->end(); 671428b92eb83b457b71d29d1d4b7900d36a0ce9a53Chris Lattner MBBI != E; ++MBBI) { 672428b92eb83b457b71d29d1d4b7900d36a0ce9a53Chris Lattner MachineBasicBlock *MBB = MBBI; 673bdc679d564e67a81792e463f6614b0088f975025Bill Wendling DOUT << ((Value*)MBB->getBasicBlock())->getName() << ":\n"; 6741a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos 675428b92eb83b457b71d29d1d4b7900d36a0ce9a53Chris Lattner MachineBasicBlock::iterator MI = MBB->begin(), miEnd = MBB->end(); 6760c9f92e1ff64ee56724eae444a0442b02f83d0a8Evan Cheng 677cb406c25973b4e88a6c10ad839ef1beeb3664715Dan Gohman // Create intervals for live-ins to this BB first. 678cb406c25973b4e88a6c10ad839ef1beeb3664715Dan Gohman for (MachineBasicBlock::const_livein_iterator LI = MBB->livein_begin(), 679cb406c25973b4e88a6c10ad839ef1beeb3664715Dan Gohman LE = MBB->livein_end(); LI != LE; ++LI) { 680cb406c25973b4e88a6c10ad839ef1beeb3664715Dan Gohman handleLiveInRegister(MBB, MIIndex, getOrCreateInterval(*LI)); 681cb406c25973b4e88a6c10ad839ef1beeb3664715Dan Gohman // Multiple live-ins can alias the same register. 6826f0d024a534af18d9e60b3ea757376cd8a3a980eDan Gohman for (const unsigned* AS = tri_->getSubRegisters(*LI); *AS; ++AS) 683cb406c25973b4e88a6c10ad839ef1beeb3664715Dan Gohman if (!hasInterval(*AS)) 684cb406c25973b4e88a6c10ad839ef1beeb3664715Dan Gohman handleLiveInRegister(MBB, MIIndex, getOrCreateInterval(*AS), 685cb406c25973b4e88a6c10ad839ef1beeb3664715Dan Gohman true); 686dffb2e83ed2546226d09c40aa43524e2392322daChris Lattner } 687dffb2e83ed2546226d09c40aa43524e2392322daChris Lattner 688428b92eb83b457b71d29d1d4b7900d36a0ce9a53Chris Lattner for (; MI != miEnd; ++MI) { 689bdc679d564e67a81792e463f6614b0088f975025Bill Wendling DOUT << MIIndex << "\t" << *MI; 6901a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos 691438f7bc67cf235ccee7e6f7ac7f4ae2186eb8020Evan Cheng // Handle defs. 692428b92eb83b457b71d29d1d4b7900d36a0ce9a53Chris Lattner for (int i = MI->getNumOperands() - 1; i >= 0; --i) { 693428b92eb83b457b71d29d1d4b7900d36a0ce9a53Chris Lattner MachineOperand &MO = MI->getOperand(i); 6941a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // handle register defs - build intervals 695428b92eb83b457b71d29d1d4b7900d36a0ce9a53Chris Lattner if (MO.isRegister() && MO.getReg() && MO.isDef()) 696ef0732d25a9882c947984ae3f2afbef5463ba00fEvan Cheng handleRegisterDef(MBB, MI, MIIndex, MO, i); 6971a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos } 6986b128bdc58a496e9f08e4d09416330320761baffChris Lattner 6996b128bdc58a496e9f08e4d09416330320761baffChris Lattner MIIndex += InstrSlots::NUM; 7007fbad27cfb7298c707e50af10609d463900d7211Owen Anderson 7017fbad27cfb7298c707e50af10609d463900d7211Owen Anderson // Skip over empty indices. 7027fbad27cfb7298c707e50af10609d463900d7211Owen Anderson while (MIIndex / InstrSlots::NUM < i2miMap_.size() && 7037fbad27cfb7298c707e50af10609d463900d7211Owen Anderson getInstructionFromIndex(MIIndex) == 0) 7047fbad27cfb7298c707e50af10609d463900d7211Owen Anderson MIIndex += InstrSlots::NUM; 705ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos } 7061a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos } 707ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos} 708b27ef248f579b354aab434f63c417ab1103e47e2Alkis Evlogimenos 7094ca980e7f9ce7b78955307c2d07001a24d3b6befEvan Chengbool LiveIntervals::findLiveInMBBs(const LiveRange &LR, 710a5bfc97da713ec9e185226d44e6adb4d3087b304Evan Cheng SmallVectorImpl<MachineBasicBlock*> &MBBs) const { 7114ca980e7f9ce7b78955307c2d07001a24d3b6befEvan Cheng std::vector<IdxMBBPair>::const_iterator I = 7124ca980e7f9ce7b78955307c2d07001a24d3b6befEvan Cheng std::lower_bound(Idx2MBBMap.begin(), Idx2MBBMap.end(), LR.start); 7134ca980e7f9ce7b78955307c2d07001a24d3b6befEvan Cheng 7144ca980e7f9ce7b78955307c2d07001a24d3b6befEvan Cheng bool ResVal = false; 7154ca980e7f9ce7b78955307c2d07001a24d3b6befEvan Cheng while (I != Idx2MBBMap.end()) { 7164ca980e7f9ce7b78955307c2d07001a24d3b6befEvan Cheng if (LR.end <= I->first) 7174ca980e7f9ce7b78955307c2d07001a24d3b6befEvan Cheng break; 7184ca980e7f9ce7b78955307c2d07001a24d3b6befEvan Cheng MBBs.push_back(I->second); 7194ca980e7f9ce7b78955307c2d07001a24d3b6befEvan Cheng ResVal = true; 7204ca980e7f9ce7b78955307c2d07001a24d3b6befEvan Cheng ++I; 7214ca980e7f9ce7b78955307c2d07001a24d3b6befEvan Cheng } 7224ca980e7f9ce7b78955307c2d07001a24d3b6befEvan Cheng return ResVal; 7234ca980e7f9ce7b78955307c2d07001a24d3b6befEvan Cheng} 7244ca980e7f9ce7b78955307c2d07001a24d3b6befEvan Cheng 7254ca980e7f9ce7b78955307c2d07001a24d3b6befEvan Cheng 726a1613db62fec94845aa8306232fb665273615badAlkis EvlogimenosLiveInterval LiveIntervals::createInterval(unsigned reg) { 7276f0d024a534af18d9e60b3ea757376cd8a3a980eDan Gohman float Weight = TargetRegisterInfo::isPhysicalRegister(reg) ? 7287902c75331fa8f38fc8380f5573d935c0d149ef5Jim Laskey HUGE_VALF : 0.0F; 729a1613db62fec94845aa8306232fb665273615badAlkis Evlogimenos return LiveInterval(reg, Weight); 7309a8b490735d216435862a3d52e669357f165550fAlkis Evlogimenos} 731f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng 732c8d044e4f779fdcfc5e7d592927740fd8f672a70Evan Cheng/// getVNInfoSourceReg - Helper function that parses the specified VNInfo 733c8d044e4f779fdcfc5e7d592927740fd8f672a70Evan Cheng/// copy field and returns the source register that defines it. 734c8d044e4f779fdcfc5e7d592927740fd8f672a70Evan Chengunsigned LiveIntervals::getVNInfoSourceReg(const VNInfo *VNI) const { 735c8d044e4f779fdcfc5e7d592927740fd8f672a70Evan Cheng if (!VNI->copy) 736c8d044e4f779fdcfc5e7d592927740fd8f672a70Evan Cheng return 0; 737c8d044e4f779fdcfc5e7d592927740fd8f672a70Evan Cheng 738c8d044e4f779fdcfc5e7d592927740fd8f672a70Evan Cheng if (VNI->copy->getOpcode() == TargetInstrInfo::EXTRACT_SUBREG) 739c8d044e4f779fdcfc5e7d592927740fd8f672a70Evan Cheng return VNI->copy->getOperand(1).getReg(); 7407e073baedb8232b9519dbe15ea141ff98ccfe6aeEvan Cheng if (VNI->copy->getOpcode() == TargetInstrInfo::INSERT_SUBREG) 7417e073baedb8232b9519dbe15ea141ff98ccfe6aeEvan Cheng return VNI->copy->getOperand(2).getReg(); 742c8d044e4f779fdcfc5e7d592927740fd8f672a70Evan Cheng unsigned SrcReg, DstReg; 743c8d044e4f779fdcfc5e7d592927740fd8f672a70Evan Cheng if (tii_->isMoveInstr(*VNI->copy, SrcReg, DstReg)) 744c8d044e4f779fdcfc5e7d592927740fd8f672a70Evan Cheng return SrcReg; 745c8d044e4f779fdcfc5e7d592927740fd8f672a70Evan Cheng assert(0 && "Unrecognized copy instruction!"); 746c8d044e4f779fdcfc5e7d592927740fd8f672a70Evan Cheng return 0; 747c8d044e4f779fdcfc5e7d592927740fd8f672a70Evan Cheng} 748f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng 749f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng//===----------------------------------------------------------------------===// 750f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng// Register allocator hooks. 751f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng// 752f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng 753d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng/// getReMatImplicitUse - If the remat definition MI has one (for now, we only 754d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng/// allow one) virtual register operand, then its uses are implicitly using 755d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng/// the register. Returns the virtual register. 756d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Chengunsigned LiveIntervals::getReMatImplicitUse(const LiveInterval &li, 757d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng MachineInstr *MI) const { 758d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng unsigned RegOp = 0; 759d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) { 760d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng MachineOperand &MO = MI->getOperand(i); 761d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng if (!MO.isRegister() || !MO.isUse()) 762d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng continue; 763d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng unsigned Reg = MO.getReg(); 764d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng if (Reg == 0 || Reg == li.reg) 765d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng continue; 766d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng // FIXME: For now, only remat MI with at most one register operand. 767d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng assert(!RegOp && 768d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng "Can't rematerialize instruction with multiple register operand!"); 769d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng RegOp = MO.getReg(); 7706d69ba8a6901c69d78488cbc41f8dbf080618fdeDan Gohman#ifndef NDEBUG 771d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng break; 7726d69ba8a6901c69d78488cbc41f8dbf080618fdeDan Gohman#endif 773d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng } 774d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng return RegOp; 775d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng} 776d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng 777d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng/// isValNoAvailableAt - Return true if the val# of the specified interval 778d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng/// which reaches the given instruction also reaches the specified use index. 779d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Chengbool LiveIntervals::isValNoAvailableAt(const LiveInterval &li, MachineInstr *MI, 780d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng unsigned UseIdx) const { 781d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng unsigned Index = getInstructionIndex(MI); 782d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng VNInfo *ValNo = li.FindLiveRangeContaining(Index)->valno; 783d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng LiveInterval::const_iterator UI = li.FindLiveRangeContaining(UseIdx); 784d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng return UI != li.end() && UI->valno == ValNo; 785d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng} 786d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng 787f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng/// isReMaterializable - Returns true if the definition MI of the specified 788f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng/// val# of the specified interval is re-materializable. 789f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Chengbool LiveIntervals::isReMaterializable(const LiveInterval &li, 7905ef3a04b542c4e585276768fa9ca2af698ef5c87Evan Cheng const VNInfo *ValNo, MachineInstr *MI, 7915ef3a04b542c4e585276768fa9ca2af698ef5c87Evan Cheng bool &isLoad) { 792f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng if (DisableReMat) 793f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng return false; 794f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng 79520ccded7dec5b90e58f649f4fb95b166a642b8cbEvan Cheng if (MI->getOpcode() == TargetInstrInfo::IMPLICIT_DEF) 796d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng return true; 797dd3465eed17cdf226bdb465e604dfa851d36029dEvan Cheng 798dd3465eed17cdf226bdb465e604dfa851d36029dEvan Cheng int FrameIdx = 0; 799dd3465eed17cdf226bdb465e604dfa851d36029dEvan Cheng if (tii_->isLoadFromStackSlot(MI, FrameIdx) && 800249ded3fa8884f91fded869fb6e251b8aebb0376Evan Cheng mf_->getFrameInfo()->isImmutableObjectIndex(FrameIdx)) 80179a0c1e46c4f7d8a2a06f4ef3e2c54d883c7fe25Evan Cheng // FIXME: Let target specific isReallyTriviallyReMaterializable determines 80279a0c1e46c4f7d8a2a06f4ef3e2c54d883c7fe25Evan Cheng // this but remember this is not safe to fold into a two-address 80379a0c1e46c4f7d8a2a06f4ef3e2c54d883c7fe25Evan Cheng // instruction. 804249ded3fa8884f91fded869fb6e251b8aebb0376Evan Cheng // This is a load from fixed stack slot. It can be rematerialized. 805dd3465eed17cdf226bdb465e604dfa851d36029dEvan Cheng return true; 806dd3465eed17cdf226bdb465e604dfa851d36029dEvan Cheng 8076d69ba8a6901c69d78488cbc41f8dbf080618fdeDan Gohman // If the target-specific rules don't identify an instruction as 8086d69ba8a6901c69d78488cbc41f8dbf080618fdeDan Gohman // being trivially rematerializable, use some target-independent 8096d69ba8a6901c69d78488cbc41f8dbf080618fdeDan Gohman // rules. 8106d69ba8a6901c69d78488cbc41f8dbf080618fdeDan Gohman if (!MI->getDesc().isRematerializable() || 8116d69ba8a6901c69d78488cbc41f8dbf080618fdeDan Gohman !tii_->isTriviallyReMaterializable(MI)) { 8124c8f87038ddc0fbcce751f0e2e7c0e564abca096Dan Gohman if (!EnableAggressiveRemat) 8134c8f87038ddc0fbcce751f0e2e7c0e564abca096Dan Gohman return false; 8146d69ba8a6901c69d78488cbc41f8dbf080618fdeDan Gohman 8150471a79f2000eb1eb4458e7b3dcd254172fae739Dan Gohman // If the instruction accesses memory but the memoperands have been lost, 8166d69ba8a6901c69d78488cbc41f8dbf080618fdeDan Gohman // we can't analyze it. 81720ccded7dec5b90e58f649f4fb95b166a642b8cbEvan Cheng const TargetInstrDesc &TID = MI->getDesc(); 8186d69ba8a6901c69d78488cbc41f8dbf080618fdeDan Gohman if ((TID.mayLoad() || TID.mayStore()) && MI->memoperands_empty()) 8196d69ba8a6901c69d78488cbc41f8dbf080618fdeDan Gohman return false; 8206d69ba8a6901c69d78488cbc41f8dbf080618fdeDan Gohman 8216d69ba8a6901c69d78488cbc41f8dbf080618fdeDan Gohman // Avoid instructions obviously unsafe for remat. 8226d69ba8a6901c69d78488cbc41f8dbf080618fdeDan Gohman if (TID.hasUnmodeledSideEffects() || TID.isNotDuplicable()) 8236d69ba8a6901c69d78488cbc41f8dbf080618fdeDan Gohman return false; 8246d69ba8a6901c69d78488cbc41f8dbf080618fdeDan Gohman 8256d69ba8a6901c69d78488cbc41f8dbf080618fdeDan Gohman // If the instruction accesses memory and the memory could be non-constant, 8266d69ba8a6901c69d78488cbc41f8dbf080618fdeDan Gohman // assume the instruction is not rematerializable. 827fed90b6d097d50881afb45e4d79f430db66dd741Dan Gohman for (std::list<MachineMemOperand>::const_iterator I = MI->memoperands_begin(), 8286d69ba8a6901c69d78488cbc41f8dbf080618fdeDan Gohman E = MI->memoperands_end(); I != E; ++I) { 8296d69ba8a6901c69d78488cbc41f8dbf080618fdeDan Gohman const MachineMemOperand &MMO = *I; 8306d69ba8a6901c69d78488cbc41f8dbf080618fdeDan Gohman if (MMO.isVolatile() || MMO.isStore()) 8316d69ba8a6901c69d78488cbc41f8dbf080618fdeDan Gohman return false; 8326d69ba8a6901c69d78488cbc41f8dbf080618fdeDan Gohman const Value *V = MMO.getValue(); 8336d69ba8a6901c69d78488cbc41f8dbf080618fdeDan Gohman if (!V) 8346d69ba8a6901c69d78488cbc41f8dbf080618fdeDan Gohman return false; 8356d69ba8a6901c69d78488cbc41f8dbf080618fdeDan Gohman if (const PseudoSourceValue *PSV = dyn_cast<PseudoSourceValue>(V)) { 8366d69ba8a6901c69d78488cbc41f8dbf080618fdeDan Gohman if (!PSV->isConstant(mf_->getFrameInfo())) 8376d69ba8a6901c69d78488cbc41f8dbf080618fdeDan Gohman return false; 8386d69ba8a6901c69d78488cbc41f8dbf080618fdeDan Gohman } else if (!aa_->pointsToConstantMemory(V)) 8396d69ba8a6901c69d78488cbc41f8dbf080618fdeDan Gohman return false; 8406d69ba8a6901c69d78488cbc41f8dbf080618fdeDan Gohman } 8416d69ba8a6901c69d78488cbc41f8dbf080618fdeDan Gohman 8426d69ba8a6901c69d78488cbc41f8dbf080618fdeDan Gohman // If any of the registers accessed are non-constant, conservatively assume 8436d69ba8a6901c69d78488cbc41f8dbf080618fdeDan Gohman // the instruction is not rematerializable. 8446d69ba8a6901c69d78488cbc41f8dbf080618fdeDan Gohman unsigned ImpUse = 0; 8456d69ba8a6901c69d78488cbc41f8dbf080618fdeDan Gohman for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) { 8466d69ba8a6901c69d78488cbc41f8dbf080618fdeDan Gohman const MachineOperand &MO = MI->getOperand(i); 8476d69ba8a6901c69d78488cbc41f8dbf080618fdeDan Gohman if (MO.isReg()) { 8486d69ba8a6901c69d78488cbc41f8dbf080618fdeDan Gohman unsigned Reg = MO.getReg(); 8496d69ba8a6901c69d78488cbc41f8dbf080618fdeDan Gohman if (Reg == 0) 850d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng continue; 8516d69ba8a6901c69d78488cbc41f8dbf080618fdeDan Gohman if (TargetRegisterInfo::isPhysicalRegister(Reg)) 8526d69ba8a6901c69d78488cbc41f8dbf080618fdeDan Gohman return false; 8536d69ba8a6901c69d78488cbc41f8dbf080618fdeDan Gohman 8546d69ba8a6901c69d78488cbc41f8dbf080618fdeDan Gohman // Only allow one def, and that in the first operand. 8556d69ba8a6901c69d78488cbc41f8dbf080618fdeDan Gohman if (MO.isDef() != (i == 0)) 856d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng return false; 8576d69ba8a6901c69d78488cbc41f8dbf080618fdeDan Gohman 8586d69ba8a6901c69d78488cbc41f8dbf080618fdeDan Gohman // Only allow constant-valued registers. 8596d69ba8a6901c69d78488cbc41f8dbf080618fdeDan Gohman bool IsLiveIn = mri_->isLiveIn(Reg); 8606d69ba8a6901c69d78488cbc41f8dbf080618fdeDan Gohman MachineRegisterInfo::def_iterator I = mri_->def_begin(Reg), 8616d69ba8a6901c69d78488cbc41f8dbf080618fdeDan Gohman E = mri_->def_end(); 8626d69ba8a6901c69d78488cbc41f8dbf080618fdeDan Gohman 8636d69ba8a6901c69d78488cbc41f8dbf080618fdeDan Gohman // For the def, it should be the only def. 8646d69ba8a6901c69d78488cbc41f8dbf080618fdeDan Gohman if (MO.isDef() && (next(I) != E || IsLiveIn)) 8656d69ba8a6901c69d78488cbc41f8dbf080618fdeDan Gohman return false; 8666d69ba8a6901c69d78488cbc41f8dbf080618fdeDan Gohman 8676d69ba8a6901c69d78488cbc41f8dbf080618fdeDan Gohman if (MO.isUse()) { 8686d69ba8a6901c69d78488cbc41f8dbf080618fdeDan Gohman // Only allow one use other register use, as that's all the 8696d69ba8a6901c69d78488cbc41f8dbf080618fdeDan Gohman // remat mechanisms support currently. 8706d69ba8a6901c69d78488cbc41f8dbf080618fdeDan Gohman if (Reg != li.reg) { 8716d69ba8a6901c69d78488cbc41f8dbf080618fdeDan Gohman if (ImpUse == 0) 8726d69ba8a6901c69d78488cbc41f8dbf080618fdeDan Gohman ImpUse = Reg; 8736d69ba8a6901c69d78488cbc41f8dbf080618fdeDan Gohman else if (Reg != ImpUse) 8746d69ba8a6901c69d78488cbc41f8dbf080618fdeDan Gohman return false; 8756d69ba8a6901c69d78488cbc41f8dbf080618fdeDan Gohman } 8766d69ba8a6901c69d78488cbc41f8dbf080618fdeDan Gohman // For uses, there should be only one associate def. 8776d69ba8a6901c69d78488cbc41f8dbf080618fdeDan Gohman if (I != E && (next(I) != E || IsLiveIn)) 8786d69ba8a6901c69d78488cbc41f8dbf080618fdeDan Gohman return false; 8796d69ba8a6901c69d78488cbc41f8dbf080618fdeDan Gohman } 880d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng } 881d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng } 8825ef3a04b542c4e585276768fa9ca2af698ef5c87Evan Cheng } 883f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng 8846d69ba8a6901c69d78488cbc41f8dbf080618fdeDan Gohman unsigned ImpUse = getReMatImplicitUse(li, MI); 8856d69ba8a6901c69d78488cbc41f8dbf080618fdeDan Gohman if (ImpUse) { 8866d69ba8a6901c69d78488cbc41f8dbf080618fdeDan Gohman const LiveInterval &ImpLi = getInterval(ImpUse); 8876d69ba8a6901c69d78488cbc41f8dbf080618fdeDan Gohman for (MachineRegisterInfo::use_iterator ri = mri_->use_begin(li.reg), 8886d69ba8a6901c69d78488cbc41f8dbf080618fdeDan Gohman re = mri_->use_end(); ri != re; ++ri) { 8896d69ba8a6901c69d78488cbc41f8dbf080618fdeDan Gohman MachineInstr *UseMI = &*ri; 8906d69ba8a6901c69d78488cbc41f8dbf080618fdeDan Gohman unsigned UseIdx = getInstructionIndex(UseMI); 8916d69ba8a6901c69d78488cbc41f8dbf080618fdeDan Gohman if (li.FindLiveRangeContaining(UseIdx)->valno != ValNo) 8926d69ba8a6901c69d78488cbc41f8dbf080618fdeDan Gohman continue; 8936d69ba8a6901c69d78488cbc41f8dbf080618fdeDan Gohman if (!isValNoAvailableAt(ImpLi, MI, UseIdx)) 8946d69ba8a6901c69d78488cbc41f8dbf080618fdeDan Gohman return false; 8956d69ba8a6901c69d78488cbc41f8dbf080618fdeDan Gohman } 8966d69ba8a6901c69d78488cbc41f8dbf080618fdeDan Gohman } 8976d69ba8a6901c69d78488cbc41f8dbf080618fdeDan Gohman return true; 8985ef3a04b542c4e585276768fa9ca2af698ef5c87Evan Cheng} 8995ef3a04b542c4e585276768fa9ca2af698ef5c87Evan Cheng 9005ef3a04b542c4e585276768fa9ca2af698ef5c87Evan Cheng/// isReMaterializable - Returns true if every definition of MI of every 9015ef3a04b542c4e585276768fa9ca2af698ef5c87Evan Cheng/// val# of the specified interval is re-materializable. 9025ef3a04b542c4e585276768fa9ca2af698ef5c87Evan Chengbool LiveIntervals::isReMaterializable(const LiveInterval &li, bool &isLoad) { 9035ef3a04b542c4e585276768fa9ca2af698ef5c87Evan Cheng isLoad = false; 9045ef3a04b542c4e585276768fa9ca2af698ef5c87Evan Cheng for (LiveInterval::const_vni_iterator i = li.vni_begin(), e = li.vni_end(); 9055ef3a04b542c4e585276768fa9ca2af698ef5c87Evan Cheng i != e; ++i) { 9065ef3a04b542c4e585276768fa9ca2af698ef5c87Evan Cheng const VNInfo *VNI = *i; 9075ef3a04b542c4e585276768fa9ca2af698ef5c87Evan Cheng unsigned DefIdx = VNI->def; 9085ef3a04b542c4e585276768fa9ca2af698ef5c87Evan Cheng if (DefIdx == ~1U) 9095ef3a04b542c4e585276768fa9ca2af698ef5c87Evan Cheng continue; // Dead val#. 9105ef3a04b542c4e585276768fa9ca2af698ef5c87Evan Cheng // Is the def for the val# rematerializable? 9115ef3a04b542c4e585276768fa9ca2af698ef5c87Evan Cheng if (DefIdx == ~0u) 9125ef3a04b542c4e585276768fa9ca2af698ef5c87Evan Cheng return false; 9135ef3a04b542c4e585276768fa9ca2af698ef5c87Evan Cheng MachineInstr *ReMatDefMI = getInstructionFromIndex(DefIdx); 9145ef3a04b542c4e585276768fa9ca2af698ef5c87Evan Cheng bool DefIsLoad = false; 915d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng if (!ReMatDefMI || 916d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng !isReMaterializable(li, VNI, ReMatDefMI, DefIsLoad)) 917f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng return false; 9185ef3a04b542c4e585276768fa9ca2af698ef5c87Evan Cheng isLoad |= DefIsLoad; 919f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng } 920f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng return true; 921f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng} 922f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng 92379a0c1e46c4f7d8a2a06f4ef3e2c54d883c7fe25Evan Cheng/// FilterFoldedOps - Filter out two-address use operands. Return 92479a0c1e46c4f7d8a2a06f4ef3e2c54d883c7fe25Evan Cheng/// true if it finds any issue with the operands that ought to prevent 92579a0c1e46c4f7d8a2a06f4ef3e2c54d883c7fe25Evan Cheng/// folding. 92679a0c1e46c4f7d8a2a06f4ef3e2c54d883c7fe25Evan Chengstatic bool FilterFoldedOps(MachineInstr *MI, 92779a0c1e46c4f7d8a2a06f4ef3e2c54d883c7fe25Evan Cheng SmallVector<unsigned, 2> &Ops, 92879a0c1e46c4f7d8a2a06f4ef3e2c54d883c7fe25Evan Cheng unsigned &MRInfo, 92979a0c1e46c4f7d8a2a06f4ef3e2c54d883c7fe25Evan Cheng SmallVector<unsigned, 2> &FoldOps) { 930749c6f6b5ed301c84aac562e414486549d7b98ebChris Lattner const TargetInstrDesc &TID = MI->getDesc(); 9316e141fd04897e5eb4925bb6351297170ebd8a756Evan Cheng 93279a0c1e46c4f7d8a2a06f4ef3e2c54d883c7fe25Evan Cheng MRInfo = 0; 933aee4af68ae2016afc5b4ec0c430e539c5810a766Evan Cheng for (unsigned i = 0, e = Ops.size(); i != e; ++i) { 934aee4af68ae2016afc5b4ec0c430e539c5810a766Evan Cheng unsigned OpIdx = Ops[i]; 935d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng MachineOperand &MO = MI->getOperand(OpIdx); 936aee4af68ae2016afc5b4ec0c430e539c5810a766Evan Cheng // FIXME: fold subreg use. 937d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng if (MO.getSubReg()) 93879a0c1e46c4f7d8a2a06f4ef3e2c54d883c7fe25Evan Cheng return true; 939d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng if (MO.isDef()) 940aee4af68ae2016afc5b4ec0c430e539c5810a766Evan Cheng MRInfo |= (unsigned)VirtRegMap::isMod; 941aee4af68ae2016afc5b4ec0c430e539c5810a766Evan Cheng else { 942aee4af68ae2016afc5b4ec0c430e539c5810a766Evan Cheng // Filter out two-address use operand(s). 943d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng if (!MO.isImplicit() && 944d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng TID.getOperandConstraint(OpIdx, TOI::TIED_TO) != -1) { 945aee4af68ae2016afc5b4ec0c430e539c5810a766Evan Cheng MRInfo = VirtRegMap::isModRef; 946aee4af68ae2016afc5b4ec0c430e539c5810a766Evan Cheng continue; 947aee4af68ae2016afc5b4ec0c430e539c5810a766Evan Cheng } 948aee4af68ae2016afc5b4ec0c430e539c5810a766Evan Cheng MRInfo |= (unsigned)VirtRegMap::isRef; 949aee4af68ae2016afc5b4ec0c430e539c5810a766Evan Cheng } 950aee4af68ae2016afc5b4ec0c430e539c5810a766Evan Cheng FoldOps.push_back(OpIdx); 951e62f97c094dba44e4c259d20135167fa91912eeaEvan Cheng } 95279a0c1e46c4f7d8a2a06f4ef3e2c54d883c7fe25Evan Cheng return false; 95379a0c1e46c4f7d8a2a06f4ef3e2c54d883c7fe25Evan Cheng} 95479a0c1e46c4f7d8a2a06f4ef3e2c54d883c7fe25Evan Cheng 95579a0c1e46c4f7d8a2a06f4ef3e2c54d883c7fe25Evan Cheng 95679a0c1e46c4f7d8a2a06f4ef3e2c54d883c7fe25Evan Cheng/// tryFoldMemoryOperand - Attempts to fold either a spill / restore from 95779a0c1e46c4f7d8a2a06f4ef3e2c54d883c7fe25Evan Cheng/// slot / to reg or any rematerialized load into ith operand of specified 95879a0c1e46c4f7d8a2a06f4ef3e2c54d883c7fe25Evan Cheng/// MI. If it is successul, MI is updated with the newly created MI and 95979a0c1e46c4f7d8a2a06f4ef3e2c54d883c7fe25Evan Cheng/// returns true. 96079a0c1e46c4f7d8a2a06f4ef3e2c54d883c7fe25Evan Chengbool LiveIntervals::tryFoldMemoryOperand(MachineInstr* &MI, 96179a0c1e46c4f7d8a2a06f4ef3e2c54d883c7fe25Evan Cheng VirtRegMap &vrm, MachineInstr *DefMI, 96279a0c1e46c4f7d8a2a06f4ef3e2c54d883c7fe25Evan Cheng unsigned InstrIdx, 96379a0c1e46c4f7d8a2a06f4ef3e2c54d883c7fe25Evan Cheng SmallVector<unsigned, 2> &Ops, 96479a0c1e46c4f7d8a2a06f4ef3e2c54d883c7fe25Evan Cheng bool isSS, int Slot, unsigned Reg) { 96579a0c1e46c4f7d8a2a06f4ef3e2c54d883c7fe25Evan Cheng // If it is an implicit def instruction, just delete it. 96620ccded7dec5b90e58f649f4fb95b166a642b8cbEvan Cheng if (MI->getOpcode() == TargetInstrInfo::IMPLICIT_DEF) { 96779a0c1e46c4f7d8a2a06f4ef3e2c54d883c7fe25Evan Cheng RemoveMachineInstrFromMaps(MI); 96879a0c1e46c4f7d8a2a06f4ef3e2c54d883c7fe25Evan Cheng vrm.RemoveMachineInstrFromMaps(MI); 96979a0c1e46c4f7d8a2a06f4ef3e2c54d883c7fe25Evan Cheng MI->eraseFromParent(); 97079a0c1e46c4f7d8a2a06f4ef3e2c54d883c7fe25Evan Cheng ++numFolds; 97179a0c1e46c4f7d8a2a06f4ef3e2c54d883c7fe25Evan Cheng return true; 97279a0c1e46c4f7d8a2a06f4ef3e2c54d883c7fe25Evan Cheng } 97379a0c1e46c4f7d8a2a06f4ef3e2c54d883c7fe25Evan Cheng 97479a0c1e46c4f7d8a2a06f4ef3e2c54d883c7fe25Evan Cheng // Filter the list of operand indexes that are to be folded. Abort if 97579a0c1e46c4f7d8a2a06f4ef3e2c54d883c7fe25Evan Cheng // any operand will prevent folding. 97679a0c1e46c4f7d8a2a06f4ef3e2c54d883c7fe25Evan Cheng unsigned MRInfo = 0; 97779a0c1e46c4f7d8a2a06f4ef3e2c54d883c7fe25Evan Cheng SmallVector<unsigned, 2> FoldOps; 97879a0c1e46c4f7d8a2a06f4ef3e2c54d883c7fe25Evan Cheng if (FilterFoldedOps(MI, Ops, MRInfo, FoldOps)) 97979a0c1e46c4f7d8a2a06f4ef3e2c54d883c7fe25Evan Cheng return false; 980cddbb83ea82e98658d9f530c50a7b9d23249afc2Evan Cheng 981427f4c106ac14dcf323dc1bbaf1b8040da03c3c7Evan Cheng // The only time it's safe to fold into a two address instruction is when 982427f4c106ac14dcf323dc1bbaf1b8040da03c3c7Evan Cheng // it's folding reload and spill from / into a spill stack slot. 983427f4c106ac14dcf323dc1bbaf1b8040da03c3c7Evan Cheng if (DefMI && (MRInfo & VirtRegMap::isMod)) 984249ded3fa8884f91fded869fb6e251b8aebb0376Evan Cheng return false; 985249ded3fa8884f91fded869fb6e251b8aebb0376Evan Cheng 986f2f8c2ae07b7d9bdbf1b89781c573c7af2bd5e1bEvan Cheng MachineInstr *fmi = isSS ? tii_->foldMemoryOperand(*mf_, MI, FoldOps, Slot) 987f2f8c2ae07b7d9bdbf1b89781c573c7af2bd5e1bEvan Cheng : tii_->foldMemoryOperand(*mf_, MI, FoldOps, DefMI); 988f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng if (fmi) { 989d36531249a9a9500e516148e7e72d4c0a7a4d0eeEvan Cheng // Remember this instruction uses the spill slot. 990d36531249a9a9500e516148e7e72d4c0a7a4d0eeEvan Cheng if (isSS) vrm.addSpillSlotUse(Slot, fmi); 991d36531249a9a9500e516148e7e72d4c0a7a4d0eeEvan Cheng 992f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng // Attempt to fold the memory reference into the instruction. If 993f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng // we can do this, we don't need to insert spill code. 994f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng MachineBasicBlock &MBB = *MI->getParent(); 9958480293f41c11c22762164449e41cd3adb0dd7d8Evan Cheng if (isSS && !mf_->getFrameInfo()->isImmutableObjectIndex(Slot)) 996aee4af68ae2016afc5b4ec0c430e539c5810a766Evan Cheng vrm.virtFolded(Reg, MI, fmi, (VirtRegMap::ModRef)MRInfo); 99781a038218171860ee4c382849c647d3dc841fe8bEvan Cheng vrm.transferSpillPts(MI, fmi); 9980cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng vrm.transferRestorePts(MI, fmi); 999c1f53c742620dd4f2460685477303002bba8a8d8Evan Cheng vrm.transferEmergencySpills(MI, fmi); 1000f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng mi2iMap_.erase(MI); 1001cddbb83ea82e98658d9f530c50a7b9d23249afc2Evan Cheng i2miMap_[InstrIdx /InstrSlots::NUM] = fmi; 1002cddbb83ea82e98658d9f530c50a7b9d23249afc2Evan Cheng mi2iMap_[fmi] = InstrIdx; 1003f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng MI = MBB.insert(MBB.erase(MI), fmi); 10040cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng ++numFolds; 1005f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng return true; 1006f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng } 1007f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng return false; 1008f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng} 1009f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng 1010018f9b020bb12b731b0a7081578e5f82fb35092dEvan Cheng/// canFoldMemoryOperand - Returns true if the specified load / store 1011018f9b020bb12b731b0a7081578e5f82fb35092dEvan Cheng/// folding is possible. 1012018f9b020bb12b731b0a7081578e5f82fb35092dEvan Chengbool LiveIntervals::canFoldMemoryOperand(MachineInstr *MI, 101379a0c1e46c4f7d8a2a06f4ef3e2c54d883c7fe25Evan Cheng SmallVector<unsigned, 2> &Ops, 10143c75ba858b4e2070993cc1241ba74ead17f647d6Evan Cheng bool ReMat) const { 101579a0c1e46c4f7d8a2a06f4ef3e2c54d883c7fe25Evan Cheng // Filter the list of operand indexes that are to be folded. Abort if 101679a0c1e46c4f7d8a2a06f4ef3e2c54d883c7fe25Evan Cheng // any operand will prevent folding. 101779a0c1e46c4f7d8a2a06f4ef3e2c54d883c7fe25Evan Cheng unsigned MRInfo = 0; 1018018f9b020bb12b731b0a7081578e5f82fb35092dEvan Cheng SmallVector<unsigned, 2> FoldOps; 101979a0c1e46c4f7d8a2a06f4ef3e2c54d883c7fe25Evan Cheng if (FilterFoldedOps(MI, Ops, MRInfo, FoldOps)) 102079a0c1e46c4f7d8a2a06f4ef3e2c54d883c7fe25Evan Cheng return false; 1021018f9b020bb12b731b0a7081578e5f82fb35092dEvan Cheng 10223c75ba858b4e2070993cc1241ba74ead17f647d6Evan Cheng // It's only legal to remat for a use, not a def. 10233c75ba858b4e2070993cc1241ba74ead17f647d6Evan Cheng if (ReMat && (MRInfo & VirtRegMap::isMod)) 102479a0c1e46c4f7d8a2a06f4ef3e2c54d883c7fe25Evan Cheng return false; 1025018f9b020bb12b731b0a7081578e5f82fb35092dEvan Cheng 1026d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng return tii_->canFoldMemoryOperand(MI, FoldOps); 1027d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng} 1028d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng 102981a038218171860ee4c382849c647d3dc841fe8bEvan Chengbool LiveIntervals::intervalIsInOneMBB(const LiveInterval &li) const { 103081a038218171860ee4c382849c647d3dc841fe8bEvan Cheng SmallPtrSet<MachineBasicBlock*, 4> MBBs; 103181a038218171860ee4c382849c647d3dc841fe8bEvan Cheng for (LiveInterval::Ranges::const_iterator 103281a038218171860ee4c382849c647d3dc841fe8bEvan Cheng I = li.ranges.begin(), E = li.ranges.end(); I != E; ++I) { 103381a038218171860ee4c382849c647d3dc841fe8bEvan Cheng std::vector<IdxMBBPair>::const_iterator II = 103481a038218171860ee4c382849c647d3dc841fe8bEvan Cheng std::lower_bound(Idx2MBBMap.begin(), Idx2MBBMap.end(), I->start); 103581a038218171860ee4c382849c647d3dc841fe8bEvan Cheng if (II == Idx2MBBMap.end()) 103681a038218171860ee4c382849c647d3dc841fe8bEvan Cheng continue; 103781a038218171860ee4c382849c647d3dc841fe8bEvan Cheng if (I->end > II->first) // crossing a MBB. 103881a038218171860ee4c382849c647d3dc841fe8bEvan Cheng return false; 103981a038218171860ee4c382849c647d3dc841fe8bEvan Cheng MBBs.insert(II->second); 104081a038218171860ee4c382849c647d3dc841fe8bEvan Cheng if (MBBs.size() > 1) 104181a038218171860ee4c382849c647d3dc841fe8bEvan Cheng return false; 104281a038218171860ee4c382849c647d3dc841fe8bEvan Cheng } 104381a038218171860ee4c382849c647d3dc841fe8bEvan Cheng return true; 104481a038218171860ee4c382849c647d3dc841fe8bEvan Cheng} 104581a038218171860ee4c382849c647d3dc841fe8bEvan Cheng 1046d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng/// rewriteImplicitOps - Rewrite implicit use operands of MI (i.e. uses of 1047d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng/// interval on to-be re-materialized operands of MI) with new register. 1048d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Chengvoid LiveIntervals::rewriteImplicitOps(const LiveInterval &li, 1049d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng MachineInstr *MI, unsigned NewVReg, 1050d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng VirtRegMap &vrm) { 1051d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng // There is an implicit use. That means one of the other operand is 1052d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng // being remat'ed and the remat'ed instruction has li.reg as an 1053d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng // use operand. Make sure we rewrite that as well. 1054d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) { 1055d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng MachineOperand &MO = MI->getOperand(i); 1056d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng if (!MO.isRegister()) 1057d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng continue; 1058d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng unsigned Reg = MO.getReg(); 1059d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng if (Reg == 0 || TargetRegisterInfo::isPhysicalRegister(Reg)) 1060d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng continue; 1061d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng if (!vrm.isReMaterialized(Reg)) 1062d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng continue; 1063d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng MachineInstr *ReMatMI = vrm.getReMaterializedMI(Reg); 10646130f66eaae89f8878590796977678afa8448926Evan Cheng MachineOperand *UseMO = ReMatMI->findRegisterUseOperand(li.reg); 10656130f66eaae89f8878590796977678afa8448926Evan Cheng if (UseMO) 10666130f66eaae89f8878590796977678afa8448926Evan Cheng UseMO->setReg(NewVReg); 1067d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng } 1068d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng} 1069d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng 1070f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng/// rewriteInstructionForSpills, rewriteInstructionsForSpills - Helper functions 1071f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng/// for addIntervalsForSpills to rewrite uses / defs for the given live range. 1072018f9b020bb12b731b0a7081578e5f82fb35092dEvan Chengbool LiveIntervals:: 1073d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan ChengrewriteInstructionForSpills(const LiveInterval &li, const VNInfo *VNI, 1074d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng bool TrySplit, unsigned index, unsigned end, MachineInstr *MI, 107581a038218171860ee4c382849c647d3dc841fe8bEvan Cheng MachineInstr *ReMatOrigDefMI, MachineInstr *ReMatDefMI, 1076f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng unsigned Slot, int LdSlot, 1077f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng bool isLoad, bool isLoadSS, bool DefIsReMat, bool CanDelete, 1078d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng VirtRegMap &vrm, 1079f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng const TargetRegisterClass* rc, 1080f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng SmallVector<int, 4> &ReMatIds, 108122f07ffd27d1d721634d502c37267721d2e025cfEvan Cheng const MachineLoopInfo *loopInfo, 1082313d4b809326f3e04814f94e5b8ae05649d8e0f6Evan Cheng unsigned &NewVReg, unsigned ImpUse, bool &HasDef, bool &HasUse, 10831953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng std::map<unsigned,unsigned> &MBBVRegsMap, 10849c3c2213647e3f1b71722d61875ebac01b65cb91Evan Cheng std::vector<LiveInterval*> &NewLIs, float &SSWeight) { 10859c3c2213647e3f1b71722d61875ebac01b65cb91Evan Cheng MachineBasicBlock *MBB = MI->getParent(); 10869c3c2213647e3f1b71722d61875ebac01b65cb91Evan Cheng unsigned loopDepth = loopInfo->getLoopDepth(MBB); 1087018f9b020bb12b731b0a7081578e5f82fb35092dEvan Cheng bool CanFold = false; 1088f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng RestartInstruction: 1089f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng for (unsigned i = 0; i != MI->getNumOperands(); ++i) { 1090f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng MachineOperand& mop = MI->getOperand(i); 1091f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng if (!mop.isRegister()) 1092f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng continue; 1093f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng unsigned Reg = mop.getReg(); 1094f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng unsigned RegI = Reg; 10956f0d024a534af18d9e60b3ea757376cd8a3a980eDan Gohman if (Reg == 0 || TargetRegisterInfo::isPhysicalRegister(Reg)) 1096f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng continue; 1097f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng if (Reg != li.reg) 1098f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng continue; 1099f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng 1100f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng bool TryFold = !DefIsReMat; 1101cb3c330d39442130d0587208d673ce9c33c7008fEvan Cheng bool FoldSS = true; // Default behavior unless it's a remat. 1102f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng int FoldSlot = Slot; 1103f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng if (DefIsReMat) { 1104f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng // If this is the rematerializable definition MI itself and 1105f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng // all of its uses are rematerialized, simply delete it. 110681a038218171860ee4c382849c647d3dc841fe8bEvan Cheng if (MI == ReMatOrigDefMI && CanDelete) { 1107cddbb83ea82e98658d9f530c50a7b9d23249afc2Evan Cheng DOUT << "\t\t\t\tErasing re-materlizable def: "; 1108cddbb83ea82e98658d9f530c50a7b9d23249afc2Evan Cheng DOUT << MI << '\n'; 1109f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng RemoveMachineInstrFromMaps(MI); 1110cada245d06959831b90f8c29f92e77beda4b71cbEvan Cheng vrm.RemoveMachineInstrFromMaps(MI); 1111f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng MI->eraseFromParent(); 1112f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng break; 1113f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng } 1114f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng 1115f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng // If def for this use can't be rematerialized, then try folding. 11160cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng // If def is rematerializable and it's a load, also try folding. 1117cb3c330d39442130d0587208d673ce9c33c7008fEvan Cheng TryFold = !ReMatDefMI || (ReMatDefMI && (MI == ReMatOrigDefMI || isLoad)); 1118f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng if (isLoad) { 1119f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng // Try fold loads (from stack slot, constant pool, etc.) into uses. 1120f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng FoldSS = isLoadSS; 1121f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng FoldSlot = LdSlot; 1122f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng } 1123f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng } 1124f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng 1125f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng // Scan all of the operands of this instruction rewriting operands 1126f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng // to use NewVReg instead of li.reg as appropriate. We do this for 1127f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng // two reasons: 1128f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng // 1129f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng // 1. If the instr reads the same spilled vreg multiple times, we 1130f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng // want to reuse the NewVReg. 1131f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng // 2. If the instr is a two-addr instruction, we are required to 1132f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng // keep the src/dst regs pinned. 1133f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng // 1134f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng // Keep track of whether we replace a use and/or def so that we can 1135f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng // create the spill interval with the appropriate range. 1136cddbb83ea82e98658d9f530c50a7b9d23249afc2Evan Cheng 113781a038218171860ee4c382849c647d3dc841fe8bEvan Cheng HasUse = mop.isUse(); 113881a038218171860ee4c382849c647d3dc841fe8bEvan Cheng HasDef = mop.isDef(); 1139aee4af68ae2016afc5b4ec0c430e539c5810a766Evan Cheng SmallVector<unsigned, 2> Ops; 1140aee4af68ae2016afc5b4ec0c430e539c5810a766Evan Cheng Ops.push_back(i); 1141f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng for (unsigned j = i+1, e = MI->getNumOperands(); j != e; ++j) { 1142aee4af68ae2016afc5b4ec0c430e539c5810a766Evan Cheng const MachineOperand &MOj = MI->getOperand(j); 1143aee4af68ae2016afc5b4ec0c430e539c5810a766Evan Cheng if (!MOj.isRegister()) 1144f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng continue; 1145aee4af68ae2016afc5b4ec0c430e539c5810a766Evan Cheng unsigned RegJ = MOj.getReg(); 11466f0d024a534af18d9e60b3ea757376cd8a3a980eDan Gohman if (RegJ == 0 || TargetRegisterInfo::isPhysicalRegister(RegJ)) 1147f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng continue; 1148f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng if (RegJ == RegI) { 1149aee4af68ae2016afc5b4ec0c430e539c5810a766Evan Cheng Ops.push_back(j); 1150aee4af68ae2016afc5b4ec0c430e539c5810a766Evan Cheng HasUse |= MOj.isUse(); 1151aee4af68ae2016afc5b4ec0c430e539c5810a766Evan Cheng HasDef |= MOj.isDef(); 1152f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng } 1153f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng } 1154f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng 115579a796c2b17c7ebd4dd489b5de1078fc2148adbaEvan Cheng if (HasUse && !li.liveAt(getUseIndex(index))) 115679a796c2b17c7ebd4dd489b5de1078fc2148adbaEvan Cheng // Must be defined by an implicit def. It should not be spilled. Note, 115779a796c2b17c7ebd4dd489b5de1078fc2148adbaEvan Cheng // this is for correctness reason. e.g. 115879a796c2b17c7ebd4dd489b5de1078fc2148adbaEvan Cheng // 8 %reg1024<def> = IMPLICIT_DEF 115979a796c2b17c7ebd4dd489b5de1078fc2148adbaEvan Cheng // 12 %reg1024<def> = INSERT_SUBREG %reg1024<kill>, %reg1025, 2 116079a796c2b17c7ebd4dd489b5de1078fc2148adbaEvan Cheng // The live range [12, 14) are not part of the r1024 live interval since 116179a796c2b17c7ebd4dd489b5de1078fc2148adbaEvan Cheng // it's defined by an implicit def. It will not conflicts with live 116279a796c2b17c7ebd4dd489b5de1078fc2148adbaEvan Cheng // interval of r1025. Now suppose both registers are spilled, you can 1163b9890ae3c35ad7d8e49261650d5b98f49f97a705Evan Cheng // easily see a situation where both registers are reloaded before 116479a796c2b17c7ebd4dd489b5de1078fc2148adbaEvan Cheng // the INSERT_SUBREG and both target registers that would overlap. 116579a796c2b17c7ebd4dd489b5de1078fc2148adbaEvan Cheng HasUse = false; 116679a796c2b17c7ebd4dd489b5de1078fc2148adbaEvan Cheng 11679c3c2213647e3f1b71722d61875ebac01b65cb91Evan Cheng // Update stack slot spill weight if we are splitting. 1168c3417609ae6e744a29be6962d4fb7811c0102d17Evan Cheng float Weight = getSpillWeight(HasDef, HasUse, loopDepth); 11699c3c2213647e3f1b71722d61875ebac01b65cb91Evan Cheng if (!TrySplit) 11709c3c2213647e3f1b71722d61875ebac01b65cb91Evan Cheng SSWeight += Weight; 11719c3c2213647e3f1b71722d61875ebac01b65cb91Evan Cheng 11729c3c2213647e3f1b71722d61875ebac01b65cb91Evan Cheng if (!TryFold) 11739c3c2213647e3f1b71722d61875ebac01b65cb91Evan Cheng CanFold = false; 11749c3c2213647e3f1b71722d61875ebac01b65cb91Evan Cheng else { 1175018f9b020bb12b731b0a7081578e5f82fb35092dEvan Cheng // Do not fold load / store here if we are splitting. We'll find an 1176018f9b020bb12b731b0a7081578e5f82fb35092dEvan Cheng // optimal point to insert a load / store later. 1177018f9b020bb12b731b0a7081578e5f82fb35092dEvan Cheng if (!TrySplit) { 1178018f9b020bb12b731b0a7081578e5f82fb35092dEvan Cheng if (tryFoldMemoryOperand(MI, vrm, ReMatDefMI, index, 1179018f9b020bb12b731b0a7081578e5f82fb35092dEvan Cheng Ops, FoldSS, FoldSlot, Reg)) { 1180018f9b020bb12b731b0a7081578e5f82fb35092dEvan Cheng // Folding the load/store can completely change the instruction in 1181018f9b020bb12b731b0a7081578e5f82fb35092dEvan Cheng // unpredictable ways, rescan it from the beginning. 1182018f9b020bb12b731b0a7081578e5f82fb35092dEvan Cheng HasUse = false; 1183018f9b020bb12b731b0a7081578e5f82fb35092dEvan Cheng HasDef = false; 1184018f9b020bb12b731b0a7081578e5f82fb35092dEvan Cheng CanFold = false; 11859c3c2213647e3f1b71722d61875ebac01b65cb91Evan Cheng if (isRemoved(MI)) { 11869c3c2213647e3f1b71722d61875ebac01b65cb91Evan Cheng SSWeight -= Weight; 11877e073baedb8232b9519dbe15ea141ff98ccfe6aeEvan Cheng break; 11889c3c2213647e3f1b71722d61875ebac01b65cb91Evan Cheng } 1189018f9b020bb12b731b0a7081578e5f82fb35092dEvan Cheng goto RestartInstruction; 1190018f9b020bb12b731b0a7081578e5f82fb35092dEvan Cheng } 1191018f9b020bb12b731b0a7081578e5f82fb35092dEvan Cheng } else { 11929c3c2213647e3f1b71722d61875ebac01b65cb91Evan Cheng // We'll try to fold it later if it's profitable. 11933c75ba858b4e2070993cc1241ba74ead17f647d6Evan Cheng CanFold = canFoldMemoryOperand(MI, Ops, DefIsReMat); 1194018f9b020bb12b731b0a7081578e5f82fb35092dEvan Cheng } 11959c3c2213647e3f1b71722d61875ebac01b65cb91Evan Cheng } 1196cddbb83ea82e98658d9f530c50a7b9d23249afc2Evan Cheng 1197cddbb83ea82e98658d9f530c50a7b9d23249afc2Evan Cheng // Create a new virtual register for the spill interval. 1198cddbb83ea82e98658d9f530c50a7b9d23249afc2Evan Cheng bool CreatedNewVReg = false; 1199cddbb83ea82e98658d9f530c50a7b9d23249afc2Evan Cheng if (NewVReg == 0) { 1200d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng NewVReg = mri_->createVirtualRegister(rc); 1201cddbb83ea82e98658d9f530c50a7b9d23249afc2Evan Cheng vrm.grow(); 1202cddbb83ea82e98658d9f530c50a7b9d23249afc2Evan Cheng CreatedNewVReg = true; 1203cddbb83ea82e98658d9f530c50a7b9d23249afc2Evan Cheng } 1204cddbb83ea82e98658d9f530c50a7b9d23249afc2Evan Cheng mop.setReg(NewVReg); 1205d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng if (mop.isImplicit()) 1206d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng rewriteImplicitOps(li, MI, NewVReg, vrm); 1207cddbb83ea82e98658d9f530c50a7b9d23249afc2Evan Cheng 1208cddbb83ea82e98658d9f530c50a7b9d23249afc2Evan Cheng // Reuse NewVReg for other reads. 1209d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng for (unsigned j = 0, e = Ops.size(); j != e; ++j) { 1210d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng MachineOperand &mopj = MI->getOperand(Ops[j]); 1211d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng mopj.setReg(NewVReg); 1212d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng if (mopj.isImplicit()) 1213d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng rewriteImplicitOps(li, MI, NewVReg, vrm); 1214d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng } 1215cddbb83ea82e98658d9f530c50a7b9d23249afc2Evan Cheng 121681a038218171860ee4c382849c647d3dc841fe8bEvan Cheng if (CreatedNewVReg) { 121781a038218171860ee4c382849c647d3dc841fe8bEvan Cheng if (DefIsReMat) { 121881a038218171860ee4c382849c647d3dc841fe8bEvan Cheng vrm.setVirtIsReMaterialized(NewVReg, ReMatDefMI/*, CanDelete*/); 1219d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng if (ReMatIds[VNI->id] == VirtRegMap::MAX_STACK_SLOT) { 122081a038218171860ee4c382849c647d3dc841fe8bEvan Cheng // Each valnum may have its own remat id. 1221d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng ReMatIds[VNI->id] = vrm.assignVirtReMatId(NewVReg); 122281a038218171860ee4c382849c647d3dc841fe8bEvan Cheng } else { 1223d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng vrm.assignVirtReMatId(NewVReg, ReMatIds[VNI->id]); 122481a038218171860ee4c382849c647d3dc841fe8bEvan Cheng } 122581a038218171860ee4c382849c647d3dc841fe8bEvan Cheng if (!CanDelete || (HasUse && HasDef)) { 122681a038218171860ee4c382849c647d3dc841fe8bEvan Cheng // If this is a two-addr instruction then its use operands are 122781a038218171860ee4c382849c647d3dc841fe8bEvan Cheng // rematerializable but its def is not. It should be assigned a 122881a038218171860ee4c382849c647d3dc841fe8bEvan Cheng // stack slot. 122981a038218171860ee4c382849c647d3dc841fe8bEvan Cheng vrm.assignVirt2StackSlot(NewVReg, Slot); 123081a038218171860ee4c382849c647d3dc841fe8bEvan Cheng } 1231f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng } else { 1232f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng vrm.assignVirt2StackSlot(NewVReg, Slot); 1233f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng } 1234cb3c330d39442130d0587208d673ce9c33c7008fEvan Cheng } else if (HasUse && HasDef && 1235cb3c330d39442130d0587208d673ce9c33c7008fEvan Cheng vrm.getStackSlot(NewVReg) == VirtRegMap::NO_STACK_SLOT) { 1236cb3c330d39442130d0587208d673ce9c33c7008fEvan Cheng // If this interval hasn't been assigned a stack slot (because earlier 1237cb3c330d39442130d0587208d673ce9c33c7008fEvan Cheng // def is a deleted remat def), do it now. 1238cb3c330d39442130d0587208d673ce9c33c7008fEvan Cheng assert(Slot != VirtRegMap::NO_STACK_SLOT); 1239cb3c330d39442130d0587208d673ce9c33c7008fEvan Cheng vrm.assignVirt2StackSlot(NewVReg, Slot); 1240f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng } 1241f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng 1242313d4b809326f3e04814f94e5b8ae05649d8e0f6Evan Cheng // Re-matting an instruction with virtual register use. Add the 1243313d4b809326f3e04814f94e5b8ae05649d8e0f6Evan Cheng // register as an implicit use on the use MI. 1244313d4b809326f3e04814f94e5b8ae05649d8e0f6Evan Cheng if (DefIsReMat && ImpUse) 1245313d4b809326f3e04814f94e5b8ae05649d8e0f6Evan Cheng MI->addOperand(MachineOperand::CreateReg(ImpUse, false, true)); 1246313d4b809326f3e04814f94e5b8ae05649d8e0f6Evan Cheng 1247f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng // create a new register interval for this spill / remat. 1248f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng LiveInterval &nI = getOrCreateInterval(NewVReg); 124981a038218171860ee4c382849c647d3dc841fe8bEvan Cheng if (CreatedNewVReg) { 125081a038218171860ee4c382849c647d3dc841fe8bEvan Cheng NewLIs.push_back(&nI); 12511953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng MBBVRegsMap.insert(std::make_pair(MI->getParent()->getNumber(), NewVReg)); 125281a038218171860ee4c382849c647d3dc841fe8bEvan Cheng if (TrySplit) 125381a038218171860ee4c382849c647d3dc841fe8bEvan Cheng vrm.setIsSplitFromReg(NewVReg, li.reg); 125481a038218171860ee4c382849c647d3dc841fe8bEvan Cheng } 1255f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng 1256f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng if (HasUse) { 125781a038218171860ee4c382849c647d3dc841fe8bEvan Cheng if (CreatedNewVReg) { 125881a038218171860ee4c382849c647d3dc841fe8bEvan Cheng LiveRange LR(getLoadIndex(index), getUseIndex(index)+1, 125981a038218171860ee4c382849c647d3dc841fe8bEvan Cheng nI.getNextValue(~0U, 0, VNInfoAllocator)); 126081a038218171860ee4c382849c647d3dc841fe8bEvan Cheng DOUT << " +" << LR; 126181a038218171860ee4c382849c647d3dc841fe8bEvan Cheng nI.addRange(LR); 126281a038218171860ee4c382849c647d3dc841fe8bEvan Cheng } else { 126381a038218171860ee4c382849c647d3dc841fe8bEvan Cheng // Extend the split live interval to this def / use. 126481a038218171860ee4c382849c647d3dc841fe8bEvan Cheng unsigned End = getUseIndex(index)+1; 126581a038218171860ee4c382849c647d3dc841fe8bEvan Cheng LiveRange LR(nI.ranges[nI.ranges.size()-1].end, End, 126681a038218171860ee4c382849c647d3dc841fe8bEvan Cheng nI.getValNumInfo(nI.getNumValNums()-1)); 126781a038218171860ee4c382849c647d3dc841fe8bEvan Cheng DOUT << " +" << LR; 126881a038218171860ee4c382849c647d3dc841fe8bEvan Cheng nI.addRange(LR); 126981a038218171860ee4c382849c647d3dc841fe8bEvan Cheng } 1270f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng } 1271f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng if (HasDef) { 1272f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng LiveRange LR(getDefIndex(index), getStoreIndex(index), 1273f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng nI.getNextValue(~0U, 0, VNInfoAllocator)); 1274f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng DOUT << " +" << LR; 1275f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng nI.addRange(LR); 1276f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng } 127781a038218171860ee4c382849c647d3dc841fe8bEvan Cheng 1278f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng DOUT << "\t\t\t\tAdded new interval: "; 12796f0d024a534af18d9e60b3ea757376cd8a3a980eDan Gohman nI.print(DOUT, tri_); 1280f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng DOUT << '\n'; 1281f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng } 1282018f9b020bb12b731b0a7081578e5f82fb35092dEvan Cheng return CanFold; 1283f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng} 128481a038218171860ee4c382849c647d3dc841fe8bEvan Chengbool LiveIntervals::anyKillInMBBAfterIdx(const LiveInterval &li, 12850cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng const VNInfo *VNI, 12860cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng MachineBasicBlock *MBB, unsigned Idx) const { 128781a038218171860ee4c382849c647d3dc841fe8bEvan Cheng unsigned End = getMBBEndIdx(MBB); 12880cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng for (unsigned j = 0, ee = VNI->kills.size(); j != ee; ++j) { 12890cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng unsigned KillIdx = VNI->kills[j]; 12900cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng if (KillIdx > Idx && KillIdx < End) 12910cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng return true; 129281a038218171860ee4c382849c647d3dc841fe8bEvan Cheng } 129381a038218171860ee4c382849c647d3dc841fe8bEvan Cheng return false; 129481a038218171860ee4c382849c647d3dc841fe8bEvan Cheng} 129581a038218171860ee4c382849c647d3dc841fe8bEvan Cheng 1296063284c001666c0a3906acbe0a26dc7cae5f081cEvan Cheng/// RewriteInfo - Keep track of machine instrs that will be rewritten 1297063284c001666c0a3906acbe0a26dc7cae5f081cEvan Cheng/// during spilling. 1298844731a7f1909f55935e3514c9e713a62d67662eDan Gohmannamespace { 1299844731a7f1909f55935e3514c9e713a62d67662eDan Gohman struct RewriteInfo { 1300844731a7f1909f55935e3514c9e713a62d67662eDan Gohman unsigned Index; 1301844731a7f1909f55935e3514c9e713a62d67662eDan Gohman MachineInstr *MI; 1302844731a7f1909f55935e3514c9e713a62d67662eDan Gohman bool HasUse; 1303844731a7f1909f55935e3514c9e713a62d67662eDan Gohman bool HasDef; 1304844731a7f1909f55935e3514c9e713a62d67662eDan Gohman RewriteInfo(unsigned i, MachineInstr *mi, bool u, bool d) 1305844731a7f1909f55935e3514c9e713a62d67662eDan Gohman : Index(i), MI(mi), HasUse(u), HasDef(d) {} 1306844731a7f1909f55935e3514c9e713a62d67662eDan Gohman }; 1307844731a7f1909f55935e3514c9e713a62d67662eDan Gohman 1308844731a7f1909f55935e3514c9e713a62d67662eDan Gohman struct RewriteInfoCompare { 1309844731a7f1909f55935e3514c9e713a62d67662eDan Gohman bool operator()(const RewriteInfo &LHS, const RewriteInfo &RHS) const { 1310844731a7f1909f55935e3514c9e713a62d67662eDan Gohman return LHS.Index < RHS.Index; 1311844731a7f1909f55935e3514c9e713a62d67662eDan Gohman } 1312844731a7f1909f55935e3514c9e713a62d67662eDan Gohman }; 1313844731a7f1909f55935e3514c9e713a62d67662eDan Gohman} 1314063284c001666c0a3906acbe0a26dc7cae5f081cEvan Cheng 1315f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Chengvoid LiveIntervals:: 131681a038218171860ee4c382849c647d3dc841fe8bEvan ChengrewriteInstructionsForSpills(const LiveInterval &li, bool TrySplit, 1317f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng LiveInterval::Ranges::const_iterator &I, 131881a038218171860ee4c382849c647d3dc841fe8bEvan Cheng MachineInstr *ReMatOrigDefMI, MachineInstr *ReMatDefMI, 1319f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng unsigned Slot, int LdSlot, 1320f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng bool isLoad, bool isLoadSS, bool DefIsReMat, bool CanDelete, 1321d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng VirtRegMap &vrm, 1322f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng const TargetRegisterClass* rc, 1323f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng SmallVector<int, 4> &ReMatIds, 132422f07ffd27d1d721634d502c37267721d2e025cfEvan Cheng const MachineLoopInfo *loopInfo, 132581a038218171860ee4c382849c647d3dc841fe8bEvan Cheng BitVector &SpillMBBs, 13261953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng std::map<unsigned, std::vector<SRInfo> > &SpillIdxes, 13270cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng BitVector &RestoreMBBs, 13281953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng std::map<unsigned, std::vector<SRInfo> > &RestoreIdxes, 13291953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng std::map<unsigned,unsigned> &MBBVRegsMap, 13309c3c2213647e3f1b71722d61875ebac01b65cb91Evan Cheng std::vector<LiveInterval*> &NewLIs, float &SSWeight) { 1331018f9b020bb12b731b0a7081578e5f82fb35092dEvan Cheng bool AllCanFold = true; 133281a038218171860ee4c382849c647d3dc841fe8bEvan Cheng unsigned NewVReg = 0; 1333063284c001666c0a3906acbe0a26dc7cae5f081cEvan Cheng unsigned start = getBaseIndex(I->start); 1334f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng unsigned end = getBaseIndex(I->end-1) + InstrSlots::NUM; 1335f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng 1336063284c001666c0a3906acbe0a26dc7cae5f081cEvan Cheng // First collect all the def / use in this live range that will be rewritten. 13377e073baedb8232b9519dbe15ea141ff98ccfe6aeEvan Cheng // Make sure they are sorted according to instruction index. 1338063284c001666c0a3906acbe0a26dc7cae5f081cEvan Cheng std::vector<RewriteInfo> RewriteMIs; 1339d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng for (MachineRegisterInfo::reg_iterator ri = mri_->reg_begin(li.reg), 1340d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng re = mri_->reg_end(); ri != re; ) { 1341419852ca8a01aecde4c0e20af6b7bd6450e70f87Evan Cheng MachineInstr *MI = &*ri; 1342063284c001666c0a3906acbe0a26dc7cae5f081cEvan Cheng MachineOperand &O = ri.getOperand(); 1343063284c001666c0a3906acbe0a26dc7cae5f081cEvan Cheng ++ri; 134424d2f8a212f08bf21360122cc00acf2657af91f9Evan Cheng assert(!O.isImplicit() && "Spilling register that's used as implicit use?"); 1345063284c001666c0a3906acbe0a26dc7cae5f081cEvan Cheng unsigned index = getInstructionIndex(MI); 1346063284c001666c0a3906acbe0a26dc7cae5f081cEvan Cheng if (index < start || index >= end) 1347063284c001666c0a3906acbe0a26dc7cae5f081cEvan Cheng continue; 134879a796c2b17c7ebd4dd489b5de1078fc2148adbaEvan Cheng if (O.isUse() && !li.liveAt(getUseIndex(index))) 134979a796c2b17c7ebd4dd489b5de1078fc2148adbaEvan Cheng // Must be defined by an implicit def. It should not be spilled. Note, 135079a796c2b17c7ebd4dd489b5de1078fc2148adbaEvan Cheng // this is for correctness reason. e.g. 135179a796c2b17c7ebd4dd489b5de1078fc2148adbaEvan Cheng // 8 %reg1024<def> = IMPLICIT_DEF 135279a796c2b17c7ebd4dd489b5de1078fc2148adbaEvan Cheng // 12 %reg1024<def> = INSERT_SUBREG %reg1024<kill>, %reg1025, 2 135379a796c2b17c7ebd4dd489b5de1078fc2148adbaEvan Cheng // The live range [12, 14) are not part of the r1024 live interval since 135479a796c2b17c7ebd4dd489b5de1078fc2148adbaEvan Cheng // it's defined by an implicit def. It will not conflicts with live 135579a796c2b17c7ebd4dd489b5de1078fc2148adbaEvan Cheng // interval of r1025. Now suppose both registers are spilled, you can 1356b9890ae3c35ad7d8e49261650d5b98f49f97a705Evan Cheng // easily see a situation where both registers are reloaded before 135779a796c2b17c7ebd4dd489b5de1078fc2148adbaEvan Cheng // the INSERT_SUBREG and both target registers that would overlap. 135879a796c2b17c7ebd4dd489b5de1078fc2148adbaEvan Cheng continue; 1359063284c001666c0a3906acbe0a26dc7cae5f081cEvan Cheng RewriteMIs.push_back(RewriteInfo(index, MI, O.isUse(), O.isDef())); 1360063284c001666c0a3906acbe0a26dc7cae5f081cEvan Cheng } 1361063284c001666c0a3906acbe0a26dc7cae5f081cEvan Cheng std::sort(RewriteMIs.begin(), RewriteMIs.end(), RewriteInfoCompare()); 1362063284c001666c0a3906acbe0a26dc7cae5f081cEvan Cheng 1363313d4b809326f3e04814f94e5b8ae05649d8e0f6Evan Cheng unsigned ImpUse = DefIsReMat ? getReMatImplicitUse(li, ReMatDefMI) : 0; 1364063284c001666c0a3906acbe0a26dc7cae5f081cEvan Cheng // Now rewrite the defs and uses. 1365063284c001666c0a3906acbe0a26dc7cae5f081cEvan Cheng for (unsigned i = 0, e = RewriteMIs.size(); i != e; ) { 1366063284c001666c0a3906acbe0a26dc7cae5f081cEvan Cheng RewriteInfo &rwi = RewriteMIs[i]; 1367063284c001666c0a3906acbe0a26dc7cae5f081cEvan Cheng ++i; 1368063284c001666c0a3906acbe0a26dc7cae5f081cEvan Cheng unsigned index = rwi.Index; 1369063284c001666c0a3906acbe0a26dc7cae5f081cEvan Cheng bool MIHasUse = rwi.HasUse; 1370063284c001666c0a3906acbe0a26dc7cae5f081cEvan Cheng bool MIHasDef = rwi.HasDef; 1371063284c001666c0a3906acbe0a26dc7cae5f081cEvan Cheng MachineInstr *MI = rwi.MI; 1372063284c001666c0a3906acbe0a26dc7cae5f081cEvan Cheng // If MI def and/or use the same register multiple times, then there 1373063284c001666c0a3906acbe0a26dc7cae5f081cEvan Cheng // are multiple entries. 1374313d4b809326f3e04814f94e5b8ae05649d8e0f6Evan Cheng unsigned NumUses = MIHasUse; 1375063284c001666c0a3906acbe0a26dc7cae5f081cEvan Cheng while (i != e && RewriteMIs[i].MI == MI) { 1376063284c001666c0a3906acbe0a26dc7cae5f081cEvan Cheng assert(RewriteMIs[i].Index == index); 1377313d4b809326f3e04814f94e5b8ae05649d8e0f6Evan Cheng bool isUse = RewriteMIs[i].HasUse; 1378313d4b809326f3e04814f94e5b8ae05649d8e0f6Evan Cheng if (isUse) ++NumUses; 1379313d4b809326f3e04814f94e5b8ae05649d8e0f6Evan Cheng MIHasUse |= isUse; 1380063284c001666c0a3906acbe0a26dc7cae5f081cEvan Cheng MIHasDef |= RewriteMIs[i].HasDef; 1381063284c001666c0a3906acbe0a26dc7cae5f081cEvan Cheng ++i; 1382063284c001666c0a3906acbe0a26dc7cae5f081cEvan Cheng } 138381a038218171860ee4c382849c647d3dc841fe8bEvan Cheng MachineBasicBlock *MBB = MI->getParent(); 1384313d4b809326f3e04814f94e5b8ae05649d8e0f6Evan Cheng 13850a891ed7d5875a9ccdb93b4472b0f43947d8289bEvan Cheng if (ImpUse && MI != ReMatDefMI) { 1386313d4b809326f3e04814f94e5b8ae05649d8e0f6Evan Cheng // Re-matting an instruction with virtual register use. Update the 138724d2f8a212f08bf21360122cc00acf2657af91f9Evan Cheng // register interval's spill weight to HUGE_VALF to prevent it from 138824d2f8a212f08bf21360122cc00acf2657af91f9Evan Cheng // being spilled. 1389313d4b809326f3e04814f94e5b8ae05649d8e0f6Evan Cheng LiveInterval &ImpLi = getInterval(ImpUse); 139024d2f8a212f08bf21360122cc00acf2657af91f9Evan Cheng ImpLi.weight = HUGE_VALF; 1391313d4b809326f3e04814f94e5b8ae05649d8e0f6Evan Cheng } 1392313d4b809326f3e04814f94e5b8ae05649d8e0f6Evan Cheng 1393063284c001666c0a3906acbe0a26dc7cae5f081cEvan Cheng unsigned MBBId = MBB->getNumber(); 1394018f9b020bb12b731b0a7081578e5f82fb35092dEvan Cheng unsigned ThisVReg = 0; 139570306f8348f27c61cfed5a60e2fceac0f29746a2Evan Cheng if (TrySplit) { 1396063284c001666c0a3906acbe0a26dc7cae5f081cEvan Cheng std::map<unsigned,unsigned>::const_iterator NVI = MBBVRegsMap.find(MBBId); 13971953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng if (NVI != MBBVRegsMap.end()) { 1398018f9b020bb12b731b0a7081578e5f82fb35092dEvan Cheng ThisVReg = NVI->second; 13991953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng // One common case: 14001953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng // x = use 14011953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng // ... 14021953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng // ... 14031953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng // def = ... 14041953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng // = use 14051953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng // It's better to start a new interval to avoid artifically 14061953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng // extend the new interval. 14071953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng if (MIHasDef && !MIHasUse) { 14081953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng MBBVRegsMap.erase(MBB->getNumber()); 1409018f9b020bb12b731b0a7081578e5f82fb35092dEvan Cheng ThisVReg = 0; 14101953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng } 14111953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng } 1412cada245d06959831b90f8c29f92e77beda4b71cbEvan Cheng } 1413018f9b020bb12b731b0a7081578e5f82fb35092dEvan Cheng 1414018f9b020bb12b731b0a7081578e5f82fb35092dEvan Cheng bool IsNew = ThisVReg == 0; 1415018f9b020bb12b731b0a7081578e5f82fb35092dEvan Cheng if (IsNew) { 1416018f9b020bb12b731b0a7081578e5f82fb35092dEvan Cheng // This ends the previous live interval. If all of its def / use 1417018f9b020bb12b731b0a7081578e5f82fb35092dEvan Cheng // can be folded, give it a low spill weight. 1418018f9b020bb12b731b0a7081578e5f82fb35092dEvan Cheng if (NewVReg && TrySplit && AllCanFold) { 1419018f9b020bb12b731b0a7081578e5f82fb35092dEvan Cheng LiveInterval &nI = getOrCreateInterval(NewVReg); 1420018f9b020bb12b731b0a7081578e5f82fb35092dEvan Cheng nI.weight /= 10.0F; 1421018f9b020bb12b731b0a7081578e5f82fb35092dEvan Cheng } 1422018f9b020bb12b731b0a7081578e5f82fb35092dEvan Cheng AllCanFold = true; 1423018f9b020bb12b731b0a7081578e5f82fb35092dEvan Cheng } 1424018f9b020bb12b731b0a7081578e5f82fb35092dEvan Cheng NewVReg = ThisVReg; 1425018f9b020bb12b731b0a7081578e5f82fb35092dEvan Cheng 142681a038218171860ee4c382849c647d3dc841fe8bEvan Cheng bool HasDef = false; 142781a038218171860ee4c382849c647d3dc841fe8bEvan Cheng bool HasUse = false; 1428d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng bool CanFold = rewriteInstructionForSpills(li, I->valno, TrySplit, 14299c3c2213647e3f1b71722d61875ebac01b65cb91Evan Cheng index, end, MI, ReMatOrigDefMI, ReMatDefMI, 14309c3c2213647e3f1b71722d61875ebac01b65cb91Evan Cheng Slot, LdSlot, isLoad, isLoadSS, DefIsReMat, 14319c3c2213647e3f1b71722d61875ebac01b65cb91Evan Cheng CanDelete, vrm, rc, ReMatIds, loopInfo, NewVReg, 14329c3c2213647e3f1b71722d61875ebac01b65cb91Evan Cheng ImpUse, HasDef, HasUse, MBBVRegsMap, NewLIs, SSWeight); 143381a038218171860ee4c382849c647d3dc841fe8bEvan Cheng if (!HasDef && !HasUse) 143481a038218171860ee4c382849c647d3dc841fe8bEvan Cheng continue; 143581a038218171860ee4c382849c647d3dc841fe8bEvan Cheng 1436018f9b020bb12b731b0a7081578e5f82fb35092dEvan Cheng AllCanFold &= CanFold; 1437018f9b020bb12b731b0a7081578e5f82fb35092dEvan Cheng 143881a038218171860ee4c382849c647d3dc841fe8bEvan Cheng // Update weight of spill interval. 143981a038218171860ee4c382849c647d3dc841fe8bEvan Cheng LiveInterval &nI = getOrCreateInterval(NewVReg); 144070306f8348f27c61cfed5a60e2fceac0f29746a2Evan Cheng if (!TrySplit) { 144181a038218171860ee4c382849c647d3dc841fe8bEvan Cheng // The spill weight is now infinity as it cannot be spilled again. 144281a038218171860ee4c382849c647d3dc841fe8bEvan Cheng nI.weight = HUGE_VALF; 14430cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng continue; 14440cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng } 14450cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng 14460cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng // Keep track of the last def and first use in each MBB. 14470cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng if (HasDef) { 14480cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng if (MI != ReMatOrigDefMI || !CanDelete) { 14490cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng bool HasKill = false; 14500cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng if (!HasUse) 14510cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng HasKill = anyKillInMBBAfterIdx(li, I->valno, MBB, getDefIndex(index)); 14520cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng else { 14531953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng // If this is a two-address code, then this index starts a new VNInfo. 14543f32d65912b4da23793dab618d981be2ce11c331Evan Cheng const VNInfo *VNI = li.findDefinedVNInfo(getDefIndex(index)); 14550cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng if (VNI) 14560cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng HasKill = anyKillInMBBAfterIdx(li, VNI, MBB, getDefIndex(index)); 145781a038218171860ee4c382849c647d3dc841fe8bEvan Cheng } 1458e3110d0825e6316fd2dd21d6a4e593295cd413f1Evan Cheng std::map<unsigned, std::vector<SRInfo> >::iterator SII = 1459e3110d0825e6316fd2dd21d6a4e593295cd413f1Evan Cheng SpillIdxes.find(MBBId); 14600cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng if (!HasKill) { 14611953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng if (SII == SpillIdxes.end()) { 14621953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng std::vector<SRInfo> S; 14631953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng S.push_back(SRInfo(index, NewVReg, true)); 14641953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng SpillIdxes.insert(std::make_pair(MBBId, S)); 14651953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng } else if (SII->second.back().vreg != NewVReg) { 14661953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng SII->second.push_back(SRInfo(index, NewVReg, true)); 14671953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng } else if ((int)index > SII->second.back().index) { 14680cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng // If there is an earlier def and this is a two-address 14690cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng // instruction, then it's not possible to fold the store (which 14700cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng // would also fold the load). 14711953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng SRInfo &Info = SII->second.back(); 14721953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng Info.index = index; 14731953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng Info.canFold = !HasUse; 147481a038218171860ee4c382849c647d3dc841fe8bEvan Cheng } 14750cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng SpillMBBs.set(MBBId); 1476e3110d0825e6316fd2dd21d6a4e593295cd413f1Evan Cheng } else if (SII != SpillIdxes.end() && 1477e3110d0825e6316fd2dd21d6a4e593295cd413f1Evan Cheng SII->second.back().vreg == NewVReg && 1478e3110d0825e6316fd2dd21d6a4e593295cd413f1Evan Cheng (int)index > SII->second.back().index) { 1479e3110d0825e6316fd2dd21d6a4e593295cd413f1Evan Cheng // There is an earlier def that's not killed (must be two-address). 1480e3110d0825e6316fd2dd21d6a4e593295cd413f1Evan Cheng // The spill is no longer needed. 1481e3110d0825e6316fd2dd21d6a4e593295cd413f1Evan Cheng SII->second.pop_back(); 1482e3110d0825e6316fd2dd21d6a4e593295cd413f1Evan Cheng if (SII->second.empty()) { 1483e3110d0825e6316fd2dd21d6a4e593295cd413f1Evan Cheng SpillIdxes.erase(MBBId); 1484e3110d0825e6316fd2dd21d6a4e593295cd413f1Evan Cheng SpillMBBs.reset(MBBId); 1485e3110d0825e6316fd2dd21d6a4e593295cd413f1Evan Cheng } 148681a038218171860ee4c382849c647d3dc841fe8bEvan Cheng } 148781a038218171860ee4c382849c647d3dc841fe8bEvan Cheng } 14880cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng } 148981a038218171860ee4c382849c647d3dc841fe8bEvan Cheng 14900cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng if (HasUse) { 14911953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng std::map<unsigned, std::vector<SRInfo> >::iterator SII = 14920cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng SpillIdxes.find(MBBId); 14931953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng if (SII != SpillIdxes.end() && 14941953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng SII->second.back().vreg == NewVReg && 14951953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng (int)index > SII->second.back().index) 14960cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng // Use(s) following the last def, it's not safe to fold the spill. 14971953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng SII->second.back().canFold = false; 14981953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng std::map<unsigned, std::vector<SRInfo> >::iterator RII = 14990cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng RestoreIdxes.find(MBBId); 15001953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng if (RII != RestoreIdxes.end() && RII->second.back().vreg == NewVReg) 15010cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng // If we are splitting live intervals, only fold if it's the first 15020cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng // use and there isn't another use later in the MBB. 15031953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng RII->second.back().canFold = false; 15040cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng else if (IsNew) { 15050cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng // Only need a reload if there isn't an earlier def / use. 15061953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng if (RII == RestoreIdxes.end()) { 15071953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng std::vector<SRInfo> Infos; 15081953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng Infos.push_back(SRInfo(index, NewVReg, true)); 15091953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng RestoreIdxes.insert(std::make_pair(MBBId, Infos)); 15101953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng } else { 15111953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng RII->second.push_back(SRInfo(index, NewVReg, true)); 15121953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng } 15130cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng RestoreMBBs.set(MBBId); 15140cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng } 151581a038218171860ee4c382849c647d3dc841fe8bEvan Cheng } 15160cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng 15170cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng // Update spill weight. 151822f07ffd27d1d721634d502c37267721d2e025cfEvan Cheng unsigned loopDepth = loopInfo->getLoopDepth(MBB); 1519c3417609ae6e744a29be6962d4fb7811c0102d17Evan Cheng nI.weight += getSpillWeight(HasDef, HasUse, loopDepth); 1520f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng } 1521018f9b020bb12b731b0a7081578e5f82fb35092dEvan Cheng 1522018f9b020bb12b731b0a7081578e5f82fb35092dEvan Cheng if (NewVReg && TrySplit && AllCanFold) { 1523018f9b020bb12b731b0a7081578e5f82fb35092dEvan Cheng // If all of its def / use can be folded, give it a low spill weight. 1524018f9b020bb12b731b0a7081578e5f82fb35092dEvan Cheng LiveInterval &nI = getOrCreateInterval(NewVReg); 1525018f9b020bb12b731b0a7081578e5f82fb35092dEvan Cheng nI.weight /= 10.0F; 1526018f9b020bb12b731b0a7081578e5f82fb35092dEvan Cheng } 1527f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng} 1528f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng 15291953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Chengbool LiveIntervals::alsoFoldARestore(int Id, int index, unsigned vr, 15301953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng BitVector &RestoreMBBs, 15311953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng std::map<unsigned,std::vector<SRInfo> > &RestoreIdxes) { 15321953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng if (!RestoreMBBs[Id]) 15331953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng return false; 15341953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng std::vector<SRInfo> &Restores = RestoreIdxes[Id]; 15351953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng for (unsigned i = 0, e = Restores.size(); i != e; ++i) 15361953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng if (Restores[i].index == index && 15371953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng Restores[i].vreg == vr && 15381953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng Restores[i].canFold) 15391953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng return true; 15401953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng return false; 15411953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng} 15421953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng 15431953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Chengvoid LiveIntervals::eraseRestoreInfo(int Id, int index, unsigned vr, 15441953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng BitVector &RestoreMBBs, 15451953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng std::map<unsigned,std::vector<SRInfo> > &RestoreIdxes) { 15461953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng if (!RestoreMBBs[Id]) 15471953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng return; 15481953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng std::vector<SRInfo> &Restores = RestoreIdxes[Id]; 15491953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng for (unsigned i = 0, e = Restores.size(); i != e; ++i) 15501953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng if (Restores[i].index == index && Restores[i].vreg) 15511953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng Restores[i].index = -1; 15521953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng} 155381a038218171860ee4c382849c647d3dc841fe8bEvan Cheng 15544cce6b4c7882ef0cc993d931b90bf33985c96110Evan Cheng/// handleSpilledImpDefs - Remove IMPLICIT_DEF instructions which are being 15554cce6b4c7882ef0cc993d931b90bf33985c96110Evan Cheng/// spilled and create empty intervals for their uses. 15564cce6b4c7882ef0cc993d931b90bf33985c96110Evan Chengvoid 15574cce6b4c7882ef0cc993d931b90bf33985c96110Evan ChengLiveIntervals::handleSpilledImpDefs(const LiveInterval &li, VirtRegMap &vrm, 15584cce6b4c7882ef0cc993d931b90bf33985c96110Evan Cheng const TargetRegisterClass* rc, 15594cce6b4c7882ef0cc993d931b90bf33985c96110Evan Cheng std::vector<LiveInterval*> &NewLIs) { 1560419852ca8a01aecde4c0e20af6b7bd6450e70f87Evan Cheng for (MachineRegisterInfo::reg_iterator ri = mri_->reg_begin(li.reg), 1561419852ca8a01aecde4c0e20af6b7bd6450e70f87Evan Cheng re = mri_->reg_end(); ri != re; ) { 15624cce6b4c7882ef0cc993d931b90bf33985c96110Evan Cheng MachineOperand &O = ri.getOperand(); 1563419852ca8a01aecde4c0e20af6b7bd6450e70f87Evan Cheng MachineInstr *MI = &*ri; 1564419852ca8a01aecde4c0e20af6b7bd6450e70f87Evan Cheng ++ri; 15654cce6b4c7882ef0cc993d931b90bf33985c96110Evan Cheng if (O.isDef()) { 15664cce6b4c7882ef0cc993d931b90bf33985c96110Evan Cheng assert(MI->getOpcode() == TargetInstrInfo::IMPLICIT_DEF && 15674cce6b4c7882ef0cc993d931b90bf33985c96110Evan Cheng "Register def was not rewritten?"); 15684cce6b4c7882ef0cc993d931b90bf33985c96110Evan Cheng RemoveMachineInstrFromMaps(MI); 15694cce6b4c7882ef0cc993d931b90bf33985c96110Evan Cheng vrm.RemoveMachineInstrFromMaps(MI); 15704cce6b4c7882ef0cc993d931b90bf33985c96110Evan Cheng MI->eraseFromParent(); 15714cce6b4c7882ef0cc993d931b90bf33985c96110Evan Cheng } else { 15724cce6b4c7882ef0cc993d931b90bf33985c96110Evan Cheng // This must be an use of an implicit_def so it's not part of the live 15734cce6b4c7882ef0cc993d931b90bf33985c96110Evan Cheng // interval. Create a new empty live interval for it. 15744cce6b4c7882ef0cc993d931b90bf33985c96110Evan Cheng // FIXME: Can we simply erase some of the instructions? e.g. Stores? 15754cce6b4c7882ef0cc993d931b90bf33985c96110Evan Cheng unsigned NewVReg = mri_->createVirtualRegister(rc); 15764cce6b4c7882ef0cc993d931b90bf33985c96110Evan Cheng vrm.grow(); 15774cce6b4c7882ef0cc993d931b90bf33985c96110Evan Cheng vrm.setIsImplicitlyDefined(NewVReg); 15784cce6b4c7882ef0cc993d931b90bf33985c96110Evan Cheng NewLIs.push_back(&getOrCreateInterval(NewVReg)); 15794cce6b4c7882ef0cc993d931b90bf33985c96110Evan Cheng for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) { 15804cce6b4c7882ef0cc993d931b90bf33985c96110Evan Cheng MachineOperand &MO = MI->getOperand(i); 15814cce6b4c7882ef0cc993d931b90bf33985c96110Evan Cheng if (MO.isReg() && MO.getReg() == li.reg) 15824cce6b4c7882ef0cc993d931b90bf33985c96110Evan Cheng MO.setReg(NewVReg); 15834cce6b4c7882ef0cc993d931b90bf33985c96110Evan Cheng } 15844cce6b4c7882ef0cc993d931b90bf33985c96110Evan Cheng } 1585419852ca8a01aecde4c0e20af6b7bd6450e70f87Evan Cheng } 1586419852ca8a01aecde4c0e20af6b7bd6450e70f87Evan Cheng} 1587419852ca8a01aecde4c0e20af6b7bd6450e70f87Evan Cheng 158881a038218171860ee4c382849c647d3dc841fe8bEvan Cheng 1589f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Chengstd::vector<LiveInterval*> LiveIntervals:: 159081a038218171860ee4c382849c647d3dc841fe8bEvan ChengaddIntervalsForSpills(const LiveInterval &li, 15919c3c2213647e3f1b71722d61875ebac01b65cb91Evan Cheng const MachineLoopInfo *loopInfo, VirtRegMap &vrm, 15929c3c2213647e3f1b71722d61875ebac01b65cb91Evan Cheng float &SSWeight) { 1593f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng assert(li.weight != HUGE_VALF && 1594f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng "attempt to spill already spilled interval!"); 1595f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng 1596f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng DOUT << "\t\t\t\tadding intervals for spills for interval: "; 15976f0d024a534af18d9e60b3ea757376cd8a3a980eDan Gohman li.print(DOUT, tri_); 1598f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng DOUT << '\n'; 1599f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng 16009c3c2213647e3f1b71722d61875ebac01b65cb91Evan Cheng // Spill slot weight. 16019c3c2213647e3f1b71722d61875ebac01b65cb91Evan Cheng SSWeight = 0.0f; 16029c3c2213647e3f1b71722d61875ebac01b65cb91Evan Cheng 160381a038218171860ee4c382849c647d3dc841fe8bEvan Cheng // Each bit specify whether it a spill is required in the MBB. 160481a038218171860ee4c382849c647d3dc841fe8bEvan Cheng BitVector SpillMBBs(mf_->getNumBlockIDs()); 16051953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng std::map<unsigned, std::vector<SRInfo> > SpillIdxes; 16060cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng BitVector RestoreMBBs(mf_->getNumBlockIDs()); 16071953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng std::map<unsigned, std::vector<SRInfo> > RestoreIdxes; 16081953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng std::map<unsigned,unsigned> MBBVRegsMap; 1609f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng std::vector<LiveInterval*> NewLIs; 1610d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng const TargetRegisterClass* rc = mri_->getRegClass(li.reg); 1611f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng 1612f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng unsigned NumValNums = li.getNumValNums(); 1613f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng SmallVector<MachineInstr*, 4> ReMatDefs; 1614f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng ReMatDefs.resize(NumValNums, NULL); 1615f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng SmallVector<MachineInstr*, 4> ReMatOrigDefs; 1616f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng ReMatOrigDefs.resize(NumValNums, NULL); 1617f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng SmallVector<int, 4> ReMatIds; 1618f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng ReMatIds.resize(NumValNums, VirtRegMap::MAX_STACK_SLOT); 1619f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng BitVector ReMatDelete(NumValNums); 1620f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng unsigned Slot = VirtRegMap::MAX_STACK_SLOT; 1621f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng 162281a038218171860ee4c382849c647d3dc841fe8bEvan Cheng // Spilling a split live interval. It cannot be split any further. Also, 162381a038218171860ee4c382849c647d3dc841fe8bEvan Cheng // it's also guaranteed to be a single val# / range interval. 162481a038218171860ee4c382849c647d3dc841fe8bEvan Cheng if (vrm.getPreSplitReg(li.reg)) { 162581a038218171860ee4c382849c647d3dc841fe8bEvan Cheng vrm.setIsSplitFromReg(li.reg, 0); 1626d120ffd26f2715c600b028d4eac9a3c41a9f4653Evan Cheng // Unset the split kill marker on the last use. 1627d120ffd26f2715c600b028d4eac9a3c41a9f4653Evan Cheng unsigned KillIdx = vrm.getKillPoint(li.reg); 1628d120ffd26f2715c600b028d4eac9a3c41a9f4653Evan Cheng if (KillIdx) { 1629d120ffd26f2715c600b028d4eac9a3c41a9f4653Evan Cheng MachineInstr *KillMI = getInstructionFromIndex(KillIdx); 1630d120ffd26f2715c600b028d4eac9a3c41a9f4653Evan Cheng assert(KillMI && "Last use disappeared?"); 1631d120ffd26f2715c600b028d4eac9a3c41a9f4653Evan Cheng int KillOp = KillMI->findRegisterUseOperandIdx(li.reg, true); 1632d120ffd26f2715c600b028d4eac9a3c41a9f4653Evan Cheng assert(KillOp != -1 && "Last use disappeared?"); 1633f73823000e2d5d6e1cf65bdf5a107297e18d35fbChris Lattner KillMI->getOperand(KillOp).setIsKill(false); 1634d120ffd26f2715c600b028d4eac9a3c41a9f4653Evan Cheng } 1635adf85906906ebf85c57c333e8209f37ef11a6c99Evan Cheng vrm.removeKillPoint(li.reg); 163681a038218171860ee4c382849c647d3dc841fe8bEvan Cheng bool DefIsReMat = vrm.isReMaterialized(li.reg); 163781a038218171860ee4c382849c647d3dc841fe8bEvan Cheng Slot = vrm.getStackSlot(li.reg); 163881a038218171860ee4c382849c647d3dc841fe8bEvan Cheng assert(Slot != VirtRegMap::MAX_STACK_SLOT); 163981a038218171860ee4c382849c647d3dc841fe8bEvan Cheng MachineInstr *ReMatDefMI = DefIsReMat ? 164081a038218171860ee4c382849c647d3dc841fe8bEvan Cheng vrm.getReMaterializedMI(li.reg) : NULL; 164181a038218171860ee4c382849c647d3dc841fe8bEvan Cheng int LdSlot = 0; 164281a038218171860ee4c382849c647d3dc841fe8bEvan Cheng bool isLoadSS = DefIsReMat && tii_->isLoadFromStackSlot(ReMatDefMI, LdSlot); 164381a038218171860ee4c382849c647d3dc841fe8bEvan Cheng bool isLoad = isLoadSS || 1644749c6f6b5ed301c84aac562e414486549d7b98ebChris Lattner (DefIsReMat && (ReMatDefMI->getDesc().isSimpleLoad())); 164581a038218171860ee4c382849c647d3dc841fe8bEvan Cheng bool IsFirstRange = true; 164681a038218171860ee4c382849c647d3dc841fe8bEvan Cheng for (LiveInterval::Ranges::const_iterator 164781a038218171860ee4c382849c647d3dc841fe8bEvan Cheng I = li.ranges.begin(), E = li.ranges.end(); I != E; ++I) { 164881a038218171860ee4c382849c647d3dc841fe8bEvan Cheng // If this is a split live interval with multiple ranges, it means there 164981a038218171860ee4c382849c647d3dc841fe8bEvan Cheng // are two-address instructions that re-defined the value. Only the 165081a038218171860ee4c382849c647d3dc841fe8bEvan Cheng // first def can be rematerialized! 165181a038218171860ee4c382849c647d3dc841fe8bEvan Cheng if (IsFirstRange) { 1652cb3c330d39442130d0587208d673ce9c33c7008fEvan Cheng // Note ReMatOrigDefMI has already been deleted. 165381a038218171860ee4c382849c647d3dc841fe8bEvan Cheng rewriteInstructionsForSpills(li, false, I, NULL, ReMatDefMI, 165481a038218171860ee4c382849c647d3dc841fe8bEvan Cheng Slot, LdSlot, isLoad, isLoadSS, DefIsReMat, 1655d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng false, vrm, rc, ReMatIds, loopInfo, 16560cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng SpillMBBs, SpillIdxes, RestoreMBBs, RestoreIdxes, 16579c3c2213647e3f1b71722d61875ebac01b65cb91Evan Cheng MBBVRegsMap, NewLIs, SSWeight); 165881a038218171860ee4c382849c647d3dc841fe8bEvan Cheng } else { 165981a038218171860ee4c382849c647d3dc841fe8bEvan Cheng rewriteInstructionsForSpills(li, false, I, NULL, 0, 166081a038218171860ee4c382849c647d3dc841fe8bEvan Cheng Slot, 0, false, false, false, 1661d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng false, vrm, rc, ReMatIds, loopInfo, 16620cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng SpillMBBs, SpillIdxes, RestoreMBBs, RestoreIdxes, 16639c3c2213647e3f1b71722d61875ebac01b65cb91Evan Cheng MBBVRegsMap, NewLIs, SSWeight); 166481a038218171860ee4c382849c647d3dc841fe8bEvan Cheng } 166581a038218171860ee4c382849c647d3dc841fe8bEvan Cheng IsFirstRange = false; 166681a038218171860ee4c382849c647d3dc841fe8bEvan Cheng } 1667419852ca8a01aecde4c0e20af6b7bd6450e70f87Evan Cheng 16689c3c2213647e3f1b71722d61875ebac01b65cb91Evan Cheng SSWeight = 0.0f; // Already accounted for when split. 16694cce6b4c7882ef0cc993d931b90bf33985c96110Evan Cheng handleSpilledImpDefs(li, vrm, rc, NewLIs); 167081a038218171860ee4c382849c647d3dc841fe8bEvan Cheng return NewLIs; 167181a038218171860ee4c382849c647d3dc841fe8bEvan Cheng } 167281a038218171860ee4c382849c647d3dc841fe8bEvan Cheng 167381a038218171860ee4c382849c647d3dc841fe8bEvan Cheng bool TrySplit = SplitAtBB && !intervalIsInOneMBB(li); 16740cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng if (SplitLimit != -1 && (int)numSplits >= SplitLimit) 16750cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng TrySplit = false; 16760cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng if (TrySplit) 16770cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng ++numSplits; 1678f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng bool NeedStackSlot = false; 1679f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng for (LiveInterval::const_vni_iterator i = li.vni_begin(), e = li.vni_end(); 1680f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng i != e; ++i) { 1681f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng const VNInfo *VNI = *i; 1682f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng unsigned VN = VNI->id; 1683f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng unsigned DefIdx = VNI->def; 1684f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng if (DefIdx == ~1U) 1685f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng continue; // Dead val#. 1686f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng // Is the def for the val# rematerializable? 168781a038218171860ee4c382849c647d3dc841fe8bEvan Cheng MachineInstr *ReMatDefMI = (DefIdx == ~0u) 168881a038218171860ee4c382849c647d3dc841fe8bEvan Cheng ? 0 : getInstructionFromIndex(DefIdx); 16895ef3a04b542c4e585276768fa9ca2af698ef5c87Evan Cheng bool dummy; 16905ef3a04b542c4e585276768fa9ca2af698ef5c87Evan Cheng if (ReMatDefMI && isReMaterializable(li, VNI, ReMatDefMI, dummy)) { 1691f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng // Remember how to remat the def of this val#. 169281a038218171860ee4c382849c647d3dc841fe8bEvan Cheng ReMatOrigDefs[VN] = ReMatDefMI; 16932c3f7ae3843bdc9dcfe85393e178211976c1f9bdDan Gohman // Original def may be modified so we have to make a copy here. 16941ed9922794cda9dbe295e74674b909287e544632Evan Cheng MachineInstr *Clone = mf_->CloneMachineInstr(ReMatDefMI); 16951ed9922794cda9dbe295e74674b909287e544632Evan Cheng ClonedMIs.push_back(Clone); 16961ed9922794cda9dbe295e74674b909287e544632Evan Cheng ReMatDefs[VN] = Clone; 1697f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng 1698f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng bool CanDelete = true; 1699c3fc7d9ec9b495c8a88cd854247105c296d3aabdEvan Cheng if (VNI->hasPHIKill) { 1700c3fc7d9ec9b495c8a88cd854247105c296d3aabdEvan Cheng // A kill is a phi node, not all of its uses can be rematerialized. 1701f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng // It must not be deleted. 1702c3fc7d9ec9b495c8a88cd854247105c296d3aabdEvan Cheng CanDelete = false; 1703c3fc7d9ec9b495c8a88cd854247105c296d3aabdEvan Cheng // Need a stack slot if there is any live range where uses cannot be 1704c3fc7d9ec9b495c8a88cd854247105c296d3aabdEvan Cheng // rematerialized. 1705c3fc7d9ec9b495c8a88cd854247105c296d3aabdEvan Cheng NeedStackSlot = true; 1706f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng } 1707f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng if (CanDelete) 1708f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng ReMatDelete.set(VN); 1709f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng } else { 1710f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng // Need a stack slot if there is any live range where uses cannot be 1711f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng // rematerialized. 1712f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng NeedStackSlot = true; 1713f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng } 1714f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng } 1715f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng 1716f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng // One stack slot per live interval. 171781a038218171860ee4c382849c647d3dc841fe8bEvan Cheng if (NeedStackSlot && vrm.getPreSplitReg(li.reg) == 0) 1718f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng Slot = vrm.assignVirt2StackSlot(li.reg); 1719f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng 1720f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng // Create new intervals and rewrite defs and uses. 1721f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng for (LiveInterval::Ranges::const_iterator 1722f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng I = li.ranges.begin(), E = li.ranges.end(); I != E; ++I) { 172381a038218171860ee4c382849c647d3dc841fe8bEvan Cheng MachineInstr *ReMatDefMI = ReMatDefs[I->valno->id]; 172481a038218171860ee4c382849c647d3dc841fe8bEvan Cheng MachineInstr *ReMatOrigDefMI = ReMatOrigDefs[I->valno->id]; 172581a038218171860ee4c382849c647d3dc841fe8bEvan Cheng bool DefIsReMat = ReMatDefMI != NULL; 1726f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng bool CanDelete = ReMatDelete[I->valno->id]; 1727f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng int LdSlot = 0; 172881a038218171860ee4c382849c647d3dc841fe8bEvan Cheng bool isLoadSS = DefIsReMat && tii_->isLoadFromStackSlot(ReMatDefMI, LdSlot); 1729f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng bool isLoad = isLoadSS || 1730749c6f6b5ed301c84aac562e414486549d7b98ebChris Lattner (DefIsReMat && ReMatDefMI->getDesc().isSimpleLoad()); 173181a038218171860ee4c382849c647d3dc841fe8bEvan Cheng rewriteInstructionsForSpills(li, TrySplit, I, ReMatOrigDefMI, ReMatDefMI, 17320cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng Slot, LdSlot, isLoad, isLoadSS, DefIsReMat, 1733d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng CanDelete, vrm, rc, ReMatIds, loopInfo, 17340cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng SpillMBBs, SpillIdxes, RestoreMBBs, RestoreIdxes, 17359c3c2213647e3f1b71722d61875ebac01b65cb91Evan Cheng MBBVRegsMap, NewLIs, SSWeight); 1736f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng } 1737f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng 17380cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng // Insert spills / restores if we are splitting. 1739419852ca8a01aecde4c0e20af6b7bd6450e70f87Evan Cheng if (!TrySplit) { 17404cce6b4c7882ef0cc993d931b90bf33985c96110Evan Cheng handleSpilledImpDefs(li, vrm, rc, NewLIs); 17411953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng return NewLIs; 1742419852ca8a01aecde4c0e20af6b7bd6450e70f87Evan Cheng } 17431953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng 1744b50bb8cf197709b3f49044740044c06d8f314564Evan Cheng SmallPtrSet<LiveInterval*, 4> AddedKill; 1745aee4af68ae2016afc5b4ec0c430e539c5810a766Evan Cheng SmallVector<unsigned, 2> Ops; 17461953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng if (NeedStackSlot) { 17471953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng int Id = SpillMBBs.find_first(); 17481953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng while (Id != -1) { 17499c3c2213647e3f1b71722d61875ebac01b65cb91Evan Cheng MachineBasicBlock *MBB = mf_->getBlockNumbered(Id); 17509c3c2213647e3f1b71722d61875ebac01b65cb91Evan Cheng unsigned loopDepth = loopInfo->getLoopDepth(MBB); 17511953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng std::vector<SRInfo> &spills = SpillIdxes[Id]; 17521953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng for (unsigned i = 0, e = spills.size(); i != e; ++i) { 17531953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng int index = spills[i].index; 17541953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng unsigned VReg = spills[i].vreg; 1755597d10d84fb6b34f7776121404d5ed802b21b2b6Evan Cheng LiveInterval &nI = getOrCreateInterval(VReg); 17560cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng bool isReMat = vrm.isReMaterialized(VReg); 17570cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng MachineInstr *MI = getInstructionFromIndex(index); 1758aee4af68ae2016afc5b4ec0c430e539c5810a766Evan Cheng bool CanFold = false; 1759aee4af68ae2016afc5b4ec0c430e539c5810a766Evan Cheng bool FoundUse = false; 1760aee4af68ae2016afc5b4ec0c430e539c5810a766Evan Cheng Ops.clear(); 1761cddbb83ea82e98658d9f530c50a7b9d23249afc2Evan Cheng if (spills[i].canFold) { 1762aee4af68ae2016afc5b4ec0c430e539c5810a766Evan Cheng CanFold = true; 17630cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng for (unsigned j = 0, ee = MI->getNumOperands(); j != ee; ++j) { 17640cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng MachineOperand &MO = MI->getOperand(j); 17650cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng if (!MO.isRegister() || MO.getReg() != VReg) 17660cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng continue; 1767aee4af68ae2016afc5b4ec0c430e539c5810a766Evan Cheng 1768aee4af68ae2016afc5b4ec0c430e539c5810a766Evan Cheng Ops.push_back(j); 1769aee4af68ae2016afc5b4ec0c430e539c5810a766Evan Cheng if (MO.isDef()) 1770cddbb83ea82e98658d9f530c50a7b9d23249afc2Evan Cheng continue; 1771aee4af68ae2016afc5b4ec0c430e539c5810a766Evan Cheng if (isReMat || 1772aee4af68ae2016afc5b4ec0c430e539c5810a766Evan Cheng (!FoundUse && !alsoFoldARestore(Id, index, VReg, 1773aee4af68ae2016afc5b4ec0c430e539c5810a766Evan Cheng RestoreMBBs, RestoreIdxes))) { 1774aee4af68ae2016afc5b4ec0c430e539c5810a766Evan Cheng // MI has two-address uses of the same register. If the use 1775aee4af68ae2016afc5b4ec0c430e539c5810a766Evan Cheng // isn't the first and only use in the BB, then we can't fold 1776aee4af68ae2016afc5b4ec0c430e539c5810a766Evan Cheng // it. FIXME: Move this to rewriteInstructionsForSpills. 1777aee4af68ae2016afc5b4ec0c430e539c5810a766Evan Cheng CanFold = false; 1778cddbb83ea82e98658d9f530c50a7b9d23249afc2Evan Cheng break; 1779cddbb83ea82e98658d9f530c50a7b9d23249afc2Evan Cheng } 1780aee4af68ae2016afc5b4ec0c430e539c5810a766Evan Cheng FoundUse = true; 17810cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng } 17820cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng } 17830cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng // Fold the store into the def if possible. 1784cddbb83ea82e98658d9f530c50a7b9d23249afc2Evan Cheng bool Folded = false; 1785aee4af68ae2016afc5b4ec0c430e539c5810a766Evan Cheng if (CanFold && !Ops.empty()) { 1786aee4af68ae2016afc5b4ec0c430e539c5810a766Evan Cheng if (tryFoldMemoryOperand(MI, vrm, NULL, index, Ops, true, Slot,VReg)){ 1787cddbb83ea82e98658d9f530c50a7b9d23249afc2Evan Cheng Folded = true; 1788f38d14f03e495ea98ae16bda6febbde276513294Evan Cheng if (FoundUse > 0) { 1789aee4af68ae2016afc5b4ec0c430e539c5810a766Evan Cheng // Also folded uses, do not issue a load. 1790aee4af68ae2016afc5b4ec0c430e539c5810a766Evan Cheng eraseRestoreInfo(Id, index, VReg, RestoreMBBs, RestoreIdxes); 1791f38d14f03e495ea98ae16bda6febbde276513294Evan Cheng nI.removeRange(getLoadIndex(index), getUseIndex(index)+1); 1792f38d14f03e495ea98ae16bda6febbde276513294Evan Cheng } 1793597d10d84fb6b34f7776121404d5ed802b21b2b6Evan Cheng nI.removeRange(getDefIndex(index), getStoreIndex(index)); 1794cddbb83ea82e98658d9f530c50a7b9d23249afc2Evan Cheng } 17950cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng } 17960cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng 17977e073baedb8232b9519dbe15ea141ff98ccfe6aeEvan Cheng // Otherwise tell the spiller to issue a spill. 1798b50bb8cf197709b3f49044740044c06d8f314564Evan Cheng if (!Folded) { 1799b50bb8cf197709b3f49044740044c06d8f314564Evan Cheng LiveRange *LR = &nI.ranges[nI.ranges.size()-1]; 1800b50bb8cf197709b3f49044740044c06d8f314564Evan Cheng bool isKill = LR->end == getStoreIndex(index); 1801b0a6f62c9b2e75fc509d84310a9795ffacbc6796Evan Cheng if (!MI->registerDefIsDead(nI.reg)) 1802b0a6f62c9b2e75fc509d84310a9795ffacbc6796Evan Cheng // No need to spill a dead def. 1803b0a6f62c9b2e75fc509d84310a9795ffacbc6796Evan Cheng vrm.addSpillPoint(VReg, isKill, MI); 1804b50bb8cf197709b3f49044740044c06d8f314564Evan Cheng if (isKill) 1805b50bb8cf197709b3f49044740044c06d8f314564Evan Cheng AddedKill.insert(&nI); 1806b50bb8cf197709b3f49044740044c06d8f314564Evan Cheng } 18079c3c2213647e3f1b71722d61875ebac01b65cb91Evan Cheng 18089c3c2213647e3f1b71722d61875ebac01b65cb91Evan Cheng // Update spill slot weight. 18099c3c2213647e3f1b71722d61875ebac01b65cb91Evan Cheng if (!isReMat) 1810c3417609ae6e744a29be6962d4fb7811c0102d17Evan Cheng SSWeight += getSpillWeight(true, false, loopDepth); 18110cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng } 18121953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng Id = SpillMBBs.find_next(Id); 18130cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng } 18141953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng } 18150cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng 18161953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng int Id = RestoreMBBs.find_first(); 18171953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng while (Id != -1) { 18189c3c2213647e3f1b71722d61875ebac01b65cb91Evan Cheng MachineBasicBlock *MBB = mf_->getBlockNumbered(Id); 18199c3c2213647e3f1b71722d61875ebac01b65cb91Evan Cheng unsigned loopDepth = loopInfo->getLoopDepth(MBB); 18209c3c2213647e3f1b71722d61875ebac01b65cb91Evan Cheng 18211953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng std::vector<SRInfo> &restores = RestoreIdxes[Id]; 18221953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng for (unsigned i = 0, e = restores.size(); i != e; ++i) { 18231953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng int index = restores[i].index; 18241953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng if (index == -1) 18251953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng continue; 18261953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng unsigned VReg = restores[i].vreg; 1827597d10d84fb6b34f7776121404d5ed802b21b2b6Evan Cheng LiveInterval &nI = getOrCreateInterval(VReg); 18289c3c2213647e3f1b71722d61875ebac01b65cb91Evan Cheng bool isReMat = vrm.isReMaterialized(VReg); 182981a038218171860ee4c382849c647d3dc841fe8bEvan Cheng MachineInstr *MI = getInstructionFromIndex(index); 1830aee4af68ae2016afc5b4ec0c430e539c5810a766Evan Cheng bool CanFold = false; 1831aee4af68ae2016afc5b4ec0c430e539c5810a766Evan Cheng Ops.clear(); 1832cddbb83ea82e98658d9f530c50a7b9d23249afc2Evan Cheng if (restores[i].canFold) { 1833aee4af68ae2016afc5b4ec0c430e539c5810a766Evan Cheng CanFold = true; 183481a038218171860ee4c382849c647d3dc841fe8bEvan Cheng for (unsigned j = 0, ee = MI->getNumOperands(); j != ee; ++j) { 183581a038218171860ee4c382849c647d3dc841fe8bEvan Cheng MachineOperand &MO = MI->getOperand(j); 183681a038218171860ee4c382849c647d3dc841fe8bEvan Cheng if (!MO.isRegister() || MO.getReg() != VReg) 183781a038218171860ee4c382849c647d3dc841fe8bEvan Cheng continue; 1838aee4af68ae2016afc5b4ec0c430e539c5810a766Evan Cheng 18390cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng if (MO.isDef()) { 1840aee4af68ae2016afc5b4ec0c430e539c5810a766Evan Cheng // If this restore were to be folded, it would have been folded 1841aee4af68ae2016afc5b4ec0c430e539c5810a766Evan Cheng // already. 1842aee4af68ae2016afc5b4ec0c430e539c5810a766Evan Cheng CanFold = false; 184381a038218171860ee4c382849c647d3dc841fe8bEvan Cheng break; 184481a038218171860ee4c382849c647d3dc841fe8bEvan Cheng } 1845aee4af68ae2016afc5b4ec0c430e539c5810a766Evan Cheng Ops.push_back(j); 184681a038218171860ee4c382849c647d3dc841fe8bEvan Cheng } 184781a038218171860ee4c382849c647d3dc841fe8bEvan Cheng } 18480cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng 18490cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng // Fold the load into the use if possible. 1850cddbb83ea82e98658d9f530c50a7b9d23249afc2Evan Cheng bool Folded = false; 1851aee4af68ae2016afc5b4ec0c430e539c5810a766Evan Cheng if (CanFold && !Ops.empty()) { 18529c3c2213647e3f1b71722d61875ebac01b65cb91Evan Cheng if (!isReMat) 1853aee4af68ae2016afc5b4ec0c430e539c5810a766Evan Cheng Folded = tryFoldMemoryOperand(MI, vrm, NULL,index,Ops,true,Slot,VReg); 1854aee4af68ae2016afc5b4ec0c430e539c5810a766Evan Cheng else { 18550cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng MachineInstr *ReMatDefMI = vrm.getReMaterializedMI(VReg); 18560cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng int LdSlot = 0; 18570cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng bool isLoadSS = tii_->isLoadFromStackSlot(ReMatDefMI, LdSlot); 18580cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng // If the rematerializable def is a load, also try to fold it. 1859749c6f6b5ed301c84aac562e414486549d7b98ebChris Lattner if (isLoadSS || ReMatDefMI->getDesc().isSimpleLoad()) 1860aee4af68ae2016afc5b4ec0c430e539c5810a766Evan Cheng Folded = tryFoldMemoryOperand(MI, vrm, ReMatDefMI, index, 1861aee4af68ae2016afc5b4ec0c430e539c5810a766Evan Cheng Ops, isLoadSS, LdSlot, VReg); 1862d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng unsigned ImpUse = getReMatImplicitUse(li, ReMatDefMI); 1863d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng if (ImpUse) { 1864d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng // Re-matting an instruction with virtual register use. Add the 1865d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng // register as an implicit use on the use MI and update the register 186624d2f8a212f08bf21360122cc00acf2657af91f9Evan Cheng // interval's spill weight to HUGE_VALF to prevent it from being 186724d2f8a212f08bf21360122cc00acf2657af91f9Evan Cheng // spilled. 1868d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng LiveInterval &ImpLi = getInterval(ImpUse); 186924d2f8a212f08bf21360122cc00acf2657af91f9Evan Cheng ImpLi.weight = HUGE_VALF; 1870d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng MI->addOperand(MachineOperand::CreateReg(ImpUse, false, true)); 1871d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng } 1872aee4af68ae2016afc5b4ec0c430e539c5810a766Evan Cheng } 18730cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng } 18740cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng // If folding is not possible / failed, then tell the spiller to issue a 18750cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng // load / rematerialization for us. 1876597d10d84fb6b34f7776121404d5ed802b21b2b6Evan Cheng if (Folded) 1877597d10d84fb6b34f7776121404d5ed802b21b2b6Evan Cheng nI.removeRange(getLoadIndex(index), getUseIndex(index)+1); 1878b50bb8cf197709b3f49044740044c06d8f314564Evan Cheng else 18790cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng vrm.addRestorePoint(VReg, MI); 18809c3c2213647e3f1b71722d61875ebac01b65cb91Evan Cheng 18819c3c2213647e3f1b71722d61875ebac01b65cb91Evan Cheng // Update spill slot weight. 18829c3c2213647e3f1b71722d61875ebac01b65cb91Evan Cheng if (!isReMat) 1883c3417609ae6e744a29be6962d4fb7811c0102d17Evan Cheng SSWeight += getSpillWeight(false, true, loopDepth); 188481a038218171860ee4c382849c647d3dc841fe8bEvan Cheng } 18851953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng Id = RestoreMBBs.find_next(Id); 188681a038218171860ee4c382849c647d3dc841fe8bEvan Cheng } 188781a038218171860ee4c382849c647d3dc841fe8bEvan Cheng 1888b50bb8cf197709b3f49044740044c06d8f314564Evan Cheng // Finalize intervals: add kills, finalize spill weights, and filter out 1889b50bb8cf197709b3f49044740044c06d8f314564Evan Cheng // dead intervals. 1890597d10d84fb6b34f7776121404d5ed802b21b2b6Evan Cheng std::vector<LiveInterval*> RetNewLIs; 1891597d10d84fb6b34f7776121404d5ed802b21b2b6Evan Cheng for (unsigned i = 0, e = NewLIs.size(); i != e; ++i) { 1892597d10d84fb6b34f7776121404d5ed802b21b2b6Evan Cheng LiveInterval *LI = NewLIs[i]; 1893597d10d84fb6b34f7776121404d5ed802b21b2b6Evan Cheng if (!LI->empty()) { 1894496bac5b084474ac33109bad24c1ef94c843e16fOwen Anderson LI->weight /= InstrSlots::NUM * getApproximateInstructionCount(*LI); 1895b50bb8cf197709b3f49044740044c06d8f314564Evan Cheng if (!AddedKill.count(LI)) { 1896b50bb8cf197709b3f49044740044c06d8f314564Evan Cheng LiveRange *LR = &LI->ranges[LI->ranges.size()-1]; 1897d120ffd26f2715c600b028d4eac9a3c41a9f4653Evan Cheng unsigned LastUseIdx = getBaseIndex(LR->end); 1898d120ffd26f2715c600b028d4eac9a3c41a9f4653Evan Cheng MachineInstr *LastUse = getInstructionFromIndex(LastUseIdx); 18996130f66eaae89f8878590796977678afa8448926Evan Cheng int UseIdx = LastUse->findRegisterUseOperandIdx(LI->reg, false); 1900b50bb8cf197709b3f49044740044c06d8f314564Evan Cheng assert(UseIdx != -1); 1901d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng if (LastUse->getOperand(UseIdx).isImplicit() || 1902d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng LastUse->getDesc().getOperandConstraint(UseIdx,TOI::TIED_TO) == -1){ 1903b50bb8cf197709b3f49044740044c06d8f314564Evan Cheng LastUse->getOperand(UseIdx).setIsKill(); 1904d120ffd26f2715c600b028d4eac9a3c41a9f4653Evan Cheng vrm.addKillPoint(LI->reg, LastUseIdx); 1905adf85906906ebf85c57c333e8209f37ef11a6c99Evan Cheng } 1906b50bb8cf197709b3f49044740044c06d8f314564Evan Cheng } 1907597d10d84fb6b34f7776121404d5ed802b21b2b6Evan Cheng RetNewLIs.push_back(LI); 1908597d10d84fb6b34f7776121404d5ed802b21b2b6Evan Cheng } 1909597d10d84fb6b34f7776121404d5ed802b21b2b6Evan Cheng } 191081a038218171860ee4c382849c647d3dc841fe8bEvan Cheng 19114cce6b4c7882ef0cc993d931b90bf33985c96110Evan Cheng handleSpilledImpDefs(li, vrm, rc, RetNewLIs); 1912597d10d84fb6b34f7776121404d5ed802b21b2b6Evan Cheng return RetNewLIs; 1913f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng} 1914676dd7c80b6f91178452535ac45ca58feb23cc42Evan Cheng 1915676dd7c80b6f91178452535ac45ca58feb23cc42Evan Cheng/// hasAllocatableSuperReg - Return true if the specified physical register has 1916676dd7c80b6f91178452535ac45ca58feb23cc42Evan Cheng/// any super register that's allocatable. 1917676dd7c80b6f91178452535ac45ca58feb23cc42Evan Chengbool LiveIntervals::hasAllocatableSuperReg(unsigned Reg) const { 1918676dd7c80b6f91178452535ac45ca58feb23cc42Evan Cheng for (const unsigned* AS = tri_->getSuperRegisters(Reg); *AS; ++AS) 1919676dd7c80b6f91178452535ac45ca58feb23cc42Evan Cheng if (allocatableRegs_[*AS] && hasInterval(*AS)) 1920676dd7c80b6f91178452535ac45ca58feb23cc42Evan Cheng return true; 1921676dd7c80b6f91178452535ac45ca58feb23cc42Evan Cheng return false; 1922676dd7c80b6f91178452535ac45ca58feb23cc42Evan Cheng} 1923676dd7c80b6f91178452535ac45ca58feb23cc42Evan Cheng 1924676dd7c80b6f91178452535ac45ca58feb23cc42Evan Cheng/// getRepresentativeReg - Find the largest super register of the specified 1925676dd7c80b6f91178452535ac45ca58feb23cc42Evan Cheng/// physical register. 1926676dd7c80b6f91178452535ac45ca58feb23cc42Evan Chengunsigned LiveIntervals::getRepresentativeReg(unsigned Reg) const { 1927676dd7c80b6f91178452535ac45ca58feb23cc42Evan Cheng // Find the largest super-register that is allocatable. 1928676dd7c80b6f91178452535ac45ca58feb23cc42Evan Cheng unsigned BestReg = Reg; 1929676dd7c80b6f91178452535ac45ca58feb23cc42Evan Cheng for (const unsigned* AS = tri_->getSuperRegisters(Reg); *AS; ++AS) { 1930676dd7c80b6f91178452535ac45ca58feb23cc42Evan Cheng unsigned SuperReg = *AS; 1931676dd7c80b6f91178452535ac45ca58feb23cc42Evan Cheng if (!hasAllocatableSuperReg(SuperReg) && hasInterval(SuperReg)) { 1932676dd7c80b6f91178452535ac45ca58feb23cc42Evan Cheng BestReg = SuperReg; 1933676dd7c80b6f91178452535ac45ca58feb23cc42Evan Cheng break; 1934676dd7c80b6f91178452535ac45ca58feb23cc42Evan Cheng } 1935676dd7c80b6f91178452535ac45ca58feb23cc42Evan Cheng } 1936676dd7c80b6f91178452535ac45ca58feb23cc42Evan Cheng return BestReg; 1937676dd7c80b6f91178452535ac45ca58feb23cc42Evan Cheng} 1938676dd7c80b6f91178452535ac45ca58feb23cc42Evan Cheng 1939676dd7c80b6f91178452535ac45ca58feb23cc42Evan Cheng/// getNumConflictsWithPhysReg - Return the number of uses and defs of the 1940676dd7c80b6f91178452535ac45ca58feb23cc42Evan Cheng/// specified interval that conflicts with the specified physical register. 1941676dd7c80b6f91178452535ac45ca58feb23cc42Evan Chengunsigned LiveIntervals::getNumConflictsWithPhysReg(const LiveInterval &li, 1942676dd7c80b6f91178452535ac45ca58feb23cc42Evan Cheng unsigned PhysReg) const { 1943676dd7c80b6f91178452535ac45ca58feb23cc42Evan Cheng unsigned NumConflicts = 0; 1944676dd7c80b6f91178452535ac45ca58feb23cc42Evan Cheng const LiveInterval &pli = getInterval(getRepresentativeReg(PhysReg)); 1945676dd7c80b6f91178452535ac45ca58feb23cc42Evan Cheng for (MachineRegisterInfo::reg_iterator I = mri_->reg_begin(li.reg), 1946676dd7c80b6f91178452535ac45ca58feb23cc42Evan Cheng E = mri_->reg_end(); I != E; ++I) { 1947676dd7c80b6f91178452535ac45ca58feb23cc42Evan Cheng MachineOperand &O = I.getOperand(); 1948676dd7c80b6f91178452535ac45ca58feb23cc42Evan Cheng MachineInstr *MI = O.getParent(); 1949676dd7c80b6f91178452535ac45ca58feb23cc42Evan Cheng unsigned Index = getInstructionIndex(MI); 1950676dd7c80b6f91178452535ac45ca58feb23cc42Evan Cheng if (pli.liveAt(Index)) 1951676dd7c80b6f91178452535ac45ca58feb23cc42Evan Cheng ++NumConflicts; 1952676dd7c80b6f91178452535ac45ca58feb23cc42Evan Cheng } 1953676dd7c80b6f91178452535ac45ca58feb23cc42Evan Cheng return NumConflicts; 1954676dd7c80b6f91178452535ac45ca58feb23cc42Evan Cheng} 1955676dd7c80b6f91178452535ac45ca58feb23cc42Evan Cheng 1956676dd7c80b6f91178452535ac45ca58feb23cc42Evan Cheng/// spillPhysRegAroundRegDefsUses - Spill the specified physical register 1957676dd7c80b6f91178452535ac45ca58feb23cc42Evan Cheng/// around all defs and uses of the specified interval. 1958676dd7c80b6f91178452535ac45ca58feb23cc42Evan Chengvoid LiveIntervals::spillPhysRegAroundRegDefsUses(const LiveInterval &li, 1959676dd7c80b6f91178452535ac45ca58feb23cc42Evan Cheng unsigned PhysReg, VirtRegMap &vrm) { 1960676dd7c80b6f91178452535ac45ca58feb23cc42Evan Cheng unsigned SpillReg = getRepresentativeReg(PhysReg); 1961676dd7c80b6f91178452535ac45ca58feb23cc42Evan Cheng 1962676dd7c80b6f91178452535ac45ca58feb23cc42Evan Cheng for (const unsigned *AS = tri_->getAliasSet(PhysReg); *AS; ++AS) 1963676dd7c80b6f91178452535ac45ca58feb23cc42Evan Cheng // If there are registers which alias PhysReg, but which are not a 1964676dd7c80b6f91178452535ac45ca58feb23cc42Evan Cheng // sub-register of the chosen representative super register. Assert 1965676dd7c80b6f91178452535ac45ca58feb23cc42Evan Cheng // since we can't handle it yet. 1966676dd7c80b6f91178452535ac45ca58feb23cc42Evan Cheng assert(*AS == SpillReg || !allocatableRegs_[*AS] || 1967676dd7c80b6f91178452535ac45ca58feb23cc42Evan Cheng tri_->isSuperRegister(*AS, SpillReg)); 1968676dd7c80b6f91178452535ac45ca58feb23cc42Evan Cheng 1969676dd7c80b6f91178452535ac45ca58feb23cc42Evan Cheng LiveInterval &pli = getInterval(SpillReg); 1970676dd7c80b6f91178452535ac45ca58feb23cc42Evan Cheng SmallPtrSet<MachineInstr*, 8> SeenMIs; 1971676dd7c80b6f91178452535ac45ca58feb23cc42Evan Cheng for (MachineRegisterInfo::reg_iterator I = mri_->reg_begin(li.reg), 1972676dd7c80b6f91178452535ac45ca58feb23cc42Evan Cheng E = mri_->reg_end(); I != E; ++I) { 1973676dd7c80b6f91178452535ac45ca58feb23cc42Evan Cheng MachineOperand &O = I.getOperand(); 1974676dd7c80b6f91178452535ac45ca58feb23cc42Evan Cheng MachineInstr *MI = O.getParent(); 1975676dd7c80b6f91178452535ac45ca58feb23cc42Evan Cheng if (SeenMIs.count(MI)) 1976676dd7c80b6f91178452535ac45ca58feb23cc42Evan Cheng continue; 1977676dd7c80b6f91178452535ac45ca58feb23cc42Evan Cheng SeenMIs.insert(MI); 1978676dd7c80b6f91178452535ac45ca58feb23cc42Evan Cheng unsigned Index = getInstructionIndex(MI); 1979676dd7c80b6f91178452535ac45ca58feb23cc42Evan Cheng if (pli.liveAt(Index)) { 1980676dd7c80b6f91178452535ac45ca58feb23cc42Evan Cheng vrm.addEmergencySpill(SpillReg, MI); 1981676dd7c80b6f91178452535ac45ca58feb23cc42Evan Cheng pli.removeRange(getLoadIndex(Index), getStoreIndex(Index)+1); 1982676dd7c80b6f91178452535ac45ca58feb23cc42Evan Cheng for (const unsigned* AS = tri_->getSubRegisters(SpillReg); *AS; ++AS) { 1983676dd7c80b6f91178452535ac45ca58feb23cc42Evan Cheng if (!hasInterval(*AS)) 1984676dd7c80b6f91178452535ac45ca58feb23cc42Evan Cheng continue; 1985676dd7c80b6f91178452535ac45ca58feb23cc42Evan Cheng LiveInterval &spli = getInterval(*AS); 1986676dd7c80b6f91178452535ac45ca58feb23cc42Evan Cheng if (spli.liveAt(Index)) 1987676dd7c80b6f91178452535ac45ca58feb23cc42Evan Cheng spli.removeRange(getLoadIndex(Index), getStoreIndex(Index)+1); 1988676dd7c80b6f91178452535ac45ca58feb23cc42Evan Cheng } 1989676dd7c80b6f91178452535ac45ca58feb23cc42Evan Cheng } 1990676dd7c80b6f91178452535ac45ca58feb23cc42Evan Cheng } 1991676dd7c80b6f91178452535ac45ca58feb23cc42Evan Cheng} 1992c4dc132c8a787fc41b6a162121251234aa618965Owen Anderson 1993c4dc132c8a787fc41b6a162121251234aa618965Owen AndersonLiveRange LiveIntervals::addLiveRangeToEndOfBlock(unsigned reg, 1994c4dc132c8a787fc41b6a162121251234aa618965Owen Anderson MachineInstr* startInst) { 1995c4dc132c8a787fc41b6a162121251234aa618965Owen Anderson LiveInterval& Interval = getOrCreateInterval(reg); 1996c4dc132c8a787fc41b6a162121251234aa618965Owen Anderson VNInfo* VN = Interval.getNextValue( 1997c4dc132c8a787fc41b6a162121251234aa618965Owen Anderson getInstructionIndex(startInst) + InstrSlots::DEF, 1998c4dc132c8a787fc41b6a162121251234aa618965Owen Anderson startInst, getVNInfoAllocator()); 1999c4dc132c8a787fc41b6a162121251234aa618965Owen Anderson VN->hasPHIKill = true; 2000c4dc132c8a787fc41b6a162121251234aa618965Owen Anderson VN->kills.push_back(getMBBEndIdx(startInst->getParent())); 2001c4dc132c8a787fc41b6a162121251234aa618965Owen Anderson LiveRange LR(getInstructionIndex(startInst) + InstrSlots::DEF, 2002c4dc132c8a787fc41b6a162121251234aa618965Owen Anderson getMBBEndIdx(startInst->getParent()) + 1, VN); 2003c4dc132c8a787fc41b6a162121251234aa618965Owen Anderson Interval.addRange(LR); 2004c4dc132c8a787fc41b6a162121251234aa618965Owen Anderson 2005c4dc132c8a787fc41b6a162121251234aa618965Owen Anderson return LR; 2006c4dc132c8a787fc41b6a162121251234aa618965Owen Anderson} 2007