LiveIntervalAnalysis.cpp revision d6664311acbd05a8a710ccea8f9f5fdbfa35f834
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); 67aa111080dfb161054255c9c367779f1ea2581849Owen Anderson AU.addPreservedID(PHIEliminationID); 68aa111080dfb161054255c9c367779f1ea2581849Owen Anderson AU.addRequiredID(PHIEliminationID); 691a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos AU.addRequiredID(TwoAddressInstructionPassID); 701a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos MachineFunctionPass::getAnalysisUsage(AU); 71ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos} 72ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos 73f7da2c7b0c6293c268881628fc351bed7763f1f4Chris Lattnervoid LiveIntervals::releaseMemory() { 7403857b29d8271a23943254579e6cf7b7df4b1bd3Owen Anderson // Free the live intervals themselves. 7520e2839cb975a2d4ee931e1ea4c4660a36ef0177Owen Anderson for (DenseMap<unsigned, LiveInterval*>::iterator I = r2iMap_.begin(), 7603857b29d8271a23943254579e6cf7b7df4b1bd3Owen Anderson E = r2iMap_.end(); I != E; ++I) 7703857b29d8271a23943254579e6cf7b7df4b1bd3Owen Anderson delete I->second; 7803857b29d8271a23943254579e6cf7b7df4b1bd3Owen Anderson 793f32d65912b4da23793dab618d981be2ce11c331Evan Cheng MBB2IdxMap.clear(); 804ca980e7f9ce7b78955307c2d07001a24d3b6befEvan Cheng Idx2MBBMap.clear(); 811a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos mi2iMap_.clear(); 821a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos i2miMap_.clear(); 831a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos r2iMap_.clear(); 84dd199d29b781bc713462f1255b63d3f153bfd9e9Evan Cheng // Release VNInfo memroy regions after all VNInfo objects are dtor'd. 85dd199d29b781bc713462f1255b63d3f153bfd9e9Evan Cheng VNInfoAllocator.Reset(); 861ed9922794cda9dbe295e74674b909287e544632Evan Cheng while (!ClonedMIs.empty()) { 871ed9922794cda9dbe295e74674b909287e544632Evan Cheng MachineInstr *MI = ClonedMIs.back(); 881ed9922794cda9dbe295e74674b909287e544632Evan Cheng ClonedMIs.pop_back(); 891ed9922794cda9dbe295e74674b909287e544632Evan Cheng mf_->DeleteMachineInstr(MI); 901ed9922794cda9dbe295e74674b909287e544632Evan Cheng } 91993141402f57b4d4cbb7f8a3113f19c61688f9b7Evan Cheng} 92993141402f57b4d4cbb7f8a3113f19c61688f9b7Evan Cheng 9380b3ce65e294a28b88c882d44a5e749a2924c9e3Owen Andersonvoid LiveIntervals::computeNumbering() { 9480b3ce65e294a28b88c882d44a5e749a2924c9e3Owen Anderson Index2MiMap OldI2MI = i2miMap_; 957fbad27cfb7298c707e50af10609d463900d7211Owen Anderson std::vector<IdxMBBPair> OldI2MBB = Idx2MBBMap; 9680b3ce65e294a28b88c882d44a5e749a2924c9e3Owen Anderson 9780b3ce65e294a28b88c882d44a5e749a2924c9e3Owen Anderson Idx2MBBMap.clear(); 9880b3ce65e294a28b88c882d44a5e749a2924c9e3Owen Anderson MBB2IdxMap.clear(); 9980b3ce65e294a28b88c882d44a5e749a2924c9e3Owen Anderson mi2iMap_.clear(); 10080b3ce65e294a28b88c882d44a5e749a2924c9e3Owen Anderson i2miMap_.clear(); 10180b3ce65e294a28b88c882d44a5e749a2924c9e3Owen Anderson 102a1566f2e12ce87a5bca30bc0189a0cdbb40136a4Owen Anderson FunctionSize = 0; 103a1566f2e12ce87a5bca30bc0189a0cdbb40136a4Owen Anderson 104428b92eb83b457b71d29d1d4b7900d36a0ce9a53Chris Lattner // Number MachineInstrs and MachineBasicBlocks. 105428b92eb83b457b71d29d1d4b7900d36a0ce9a53Chris Lattner // Initialize MBB indexes to a sentinal. 106549f27d3070195d6647b796841a5291b4549e8e0Evan Cheng MBB2IdxMap.resize(mf_->getNumBlockIDs(), std::make_pair(~0U,~0U)); 107428b92eb83b457b71d29d1d4b7900d36a0ce9a53Chris Lattner 108428b92eb83b457b71d29d1d4b7900d36a0ce9a53Chris Lattner unsigned MIIndex = 0; 109428b92eb83b457b71d29d1d4b7900d36a0ce9a53Chris Lattner for (MachineFunction::iterator MBB = mf_->begin(), E = mf_->end(); 110428b92eb83b457b71d29d1d4b7900d36a0ce9a53Chris Lattner MBB != E; ++MBB) { 111549f27d3070195d6647b796841a5291b4549e8e0Evan Cheng unsigned StartIdx = MIIndex; 1120c9f92e1ff64ee56724eae444a0442b02f83d0a8Evan Cheng 1137fbad27cfb7298c707e50af10609d463900d7211Owen Anderson // Insert an empty slot at the beginning of each block. 1147fbad27cfb7298c707e50af10609d463900d7211Owen Anderson MIIndex += InstrSlots::NUM; 1157fbad27cfb7298c707e50af10609d463900d7211Owen Anderson i2miMap_.push_back(0); 1167fbad27cfb7298c707e50af10609d463900d7211Owen Anderson 117428b92eb83b457b71d29d1d4b7900d36a0ce9a53Chris Lattner for (MachineBasicBlock::iterator I = MBB->begin(), E = MBB->end(); 118428b92eb83b457b71d29d1d4b7900d36a0ce9a53Chris Lattner I != E; ++I) { 119428b92eb83b457b71d29d1d4b7900d36a0ce9a53Chris Lattner bool inserted = mi2iMap_.insert(std::make_pair(I, MIIndex)).second; 1201a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos assert(inserted && "multiple MachineInstr -> index mappings"); 121428b92eb83b457b71d29d1d4b7900d36a0ce9a53Chris Lattner i2miMap_.push_back(I); 122428b92eb83b457b71d29d1d4b7900d36a0ce9a53Chris Lattner MIIndex += InstrSlots::NUM; 123a1566f2e12ce87a5bca30bc0189a0cdbb40136a4Owen Anderson FunctionSize++; 1247fbad27cfb7298c707e50af10609d463900d7211Owen Anderson 1257fbad27cfb7298c707e50af10609d463900d7211Owen Anderson // Insert an empty slot after every instruction. 1261fbb4545d41e65191ae66a7302276fa5424518c5Owen Anderson MIIndex += InstrSlots::NUM; 1271fbb4545d41e65191ae66a7302276fa5424518c5Owen Anderson i2miMap_.push_back(0); 128355780128986e375c7ac2a75025ac129bb8280bfOwen Anderson } 1297fbad27cfb7298c707e50af10609d463900d7211Owen Anderson 1301fbb4545d41e65191ae66a7302276fa5424518c5Owen Anderson // Set the MBB2IdxMap entry for this MBB. 1311fbb4545d41e65191ae66a7302276fa5424518c5Owen Anderson MBB2IdxMap[MBB->getNumber()] = std::make_pair(StartIdx, MIIndex - 1); 1321fbb4545d41e65191ae66a7302276fa5424518c5Owen Anderson Idx2MBBMap.push_back(std::make_pair(StartIdx, MBB)); 133428b92eb83b457b71d29d1d4b7900d36a0ce9a53Chris Lattner } 1344ca980e7f9ce7b78955307c2d07001a24d3b6befEvan Cheng std::sort(Idx2MBBMap.begin(), Idx2MBBMap.end(), Idx2MBBCompare()); 13580b3ce65e294a28b88c882d44a5e749a2924c9e3Owen Anderson 13680b3ce65e294a28b88c882d44a5e749a2924c9e3Owen Anderson if (!OldI2MI.empty()) 137788d04152a132121dfc04e63382c1e87e7b9607fOwen Anderson for (iterator OI = begin(), OE = end(); OI != OE; ++OI) { 13803857b29d8271a23943254579e6cf7b7df4b1bd3Owen Anderson for (LiveInterval::iterator LI = OI->second->begin(), 13903857b29d8271a23943254579e6cf7b7df4b1bd3Owen Anderson LE = OI->second->end(); LI != LE; ++LI) { 1407eec0c243320fb2629554681547d7384ea9d0c53Owen Anderson 1417eec0c243320fb2629554681547d7384ea9d0c53Owen Anderson // Remap the start index of the live range to the corresponding new 1427eec0c243320fb2629554681547d7384ea9d0c53Owen Anderson // number, or our best guess at what it _should_ correspond to if the 1437eec0c243320fb2629554681547d7384ea9d0c53Owen Anderson // original instruction has been erased. This is either the following 1447eec0c243320fb2629554681547d7384ea9d0c53Owen Anderson // instruction or its predecessor. 1457fbad27cfb7298c707e50af10609d463900d7211Owen Anderson unsigned index = LI->start / InstrSlots::NUM; 1464b5b209679f866d3ac6372f963aa7e9906f9a08bOwen Anderson unsigned offset = LI->start % InstrSlots::NUM; 1470a7615af25542d5e7d824b520f94094cdc8a2179Owen Anderson if (offset == InstrSlots::LOAD) { 1487fbad27cfb7298c707e50af10609d463900d7211Owen Anderson std::vector<IdxMBBPair>::const_iterator I = 149d7dcbecdbcf5d7a1efc5ed65ddcc26bb8c20c1e6Owen Anderson std::lower_bound(OldI2MBB.begin(), OldI2MBB.end(), LI->start); 1507fbad27cfb7298c707e50af10609d463900d7211Owen Anderson // Take the pair containing the index 1517fbad27cfb7298c707e50af10609d463900d7211Owen Anderson std::vector<IdxMBBPair>::const_iterator J = 152a0c032f9b2eeae3a436850eaca54de4c6a5f23b6Owen Anderson (I == OldI2MBB.end() && OldI2MBB.size()>0) ? (I-1): I; 1537eec0c243320fb2629554681547d7384ea9d0c53Owen Anderson 1547fbad27cfb7298c707e50af10609d463900d7211Owen Anderson LI->start = getMBBStartIdx(J->second); 1557fbad27cfb7298c707e50af10609d463900d7211Owen Anderson } else { 1567fbad27cfb7298c707e50af10609d463900d7211Owen Anderson LI->start = mi2iMap_[OldI2MI[index]] + offset; 1577eec0c243320fb2629554681547d7384ea9d0c53Owen Anderson } 1584b5b209679f866d3ac6372f963aa7e9906f9a08bOwen Anderson 1597eec0c243320fb2629554681547d7384ea9d0c53Owen Anderson // Remap the ending index in the same way that we remapped the start, 1607eec0c243320fb2629554681547d7384ea9d0c53Owen Anderson // except for the final step where we always map to the immediately 1617eec0c243320fb2629554681547d7384ea9d0c53Owen Anderson // following instruction. 162d7dcbecdbcf5d7a1efc5ed65ddcc26bb8c20c1e6Owen Anderson index = (LI->end - 1) / InstrSlots::NUM; 1637fbad27cfb7298c707e50af10609d463900d7211Owen Anderson offset = LI->end % InstrSlots::NUM; 1649382b9310f008a3347e565d76aadda6a97351de9Owen Anderson if (offset == InstrSlots::LOAD) { 1659382b9310f008a3347e565d76aadda6a97351de9Owen Anderson // VReg dies at end of block. 1667fbad27cfb7298c707e50af10609d463900d7211Owen Anderson std::vector<IdxMBBPair>::const_iterator I = 167d7dcbecdbcf5d7a1efc5ed65ddcc26bb8c20c1e6Owen Anderson std::lower_bound(OldI2MBB.begin(), OldI2MBB.end(), LI->end); 1689382b9310f008a3347e565d76aadda6a97351de9Owen Anderson --I; 1697fbad27cfb7298c707e50af10609d463900d7211Owen Anderson 1709382b9310f008a3347e565d76aadda6a97351de9Owen Anderson LI->end = getMBBEndIdx(I->second) + 1; 1714b5b209679f866d3ac6372f963aa7e9906f9a08bOwen Anderson } else { 172d7dcbecdbcf5d7a1efc5ed65ddcc26bb8c20c1e6Owen Anderson unsigned idx = index; 1738d0cc0af5a4b4c08eb74b6e36761651b63816d06Owen Anderson while (index < OldI2MI.size() && !OldI2MI[index]) ++index; 1748d0cc0af5a4b4c08eb74b6e36761651b63816d06Owen Anderson 1758d0cc0af5a4b4c08eb74b6e36761651b63816d06Owen Anderson if (index != OldI2MI.size()) 1768d0cc0af5a4b4c08eb74b6e36761651b63816d06Owen Anderson LI->end = mi2iMap_[OldI2MI[index]] + (idx == index ? offset : 0); 1778d0cc0af5a4b4c08eb74b6e36761651b63816d06Owen Anderson else 1788d0cc0af5a4b4c08eb74b6e36761651b63816d06Owen Anderson LI->end = InstrSlots::NUM * i2miMap_.size(); 1794b5b209679f866d3ac6372f963aa7e9906f9a08bOwen Anderson } 180788d04152a132121dfc04e63382c1e87e7b9607fOwen Anderson } 181788d04152a132121dfc04e63382c1e87e7b9607fOwen Anderson 18203857b29d8271a23943254579e6cf7b7df4b1bd3Owen Anderson for (LiveInterval::vni_iterator VNI = OI->second->vni_begin(), 18303857b29d8271a23943254579e6cf7b7df4b1bd3Owen Anderson VNE = OI->second->vni_end(); VNI != VNE; ++VNI) { 184788d04152a132121dfc04e63382c1e87e7b9607fOwen Anderson VNInfo* vni = *VNI; 185745825f431920662e97bdab5c1bcfac62e48c52fOwen Anderson 1867eec0c243320fb2629554681547d7384ea9d0c53Owen Anderson // Remap the VNInfo def index, which works the same as the 187788d04152a132121dfc04e63382c1e87e7b9607fOwen Anderson // start indices above. VN's with special sentinel defs 188788d04152a132121dfc04e63382c1e87e7b9607fOwen Anderson // don't need to be remapped. 189912923925f790427a77781b8a0469fa832c7740dOwen Anderson if (vni->def != ~0U && vni->def != ~1U) { 190788d04152a132121dfc04e63382c1e87e7b9607fOwen Anderson unsigned index = vni->def / InstrSlots::NUM; 191788d04152a132121dfc04e63382c1e87e7b9607fOwen Anderson unsigned offset = vni->def % InstrSlots::NUM; 192912923925f790427a77781b8a0469fa832c7740dOwen Anderson if (offset == InstrSlots::LOAD) { 193912923925f790427a77781b8a0469fa832c7740dOwen Anderson std::vector<IdxMBBPair>::const_iterator I = 1940a7615af25542d5e7d824b520f94094cdc8a2179Owen Anderson std::lower_bound(OldI2MBB.begin(), OldI2MBB.end(), vni->def); 195912923925f790427a77781b8a0469fa832c7740dOwen Anderson // Take the pair containing the index 196912923925f790427a77781b8a0469fa832c7740dOwen Anderson std::vector<IdxMBBPair>::const_iterator J = 197a0c032f9b2eeae3a436850eaca54de4c6a5f23b6Owen Anderson (I == OldI2MBB.end() && OldI2MBB.size()>0) ? (I-1): I; 1987eec0c243320fb2629554681547d7384ea9d0c53Owen Anderson 199912923925f790427a77781b8a0469fa832c7740dOwen Anderson vni->def = getMBBStartIdx(J->second); 200912923925f790427a77781b8a0469fa832c7740dOwen Anderson } else { 201912923925f790427a77781b8a0469fa832c7740dOwen Anderson vni->def = mi2iMap_[OldI2MI[index]] + offset; 202912923925f790427a77781b8a0469fa832c7740dOwen Anderson } 2037eec0c243320fb2629554681547d7384ea9d0c53Owen Anderson } 204745825f431920662e97bdab5c1bcfac62e48c52fOwen Anderson 2057eec0c243320fb2629554681547d7384ea9d0c53Owen Anderson // Remap the VNInfo kill indices, which works the same as 2067eec0c243320fb2629554681547d7384ea9d0c53Owen Anderson // the end indices above. 2074b5b209679f866d3ac6372f963aa7e9906f9a08bOwen Anderson for (size_t i = 0; i < vni->kills.size(); ++i) { 2089382b9310f008a3347e565d76aadda6a97351de9Owen Anderson // PHI kills don't need to be remapped. 2099382b9310f008a3347e565d76aadda6a97351de9Owen Anderson if (!vni->kills[i]) continue; 2109382b9310f008a3347e565d76aadda6a97351de9Owen Anderson 211788d04152a132121dfc04e63382c1e87e7b9607fOwen Anderson unsigned index = (vni->kills[i]-1) / InstrSlots::NUM; 212788d04152a132121dfc04e63382c1e87e7b9607fOwen Anderson unsigned offset = vni->kills[i] % InstrSlots::NUM; 213788d04152a132121dfc04e63382c1e87e7b9607fOwen Anderson if (offset == InstrSlots::STORE) { 2147fbad27cfb7298c707e50af10609d463900d7211Owen Anderson std::vector<IdxMBBPair>::const_iterator I = 215d7dcbecdbcf5d7a1efc5ed65ddcc26bb8c20c1e6Owen Anderson std::lower_bound(OldI2MBB.begin(), OldI2MBB.end(), vni->kills[i]); 2169382b9310f008a3347e565d76aadda6a97351de9Owen Anderson --I; 2177fbad27cfb7298c707e50af10609d463900d7211Owen Anderson 218788d04152a132121dfc04e63382c1e87e7b9607fOwen Anderson vni->kills[i] = getMBBEndIdx(I->second); 2197fbad27cfb7298c707e50af10609d463900d7211Owen Anderson } else { 220d7dcbecdbcf5d7a1efc5ed65ddcc26bb8c20c1e6Owen Anderson unsigned idx = index; 2218d0cc0af5a4b4c08eb74b6e36761651b63816d06Owen Anderson while (index < OldI2MI.size() && !OldI2MI[index]) ++index; 2228d0cc0af5a4b4c08eb74b6e36761651b63816d06Owen Anderson 2238d0cc0af5a4b4c08eb74b6e36761651b63816d06Owen Anderson if (index != OldI2MI.size()) 2248d0cc0af5a4b4c08eb74b6e36761651b63816d06Owen Anderson vni->kills[i] = mi2iMap_[OldI2MI[index]] + 2258d0cc0af5a4b4c08eb74b6e36761651b63816d06Owen Anderson (idx == index ? offset : 0); 2268d0cc0af5a4b4c08eb74b6e36761651b63816d06Owen Anderson else 2278d0cc0af5a4b4c08eb74b6e36761651b63816d06Owen Anderson vni->kills[i] = InstrSlots::NUM * i2miMap_.size(); 2287eec0c243320fb2629554681547d7384ea9d0c53Owen Anderson } 2294b5b209679f866d3ac6372f963aa7e9906f9a08bOwen Anderson } 23080b3ce65e294a28b88c882d44a5e749a2924c9e3Owen Anderson } 231788d04152a132121dfc04e63382c1e87e7b9607fOwen Anderson } 23280b3ce65e294a28b88c882d44a5e749a2924c9e3Owen Anderson} 23380b3ce65e294a28b88c882d44a5e749a2924c9e3Owen Anderson 23480b3ce65e294a28b88c882d44a5e749a2924c9e3Owen Anderson/// runOnMachineFunction - Register allocate the whole function 23580b3ce65e294a28b88c882d44a5e749a2924c9e3Owen Anderson/// 23680b3ce65e294a28b88c882d44a5e749a2924c9e3Owen Andersonbool LiveIntervals::runOnMachineFunction(MachineFunction &fn) { 23780b3ce65e294a28b88c882d44a5e749a2924c9e3Owen Anderson mf_ = &fn; 23880b3ce65e294a28b88c882d44a5e749a2924c9e3Owen Anderson mri_ = &mf_->getRegInfo(); 23980b3ce65e294a28b88c882d44a5e749a2924c9e3Owen Anderson tm_ = &fn.getTarget(); 24080b3ce65e294a28b88c882d44a5e749a2924c9e3Owen Anderson tri_ = tm_->getRegisterInfo(); 24180b3ce65e294a28b88c882d44a5e749a2924c9e3Owen Anderson tii_ = tm_->getInstrInfo(); 2426d69ba8a6901c69d78488cbc41f8dbf080618fdeDan Gohman aa_ = &getAnalysis<AliasAnalysis>(); 24380b3ce65e294a28b88c882d44a5e749a2924c9e3Owen Anderson lv_ = &getAnalysis<LiveVariables>(); 24480b3ce65e294a28b88c882d44a5e749a2924c9e3Owen Anderson allocatableRegs_ = tri_->getAllocatableSet(fn); 245ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos 24680b3ce65e294a28b88c882d44a5e749a2924c9e3Owen Anderson computeNumbering(); 2471a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos computeIntervals(); 248ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos 2491a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos numIntervals += getNumIntervals(); 250843b160a2040b3ec4d3452678450afa11704c473Alkis Evlogimenos 251bdc679d564e67a81792e463f6614b0088f975025Bill Wendling DOUT << "********** INTERVALS **********\n"; 252bdc679d564e67a81792e463f6614b0088f975025Bill Wendling for (iterator I = begin(), E = end(); I != E; ++I) { 25303857b29d8271a23943254579e6cf7b7df4b1bd3Owen Anderson I->second->print(DOUT, tri_); 254bdc679d564e67a81792e463f6614b0088f975025Bill Wendling DOUT << "\n"; 255bdc679d564e67a81792e463f6614b0088f975025Bill Wendling } 2567ac2d3146a196fa0120c579ecd2ddd69652ad230Chris Lattner 2571a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos numIntervalsAfter += getNumIntervals(); 25870ca358b7d540b6061236ddf757085042873c12cChris Lattner DEBUG(dump()); 2591a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos return true; 260ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos} 261ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos 26270ca358b7d540b6061236ddf757085042873c12cChris Lattner/// print - Implement the dump method. 263ce9653ce449f1409815547e1bf60abcd1332d2c9Reid Spencervoid LiveIntervals::print(std::ostream &O, const Module* ) const { 26470ca358b7d540b6061236ddf757085042873c12cChris Lattner O << "********** INTERVALS **********\n"; 2658e7a70976deee78a84099b916591d40f7a1cdc34Chris Lattner for (const_iterator I = begin(), E = end(); I != E; ++I) { 26603857b29d8271a23943254579e6cf7b7df4b1bd3Owen Anderson I->second->print(O, tri_); 2673f32d65912b4da23793dab618d981be2ce11c331Evan Cheng O << "\n"; 2688e7a70976deee78a84099b916591d40f7a1cdc34Chris Lattner } 26970ca358b7d540b6061236ddf757085042873c12cChris Lattner 27070ca358b7d540b6061236ddf757085042873c12cChris Lattner O << "********** MACHINEINSTRS **********\n"; 27170ca358b7d540b6061236ddf757085042873c12cChris Lattner for (MachineFunction::iterator mbbi = mf_->begin(), mbbe = mf_->end(); 27270ca358b7d540b6061236ddf757085042873c12cChris Lattner mbbi != mbbe; ++mbbi) { 27370ca358b7d540b6061236ddf757085042873c12cChris Lattner O << ((Value*)mbbi->getBasicBlock())->getName() << ":\n"; 27470ca358b7d540b6061236ddf757085042873c12cChris Lattner for (MachineBasicBlock::iterator mii = mbbi->begin(), 27570ca358b7d540b6061236ddf757085042873c12cChris Lattner mie = mbbi->end(); mii != mie; ++mii) { 276477e4555de341c5de780de3720d6f115ec133c4eChris Lattner O << getInstructionIndex(mii) << '\t' << *mii; 27770ca358b7d540b6061236ddf757085042873c12cChris Lattner } 27870ca358b7d540b6061236ddf757085042873c12cChris Lattner } 27970ca358b7d540b6061236ddf757085042873c12cChris Lattner} 28070ca358b7d540b6061236ddf757085042873c12cChris Lattner 281c92da3882ee4e18153bb36fcdf33af393aba8259Evan Cheng/// conflictsWithPhysRegDef - Returns true if the specified register 282c92da3882ee4e18153bb36fcdf33af393aba8259Evan Cheng/// is defined during the duration of the specified interval. 283c92da3882ee4e18153bb36fcdf33af393aba8259Evan Chengbool LiveIntervals::conflictsWithPhysRegDef(const LiveInterval &li, 284c92da3882ee4e18153bb36fcdf33af393aba8259Evan Cheng VirtRegMap &vrm, unsigned reg) { 285c92da3882ee4e18153bb36fcdf33af393aba8259Evan Cheng for (LiveInterval::Ranges::const_iterator 286c92da3882ee4e18153bb36fcdf33af393aba8259Evan Cheng I = li.ranges.begin(), E = li.ranges.end(); I != E; ++I) { 287c92da3882ee4e18153bb36fcdf33af393aba8259Evan Cheng for (unsigned index = getBaseIndex(I->start), 288c92da3882ee4e18153bb36fcdf33af393aba8259Evan Cheng end = getBaseIndex(I->end-1) + InstrSlots::NUM; index != end; 289c92da3882ee4e18153bb36fcdf33af393aba8259Evan Cheng index += InstrSlots::NUM) { 290c92da3882ee4e18153bb36fcdf33af393aba8259Evan Cheng // skip deleted instructions 291c92da3882ee4e18153bb36fcdf33af393aba8259Evan Cheng while (index != end && !getInstructionFromIndex(index)) 292c92da3882ee4e18153bb36fcdf33af393aba8259Evan Cheng index += InstrSlots::NUM; 293c92da3882ee4e18153bb36fcdf33af393aba8259Evan Cheng if (index == end) break; 294c92da3882ee4e18153bb36fcdf33af393aba8259Evan Cheng 295c92da3882ee4e18153bb36fcdf33af393aba8259Evan Cheng MachineInstr *MI = getInstructionFromIndex(index); 2965d446265c740c17ed12e693423f0363296670d60Evan Cheng unsigned SrcReg, DstReg; 2975d446265c740c17ed12e693423f0363296670d60Evan Cheng if (tii_->isMoveInstr(*MI, SrcReg, DstReg)) 2985d446265c740c17ed12e693423f0363296670d60Evan Cheng if (SrcReg == li.reg || DstReg == li.reg) 2995d446265c740c17ed12e693423f0363296670d60Evan Cheng continue; 300c92da3882ee4e18153bb36fcdf33af393aba8259Evan Cheng for (unsigned i = 0; i != MI->getNumOperands(); ++i) { 301c92da3882ee4e18153bb36fcdf33af393aba8259Evan Cheng MachineOperand& mop = MI->getOperand(i); 3025d446265c740c17ed12e693423f0363296670d60Evan Cheng if (!mop.isRegister()) 303c92da3882ee4e18153bb36fcdf33af393aba8259Evan Cheng continue; 304c92da3882ee4e18153bb36fcdf33af393aba8259Evan Cheng unsigned PhysReg = mop.getReg(); 3055d446265c740c17ed12e693423f0363296670d60Evan Cheng if (PhysReg == 0 || PhysReg == li.reg) 306c92da3882ee4e18153bb36fcdf33af393aba8259Evan Cheng continue; 3076f0d024a534af18d9e60b3ea757376cd8a3a980eDan Gohman if (TargetRegisterInfo::isVirtualRegister(PhysReg)) { 3085d446265c740c17ed12e693423f0363296670d60Evan Cheng if (!vrm.hasPhys(PhysReg)) 3095d446265c740c17ed12e693423f0363296670d60Evan Cheng continue; 310c92da3882ee4e18153bb36fcdf33af393aba8259Evan Cheng PhysReg = vrm.getPhys(PhysReg); 3115d446265c740c17ed12e693423f0363296670d60Evan Cheng } 3126f0d024a534af18d9e60b3ea757376cd8a3a980eDan Gohman if (PhysReg && tri_->regsOverlap(PhysReg, reg)) 313c92da3882ee4e18153bb36fcdf33af393aba8259Evan Cheng return true; 314c92da3882ee4e18153bb36fcdf33af393aba8259Evan Cheng } 315c92da3882ee4e18153bb36fcdf33af393aba8259Evan Cheng } 316c92da3882ee4e18153bb36fcdf33af393aba8259Evan Cheng } 317c92da3882ee4e18153bb36fcdf33af393aba8259Evan Cheng 318c92da3882ee4e18153bb36fcdf33af393aba8259Evan Cheng return false; 319c92da3882ee4e18153bb36fcdf33af393aba8259Evan Cheng} 320c92da3882ee4e18153bb36fcdf33af393aba8259Evan Cheng 321be4f88a8b8bb3311e0dc4cde8533763d7923c3eaChris Lattnervoid LiveIntervals::printRegName(unsigned reg) const { 3226f0d024a534af18d9e60b3ea757376cd8a3a980eDan Gohman if (TargetRegisterInfo::isPhysicalRegister(reg)) 323e6d088acc90e422451e098555d383d4d65b6ce6bBill Wendling cerr << tri_->getName(reg); 3241a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos else 325e81561909d128c6e2d8033cb5465a49b2596b26aBill Wendling cerr << "%reg" << reg; 326ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos} 327ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos 328be4f88a8b8bb3311e0dc4cde8533763d7923c3eaChris Lattnervoid LiveIntervals::handleVirtualRegisterDef(MachineBasicBlock *mbb, 329ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos MachineBasicBlock::iterator mi, 3306b098dee286cc6fe5a5a476464d92dec5602e406Owen Anderson unsigned MIIdx, MachineOperand& MO, 331ef0732d25a9882c947984ae3f2afbef5463ba00fEvan Cheng unsigned MOIdx, 332be4f88a8b8bb3311e0dc4cde8533763d7923c3eaChris Lattner LiveInterval &interval) { 333bdc679d564e67a81792e463f6614b0088f975025Bill Wendling DOUT << "\t\tregister: "; DEBUG(printRegName(interval.reg)); 3341a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos LiveVariables::VarInfo& vi = lv_->getVarInfo(interval.reg); 3351a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos 336419852ca8a01aecde4c0e20af6b7bd6450e70f87Evan Cheng if (mi->getOpcode() == TargetInstrInfo::IMPLICIT_DEF) { 337419852ca8a01aecde4c0e20af6b7bd6450e70f87Evan Cheng DOUT << "is a implicit_def\n"; 338419852ca8a01aecde4c0e20af6b7bd6450e70f87Evan Cheng return; 339419852ca8a01aecde4c0e20af6b7bd6450e70f87Evan Cheng } 340419852ca8a01aecde4c0e20af6b7bd6450e70f87Evan Cheng 341706515727c6d024015fffded2b3109a4f0ac5299Alkis Evlogimenos // Virtual registers may be defined multiple times (due to phi 342706515727c6d024015fffded2b3109a4f0ac5299Alkis Evlogimenos // elimination and 2-addr elimination). Much of what we do only has to be 343706515727c6d024015fffded2b3109a4f0ac5299Alkis Evlogimenos // done once for the vreg. We use an empty interval to detect the first 3441a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // time we see a vreg. 3451a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos if (interval.empty()) { 3461a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // Get the Idx of the defining instructions. 3476b128bdc58a496e9f08e4d09416330320761baffChris Lattner unsigned defIndex = getDefIndex(MIIdx); 3487ecb38be0a533e7b9c7d3b8e9b5c8a6fa5f6b349Evan Cheng VNInfo *ValNo; 349c8d044e4f779fdcfc5e7d592927740fd8f672a70Evan Cheng MachineInstr *CopyMI = NULL; 35091725b75852443923b419fd23215194cfc65dd88Chris Lattner unsigned SrcReg, DstReg; 351c8d044e4f779fdcfc5e7d592927740fd8f672a70Evan Cheng if (mi->getOpcode() == TargetInstrInfo::EXTRACT_SUBREG || 3527e073baedb8232b9519dbe15ea141ff98ccfe6aeEvan Cheng mi->getOpcode() == TargetInstrInfo::INSERT_SUBREG || 353c8d044e4f779fdcfc5e7d592927740fd8f672a70Evan Cheng tii_->isMoveInstr(*mi, SrcReg, DstReg)) 354c8d044e4f779fdcfc5e7d592927740fd8f672a70Evan Cheng CopyMI = mi; 355c8d044e4f779fdcfc5e7d592927740fd8f672a70Evan Cheng ValNo = interval.getNextValue(defIndex, CopyMI, VNInfoAllocator); 3567ecb38be0a533e7b9c7d3b8e9b5c8a6fa5f6b349Evan Cheng 3577ecb38be0a533e7b9c7d3b8e9b5c8a6fa5f6b349Evan Cheng assert(ValNo->id == 0 && "First value in interval is not 0?"); 3581a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos 3591a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // Loop over all of the blocks that the vreg is defined in. There are 3601a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // two cases we have to handle here. The most common case is a vreg 3611a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // whose lifetime is contained within a basic block. In this case there 3621a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // will be a single kill, in MBB, which comes after the definition. 3631a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos if (vi.Kills.size() == 1 && vi.Kills[0]->getParent() == mbb) { 3641a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // FIXME: what about dead vars? 3651a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos unsigned killIdx; 3661a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos if (vi.Kills[0] != mi) 3671a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos killIdx = getUseIndex(getInstructionIndex(vi.Kills[0]))+1; 3681a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos else 3691a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos killIdx = defIndex+1; 3701a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos 3711a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // If the kill happens after the definition, we have an intra-block 3721a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // live range. 3731a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos if (killIdx > defIndex) { 37461de82d8853a02fe39c47302432abb70a586704fEvan Cheng assert(vi.AliveBlocks.none() && 3751a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos "Shouldn't be alive across any blocks!"); 3767ecb38be0a533e7b9c7d3b8e9b5c8a6fa5f6b349Evan Cheng LiveRange LR(defIndex, killIdx, ValNo); 3771a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos interval.addRange(LR); 378bdc679d564e67a81792e463f6614b0088f975025Bill Wendling DOUT << " +" << LR << "\n"; 379f3bb2e65d12857f83b273f4ecab013680310bbbcEvan Cheng interval.addKill(ValNo, killIdx); 3801a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos return; 3811a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos } 3821a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos } 3836097d13b2a624048dbe02e39e2dfb23bfa269b64Chris Lattner 3841a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // The other case we handle is when a virtual register lives to the end 3851a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // of the defining block, potentially live across some blocks, then is 3861a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // live into some number of blocks, but gets killed. Start by adding a 3871a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // range that goes from this definition to the end of the defining block. 3887fbad27cfb7298c707e50af10609d463900d7211Owen Anderson LiveRange NewLR(defIndex, getMBBEndIdx(mbb)+1, ValNo); 389bdc679d564e67a81792e463f6614b0088f975025Bill Wendling DOUT << " +" << NewLR; 3901a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos interval.addRange(NewLR); 3911a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos 3921a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // Iterate over all of the blocks that the variable is completely 3931a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // live in, adding [insrtIndex(begin), instrIndex(end)+4) to the 3941a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // live interval. 3951a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos for (unsigned i = 0, e = vi.AliveBlocks.size(); i != e; ++i) { 3961a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos if (vi.AliveBlocks[i]) { 39731ec841be1f51a60f5b655aa2a008eb68e48c07aOwen Anderson LiveRange LR(getMBBStartIdx(i), 398f26e8557deccd5fb28b56548ca5f7ea25aee31c6Evan Cheng getMBBEndIdx(i)+1, // MBB ends at -1. 39931ec841be1f51a60f5b655aa2a008eb68e48c07aOwen Anderson ValNo); 40031ec841be1f51a60f5b655aa2a008eb68e48c07aOwen Anderson interval.addRange(LR); 40131ec841be1f51a60f5b655aa2a008eb68e48c07aOwen Anderson DOUT << " +" << LR; 4021a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos } 4031a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos } 4041a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos 4051a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // Finally, this virtual register is live from the start of any killing 4061a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // block to the 'use' slot of the killing instruction. 4071a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos for (unsigned i = 0, e = vi.Kills.size(); i != e; ++i) { 4081a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos MachineInstr *Kill = vi.Kills[i]; 4098df786012dc6b875f31ba4152e09c6e0098082eeEvan Cheng unsigned killIdx = getUseIndex(getInstructionIndex(Kill))+1; 410428b92eb83b457b71d29d1d4b7900d36a0ce9a53Chris Lattner LiveRange LR(getMBBStartIdx(Kill->getParent()), 4117ecb38be0a533e7b9c7d3b8e9b5c8a6fa5f6b349Evan Cheng killIdx, ValNo); 4121a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos interval.addRange(LR); 413f3bb2e65d12857f83b273f4ecab013680310bbbcEvan Cheng interval.addKill(ValNo, killIdx); 414bdc679d564e67a81792e463f6614b0088f975025Bill Wendling DOUT << " +" << LR; 4151a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos } 4161a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos 4171a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos } else { 4181a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // If this is the second time we see a virtual register definition, it 4191a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // must be due to phi elimination or two addr elimination. If this is 420bf105c842450d3308d024be203ddd533f37051ecEvan Cheng // the result of two address elimination, then the vreg is one of the 421bf105c842450d3308d024be203ddd533f37051ecEvan Cheng // def-and-use register operand. 422ef0732d25a9882c947984ae3f2afbef5463ba00fEvan Cheng if (mi->isRegReDefinedByTwoAddr(interval.reg, MOIdx)) { 4231a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // If this is a two-address definition, then we have already processed 4241a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // the live range. The only problem is that we didn't realize there 4251a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // are actually two values in the live interval. Because of this we 4261a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // need to take the LiveRegion that defines this register and split it 4271a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // into two values. 428a07cec9e24a286157541d2337cd66b24cd116586Evan Cheng assert(interval.containsOneValue()); 429a07cec9e24a286157541d2337cd66b24cd116586Evan Cheng unsigned DefIndex = getDefIndex(interval.getValNumInfo(0)->def); 4306b128bdc58a496e9f08e4d09416330320761baffChris Lattner unsigned RedefIndex = getDefIndex(MIIdx); 4311a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos 4324f8ff168de12eabdeb4b9437bf9402489ecf85cbEvan Cheng const LiveRange *OldLR = interval.getLiveRangeContaining(RedefIndex-1); 4337ecb38be0a533e7b9c7d3b8e9b5c8a6fa5f6b349Evan Cheng VNInfo *OldValNo = OldLR->valno; 4344f8ff168de12eabdeb4b9437bf9402489ecf85cbEvan Cheng 4351a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // Delete the initial value, which should be short and continuous, 436be4f88a8b8bb3311e0dc4cde8533763d7923c3eaChris Lattner // because the 2-addr copy must be in the same MBB as the redef. 4371a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos interval.removeRange(DefIndex, RedefIndex); 438706515727c6d024015fffded2b3109a4f0ac5299Alkis Evlogimenos 439be4f88a8b8bb3311e0dc4cde8533763d7923c3eaChris Lattner // Two-address vregs should always only be redefined once. This means 440be4f88a8b8bb3311e0dc4cde8533763d7923c3eaChris Lattner // that at this point, there should be exactly one value number in it. 441be4f88a8b8bb3311e0dc4cde8533763d7923c3eaChris Lattner assert(interval.containsOneValue() && "Unexpected 2-addr liveint!"); 442be4f88a8b8bb3311e0dc4cde8533763d7923c3eaChris Lattner 44391725b75852443923b419fd23215194cfc65dd88Chris Lattner // The new value number (#1) is defined by the instruction we claimed 44491725b75852443923b419fd23215194cfc65dd88Chris Lattner // defined value #0. 445c8d044e4f779fdcfc5e7d592927740fd8f672a70Evan Cheng VNInfo *ValNo = interval.getNextValue(OldValNo->def, OldValNo->copy, 446c8d044e4f779fdcfc5e7d592927740fd8f672a70Evan Cheng VNInfoAllocator); 447be4f88a8b8bb3311e0dc4cde8533763d7923c3eaChris Lattner 44891725b75852443923b419fd23215194cfc65dd88Chris Lattner // Value#0 is now defined by the 2-addr instruction. 449c8d044e4f779fdcfc5e7d592927740fd8f672a70Evan Cheng OldValNo->def = RedefIndex; 450c8d044e4f779fdcfc5e7d592927740fd8f672a70Evan Cheng OldValNo->copy = 0; 451be4f88a8b8bb3311e0dc4cde8533763d7923c3eaChris Lattner 452be4f88a8b8bb3311e0dc4cde8533763d7923c3eaChris Lattner // Add the new live interval which replaces the range for the input copy. 453be4f88a8b8bb3311e0dc4cde8533763d7923c3eaChris Lattner LiveRange LR(DefIndex, RedefIndex, ValNo); 454bdc679d564e67a81792e463f6614b0088f975025Bill Wendling DOUT << " replace range with " << LR; 4551a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos interval.addRange(LR); 456f3bb2e65d12857f83b273f4ecab013680310bbbcEvan Cheng interval.addKill(ValNo, RedefIndex); 4571a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos 4581a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // If this redefinition is dead, we need to add a dummy unit live 4591a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // range covering the def slot. 4606b098dee286cc6fe5a5a476464d92dec5602e406Owen Anderson if (MO.isDead()) 4617ecb38be0a533e7b9c7d3b8e9b5c8a6fa5f6b349Evan Cheng interval.addRange(LiveRange(RedefIndex, RedefIndex+1, OldValNo)); 4621a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos 46356fdd7af884a35673fb6dd3e01333960922c3ac2Evan Cheng DOUT << " RESULT: "; 4646f0d024a534af18d9e60b3ea757376cd8a3a980eDan Gohman interval.print(DOUT, tri_); 4651a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos 4661a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos } else { 4671a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // Otherwise, this must be because of phi elimination. If this is the 4681a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // first redefinition of the vreg that we have seen, go back and change 4691a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // the live range in the PHI block to be a different value number. 4701a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos if (interval.containsOneValue()) { 4711a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos assert(vi.Kills.size() == 1 && 4721a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos "PHI elimination vreg should have one kill, the PHI itself!"); 4731a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos 4741a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // Remove the old range that we now know has an incorrect number. 475f3bb2e65d12857f83b273f4ecab013680310bbbcEvan Cheng VNInfo *VNI = interval.getValNumInfo(0); 4761a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos MachineInstr *Killer = vi.Kills[0]; 477428b92eb83b457b71d29d1d4b7900d36a0ce9a53Chris Lattner unsigned Start = getMBBStartIdx(Killer->getParent()); 4781a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos unsigned End = getUseIndex(getInstructionIndex(Killer))+1; 47956fdd7af884a35673fb6dd3e01333960922c3ac2Evan Cheng DOUT << " Removing [" << Start << "," << End << "] from: "; 4806f0d024a534af18d9e60b3ea757376cd8a3a980eDan Gohman interval.print(DOUT, tri_); DOUT << "\n"; 4811a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos interval.removeRange(Start, End); 482c3fc7d9ec9b495c8a88cd854247105c296d3aabdEvan Cheng VNI->hasPHIKill = true; 4836f0d024a534af18d9e60b3ea757376cd8a3a980eDan Gohman DOUT << " RESULT: "; interval.print(DOUT, tri_); 4841a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos 485be4f88a8b8bb3311e0dc4cde8533763d7923c3eaChris Lattner // Replace the interval with one of a NEW value number. Note that this 486be4f88a8b8bb3311e0dc4cde8533763d7923c3eaChris Lattner // value number isn't actually defined by an instruction, weird huh? :) 487f3bb2e65d12857f83b273f4ecab013680310bbbcEvan Cheng LiveRange LR(Start, End, interval.getNextValue(~0, 0, VNInfoAllocator)); 488bdc679d564e67a81792e463f6614b0088f975025Bill Wendling DOUT << " replace range with " << LR; 4891a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos interval.addRange(LR); 490f3bb2e65d12857f83b273f4ecab013680310bbbcEvan Cheng interval.addKill(LR.valno, End); 4916f0d024a534af18d9e60b3ea757376cd8a3a980eDan Gohman DOUT << " RESULT: "; interval.print(DOUT, tri_); 4921a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos } 4931a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos 4941a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // In the case of PHI elimination, each variable definition is only 4951a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // live until the end of the block. We've already taken care of the 4961a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // rest of the live range. 4976b128bdc58a496e9f08e4d09416330320761baffChris Lattner unsigned defIndex = getDefIndex(MIIdx); 49891725b75852443923b419fd23215194cfc65dd88Chris Lattner 4997ecb38be0a533e7b9c7d3b8e9b5c8a6fa5f6b349Evan Cheng VNInfo *ValNo; 500c8d044e4f779fdcfc5e7d592927740fd8f672a70Evan Cheng MachineInstr *CopyMI = NULL; 50191725b75852443923b419fd23215194cfc65dd88Chris Lattner unsigned SrcReg, DstReg; 502c8d044e4f779fdcfc5e7d592927740fd8f672a70Evan Cheng if (mi->getOpcode() == TargetInstrInfo::EXTRACT_SUBREG || 5037e073baedb8232b9519dbe15ea141ff98ccfe6aeEvan Cheng mi->getOpcode() == TargetInstrInfo::INSERT_SUBREG || 504c8d044e4f779fdcfc5e7d592927740fd8f672a70Evan Cheng tii_->isMoveInstr(*mi, SrcReg, DstReg)) 505c8d044e4f779fdcfc5e7d592927740fd8f672a70Evan Cheng CopyMI = mi; 506c8d044e4f779fdcfc5e7d592927740fd8f672a70Evan Cheng ValNo = interval.getNextValue(defIndex, CopyMI, VNInfoAllocator); 50791725b75852443923b419fd23215194cfc65dd88Chris Lattner 5087fbad27cfb7298c707e50af10609d463900d7211Owen Anderson unsigned killIndex = getMBBEndIdx(mbb) + 1; 5097ecb38be0a533e7b9c7d3b8e9b5c8a6fa5f6b349Evan Cheng LiveRange LR(defIndex, killIndex, ValNo); 5101a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos interval.addRange(LR); 511c3fc7d9ec9b495c8a88cd854247105c296d3aabdEvan Cheng interval.addKill(ValNo, killIndex); 512c3fc7d9ec9b495c8a88cd854247105c296d3aabdEvan Cheng ValNo->hasPHIKill = true; 513bdc679d564e67a81792e463f6614b0088f975025Bill Wendling DOUT << " +" << LR; 514dd2cc65f34f9b7bfda1cd0c42becedfc361d46f8Alkis Evlogimenos } 5151a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos } 516ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos 517bdc679d564e67a81792e463f6614b0088f975025Bill Wendling DOUT << '\n'; 518ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos} 519ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos 520f35fef7060c465dd7b578bf6339a18e8a8911888Chris Lattnervoid LiveIntervals::handlePhysicalRegisterDef(MachineBasicBlock *MBB, 521ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos MachineBasicBlock::iterator mi, 5226b128bdc58a496e9f08e4d09416330320761baffChris Lattner unsigned MIIdx, 5236b098dee286cc6fe5a5a476464d92dec5602e406Owen Anderson MachineOperand& MO, 52491725b75852443923b419fd23215194cfc65dd88Chris Lattner LiveInterval &interval, 525c8d044e4f779fdcfc5e7d592927740fd8f672a70Evan Cheng MachineInstr *CopyMI) { 5261a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // A physical register cannot be live across basic block, so its 5271a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // lifetime must end somewhere in its defining basic block. 528bdc679d564e67a81792e463f6614b0088f975025Bill Wendling DOUT << "\t\tregister: "; DEBUG(printRegName(interval.reg)); 5291a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos 5306b128bdc58a496e9f08e4d09416330320761baffChris Lattner unsigned baseIndex = MIIdx; 5311a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos unsigned start = getDefIndex(baseIndex); 5321a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos unsigned end = start; 5331a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos 5341a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // If it is not used after definition, it is considered dead at 5351a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // the instruction defining it. Hence its interval is: 5361a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // [defSlot(def), defSlot(def)+1) 5376b098dee286cc6fe5a5a476464d92dec5602e406Owen Anderson if (MO.isDead()) { 538bdc679d564e67a81792e463f6614b0088f975025Bill Wendling DOUT << " dead"; 539ab4b66d4c279e8cd9e448687020fc838e7881dbcChris Lattner end = getDefIndex(start) + 1; 540ab4b66d4c279e8cd9e448687020fc838e7881dbcChris Lattner goto exit; 5411a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos } 542ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos 5431a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // If it is not dead on definition, it must be killed by a 5441a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // subsequent instruction. Hence its interval is: 5451a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // [defSlot(def), useSlot(kill)+1) 5467fbad27cfb7298c707e50af10609d463900d7211Owen Anderson baseIndex += InstrSlots::NUM; 5475ab6f5fe666d0e3403d9b777324d1a1999118153Chris Lattner while (++mi != MBB->end()) { 5487fbad27cfb7298c707e50af10609d463900d7211Owen Anderson while (baseIndex / InstrSlots::NUM < i2miMap_.size() && 5497fbad27cfb7298c707e50af10609d463900d7211Owen Anderson getInstructionFromIndex(baseIndex) == 0) 5507fbad27cfb7298c707e50af10609d463900d7211Owen Anderson baseIndex += InstrSlots::NUM; 5516130f66eaae89f8878590796977678afa8448926Evan Cheng if (mi->killsRegister(interval.reg, tri_)) { 552bdc679d564e67a81792e463f6614b0088f975025Bill Wendling DOUT << " killed"; 553ab4b66d4c279e8cd9e448687020fc838e7881dbcChris Lattner end = getUseIndex(baseIndex) + 1; 554ab4b66d4c279e8cd9e448687020fc838e7881dbcChris Lattner goto exit; 5556130f66eaae89f8878590796977678afa8448926Evan Cheng } else if (mi->modifiesRegister(interval.reg, tri_)) { 5569a1956ae6ad2d4892afbc9f1b97d645d220b6d4aEvan Cheng // Another instruction redefines the register before it is ever read. 5579a1956ae6ad2d4892afbc9f1b97d645d220b6d4aEvan Cheng // Then the register is essentially dead at the instruction that defines 5589a1956ae6ad2d4892afbc9f1b97d645d220b6d4aEvan Cheng // it. Hence its interval is: 5599a1956ae6ad2d4892afbc9f1b97d645d220b6d4aEvan Cheng // [defSlot(def), defSlot(def)+1) 560bdc679d564e67a81792e463f6614b0088f975025Bill Wendling DOUT << " dead"; 5619a1956ae6ad2d4892afbc9f1b97d645d220b6d4aEvan Cheng end = getDefIndex(start) + 1; 5629a1956ae6ad2d4892afbc9f1b97d645d220b6d4aEvan Cheng goto exit; 563f35fef7060c465dd7b578bf6339a18e8a8911888Chris Lattner } 5647fbad27cfb7298c707e50af10609d463900d7211Owen Anderson 5657fbad27cfb7298c707e50af10609d463900d7211Owen Anderson baseIndex += InstrSlots::NUM; 5661a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos } 5675ab6f5fe666d0e3403d9b777324d1a1999118153Chris Lattner 5685ab6f5fe666d0e3403d9b777324d1a1999118153Chris Lattner // The only case we should have a dead physreg here without a killing or 5695ab6f5fe666d0e3403d9b777324d1a1999118153Chris Lattner // instruction where we know it's dead is if it is live-in to the function 5705ab6f5fe666d0e3403d9b777324d1a1999118153Chris Lattner // and never used. 571c8d044e4f779fdcfc5e7d592927740fd8f672a70Evan Cheng assert(!CopyMI && "physreg was not killed in defining block!"); 5725ab6f5fe666d0e3403d9b777324d1a1999118153Chris Lattner end = getDefIndex(start) + 1; // It's dead. 57302ba13c9897ae2b19f9201e57460d7ee2b753a0bAlkis Evlogimenos 574ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenosexit: 5751a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos assert(start < end && "did not find end of interval?"); 576f768bba43f5c036039851d2fcca8212edca18467Chris Lattner 57724a3cc4c83e5edb25fadf7b8979a26b4451795c6Evan Cheng // Already exists? Extend old live interval. 57824a3cc4c83e5edb25fadf7b8979a26b4451795c6Evan Cheng LiveInterval::iterator OldLR = interval.FindLiveRangeContaining(start); 5797ecb38be0a533e7b9c7d3b8e9b5c8a6fa5f6b349Evan Cheng VNInfo *ValNo = (OldLR != interval.end()) 580c8d044e4f779fdcfc5e7d592927740fd8f672a70Evan Cheng ? OldLR->valno : interval.getNextValue(start, CopyMI, VNInfoAllocator); 5817ecb38be0a533e7b9c7d3b8e9b5c8a6fa5f6b349Evan Cheng LiveRange LR(start, end, ValNo); 5821a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos interval.addRange(LR); 583f3bb2e65d12857f83b273f4ecab013680310bbbcEvan Cheng interval.addKill(LR.valno, end); 584bdc679d564e67a81792e463f6614b0088f975025Bill Wendling DOUT << " +" << LR << '\n'; 585ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos} 586ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos 587f35fef7060c465dd7b578bf6339a18e8a8911888Chris Lattnervoid LiveIntervals::handleRegisterDef(MachineBasicBlock *MBB, 588f35fef7060c465dd7b578bf6339a18e8a8911888Chris Lattner MachineBasicBlock::iterator MI, 5896b128bdc58a496e9f08e4d09416330320761baffChris Lattner unsigned MIIdx, 590ef0732d25a9882c947984ae3f2afbef5463ba00fEvan Cheng MachineOperand& MO, 591ef0732d25a9882c947984ae3f2afbef5463ba00fEvan Cheng unsigned MOIdx) { 5926b098dee286cc6fe5a5a476464d92dec5602e406Owen Anderson if (TargetRegisterInfo::isVirtualRegister(MO.getReg())) 593ef0732d25a9882c947984ae3f2afbef5463ba00fEvan Cheng handleVirtualRegisterDef(MBB, MI, MIIdx, MO, MOIdx, 5946b098dee286cc6fe5a5a476464d92dec5602e406Owen Anderson getOrCreateInterval(MO.getReg())); 5956b098dee286cc6fe5a5a476464d92dec5602e406Owen Anderson else if (allocatableRegs_[MO.getReg()]) { 596c8d044e4f779fdcfc5e7d592927740fd8f672a70Evan Cheng MachineInstr *CopyMI = NULL; 59791725b75852443923b419fd23215194cfc65dd88Chris Lattner unsigned SrcReg, DstReg; 598c8d044e4f779fdcfc5e7d592927740fd8f672a70Evan Cheng if (MI->getOpcode() == TargetInstrInfo::EXTRACT_SUBREG || 5997e073baedb8232b9519dbe15ea141ff98ccfe6aeEvan Cheng MI->getOpcode() == TargetInstrInfo::INSERT_SUBREG || 600c8d044e4f779fdcfc5e7d592927740fd8f672a70Evan Cheng tii_->isMoveInstr(*MI, SrcReg, DstReg)) 601c8d044e4f779fdcfc5e7d592927740fd8f672a70Evan Cheng CopyMI = MI; 6026b098dee286cc6fe5a5a476464d92dec5602e406Owen Anderson handlePhysicalRegisterDef(MBB, MI, MIIdx, MO, 6036b098dee286cc6fe5a5a476464d92dec5602e406Owen Anderson getOrCreateInterval(MO.getReg()), CopyMI); 60424a3cc4c83e5edb25fadf7b8979a26b4451795c6Evan Cheng // Def of a register also defines its sub-registers. 6056b098dee286cc6fe5a5a476464d92dec5602e406Owen Anderson for (const unsigned* AS = tri_->getSubRegisters(MO.getReg()); *AS; ++AS) 6066130f66eaae89f8878590796977678afa8448926Evan Cheng // If MI also modifies the sub-register explicitly, avoid processing it 6076130f66eaae89f8878590796977678afa8448926Evan Cheng // more than once. Do not pass in TRI here so it checks for exact match. 6086130f66eaae89f8878590796977678afa8448926Evan Cheng if (!MI->modifiesRegister(*AS)) 6096b098dee286cc6fe5a5a476464d92dec5602e406Owen Anderson handlePhysicalRegisterDef(MBB, MI, MIIdx, MO, 6106b098dee286cc6fe5a5a476464d92dec5602e406Owen Anderson getOrCreateInterval(*AS), 0); 611f35fef7060c465dd7b578bf6339a18e8a8911888Chris Lattner } 6124d46e1e521c0df1990ea50f8146d22bd77ea71a6Alkis Evlogimenos} 6134d46e1e521c0df1990ea50f8146d22bd77ea71a6Alkis Evlogimenos 614b371f457b0ea4a652a9f526ba4375c80ae542252Evan Chengvoid LiveIntervals::handleLiveInRegister(MachineBasicBlock *MBB, 6159b25b8ca24d6df2e097741dcc15016772ee4eda7Jim Laskey unsigned MIIdx, 61624a3cc4c83e5edb25fadf7b8979a26b4451795c6Evan Cheng LiveInterval &interval, bool isAlias) { 617b371f457b0ea4a652a9f526ba4375c80ae542252Evan Cheng DOUT << "\t\tlivein register: "; DEBUG(printRegName(interval.reg)); 618b371f457b0ea4a652a9f526ba4375c80ae542252Evan Cheng 619b371f457b0ea4a652a9f526ba4375c80ae542252Evan Cheng // Look for kills, if it reaches a def before it's killed, then it shouldn't 620b371f457b0ea4a652a9f526ba4375c80ae542252Evan Cheng // be considered a livein. 621b371f457b0ea4a652a9f526ba4375c80ae542252Evan Cheng MachineBasicBlock::iterator mi = MBB->begin(); 6229b25b8ca24d6df2e097741dcc15016772ee4eda7Jim Laskey unsigned baseIndex = MIIdx; 6239b25b8ca24d6df2e097741dcc15016772ee4eda7Jim Laskey unsigned start = baseIndex; 624b371f457b0ea4a652a9f526ba4375c80ae542252Evan Cheng unsigned end = start; 625b371f457b0ea4a652a9f526ba4375c80ae542252Evan Cheng while (mi != MBB->end()) { 6266130f66eaae89f8878590796977678afa8448926Evan Cheng if (mi->killsRegister(interval.reg, tri_)) { 627b371f457b0ea4a652a9f526ba4375c80ae542252Evan Cheng DOUT << " killed"; 628b371f457b0ea4a652a9f526ba4375c80ae542252Evan Cheng end = getUseIndex(baseIndex) + 1; 629b371f457b0ea4a652a9f526ba4375c80ae542252Evan Cheng goto exit; 6306130f66eaae89f8878590796977678afa8448926Evan Cheng } else if (mi->modifiesRegister(interval.reg, tri_)) { 631b371f457b0ea4a652a9f526ba4375c80ae542252Evan Cheng // Another instruction redefines the register before it is ever read. 632b371f457b0ea4a652a9f526ba4375c80ae542252Evan Cheng // Then the register is essentially dead at the instruction that defines 633b371f457b0ea4a652a9f526ba4375c80ae542252Evan Cheng // it. Hence its interval is: 634b371f457b0ea4a652a9f526ba4375c80ae542252Evan Cheng // [defSlot(def), defSlot(def)+1) 635b371f457b0ea4a652a9f526ba4375c80ae542252Evan Cheng DOUT << " dead"; 636b371f457b0ea4a652a9f526ba4375c80ae542252Evan Cheng end = getDefIndex(start) + 1; 637b371f457b0ea4a652a9f526ba4375c80ae542252Evan Cheng goto exit; 638b371f457b0ea4a652a9f526ba4375c80ae542252Evan Cheng } 639b371f457b0ea4a652a9f526ba4375c80ae542252Evan Cheng 640b371f457b0ea4a652a9f526ba4375c80ae542252Evan Cheng baseIndex += InstrSlots::NUM; 6417fbad27cfb7298c707e50af10609d463900d7211Owen Anderson while (baseIndex / InstrSlots::NUM < i2miMap_.size() && 6427fbad27cfb7298c707e50af10609d463900d7211Owen Anderson getInstructionFromIndex(baseIndex) == 0) 6437fbad27cfb7298c707e50af10609d463900d7211Owen Anderson baseIndex += InstrSlots::NUM; 644b371f457b0ea4a652a9f526ba4375c80ae542252Evan Cheng ++mi; 645b371f457b0ea4a652a9f526ba4375c80ae542252Evan Cheng } 646b371f457b0ea4a652a9f526ba4375c80ae542252Evan Cheng 647b371f457b0ea4a652a9f526ba4375c80ae542252Evan Chengexit: 64875611fb4e6ab253be30ac29a2b15e9bf8c1d146eEvan Cheng // Live-in register might not be used at all. 64975611fb4e6ab253be30ac29a2b15e9bf8c1d146eEvan Cheng if (end == MIIdx) { 650292da949f6c87d6499425d64d37d7c5870ec57adEvan Cheng if (isAlias) { 651292da949f6c87d6499425d64d37d7c5870ec57adEvan Cheng DOUT << " dead"; 65275611fb4e6ab253be30ac29a2b15e9bf8c1d146eEvan Cheng end = getDefIndex(MIIdx) + 1; 653292da949f6c87d6499425d64d37d7c5870ec57adEvan Cheng } else { 654292da949f6c87d6499425d64d37d7c5870ec57adEvan Cheng DOUT << " live through"; 655292da949f6c87d6499425d64d37d7c5870ec57adEvan Cheng end = baseIndex; 656292da949f6c87d6499425d64d37d7c5870ec57adEvan Cheng } 65724a3cc4c83e5edb25fadf7b8979a26b4451795c6Evan Cheng } 65824a3cc4c83e5edb25fadf7b8979a26b4451795c6Evan Cheng 659f3bb2e65d12857f83b273f4ecab013680310bbbcEvan Cheng LiveRange LR(start, end, interval.getNextValue(start, 0, VNInfoAllocator)); 6609b25b8ca24d6df2e097741dcc15016772ee4eda7Jim Laskey interval.addRange(LR); 661f3bb2e65d12857f83b273f4ecab013680310bbbcEvan Cheng interval.addKill(LR.valno, end); 66224c2e5cf7e926452ea5875d027ec0d24d9c19e39Evan Cheng DOUT << " +" << LR << '\n'; 663b371f457b0ea4a652a9f526ba4375c80ae542252Evan Cheng} 664b371f457b0ea4a652a9f526ba4375c80ae542252Evan Cheng 665ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos/// computeIntervals - computes the live intervals for virtual 6664d46e1e521c0df1990ea50f8146d22bd77ea71a6Alkis Evlogimenos/// registers. for some ordering of the machine instructions [1,N] a 66708cec00588ec1a8fa85b208555f006d7396ae7a4Alkis Evlogimenos/// live interval is an interval [i, j) where 1 <= i <= j < N for 668ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos/// which a variable is live 669f7da2c7b0c6293c268881628fc351bed7763f1f4Chris Lattnervoid LiveIntervals::computeIntervals() { 670bdc679d564e67a81792e463f6614b0088f975025Bill Wendling DOUT << "********** COMPUTING LIVE INTERVALS **********\n" 671bdc679d564e67a81792e463f6614b0088f975025Bill Wendling << "********** Function: " 672bdc679d564e67a81792e463f6614b0088f975025Bill Wendling << ((Value*)mf_->getFunction())->getName() << '\n'; 6736b128bdc58a496e9f08e4d09416330320761baffChris Lattner // Track the index of the current machine instr. 6746b128bdc58a496e9f08e4d09416330320761baffChris Lattner unsigned MIIndex = 0; 6757fbad27cfb7298c707e50af10609d463900d7211Owen Anderson 6767fbad27cfb7298c707e50af10609d463900d7211Owen Anderson // Skip over empty initial indices. 6777fbad27cfb7298c707e50af10609d463900d7211Owen Anderson while (MIIndex / InstrSlots::NUM < i2miMap_.size() && 6787fbad27cfb7298c707e50af10609d463900d7211Owen Anderson getInstructionFromIndex(MIIndex) == 0) 6797fbad27cfb7298c707e50af10609d463900d7211Owen Anderson MIIndex += InstrSlots::NUM; 6807fbad27cfb7298c707e50af10609d463900d7211Owen Anderson 681428b92eb83b457b71d29d1d4b7900d36a0ce9a53Chris Lattner for (MachineFunction::iterator MBBI = mf_->begin(), E = mf_->end(); 682428b92eb83b457b71d29d1d4b7900d36a0ce9a53Chris Lattner MBBI != E; ++MBBI) { 683428b92eb83b457b71d29d1d4b7900d36a0ce9a53Chris Lattner MachineBasicBlock *MBB = MBBI; 684bdc679d564e67a81792e463f6614b0088f975025Bill Wendling DOUT << ((Value*)MBB->getBasicBlock())->getName() << ":\n"; 6851a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos 686428b92eb83b457b71d29d1d4b7900d36a0ce9a53Chris Lattner MachineBasicBlock::iterator MI = MBB->begin(), miEnd = MBB->end(); 6870c9f92e1ff64ee56724eae444a0442b02f83d0a8Evan Cheng 688cb406c25973b4e88a6c10ad839ef1beeb3664715Dan Gohman // Create intervals for live-ins to this BB first. 689cb406c25973b4e88a6c10ad839ef1beeb3664715Dan Gohman for (MachineBasicBlock::const_livein_iterator LI = MBB->livein_begin(), 690cb406c25973b4e88a6c10ad839ef1beeb3664715Dan Gohman LE = MBB->livein_end(); LI != LE; ++LI) { 691cb406c25973b4e88a6c10ad839ef1beeb3664715Dan Gohman handleLiveInRegister(MBB, MIIndex, getOrCreateInterval(*LI)); 692cb406c25973b4e88a6c10ad839ef1beeb3664715Dan Gohman // Multiple live-ins can alias the same register. 6936f0d024a534af18d9e60b3ea757376cd8a3a980eDan Gohman for (const unsigned* AS = tri_->getSubRegisters(*LI); *AS; ++AS) 694cb406c25973b4e88a6c10ad839ef1beeb3664715Dan Gohman if (!hasInterval(*AS)) 695cb406c25973b4e88a6c10ad839ef1beeb3664715Dan Gohman handleLiveInRegister(MBB, MIIndex, getOrCreateInterval(*AS), 696cb406c25973b4e88a6c10ad839ef1beeb3664715Dan Gohman true); 697dffb2e83ed2546226d09c40aa43524e2392322daChris Lattner } 698dffb2e83ed2546226d09c40aa43524e2392322daChris Lattner 699428b92eb83b457b71d29d1d4b7900d36a0ce9a53Chris Lattner for (; MI != miEnd; ++MI) { 700bdc679d564e67a81792e463f6614b0088f975025Bill Wendling DOUT << MIIndex << "\t" << *MI; 7011a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos 702438f7bc67cf235ccee7e6f7ac7f4ae2186eb8020Evan Cheng // Handle defs. 703428b92eb83b457b71d29d1d4b7900d36a0ce9a53Chris Lattner for (int i = MI->getNumOperands() - 1; i >= 0; --i) { 704428b92eb83b457b71d29d1d4b7900d36a0ce9a53Chris Lattner MachineOperand &MO = MI->getOperand(i); 7051a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // handle register defs - build intervals 706428b92eb83b457b71d29d1d4b7900d36a0ce9a53Chris Lattner if (MO.isRegister() && MO.getReg() && MO.isDef()) 707ef0732d25a9882c947984ae3f2afbef5463ba00fEvan Cheng handleRegisterDef(MBB, MI, MIIndex, MO, i); 7081a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos } 7096b128bdc58a496e9f08e4d09416330320761baffChris Lattner 7106b128bdc58a496e9f08e4d09416330320761baffChris Lattner MIIndex += InstrSlots::NUM; 7117fbad27cfb7298c707e50af10609d463900d7211Owen Anderson 7127fbad27cfb7298c707e50af10609d463900d7211Owen Anderson // Skip over empty indices. 7137fbad27cfb7298c707e50af10609d463900d7211Owen Anderson while (MIIndex / InstrSlots::NUM < i2miMap_.size() && 7147fbad27cfb7298c707e50af10609d463900d7211Owen Anderson getInstructionFromIndex(MIIndex) == 0) 7157fbad27cfb7298c707e50af10609d463900d7211Owen Anderson MIIndex += InstrSlots::NUM; 716ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos } 7171a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos } 718ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos} 719b27ef248f579b354aab434f63c417ab1103e47e2Alkis Evlogimenos 7204ca980e7f9ce7b78955307c2d07001a24d3b6befEvan Chengbool LiveIntervals::findLiveInMBBs(const LiveRange &LR, 721a5bfc97da713ec9e185226d44e6adb4d3087b304Evan Cheng SmallVectorImpl<MachineBasicBlock*> &MBBs) const { 7224ca980e7f9ce7b78955307c2d07001a24d3b6befEvan Cheng std::vector<IdxMBBPair>::const_iterator I = 7234ca980e7f9ce7b78955307c2d07001a24d3b6befEvan Cheng std::lower_bound(Idx2MBBMap.begin(), Idx2MBBMap.end(), LR.start); 7244ca980e7f9ce7b78955307c2d07001a24d3b6befEvan Cheng 7254ca980e7f9ce7b78955307c2d07001a24d3b6befEvan Cheng bool ResVal = false; 7264ca980e7f9ce7b78955307c2d07001a24d3b6befEvan Cheng while (I != Idx2MBBMap.end()) { 7274ca980e7f9ce7b78955307c2d07001a24d3b6befEvan Cheng if (LR.end <= I->first) 7284ca980e7f9ce7b78955307c2d07001a24d3b6befEvan Cheng break; 7294ca980e7f9ce7b78955307c2d07001a24d3b6befEvan Cheng MBBs.push_back(I->second); 7304ca980e7f9ce7b78955307c2d07001a24d3b6befEvan Cheng ResVal = true; 7314ca980e7f9ce7b78955307c2d07001a24d3b6befEvan Cheng ++I; 7324ca980e7f9ce7b78955307c2d07001a24d3b6befEvan Cheng } 7334ca980e7f9ce7b78955307c2d07001a24d3b6befEvan Cheng return ResVal; 7344ca980e7f9ce7b78955307c2d07001a24d3b6befEvan Cheng} 7354ca980e7f9ce7b78955307c2d07001a24d3b6befEvan Cheng 7364ca980e7f9ce7b78955307c2d07001a24d3b6befEvan Cheng 73703857b29d8271a23943254579e6cf7b7df4b1bd3Owen AndersonLiveInterval* LiveIntervals::createInterval(unsigned reg) { 7386f0d024a534af18d9e60b3ea757376cd8a3a980eDan Gohman float Weight = TargetRegisterInfo::isPhysicalRegister(reg) ? 7397902c75331fa8f38fc8380f5573d935c0d149ef5Jim Laskey HUGE_VALF : 0.0F; 74003857b29d8271a23943254579e6cf7b7df4b1bd3Owen Anderson return new LiveInterval(reg, Weight); 7419a8b490735d216435862a3d52e669357f165550fAlkis Evlogimenos} 742f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng 743c8d044e4f779fdcfc5e7d592927740fd8f672a70Evan Cheng/// getVNInfoSourceReg - Helper function that parses the specified VNInfo 744c8d044e4f779fdcfc5e7d592927740fd8f672a70Evan Cheng/// copy field and returns the source register that defines it. 745c8d044e4f779fdcfc5e7d592927740fd8f672a70Evan Chengunsigned LiveIntervals::getVNInfoSourceReg(const VNInfo *VNI) const { 746c8d044e4f779fdcfc5e7d592927740fd8f672a70Evan Cheng if (!VNI->copy) 747c8d044e4f779fdcfc5e7d592927740fd8f672a70Evan Cheng return 0; 748c8d044e4f779fdcfc5e7d592927740fd8f672a70Evan Cheng 749c8d044e4f779fdcfc5e7d592927740fd8f672a70Evan Cheng if (VNI->copy->getOpcode() == TargetInstrInfo::EXTRACT_SUBREG) 750c8d044e4f779fdcfc5e7d592927740fd8f672a70Evan Cheng return VNI->copy->getOperand(1).getReg(); 7517e073baedb8232b9519dbe15ea141ff98ccfe6aeEvan Cheng if (VNI->copy->getOpcode() == TargetInstrInfo::INSERT_SUBREG) 7527e073baedb8232b9519dbe15ea141ff98ccfe6aeEvan Cheng return VNI->copy->getOperand(2).getReg(); 753c8d044e4f779fdcfc5e7d592927740fd8f672a70Evan Cheng unsigned SrcReg, DstReg; 754c8d044e4f779fdcfc5e7d592927740fd8f672a70Evan Cheng if (tii_->isMoveInstr(*VNI->copy, SrcReg, DstReg)) 755c8d044e4f779fdcfc5e7d592927740fd8f672a70Evan Cheng return SrcReg; 756c8d044e4f779fdcfc5e7d592927740fd8f672a70Evan Cheng assert(0 && "Unrecognized copy instruction!"); 757c8d044e4f779fdcfc5e7d592927740fd8f672a70Evan Cheng return 0; 758c8d044e4f779fdcfc5e7d592927740fd8f672a70Evan Cheng} 759f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng 760f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng//===----------------------------------------------------------------------===// 761f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng// Register allocator hooks. 762f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng// 763f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng 764d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng/// getReMatImplicitUse - If the remat definition MI has one (for now, we only 765d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng/// allow one) virtual register operand, then its uses are implicitly using 766d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng/// the register. Returns the virtual register. 767d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Chengunsigned LiveIntervals::getReMatImplicitUse(const LiveInterval &li, 768d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng MachineInstr *MI) const { 769d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng unsigned RegOp = 0; 770d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) { 771d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng MachineOperand &MO = MI->getOperand(i); 772d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng if (!MO.isRegister() || !MO.isUse()) 773d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng continue; 774d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng unsigned Reg = MO.getReg(); 775d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng if (Reg == 0 || Reg == li.reg) 776d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng continue; 777d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng // FIXME: For now, only remat MI with at most one register operand. 778d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng assert(!RegOp && 779d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng "Can't rematerialize instruction with multiple register operand!"); 780d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng RegOp = MO.getReg(); 7816d69ba8a6901c69d78488cbc41f8dbf080618fdeDan Gohman#ifndef NDEBUG 782d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng break; 7836d69ba8a6901c69d78488cbc41f8dbf080618fdeDan Gohman#endif 784d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng } 785d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng return RegOp; 786d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng} 787d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng 788d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng/// isValNoAvailableAt - Return true if the val# of the specified interval 789d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng/// which reaches the given instruction also reaches the specified use index. 790d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Chengbool LiveIntervals::isValNoAvailableAt(const LiveInterval &li, MachineInstr *MI, 791d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng unsigned UseIdx) const { 792d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng unsigned Index = getInstructionIndex(MI); 793d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng VNInfo *ValNo = li.FindLiveRangeContaining(Index)->valno; 794d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng LiveInterval::const_iterator UI = li.FindLiveRangeContaining(UseIdx); 795d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng return UI != li.end() && UI->valno == ValNo; 796d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng} 797d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng 798f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng/// isReMaterializable - Returns true if the definition MI of the specified 799f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng/// val# of the specified interval is re-materializable. 800f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Chengbool LiveIntervals::isReMaterializable(const LiveInterval &li, 8015ef3a04b542c4e585276768fa9ca2af698ef5c87Evan Cheng const VNInfo *ValNo, MachineInstr *MI, 8025ef3a04b542c4e585276768fa9ca2af698ef5c87Evan Cheng bool &isLoad) { 803f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng if (DisableReMat) 804f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng return false; 805f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng 80620ccded7dec5b90e58f649f4fb95b166a642b8cbEvan Cheng if (MI->getOpcode() == TargetInstrInfo::IMPLICIT_DEF) 807d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng return true; 808dd3465eed17cdf226bdb465e604dfa851d36029dEvan Cheng 809dd3465eed17cdf226bdb465e604dfa851d36029dEvan Cheng int FrameIdx = 0; 810dd3465eed17cdf226bdb465e604dfa851d36029dEvan Cheng if (tii_->isLoadFromStackSlot(MI, FrameIdx) && 811249ded3fa8884f91fded869fb6e251b8aebb0376Evan Cheng mf_->getFrameInfo()->isImmutableObjectIndex(FrameIdx)) 81279a0c1e46c4f7d8a2a06f4ef3e2c54d883c7fe25Evan Cheng // FIXME: Let target specific isReallyTriviallyReMaterializable determines 81379a0c1e46c4f7d8a2a06f4ef3e2c54d883c7fe25Evan Cheng // this but remember this is not safe to fold into a two-address 81479a0c1e46c4f7d8a2a06f4ef3e2c54d883c7fe25Evan Cheng // instruction. 815249ded3fa8884f91fded869fb6e251b8aebb0376Evan Cheng // This is a load from fixed stack slot. It can be rematerialized. 816dd3465eed17cdf226bdb465e604dfa851d36029dEvan Cheng return true; 817dd3465eed17cdf226bdb465e604dfa851d36029dEvan Cheng 8186d69ba8a6901c69d78488cbc41f8dbf080618fdeDan Gohman // If the target-specific rules don't identify an instruction as 8196d69ba8a6901c69d78488cbc41f8dbf080618fdeDan Gohman // being trivially rematerializable, use some target-independent 8206d69ba8a6901c69d78488cbc41f8dbf080618fdeDan Gohman // rules. 8216d69ba8a6901c69d78488cbc41f8dbf080618fdeDan Gohman if (!MI->getDesc().isRematerializable() || 8226d69ba8a6901c69d78488cbc41f8dbf080618fdeDan Gohman !tii_->isTriviallyReMaterializable(MI)) { 8234c8f87038ddc0fbcce751f0e2e7c0e564abca096Dan Gohman if (!EnableAggressiveRemat) 8244c8f87038ddc0fbcce751f0e2e7c0e564abca096Dan Gohman return false; 8256d69ba8a6901c69d78488cbc41f8dbf080618fdeDan Gohman 8260471a79f2000eb1eb4458e7b3dcd254172fae739Dan Gohman // If the instruction accesses memory but the memoperands have been lost, 8276d69ba8a6901c69d78488cbc41f8dbf080618fdeDan Gohman // we can't analyze it. 82820ccded7dec5b90e58f649f4fb95b166a642b8cbEvan Cheng const TargetInstrDesc &TID = MI->getDesc(); 8296d69ba8a6901c69d78488cbc41f8dbf080618fdeDan Gohman if ((TID.mayLoad() || TID.mayStore()) && MI->memoperands_empty()) 8306d69ba8a6901c69d78488cbc41f8dbf080618fdeDan Gohman return false; 8316d69ba8a6901c69d78488cbc41f8dbf080618fdeDan Gohman 8326d69ba8a6901c69d78488cbc41f8dbf080618fdeDan Gohman // Avoid instructions obviously unsafe for remat. 8336d69ba8a6901c69d78488cbc41f8dbf080618fdeDan Gohman if (TID.hasUnmodeledSideEffects() || TID.isNotDuplicable()) 8346d69ba8a6901c69d78488cbc41f8dbf080618fdeDan Gohman return false; 8356d69ba8a6901c69d78488cbc41f8dbf080618fdeDan Gohman 8366d69ba8a6901c69d78488cbc41f8dbf080618fdeDan Gohman // If the instruction accesses memory and the memory could be non-constant, 8376d69ba8a6901c69d78488cbc41f8dbf080618fdeDan Gohman // assume the instruction is not rematerializable. 838fed90b6d097d50881afb45e4d79f430db66dd741Dan Gohman for (std::list<MachineMemOperand>::const_iterator I = MI->memoperands_begin(), 8396d69ba8a6901c69d78488cbc41f8dbf080618fdeDan Gohman E = MI->memoperands_end(); I != E; ++I) { 8406d69ba8a6901c69d78488cbc41f8dbf080618fdeDan Gohman const MachineMemOperand &MMO = *I; 8416d69ba8a6901c69d78488cbc41f8dbf080618fdeDan Gohman if (MMO.isVolatile() || MMO.isStore()) 8426d69ba8a6901c69d78488cbc41f8dbf080618fdeDan Gohman return false; 8436d69ba8a6901c69d78488cbc41f8dbf080618fdeDan Gohman const Value *V = MMO.getValue(); 8446d69ba8a6901c69d78488cbc41f8dbf080618fdeDan Gohman if (!V) 8456d69ba8a6901c69d78488cbc41f8dbf080618fdeDan Gohman return false; 8466d69ba8a6901c69d78488cbc41f8dbf080618fdeDan Gohman if (const PseudoSourceValue *PSV = dyn_cast<PseudoSourceValue>(V)) { 8476d69ba8a6901c69d78488cbc41f8dbf080618fdeDan Gohman if (!PSV->isConstant(mf_->getFrameInfo())) 8486d69ba8a6901c69d78488cbc41f8dbf080618fdeDan Gohman return false; 8496d69ba8a6901c69d78488cbc41f8dbf080618fdeDan Gohman } else if (!aa_->pointsToConstantMemory(V)) 8506d69ba8a6901c69d78488cbc41f8dbf080618fdeDan Gohman return false; 8516d69ba8a6901c69d78488cbc41f8dbf080618fdeDan Gohman } 8526d69ba8a6901c69d78488cbc41f8dbf080618fdeDan Gohman 8536d69ba8a6901c69d78488cbc41f8dbf080618fdeDan Gohman // If any of the registers accessed are non-constant, conservatively assume 8546d69ba8a6901c69d78488cbc41f8dbf080618fdeDan Gohman // the instruction is not rematerializable. 8556d69ba8a6901c69d78488cbc41f8dbf080618fdeDan Gohman unsigned ImpUse = 0; 8566d69ba8a6901c69d78488cbc41f8dbf080618fdeDan Gohman for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) { 8576d69ba8a6901c69d78488cbc41f8dbf080618fdeDan Gohman const MachineOperand &MO = MI->getOperand(i); 8586d69ba8a6901c69d78488cbc41f8dbf080618fdeDan Gohman if (MO.isReg()) { 8596d69ba8a6901c69d78488cbc41f8dbf080618fdeDan Gohman unsigned Reg = MO.getReg(); 8606d69ba8a6901c69d78488cbc41f8dbf080618fdeDan Gohman if (Reg == 0) 861d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng continue; 8626d69ba8a6901c69d78488cbc41f8dbf080618fdeDan Gohman if (TargetRegisterInfo::isPhysicalRegister(Reg)) 8636d69ba8a6901c69d78488cbc41f8dbf080618fdeDan Gohman return false; 8646d69ba8a6901c69d78488cbc41f8dbf080618fdeDan Gohman 8656d69ba8a6901c69d78488cbc41f8dbf080618fdeDan Gohman // Only allow one def, and that in the first operand. 8666d69ba8a6901c69d78488cbc41f8dbf080618fdeDan Gohman if (MO.isDef() != (i == 0)) 867d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng return false; 8686d69ba8a6901c69d78488cbc41f8dbf080618fdeDan Gohman 8696d69ba8a6901c69d78488cbc41f8dbf080618fdeDan Gohman // Only allow constant-valued registers. 8706d69ba8a6901c69d78488cbc41f8dbf080618fdeDan Gohman bool IsLiveIn = mri_->isLiveIn(Reg); 8716d69ba8a6901c69d78488cbc41f8dbf080618fdeDan Gohman MachineRegisterInfo::def_iterator I = mri_->def_begin(Reg), 8726d69ba8a6901c69d78488cbc41f8dbf080618fdeDan Gohman E = mri_->def_end(); 8736d69ba8a6901c69d78488cbc41f8dbf080618fdeDan Gohman 8746d69ba8a6901c69d78488cbc41f8dbf080618fdeDan Gohman // For the def, it should be the only def. 8756d69ba8a6901c69d78488cbc41f8dbf080618fdeDan Gohman if (MO.isDef() && (next(I) != E || IsLiveIn)) 8766d69ba8a6901c69d78488cbc41f8dbf080618fdeDan Gohman return false; 8776d69ba8a6901c69d78488cbc41f8dbf080618fdeDan Gohman 8786d69ba8a6901c69d78488cbc41f8dbf080618fdeDan Gohman if (MO.isUse()) { 8796d69ba8a6901c69d78488cbc41f8dbf080618fdeDan Gohman // Only allow one use other register use, as that's all the 8806d69ba8a6901c69d78488cbc41f8dbf080618fdeDan Gohman // remat mechanisms support currently. 8816d69ba8a6901c69d78488cbc41f8dbf080618fdeDan Gohman if (Reg != li.reg) { 8826d69ba8a6901c69d78488cbc41f8dbf080618fdeDan Gohman if (ImpUse == 0) 8836d69ba8a6901c69d78488cbc41f8dbf080618fdeDan Gohman ImpUse = Reg; 8846d69ba8a6901c69d78488cbc41f8dbf080618fdeDan Gohman else if (Reg != ImpUse) 8856d69ba8a6901c69d78488cbc41f8dbf080618fdeDan Gohman return false; 8866d69ba8a6901c69d78488cbc41f8dbf080618fdeDan Gohman } 8876d69ba8a6901c69d78488cbc41f8dbf080618fdeDan Gohman // For uses, there should be only one associate def. 8886d69ba8a6901c69d78488cbc41f8dbf080618fdeDan Gohman if (I != E && (next(I) != E || IsLiveIn)) 8896d69ba8a6901c69d78488cbc41f8dbf080618fdeDan Gohman return false; 8906d69ba8a6901c69d78488cbc41f8dbf080618fdeDan Gohman } 891d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng } 892d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng } 8935ef3a04b542c4e585276768fa9ca2af698ef5c87Evan Cheng } 894f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng 8956d69ba8a6901c69d78488cbc41f8dbf080618fdeDan Gohman unsigned ImpUse = getReMatImplicitUse(li, MI); 8966d69ba8a6901c69d78488cbc41f8dbf080618fdeDan Gohman if (ImpUse) { 8976d69ba8a6901c69d78488cbc41f8dbf080618fdeDan Gohman const LiveInterval &ImpLi = getInterval(ImpUse); 8986d69ba8a6901c69d78488cbc41f8dbf080618fdeDan Gohman for (MachineRegisterInfo::use_iterator ri = mri_->use_begin(li.reg), 8996d69ba8a6901c69d78488cbc41f8dbf080618fdeDan Gohman re = mri_->use_end(); ri != re; ++ri) { 9006d69ba8a6901c69d78488cbc41f8dbf080618fdeDan Gohman MachineInstr *UseMI = &*ri; 9016d69ba8a6901c69d78488cbc41f8dbf080618fdeDan Gohman unsigned UseIdx = getInstructionIndex(UseMI); 9026d69ba8a6901c69d78488cbc41f8dbf080618fdeDan Gohman if (li.FindLiveRangeContaining(UseIdx)->valno != ValNo) 9036d69ba8a6901c69d78488cbc41f8dbf080618fdeDan Gohman continue; 9046d69ba8a6901c69d78488cbc41f8dbf080618fdeDan Gohman if (!isValNoAvailableAt(ImpLi, MI, UseIdx)) 9056d69ba8a6901c69d78488cbc41f8dbf080618fdeDan Gohman return false; 9066d69ba8a6901c69d78488cbc41f8dbf080618fdeDan Gohman } 9076d69ba8a6901c69d78488cbc41f8dbf080618fdeDan Gohman } 9086d69ba8a6901c69d78488cbc41f8dbf080618fdeDan Gohman return true; 9095ef3a04b542c4e585276768fa9ca2af698ef5c87Evan Cheng} 9105ef3a04b542c4e585276768fa9ca2af698ef5c87Evan Cheng 9115ef3a04b542c4e585276768fa9ca2af698ef5c87Evan Cheng/// isReMaterializable - Returns true if every definition of MI of every 9125ef3a04b542c4e585276768fa9ca2af698ef5c87Evan Cheng/// val# of the specified interval is re-materializable. 9135ef3a04b542c4e585276768fa9ca2af698ef5c87Evan Chengbool LiveIntervals::isReMaterializable(const LiveInterval &li, bool &isLoad) { 9145ef3a04b542c4e585276768fa9ca2af698ef5c87Evan Cheng isLoad = false; 9155ef3a04b542c4e585276768fa9ca2af698ef5c87Evan Cheng for (LiveInterval::const_vni_iterator i = li.vni_begin(), e = li.vni_end(); 9165ef3a04b542c4e585276768fa9ca2af698ef5c87Evan Cheng i != e; ++i) { 9175ef3a04b542c4e585276768fa9ca2af698ef5c87Evan Cheng const VNInfo *VNI = *i; 9185ef3a04b542c4e585276768fa9ca2af698ef5c87Evan Cheng unsigned DefIdx = VNI->def; 9195ef3a04b542c4e585276768fa9ca2af698ef5c87Evan Cheng if (DefIdx == ~1U) 9205ef3a04b542c4e585276768fa9ca2af698ef5c87Evan Cheng continue; // Dead val#. 9215ef3a04b542c4e585276768fa9ca2af698ef5c87Evan Cheng // Is the def for the val# rematerializable? 9225ef3a04b542c4e585276768fa9ca2af698ef5c87Evan Cheng if (DefIdx == ~0u) 9235ef3a04b542c4e585276768fa9ca2af698ef5c87Evan Cheng return false; 9245ef3a04b542c4e585276768fa9ca2af698ef5c87Evan Cheng MachineInstr *ReMatDefMI = getInstructionFromIndex(DefIdx); 9255ef3a04b542c4e585276768fa9ca2af698ef5c87Evan Cheng bool DefIsLoad = false; 926d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng if (!ReMatDefMI || 927d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng !isReMaterializable(li, VNI, ReMatDefMI, DefIsLoad)) 928f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng return false; 9295ef3a04b542c4e585276768fa9ca2af698ef5c87Evan Cheng isLoad |= DefIsLoad; 930f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng } 931f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng return true; 932f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng} 933f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng 93479a0c1e46c4f7d8a2a06f4ef3e2c54d883c7fe25Evan Cheng/// FilterFoldedOps - Filter out two-address use operands. Return 93579a0c1e46c4f7d8a2a06f4ef3e2c54d883c7fe25Evan Cheng/// true if it finds any issue with the operands that ought to prevent 93679a0c1e46c4f7d8a2a06f4ef3e2c54d883c7fe25Evan Cheng/// folding. 93779a0c1e46c4f7d8a2a06f4ef3e2c54d883c7fe25Evan Chengstatic bool FilterFoldedOps(MachineInstr *MI, 93879a0c1e46c4f7d8a2a06f4ef3e2c54d883c7fe25Evan Cheng SmallVector<unsigned, 2> &Ops, 93979a0c1e46c4f7d8a2a06f4ef3e2c54d883c7fe25Evan Cheng unsigned &MRInfo, 94079a0c1e46c4f7d8a2a06f4ef3e2c54d883c7fe25Evan Cheng SmallVector<unsigned, 2> &FoldOps) { 941749c6f6b5ed301c84aac562e414486549d7b98ebChris Lattner const TargetInstrDesc &TID = MI->getDesc(); 9426e141fd04897e5eb4925bb6351297170ebd8a756Evan Cheng 94379a0c1e46c4f7d8a2a06f4ef3e2c54d883c7fe25Evan Cheng MRInfo = 0; 944aee4af68ae2016afc5b4ec0c430e539c5810a766Evan Cheng for (unsigned i = 0, e = Ops.size(); i != e; ++i) { 945aee4af68ae2016afc5b4ec0c430e539c5810a766Evan Cheng unsigned OpIdx = Ops[i]; 946d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng MachineOperand &MO = MI->getOperand(OpIdx); 947aee4af68ae2016afc5b4ec0c430e539c5810a766Evan Cheng // FIXME: fold subreg use. 948d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng if (MO.getSubReg()) 94979a0c1e46c4f7d8a2a06f4ef3e2c54d883c7fe25Evan Cheng return true; 950d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng if (MO.isDef()) 951aee4af68ae2016afc5b4ec0c430e539c5810a766Evan Cheng MRInfo |= (unsigned)VirtRegMap::isMod; 952aee4af68ae2016afc5b4ec0c430e539c5810a766Evan Cheng else { 953aee4af68ae2016afc5b4ec0c430e539c5810a766Evan Cheng // Filter out two-address use operand(s). 954d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng if (!MO.isImplicit() && 955d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng TID.getOperandConstraint(OpIdx, TOI::TIED_TO) != -1) { 956aee4af68ae2016afc5b4ec0c430e539c5810a766Evan Cheng MRInfo = VirtRegMap::isModRef; 957aee4af68ae2016afc5b4ec0c430e539c5810a766Evan Cheng continue; 958aee4af68ae2016afc5b4ec0c430e539c5810a766Evan Cheng } 959aee4af68ae2016afc5b4ec0c430e539c5810a766Evan Cheng MRInfo |= (unsigned)VirtRegMap::isRef; 960aee4af68ae2016afc5b4ec0c430e539c5810a766Evan Cheng } 961aee4af68ae2016afc5b4ec0c430e539c5810a766Evan Cheng FoldOps.push_back(OpIdx); 962e62f97c094dba44e4c259d20135167fa91912eeaEvan Cheng } 96379a0c1e46c4f7d8a2a06f4ef3e2c54d883c7fe25Evan Cheng return false; 96479a0c1e46c4f7d8a2a06f4ef3e2c54d883c7fe25Evan Cheng} 96579a0c1e46c4f7d8a2a06f4ef3e2c54d883c7fe25Evan Cheng 96679a0c1e46c4f7d8a2a06f4ef3e2c54d883c7fe25Evan Cheng 96779a0c1e46c4f7d8a2a06f4ef3e2c54d883c7fe25Evan Cheng/// tryFoldMemoryOperand - Attempts to fold either a spill / restore from 96879a0c1e46c4f7d8a2a06f4ef3e2c54d883c7fe25Evan Cheng/// slot / to reg or any rematerialized load into ith operand of specified 96979a0c1e46c4f7d8a2a06f4ef3e2c54d883c7fe25Evan Cheng/// MI. If it is successul, MI is updated with the newly created MI and 97079a0c1e46c4f7d8a2a06f4ef3e2c54d883c7fe25Evan Cheng/// returns true. 97179a0c1e46c4f7d8a2a06f4ef3e2c54d883c7fe25Evan Chengbool LiveIntervals::tryFoldMemoryOperand(MachineInstr* &MI, 97279a0c1e46c4f7d8a2a06f4ef3e2c54d883c7fe25Evan Cheng VirtRegMap &vrm, MachineInstr *DefMI, 97379a0c1e46c4f7d8a2a06f4ef3e2c54d883c7fe25Evan Cheng unsigned InstrIdx, 97479a0c1e46c4f7d8a2a06f4ef3e2c54d883c7fe25Evan Cheng SmallVector<unsigned, 2> &Ops, 97579a0c1e46c4f7d8a2a06f4ef3e2c54d883c7fe25Evan Cheng bool isSS, int Slot, unsigned Reg) { 97679a0c1e46c4f7d8a2a06f4ef3e2c54d883c7fe25Evan Cheng // If it is an implicit def instruction, just delete it. 97720ccded7dec5b90e58f649f4fb95b166a642b8cbEvan Cheng if (MI->getOpcode() == TargetInstrInfo::IMPLICIT_DEF) { 97879a0c1e46c4f7d8a2a06f4ef3e2c54d883c7fe25Evan Cheng RemoveMachineInstrFromMaps(MI); 97979a0c1e46c4f7d8a2a06f4ef3e2c54d883c7fe25Evan Cheng vrm.RemoveMachineInstrFromMaps(MI); 98079a0c1e46c4f7d8a2a06f4ef3e2c54d883c7fe25Evan Cheng MI->eraseFromParent(); 98179a0c1e46c4f7d8a2a06f4ef3e2c54d883c7fe25Evan Cheng ++numFolds; 98279a0c1e46c4f7d8a2a06f4ef3e2c54d883c7fe25Evan Cheng return true; 98379a0c1e46c4f7d8a2a06f4ef3e2c54d883c7fe25Evan Cheng } 98479a0c1e46c4f7d8a2a06f4ef3e2c54d883c7fe25Evan Cheng 98579a0c1e46c4f7d8a2a06f4ef3e2c54d883c7fe25Evan Cheng // Filter the list of operand indexes that are to be folded. Abort if 98679a0c1e46c4f7d8a2a06f4ef3e2c54d883c7fe25Evan Cheng // any operand will prevent folding. 98779a0c1e46c4f7d8a2a06f4ef3e2c54d883c7fe25Evan Cheng unsigned MRInfo = 0; 98879a0c1e46c4f7d8a2a06f4ef3e2c54d883c7fe25Evan Cheng SmallVector<unsigned, 2> FoldOps; 98979a0c1e46c4f7d8a2a06f4ef3e2c54d883c7fe25Evan Cheng if (FilterFoldedOps(MI, Ops, MRInfo, FoldOps)) 99079a0c1e46c4f7d8a2a06f4ef3e2c54d883c7fe25Evan Cheng return false; 991cddbb83ea82e98658d9f530c50a7b9d23249afc2Evan Cheng 992427f4c106ac14dcf323dc1bbaf1b8040da03c3c7Evan Cheng // The only time it's safe to fold into a two address instruction is when 993427f4c106ac14dcf323dc1bbaf1b8040da03c3c7Evan Cheng // it's folding reload and spill from / into a spill stack slot. 994427f4c106ac14dcf323dc1bbaf1b8040da03c3c7Evan Cheng if (DefMI && (MRInfo & VirtRegMap::isMod)) 995249ded3fa8884f91fded869fb6e251b8aebb0376Evan Cheng return false; 996249ded3fa8884f91fded869fb6e251b8aebb0376Evan Cheng 997f2f8c2ae07b7d9bdbf1b89781c573c7af2bd5e1bEvan Cheng MachineInstr *fmi = isSS ? tii_->foldMemoryOperand(*mf_, MI, FoldOps, Slot) 998f2f8c2ae07b7d9bdbf1b89781c573c7af2bd5e1bEvan Cheng : tii_->foldMemoryOperand(*mf_, MI, FoldOps, DefMI); 999f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng if (fmi) { 1000d36531249a9a9500e516148e7e72d4c0a7a4d0eeEvan Cheng // Remember this instruction uses the spill slot. 1001d36531249a9a9500e516148e7e72d4c0a7a4d0eeEvan Cheng if (isSS) vrm.addSpillSlotUse(Slot, fmi); 1002d36531249a9a9500e516148e7e72d4c0a7a4d0eeEvan Cheng 1003f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng // Attempt to fold the memory reference into the instruction. If 1004f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng // we can do this, we don't need to insert spill code. 1005f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng MachineBasicBlock &MBB = *MI->getParent(); 10068480293f41c11c22762164449e41cd3adb0dd7d8Evan Cheng if (isSS && !mf_->getFrameInfo()->isImmutableObjectIndex(Slot)) 1007aee4af68ae2016afc5b4ec0c430e539c5810a766Evan Cheng vrm.virtFolded(Reg, MI, fmi, (VirtRegMap::ModRef)MRInfo); 100881a038218171860ee4c382849c647d3dc841fe8bEvan Cheng vrm.transferSpillPts(MI, fmi); 10090cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng vrm.transferRestorePts(MI, fmi); 1010c1f53c742620dd4f2460685477303002bba8a8d8Evan Cheng vrm.transferEmergencySpills(MI, fmi); 1011f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng mi2iMap_.erase(MI); 1012cddbb83ea82e98658d9f530c50a7b9d23249afc2Evan Cheng i2miMap_[InstrIdx /InstrSlots::NUM] = fmi; 1013cddbb83ea82e98658d9f530c50a7b9d23249afc2Evan Cheng mi2iMap_[fmi] = InstrIdx; 1014f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng MI = MBB.insert(MBB.erase(MI), fmi); 10150cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng ++numFolds; 1016f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng return true; 1017f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng } 1018f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng return false; 1019f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng} 1020f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng 1021018f9b020bb12b731b0a7081578e5f82fb35092dEvan Cheng/// canFoldMemoryOperand - Returns true if the specified load / store 1022018f9b020bb12b731b0a7081578e5f82fb35092dEvan Cheng/// folding is possible. 1023018f9b020bb12b731b0a7081578e5f82fb35092dEvan Chengbool LiveIntervals::canFoldMemoryOperand(MachineInstr *MI, 102479a0c1e46c4f7d8a2a06f4ef3e2c54d883c7fe25Evan Cheng SmallVector<unsigned, 2> &Ops, 10253c75ba858b4e2070993cc1241ba74ead17f647d6Evan Cheng bool ReMat) const { 102679a0c1e46c4f7d8a2a06f4ef3e2c54d883c7fe25Evan Cheng // Filter the list of operand indexes that are to be folded. Abort if 102779a0c1e46c4f7d8a2a06f4ef3e2c54d883c7fe25Evan Cheng // any operand will prevent folding. 102879a0c1e46c4f7d8a2a06f4ef3e2c54d883c7fe25Evan Cheng unsigned MRInfo = 0; 1029018f9b020bb12b731b0a7081578e5f82fb35092dEvan Cheng SmallVector<unsigned, 2> FoldOps; 103079a0c1e46c4f7d8a2a06f4ef3e2c54d883c7fe25Evan Cheng if (FilterFoldedOps(MI, Ops, MRInfo, FoldOps)) 103179a0c1e46c4f7d8a2a06f4ef3e2c54d883c7fe25Evan Cheng return false; 1032018f9b020bb12b731b0a7081578e5f82fb35092dEvan Cheng 10333c75ba858b4e2070993cc1241ba74ead17f647d6Evan Cheng // It's only legal to remat for a use, not a def. 10343c75ba858b4e2070993cc1241ba74ead17f647d6Evan Cheng if (ReMat && (MRInfo & VirtRegMap::isMod)) 103579a0c1e46c4f7d8a2a06f4ef3e2c54d883c7fe25Evan Cheng return false; 1036018f9b020bb12b731b0a7081578e5f82fb35092dEvan Cheng 1037d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng return tii_->canFoldMemoryOperand(MI, FoldOps); 1038d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng} 1039d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng 104081a038218171860ee4c382849c647d3dc841fe8bEvan Chengbool LiveIntervals::intervalIsInOneMBB(const LiveInterval &li) const { 104181a038218171860ee4c382849c647d3dc841fe8bEvan Cheng SmallPtrSet<MachineBasicBlock*, 4> MBBs; 104281a038218171860ee4c382849c647d3dc841fe8bEvan Cheng for (LiveInterval::Ranges::const_iterator 104381a038218171860ee4c382849c647d3dc841fe8bEvan Cheng I = li.ranges.begin(), E = li.ranges.end(); I != E; ++I) { 104481a038218171860ee4c382849c647d3dc841fe8bEvan Cheng std::vector<IdxMBBPair>::const_iterator II = 104581a038218171860ee4c382849c647d3dc841fe8bEvan Cheng std::lower_bound(Idx2MBBMap.begin(), Idx2MBBMap.end(), I->start); 104681a038218171860ee4c382849c647d3dc841fe8bEvan Cheng if (II == Idx2MBBMap.end()) 104781a038218171860ee4c382849c647d3dc841fe8bEvan Cheng continue; 104881a038218171860ee4c382849c647d3dc841fe8bEvan Cheng if (I->end > II->first) // crossing a MBB. 104981a038218171860ee4c382849c647d3dc841fe8bEvan Cheng return false; 105081a038218171860ee4c382849c647d3dc841fe8bEvan Cheng MBBs.insert(II->second); 105181a038218171860ee4c382849c647d3dc841fe8bEvan Cheng if (MBBs.size() > 1) 105281a038218171860ee4c382849c647d3dc841fe8bEvan Cheng return false; 105381a038218171860ee4c382849c647d3dc841fe8bEvan Cheng } 105481a038218171860ee4c382849c647d3dc841fe8bEvan Cheng return true; 105581a038218171860ee4c382849c647d3dc841fe8bEvan Cheng} 105681a038218171860ee4c382849c647d3dc841fe8bEvan Cheng 1057d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng/// rewriteImplicitOps - Rewrite implicit use operands of MI (i.e. uses of 1058d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng/// interval on to-be re-materialized operands of MI) with new register. 1059d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Chengvoid LiveIntervals::rewriteImplicitOps(const LiveInterval &li, 1060d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng MachineInstr *MI, unsigned NewVReg, 1061d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng VirtRegMap &vrm) { 1062d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng // There is an implicit use. That means one of the other operand is 1063d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng // being remat'ed and the remat'ed instruction has li.reg as an 1064d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng // use operand. Make sure we rewrite that as well. 1065d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) { 1066d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng MachineOperand &MO = MI->getOperand(i); 1067d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng if (!MO.isRegister()) 1068d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng continue; 1069d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng unsigned Reg = MO.getReg(); 1070d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng if (Reg == 0 || TargetRegisterInfo::isPhysicalRegister(Reg)) 1071d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng continue; 1072d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng if (!vrm.isReMaterialized(Reg)) 1073d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng continue; 1074d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng MachineInstr *ReMatMI = vrm.getReMaterializedMI(Reg); 10756130f66eaae89f8878590796977678afa8448926Evan Cheng MachineOperand *UseMO = ReMatMI->findRegisterUseOperand(li.reg); 10766130f66eaae89f8878590796977678afa8448926Evan Cheng if (UseMO) 10776130f66eaae89f8878590796977678afa8448926Evan Cheng UseMO->setReg(NewVReg); 1078d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng } 1079d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng} 1080d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng 1081f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng/// rewriteInstructionForSpills, rewriteInstructionsForSpills - Helper functions 1082f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng/// for addIntervalsForSpills to rewrite uses / defs for the given live range. 1083018f9b020bb12b731b0a7081578e5f82fb35092dEvan Chengbool LiveIntervals:: 1084d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan ChengrewriteInstructionForSpills(const LiveInterval &li, const VNInfo *VNI, 1085d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng bool TrySplit, unsigned index, unsigned end, MachineInstr *MI, 108681a038218171860ee4c382849c647d3dc841fe8bEvan Cheng MachineInstr *ReMatOrigDefMI, MachineInstr *ReMatDefMI, 1087f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng unsigned Slot, int LdSlot, 1088f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng bool isLoad, bool isLoadSS, bool DefIsReMat, bool CanDelete, 1089d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng VirtRegMap &vrm, 1090f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng const TargetRegisterClass* rc, 1091f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng SmallVector<int, 4> &ReMatIds, 109222f07ffd27d1d721634d502c37267721d2e025cfEvan Cheng const MachineLoopInfo *loopInfo, 1093313d4b809326f3e04814f94e5b8ae05649d8e0f6Evan Cheng unsigned &NewVReg, unsigned ImpUse, bool &HasDef, bool &HasUse, 1094289983123ba4170c8a27e9638935818f8142bc89Owen Anderson DenseMap<unsigned,unsigned> &MBBVRegsMap, 10959c3c2213647e3f1b71722d61875ebac01b65cb91Evan Cheng std::vector<LiveInterval*> &NewLIs, float &SSWeight) { 10969c3c2213647e3f1b71722d61875ebac01b65cb91Evan Cheng MachineBasicBlock *MBB = MI->getParent(); 10979c3c2213647e3f1b71722d61875ebac01b65cb91Evan Cheng unsigned loopDepth = loopInfo->getLoopDepth(MBB); 1098018f9b020bb12b731b0a7081578e5f82fb35092dEvan Cheng bool CanFold = false; 1099f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng RestartInstruction: 1100f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng for (unsigned i = 0; i != MI->getNumOperands(); ++i) { 1101f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng MachineOperand& mop = MI->getOperand(i); 1102f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng if (!mop.isRegister()) 1103f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng continue; 1104f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng unsigned Reg = mop.getReg(); 1105f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng unsigned RegI = Reg; 11066f0d024a534af18d9e60b3ea757376cd8a3a980eDan Gohman if (Reg == 0 || TargetRegisterInfo::isPhysicalRegister(Reg)) 1107f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng continue; 1108f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng if (Reg != li.reg) 1109f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng continue; 1110f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng 1111f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng bool TryFold = !DefIsReMat; 1112cb3c330d39442130d0587208d673ce9c33c7008fEvan Cheng bool FoldSS = true; // Default behavior unless it's a remat. 1113f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng int FoldSlot = Slot; 1114f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng if (DefIsReMat) { 1115f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng // If this is the rematerializable definition MI itself and 1116f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng // all of its uses are rematerialized, simply delete it. 111781a038218171860ee4c382849c647d3dc841fe8bEvan Cheng if (MI == ReMatOrigDefMI && CanDelete) { 1118cddbb83ea82e98658d9f530c50a7b9d23249afc2Evan Cheng DOUT << "\t\t\t\tErasing re-materlizable def: "; 1119cddbb83ea82e98658d9f530c50a7b9d23249afc2Evan Cheng DOUT << MI << '\n'; 1120f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng RemoveMachineInstrFromMaps(MI); 1121cada245d06959831b90f8c29f92e77beda4b71cbEvan Cheng vrm.RemoveMachineInstrFromMaps(MI); 1122f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng MI->eraseFromParent(); 1123f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng break; 1124f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng } 1125f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng 1126f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng // If def for this use can't be rematerialized, then try folding. 11270cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng // If def is rematerializable and it's a load, also try folding. 1128cb3c330d39442130d0587208d673ce9c33c7008fEvan Cheng TryFold = !ReMatDefMI || (ReMatDefMI && (MI == ReMatOrigDefMI || isLoad)); 1129f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng if (isLoad) { 1130f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng // Try fold loads (from stack slot, constant pool, etc.) into uses. 1131f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng FoldSS = isLoadSS; 1132f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng FoldSlot = LdSlot; 1133f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng } 1134f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng } 1135f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng 1136f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng // Scan all of the operands of this instruction rewriting operands 1137f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng // to use NewVReg instead of li.reg as appropriate. We do this for 1138f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng // two reasons: 1139f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng // 1140f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng // 1. If the instr reads the same spilled vreg multiple times, we 1141f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng // want to reuse the NewVReg. 1142f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng // 2. If the instr is a two-addr instruction, we are required to 1143f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng // keep the src/dst regs pinned. 1144f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng // 1145f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng // Keep track of whether we replace a use and/or def so that we can 1146f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng // create the spill interval with the appropriate range. 1147cddbb83ea82e98658d9f530c50a7b9d23249afc2Evan Cheng 114881a038218171860ee4c382849c647d3dc841fe8bEvan Cheng HasUse = mop.isUse(); 114981a038218171860ee4c382849c647d3dc841fe8bEvan Cheng HasDef = mop.isDef(); 1150aee4af68ae2016afc5b4ec0c430e539c5810a766Evan Cheng SmallVector<unsigned, 2> Ops; 1151aee4af68ae2016afc5b4ec0c430e539c5810a766Evan Cheng Ops.push_back(i); 1152f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng for (unsigned j = i+1, e = MI->getNumOperands(); j != e; ++j) { 1153aee4af68ae2016afc5b4ec0c430e539c5810a766Evan Cheng const MachineOperand &MOj = MI->getOperand(j); 1154aee4af68ae2016afc5b4ec0c430e539c5810a766Evan Cheng if (!MOj.isRegister()) 1155f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng continue; 1156aee4af68ae2016afc5b4ec0c430e539c5810a766Evan Cheng unsigned RegJ = MOj.getReg(); 11576f0d024a534af18d9e60b3ea757376cd8a3a980eDan Gohman if (RegJ == 0 || TargetRegisterInfo::isPhysicalRegister(RegJ)) 1158f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng continue; 1159f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng if (RegJ == RegI) { 1160aee4af68ae2016afc5b4ec0c430e539c5810a766Evan Cheng Ops.push_back(j); 1161aee4af68ae2016afc5b4ec0c430e539c5810a766Evan Cheng HasUse |= MOj.isUse(); 1162aee4af68ae2016afc5b4ec0c430e539c5810a766Evan Cheng HasDef |= MOj.isDef(); 1163f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng } 1164f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng } 1165f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng 116679a796c2b17c7ebd4dd489b5de1078fc2148adbaEvan Cheng if (HasUse && !li.liveAt(getUseIndex(index))) 116779a796c2b17c7ebd4dd489b5de1078fc2148adbaEvan Cheng // Must be defined by an implicit def. It should not be spilled. Note, 116879a796c2b17c7ebd4dd489b5de1078fc2148adbaEvan Cheng // this is for correctness reason. e.g. 116979a796c2b17c7ebd4dd489b5de1078fc2148adbaEvan Cheng // 8 %reg1024<def> = IMPLICIT_DEF 117079a796c2b17c7ebd4dd489b5de1078fc2148adbaEvan Cheng // 12 %reg1024<def> = INSERT_SUBREG %reg1024<kill>, %reg1025, 2 117179a796c2b17c7ebd4dd489b5de1078fc2148adbaEvan Cheng // The live range [12, 14) are not part of the r1024 live interval since 117279a796c2b17c7ebd4dd489b5de1078fc2148adbaEvan Cheng // it's defined by an implicit def. It will not conflicts with live 117379a796c2b17c7ebd4dd489b5de1078fc2148adbaEvan Cheng // interval of r1025. Now suppose both registers are spilled, you can 1174b9890ae3c35ad7d8e49261650d5b98f49f97a705Evan Cheng // easily see a situation where both registers are reloaded before 117579a796c2b17c7ebd4dd489b5de1078fc2148adbaEvan Cheng // the INSERT_SUBREG and both target registers that would overlap. 117679a796c2b17c7ebd4dd489b5de1078fc2148adbaEvan Cheng HasUse = false; 117779a796c2b17c7ebd4dd489b5de1078fc2148adbaEvan Cheng 11789c3c2213647e3f1b71722d61875ebac01b65cb91Evan Cheng // Update stack slot spill weight if we are splitting. 1179c3417609ae6e744a29be6962d4fb7811c0102d17Evan Cheng float Weight = getSpillWeight(HasDef, HasUse, loopDepth); 11809c3c2213647e3f1b71722d61875ebac01b65cb91Evan Cheng if (!TrySplit) 11819c3c2213647e3f1b71722d61875ebac01b65cb91Evan Cheng SSWeight += Weight; 11829c3c2213647e3f1b71722d61875ebac01b65cb91Evan Cheng 11839c3c2213647e3f1b71722d61875ebac01b65cb91Evan Cheng if (!TryFold) 11849c3c2213647e3f1b71722d61875ebac01b65cb91Evan Cheng CanFold = false; 11859c3c2213647e3f1b71722d61875ebac01b65cb91Evan Cheng else { 1186018f9b020bb12b731b0a7081578e5f82fb35092dEvan Cheng // Do not fold load / store here if we are splitting. We'll find an 1187018f9b020bb12b731b0a7081578e5f82fb35092dEvan Cheng // optimal point to insert a load / store later. 1188018f9b020bb12b731b0a7081578e5f82fb35092dEvan Cheng if (!TrySplit) { 1189018f9b020bb12b731b0a7081578e5f82fb35092dEvan Cheng if (tryFoldMemoryOperand(MI, vrm, ReMatDefMI, index, 1190018f9b020bb12b731b0a7081578e5f82fb35092dEvan Cheng Ops, FoldSS, FoldSlot, Reg)) { 1191018f9b020bb12b731b0a7081578e5f82fb35092dEvan Cheng // Folding the load/store can completely change the instruction in 1192018f9b020bb12b731b0a7081578e5f82fb35092dEvan Cheng // unpredictable ways, rescan it from the beginning. 1193018f9b020bb12b731b0a7081578e5f82fb35092dEvan Cheng HasUse = false; 1194018f9b020bb12b731b0a7081578e5f82fb35092dEvan Cheng HasDef = false; 1195018f9b020bb12b731b0a7081578e5f82fb35092dEvan Cheng CanFold = false; 11969c3c2213647e3f1b71722d61875ebac01b65cb91Evan Cheng if (isRemoved(MI)) { 11979c3c2213647e3f1b71722d61875ebac01b65cb91Evan Cheng SSWeight -= Weight; 11987e073baedb8232b9519dbe15ea141ff98ccfe6aeEvan Cheng break; 11999c3c2213647e3f1b71722d61875ebac01b65cb91Evan Cheng } 1200018f9b020bb12b731b0a7081578e5f82fb35092dEvan Cheng goto RestartInstruction; 1201018f9b020bb12b731b0a7081578e5f82fb35092dEvan Cheng } 1202018f9b020bb12b731b0a7081578e5f82fb35092dEvan Cheng } else { 12039c3c2213647e3f1b71722d61875ebac01b65cb91Evan Cheng // We'll try to fold it later if it's profitable. 12043c75ba858b4e2070993cc1241ba74ead17f647d6Evan Cheng CanFold = canFoldMemoryOperand(MI, Ops, DefIsReMat); 1205018f9b020bb12b731b0a7081578e5f82fb35092dEvan Cheng } 12069c3c2213647e3f1b71722d61875ebac01b65cb91Evan Cheng } 1207cddbb83ea82e98658d9f530c50a7b9d23249afc2Evan Cheng 1208cddbb83ea82e98658d9f530c50a7b9d23249afc2Evan Cheng // Create a new virtual register for the spill interval. 1209cddbb83ea82e98658d9f530c50a7b9d23249afc2Evan Cheng bool CreatedNewVReg = false; 1210cddbb83ea82e98658d9f530c50a7b9d23249afc2Evan Cheng if (NewVReg == 0) { 1211d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng NewVReg = mri_->createVirtualRegister(rc); 1212cddbb83ea82e98658d9f530c50a7b9d23249afc2Evan Cheng vrm.grow(); 1213cddbb83ea82e98658d9f530c50a7b9d23249afc2Evan Cheng CreatedNewVReg = true; 1214cddbb83ea82e98658d9f530c50a7b9d23249afc2Evan Cheng } 1215cddbb83ea82e98658d9f530c50a7b9d23249afc2Evan Cheng mop.setReg(NewVReg); 1216d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng if (mop.isImplicit()) 1217d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng rewriteImplicitOps(li, MI, NewVReg, vrm); 1218cddbb83ea82e98658d9f530c50a7b9d23249afc2Evan Cheng 1219cddbb83ea82e98658d9f530c50a7b9d23249afc2Evan Cheng // Reuse NewVReg for other reads. 1220d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng for (unsigned j = 0, e = Ops.size(); j != e; ++j) { 1221d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng MachineOperand &mopj = MI->getOperand(Ops[j]); 1222d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng mopj.setReg(NewVReg); 1223d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng if (mopj.isImplicit()) 1224d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng rewriteImplicitOps(li, MI, NewVReg, vrm); 1225d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng } 1226cddbb83ea82e98658d9f530c50a7b9d23249afc2Evan Cheng 122781a038218171860ee4c382849c647d3dc841fe8bEvan Cheng if (CreatedNewVReg) { 122881a038218171860ee4c382849c647d3dc841fe8bEvan Cheng if (DefIsReMat) { 122981a038218171860ee4c382849c647d3dc841fe8bEvan Cheng vrm.setVirtIsReMaterialized(NewVReg, ReMatDefMI/*, CanDelete*/); 1230d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng if (ReMatIds[VNI->id] == VirtRegMap::MAX_STACK_SLOT) { 123181a038218171860ee4c382849c647d3dc841fe8bEvan Cheng // Each valnum may have its own remat id. 1232d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng ReMatIds[VNI->id] = vrm.assignVirtReMatId(NewVReg); 123381a038218171860ee4c382849c647d3dc841fe8bEvan Cheng } else { 1234d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng vrm.assignVirtReMatId(NewVReg, ReMatIds[VNI->id]); 123581a038218171860ee4c382849c647d3dc841fe8bEvan Cheng } 123681a038218171860ee4c382849c647d3dc841fe8bEvan Cheng if (!CanDelete || (HasUse && HasDef)) { 123781a038218171860ee4c382849c647d3dc841fe8bEvan Cheng // If this is a two-addr instruction then its use operands are 123881a038218171860ee4c382849c647d3dc841fe8bEvan Cheng // rematerializable but its def is not. It should be assigned a 123981a038218171860ee4c382849c647d3dc841fe8bEvan Cheng // stack slot. 124081a038218171860ee4c382849c647d3dc841fe8bEvan Cheng vrm.assignVirt2StackSlot(NewVReg, Slot); 124181a038218171860ee4c382849c647d3dc841fe8bEvan Cheng } 1242f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng } else { 1243f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng vrm.assignVirt2StackSlot(NewVReg, Slot); 1244f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng } 1245cb3c330d39442130d0587208d673ce9c33c7008fEvan Cheng } else if (HasUse && HasDef && 1246cb3c330d39442130d0587208d673ce9c33c7008fEvan Cheng vrm.getStackSlot(NewVReg) == VirtRegMap::NO_STACK_SLOT) { 1247cb3c330d39442130d0587208d673ce9c33c7008fEvan Cheng // If this interval hasn't been assigned a stack slot (because earlier 1248cb3c330d39442130d0587208d673ce9c33c7008fEvan Cheng // def is a deleted remat def), do it now. 1249cb3c330d39442130d0587208d673ce9c33c7008fEvan Cheng assert(Slot != VirtRegMap::NO_STACK_SLOT); 1250cb3c330d39442130d0587208d673ce9c33c7008fEvan Cheng vrm.assignVirt2StackSlot(NewVReg, Slot); 1251f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng } 1252f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng 1253313d4b809326f3e04814f94e5b8ae05649d8e0f6Evan Cheng // Re-matting an instruction with virtual register use. Add the 1254313d4b809326f3e04814f94e5b8ae05649d8e0f6Evan Cheng // register as an implicit use on the use MI. 1255313d4b809326f3e04814f94e5b8ae05649d8e0f6Evan Cheng if (DefIsReMat && ImpUse) 1256313d4b809326f3e04814f94e5b8ae05649d8e0f6Evan Cheng MI->addOperand(MachineOperand::CreateReg(ImpUse, false, true)); 1257313d4b809326f3e04814f94e5b8ae05649d8e0f6Evan Cheng 1258f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng // create a new register interval for this spill / remat. 1259f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng LiveInterval &nI = getOrCreateInterval(NewVReg); 126081a038218171860ee4c382849c647d3dc841fe8bEvan Cheng if (CreatedNewVReg) { 126181a038218171860ee4c382849c647d3dc841fe8bEvan Cheng NewLIs.push_back(&nI); 12621953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng MBBVRegsMap.insert(std::make_pair(MI->getParent()->getNumber(), NewVReg)); 126381a038218171860ee4c382849c647d3dc841fe8bEvan Cheng if (TrySplit) 126481a038218171860ee4c382849c647d3dc841fe8bEvan Cheng vrm.setIsSplitFromReg(NewVReg, li.reg); 126581a038218171860ee4c382849c647d3dc841fe8bEvan Cheng } 1266f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng 1267f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng if (HasUse) { 126881a038218171860ee4c382849c647d3dc841fe8bEvan Cheng if (CreatedNewVReg) { 126981a038218171860ee4c382849c647d3dc841fe8bEvan Cheng LiveRange LR(getLoadIndex(index), getUseIndex(index)+1, 127081a038218171860ee4c382849c647d3dc841fe8bEvan Cheng nI.getNextValue(~0U, 0, VNInfoAllocator)); 127181a038218171860ee4c382849c647d3dc841fe8bEvan Cheng DOUT << " +" << LR; 127281a038218171860ee4c382849c647d3dc841fe8bEvan Cheng nI.addRange(LR); 127381a038218171860ee4c382849c647d3dc841fe8bEvan Cheng } else { 127481a038218171860ee4c382849c647d3dc841fe8bEvan Cheng // Extend the split live interval to this def / use. 127581a038218171860ee4c382849c647d3dc841fe8bEvan Cheng unsigned End = getUseIndex(index)+1; 127681a038218171860ee4c382849c647d3dc841fe8bEvan Cheng LiveRange LR(nI.ranges[nI.ranges.size()-1].end, End, 127781a038218171860ee4c382849c647d3dc841fe8bEvan Cheng nI.getValNumInfo(nI.getNumValNums()-1)); 127881a038218171860ee4c382849c647d3dc841fe8bEvan Cheng DOUT << " +" << LR; 127981a038218171860ee4c382849c647d3dc841fe8bEvan Cheng nI.addRange(LR); 128081a038218171860ee4c382849c647d3dc841fe8bEvan Cheng } 1281f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng } 1282f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng if (HasDef) { 1283f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng LiveRange LR(getDefIndex(index), getStoreIndex(index), 1284f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng nI.getNextValue(~0U, 0, VNInfoAllocator)); 1285f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng DOUT << " +" << LR; 1286f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng nI.addRange(LR); 1287f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng } 128881a038218171860ee4c382849c647d3dc841fe8bEvan Cheng 1289f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng DOUT << "\t\t\t\tAdded new interval: "; 12906f0d024a534af18d9e60b3ea757376cd8a3a980eDan Gohman nI.print(DOUT, tri_); 1291f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng DOUT << '\n'; 1292f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng } 1293018f9b020bb12b731b0a7081578e5f82fb35092dEvan Cheng return CanFold; 1294f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng} 129581a038218171860ee4c382849c647d3dc841fe8bEvan Chengbool LiveIntervals::anyKillInMBBAfterIdx(const LiveInterval &li, 12960cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng const VNInfo *VNI, 12970cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng MachineBasicBlock *MBB, unsigned Idx) const { 129881a038218171860ee4c382849c647d3dc841fe8bEvan Cheng unsigned End = getMBBEndIdx(MBB); 12990cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng for (unsigned j = 0, ee = VNI->kills.size(); j != ee; ++j) { 13000cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng unsigned KillIdx = VNI->kills[j]; 13010cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng if (KillIdx > Idx && KillIdx < End) 13020cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng return true; 130381a038218171860ee4c382849c647d3dc841fe8bEvan Cheng } 130481a038218171860ee4c382849c647d3dc841fe8bEvan Cheng return false; 130581a038218171860ee4c382849c647d3dc841fe8bEvan Cheng} 130681a038218171860ee4c382849c647d3dc841fe8bEvan Cheng 1307063284c001666c0a3906acbe0a26dc7cae5f081cEvan Cheng/// RewriteInfo - Keep track of machine instrs that will be rewritten 1308063284c001666c0a3906acbe0a26dc7cae5f081cEvan Cheng/// during spilling. 1309844731a7f1909f55935e3514c9e713a62d67662eDan Gohmannamespace { 1310844731a7f1909f55935e3514c9e713a62d67662eDan Gohman struct RewriteInfo { 1311844731a7f1909f55935e3514c9e713a62d67662eDan Gohman unsigned Index; 1312844731a7f1909f55935e3514c9e713a62d67662eDan Gohman MachineInstr *MI; 1313844731a7f1909f55935e3514c9e713a62d67662eDan Gohman bool HasUse; 1314844731a7f1909f55935e3514c9e713a62d67662eDan Gohman bool HasDef; 1315844731a7f1909f55935e3514c9e713a62d67662eDan Gohman RewriteInfo(unsigned i, MachineInstr *mi, bool u, bool d) 1316844731a7f1909f55935e3514c9e713a62d67662eDan Gohman : Index(i), MI(mi), HasUse(u), HasDef(d) {} 1317844731a7f1909f55935e3514c9e713a62d67662eDan Gohman }; 1318844731a7f1909f55935e3514c9e713a62d67662eDan Gohman 1319844731a7f1909f55935e3514c9e713a62d67662eDan Gohman struct RewriteInfoCompare { 1320844731a7f1909f55935e3514c9e713a62d67662eDan Gohman bool operator()(const RewriteInfo &LHS, const RewriteInfo &RHS) const { 1321844731a7f1909f55935e3514c9e713a62d67662eDan Gohman return LHS.Index < RHS.Index; 1322844731a7f1909f55935e3514c9e713a62d67662eDan Gohman } 1323844731a7f1909f55935e3514c9e713a62d67662eDan Gohman }; 1324844731a7f1909f55935e3514c9e713a62d67662eDan Gohman} 1325063284c001666c0a3906acbe0a26dc7cae5f081cEvan Cheng 1326f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Chengvoid LiveIntervals:: 132781a038218171860ee4c382849c647d3dc841fe8bEvan ChengrewriteInstructionsForSpills(const LiveInterval &li, bool TrySplit, 1328f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng LiveInterval::Ranges::const_iterator &I, 132981a038218171860ee4c382849c647d3dc841fe8bEvan Cheng MachineInstr *ReMatOrigDefMI, MachineInstr *ReMatDefMI, 1330f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng unsigned Slot, int LdSlot, 1331f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng bool isLoad, bool isLoadSS, bool DefIsReMat, bool CanDelete, 1332d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng VirtRegMap &vrm, 1333f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng const TargetRegisterClass* rc, 1334f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng SmallVector<int, 4> &ReMatIds, 133522f07ffd27d1d721634d502c37267721d2e025cfEvan Cheng const MachineLoopInfo *loopInfo, 133681a038218171860ee4c382849c647d3dc841fe8bEvan Cheng BitVector &SpillMBBs, 1337289983123ba4170c8a27e9638935818f8142bc89Owen Anderson DenseMap<unsigned, std::vector<SRInfo> > &SpillIdxes, 13380cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng BitVector &RestoreMBBs, 1339289983123ba4170c8a27e9638935818f8142bc89Owen Anderson DenseMap<unsigned, std::vector<SRInfo> > &RestoreIdxes, 1340289983123ba4170c8a27e9638935818f8142bc89Owen Anderson DenseMap<unsigned,unsigned> &MBBVRegsMap, 13419c3c2213647e3f1b71722d61875ebac01b65cb91Evan Cheng std::vector<LiveInterval*> &NewLIs, float &SSWeight) { 1342018f9b020bb12b731b0a7081578e5f82fb35092dEvan Cheng bool AllCanFold = true; 134381a038218171860ee4c382849c647d3dc841fe8bEvan Cheng unsigned NewVReg = 0; 1344063284c001666c0a3906acbe0a26dc7cae5f081cEvan Cheng unsigned start = getBaseIndex(I->start); 1345f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng unsigned end = getBaseIndex(I->end-1) + InstrSlots::NUM; 1346f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng 1347063284c001666c0a3906acbe0a26dc7cae5f081cEvan Cheng // First collect all the def / use in this live range that will be rewritten. 13487e073baedb8232b9519dbe15ea141ff98ccfe6aeEvan Cheng // Make sure they are sorted according to instruction index. 1349063284c001666c0a3906acbe0a26dc7cae5f081cEvan Cheng std::vector<RewriteInfo> RewriteMIs; 1350d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng for (MachineRegisterInfo::reg_iterator ri = mri_->reg_begin(li.reg), 1351d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng re = mri_->reg_end(); ri != re; ) { 1352419852ca8a01aecde4c0e20af6b7bd6450e70f87Evan Cheng MachineInstr *MI = &*ri; 1353063284c001666c0a3906acbe0a26dc7cae5f081cEvan Cheng MachineOperand &O = ri.getOperand(); 1354063284c001666c0a3906acbe0a26dc7cae5f081cEvan Cheng ++ri; 135524d2f8a212f08bf21360122cc00acf2657af91f9Evan Cheng assert(!O.isImplicit() && "Spilling register that's used as implicit use?"); 1356063284c001666c0a3906acbe0a26dc7cae5f081cEvan Cheng unsigned index = getInstructionIndex(MI); 1357063284c001666c0a3906acbe0a26dc7cae5f081cEvan Cheng if (index < start || index >= end) 1358063284c001666c0a3906acbe0a26dc7cae5f081cEvan Cheng continue; 135979a796c2b17c7ebd4dd489b5de1078fc2148adbaEvan Cheng if (O.isUse() && !li.liveAt(getUseIndex(index))) 136079a796c2b17c7ebd4dd489b5de1078fc2148adbaEvan Cheng // Must be defined by an implicit def. It should not be spilled. Note, 136179a796c2b17c7ebd4dd489b5de1078fc2148adbaEvan Cheng // this is for correctness reason. e.g. 136279a796c2b17c7ebd4dd489b5de1078fc2148adbaEvan Cheng // 8 %reg1024<def> = IMPLICIT_DEF 136379a796c2b17c7ebd4dd489b5de1078fc2148adbaEvan Cheng // 12 %reg1024<def> = INSERT_SUBREG %reg1024<kill>, %reg1025, 2 136479a796c2b17c7ebd4dd489b5de1078fc2148adbaEvan Cheng // The live range [12, 14) are not part of the r1024 live interval since 136579a796c2b17c7ebd4dd489b5de1078fc2148adbaEvan Cheng // it's defined by an implicit def. It will not conflicts with live 136679a796c2b17c7ebd4dd489b5de1078fc2148adbaEvan Cheng // interval of r1025. Now suppose both registers are spilled, you can 1367b9890ae3c35ad7d8e49261650d5b98f49f97a705Evan Cheng // easily see a situation where both registers are reloaded before 136879a796c2b17c7ebd4dd489b5de1078fc2148adbaEvan Cheng // the INSERT_SUBREG and both target registers that would overlap. 136979a796c2b17c7ebd4dd489b5de1078fc2148adbaEvan Cheng continue; 1370063284c001666c0a3906acbe0a26dc7cae5f081cEvan Cheng RewriteMIs.push_back(RewriteInfo(index, MI, O.isUse(), O.isDef())); 1371063284c001666c0a3906acbe0a26dc7cae5f081cEvan Cheng } 1372063284c001666c0a3906acbe0a26dc7cae5f081cEvan Cheng std::sort(RewriteMIs.begin(), RewriteMIs.end(), RewriteInfoCompare()); 1373063284c001666c0a3906acbe0a26dc7cae5f081cEvan Cheng 1374313d4b809326f3e04814f94e5b8ae05649d8e0f6Evan Cheng unsigned ImpUse = DefIsReMat ? getReMatImplicitUse(li, ReMatDefMI) : 0; 1375063284c001666c0a3906acbe0a26dc7cae5f081cEvan Cheng // Now rewrite the defs and uses. 1376063284c001666c0a3906acbe0a26dc7cae5f081cEvan Cheng for (unsigned i = 0, e = RewriteMIs.size(); i != e; ) { 1377063284c001666c0a3906acbe0a26dc7cae5f081cEvan Cheng RewriteInfo &rwi = RewriteMIs[i]; 1378063284c001666c0a3906acbe0a26dc7cae5f081cEvan Cheng ++i; 1379063284c001666c0a3906acbe0a26dc7cae5f081cEvan Cheng unsigned index = rwi.Index; 1380063284c001666c0a3906acbe0a26dc7cae5f081cEvan Cheng bool MIHasUse = rwi.HasUse; 1381063284c001666c0a3906acbe0a26dc7cae5f081cEvan Cheng bool MIHasDef = rwi.HasDef; 1382063284c001666c0a3906acbe0a26dc7cae5f081cEvan Cheng MachineInstr *MI = rwi.MI; 1383063284c001666c0a3906acbe0a26dc7cae5f081cEvan Cheng // If MI def and/or use the same register multiple times, then there 1384063284c001666c0a3906acbe0a26dc7cae5f081cEvan Cheng // are multiple entries. 1385313d4b809326f3e04814f94e5b8ae05649d8e0f6Evan Cheng unsigned NumUses = MIHasUse; 1386063284c001666c0a3906acbe0a26dc7cae5f081cEvan Cheng while (i != e && RewriteMIs[i].MI == MI) { 1387063284c001666c0a3906acbe0a26dc7cae5f081cEvan Cheng assert(RewriteMIs[i].Index == index); 1388313d4b809326f3e04814f94e5b8ae05649d8e0f6Evan Cheng bool isUse = RewriteMIs[i].HasUse; 1389313d4b809326f3e04814f94e5b8ae05649d8e0f6Evan Cheng if (isUse) ++NumUses; 1390313d4b809326f3e04814f94e5b8ae05649d8e0f6Evan Cheng MIHasUse |= isUse; 1391063284c001666c0a3906acbe0a26dc7cae5f081cEvan Cheng MIHasDef |= RewriteMIs[i].HasDef; 1392063284c001666c0a3906acbe0a26dc7cae5f081cEvan Cheng ++i; 1393063284c001666c0a3906acbe0a26dc7cae5f081cEvan Cheng } 139481a038218171860ee4c382849c647d3dc841fe8bEvan Cheng MachineBasicBlock *MBB = MI->getParent(); 1395313d4b809326f3e04814f94e5b8ae05649d8e0f6Evan Cheng 13960a891ed7d5875a9ccdb93b4472b0f43947d8289bEvan Cheng if (ImpUse && MI != ReMatDefMI) { 1397313d4b809326f3e04814f94e5b8ae05649d8e0f6Evan Cheng // Re-matting an instruction with virtual register use. Update the 139824d2f8a212f08bf21360122cc00acf2657af91f9Evan Cheng // register interval's spill weight to HUGE_VALF to prevent it from 139924d2f8a212f08bf21360122cc00acf2657af91f9Evan Cheng // being spilled. 1400313d4b809326f3e04814f94e5b8ae05649d8e0f6Evan Cheng LiveInterval &ImpLi = getInterval(ImpUse); 140124d2f8a212f08bf21360122cc00acf2657af91f9Evan Cheng ImpLi.weight = HUGE_VALF; 1402313d4b809326f3e04814f94e5b8ae05649d8e0f6Evan Cheng } 1403313d4b809326f3e04814f94e5b8ae05649d8e0f6Evan Cheng 1404063284c001666c0a3906acbe0a26dc7cae5f081cEvan Cheng unsigned MBBId = MBB->getNumber(); 1405018f9b020bb12b731b0a7081578e5f82fb35092dEvan Cheng unsigned ThisVReg = 0; 140670306f8348f27c61cfed5a60e2fceac0f29746a2Evan Cheng if (TrySplit) { 1407289983123ba4170c8a27e9638935818f8142bc89Owen Anderson DenseMap<unsigned,unsigned>::iterator NVI = MBBVRegsMap.find(MBBId); 14081953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng if (NVI != MBBVRegsMap.end()) { 1409018f9b020bb12b731b0a7081578e5f82fb35092dEvan Cheng ThisVReg = NVI->second; 14101953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng // One common case: 14111953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng // x = use 14121953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng // ... 14131953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng // ... 14141953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng // def = ... 14151953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng // = use 14161953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng // It's better to start a new interval to avoid artifically 14171953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng // extend the new interval. 14181953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng if (MIHasDef && !MIHasUse) { 14191953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng MBBVRegsMap.erase(MBB->getNumber()); 1420018f9b020bb12b731b0a7081578e5f82fb35092dEvan Cheng ThisVReg = 0; 14211953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng } 14221953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng } 1423cada245d06959831b90f8c29f92e77beda4b71cbEvan Cheng } 1424018f9b020bb12b731b0a7081578e5f82fb35092dEvan Cheng 1425018f9b020bb12b731b0a7081578e5f82fb35092dEvan Cheng bool IsNew = ThisVReg == 0; 1426018f9b020bb12b731b0a7081578e5f82fb35092dEvan Cheng if (IsNew) { 1427018f9b020bb12b731b0a7081578e5f82fb35092dEvan Cheng // This ends the previous live interval. If all of its def / use 1428018f9b020bb12b731b0a7081578e5f82fb35092dEvan Cheng // can be folded, give it a low spill weight. 1429018f9b020bb12b731b0a7081578e5f82fb35092dEvan Cheng if (NewVReg && TrySplit && AllCanFold) { 1430018f9b020bb12b731b0a7081578e5f82fb35092dEvan Cheng LiveInterval &nI = getOrCreateInterval(NewVReg); 1431018f9b020bb12b731b0a7081578e5f82fb35092dEvan Cheng nI.weight /= 10.0F; 1432018f9b020bb12b731b0a7081578e5f82fb35092dEvan Cheng } 1433018f9b020bb12b731b0a7081578e5f82fb35092dEvan Cheng AllCanFold = true; 1434018f9b020bb12b731b0a7081578e5f82fb35092dEvan Cheng } 1435018f9b020bb12b731b0a7081578e5f82fb35092dEvan Cheng NewVReg = ThisVReg; 1436018f9b020bb12b731b0a7081578e5f82fb35092dEvan Cheng 143781a038218171860ee4c382849c647d3dc841fe8bEvan Cheng bool HasDef = false; 143881a038218171860ee4c382849c647d3dc841fe8bEvan Cheng bool HasUse = false; 1439d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng bool CanFold = rewriteInstructionForSpills(li, I->valno, TrySplit, 14409c3c2213647e3f1b71722d61875ebac01b65cb91Evan Cheng index, end, MI, ReMatOrigDefMI, ReMatDefMI, 14419c3c2213647e3f1b71722d61875ebac01b65cb91Evan Cheng Slot, LdSlot, isLoad, isLoadSS, DefIsReMat, 14429c3c2213647e3f1b71722d61875ebac01b65cb91Evan Cheng CanDelete, vrm, rc, ReMatIds, loopInfo, NewVReg, 14439c3c2213647e3f1b71722d61875ebac01b65cb91Evan Cheng ImpUse, HasDef, HasUse, MBBVRegsMap, NewLIs, SSWeight); 144481a038218171860ee4c382849c647d3dc841fe8bEvan Cheng if (!HasDef && !HasUse) 144581a038218171860ee4c382849c647d3dc841fe8bEvan Cheng continue; 144681a038218171860ee4c382849c647d3dc841fe8bEvan Cheng 1447018f9b020bb12b731b0a7081578e5f82fb35092dEvan Cheng AllCanFold &= CanFold; 1448018f9b020bb12b731b0a7081578e5f82fb35092dEvan Cheng 144981a038218171860ee4c382849c647d3dc841fe8bEvan Cheng // Update weight of spill interval. 145081a038218171860ee4c382849c647d3dc841fe8bEvan Cheng LiveInterval &nI = getOrCreateInterval(NewVReg); 145170306f8348f27c61cfed5a60e2fceac0f29746a2Evan Cheng if (!TrySplit) { 145281a038218171860ee4c382849c647d3dc841fe8bEvan Cheng // The spill weight is now infinity as it cannot be spilled again. 145381a038218171860ee4c382849c647d3dc841fe8bEvan Cheng nI.weight = HUGE_VALF; 14540cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng continue; 14550cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng } 14560cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng 14570cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng // Keep track of the last def and first use in each MBB. 14580cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng if (HasDef) { 14590cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng if (MI != ReMatOrigDefMI || !CanDelete) { 14600cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng bool HasKill = false; 14610cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng if (!HasUse) 14620cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng HasKill = anyKillInMBBAfterIdx(li, I->valno, MBB, getDefIndex(index)); 14630cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng else { 14641953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng // If this is a two-address code, then this index starts a new VNInfo. 14653f32d65912b4da23793dab618d981be2ce11c331Evan Cheng const VNInfo *VNI = li.findDefinedVNInfo(getDefIndex(index)); 14660cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng if (VNI) 14670cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng HasKill = anyKillInMBBAfterIdx(li, VNI, MBB, getDefIndex(index)); 146881a038218171860ee4c382849c647d3dc841fe8bEvan Cheng } 1469289983123ba4170c8a27e9638935818f8142bc89Owen Anderson DenseMap<unsigned, std::vector<SRInfo> >::iterator SII = 1470e3110d0825e6316fd2dd21d6a4e593295cd413f1Evan Cheng SpillIdxes.find(MBBId); 14710cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng if (!HasKill) { 14721953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng if (SII == SpillIdxes.end()) { 14731953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng std::vector<SRInfo> S; 14741953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng S.push_back(SRInfo(index, NewVReg, true)); 14751953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng SpillIdxes.insert(std::make_pair(MBBId, S)); 14761953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng } else if (SII->second.back().vreg != NewVReg) { 14771953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng SII->second.push_back(SRInfo(index, NewVReg, true)); 14781953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng } else if ((int)index > SII->second.back().index) { 14790cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng // If there is an earlier def and this is a two-address 14800cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng // instruction, then it's not possible to fold the store (which 14810cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng // would also fold the load). 14821953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng SRInfo &Info = SII->second.back(); 14831953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng Info.index = index; 14841953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng Info.canFold = !HasUse; 148581a038218171860ee4c382849c647d3dc841fe8bEvan Cheng } 14860cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng SpillMBBs.set(MBBId); 1487e3110d0825e6316fd2dd21d6a4e593295cd413f1Evan Cheng } else if (SII != SpillIdxes.end() && 1488e3110d0825e6316fd2dd21d6a4e593295cd413f1Evan Cheng SII->second.back().vreg == NewVReg && 1489e3110d0825e6316fd2dd21d6a4e593295cd413f1Evan Cheng (int)index > SII->second.back().index) { 1490e3110d0825e6316fd2dd21d6a4e593295cd413f1Evan Cheng // There is an earlier def that's not killed (must be two-address). 1491e3110d0825e6316fd2dd21d6a4e593295cd413f1Evan Cheng // The spill is no longer needed. 1492e3110d0825e6316fd2dd21d6a4e593295cd413f1Evan Cheng SII->second.pop_back(); 1493e3110d0825e6316fd2dd21d6a4e593295cd413f1Evan Cheng if (SII->second.empty()) { 1494e3110d0825e6316fd2dd21d6a4e593295cd413f1Evan Cheng SpillIdxes.erase(MBBId); 1495e3110d0825e6316fd2dd21d6a4e593295cd413f1Evan Cheng SpillMBBs.reset(MBBId); 1496e3110d0825e6316fd2dd21d6a4e593295cd413f1Evan Cheng } 149781a038218171860ee4c382849c647d3dc841fe8bEvan Cheng } 149881a038218171860ee4c382849c647d3dc841fe8bEvan Cheng } 14990cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng } 150081a038218171860ee4c382849c647d3dc841fe8bEvan Cheng 15010cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng if (HasUse) { 1502289983123ba4170c8a27e9638935818f8142bc89Owen Anderson DenseMap<unsigned, std::vector<SRInfo> >::iterator SII = 15030cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng SpillIdxes.find(MBBId); 15041953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng if (SII != SpillIdxes.end() && 15051953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng SII->second.back().vreg == NewVReg && 15061953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng (int)index > SII->second.back().index) 15070cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng // Use(s) following the last def, it's not safe to fold the spill. 15081953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng SII->second.back().canFold = false; 1509289983123ba4170c8a27e9638935818f8142bc89Owen Anderson DenseMap<unsigned, std::vector<SRInfo> >::iterator RII = 15100cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng RestoreIdxes.find(MBBId); 15111953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng if (RII != RestoreIdxes.end() && RII->second.back().vreg == NewVReg) 15120cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng // If we are splitting live intervals, only fold if it's the first 15130cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng // use and there isn't another use later in the MBB. 15141953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng RII->second.back().canFold = false; 15150cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng else if (IsNew) { 15160cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng // Only need a reload if there isn't an earlier def / use. 15171953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng if (RII == RestoreIdxes.end()) { 15181953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng std::vector<SRInfo> Infos; 15191953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng Infos.push_back(SRInfo(index, NewVReg, true)); 15201953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng RestoreIdxes.insert(std::make_pair(MBBId, Infos)); 15211953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng } else { 15221953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng RII->second.push_back(SRInfo(index, NewVReg, true)); 15231953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng } 15240cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng RestoreMBBs.set(MBBId); 15250cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng } 152681a038218171860ee4c382849c647d3dc841fe8bEvan Cheng } 15270cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng 15280cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng // Update spill weight. 152922f07ffd27d1d721634d502c37267721d2e025cfEvan Cheng unsigned loopDepth = loopInfo->getLoopDepth(MBB); 1530c3417609ae6e744a29be6962d4fb7811c0102d17Evan Cheng nI.weight += getSpillWeight(HasDef, HasUse, loopDepth); 1531f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng } 1532018f9b020bb12b731b0a7081578e5f82fb35092dEvan Cheng 1533018f9b020bb12b731b0a7081578e5f82fb35092dEvan Cheng if (NewVReg && TrySplit && AllCanFold) { 1534018f9b020bb12b731b0a7081578e5f82fb35092dEvan Cheng // If all of its def / use can be folded, give it a low spill weight. 1535018f9b020bb12b731b0a7081578e5f82fb35092dEvan Cheng LiveInterval &nI = getOrCreateInterval(NewVReg); 1536018f9b020bb12b731b0a7081578e5f82fb35092dEvan Cheng nI.weight /= 10.0F; 1537018f9b020bb12b731b0a7081578e5f82fb35092dEvan Cheng } 1538f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng} 1539f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng 15401953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Chengbool LiveIntervals::alsoFoldARestore(int Id, int index, unsigned vr, 15411953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng BitVector &RestoreMBBs, 1542289983123ba4170c8a27e9638935818f8142bc89Owen Anderson DenseMap<unsigned,std::vector<SRInfo> > &RestoreIdxes) { 15431953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng if (!RestoreMBBs[Id]) 15441953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng return false; 15451953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng std::vector<SRInfo> &Restores = RestoreIdxes[Id]; 15461953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng for (unsigned i = 0, e = Restores.size(); i != e; ++i) 15471953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng if (Restores[i].index == index && 15481953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng Restores[i].vreg == vr && 15491953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng Restores[i].canFold) 15501953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng return true; 15511953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng return false; 15521953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng} 15531953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng 15541953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Chengvoid LiveIntervals::eraseRestoreInfo(int Id, int index, unsigned vr, 15551953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng BitVector &RestoreMBBs, 1556289983123ba4170c8a27e9638935818f8142bc89Owen Anderson DenseMap<unsigned,std::vector<SRInfo> > &RestoreIdxes) { 15571953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng if (!RestoreMBBs[Id]) 15581953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng return; 15591953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng std::vector<SRInfo> &Restores = RestoreIdxes[Id]; 15601953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng for (unsigned i = 0, e = Restores.size(); i != e; ++i) 15611953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng if (Restores[i].index == index && Restores[i].vreg) 15621953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng Restores[i].index = -1; 15631953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng} 156481a038218171860ee4c382849c647d3dc841fe8bEvan Cheng 15654cce6b4c7882ef0cc993d931b90bf33985c96110Evan Cheng/// handleSpilledImpDefs - Remove IMPLICIT_DEF instructions which are being 15664cce6b4c7882ef0cc993d931b90bf33985c96110Evan Cheng/// spilled and create empty intervals for their uses. 15674cce6b4c7882ef0cc993d931b90bf33985c96110Evan Chengvoid 15684cce6b4c7882ef0cc993d931b90bf33985c96110Evan ChengLiveIntervals::handleSpilledImpDefs(const LiveInterval &li, VirtRegMap &vrm, 15694cce6b4c7882ef0cc993d931b90bf33985c96110Evan Cheng const TargetRegisterClass* rc, 15704cce6b4c7882ef0cc993d931b90bf33985c96110Evan Cheng std::vector<LiveInterval*> &NewLIs) { 1571419852ca8a01aecde4c0e20af6b7bd6450e70f87Evan Cheng for (MachineRegisterInfo::reg_iterator ri = mri_->reg_begin(li.reg), 1572419852ca8a01aecde4c0e20af6b7bd6450e70f87Evan Cheng re = mri_->reg_end(); ri != re; ) { 15734cce6b4c7882ef0cc993d931b90bf33985c96110Evan Cheng MachineOperand &O = ri.getOperand(); 1574419852ca8a01aecde4c0e20af6b7bd6450e70f87Evan Cheng MachineInstr *MI = &*ri; 1575419852ca8a01aecde4c0e20af6b7bd6450e70f87Evan Cheng ++ri; 15764cce6b4c7882ef0cc993d931b90bf33985c96110Evan Cheng if (O.isDef()) { 15774cce6b4c7882ef0cc993d931b90bf33985c96110Evan Cheng assert(MI->getOpcode() == TargetInstrInfo::IMPLICIT_DEF && 15784cce6b4c7882ef0cc993d931b90bf33985c96110Evan Cheng "Register def was not rewritten?"); 15794cce6b4c7882ef0cc993d931b90bf33985c96110Evan Cheng RemoveMachineInstrFromMaps(MI); 15804cce6b4c7882ef0cc993d931b90bf33985c96110Evan Cheng vrm.RemoveMachineInstrFromMaps(MI); 15814cce6b4c7882ef0cc993d931b90bf33985c96110Evan Cheng MI->eraseFromParent(); 15824cce6b4c7882ef0cc993d931b90bf33985c96110Evan Cheng } else { 15834cce6b4c7882ef0cc993d931b90bf33985c96110Evan Cheng // This must be an use of an implicit_def so it's not part of the live 15844cce6b4c7882ef0cc993d931b90bf33985c96110Evan Cheng // interval. Create a new empty live interval for it. 15854cce6b4c7882ef0cc993d931b90bf33985c96110Evan Cheng // FIXME: Can we simply erase some of the instructions? e.g. Stores? 15864cce6b4c7882ef0cc993d931b90bf33985c96110Evan Cheng unsigned NewVReg = mri_->createVirtualRegister(rc); 15874cce6b4c7882ef0cc993d931b90bf33985c96110Evan Cheng vrm.grow(); 15884cce6b4c7882ef0cc993d931b90bf33985c96110Evan Cheng vrm.setIsImplicitlyDefined(NewVReg); 15894cce6b4c7882ef0cc993d931b90bf33985c96110Evan Cheng NewLIs.push_back(&getOrCreateInterval(NewVReg)); 15904cce6b4c7882ef0cc993d931b90bf33985c96110Evan Cheng for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) { 15914cce6b4c7882ef0cc993d931b90bf33985c96110Evan Cheng MachineOperand &MO = MI->getOperand(i); 15924cce6b4c7882ef0cc993d931b90bf33985c96110Evan Cheng if (MO.isReg() && MO.getReg() == li.reg) 15934cce6b4c7882ef0cc993d931b90bf33985c96110Evan Cheng MO.setReg(NewVReg); 15944cce6b4c7882ef0cc993d931b90bf33985c96110Evan Cheng } 15954cce6b4c7882ef0cc993d931b90bf33985c96110Evan Cheng } 1596419852ca8a01aecde4c0e20af6b7bd6450e70f87Evan Cheng } 1597419852ca8a01aecde4c0e20af6b7bd6450e70f87Evan Cheng} 1598419852ca8a01aecde4c0e20af6b7bd6450e70f87Evan Cheng 159981a038218171860ee4c382849c647d3dc841fe8bEvan Cheng 1600f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Chengstd::vector<LiveInterval*> LiveIntervals:: 1601d6664311acbd05a8a710ccea8f9f5fdbfa35f834Owen AndersonaddIntervalsForSpillsFast(const LiveInterval &li, 1602d6664311acbd05a8a710ccea8f9f5fdbfa35f834Owen Anderson const MachineLoopInfo *loopInfo, 1603d6664311acbd05a8a710ccea8f9f5fdbfa35f834Owen Anderson VirtRegMap &vrm, float& SSWeight) { 1604d6664311acbd05a8a710ccea8f9f5fdbfa35f834Owen Anderson unsigned slot = vrm.assignVirt2StackSlot(li.reg); 1605d6664311acbd05a8a710ccea8f9f5fdbfa35f834Owen Anderson 1606d6664311acbd05a8a710ccea8f9f5fdbfa35f834Owen Anderson // since this is called after the analysis is done we don't know if 1607d6664311acbd05a8a710ccea8f9f5fdbfa35f834Owen Anderson // LiveVariables is available 1608d6664311acbd05a8a710ccea8f9f5fdbfa35f834Owen Anderson lv_ = getAnalysisToUpdate<LiveVariables>(); 1609d6664311acbd05a8a710ccea8f9f5fdbfa35f834Owen Anderson 1610d6664311acbd05a8a710ccea8f9f5fdbfa35f834Owen Anderson std::vector<LiveInterval*> added; 1611d6664311acbd05a8a710ccea8f9f5fdbfa35f834Owen Anderson 1612d6664311acbd05a8a710ccea8f9f5fdbfa35f834Owen Anderson assert(li.weight != HUGE_VALF && 1613d6664311acbd05a8a710ccea8f9f5fdbfa35f834Owen Anderson "attempt to spill already spilled interval!"); 1614d6664311acbd05a8a710ccea8f9f5fdbfa35f834Owen Anderson 1615d6664311acbd05a8a710ccea8f9f5fdbfa35f834Owen Anderson DOUT << "\t\t\t\tadding intervals for spills for interval: "; 1616d6664311acbd05a8a710ccea8f9f5fdbfa35f834Owen Anderson DEBUG(li.dump()); 1617d6664311acbd05a8a710ccea8f9f5fdbfa35f834Owen Anderson DOUT << '\n'; 1618d6664311acbd05a8a710ccea8f9f5fdbfa35f834Owen Anderson 1619d6664311acbd05a8a710ccea8f9f5fdbfa35f834Owen Anderson const TargetRegisterClass* rc = mri_->getRegClass(li.reg); 1620d6664311acbd05a8a710ccea8f9f5fdbfa35f834Owen Anderson 1621d6664311acbd05a8a710ccea8f9f5fdbfa35f834Owen Anderson for (LiveInterval::Ranges::const_iterator 1622d6664311acbd05a8a710ccea8f9f5fdbfa35f834Owen Anderson i = li.ranges.begin(), e = li.ranges.end(); i != e; ++i) { 1623d6664311acbd05a8a710ccea8f9f5fdbfa35f834Owen Anderson unsigned index = getBaseIndex(i->start); 1624d6664311acbd05a8a710ccea8f9f5fdbfa35f834Owen Anderson unsigned end = getBaseIndex(i->end-1) + InstrSlots::NUM; 1625d6664311acbd05a8a710ccea8f9f5fdbfa35f834Owen Anderson for (; index != end; index += InstrSlots::NUM) { 1626d6664311acbd05a8a710ccea8f9f5fdbfa35f834Owen Anderson // skip deleted instructions 1627d6664311acbd05a8a710ccea8f9f5fdbfa35f834Owen Anderson while (index != end && !getInstructionFromIndex(index)) 1628d6664311acbd05a8a710ccea8f9f5fdbfa35f834Owen Anderson index += InstrSlots::NUM; 1629d6664311acbd05a8a710ccea8f9f5fdbfa35f834Owen Anderson if (index == end) break; 1630d6664311acbd05a8a710ccea8f9f5fdbfa35f834Owen Anderson 1631d6664311acbd05a8a710ccea8f9f5fdbfa35f834Owen Anderson MachineInstr *MI = getInstructionFromIndex(index); 1632d6664311acbd05a8a710ccea8f9f5fdbfa35f834Owen Anderson 1633d6664311acbd05a8a710ccea8f9f5fdbfa35f834Owen Anderson for (unsigned i = 0; i != MI->getNumOperands(); ++i) { 1634d6664311acbd05a8a710ccea8f9f5fdbfa35f834Owen Anderson MachineOperand& mop = MI->getOperand(i); 1635d6664311acbd05a8a710ccea8f9f5fdbfa35f834Owen Anderson if (mop.isRegister() && mop.getReg() == li.reg) { 1636d6664311acbd05a8a710ccea8f9f5fdbfa35f834Owen Anderson // Create a new virtual register for the spill interval. 1637d6664311acbd05a8a710ccea8f9f5fdbfa35f834Owen Anderson unsigned NewVReg = mri_->createVirtualRegister(rc); 1638d6664311acbd05a8a710ccea8f9f5fdbfa35f834Owen Anderson 1639d6664311acbd05a8a710ccea8f9f5fdbfa35f834Owen Anderson // Scan all of the operands of this instruction rewriting operands 1640d6664311acbd05a8a710ccea8f9f5fdbfa35f834Owen Anderson // to use NewVReg instead of li.reg as appropriate. We do this for 1641d6664311acbd05a8a710ccea8f9f5fdbfa35f834Owen Anderson // two reasons: 1642d6664311acbd05a8a710ccea8f9f5fdbfa35f834Owen Anderson // 1643d6664311acbd05a8a710ccea8f9f5fdbfa35f834Owen Anderson // 1. If the instr reads the same spilled vreg multiple times, we 1644d6664311acbd05a8a710ccea8f9f5fdbfa35f834Owen Anderson // want to reuse the NewVReg. 1645d6664311acbd05a8a710ccea8f9f5fdbfa35f834Owen Anderson // 2. If the instr is a two-addr instruction, we are required to 1646d6664311acbd05a8a710ccea8f9f5fdbfa35f834Owen Anderson // keep the src/dst regs pinned. 1647d6664311acbd05a8a710ccea8f9f5fdbfa35f834Owen Anderson // 1648d6664311acbd05a8a710ccea8f9f5fdbfa35f834Owen Anderson // Keep track of whether we replace a use and/or def so that we can 1649d6664311acbd05a8a710ccea8f9f5fdbfa35f834Owen Anderson // create the spill interval with the appropriate range. 1650d6664311acbd05a8a710ccea8f9f5fdbfa35f834Owen Anderson mop.setReg(NewVReg); 1651d6664311acbd05a8a710ccea8f9f5fdbfa35f834Owen Anderson 1652d6664311acbd05a8a710ccea8f9f5fdbfa35f834Owen Anderson bool HasUse = mop.isUse(); 1653d6664311acbd05a8a710ccea8f9f5fdbfa35f834Owen Anderson bool HasDef = mop.isDef(); 1654d6664311acbd05a8a710ccea8f9f5fdbfa35f834Owen Anderson for (unsigned j = i+1, e = MI->getNumOperands(); j != e; ++j) { 1655d6664311acbd05a8a710ccea8f9f5fdbfa35f834Owen Anderson if (MI->getOperand(j).isReg() && 1656d6664311acbd05a8a710ccea8f9f5fdbfa35f834Owen Anderson MI->getOperand(j).getReg() == li.reg) { 1657d6664311acbd05a8a710ccea8f9f5fdbfa35f834Owen Anderson MI->getOperand(j).setReg(NewVReg); 1658d6664311acbd05a8a710ccea8f9f5fdbfa35f834Owen Anderson HasUse |= MI->getOperand(j).isUse(); 1659d6664311acbd05a8a710ccea8f9f5fdbfa35f834Owen Anderson HasDef |= MI->getOperand(j).isDef(); 1660d6664311acbd05a8a710ccea8f9f5fdbfa35f834Owen Anderson } 1661d6664311acbd05a8a710ccea8f9f5fdbfa35f834Owen Anderson } 1662d6664311acbd05a8a710ccea8f9f5fdbfa35f834Owen Anderson 1663d6664311acbd05a8a710ccea8f9f5fdbfa35f834Owen Anderson // create a new register for this spill 1664d6664311acbd05a8a710ccea8f9f5fdbfa35f834Owen Anderson vrm.grow(); 1665d6664311acbd05a8a710ccea8f9f5fdbfa35f834Owen Anderson vrm.assignVirt2StackSlot(NewVReg, slot); 1666d6664311acbd05a8a710ccea8f9f5fdbfa35f834Owen Anderson LiveInterval &nI = getOrCreateInterval(NewVReg); 1667d6664311acbd05a8a710ccea8f9f5fdbfa35f834Owen Anderson assert(nI.empty()); 1668d6664311acbd05a8a710ccea8f9f5fdbfa35f834Owen Anderson 1669d6664311acbd05a8a710ccea8f9f5fdbfa35f834Owen Anderson // the spill weight is now infinity as it 1670d6664311acbd05a8a710ccea8f9f5fdbfa35f834Owen Anderson // cannot be spilled again 1671d6664311acbd05a8a710ccea8f9f5fdbfa35f834Owen Anderson nI.weight = HUGE_VALF; 1672d6664311acbd05a8a710ccea8f9f5fdbfa35f834Owen Anderson 1673d6664311acbd05a8a710ccea8f9f5fdbfa35f834Owen Anderson if (HasUse) { 1674d6664311acbd05a8a710ccea8f9f5fdbfa35f834Owen Anderson LiveRange LR(getLoadIndex(index), getUseIndex(index), 1675d6664311acbd05a8a710ccea8f9f5fdbfa35f834Owen Anderson nI.getNextValue(~0U, 0, getVNInfoAllocator())); 1676d6664311acbd05a8a710ccea8f9f5fdbfa35f834Owen Anderson DOUT << " +" << LR; 1677d6664311acbd05a8a710ccea8f9f5fdbfa35f834Owen Anderson nI.addRange(LR); 1678d6664311acbd05a8a710ccea8f9f5fdbfa35f834Owen Anderson } 1679d6664311acbd05a8a710ccea8f9f5fdbfa35f834Owen Anderson if (HasDef) { 1680d6664311acbd05a8a710ccea8f9f5fdbfa35f834Owen Anderson LiveRange LR(getDefIndex(index), getStoreIndex(index), 1681d6664311acbd05a8a710ccea8f9f5fdbfa35f834Owen Anderson nI.getNextValue(~0U, 0, getVNInfoAllocator())); 1682d6664311acbd05a8a710ccea8f9f5fdbfa35f834Owen Anderson DOUT << " +" << LR; 1683d6664311acbd05a8a710ccea8f9f5fdbfa35f834Owen Anderson nI.addRange(LR); 1684d6664311acbd05a8a710ccea8f9f5fdbfa35f834Owen Anderson } 1685d6664311acbd05a8a710ccea8f9f5fdbfa35f834Owen Anderson 1686d6664311acbd05a8a710ccea8f9f5fdbfa35f834Owen Anderson added.push_back(&nI); 1687d6664311acbd05a8a710ccea8f9f5fdbfa35f834Owen Anderson 1688d6664311acbd05a8a710ccea8f9f5fdbfa35f834Owen Anderson // update live variables if it is available 1689d6664311acbd05a8a710ccea8f9f5fdbfa35f834Owen Anderson if (lv_) 1690d6664311acbd05a8a710ccea8f9f5fdbfa35f834Owen Anderson lv_->addVirtualRegisterKilled(NewVReg, MI); 1691d6664311acbd05a8a710ccea8f9f5fdbfa35f834Owen Anderson 1692d6664311acbd05a8a710ccea8f9f5fdbfa35f834Owen Anderson DOUT << "\t\t\t\tadded new interval: "; 1693d6664311acbd05a8a710ccea8f9f5fdbfa35f834Owen Anderson DEBUG(nI.dump()); 1694d6664311acbd05a8a710ccea8f9f5fdbfa35f834Owen Anderson DOUT << '\n'; 1695d6664311acbd05a8a710ccea8f9f5fdbfa35f834Owen Anderson } 1696d6664311acbd05a8a710ccea8f9f5fdbfa35f834Owen Anderson } 1697d6664311acbd05a8a710ccea8f9f5fdbfa35f834Owen Anderson } 1698d6664311acbd05a8a710ccea8f9f5fdbfa35f834Owen Anderson } 1699d6664311acbd05a8a710ccea8f9f5fdbfa35f834Owen Anderson 1700d6664311acbd05a8a710ccea8f9f5fdbfa35f834Owen Anderson SSWeight = HUGE_VALF; 1701d6664311acbd05a8a710ccea8f9f5fdbfa35f834Owen Anderson 1702d6664311acbd05a8a710ccea8f9f5fdbfa35f834Owen Anderson return added; 1703d6664311acbd05a8a710ccea8f9f5fdbfa35f834Owen Anderson} 1704d6664311acbd05a8a710ccea8f9f5fdbfa35f834Owen Anderson 1705d6664311acbd05a8a710ccea8f9f5fdbfa35f834Owen Andersonstd::vector<LiveInterval*> LiveIntervals:: 170681a038218171860ee4c382849c647d3dc841fe8bEvan ChengaddIntervalsForSpills(const LiveInterval &li, 17079c3c2213647e3f1b71722d61875ebac01b65cb91Evan Cheng const MachineLoopInfo *loopInfo, VirtRegMap &vrm, 17089c3c2213647e3f1b71722d61875ebac01b65cb91Evan Cheng float &SSWeight) { 1709f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng assert(li.weight != HUGE_VALF && 1710f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng "attempt to spill already spilled interval!"); 1711f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng 1712f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng DOUT << "\t\t\t\tadding intervals for spills for interval: "; 17136f0d024a534af18d9e60b3ea757376cd8a3a980eDan Gohman li.print(DOUT, tri_); 1714f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng DOUT << '\n'; 1715f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng 17169c3c2213647e3f1b71722d61875ebac01b65cb91Evan Cheng // Spill slot weight. 17179c3c2213647e3f1b71722d61875ebac01b65cb91Evan Cheng SSWeight = 0.0f; 17189c3c2213647e3f1b71722d61875ebac01b65cb91Evan Cheng 171981a038218171860ee4c382849c647d3dc841fe8bEvan Cheng // Each bit specify whether it a spill is required in the MBB. 172081a038218171860ee4c382849c647d3dc841fe8bEvan Cheng BitVector SpillMBBs(mf_->getNumBlockIDs()); 1721289983123ba4170c8a27e9638935818f8142bc89Owen Anderson DenseMap<unsigned, std::vector<SRInfo> > SpillIdxes; 17220cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng BitVector RestoreMBBs(mf_->getNumBlockIDs()); 1723289983123ba4170c8a27e9638935818f8142bc89Owen Anderson DenseMap<unsigned, std::vector<SRInfo> > RestoreIdxes; 1724289983123ba4170c8a27e9638935818f8142bc89Owen Anderson DenseMap<unsigned,unsigned> MBBVRegsMap; 1725f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng std::vector<LiveInterval*> NewLIs; 1726d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng const TargetRegisterClass* rc = mri_->getRegClass(li.reg); 1727f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng 1728f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng unsigned NumValNums = li.getNumValNums(); 1729f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng SmallVector<MachineInstr*, 4> ReMatDefs; 1730f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng ReMatDefs.resize(NumValNums, NULL); 1731f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng SmallVector<MachineInstr*, 4> ReMatOrigDefs; 1732f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng ReMatOrigDefs.resize(NumValNums, NULL); 1733f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng SmallVector<int, 4> ReMatIds; 1734f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng ReMatIds.resize(NumValNums, VirtRegMap::MAX_STACK_SLOT); 1735f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng BitVector ReMatDelete(NumValNums); 1736f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng unsigned Slot = VirtRegMap::MAX_STACK_SLOT; 1737f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng 173881a038218171860ee4c382849c647d3dc841fe8bEvan Cheng // Spilling a split live interval. It cannot be split any further. Also, 173981a038218171860ee4c382849c647d3dc841fe8bEvan Cheng // it's also guaranteed to be a single val# / range interval. 174081a038218171860ee4c382849c647d3dc841fe8bEvan Cheng if (vrm.getPreSplitReg(li.reg)) { 174181a038218171860ee4c382849c647d3dc841fe8bEvan Cheng vrm.setIsSplitFromReg(li.reg, 0); 1742d120ffd26f2715c600b028d4eac9a3c41a9f4653Evan Cheng // Unset the split kill marker on the last use. 1743d120ffd26f2715c600b028d4eac9a3c41a9f4653Evan Cheng unsigned KillIdx = vrm.getKillPoint(li.reg); 1744d120ffd26f2715c600b028d4eac9a3c41a9f4653Evan Cheng if (KillIdx) { 1745d120ffd26f2715c600b028d4eac9a3c41a9f4653Evan Cheng MachineInstr *KillMI = getInstructionFromIndex(KillIdx); 1746d120ffd26f2715c600b028d4eac9a3c41a9f4653Evan Cheng assert(KillMI && "Last use disappeared?"); 1747d120ffd26f2715c600b028d4eac9a3c41a9f4653Evan Cheng int KillOp = KillMI->findRegisterUseOperandIdx(li.reg, true); 1748d120ffd26f2715c600b028d4eac9a3c41a9f4653Evan Cheng assert(KillOp != -1 && "Last use disappeared?"); 1749f73823000e2d5d6e1cf65bdf5a107297e18d35fbChris Lattner KillMI->getOperand(KillOp).setIsKill(false); 1750d120ffd26f2715c600b028d4eac9a3c41a9f4653Evan Cheng } 1751adf85906906ebf85c57c333e8209f37ef11a6c99Evan Cheng vrm.removeKillPoint(li.reg); 175281a038218171860ee4c382849c647d3dc841fe8bEvan Cheng bool DefIsReMat = vrm.isReMaterialized(li.reg); 175381a038218171860ee4c382849c647d3dc841fe8bEvan Cheng Slot = vrm.getStackSlot(li.reg); 175481a038218171860ee4c382849c647d3dc841fe8bEvan Cheng assert(Slot != VirtRegMap::MAX_STACK_SLOT); 175581a038218171860ee4c382849c647d3dc841fe8bEvan Cheng MachineInstr *ReMatDefMI = DefIsReMat ? 175681a038218171860ee4c382849c647d3dc841fe8bEvan Cheng vrm.getReMaterializedMI(li.reg) : NULL; 175781a038218171860ee4c382849c647d3dc841fe8bEvan Cheng int LdSlot = 0; 175881a038218171860ee4c382849c647d3dc841fe8bEvan Cheng bool isLoadSS = DefIsReMat && tii_->isLoadFromStackSlot(ReMatDefMI, LdSlot); 175981a038218171860ee4c382849c647d3dc841fe8bEvan Cheng bool isLoad = isLoadSS || 1760749c6f6b5ed301c84aac562e414486549d7b98ebChris Lattner (DefIsReMat && (ReMatDefMI->getDesc().isSimpleLoad())); 176181a038218171860ee4c382849c647d3dc841fe8bEvan Cheng bool IsFirstRange = true; 176281a038218171860ee4c382849c647d3dc841fe8bEvan Cheng for (LiveInterval::Ranges::const_iterator 176381a038218171860ee4c382849c647d3dc841fe8bEvan Cheng I = li.ranges.begin(), E = li.ranges.end(); I != E; ++I) { 176481a038218171860ee4c382849c647d3dc841fe8bEvan Cheng // If this is a split live interval with multiple ranges, it means there 176581a038218171860ee4c382849c647d3dc841fe8bEvan Cheng // are two-address instructions that re-defined the value. Only the 176681a038218171860ee4c382849c647d3dc841fe8bEvan Cheng // first def can be rematerialized! 176781a038218171860ee4c382849c647d3dc841fe8bEvan Cheng if (IsFirstRange) { 1768cb3c330d39442130d0587208d673ce9c33c7008fEvan Cheng // Note ReMatOrigDefMI has already been deleted. 176981a038218171860ee4c382849c647d3dc841fe8bEvan Cheng rewriteInstructionsForSpills(li, false, I, NULL, ReMatDefMI, 177081a038218171860ee4c382849c647d3dc841fe8bEvan Cheng Slot, LdSlot, isLoad, isLoadSS, DefIsReMat, 1771d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng false, vrm, rc, ReMatIds, loopInfo, 17720cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng SpillMBBs, SpillIdxes, RestoreMBBs, RestoreIdxes, 17739c3c2213647e3f1b71722d61875ebac01b65cb91Evan Cheng MBBVRegsMap, NewLIs, SSWeight); 177481a038218171860ee4c382849c647d3dc841fe8bEvan Cheng } else { 177581a038218171860ee4c382849c647d3dc841fe8bEvan Cheng rewriteInstructionsForSpills(li, false, I, NULL, 0, 177681a038218171860ee4c382849c647d3dc841fe8bEvan Cheng Slot, 0, false, false, false, 1777d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng false, vrm, rc, ReMatIds, loopInfo, 17780cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng SpillMBBs, SpillIdxes, RestoreMBBs, RestoreIdxes, 17799c3c2213647e3f1b71722d61875ebac01b65cb91Evan Cheng MBBVRegsMap, NewLIs, SSWeight); 178081a038218171860ee4c382849c647d3dc841fe8bEvan Cheng } 178181a038218171860ee4c382849c647d3dc841fe8bEvan Cheng IsFirstRange = false; 178281a038218171860ee4c382849c647d3dc841fe8bEvan Cheng } 1783419852ca8a01aecde4c0e20af6b7bd6450e70f87Evan Cheng 17849c3c2213647e3f1b71722d61875ebac01b65cb91Evan Cheng SSWeight = 0.0f; // Already accounted for when split. 17854cce6b4c7882ef0cc993d931b90bf33985c96110Evan Cheng handleSpilledImpDefs(li, vrm, rc, NewLIs); 178681a038218171860ee4c382849c647d3dc841fe8bEvan Cheng return NewLIs; 178781a038218171860ee4c382849c647d3dc841fe8bEvan Cheng } 178881a038218171860ee4c382849c647d3dc841fe8bEvan Cheng 178981a038218171860ee4c382849c647d3dc841fe8bEvan Cheng bool TrySplit = SplitAtBB && !intervalIsInOneMBB(li); 17900cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng if (SplitLimit != -1 && (int)numSplits >= SplitLimit) 17910cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng TrySplit = false; 17920cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng if (TrySplit) 17930cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng ++numSplits; 1794f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng bool NeedStackSlot = false; 1795f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng for (LiveInterval::const_vni_iterator i = li.vni_begin(), e = li.vni_end(); 1796f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng i != e; ++i) { 1797f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng const VNInfo *VNI = *i; 1798f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng unsigned VN = VNI->id; 1799f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng unsigned DefIdx = VNI->def; 1800f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng if (DefIdx == ~1U) 1801f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng continue; // Dead val#. 1802f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng // Is the def for the val# rematerializable? 180381a038218171860ee4c382849c647d3dc841fe8bEvan Cheng MachineInstr *ReMatDefMI = (DefIdx == ~0u) 180481a038218171860ee4c382849c647d3dc841fe8bEvan Cheng ? 0 : getInstructionFromIndex(DefIdx); 18055ef3a04b542c4e585276768fa9ca2af698ef5c87Evan Cheng bool dummy; 18065ef3a04b542c4e585276768fa9ca2af698ef5c87Evan Cheng if (ReMatDefMI && isReMaterializable(li, VNI, ReMatDefMI, dummy)) { 1807f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng // Remember how to remat the def of this val#. 180881a038218171860ee4c382849c647d3dc841fe8bEvan Cheng ReMatOrigDefs[VN] = ReMatDefMI; 18092c3f7ae3843bdc9dcfe85393e178211976c1f9bdDan Gohman // Original def may be modified so we have to make a copy here. 18101ed9922794cda9dbe295e74674b909287e544632Evan Cheng MachineInstr *Clone = mf_->CloneMachineInstr(ReMatDefMI); 18111ed9922794cda9dbe295e74674b909287e544632Evan Cheng ClonedMIs.push_back(Clone); 18121ed9922794cda9dbe295e74674b909287e544632Evan Cheng ReMatDefs[VN] = Clone; 1813f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng 1814f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng bool CanDelete = true; 1815c3fc7d9ec9b495c8a88cd854247105c296d3aabdEvan Cheng if (VNI->hasPHIKill) { 1816c3fc7d9ec9b495c8a88cd854247105c296d3aabdEvan Cheng // A kill is a phi node, not all of its uses can be rematerialized. 1817f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng // It must not be deleted. 1818c3fc7d9ec9b495c8a88cd854247105c296d3aabdEvan Cheng CanDelete = false; 1819c3fc7d9ec9b495c8a88cd854247105c296d3aabdEvan Cheng // Need a stack slot if there is any live range where uses cannot be 1820c3fc7d9ec9b495c8a88cd854247105c296d3aabdEvan Cheng // rematerialized. 1821c3fc7d9ec9b495c8a88cd854247105c296d3aabdEvan Cheng NeedStackSlot = true; 1822f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng } 1823f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng if (CanDelete) 1824f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng ReMatDelete.set(VN); 1825f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng } else { 1826f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng // Need a stack slot if there is any live range where uses cannot be 1827f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng // rematerialized. 1828f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng NeedStackSlot = true; 1829f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng } 1830f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng } 1831f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng 1832f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng // One stack slot per live interval. 183381a038218171860ee4c382849c647d3dc841fe8bEvan Cheng if (NeedStackSlot && vrm.getPreSplitReg(li.reg) == 0) 1834f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng Slot = vrm.assignVirt2StackSlot(li.reg); 1835f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng 1836f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng // Create new intervals and rewrite defs and uses. 1837f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng for (LiveInterval::Ranges::const_iterator 1838f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng I = li.ranges.begin(), E = li.ranges.end(); I != E; ++I) { 183981a038218171860ee4c382849c647d3dc841fe8bEvan Cheng MachineInstr *ReMatDefMI = ReMatDefs[I->valno->id]; 184081a038218171860ee4c382849c647d3dc841fe8bEvan Cheng MachineInstr *ReMatOrigDefMI = ReMatOrigDefs[I->valno->id]; 184181a038218171860ee4c382849c647d3dc841fe8bEvan Cheng bool DefIsReMat = ReMatDefMI != NULL; 1842f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng bool CanDelete = ReMatDelete[I->valno->id]; 1843f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng int LdSlot = 0; 184481a038218171860ee4c382849c647d3dc841fe8bEvan Cheng bool isLoadSS = DefIsReMat && tii_->isLoadFromStackSlot(ReMatDefMI, LdSlot); 1845f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng bool isLoad = isLoadSS || 1846749c6f6b5ed301c84aac562e414486549d7b98ebChris Lattner (DefIsReMat && ReMatDefMI->getDesc().isSimpleLoad()); 184781a038218171860ee4c382849c647d3dc841fe8bEvan Cheng rewriteInstructionsForSpills(li, TrySplit, I, ReMatOrigDefMI, ReMatDefMI, 18480cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng Slot, LdSlot, isLoad, isLoadSS, DefIsReMat, 1849d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng CanDelete, vrm, rc, ReMatIds, loopInfo, 18500cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng SpillMBBs, SpillIdxes, RestoreMBBs, RestoreIdxes, 18519c3c2213647e3f1b71722d61875ebac01b65cb91Evan Cheng MBBVRegsMap, NewLIs, SSWeight); 1852f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng } 1853f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng 18540cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng // Insert spills / restores if we are splitting. 1855419852ca8a01aecde4c0e20af6b7bd6450e70f87Evan Cheng if (!TrySplit) { 18564cce6b4c7882ef0cc993d931b90bf33985c96110Evan Cheng handleSpilledImpDefs(li, vrm, rc, NewLIs); 18571953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng return NewLIs; 1858419852ca8a01aecde4c0e20af6b7bd6450e70f87Evan Cheng } 18591953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng 1860b50bb8cf197709b3f49044740044c06d8f314564Evan Cheng SmallPtrSet<LiveInterval*, 4> AddedKill; 1861aee4af68ae2016afc5b4ec0c430e539c5810a766Evan Cheng SmallVector<unsigned, 2> Ops; 18621953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng if (NeedStackSlot) { 18631953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng int Id = SpillMBBs.find_first(); 18641953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng while (Id != -1) { 18659c3c2213647e3f1b71722d61875ebac01b65cb91Evan Cheng MachineBasicBlock *MBB = mf_->getBlockNumbered(Id); 18669c3c2213647e3f1b71722d61875ebac01b65cb91Evan Cheng unsigned loopDepth = loopInfo->getLoopDepth(MBB); 18671953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng std::vector<SRInfo> &spills = SpillIdxes[Id]; 18681953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng for (unsigned i = 0, e = spills.size(); i != e; ++i) { 18691953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng int index = spills[i].index; 18701953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng unsigned VReg = spills[i].vreg; 1871597d10d84fb6b34f7776121404d5ed802b21b2b6Evan Cheng LiveInterval &nI = getOrCreateInterval(VReg); 18720cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng bool isReMat = vrm.isReMaterialized(VReg); 18730cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng MachineInstr *MI = getInstructionFromIndex(index); 1874aee4af68ae2016afc5b4ec0c430e539c5810a766Evan Cheng bool CanFold = false; 1875aee4af68ae2016afc5b4ec0c430e539c5810a766Evan Cheng bool FoundUse = false; 1876aee4af68ae2016afc5b4ec0c430e539c5810a766Evan Cheng Ops.clear(); 1877cddbb83ea82e98658d9f530c50a7b9d23249afc2Evan Cheng if (spills[i].canFold) { 1878aee4af68ae2016afc5b4ec0c430e539c5810a766Evan Cheng CanFold = true; 18790cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng for (unsigned j = 0, ee = MI->getNumOperands(); j != ee; ++j) { 18800cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng MachineOperand &MO = MI->getOperand(j); 18810cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng if (!MO.isRegister() || MO.getReg() != VReg) 18820cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng continue; 1883aee4af68ae2016afc5b4ec0c430e539c5810a766Evan Cheng 1884aee4af68ae2016afc5b4ec0c430e539c5810a766Evan Cheng Ops.push_back(j); 1885aee4af68ae2016afc5b4ec0c430e539c5810a766Evan Cheng if (MO.isDef()) 1886cddbb83ea82e98658d9f530c50a7b9d23249afc2Evan Cheng continue; 1887aee4af68ae2016afc5b4ec0c430e539c5810a766Evan Cheng if (isReMat || 1888aee4af68ae2016afc5b4ec0c430e539c5810a766Evan Cheng (!FoundUse && !alsoFoldARestore(Id, index, VReg, 1889aee4af68ae2016afc5b4ec0c430e539c5810a766Evan Cheng RestoreMBBs, RestoreIdxes))) { 1890aee4af68ae2016afc5b4ec0c430e539c5810a766Evan Cheng // MI has two-address uses of the same register. If the use 1891aee4af68ae2016afc5b4ec0c430e539c5810a766Evan Cheng // isn't the first and only use in the BB, then we can't fold 1892aee4af68ae2016afc5b4ec0c430e539c5810a766Evan Cheng // it. FIXME: Move this to rewriteInstructionsForSpills. 1893aee4af68ae2016afc5b4ec0c430e539c5810a766Evan Cheng CanFold = false; 1894cddbb83ea82e98658d9f530c50a7b9d23249afc2Evan Cheng break; 1895cddbb83ea82e98658d9f530c50a7b9d23249afc2Evan Cheng } 1896aee4af68ae2016afc5b4ec0c430e539c5810a766Evan Cheng FoundUse = true; 18970cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng } 18980cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng } 18990cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng // Fold the store into the def if possible. 1900cddbb83ea82e98658d9f530c50a7b9d23249afc2Evan Cheng bool Folded = false; 1901aee4af68ae2016afc5b4ec0c430e539c5810a766Evan Cheng if (CanFold && !Ops.empty()) { 1902aee4af68ae2016afc5b4ec0c430e539c5810a766Evan Cheng if (tryFoldMemoryOperand(MI, vrm, NULL, index, Ops, true, Slot,VReg)){ 1903cddbb83ea82e98658d9f530c50a7b9d23249afc2Evan Cheng Folded = true; 1904f38d14f03e495ea98ae16bda6febbde276513294Evan Cheng if (FoundUse > 0) { 1905aee4af68ae2016afc5b4ec0c430e539c5810a766Evan Cheng // Also folded uses, do not issue a load. 1906aee4af68ae2016afc5b4ec0c430e539c5810a766Evan Cheng eraseRestoreInfo(Id, index, VReg, RestoreMBBs, RestoreIdxes); 1907f38d14f03e495ea98ae16bda6febbde276513294Evan Cheng nI.removeRange(getLoadIndex(index), getUseIndex(index)+1); 1908f38d14f03e495ea98ae16bda6febbde276513294Evan Cheng } 1909597d10d84fb6b34f7776121404d5ed802b21b2b6Evan Cheng nI.removeRange(getDefIndex(index), getStoreIndex(index)); 1910cddbb83ea82e98658d9f530c50a7b9d23249afc2Evan Cheng } 19110cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng } 19120cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng 19137e073baedb8232b9519dbe15ea141ff98ccfe6aeEvan Cheng // Otherwise tell the spiller to issue a spill. 1914b50bb8cf197709b3f49044740044c06d8f314564Evan Cheng if (!Folded) { 1915b50bb8cf197709b3f49044740044c06d8f314564Evan Cheng LiveRange *LR = &nI.ranges[nI.ranges.size()-1]; 1916b50bb8cf197709b3f49044740044c06d8f314564Evan Cheng bool isKill = LR->end == getStoreIndex(index); 1917b0a6f62c9b2e75fc509d84310a9795ffacbc6796Evan Cheng if (!MI->registerDefIsDead(nI.reg)) 1918b0a6f62c9b2e75fc509d84310a9795ffacbc6796Evan Cheng // No need to spill a dead def. 1919b0a6f62c9b2e75fc509d84310a9795ffacbc6796Evan Cheng vrm.addSpillPoint(VReg, isKill, MI); 1920b50bb8cf197709b3f49044740044c06d8f314564Evan Cheng if (isKill) 1921b50bb8cf197709b3f49044740044c06d8f314564Evan Cheng AddedKill.insert(&nI); 1922b50bb8cf197709b3f49044740044c06d8f314564Evan Cheng } 19239c3c2213647e3f1b71722d61875ebac01b65cb91Evan Cheng 19249c3c2213647e3f1b71722d61875ebac01b65cb91Evan Cheng // Update spill slot weight. 19259c3c2213647e3f1b71722d61875ebac01b65cb91Evan Cheng if (!isReMat) 1926c3417609ae6e744a29be6962d4fb7811c0102d17Evan Cheng SSWeight += getSpillWeight(true, false, loopDepth); 19270cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng } 19281953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng Id = SpillMBBs.find_next(Id); 19290cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng } 19301953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng } 19310cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng 19321953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng int Id = RestoreMBBs.find_first(); 19331953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng while (Id != -1) { 19349c3c2213647e3f1b71722d61875ebac01b65cb91Evan Cheng MachineBasicBlock *MBB = mf_->getBlockNumbered(Id); 19359c3c2213647e3f1b71722d61875ebac01b65cb91Evan Cheng unsigned loopDepth = loopInfo->getLoopDepth(MBB); 19369c3c2213647e3f1b71722d61875ebac01b65cb91Evan Cheng 19371953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng std::vector<SRInfo> &restores = RestoreIdxes[Id]; 19381953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng for (unsigned i = 0, e = restores.size(); i != e; ++i) { 19391953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng int index = restores[i].index; 19401953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng if (index == -1) 19411953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng continue; 19421953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng unsigned VReg = restores[i].vreg; 1943597d10d84fb6b34f7776121404d5ed802b21b2b6Evan Cheng LiveInterval &nI = getOrCreateInterval(VReg); 19449c3c2213647e3f1b71722d61875ebac01b65cb91Evan Cheng bool isReMat = vrm.isReMaterialized(VReg); 194581a038218171860ee4c382849c647d3dc841fe8bEvan Cheng MachineInstr *MI = getInstructionFromIndex(index); 1946aee4af68ae2016afc5b4ec0c430e539c5810a766Evan Cheng bool CanFold = false; 1947aee4af68ae2016afc5b4ec0c430e539c5810a766Evan Cheng Ops.clear(); 1948cddbb83ea82e98658d9f530c50a7b9d23249afc2Evan Cheng if (restores[i].canFold) { 1949aee4af68ae2016afc5b4ec0c430e539c5810a766Evan Cheng CanFold = true; 195081a038218171860ee4c382849c647d3dc841fe8bEvan Cheng for (unsigned j = 0, ee = MI->getNumOperands(); j != ee; ++j) { 195181a038218171860ee4c382849c647d3dc841fe8bEvan Cheng MachineOperand &MO = MI->getOperand(j); 195281a038218171860ee4c382849c647d3dc841fe8bEvan Cheng if (!MO.isRegister() || MO.getReg() != VReg) 195381a038218171860ee4c382849c647d3dc841fe8bEvan Cheng continue; 1954aee4af68ae2016afc5b4ec0c430e539c5810a766Evan Cheng 19550cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng if (MO.isDef()) { 1956aee4af68ae2016afc5b4ec0c430e539c5810a766Evan Cheng // If this restore were to be folded, it would have been folded 1957aee4af68ae2016afc5b4ec0c430e539c5810a766Evan Cheng // already. 1958aee4af68ae2016afc5b4ec0c430e539c5810a766Evan Cheng CanFold = false; 195981a038218171860ee4c382849c647d3dc841fe8bEvan Cheng break; 196081a038218171860ee4c382849c647d3dc841fe8bEvan Cheng } 1961aee4af68ae2016afc5b4ec0c430e539c5810a766Evan Cheng Ops.push_back(j); 196281a038218171860ee4c382849c647d3dc841fe8bEvan Cheng } 196381a038218171860ee4c382849c647d3dc841fe8bEvan Cheng } 19640cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng 19650cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng // Fold the load into the use if possible. 1966cddbb83ea82e98658d9f530c50a7b9d23249afc2Evan Cheng bool Folded = false; 1967aee4af68ae2016afc5b4ec0c430e539c5810a766Evan Cheng if (CanFold && !Ops.empty()) { 19689c3c2213647e3f1b71722d61875ebac01b65cb91Evan Cheng if (!isReMat) 1969aee4af68ae2016afc5b4ec0c430e539c5810a766Evan Cheng Folded = tryFoldMemoryOperand(MI, vrm, NULL,index,Ops,true,Slot,VReg); 1970aee4af68ae2016afc5b4ec0c430e539c5810a766Evan Cheng else { 19710cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng MachineInstr *ReMatDefMI = vrm.getReMaterializedMI(VReg); 19720cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng int LdSlot = 0; 19730cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng bool isLoadSS = tii_->isLoadFromStackSlot(ReMatDefMI, LdSlot); 19740cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng // If the rematerializable def is a load, also try to fold it. 1975749c6f6b5ed301c84aac562e414486549d7b98ebChris Lattner if (isLoadSS || ReMatDefMI->getDesc().isSimpleLoad()) 1976aee4af68ae2016afc5b4ec0c430e539c5810a766Evan Cheng Folded = tryFoldMemoryOperand(MI, vrm, ReMatDefMI, index, 1977aee4af68ae2016afc5b4ec0c430e539c5810a766Evan Cheng Ops, isLoadSS, LdSlot, VReg); 1978d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng unsigned ImpUse = getReMatImplicitUse(li, ReMatDefMI); 1979d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng if (ImpUse) { 1980d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng // Re-matting an instruction with virtual register use. Add the 1981d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng // register as an implicit use on the use MI and update the register 198224d2f8a212f08bf21360122cc00acf2657af91f9Evan Cheng // interval's spill weight to HUGE_VALF to prevent it from being 198324d2f8a212f08bf21360122cc00acf2657af91f9Evan Cheng // spilled. 1984d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng LiveInterval &ImpLi = getInterval(ImpUse); 198524d2f8a212f08bf21360122cc00acf2657af91f9Evan Cheng ImpLi.weight = HUGE_VALF; 1986d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng MI->addOperand(MachineOperand::CreateReg(ImpUse, false, true)); 1987d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng } 1988aee4af68ae2016afc5b4ec0c430e539c5810a766Evan Cheng } 19890cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng } 19900cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng // If folding is not possible / failed, then tell the spiller to issue a 19910cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng // load / rematerialization for us. 1992597d10d84fb6b34f7776121404d5ed802b21b2b6Evan Cheng if (Folded) 1993597d10d84fb6b34f7776121404d5ed802b21b2b6Evan Cheng nI.removeRange(getLoadIndex(index), getUseIndex(index)+1); 1994b50bb8cf197709b3f49044740044c06d8f314564Evan Cheng else 19950cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng vrm.addRestorePoint(VReg, MI); 19969c3c2213647e3f1b71722d61875ebac01b65cb91Evan Cheng 19979c3c2213647e3f1b71722d61875ebac01b65cb91Evan Cheng // Update spill slot weight. 19989c3c2213647e3f1b71722d61875ebac01b65cb91Evan Cheng if (!isReMat) 1999c3417609ae6e744a29be6962d4fb7811c0102d17Evan Cheng SSWeight += getSpillWeight(false, true, loopDepth); 200081a038218171860ee4c382849c647d3dc841fe8bEvan Cheng } 20011953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng Id = RestoreMBBs.find_next(Id); 200281a038218171860ee4c382849c647d3dc841fe8bEvan Cheng } 200381a038218171860ee4c382849c647d3dc841fe8bEvan Cheng 2004b50bb8cf197709b3f49044740044c06d8f314564Evan Cheng // Finalize intervals: add kills, finalize spill weights, and filter out 2005b50bb8cf197709b3f49044740044c06d8f314564Evan Cheng // dead intervals. 2006597d10d84fb6b34f7776121404d5ed802b21b2b6Evan Cheng std::vector<LiveInterval*> RetNewLIs; 2007597d10d84fb6b34f7776121404d5ed802b21b2b6Evan Cheng for (unsigned i = 0, e = NewLIs.size(); i != e; ++i) { 2008597d10d84fb6b34f7776121404d5ed802b21b2b6Evan Cheng LiveInterval *LI = NewLIs[i]; 2009597d10d84fb6b34f7776121404d5ed802b21b2b6Evan Cheng if (!LI->empty()) { 2010496bac5b084474ac33109bad24c1ef94c843e16fOwen Anderson LI->weight /= InstrSlots::NUM * getApproximateInstructionCount(*LI); 2011b50bb8cf197709b3f49044740044c06d8f314564Evan Cheng if (!AddedKill.count(LI)) { 2012b50bb8cf197709b3f49044740044c06d8f314564Evan Cheng LiveRange *LR = &LI->ranges[LI->ranges.size()-1]; 2013d120ffd26f2715c600b028d4eac9a3c41a9f4653Evan Cheng unsigned LastUseIdx = getBaseIndex(LR->end); 2014d120ffd26f2715c600b028d4eac9a3c41a9f4653Evan Cheng MachineInstr *LastUse = getInstructionFromIndex(LastUseIdx); 20156130f66eaae89f8878590796977678afa8448926Evan Cheng int UseIdx = LastUse->findRegisterUseOperandIdx(LI->reg, false); 2016b50bb8cf197709b3f49044740044c06d8f314564Evan Cheng assert(UseIdx != -1); 2017d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng if (LastUse->getOperand(UseIdx).isImplicit() || 2018d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng LastUse->getDesc().getOperandConstraint(UseIdx,TOI::TIED_TO) == -1){ 2019b50bb8cf197709b3f49044740044c06d8f314564Evan Cheng LastUse->getOperand(UseIdx).setIsKill(); 2020d120ffd26f2715c600b028d4eac9a3c41a9f4653Evan Cheng vrm.addKillPoint(LI->reg, LastUseIdx); 2021adf85906906ebf85c57c333e8209f37ef11a6c99Evan Cheng } 2022b50bb8cf197709b3f49044740044c06d8f314564Evan Cheng } 2023597d10d84fb6b34f7776121404d5ed802b21b2b6Evan Cheng RetNewLIs.push_back(LI); 2024597d10d84fb6b34f7776121404d5ed802b21b2b6Evan Cheng } 2025597d10d84fb6b34f7776121404d5ed802b21b2b6Evan Cheng } 202681a038218171860ee4c382849c647d3dc841fe8bEvan Cheng 20274cce6b4c7882ef0cc993d931b90bf33985c96110Evan Cheng handleSpilledImpDefs(li, vrm, rc, RetNewLIs); 2028597d10d84fb6b34f7776121404d5ed802b21b2b6Evan Cheng return RetNewLIs; 2029f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng} 2030676dd7c80b6f91178452535ac45ca58feb23cc42Evan Cheng 2031676dd7c80b6f91178452535ac45ca58feb23cc42Evan Cheng/// hasAllocatableSuperReg - Return true if the specified physical register has 2032676dd7c80b6f91178452535ac45ca58feb23cc42Evan Cheng/// any super register that's allocatable. 2033676dd7c80b6f91178452535ac45ca58feb23cc42Evan Chengbool LiveIntervals::hasAllocatableSuperReg(unsigned Reg) const { 2034676dd7c80b6f91178452535ac45ca58feb23cc42Evan Cheng for (const unsigned* AS = tri_->getSuperRegisters(Reg); *AS; ++AS) 2035676dd7c80b6f91178452535ac45ca58feb23cc42Evan Cheng if (allocatableRegs_[*AS] && hasInterval(*AS)) 2036676dd7c80b6f91178452535ac45ca58feb23cc42Evan Cheng return true; 2037676dd7c80b6f91178452535ac45ca58feb23cc42Evan Cheng return false; 2038676dd7c80b6f91178452535ac45ca58feb23cc42Evan Cheng} 2039676dd7c80b6f91178452535ac45ca58feb23cc42Evan Cheng 2040676dd7c80b6f91178452535ac45ca58feb23cc42Evan Cheng/// getRepresentativeReg - Find the largest super register of the specified 2041676dd7c80b6f91178452535ac45ca58feb23cc42Evan Cheng/// physical register. 2042676dd7c80b6f91178452535ac45ca58feb23cc42Evan Chengunsigned LiveIntervals::getRepresentativeReg(unsigned Reg) const { 2043676dd7c80b6f91178452535ac45ca58feb23cc42Evan Cheng // Find the largest super-register that is allocatable. 2044676dd7c80b6f91178452535ac45ca58feb23cc42Evan Cheng unsigned BestReg = Reg; 2045676dd7c80b6f91178452535ac45ca58feb23cc42Evan Cheng for (const unsigned* AS = tri_->getSuperRegisters(Reg); *AS; ++AS) { 2046676dd7c80b6f91178452535ac45ca58feb23cc42Evan Cheng unsigned SuperReg = *AS; 2047676dd7c80b6f91178452535ac45ca58feb23cc42Evan Cheng if (!hasAllocatableSuperReg(SuperReg) && hasInterval(SuperReg)) { 2048676dd7c80b6f91178452535ac45ca58feb23cc42Evan Cheng BestReg = SuperReg; 2049676dd7c80b6f91178452535ac45ca58feb23cc42Evan Cheng break; 2050676dd7c80b6f91178452535ac45ca58feb23cc42Evan Cheng } 2051676dd7c80b6f91178452535ac45ca58feb23cc42Evan Cheng } 2052676dd7c80b6f91178452535ac45ca58feb23cc42Evan Cheng return BestReg; 2053676dd7c80b6f91178452535ac45ca58feb23cc42Evan Cheng} 2054676dd7c80b6f91178452535ac45ca58feb23cc42Evan Cheng 2055676dd7c80b6f91178452535ac45ca58feb23cc42Evan Cheng/// getNumConflictsWithPhysReg - Return the number of uses and defs of the 2056676dd7c80b6f91178452535ac45ca58feb23cc42Evan Cheng/// specified interval that conflicts with the specified physical register. 2057676dd7c80b6f91178452535ac45ca58feb23cc42Evan Chengunsigned LiveIntervals::getNumConflictsWithPhysReg(const LiveInterval &li, 2058676dd7c80b6f91178452535ac45ca58feb23cc42Evan Cheng unsigned PhysReg) const { 2059676dd7c80b6f91178452535ac45ca58feb23cc42Evan Cheng unsigned NumConflicts = 0; 2060676dd7c80b6f91178452535ac45ca58feb23cc42Evan Cheng const LiveInterval &pli = getInterval(getRepresentativeReg(PhysReg)); 2061676dd7c80b6f91178452535ac45ca58feb23cc42Evan Cheng for (MachineRegisterInfo::reg_iterator I = mri_->reg_begin(li.reg), 2062676dd7c80b6f91178452535ac45ca58feb23cc42Evan Cheng E = mri_->reg_end(); I != E; ++I) { 2063676dd7c80b6f91178452535ac45ca58feb23cc42Evan Cheng MachineOperand &O = I.getOperand(); 2064676dd7c80b6f91178452535ac45ca58feb23cc42Evan Cheng MachineInstr *MI = O.getParent(); 2065676dd7c80b6f91178452535ac45ca58feb23cc42Evan Cheng unsigned Index = getInstructionIndex(MI); 2066676dd7c80b6f91178452535ac45ca58feb23cc42Evan Cheng if (pli.liveAt(Index)) 2067676dd7c80b6f91178452535ac45ca58feb23cc42Evan Cheng ++NumConflicts; 2068676dd7c80b6f91178452535ac45ca58feb23cc42Evan Cheng } 2069676dd7c80b6f91178452535ac45ca58feb23cc42Evan Cheng return NumConflicts; 2070676dd7c80b6f91178452535ac45ca58feb23cc42Evan Cheng} 2071676dd7c80b6f91178452535ac45ca58feb23cc42Evan Cheng 2072676dd7c80b6f91178452535ac45ca58feb23cc42Evan Cheng/// spillPhysRegAroundRegDefsUses - Spill the specified physical register 2073676dd7c80b6f91178452535ac45ca58feb23cc42Evan Cheng/// around all defs and uses of the specified interval. 2074676dd7c80b6f91178452535ac45ca58feb23cc42Evan Chengvoid LiveIntervals::spillPhysRegAroundRegDefsUses(const LiveInterval &li, 2075676dd7c80b6f91178452535ac45ca58feb23cc42Evan Cheng unsigned PhysReg, VirtRegMap &vrm) { 2076676dd7c80b6f91178452535ac45ca58feb23cc42Evan Cheng unsigned SpillReg = getRepresentativeReg(PhysReg); 2077676dd7c80b6f91178452535ac45ca58feb23cc42Evan Cheng 2078676dd7c80b6f91178452535ac45ca58feb23cc42Evan Cheng for (const unsigned *AS = tri_->getAliasSet(PhysReg); *AS; ++AS) 2079676dd7c80b6f91178452535ac45ca58feb23cc42Evan Cheng // If there are registers which alias PhysReg, but which are not a 2080676dd7c80b6f91178452535ac45ca58feb23cc42Evan Cheng // sub-register of the chosen representative super register. Assert 2081676dd7c80b6f91178452535ac45ca58feb23cc42Evan Cheng // since we can't handle it yet. 2082676dd7c80b6f91178452535ac45ca58feb23cc42Evan Cheng assert(*AS == SpillReg || !allocatableRegs_[*AS] || 2083676dd7c80b6f91178452535ac45ca58feb23cc42Evan Cheng tri_->isSuperRegister(*AS, SpillReg)); 2084676dd7c80b6f91178452535ac45ca58feb23cc42Evan Cheng 2085676dd7c80b6f91178452535ac45ca58feb23cc42Evan Cheng LiveInterval &pli = getInterval(SpillReg); 2086676dd7c80b6f91178452535ac45ca58feb23cc42Evan Cheng SmallPtrSet<MachineInstr*, 8> SeenMIs; 2087676dd7c80b6f91178452535ac45ca58feb23cc42Evan Cheng for (MachineRegisterInfo::reg_iterator I = mri_->reg_begin(li.reg), 2088676dd7c80b6f91178452535ac45ca58feb23cc42Evan Cheng E = mri_->reg_end(); I != E; ++I) { 2089676dd7c80b6f91178452535ac45ca58feb23cc42Evan Cheng MachineOperand &O = I.getOperand(); 2090676dd7c80b6f91178452535ac45ca58feb23cc42Evan Cheng MachineInstr *MI = O.getParent(); 2091676dd7c80b6f91178452535ac45ca58feb23cc42Evan Cheng if (SeenMIs.count(MI)) 2092676dd7c80b6f91178452535ac45ca58feb23cc42Evan Cheng continue; 2093676dd7c80b6f91178452535ac45ca58feb23cc42Evan Cheng SeenMIs.insert(MI); 2094676dd7c80b6f91178452535ac45ca58feb23cc42Evan Cheng unsigned Index = getInstructionIndex(MI); 2095676dd7c80b6f91178452535ac45ca58feb23cc42Evan Cheng if (pli.liveAt(Index)) { 2096676dd7c80b6f91178452535ac45ca58feb23cc42Evan Cheng vrm.addEmergencySpill(SpillReg, MI); 2097676dd7c80b6f91178452535ac45ca58feb23cc42Evan Cheng pli.removeRange(getLoadIndex(Index), getStoreIndex(Index)+1); 2098676dd7c80b6f91178452535ac45ca58feb23cc42Evan Cheng for (const unsigned* AS = tri_->getSubRegisters(SpillReg); *AS; ++AS) { 2099676dd7c80b6f91178452535ac45ca58feb23cc42Evan Cheng if (!hasInterval(*AS)) 2100676dd7c80b6f91178452535ac45ca58feb23cc42Evan Cheng continue; 2101676dd7c80b6f91178452535ac45ca58feb23cc42Evan Cheng LiveInterval &spli = getInterval(*AS); 2102676dd7c80b6f91178452535ac45ca58feb23cc42Evan Cheng if (spli.liveAt(Index)) 2103676dd7c80b6f91178452535ac45ca58feb23cc42Evan Cheng spli.removeRange(getLoadIndex(Index), getStoreIndex(Index)+1); 2104676dd7c80b6f91178452535ac45ca58feb23cc42Evan Cheng } 2105676dd7c80b6f91178452535ac45ca58feb23cc42Evan Cheng } 2106676dd7c80b6f91178452535ac45ca58feb23cc42Evan Cheng } 2107676dd7c80b6f91178452535ac45ca58feb23cc42Evan Cheng} 2108c4dc132c8a787fc41b6a162121251234aa618965Owen Anderson 2109c4dc132c8a787fc41b6a162121251234aa618965Owen AndersonLiveRange LiveIntervals::addLiveRangeToEndOfBlock(unsigned reg, 2110c4dc132c8a787fc41b6a162121251234aa618965Owen Anderson MachineInstr* startInst) { 2111c4dc132c8a787fc41b6a162121251234aa618965Owen Anderson LiveInterval& Interval = getOrCreateInterval(reg); 2112c4dc132c8a787fc41b6a162121251234aa618965Owen Anderson VNInfo* VN = Interval.getNextValue( 2113c4dc132c8a787fc41b6a162121251234aa618965Owen Anderson getInstructionIndex(startInst) + InstrSlots::DEF, 2114c4dc132c8a787fc41b6a162121251234aa618965Owen Anderson startInst, getVNInfoAllocator()); 2115c4dc132c8a787fc41b6a162121251234aa618965Owen Anderson VN->hasPHIKill = true; 2116c4dc132c8a787fc41b6a162121251234aa618965Owen Anderson VN->kills.push_back(getMBBEndIdx(startInst->getParent())); 2117c4dc132c8a787fc41b6a162121251234aa618965Owen Anderson LiveRange LR(getInstructionIndex(startInst) + InstrSlots::DEF, 2118c4dc132c8a787fc41b6a162121251234aa618965Owen Anderson getMBBEndIdx(startInst->getParent()) + 1, VN); 2119c4dc132c8a787fc41b6a162121251234aa618965Owen Anderson Interval.addRange(LR); 2120c4dc132c8a787fc41b6a162121251234aa618965Owen Anderson 2121c4dc132c8a787fc41b6a162121251234aa618965Owen Anderson return LR; 2122c4dc132c8a787fc41b6a162121251234aa618965Owen Anderson} 2123