LiveIntervalAnalysis.cpp revision d21c31610c4a10e9e638f4221b5df89ea932e258
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" 3395dad830bbf975cb4cea4e1ac685781a18676a7aOwen Anderson#include "llvm/Target/TargetOptions.h" 34551ccae044b0ff658fe629dd67edd5ffe75d10e8Reid Spencer#include "llvm/Support/CommandLine.h" 35551ccae044b0ff658fe629dd67edd5ffe75d10e8Reid Spencer#include "llvm/Support/Debug.h" 36551ccae044b0ff658fe629dd67edd5ffe75d10e8Reid Spencer#include "llvm/ADT/Statistic.h" 37551ccae044b0ff658fe629dd67edd5ffe75d10e8Reid Spencer#include "llvm/ADT/STLExtras.h" 3820aa474f8fbebde588edc101b90e834df28ce4ceAlkis Evlogimenos#include <algorithm> 39f41538d1b54f55e8900394929b50f7ce3e61125fLang Hames#include <limits> 4097af751deb9b26fd42fbcee082da9ccc4ded5b45Jeff Cohen#include <cmath> 41ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenosusing namespace llvm; 42ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos 43844731a7f1909f55935e3514c9e713a62d67662eDan Gohman// Hidden options for help debugging. 44844731a7f1909f55935e3514c9e713a62d67662eDan Gohmanstatic cl::opt<bool> DisableReMat("disable-rematerialization", 45844731a7f1909f55935e3514c9e713a62d67662eDan Gohman cl::init(false), cl::Hidden); 46844731a7f1909f55935e3514c9e713a62d67662eDan Gohman 47844731a7f1909f55935e3514c9e713a62d67662eDan Gohmanstatic cl::opt<bool> SplitAtBB("split-intervals-at-bb", 48844731a7f1909f55935e3514c9e713a62d67662eDan Gohman cl::init(true), cl::Hidden); 49844731a7f1909f55935e3514c9e713a62d67662eDan Gohmanstatic cl::opt<int> SplitLimit("split-limit", 50844731a7f1909f55935e3514c9e713a62d67662eDan Gohman cl::init(-1), cl::Hidden); 51bc165e436beb02443abea9736c1b77e2dd7828b6Evan Cheng 524c8f87038ddc0fbcce751f0e2e7c0e564abca096Dan Gohmanstatic cl::opt<bool> EnableAggressiveRemat("aggressive-remat", cl::Hidden); 534c8f87038ddc0fbcce751f0e2e7c0e564abca096Dan Gohman 54ae339babb2a2445e7bb009912a39994718f10d54Owen Andersonstatic cl::opt<bool> EnableFastSpilling("fast-spill", 55ae339babb2a2445e7bb009912a39994718f10d54Owen Anderson cl::init(false), cl::Hidden); 56ae339babb2a2445e7bb009912a39994718f10d54Owen Anderson 57cd3245ac45c595da96bb768a55cddc356dff55feChris LattnerSTATISTIC(numIntervals, "Number of original intervals"); 580cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan ChengSTATISTIC(numFolds , "Number of loads/stores folded into instructions"); 590cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan ChengSTATISTIC(numSplits , "Number of intervals split"); 60cd3245ac45c595da96bb768a55cddc356dff55feChris Lattner 611997473cf72957d0e70322e2fe6fe2ab141c58a6Devang Patelchar LiveIntervals::ID = 0; 62844731a7f1909f55935e3514c9e713a62d67662eDan Gohmanstatic RegisterPass<LiveIntervals> X("liveintervals", "Live Interval Analysis"); 63ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos 64f7da2c7b0c6293c268881628fc351bed7763f1f4Chris Lattnervoid LiveIntervals::getAnalysisUsage(AnalysisUsage &AU) const { 656d69ba8a6901c69d78488cbc41f8dbf080618fdeDan Gohman AU.addRequired<AliasAnalysis>(); 666d69ba8a6901c69d78488cbc41f8dbf080618fdeDan Gohman AU.addPreserved<AliasAnalysis>(); 672513330de8f8020d15d5bc96640a0957b7c733b9David Greene AU.addPreserved<LiveVariables>(); 681a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos AU.addRequired<LiveVariables>(); 6967d65bb69d5cad957cbb6d672dc0b4a19c211a42Bill Wendling AU.addPreservedID(MachineLoopInfoID); 7067d65bb69d5cad957cbb6d672dc0b4a19c211a42Bill Wendling AU.addPreservedID(MachineDominatorsID); 7195dad830bbf975cb4cea4e1ac685781a18676a7aOwen Anderson 7295dad830bbf975cb4cea4e1ac685781a18676a7aOwen Anderson if (!StrongPHIElim) { 7395dad830bbf975cb4cea4e1ac685781a18676a7aOwen Anderson AU.addPreservedID(PHIEliminationID); 7495dad830bbf975cb4cea4e1ac685781a18676a7aOwen Anderson AU.addRequiredID(PHIEliminationID); 7595dad830bbf975cb4cea4e1ac685781a18676a7aOwen Anderson } 7695dad830bbf975cb4cea4e1ac685781a18676a7aOwen Anderson 771a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos AU.addRequiredID(TwoAddressInstructionPassID); 781a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos MachineFunctionPass::getAnalysisUsage(AU); 79ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos} 80ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos 81f7da2c7b0c6293c268881628fc351bed7763f1f4Chris Lattnervoid LiveIntervals::releaseMemory() { 8203857b29d8271a23943254579e6cf7b7df4b1bd3Owen Anderson // Free the live intervals themselves. 8320e2839cb975a2d4ee931e1ea4c4660a36ef0177Owen Anderson for (DenseMap<unsigned, LiveInterval*>::iterator I = r2iMap_.begin(), 8403857b29d8271a23943254579e6cf7b7df4b1bd3Owen Anderson E = r2iMap_.end(); I != E; ++I) 8503857b29d8271a23943254579e6cf7b7df4b1bd3Owen Anderson delete I->second; 8603857b29d8271a23943254579e6cf7b7df4b1bd3Owen Anderson 873f32d65912b4da23793dab618d981be2ce11c331Evan Cheng MBB2IdxMap.clear(); 884ca980e7f9ce7b78955307c2d07001a24d3b6befEvan Cheng Idx2MBBMap.clear(); 891a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos mi2iMap_.clear(); 901a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos i2miMap_.clear(); 911a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos r2iMap_.clear(); 92dd199d29b781bc713462f1255b63d3f153bfd9e9Evan Cheng // Release VNInfo memroy regions after all VNInfo objects are dtor'd. 93dd199d29b781bc713462f1255b63d3f153bfd9e9Evan Cheng VNInfoAllocator.Reset(); 941ed9922794cda9dbe295e74674b909287e544632Evan Cheng while (!ClonedMIs.empty()) { 951ed9922794cda9dbe295e74674b909287e544632Evan Cheng MachineInstr *MI = ClonedMIs.back(); 961ed9922794cda9dbe295e74674b909287e544632Evan Cheng ClonedMIs.pop_back(); 971ed9922794cda9dbe295e74674b909287e544632Evan Cheng mf_->DeleteMachineInstr(MI); 981ed9922794cda9dbe295e74674b909287e544632Evan Cheng } 99993141402f57b4d4cbb7f8a3113f19c61688f9b7Evan Cheng} 100993141402f57b4d4cbb7f8a3113f19c61688f9b7Evan Cheng 10180b3ce65e294a28b88c882d44a5e749a2924c9e3Owen Andersonvoid LiveIntervals::computeNumbering() { 10280b3ce65e294a28b88c882d44a5e749a2924c9e3Owen Anderson Index2MiMap OldI2MI = i2miMap_; 1037fbad27cfb7298c707e50af10609d463900d7211Owen Anderson std::vector<IdxMBBPair> OldI2MBB = Idx2MBBMap; 10480b3ce65e294a28b88c882d44a5e749a2924c9e3Owen Anderson 10580b3ce65e294a28b88c882d44a5e749a2924c9e3Owen Anderson Idx2MBBMap.clear(); 10680b3ce65e294a28b88c882d44a5e749a2924c9e3Owen Anderson MBB2IdxMap.clear(); 10780b3ce65e294a28b88c882d44a5e749a2924c9e3Owen Anderson mi2iMap_.clear(); 10880b3ce65e294a28b88c882d44a5e749a2924c9e3Owen Anderson i2miMap_.clear(); 10980b3ce65e294a28b88c882d44a5e749a2924c9e3Owen Anderson 110a1566f2e12ce87a5bca30bc0189a0cdbb40136a4Owen Anderson FunctionSize = 0; 111a1566f2e12ce87a5bca30bc0189a0cdbb40136a4Owen Anderson 112428b92eb83b457b71d29d1d4b7900d36a0ce9a53Chris Lattner // Number MachineInstrs and MachineBasicBlocks. 113428b92eb83b457b71d29d1d4b7900d36a0ce9a53Chris Lattner // Initialize MBB indexes to a sentinal. 114549f27d3070195d6647b796841a5291b4549e8e0Evan Cheng MBB2IdxMap.resize(mf_->getNumBlockIDs(), std::make_pair(~0U,~0U)); 115428b92eb83b457b71d29d1d4b7900d36a0ce9a53Chris Lattner 116428b92eb83b457b71d29d1d4b7900d36a0ce9a53Chris Lattner unsigned MIIndex = 0; 117428b92eb83b457b71d29d1d4b7900d36a0ce9a53Chris Lattner for (MachineFunction::iterator MBB = mf_->begin(), E = mf_->end(); 118428b92eb83b457b71d29d1d4b7900d36a0ce9a53Chris Lattner MBB != E; ++MBB) { 119549f27d3070195d6647b796841a5291b4549e8e0Evan Cheng unsigned StartIdx = MIIndex; 1200c9f92e1ff64ee56724eae444a0442b02f83d0a8Evan Cheng 1217fbad27cfb7298c707e50af10609d463900d7211Owen Anderson // Insert an empty slot at the beginning of each block. 1227fbad27cfb7298c707e50af10609d463900d7211Owen Anderson MIIndex += InstrSlots::NUM; 1237fbad27cfb7298c707e50af10609d463900d7211Owen Anderson i2miMap_.push_back(0); 1247fbad27cfb7298c707e50af10609d463900d7211Owen Anderson 125428b92eb83b457b71d29d1d4b7900d36a0ce9a53Chris Lattner for (MachineBasicBlock::iterator I = MBB->begin(), E = MBB->end(); 126428b92eb83b457b71d29d1d4b7900d36a0ce9a53Chris Lattner I != E; ++I) { 127428b92eb83b457b71d29d1d4b7900d36a0ce9a53Chris Lattner bool inserted = mi2iMap_.insert(std::make_pair(I, MIIndex)).second; 1281a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos assert(inserted && "multiple MachineInstr -> index mappings"); 12959500c8f9a76b3386329b6f837255c16f4e8b61bDevang Patel inserted = true; 130428b92eb83b457b71d29d1d4b7900d36a0ce9a53Chris Lattner i2miMap_.push_back(I); 131428b92eb83b457b71d29d1d4b7900d36a0ce9a53Chris Lattner MIIndex += InstrSlots::NUM; 132a1566f2e12ce87a5bca30bc0189a0cdbb40136a4Owen Anderson FunctionSize++; 1337fbad27cfb7298c707e50af10609d463900d7211Owen Anderson 1344ed4329c37f5a64c16ad4dc1960cbcb66b7118d4Evan Cheng // Insert max(1, numdefs) empty slots after every instruction. 13599fe34b9b2bb8786da6c7f6134ae17d4c2cd8bf7Evan Cheng unsigned Slots = I->getDesc().getNumDefs(); 13699fe34b9b2bb8786da6c7f6134ae17d4c2cd8bf7Evan Cheng if (Slots == 0) 13799fe34b9b2bb8786da6c7f6134ae17d4c2cd8bf7Evan Cheng Slots = 1; 13899fe34b9b2bb8786da6c7f6134ae17d4c2cd8bf7Evan Cheng MIIndex += InstrSlots::NUM * Slots; 13999fe34b9b2bb8786da6c7f6134ae17d4c2cd8bf7Evan Cheng while (Slots--) 14099fe34b9b2bb8786da6c7f6134ae17d4c2cd8bf7Evan Cheng i2miMap_.push_back(0); 141355780128986e375c7ac2a75025ac129bb8280bfOwen Anderson } 1427fbad27cfb7298c707e50af10609d463900d7211Owen Anderson 1431fbb4545d41e65191ae66a7302276fa5424518c5Owen Anderson // Set the MBB2IdxMap entry for this MBB. 1441fbb4545d41e65191ae66a7302276fa5424518c5Owen Anderson MBB2IdxMap[MBB->getNumber()] = std::make_pair(StartIdx, MIIndex - 1); 1451fbb4545d41e65191ae66a7302276fa5424518c5Owen Anderson Idx2MBBMap.push_back(std::make_pair(StartIdx, MBB)); 146428b92eb83b457b71d29d1d4b7900d36a0ce9a53Chris Lattner } 1474ca980e7f9ce7b78955307c2d07001a24d3b6befEvan Cheng std::sort(Idx2MBBMap.begin(), Idx2MBBMap.end(), Idx2MBBCompare()); 14880b3ce65e294a28b88c882d44a5e749a2924c9e3Owen Anderson 14980b3ce65e294a28b88c882d44a5e749a2924c9e3Owen Anderson if (!OldI2MI.empty()) 150788d04152a132121dfc04e63382c1e87e7b9607fOwen Anderson for (iterator OI = begin(), OE = end(); OI != OE; ++OI) { 15103857b29d8271a23943254579e6cf7b7df4b1bd3Owen Anderson for (LiveInterval::iterator LI = OI->second->begin(), 15203857b29d8271a23943254579e6cf7b7df4b1bd3Owen Anderson LE = OI->second->end(); LI != LE; ++LI) { 1537eec0c243320fb2629554681547d7384ea9d0c53Owen Anderson 1547eec0c243320fb2629554681547d7384ea9d0c53Owen Anderson // Remap the start index of the live range to the corresponding new 1557eec0c243320fb2629554681547d7384ea9d0c53Owen Anderson // number, or our best guess at what it _should_ correspond to if the 1567eec0c243320fb2629554681547d7384ea9d0c53Owen Anderson // original instruction has been erased. This is either the following 1577eec0c243320fb2629554681547d7384ea9d0c53Owen Anderson // instruction or its predecessor. 1587fbad27cfb7298c707e50af10609d463900d7211Owen Anderson unsigned index = LI->start / InstrSlots::NUM; 1594b5b209679f866d3ac6372f963aa7e9906f9a08bOwen Anderson unsigned offset = LI->start % InstrSlots::NUM; 1600a7615af25542d5e7d824b520f94094cdc8a2179Owen Anderson if (offset == InstrSlots::LOAD) { 1617fbad27cfb7298c707e50af10609d463900d7211Owen Anderson std::vector<IdxMBBPair>::const_iterator I = 162d7dcbecdbcf5d7a1efc5ed65ddcc26bb8c20c1e6Owen Anderson std::lower_bound(OldI2MBB.begin(), OldI2MBB.end(), LI->start); 1637fbad27cfb7298c707e50af10609d463900d7211Owen Anderson // Take the pair containing the index 1647fbad27cfb7298c707e50af10609d463900d7211Owen Anderson std::vector<IdxMBBPair>::const_iterator J = 165a0c032f9b2eeae3a436850eaca54de4c6a5f23b6Owen Anderson (I == OldI2MBB.end() && OldI2MBB.size()>0) ? (I-1): I; 1667eec0c243320fb2629554681547d7384ea9d0c53Owen Anderson 1677fbad27cfb7298c707e50af10609d463900d7211Owen Anderson LI->start = getMBBStartIdx(J->second); 1687fbad27cfb7298c707e50af10609d463900d7211Owen Anderson } else { 1697fbad27cfb7298c707e50af10609d463900d7211Owen Anderson LI->start = mi2iMap_[OldI2MI[index]] + offset; 1707eec0c243320fb2629554681547d7384ea9d0c53Owen Anderson } 1714b5b209679f866d3ac6372f963aa7e9906f9a08bOwen Anderson 1727eec0c243320fb2629554681547d7384ea9d0c53Owen Anderson // Remap the ending index in the same way that we remapped the start, 1737eec0c243320fb2629554681547d7384ea9d0c53Owen Anderson // except for the final step where we always map to the immediately 1747eec0c243320fb2629554681547d7384ea9d0c53Owen Anderson // following instruction. 175d7dcbecdbcf5d7a1efc5ed65ddcc26bb8c20c1e6Owen Anderson index = (LI->end - 1) / InstrSlots::NUM; 1767fbad27cfb7298c707e50af10609d463900d7211Owen Anderson offset = LI->end % InstrSlots::NUM; 1779382b9310f008a3347e565d76aadda6a97351de9Owen Anderson if (offset == InstrSlots::LOAD) { 1789382b9310f008a3347e565d76aadda6a97351de9Owen Anderson // VReg dies at end of block. 1797fbad27cfb7298c707e50af10609d463900d7211Owen Anderson std::vector<IdxMBBPair>::const_iterator I = 180d7dcbecdbcf5d7a1efc5ed65ddcc26bb8c20c1e6Owen Anderson std::lower_bound(OldI2MBB.begin(), OldI2MBB.end(), LI->end); 1819382b9310f008a3347e565d76aadda6a97351de9Owen Anderson --I; 1827fbad27cfb7298c707e50af10609d463900d7211Owen Anderson 1839382b9310f008a3347e565d76aadda6a97351de9Owen Anderson LI->end = getMBBEndIdx(I->second) + 1; 1844b5b209679f866d3ac6372f963aa7e9906f9a08bOwen Anderson } else { 185d7dcbecdbcf5d7a1efc5ed65ddcc26bb8c20c1e6Owen Anderson unsigned idx = index; 1868d0cc0af5a4b4c08eb74b6e36761651b63816d06Owen Anderson while (index < OldI2MI.size() && !OldI2MI[index]) ++index; 1878d0cc0af5a4b4c08eb74b6e36761651b63816d06Owen Anderson 1888d0cc0af5a4b4c08eb74b6e36761651b63816d06Owen Anderson if (index != OldI2MI.size()) 1898d0cc0af5a4b4c08eb74b6e36761651b63816d06Owen Anderson LI->end = mi2iMap_[OldI2MI[index]] + (idx == index ? offset : 0); 1908d0cc0af5a4b4c08eb74b6e36761651b63816d06Owen Anderson else 1918d0cc0af5a4b4c08eb74b6e36761651b63816d06Owen Anderson LI->end = InstrSlots::NUM * i2miMap_.size(); 1924b5b209679f866d3ac6372f963aa7e9906f9a08bOwen Anderson } 193788d04152a132121dfc04e63382c1e87e7b9607fOwen Anderson } 194788d04152a132121dfc04e63382c1e87e7b9607fOwen Anderson 19503857b29d8271a23943254579e6cf7b7df4b1bd3Owen Anderson for (LiveInterval::vni_iterator VNI = OI->second->vni_begin(), 19603857b29d8271a23943254579e6cf7b7df4b1bd3Owen Anderson VNE = OI->second->vni_end(); VNI != VNE; ++VNI) { 197788d04152a132121dfc04e63382c1e87e7b9607fOwen Anderson VNInfo* vni = *VNI; 198745825f431920662e97bdab5c1bcfac62e48c52fOwen Anderson 1997eec0c243320fb2629554681547d7384ea9d0c53Owen Anderson // Remap the VNInfo def index, which works the same as the 200788d04152a132121dfc04e63382c1e87e7b9607fOwen Anderson // start indices above. VN's with special sentinel defs 201788d04152a132121dfc04e63382c1e87e7b9607fOwen Anderson // don't need to be remapped. 202857c4e01f85601cf2084adb860616256ee47c177Lang Hames if (vni->isDefAccurate() && !vni->isUnused()) { 203788d04152a132121dfc04e63382c1e87e7b9607fOwen Anderson unsigned index = vni->def / InstrSlots::NUM; 204788d04152a132121dfc04e63382c1e87e7b9607fOwen Anderson unsigned offset = vni->def % InstrSlots::NUM; 205912923925f790427a77781b8a0469fa832c7740dOwen Anderson if (offset == InstrSlots::LOAD) { 206912923925f790427a77781b8a0469fa832c7740dOwen Anderson std::vector<IdxMBBPair>::const_iterator I = 2070a7615af25542d5e7d824b520f94094cdc8a2179Owen Anderson std::lower_bound(OldI2MBB.begin(), OldI2MBB.end(), vni->def); 208912923925f790427a77781b8a0469fa832c7740dOwen Anderson // Take the pair containing the index 209912923925f790427a77781b8a0469fa832c7740dOwen Anderson std::vector<IdxMBBPair>::const_iterator J = 210a0c032f9b2eeae3a436850eaca54de4c6a5f23b6Owen Anderson (I == OldI2MBB.end() && OldI2MBB.size()>0) ? (I-1): I; 2117eec0c243320fb2629554681547d7384ea9d0c53Owen Anderson 212912923925f790427a77781b8a0469fa832c7740dOwen Anderson vni->def = getMBBStartIdx(J->second); 213912923925f790427a77781b8a0469fa832c7740dOwen Anderson } else { 214912923925f790427a77781b8a0469fa832c7740dOwen Anderson vni->def = mi2iMap_[OldI2MI[index]] + offset; 215912923925f790427a77781b8a0469fa832c7740dOwen Anderson } 2167eec0c243320fb2629554681547d7384ea9d0c53Owen Anderson } 217745825f431920662e97bdab5c1bcfac62e48c52fOwen Anderson 2187eec0c243320fb2629554681547d7384ea9d0c53Owen Anderson // Remap the VNInfo kill indices, which works the same as 2197eec0c243320fb2629554681547d7384ea9d0c53Owen Anderson // the end indices above. 2204b5b209679f866d3ac6372f963aa7e9906f9a08bOwen Anderson for (size_t i = 0; i < vni->kills.size(); ++i) { 2219382b9310f008a3347e565d76aadda6a97351de9Owen Anderson // PHI kills don't need to be remapped. 2229382b9310f008a3347e565d76aadda6a97351de9Owen Anderson if (!vni->kills[i]) continue; 2239382b9310f008a3347e565d76aadda6a97351de9Owen Anderson 224788d04152a132121dfc04e63382c1e87e7b9607fOwen Anderson unsigned index = (vni->kills[i]-1) / InstrSlots::NUM; 225788d04152a132121dfc04e63382c1e87e7b9607fOwen Anderson unsigned offset = vni->kills[i] % InstrSlots::NUM; 226309c6162c62ba35ded8650a0ea4d2036de7480fdOwen Anderson if (offset == InstrSlots::LOAD) { 2277fbad27cfb7298c707e50af10609d463900d7211Owen Anderson std::vector<IdxMBBPair>::const_iterator I = 228d7dcbecdbcf5d7a1efc5ed65ddcc26bb8c20c1e6Owen Anderson std::lower_bound(OldI2MBB.begin(), OldI2MBB.end(), vni->kills[i]); 2299382b9310f008a3347e565d76aadda6a97351de9Owen Anderson --I; 2307fbad27cfb7298c707e50af10609d463900d7211Owen Anderson 231788d04152a132121dfc04e63382c1e87e7b9607fOwen Anderson vni->kills[i] = getMBBEndIdx(I->second); 2327fbad27cfb7298c707e50af10609d463900d7211Owen Anderson } else { 233d7dcbecdbcf5d7a1efc5ed65ddcc26bb8c20c1e6Owen Anderson unsigned idx = index; 2348d0cc0af5a4b4c08eb74b6e36761651b63816d06Owen Anderson while (index < OldI2MI.size() && !OldI2MI[index]) ++index; 2358d0cc0af5a4b4c08eb74b6e36761651b63816d06Owen Anderson 2368d0cc0af5a4b4c08eb74b6e36761651b63816d06Owen Anderson if (index != OldI2MI.size()) 2378d0cc0af5a4b4c08eb74b6e36761651b63816d06Owen Anderson vni->kills[i] = mi2iMap_[OldI2MI[index]] + 2388d0cc0af5a4b4c08eb74b6e36761651b63816d06Owen Anderson (idx == index ? offset : 0); 2398d0cc0af5a4b4c08eb74b6e36761651b63816d06Owen Anderson else 2408d0cc0af5a4b4c08eb74b6e36761651b63816d06Owen Anderson vni->kills[i] = InstrSlots::NUM * i2miMap_.size(); 2417eec0c243320fb2629554681547d7384ea9d0c53Owen Anderson } 2424b5b209679f866d3ac6372f963aa7e9906f9a08bOwen Anderson } 24380b3ce65e294a28b88c882d44a5e749a2924c9e3Owen Anderson } 244788d04152a132121dfc04e63382c1e87e7b9607fOwen Anderson } 24580b3ce65e294a28b88c882d44a5e749a2924c9e3Owen Anderson} 24680b3ce65e294a28b88c882d44a5e749a2924c9e3Owen Anderson 247f41538d1b54f55e8900394929b50f7ce3e61125fLang Hamesvoid LiveIntervals::scaleNumbering(int factor) { 248f41538d1b54f55e8900394929b50f7ce3e61125fLang Hames // Need to 249f41538d1b54f55e8900394929b50f7ce3e61125fLang Hames // * scale MBB begin and end points 250f41538d1b54f55e8900394929b50f7ce3e61125fLang Hames // * scale all ranges. 251f41538d1b54f55e8900394929b50f7ce3e61125fLang Hames // * Update VNI structures. 252f41538d1b54f55e8900394929b50f7ce3e61125fLang Hames // * Scale instruction numberings 253f41538d1b54f55e8900394929b50f7ce3e61125fLang Hames 254f41538d1b54f55e8900394929b50f7ce3e61125fLang Hames // Scale the MBB indices. 255f41538d1b54f55e8900394929b50f7ce3e61125fLang Hames Idx2MBBMap.clear(); 256f41538d1b54f55e8900394929b50f7ce3e61125fLang Hames for (MachineFunction::iterator MBB = mf_->begin(), MBBE = mf_->end(); 257f41538d1b54f55e8900394929b50f7ce3e61125fLang Hames MBB != MBBE; ++MBB) { 258f41538d1b54f55e8900394929b50f7ce3e61125fLang Hames std::pair<unsigned, unsigned> &mbbIndices = MBB2IdxMap[MBB->getNumber()]; 259f41538d1b54f55e8900394929b50f7ce3e61125fLang Hames mbbIndices.first = InstrSlots::scale(mbbIndices.first, factor); 260f41538d1b54f55e8900394929b50f7ce3e61125fLang Hames mbbIndices.second = InstrSlots::scale(mbbIndices.second, factor); 261f41538d1b54f55e8900394929b50f7ce3e61125fLang Hames Idx2MBBMap.push_back(std::make_pair(mbbIndices.first, MBB)); 262f41538d1b54f55e8900394929b50f7ce3e61125fLang Hames } 263f41538d1b54f55e8900394929b50f7ce3e61125fLang Hames std::sort(Idx2MBBMap.begin(), Idx2MBBMap.end(), Idx2MBBCompare()); 264f41538d1b54f55e8900394929b50f7ce3e61125fLang Hames 265f41538d1b54f55e8900394929b50f7ce3e61125fLang Hames // Scale the intervals. 266f41538d1b54f55e8900394929b50f7ce3e61125fLang Hames for (iterator LI = begin(), LE = end(); LI != LE; ++LI) { 267f41538d1b54f55e8900394929b50f7ce3e61125fLang Hames LI->second->scaleNumbering(factor); 268f41538d1b54f55e8900394929b50f7ce3e61125fLang Hames } 269f41538d1b54f55e8900394929b50f7ce3e61125fLang Hames 270f41538d1b54f55e8900394929b50f7ce3e61125fLang Hames // Scale MachineInstrs. 271f41538d1b54f55e8900394929b50f7ce3e61125fLang Hames Mi2IndexMap oldmi2iMap = mi2iMap_; 272f41538d1b54f55e8900394929b50f7ce3e61125fLang Hames unsigned highestSlot = 0; 273f41538d1b54f55e8900394929b50f7ce3e61125fLang Hames for (Mi2IndexMap::iterator MI = oldmi2iMap.begin(), ME = oldmi2iMap.end(); 274f41538d1b54f55e8900394929b50f7ce3e61125fLang Hames MI != ME; ++MI) { 275f41538d1b54f55e8900394929b50f7ce3e61125fLang Hames unsigned newSlot = InstrSlots::scale(MI->second, factor); 276f41538d1b54f55e8900394929b50f7ce3e61125fLang Hames mi2iMap_[MI->first] = newSlot; 277f41538d1b54f55e8900394929b50f7ce3e61125fLang Hames highestSlot = std::max(highestSlot, newSlot); 278f41538d1b54f55e8900394929b50f7ce3e61125fLang Hames } 279f41538d1b54f55e8900394929b50f7ce3e61125fLang Hames 280f41538d1b54f55e8900394929b50f7ce3e61125fLang Hames i2miMap_.clear(); 281f41538d1b54f55e8900394929b50f7ce3e61125fLang Hames i2miMap_.resize(highestSlot + 1); 282f41538d1b54f55e8900394929b50f7ce3e61125fLang Hames for (Mi2IndexMap::iterator MI = mi2iMap_.begin(), ME = mi2iMap_.end(); 283f41538d1b54f55e8900394929b50f7ce3e61125fLang Hames MI != ME; ++MI) { 284f41538d1b54f55e8900394929b50f7ce3e61125fLang Hames i2miMap_[MI->second] = MI->first; 285f41538d1b54f55e8900394929b50f7ce3e61125fLang Hames } 286f41538d1b54f55e8900394929b50f7ce3e61125fLang Hames 287f41538d1b54f55e8900394929b50f7ce3e61125fLang Hames} 288f41538d1b54f55e8900394929b50f7ce3e61125fLang Hames 289f41538d1b54f55e8900394929b50f7ce3e61125fLang Hames 29080b3ce65e294a28b88c882d44a5e749a2924c9e3Owen Anderson/// runOnMachineFunction - Register allocate the whole function 29180b3ce65e294a28b88c882d44a5e749a2924c9e3Owen Anderson/// 29280b3ce65e294a28b88c882d44a5e749a2924c9e3Owen Andersonbool LiveIntervals::runOnMachineFunction(MachineFunction &fn) { 29380b3ce65e294a28b88c882d44a5e749a2924c9e3Owen Anderson mf_ = &fn; 29480b3ce65e294a28b88c882d44a5e749a2924c9e3Owen Anderson mri_ = &mf_->getRegInfo(); 29580b3ce65e294a28b88c882d44a5e749a2924c9e3Owen Anderson tm_ = &fn.getTarget(); 29680b3ce65e294a28b88c882d44a5e749a2924c9e3Owen Anderson tri_ = tm_->getRegisterInfo(); 29780b3ce65e294a28b88c882d44a5e749a2924c9e3Owen Anderson tii_ = tm_->getInstrInfo(); 2986d69ba8a6901c69d78488cbc41f8dbf080618fdeDan Gohman aa_ = &getAnalysis<AliasAnalysis>(); 29980b3ce65e294a28b88c882d44a5e749a2924c9e3Owen Anderson lv_ = &getAnalysis<LiveVariables>(); 30080b3ce65e294a28b88c882d44a5e749a2924c9e3Owen Anderson allocatableRegs_ = tri_->getAllocatableSet(fn); 301ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos 30280b3ce65e294a28b88c882d44a5e749a2924c9e3Owen Anderson computeNumbering(); 3031a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos computeIntervals(); 304ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos 3051a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos numIntervals += getNumIntervals(); 306843b160a2040b3ec4d3452678450afa11704c473Alkis Evlogimenos 30770ca358b7d540b6061236ddf757085042873c12cChris Lattner DEBUG(dump()); 3081a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos return true; 309ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos} 310ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos 31170ca358b7d540b6061236ddf757085042873c12cChris Lattner/// print - Implement the dump method. 312ce9653ce449f1409815547e1bf60abcd1332d2c9Reid Spencervoid LiveIntervals::print(std::ostream &O, const Module* ) const { 31370ca358b7d540b6061236ddf757085042873c12cChris Lattner O << "********** INTERVALS **********\n"; 3148e7a70976deee78a84099b916591d40f7a1cdc34Chris Lattner for (const_iterator I = begin(), E = end(); I != E; ++I) { 31503857b29d8271a23943254579e6cf7b7df4b1bd3Owen Anderson I->second->print(O, tri_); 3163f32d65912b4da23793dab618d981be2ce11c331Evan Cheng O << "\n"; 3178e7a70976deee78a84099b916591d40f7a1cdc34Chris Lattner } 31870ca358b7d540b6061236ddf757085042873c12cChris Lattner 31970ca358b7d540b6061236ddf757085042873c12cChris Lattner O << "********** MACHINEINSTRS **********\n"; 32070ca358b7d540b6061236ddf757085042873c12cChris Lattner for (MachineFunction::iterator mbbi = mf_->begin(), mbbe = mf_->end(); 32170ca358b7d540b6061236ddf757085042873c12cChris Lattner mbbi != mbbe; ++mbbi) { 32270ca358b7d540b6061236ddf757085042873c12cChris Lattner O << ((Value*)mbbi->getBasicBlock())->getName() << ":\n"; 32370ca358b7d540b6061236ddf757085042873c12cChris Lattner for (MachineBasicBlock::iterator mii = mbbi->begin(), 32470ca358b7d540b6061236ddf757085042873c12cChris Lattner mie = mbbi->end(); mii != mie; ++mii) { 325477e4555de341c5de780de3720d6f115ec133c4eChris Lattner O << getInstructionIndex(mii) << '\t' << *mii; 32670ca358b7d540b6061236ddf757085042873c12cChris Lattner } 32770ca358b7d540b6061236ddf757085042873c12cChris Lattner } 32870ca358b7d540b6061236ddf757085042873c12cChris Lattner} 32970ca358b7d540b6061236ddf757085042873c12cChris Lattner 330c92da3882ee4e18153bb36fcdf33af393aba8259Evan Cheng/// conflictsWithPhysRegDef - Returns true if the specified register 331c92da3882ee4e18153bb36fcdf33af393aba8259Evan Cheng/// is defined during the duration of the specified interval. 332c92da3882ee4e18153bb36fcdf33af393aba8259Evan Chengbool LiveIntervals::conflictsWithPhysRegDef(const LiveInterval &li, 333c92da3882ee4e18153bb36fcdf33af393aba8259Evan Cheng VirtRegMap &vrm, unsigned reg) { 334c92da3882ee4e18153bb36fcdf33af393aba8259Evan Cheng for (LiveInterval::Ranges::const_iterator 335c92da3882ee4e18153bb36fcdf33af393aba8259Evan Cheng I = li.ranges.begin(), E = li.ranges.end(); I != E; ++I) { 336c92da3882ee4e18153bb36fcdf33af393aba8259Evan Cheng for (unsigned index = getBaseIndex(I->start), 337c92da3882ee4e18153bb36fcdf33af393aba8259Evan Cheng end = getBaseIndex(I->end-1) + InstrSlots::NUM; index != end; 338c92da3882ee4e18153bb36fcdf33af393aba8259Evan Cheng index += InstrSlots::NUM) { 339c92da3882ee4e18153bb36fcdf33af393aba8259Evan Cheng // skip deleted instructions 340c92da3882ee4e18153bb36fcdf33af393aba8259Evan Cheng while (index != end && !getInstructionFromIndex(index)) 341c92da3882ee4e18153bb36fcdf33af393aba8259Evan Cheng index += InstrSlots::NUM; 342c92da3882ee4e18153bb36fcdf33af393aba8259Evan Cheng if (index == end) break; 343c92da3882ee4e18153bb36fcdf33af393aba8259Evan Cheng 344c92da3882ee4e18153bb36fcdf33af393aba8259Evan Cheng MachineInstr *MI = getInstructionFromIndex(index); 34504ee5a1d9267e5e6fab8f088095fcb83c3c5cbd1Evan Cheng unsigned SrcReg, DstReg, SrcSubReg, DstSubReg; 34604ee5a1d9267e5e6fab8f088095fcb83c3c5cbd1Evan Cheng if (tii_->isMoveInstr(*MI, SrcReg, DstReg, SrcSubReg, DstSubReg)) 3475d446265c740c17ed12e693423f0363296670d60Evan Cheng if (SrcReg == li.reg || DstReg == li.reg) 3485d446265c740c17ed12e693423f0363296670d60Evan Cheng continue; 349c92da3882ee4e18153bb36fcdf33af393aba8259Evan Cheng for (unsigned i = 0; i != MI->getNumOperands(); ++i) { 350c92da3882ee4e18153bb36fcdf33af393aba8259Evan Cheng MachineOperand& mop = MI->getOperand(i); 351d735b8019b0f297d7c14b55adcd887af24d8e602Dan Gohman if (!mop.isReg()) 352c92da3882ee4e18153bb36fcdf33af393aba8259Evan Cheng continue; 353c92da3882ee4e18153bb36fcdf33af393aba8259Evan Cheng unsigned PhysReg = mop.getReg(); 3545d446265c740c17ed12e693423f0363296670d60Evan Cheng if (PhysReg == 0 || PhysReg == li.reg) 355c92da3882ee4e18153bb36fcdf33af393aba8259Evan Cheng continue; 3566f0d024a534af18d9e60b3ea757376cd8a3a980eDan Gohman if (TargetRegisterInfo::isVirtualRegister(PhysReg)) { 3575d446265c740c17ed12e693423f0363296670d60Evan Cheng if (!vrm.hasPhys(PhysReg)) 3585d446265c740c17ed12e693423f0363296670d60Evan Cheng continue; 359c92da3882ee4e18153bb36fcdf33af393aba8259Evan Cheng PhysReg = vrm.getPhys(PhysReg); 3605d446265c740c17ed12e693423f0363296670d60Evan Cheng } 3616f0d024a534af18d9e60b3ea757376cd8a3a980eDan Gohman if (PhysReg && tri_->regsOverlap(PhysReg, reg)) 362c92da3882ee4e18153bb36fcdf33af393aba8259Evan Cheng return true; 363c92da3882ee4e18153bb36fcdf33af393aba8259Evan Cheng } 364c92da3882ee4e18153bb36fcdf33af393aba8259Evan Cheng } 365c92da3882ee4e18153bb36fcdf33af393aba8259Evan Cheng } 366c92da3882ee4e18153bb36fcdf33af393aba8259Evan Cheng 367c92da3882ee4e18153bb36fcdf33af393aba8259Evan Cheng return false; 368c92da3882ee4e18153bb36fcdf33af393aba8259Evan Cheng} 369c92da3882ee4e18153bb36fcdf33af393aba8259Evan Cheng 3708f90b6eb2fd0125f5b779de80954944f9071fb87Evan Cheng/// conflictsWithPhysRegRef - Similar to conflictsWithPhysRegRef except 3718f90b6eb2fd0125f5b779de80954944f9071fb87Evan Cheng/// it can check use as well. 3728f90b6eb2fd0125f5b779de80954944f9071fb87Evan Chengbool LiveIntervals::conflictsWithPhysRegRef(LiveInterval &li, 3738f90b6eb2fd0125f5b779de80954944f9071fb87Evan Cheng unsigned Reg, bool CheckUse, 3748f90b6eb2fd0125f5b779de80954944f9071fb87Evan Cheng SmallPtrSet<MachineInstr*,32> &JoinedCopies) { 3758f90b6eb2fd0125f5b779de80954944f9071fb87Evan Cheng for (LiveInterval::Ranges::const_iterator 3768f90b6eb2fd0125f5b779de80954944f9071fb87Evan Cheng I = li.ranges.begin(), E = li.ranges.end(); I != E; ++I) { 3778f90b6eb2fd0125f5b779de80954944f9071fb87Evan Cheng for (unsigned index = getBaseIndex(I->start), 3788f90b6eb2fd0125f5b779de80954944f9071fb87Evan Cheng end = getBaseIndex(I->end-1) + InstrSlots::NUM; index != end; 3798f90b6eb2fd0125f5b779de80954944f9071fb87Evan Cheng index += InstrSlots::NUM) { 3808f90b6eb2fd0125f5b779de80954944f9071fb87Evan Cheng // Skip deleted instructions. 3818f90b6eb2fd0125f5b779de80954944f9071fb87Evan Cheng MachineInstr *MI = 0; 3828f90b6eb2fd0125f5b779de80954944f9071fb87Evan Cheng while (index != end) { 3838f90b6eb2fd0125f5b779de80954944f9071fb87Evan Cheng MI = getInstructionFromIndex(index); 3848f90b6eb2fd0125f5b779de80954944f9071fb87Evan Cheng if (MI) 3858f90b6eb2fd0125f5b779de80954944f9071fb87Evan Cheng break; 3868f90b6eb2fd0125f5b779de80954944f9071fb87Evan Cheng index += InstrSlots::NUM; 3878f90b6eb2fd0125f5b779de80954944f9071fb87Evan Cheng } 3888f90b6eb2fd0125f5b779de80954944f9071fb87Evan Cheng if (index == end) break; 3898f90b6eb2fd0125f5b779de80954944f9071fb87Evan Cheng 3908f90b6eb2fd0125f5b779de80954944f9071fb87Evan Cheng if (JoinedCopies.count(MI)) 3918f90b6eb2fd0125f5b779de80954944f9071fb87Evan Cheng continue; 3928f90b6eb2fd0125f5b779de80954944f9071fb87Evan Cheng for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) { 3938f90b6eb2fd0125f5b779de80954944f9071fb87Evan Cheng MachineOperand& MO = MI->getOperand(i); 3948f90b6eb2fd0125f5b779de80954944f9071fb87Evan Cheng if (!MO.isReg()) 3958f90b6eb2fd0125f5b779de80954944f9071fb87Evan Cheng continue; 3968f90b6eb2fd0125f5b779de80954944f9071fb87Evan Cheng if (MO.isUse() && !CheckUse) 3978f90b6eb2fd0125f5b779de80954944f9071fb87Evan Cheng continue; 3988f90b6eb2fd0125f5b779de80954944f9071fb87Evan Cheng unsigned PhysReg = MO.getReg(); 3998f90b6eb2fd0125f5b779de80954944f9071fb87Evan Cheng if (PhysReg == 0 || TargetRegisterInfo::isVirtualRegister(PhysReg)) 4008f90b6eb2fd0125f5b779de80954944f9071fb87Evan Cheng continue; 4018f90b6eb2fd0125f5b779de80954944f9071fb87Evan Cheng if (tri_->isSubRegister(Reg, PhysReg)) 4028f90b6eb2fd0125f5b779de80954944f9071fb87Evan Cheng return true; 4038f90b6eb2fd0125f5b779de80954944f9071fb87Evan Cheng } 4048f90b6eb2fd0125f5b779de80954944f9071fb87Evan Cheng } 4058f90b6eb2fd0125f5b779de80954944f9071fb87Evan Cheng } 4068f90b6eb2fd0125f5b779de80954944f9071fb87Evan Cheng 4078f90b6eb2fd0125f5b779de80954944f9071fb87Evan Cheng return false; 4088f90b6eb2fd0125f5b779de80954944f9071fb87Evan Cheng} 4098f90b6eb2fd0125f5b779de80954944f9071fb87Evan Cheng 4108f90b6eb2fd0125f5b779de80954944f9071fb87Evan Cheng 411be4f88a8b8bb3311e0dc4cde8533763d7923c3eaChris Lattnervoid LiveIntervals::printRegName(unsigned reg) const { 4126f0d024a534af18d9e60b3ea757376cd8a3a980eDan Gohman if (TargetRegisterInfo::isPhysicalRegister(reg)) 413e6d088acc90e422451e098555d383d4d65b6ce6bBill Wendling cerr << tri_->getName(reg); 4141a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos else 415e81561909d128c6e2d8033cb5465a49b2596b26aBill Wendling cerr << "%reg" << reg; 416ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos} 417ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos 418be4f88a8b8bb3311e0dc4cde8533763d7923c3eaChris Lattnervoid LiveIntervals::handleVirtualRegisterDef(MachineBasicBlock *mbb, 419ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos MachineBasicBlock::iterator mi, 4206b098dee286cc6fe5a5a476464d92dec5602e406Owen Anderson unsigned MIIdx, MachineOperand& MO, 421ef0732d25a9882c947984ae3f2afbef5463ba00fEvan Cheng unsigned MOIdx, 422be4f88a8b8bb3311e0dc4cde8533763d7923c3eaChris Lattner LiveInterval &interval) { 423bdc679d564e67a81792e463f6614b0088f975025Bill Wendling DOUT << "\t\tregister: "; DEBUG(printRegName(interval.reg)); 4241a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos LiveVariables::VarInfo& vi = lv_->getVarInfo(interval.reg); 4251a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos 426419852ca8a01aecde4c0e20af6b7bd6450e70f87Evan Cheng if (mi->getOpcode() == TargetInstrInfo::IMPLICIT_DEF) { 427419852ca8a01aecde4c0e20af6b7bd6450e70f87Evan Cheng DOUT << "is a implicit_def\n"; 428419852ca8a01aecde4c0e20af6b7bd6450e70f87Evan Cheng return; 429419852ca8a01aecde4c0e20af6b7bd6450e70f87Evan Cheng } 430419852ca8a01aecde4c0e20af6b7bd6450e70f87Evan Cheng 431706515727c6d024015fffded2b3109a4f0ac5299Alkis Evlogimenos // Virtual registers may be defined multiple times (due to phi 432706515727c6d024015fffded2b3109a4f0ac5299Alkis Evlogimenos // elimination and 2-addr elimination). Much of what we do only has to be 433706515727c6d024015fffded2b3109a4f0ac5299Alkis Evlogimenos // done once for the vreg. We use an empty interval to detect the first 4341a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // time we see a vreg. 4351a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos if (interval.empty()) { 4361a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // Get the Idx of the defining instructions. 4376b128bdc58a496e9f08e4d09416330320761baffChris Lattner unsigned defIndex = getDefIndex(MIIdx); 43886b49f8e2de796cb46c7c8b6a4c4900533fd53f4Dale Johannesen // Earlyclobbers move back one. 43986b49f8e2de796cb46c7c8b6a4c4900533fd53f4Dale Johannesen if (MO.isEarlyClobber()) 44086b49f8e2de796cb46c7c8b6a4c4900533fd53f4Dale Johannesen defIndex = getUseIndex(MIIdx); 4417ecb38be0a533e7b9c7d3b8e9b5c8a6fa5f6b349Evan Cheng VNInfo *ValNo; 442c8d044e4f779fdcfc5e7d592927740fd8f672a70Evan Cheng MachineInstr *CopyMI = NULL; 44304ee5a1d9267e5e6fab8f088095fcb83c3c5cbd1Evan Cheng unsigned SrcReg, DstReg, SrcSubReg, DstSubReg; 444c8d044e4f779fdcfc5e7d592927740fd8f672a70Evan Cheng if (mi->getOpcode() == TargetInstrInfo::EXTRACT_SUBREG || 4457e073baedb8232b9519dbe15ea141ff98ccfe6aeEvan Cheng mi->getOpcode() == TargetInstrInfo::INSERT_SUBREG || 44697121ba2afb8d566ff1bf5c4e8fc5d4077940a7fDan Gohman mi->getOpcode() == TargetInstrInfo::SUBREG_TO_REG || 44704ee5a1d9267e5e6fab8f088095fcb83c3c5cbd1Evan Cheng tii_->isMoveInstr(*mi, SrcReg, DstReg, SrcSubReg, DstSubReg)) 448c8d044e4f779fdcfc5e7d592927740fd8f672a70Evan Cheng CopyMI = mi; 4495379f412bc6ac6171f3bd73930197bfce88c2faaEvan Cheng // Earlyclobbers move back one. 450857c4e01f85601cf2084adb860616256ee47c177Lang Hames ValNo = interval.getNextValue(defIndex, CopyMI, true, VNInfoAllocator); 4517ecb38be0a533e7b9c7d3b8e9b5c8a6fa5f6b349Evan Cheng 4527ecb38be0a533e7b9c7d3b8e9b5c8a6fa5f6b349Evan Cheng assert(ValNo->id == 0 && "First value in interval is not 0?"); 4531a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos 4541a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // Loop over all of the blocks that the vreg is defined in. There are 4551a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // two cases we have to handle here. The most common case is a vreg 4561a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // whose lifetime is contained within a basic block. In this case there 4571a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // will be a single kill, in MBB, which comes after the definition. 4581a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos if (vi.Kills.size() == 1 && vi.Kills[0]->getParent() == mbb) { 4591a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // FIXME: what about dead vars? 4601a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos unsigned killIdx; 4611a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos if (vi.Kills[0] != mi) 4621a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos killIdx = getUseIndex(getInstructionIndex(vi.Kills[0]))+1; 4631a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos else 4641a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos killIdx = defIndex+1; 4651a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos 4661a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // If the kill happens after the definition, we have an intra-block 4671a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // live range. 4681a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos if (killIdx > defIndex) { 469493a3d015cbb2bcc18d9293a4dec3b35c7493818Jeffrey Yasskin assert(vi.AliveBlocks.empty() && 4701a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos "Shouldn't be alive across any blocks!"); 4717ecb38be0a533e7b9c7d3b8e9b5c8a6fa5f6b349Evan Cheng LiveRange LR(defIndex, killIdx, ValNo); 4721a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos interval.addRange(LR); 473bdc679d564e67a81792e463f6614b0088f975025Bill Wendling DOUT << " +" << LR << "\n"; 474f3bb2e65d12857f83b273f4ecab013680310bbbcEvan Cheng interval.addKill(ValNo, killIdx); 4751a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos return; 4761a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos } 4771a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos } 4786097d13b2a624048dbe02e39e2dfb23bfa269b64Chris Lattner 4791a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // The other case we handle is when a virtual register lives to the end 4801a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // of the defining block, potentially live across some blocks, then is 4811a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // live into some number of blocks, but gets killed. Start by adding a 4821a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // range that goes from this definition to the end of the defining block. 4837fbad27cfb7298c707e50af10609d463900d7211Owen Anderson LiveRange NewLR(defIndex, getMBBEndIdx(mbb)+1, ValNo); 484bdc679d564e67a81792e463f6614b0088f975025Bill Wendling DOUT << " +" << NewLR; 4851a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos interval.addRange(NewLR); 4861a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos 4871a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // Iterate over all of the blocks that the variable is completely 4881a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // live in, adding [insrtIndex(begin), instrIndex(end)+4) to the 4891a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // live interval. 490493a3d015cbb2bcc18d9293a4dec3b35c7493818Jeffrey Yasskin for (SparseBitVector<>::iterator I = vi.AliveBlocks.begin(), 491493a3d015cbb2bcc18d9293a4dec3b35c7493818Jeffrey Yasskin E = vi.AliveBlocks.end(); I != E; ++I) { 492493a3d015cbb2bcc18d9293a4dec3b35c7493818Jeffrey Yasskin LiveRange LR(getMBBStartIdx(*I), 493493a3d015cbb2bcc18d9293a4dec3b35c7493818Jeffrey Yasskin getMBBEndIdx(*I)+1, // MBB ends at -1. 4944a829ecc54cdcb0192550639556a18728af5119cDan Gohman ValNo); 4954a829ecc54cdcb0192550639556a18728af5119cDan Gohman interval.addRange(LR); 4964a829ecc54cdcb0192550639556a18728af5119cDan Gohman DOUT << " +" << LR; 4971a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos } 4981a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos 4991a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // Finally, this virtual register is live from the start of any killing 5001a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // block to the 'use' slot of the killing instruction. 5011a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos for (unsigned i = 0, e = vi.Kills.size(); i != e; ++i) { 5021a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos MachineInstr *Kill = vi.Kills[i]; 5038df786012dc6b875f31ba4152e09c6e0098082eeEvan Cheng unsigned killIdx = getUseIndex(getInstructionIndex(Kill))+1; 504428b92eb83b457b71d29d1d4b7900d36a0ce9a53Chris Lattner LiveRange LR(getMBBStartIdx(Kill->getParent()), 5057ecb38be0a533e7b9c7d3b8e9b5c8a6fa5f6b349Evan Cheng killIdx, ValNo); 5061a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos interval.addRange(LR); 507f3bb2e65d12857f83b273f4ecab013680310bbbcEvan Cheng interval.addKill(ValNo, killIdx); 508bdc679d564e67a81792e463f6614b0088f975025Bill Wendling DOUT << " +" << LR; 5091a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos } 5101a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos 5111a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos } else { 5121a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // If this is the second time we see a virtual register definition, it 5131a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // must be due to phi elimination or two addr elimination. If this is 514bf105c842450d3308d024be203ddd533f37051ecEvan Cheng // the result of two address elimination, then the vreg is one of the 515bf105c842450d3308d024be203ddd533f37051ecEvan Cheng // def-and-use register operand. 516d9df5017040489303acb57bdd8697ef0f8bafc08Bob Wilson if (mi->isRegTiedToUseOperand(MOIdx)) { 5171a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // If this is a two-address definition, then we have already processed 5181a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // the live range. The only problem is that we didn't realize there 5191a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // are actually two values in the live interval. Because of this we 5201a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // need to take the LiveRegion that defines this register and split it 5211a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // into two values. 522a07cec9e24a286157541d2337cd66b24cd116586Evan Cheng assert(interval.containsOneValue()); 523a07cec9e24a286157541d2337cd66b24cd116586Evan Cheng unsigned DefIndex = getDefIndex(interval.getValNumInfo(0)->def); 5246b128bdc58a496e9f08e4d09416330320761baffChris Lattner unsigned RedefIndex = getDefIndex(MIIdx); 525fb11288109329cb736d9f49769581a0d0c23fe19Evan Cheng if (MO.isEarlyClobber()) 526fb11288109329cb736d9f49769581a0d0c23fe19Evan Cheng RedefIndex = getUseIndex(MIIdx); 5271a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos 5284f8ff168de12eabdeb4b9437bf9402489ecf85cbEvan Cheng const LiveRange *OldLR = interval.getLiveRangeContaining(RedefIndex-1); 5297ecb38be0a533e7b9c7d3b8e9b5c8a6fa5f6b349Evan Cheng VNInfo *OldValNo = OldLR->valno; 5304f8ff168de12eabdeb4b9437bf9402489ecf85cbEvan Cheng 5311a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // Delete the initial value, which should be short and continuous, 532be4f88a8b8bb3311e0dc4cde8533763d7923c3eaChris Lattner // because the 2-addr copy must be in the same MBB as the redef. 5331a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos interval.removeRange(DefIndex, RedefIndex); 534706515727c6d024015fffded2b3109a4f0ac5299Alkis Evlogimenos 535be4f88a8b8bb3311e0dc4cde8533763d7923c3eaChris Lattner // Two-address vregs should always only be redefined once. This means 536be4f88a8b8bb3311e0dc4cde8533763d7923c3eaChris Lattner // that at this point, there should be exactly one value number in it. 537be4f88a8b8bb3311e0dc4cde8533763d7923c3eaChris Lattner assert(interval.containsOneValue() && "Unexpected 2-addr liveint!"); 538be4f88a8b8bb3311e0dc4cde8533763d7923c3eaChris Lattner 53991725b75852443923b419fd23215194cfc65dd88Chris Lattner // The new value number (#1) is defined by the instruction we claimed 54091725b75852443923b419fd23215194cfc65dd88Chris Lattner // defined value #0. 541c8d044e4f779fdcfc5e7d592927740fd8f672a70Evan Cheng VNInfo *ValNo = interval.getNextValue(OldValNo->def, OldValNo->copy, 542857c4e01f85601cf2084adb860616256ee47c177Lang Hames false, // update at * 543c8d044e4f779fdcfc5e7d592927740fd8f672a70Evan Cheng VNInfoAllocator); 544857c4e01f85601cf2084adb860616256ee47c177Lang Hames ValNo->setFlags(OldValNo->getFlags()); // * <- updating here 545857c4e01f85601cf2084adb860616256ee47c177Lang Hames 54691725b75852443923b419fd23215194cfc65dd88Chris Lattner // Value#0 is now defined by the 2-addr instruction. 547c8d044e4f779fdcfc5e7d592927740fd8f672a70Evan Cheng OldValNo->def = RedefIndex; 548c8d044e4f779fdcfc5e7d592927740fd8f672a70Evan Cheng OldValNo->copy = 0; 549fb11288109329cb736d9f49769581a0d0c23fe19Evan Cheng if (MO.isEarlyClobber()) 550857c4e01f85601cf2084adb860616256ee47c177Lang Hames OldValNo->setHasRedefByEC(true); 551be4f88a8b8bb3311e0dc4cde8533763d7923c3eaChris Lattner 552be4f88a8b8bb3311e0dc4cde8533763d7923c3eaChris Lattner // Add the new live interval which replaces the range for the input copy. 553be4f88a8b8bb3311e0dc4cde8533763d7923c3eaChris Lattner LiveRange LR(DefIndex, RedefIndex, ValNo); 554bdc679d564e67a81792e463f6614b0088f975025Bill Wendling DOUT << " replace range with " << LR; 5551a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos interval.addRange(LR); 556f3bb2e65d12857f83b273f4ecab013680310bbbcEvan Cheng interval.addKill(ValNo, RedefIndex); 5571a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos 5581a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // If this redefinition is dead, we need to add a dummy unit live 5591a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // range covering the def slot. 5606b098dee286cc6fe5a5a476464d92dec5602e406Owen Anderson if (MO.isDead()) 5617ecb38be0a533e7b9c7d3b8e9b5c8a6fa5f6b349Evan Cheng interval.addRange(LiveRange(RedefIndex, RedefIndex+1, OldValNo)); 5621a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos 56356fdd7af884a35673fb6dd3e01333960922c3ac2Evan Cheng DOUT << " RESULT: "; 5646f0d024a534af18d9e60b3ea757376cd8a3a980eDan Gohman interval.print(DOUT, tri_); 5651a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos 5661a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos } else { 5671a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // Otherwise, this must be because of phi elimination. If this is the 5681a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // first redefinition of the vreg that we have seen, go back and change 5691a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // the live range in the PHI block to be a different value number. 5701a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos if (interval.containsOneValue()) { 5711a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos assert(vi.Kills.size() == 1 && 5721a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos "PHI elimination vreg should have one kill, the PHI itself!"); 5731a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos 5741a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // Remove the old range that we now know has an incorrect number. 575f3bb2e65d12857f83b273f4ecab013680310bbbcEvan Cheng VNInfo *VNI = interval.getValNumInfo(0); 5761a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos MachineInstr *Killer = vi.Kills[0]; 577428b92eb83b457b71d29d1d4b7900d36a0ce9a53Chris Lattner unsigned Start = getMBBStartIdx(Killer->getParent()); 5781a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos unsigned End = getUseIndex(getInstructionIndex(Killer))+1; 57956fdd7af884a35673fb6dd3e01333960922c3ac2Evan Cheng DOUT << " Removing [" << Start << "," << End << "] from: "; 5806f0d024a534af18d9e60b3ea757376cd8a3a980eDan Gohman interval.print(DOUT, tri_); DOUT << "\n"; 5811a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos interval.removeRange(Start, End); 582857c4e01f85601cf2084adb860616256ee47c177Lang Hames VNI->setHasPHIKill(true); 5836f0d024a534af18d9e60b3ea757376cd8a3a980eDan Gohman DOUT << " RESULT: "; interval.print(DOUT, tri_); 5841a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos 585be4f88a8b8bb3311e0dc4cde8533763d7923c3eaChris Lattner // Replace the interval with one of a NEW value number. Note that this 586be4f88a8b8bb3311e0dc4cde8533763d7923c3eaChris Lattner // value number isn't actually defined by an instruction, weird huh? :) 587d21c31610c4a10e9e638f4221b5df89ea932e258Lang Hames LiveRange LR(Start, End, interval.getNextValue(Start, 0, false, VNInfoAllocator)); 588857c4e01f85601cf2084adb860616256ee47c177Lang Hames LR.valno->setIsPHIDef(true); 589bdc679d564e67a81792e463f6614b0088f975025Bill Wendling DOUT << " replace range with " << LR; 5901a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos interval.addRange(LR); 591f3bb2e65d12857f83b273f4ecab013680310bbbcEvan Cheng interval.addKill(LR.valno, End); 5926f0d024a534af18d9e60b3ea757376cd8a3a980eDan Gohman DOUT << " RESULT: "; interval.print(DOUT, tri_); 5931a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos } 5941a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos 5951a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // In the case of PHI elimination, each variable definition is only 5961a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // live until the end of the block. We've already taken care of the 5971a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // rest of the live range. 5986b128bdc58a496e9f08e4d09416330320761baffChris Lattner unsigned defIndex = getDefIndex(MIIdx); 599fb11288109329cb736d9f49769581a0d0c23fe19Evan Cheng if (MO.isEarlyClobber()) 600fb11288109329cb736d9f49769581a0d0c23fe19Evan Cheng defIndex = getUseIndex(MIIdx); 60191725b75852443923b419fd23215194cfc65dd88Chris Lattner 6027ecb38be0a533e7b9c7d3b8e9b5c8a6fa5f6b349Evan Cheng VNInfo *ValNo; 603c8d044e4f779fdcfc5e7d592927740fd8f672a70Evan Cheng MachineInstr *CopyMI = NULL; 60404ee5a1d9267e5e6fab8f088095fcb83c3c5cbd1Evan Cheng unsigned SrcReg, DstReg, SrcSubReg, DstSubReg; 605c8d044e4f779fdcfc5e7d592927740fd8f672a70Evan Cheng if (mi->getOpcode() == TargetInstrInfo::EXTRACT_SUBREG || 6067e073baedb8232b9519dbe15ea141ff98ccfe6aeEvan Cheng mi->getOpcode() == TargetInstrInfo::INSERT_SUBREG || 60797121ba2afb8d566ff1bf5c4e8fc5d4077940a7fDan Gohman mi->getOpcode() == TargetInstrInfo::SUBREG_TO_REG || 60804ee5a1d9267e5e6fab8f088095fcb83c3c5cbd1Evan Cheng tii_->isMoveInstr(*mi, SrcReg, DstReg, SrcSubReg, DstSubReg)) 609c8d044e4f779fdcfc5e7d592927740fd8f672a70Evan Cheng CopyMI = mi; 610857c4e01f85601cf2084adb860616256ee47c177Lang Hames ValNo = interval.getNextValue(defIndex, CopyMI, true, VNInfoAllocator); 61191725b75852443923b419fd23215194cfc65dd88Chris Lattner 6127fbad27cfb7298c707e50af10609d463900d7211Owen Anderson unsigned killIndex = getMBBEndIdx(mbb) + 1; 6137ecb38be0a533e7b9c7d3b8e9b5c8a6fa5f6b349Evan Cheng LiveRange LR(defIndex, killIndex, ValNo); 6141a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos interval.addRange(LR); 615c3fc7d9ec9b495c8a88cd854247105c296d3aabdEvan Cheng interval.addKill(ValNo, killIndex); 616857c4e01f85601cf2084adb860616256ee47c177Lang Hames ValNo->setHasPHIKill(true); 617bdc679d564e67a81792e463f6614b0088f975025Bill Wendling DOUT << " +" << LR; 618dd2cc65f34f9b7bfda1cd0c42becedfc361d46f8Alkis Evlogimenos } 6191a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos } 620ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos 621bdc679d564e67a81792e463f6614b0088f975025Bill Wendling DOUT << '\n'; 622ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos} 623ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos 624f35fef7060c465dd7b578bf6339a18e8a8911888Chris Lattnervoid LiveIntervals::handlePhysicalRegisterDef(MachineBasicBlock *MBB, 625ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos MachineBasicBlock::iterator mi, 6266b128bdc58a496e9f08e4d09416330320761baffChris Lattner unsigned MIIdx, 6276b098dee286cc6fe5a5a476464d92dec5602e406Owen Anderson MachineOperand& MO, 62891725b75852443923b419fd23215194cfc65dd88Chris Lattner LiveInterval &interval, 629c8d044e4f779fdcfc5e7d592927740fd8f672a70Evan Cheng MachineInstr *CopyMI) { 6301a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // A physical register cannot be live across basic block, so its 6311a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // lifetime must end somewhere in its defining basic block. 632bdc679d564e67a81792e463f6614b0088f975025Bill Wendling DOUT << "\t\tregister: "; DEBUG(printRegName(interval.reg)); 6331a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos 6346b128bdc58a496e9f08e4d09416330320761baffChris Lattner unsigned baseIndex = MIIdx; 6351a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos unsigned start = getDefIndex(baseIndex); 63686b49f8e2de796cb46c7c8b6a4c4900533fd53f4Dale Johannesen // Earlyclobbers move back one. 63786b49f8e2de796cb46c7c8b6a4c4900533fd53f4Dale Johannesen if (MO.isEarlyClobber()) 63886b49f8e2de796cb46c7c8b6a4c4900533fd53f4Dale Johannesen start = getUseIndex(MIIdx); 6391a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos unsigned end = start; 6401a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos 6411a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // If it is not used after definition, it is considered dead at 6421a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // the instruction defining it. Hence its interval is: 6431a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // [defSlot(def), defSlot(def)+1) 6446b098dee286cc6fe5a5a476464d92dec5602e406Owen Anderson if (MO.isDead()) { 645bdc679d564e67a81792e463f6614b0088f975025Bill Wendling DOUT << " dead"; 64686b49f8e2de796cb46c7c8b6a4c4900533fd53f4Dale Johannesen end = start + 1; 647ab4b66d4c279e8cd9e448687020fc838e7881dbcChris Lattner goto exit; 6481a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos } 649ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos 6501a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // If it is not dead on definition, it must be killed by a 6511a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // subsequent instruction. Hence its interval is: 6521a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // [defSlot(def), useSlot(kill)+1) 6537fbad27cfb7298c707e50af10609d463900d7211Owen Anderson baseIndex += InstrSlots::NUM; 6545ab6f5fe666d0e3403d9b777324d1a1999118153Chris Lattner while (++mi != MBB->end()) { 6557fbad27cfb7298c707e50af10609d463900d7211Owen Anderson while (baseIndex / InstrSlots::NUM < i2miMap_.size() && 6567fbad27cfb7298c707e50af10609d463900d7211Owen Anderson getInstructionFromIndex(baseIndex) == 0) 6577fbad27cfb7298c707e50af10609d463900d7211Owen Anderson baseIndex += InstrSlots::NUM; 6586130f66eaae89f8878590796977678afa8448926Evan Cheng if (mi->killsRegister(interval.reg, tri_)) { 659bdc679d564e67a81792e463f6614b0088f975025Bill Wendling DOUT << " killed"; 660ab4b66d4c279e8cd9e448687020fc838e7881dbcChris Lattner end = getUseIndex(baseIndex) + 1; 661ab4b66d4c279e8cd9e448687020fc838e7881dbcChris Lattner goto exit; 662c45288e06bfe7d0b0e74eff350d280fa6c944373Evan Cheng } else { 663c45288e06bfe7d0b0e74eff350d280fa6c944373Evan Cheng int DefIdx = mi->findRegisterDefOperandIdx(interval.reg, false, tri_); 664c45288e06bfe7d0b0e74eff350d280fa6c944373Evan Cheng if (DefIdx != -1) { 665c45288e06bfe7d0b0e74eff350d280fa6c944373Evan Cheng if (mi->isRegTiedToUseOperand(DefIdx)) { 666c45288e06bfe7d0b0e74eff350d280fa6c944373Evan Cheng // Two-address instruction. 667c45288e06bfe7d0b0e74eff350d280fa6c944373Evan Cheng end = getDefIndex(baseIndex); 668c45288e06bfe7d0b0e74eff350d280fa6c944373Evan Cheng if (mi->getOperand(DefIdx).isEarlyClobber()) 669c45288e06bfe7d0b0e74eff350d280fa6c944373Evan Cheng end = getUseIndex(baseIndex); 670c45288e06bfe7d0b0e74eff350d280fa6c944373Evan Cheng } else { 671c45288e06bfe7d0b0e74eff350d280fa6c944373Evan Cheng // Another instruction redefines the register before it is ever read. 672c45288e06bfe7d0b0e74eff350d280fa6c944373Evan Cheng // Then the register is essentially dead at the instruction that defines 673c45288e06bfe7d0b0e74eff350d280fa6c944373Evan Cheng // it. Hence its interval is: 674c45288e06bfe7d0b0e74eff350d280fa6c944373Evan Cheng // [defSlot(def), defSlot(def)+1) 675c45288e06bfe7d0b0e74eff350d280fa6c944373Evan Cheng DOUT << " dead"; 676c45288e06bfe7d0b0e74eff350d280fa6c944373Evan Cheng end = start + 1; 677c45288e06bfe7d0b0e74eff350d280fa6c944373Evan Cheng } 678c45288e06bfe7d0b0e74eff350d280fa6c944373Evan Cheng goto exit; 679c45288e06bfe7d0b0e74eff350d280fa6c944373Evan Cheng } 680f35fef7060c465dd7b578bf6339a18e8a8911888Chris Lattner } 6817fbad27cfb7298c707e50af10609d463900d7211Owen Anderson 6827fbad27cfb7298c707e50af10609d463900d7211Owen Anderson baseIndex += InstrSlots::NUM; 6831a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos } 6845ab6f5fe666d0e3403d9b777324d1a1999118153Chris Lattner 6855ab6f5fe666d0e3403d9b777324d1a1999118153Chris Lattner // The only case we should have a dead physreg here without a killing or 6865ab6f5fe666d0e3403d9b777324d1a1999118153Chris Lattner // instruction where we know it's dead is if it is live-in to the function 687d521bc983b32da71b85d42dd30da87079afa5728Evan Cheng // and never used. Another possible case is the implicit use of the 688d521bc983b32da71b85d42dd30da87079afa5728Evan Cheng // physical register has been deleted by two-address pass. 68986b49f8e2de796cb46c7c8b6a4c4900533fd53f4Dale Johannesen end = start + 1; 69002ba13c9897ae2b19f9201e57460d7ee2b753a0bAlkis Evlogimenos 691ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenosexit: 6921a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos assert(start < end && "did not find end of interval?"); 693f768bba43f5c036039851d2fcca8212edca18467Chris Lattner 69424a3cc4c83e5edb25fadf7b8979a26b4451795c6Evan Cheng // Already exists? Extend old live interval. 69524a3cc4c83e5edb25fadf7b8979a26b4451795c6Evan Cheng LiveInterval::iterator OldLR = interval.FindLiveRangeContaining(start); 6965379f412bc6ac6171f3bd73930197bfce88c2faaEvan Cheng bool Extend = OldLR != interval.end(); 6975379f412bc6ac6171f3bd73930197bfce88c2faaEvan Cheng VNInfo *ValNo = Extend 698857c4e01f85601cf2084adb860616256ee47c177Lang Hames ? OldLR->valno : interval.getNextValue(start, CopyMI, true, VNInfoAllocator); 6995379f412bc6ac6171f3bd73930197bfce88c2faaEvan Cheng if (MO.isEarlyClobber() && Extend) 700857c4e01f85601cf2084adb860616256ee47c177Lang Hames ValNo->setHasRedefByEC(true); 7017ecb38be0a533e7b9c7d3b8e9b5c8a6fa5f6b349Evan Cheng LiveRange LR(start, end, ValNo); 7021a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos interval.addRange(LR); 703f3bb2e65d12857f83b273f4ecab013680310bbbcEvan Cheng interval.addKill(LR.valno, end); 704bdc679d564e67a81792e463f6614b0088f975025Bill Wendling DOUT << " +" << LR << '\n'; 705ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos} 706ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos 707f35fef7060c465dd7b578bf6339a18e8a8911888Chris Lattnervoid LiveIntervals::handleRegisterDef(MachineBasicBlock *MBB, 708f35fef7060c465dd7b578bf6339a18e8a8911888Chris Lattner MachineBasicBlock::iterator MI, 7096b128bdc58a496e9f08e4d09416330320761baffChris Lattner unsigned MIIdx, 710ef0732d25a9882c947984ae3f2afbef5463ba00fEvan Cheng MachineOperand& MO, 711ef0732d25a9882c947984ae3f2afbef5463ba00fEvan Cheng unsigned MOIdx) { 7126b098dee286cc6fe5a5a476464d92dec5602e406Owen Anderson if (TargetRegisterInfo::isVirtualRegister(MO.getReg())) 713ef0732d25a9882c947984ae3f2afbef5463ba00fEvan Cheng handleVirtualRegisterDef(MBB, MI, MIIdx, MO, MOIdx, 7146b098dee286cc6fe5a5a476464d92dec5602e406Owen Anderson getOrCreateInterval(MO.getReg())); 7156b098dee286cc6fe5a5a476464d92dec5602e406Owen Anderson else if (allocatableRegs_[MO.getReg()]) { 716c8d044e4f779fdcfc5e7d592927740fd8f672a70Evan Cheng MachineInstr *CopyMI = NULL; 71704ee5a1d9267e5e6fab8f088095fcb83c3c5cbd1Evan Cheng unsigned SrcReg, DstReg, SrcSubReg, DstSubReg; 718c8d044e4f779fdcfc5e7d592927740fd8f672a70Evan Cheng if (MI->getOpcode() == TargetInstrInfo::EXTRACT_SUBREG || 7197e073baedb8232b9519dbe15ea141ff98ccfe6aeEvan Cheng MI->getOpcode() == TargetInstrInfo::INSERT_SUBREG || 72097121ba2afb8d566ff1bf5c4e8fc5d4077940a7fDan Gohman MI->getOpcode() == TargetInstrInfo::SUBREG_TO_REG || 72104ee5a1d9267e5e6fab8f088095fcb83c3c5cbd1Evan Cheng tii_->isMoveInstr(*MI, SrcReg, DstReg, SrcSubReg, DstSubReg)) 722c8d044e4f779fdcfc5e7d592927740fd8f672a70Evan Cheng CopyMI = MI; 723c45288e06bfe7d0b0e74eff350d280fa6c944373Evan Cheng handlePhysicalRegisterDef(MBB, MI, MIIdx, MO, 7246b098dee286cc6fe5a5a476464d92dec5602e406Owen Anderson getOrCreateInterval(MO.getReg()), CopyMI); 72524a3cc4c83e5edb25fadf7b8979a26b4451795c6Evan Cheng // Def of a register also defines its sub-registers. 7266b098dee286cc6fe5a5a476464d92dec5602e406Owen Anderson for (const unsigned* AS = tri_->getSubRegisters(MO.getReg()); *AS; ++AS) 7276130f66eaae89f8878590796977678afa8448926Evan Cheng // If MI also modifies the sub-register explicitly, avoid processing it 7286130f66eaae89f8878590796977678afa8448926Evan Cheng // more than once. Do not pass in TRI here so it checks for exact match. 7296130f66eaae89f8878590796977678afa8448926Evan Cheng if (!MI->modifiesRegister(*AS)) 730c45288e06bfe7d0b0e74eff350d280fa6c944373Evan Cheng handlePhysicalRegisterDef(MBB, MI, MIIdx, MO, 7316b098dee286cc6fe5a5a476464d92dec5602e406Owen Anderson getOrCreateInterval(*AS), 0); 732f35fef7060c465dd7b578bf6339a18e8a8911888Chris Lattner } 7334d46e1e521c0df1990ea50f8146d22bd77ea71a6Alkis Evlogimenos} 7344d46e1e521c0df1990ea50f8146d22bd77ea71a6Alkis Evlogimenos 735b371f457b0ea4a652a9f526ba4375c80ae542252Evan Chengvoid LiveIntervals::handleLiveInRegister(MachineBasicBlock *MBB, 7369b25b8ca24d6df2e097741dcc15016772ee4eda7Jim Laskey unsigned MIIdx, 73724a3cc4c83e5edb25fadf7b8979a26b4451795c6Evan Cheng LiveInterval &interval, bool isAlias) { 738b371f457b0ea4a652a9f526ba4375c80ae542252Evan Cheng DOUT << "\t\tlivein register: "; DEBUG(printRegName(interval.reg)); 739b371f457b0ea4a652a9f526ba4375c80ae542252Evan Cheng 740b371f457b0ea4a652a9f526ba4375c80ae542252Evan Cheng // Look for kills, if it reaches a def before it's killed, then it shouldn't 741b371f457b0ea4a652a9f526ba4375c80ae542252Evan Cheng // be considered a livein. 742b371f457b0ea4a652a9f526ba4375c80ae542252Evan Cheng MachineBasicBlock::iterator mi = MBB->begin(); 7439b25b8ca24d6df2e097741dcc15016772ee4eda7Jim Laskey unsigned baseIndex = MIIdx; 7449b25b8ca24d6df2e097741dcc15016772ee4eda7Jim Laskey unsigned start = baseIndex; 74599500aeb7c9a05db57e228544a3f81de2faf24efOwen Anderson while (baseIndex / InstrSlots::NUM < i2miMap_.size() && 74699500aeb7c9a05db57e228544a3f81de2faf24efOwen Anderson getInstructionFromIndex(baseIndex) == 0) 74799500aeb7c9a05db57e228544a3f81de2faf24efOwen Anderson baseIndex += InstrSlots::NUM; 74899500aeb7c9a05db57e228544a3f81de2faf24efOwen Anderson unsigned end = baseIndex; 7490076c616e8abc2ecf36600a7ac20ec784420cdc4Evan Cheng bool SeenDefUse = false; 75099500aeb7c9a05db57e228544a3f81de2faf24efOwen Anderson 751b371f457b0ea4a652a9f526ba4375c80ae542252Evan Cheng while (mi != MBB->end()) { 7526130f66eaae89f8878590796977678afa8448926Evan Cheng if (mi->killsRegister(interval.reg, tri_)) { 753b371f457b0ea4a652a9f526ba4375c80ae542252Evan Cheng DOUT << " killed"; 754b371f457b0ea4a652a9f526ba4375c80ae542252Evan Cheng end = getUseIndex(baseIndex) + 1; 7550076c616e8abc2ecf36600a7ac20ec784420cdc4Evan Cheng SeenDefUse = true; 756d21c31610c4a10e9e638f4221b5df89ea932e258Lang Hames break; 7576130f66eaae89f8878590796977678afa8448926Evan Cheng } else if (mi->modifiesRegister(interval.reg, tri_)) { 758b371f457b0ea4a652a9f526ba4375c80ae542252Evan Cheng // Another instruction redefines the register before it is ever read. 759b371f457b0ea4a652a9f526ba4375c80ae542252Evan Cheng // Then the register is essentially dead at the instruction that defines 760b371f457b0ea4a652a9f526ba4375c80ae542252Evan Cheng // it. Hence its interval is: 761b371f457b0ea4a652a9f526ba4375c80ae542252Evan Cheng // [defSlot(def), defSlot(def)+1) 762b371f457b0ea4a652a9f526ba4375c80ae542252Evan Cheng DOUT << " dead"; 763b371f457b0ea4a652a9f526ba4375c80ae542252Evan Cheng end = getDefIndex(start) + 1; 7640076c616e8abc2ecf36600a7ac20ec784420cdc4Evan Cheng SeenDefUse = true; 765d21c31610c4a10e9e638f4221b5df89ea932e258Lang Hames break; 766b371f457b0ea4a652a9f526ba4375c80ae542252Evan Cheng } 767b371f457b0ea4a652a9f526ba4375c80ae542252Evan Cheng 768b371f457b0ea4a652a9f526ba4375c80ae542252Evan Cheng baseIndex += InstrSlots::NUM; 769b371f457b0ea4a652a9f526ba4375c80ae542252Evan Cheng ++mi; 7700076c616e8abc2ecf36600a7ac20ec784420cdc4Evan Cheng if (mi != MBB->end()) { 7710076c616e8abc2ecf36600a7ac20ec784420cdc4Evan Cheng while (baseIndex / InstrSlots::NUM < i2miMap_.size() && 7720076c616e8abc2ecf36600a7ac20ec784420cdc4Evan Cheng getInstructionFromIndex(baseIndex) == 0) 7730076c616e8abc2ecf36600a7ac20ec784420cdc4Evan Cheng baseIndex += InstrSlots::NUM; 7740076c616e8abc2ecf36600a7ac20ec784420cdc4Evan Cheng } 775b371f457b0ea4a652a9f526ba4375c80ae542252Evan Cheng } 776b371f457b0ea4a652a9f526ba4375c80ae542252Evan Cheng 77775611fb4e6ab253be30ac29a2b15e9bf8c1d146eEvan Cheng // Live-in register might not be used at all. 7780076c616e8abc2ecf36600a7ac20ec784420cdc4Evan Cheng if (!SeenDefUse) { 779292da949f6c87d6499425d64d37d7c5870ec57adEvan Cheng if (isAlias) { 780292da949f6c87d6499425d64d37d7c5870ec57adEvan Cheng DOUT << " dead"; 78175611fb4e6ab253be30ac29a2b15e9bf8c1d146eEvan Cheng end = getDefIndex(MIIdx) + 1; 782292da949f6c87d6499425d64d37d7c5870ec57adEvan Cheng } else { 783292da949f6c87d6499425d64d37d7c5870ec57adEvan Cheng DOUT << " live through"; 784292da949f6c87d6499425d64d37d7c5870ec57adEvan Cheng end = baseIndex; 785292da949f6c87d6499425d64d37d7c5870ec57adEvan Cheng } 78624a3cc4c83e5edb25fadf7b8979a26b4451795c6Evan Cheng } 78724a3cc4c83e5edb25fadf7b8979a26b4451795c6Evan Cheng 788d21c31610c4a10e9e638f4221b5df89ea932e258Lang Hames VNInfo *vni = interval.getNextValue(start, 0, false, VNInfoAllocator); 789d21c31610c4a10e9e638f4221b5df89ea932e258Lang Hames vni->setIsPHIDef(true); 790d21c31610c4a10e9e638f4221b5df89ea932e258Lang Hames LiveRange LR(start, end, vni); 791d21c31610c4a10e9e638f4221b5df89ea932e258Lang Hames 7929b25b8ca24d6df2e097741dcc15016772ee4eda7Jim Laskey interval.addRange(LR); 793f3bb2e65d12857f83b273f4ecab013680310bbbcEvan Cheng interval.addKill(LR.valno, end); 79424c2e5cf7e926452ea5875d027ec0d24d9c19e39Evan Cheng DOUT << " +" << LR << '\n'; 795b371f457b0ea4a652a9f526ba4375c80ae542252Evan Cheng} 796b371f457b0ea4a652a9f526ba4375c80ae542252Evan Cheng 797ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos/// computeIntervals - computes the live intervals for virtual 7984d46e1e521c0df1990ea50f8146d22bd77ea71a6Alkis Evlogimenos/// registers. for some ordering of the machine instructions [1,N] a 79908cec00588ec1a8fa85b208555f006d7396ae7a4Alkis Evlogimenos/// live interval is an interval [i, j) where 1 <= i <= j < N for 800ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos/// which a variable is live 80191aac1015e6714d959801dd8d60f55a72827dc4dDale Johannesenvoid LiveIntervals::computeIntervals() { 80291aac1015e6714d959801dd8d60f55a72827dc4dDale Johannesen 803bdc679d564e67a81792e463f6614b0088f975025Bill Wendling DOUT << "********** COMPUTING LIVE INTERVALS **********\n" 804bdc679d564e67a81792e463f6614b0088f975025Bill Wendling << "********** Function: " 805bdc679d564e67a81792e463f6614b0088f975025Bill Wendling << ((Value*)mf_->getFunction())->getName() << '\n'; 8067fbad27cfb7298c707e50af10609d463900d7211Owen Anderson 807428b92eb83b457b71d29d1d4b7900d36a0ce9a53Chris Lattner for (MachineFunction::iterator MBBI = mf_->begin(), E = mf_->end(); 808428b92eb83b457b71d29d1d4b7900d36a0ce9a53Chris Lattner MBBI != E; ++MBBI) { 809428b92eb83b457b71d29d1d4b7900d36a0ce9a53Chris Lattner MachineBasicBlock *MBB = MBBI; 810134eb73fc35e6ead3cfd3ed5024d0d7efa507441Owen Anderson // Track the index of the current machine instr. 811134eb73fc35e6ead3cfd3ed5024d0d7efa507441Owen Anderson unsigned MIIndex = getMBBStartIdx(MBB); 812bdc679d564e67a81792e463f6614b0088f975025Bill Wendling DOUT << ((Value*)MBB->getBasicBlock())->getName() << ":\n"; 8131a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos 814428b92eb83b457b71d29d1d4b7900d36a0ce9a53Chris Lattner MachineBasicBlock::iterator MI = MBB->begin(), miEnd = MBB->end(); 8150c9f92e1ff64ee56724eae444a0442b02f83d0a8Evan Cheng 816cb406c25973b4e88a6c10ad839ef1beeb3664715Dan Gohman // Create intervals for live-ins to this BB first. 817cb406c25973b4e88a6c10ad839ef1beeb3664715Dan Gohman for (MachineBasicBlock::const_livein_iterator LI = MBB->livein_begin(), 818cb406c25973b4e88a6c10ad839ef1beeb3664715Dan Gohman LE = MBB->livein_end(); LI != LE; ++LI) { 819cb406c25973b4e88a6c10ad839ef1beeb3664715Dan Gohman handleLiveInRegister(MBB, MIIndex, getOrCreateInterval(*LI)); 820cb406c25973b4e88a6c10ad839ef1beeb3664715Dan Gohman // Multiple live-ins can alias the same register. 8216f0d024a534af18d9e60b3ea757376cd8a3a980eDan Gohman for (const unsigned* AS = tri_->getSubRegisters(*LI); *AS; ++AS) 822cb406c25973b4e88a6c10ad839ef1beeb3664715Dan Gohman if (!hasInterval(*AS)) 823cb406c25973b4e88a6c10ad839ef1beeb3664715Dan Gohman handleLiveInRegister(MBB, MIIndex, getOrCreateInterval(*AS), 824cb406c25973b4e88a6c10ad839ef1beeb3664715Dan Gohman true); 825dffb2e83ed2546226d09c40aa43524e2392322daChris Lattner } 826dffb2e83ed2546226d09c40aa43524e2392322daChris Lattner 82799500aeb7c9a05db57e228544a3f81de2faf24efOwen Anderson // Skip over empty initial indices. 82899500aeb7c9a05db57e228544a3f81de2faf24efOwen Anderson while (MIIndex / InstrSlots::NUM < i2miMap_.size() && 82999500aeb7c9a05db57e228544a3f81de2faf24efOwen Anderson getInstructionFromIndex(MIIndex) == 0) 83099500aeb7c9a05db57e228544a3f81de2faf24efOwen Anderson MIIndex += InstrSlots::NUM; 83199500aeb7c9a05db57e228544a3f81de2faf24efOwen Anderson 832428b92eb83b457b71d29d1d4b7900d36a0ce9a53Chris Lattner for (; MI != miEnd; ++MI) { 833bdc679d564e67a81792e463f6614b0088f975025Bill Wendling DOUT << MIIndex << "\t" << *MI; 8341a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos 835438f7bc67cf235ccee7e6f7ac7f4ae2186eb8020Evan Cheng // Handle defs. 836428b92eb83b457b71d29d1d4b7900d36a0ce9a53Chris Lattner for (int i = MI->getNumOperands() - 1; i >= 0; --i) { 837428b92eb83b457b71d29d1d4b7900d36a0ce9a53Chris Lattner MachineOperand &MO = MI->getOperand(i); 8381a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // handle register defs - build intervals 839d735b8019b0f297d7c14b55adcd887af24d8e602Dan Gohman if (MO.isReg() && MO.getReg() && MO.isDef()) { 840ef0732d25a9882c947984ae3f2afbef5463ba00fEvan Cheng handleRegisterDef(MBB, MI, MIIndex, MO, i); 84191aac1015e6714d959801dd8d60f55a72827dc4dDale Johannesen } 8421a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos } 84399fe34b9b2bb8786da6c7f6134ae17d4c2cd8bf7Evan Cheng 84499fe34b9b2bb8786da6c7f6134ae17d4c2cd8bf7Evan Cheng // Skip over the empty slots after each instruction. 84599fe34b9b2bb8786da6c7f6134ae17d4c2cd8bf7Evan Cheng unsigned Slots = MI->getDesc().getNumDefs(); 84699fe34b9b2bb8786da6c7f6134ae17d4c2cd8bf7Evan Cheng if (Slots == 0) 84799fe34b9b2bb8786da6c7f6134ae17d4c2cd8bf7Evan Cheng Slots = 1; 84899fe34b9b2bb8786da6c7f6134ae17d4c2cd8bf7Evan Cheng MIIndex += InstrSlots::NUM * Slots; 8497fbad27cfb7298c707e50af10609d463900d7211Owen Anderson 8507fbad27cfb7298c707e50af10609d463900d7211Owen Anderson // Skip over empty indices. 8517fbad27cfb7298c707e50af10609d463900d7211Owen Anderson while (MIIndex / InstrSlots::NUM < i2miMap_.size() && 8527fbad27cfb7298c707e50af10609d463900d7211Owen Anderson getInstructionFromIndex(MIIndex) == 0) 8537fbad27cfb7298c707e50af10609d463900d7211Owen Anderson MIIndex += InstrSlots::NUM; 854ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos } 8551a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos } 856ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos} 857b27ef248f579b354aab434f63c417ab1103e47e2Alkis Evlogimenos 858d0e32c5d5c1bb03bc0cc8aeef52728724cab1c51Evan Chengbool LiveIntervals::findLiveInMBBs(unsigned Start, unsigned End, 859a5bfc97da713ec9e185226d44e6adb4d3087b304Evan Cheng SmallVectorImpl<MachineBasicBlock*> &MBBs) const { 8604ca980e7f9ce7b78955307c2d07001a24d3b6befEvan Cheng std::vector<IdxMBBPair>::const_iterator I = 861d0e32c5d5c1bb03bc0cc8aeef52728724cab1c51Evan Cheng std::lower_bound(Idx2MBBMap.begin(), Idx2MBBMap.end(), Start); 8624ca980e7f9ce7b78955307c2d07001a24d3b6befEvan Cheng 8634ca980e7f9ce7b78955307c2d07001a24d3b6befEvan Cheng bool ResVal = false; 8644ca980e7f9ce7b78955307c2d07001a24d3b6befEvan Cheng while (I != Idx2MBBMap.end()) { 8652ad8245566a3c92d4559727a877d57ecf5d078c8Dan Gohman if (I->first >= End) 8664ca980e7f9ce7b78955307c2d07001a24d3b6befEvan Cheng break; 8674ca980e7f9ce7b78955307c2d07001a24d3b6befEvan Cheng MBBs.push_back(I->second); 8684ca980e7f9ce7b78955307c2d07001a24d3b6befEvan Cheng ResVal = true; 8694ca980e7f9ce7b78955307c2d07001a24d3b6befEvan Cheng ++I; 8704ca980e7f9ce7b78955307c2d07001a24d3b6befEvan Cheng } 8714ca980e7f9ce7b78955307c2d07001a24d3b6befEvan Cheng return ResVal; 8724ca980e7f9ce7b78955307c2d07001a24d3b6befEvan Cheng} 8734ca980e7f9ce7b78955307c2d07001a24d3b6befEvan Cheng 874d0e32c5d5c1bb03bc0cc8aeef52728724cab1c51Evan Chengbool LiveIntervals::findReachableMBBs(unsigned Start, unsigned End, 875d0e32c5d5c1bb03bc0cc8aeef52728724cab1c51Evan Cheng SmallVectorImpl<MachineBasicBlock*> &MBBs) const { 876d0e32c5d5c1bb03bc0cc8aeef52728724cab1c51Evan Cheng std::vector<IdxMBBPair>::const_iterator I = 877d0e32c5d5c1bb03bc0cc8aeef52728724cab1c51Evan Cheng std::lower_bound(Idx2MBBMap.begin(), Idx2MBBMap.end(), Start); 878d0e32c5d5c1bb03bc0cc8aeef52728724cab1c51Evan Cheng 879d0e32c5d5c1bb03bc0cc8aeef52728724cab1c51Evan Cheng bool ResVal = false; 880d0e32c5d5c1bb03bc0cc8aeef52728724cab1c51Evan Cheng while (I != Idx2MBBMap.end()) { 881d0e32c5d5c1bb03bc0cc8aeef52728724cab1c51Evan Cheng if (I->first > End) 882d0e32c5d5c1bb03bc0cc8aeef52728724cab1c51Evan Cheng break; 883d0e32c5d5c1bb03bc0cc8aeef52728724cab1c51Evan Cheng MachineBasicBlock *MBB = I->second; 884d0e32c5d5c1bb03bc0cc8aeef52728724cab1c51Evan Cheng if (getMBBEndIdx(MBB) > End) 885d0e32c5d5c1bb03bc0cc8aeef52728724cab1c51Evan Cheng break; 886d0e32c5d5c1bb03bc0cc8aeef52728724cab1c51Evan Cheng for (MachineBasicBlock::succ_iterator SI = MBB->succ_begin(), 887d0e32c5d5c1bb03bc0cc8aeef52728724cab1c51Evan Cheng SE = MBB->succ_end(); SI != SE; ++SI) 888d0e32c5d5c1bb03bc0cc8aeef52728724cab1c51Evan Cheng MBBs.push_back(*SI); 889d0e32c5d5c1bb03bc0cc8aeef52728724cab1c51Evan Cheng ResVal = true; 890d0e32c5d5c1bb03bc0cc8aeef52728724cab1c51Evan Cheng ++I; 891d0e32c5d5c1bb03bc0cc8aeef52728724cab1c51Evan Cheng } 892d0e32c5d5c1bb03bc0cc8aeef52728724cab1c51Evan Cheng return ResVal; 893d0e32c5d5c1bb03bc0cc8aeef52728724cab1c51Evan Cheng} 894d0e32c5d5c1bb03bc0cc8aeef52728724cab1c51Evan Cheng 89503857b29d8271a23943254579e6cf7b7df4b1bd3Owen AndersonLiveInterval* LiveIntervals::createInterval(unsigned reg) { 8960a1fcce09230e9b4bd30a8f07447aa075dce7470Evan Cheng float Weight = TargetRegisterInfo::isPhysicalRegister(reg) ? HUGE_VALF : 0.0F; 89703857b29d8271a23943254579e6cf7b7df4b1bd3Owen Anderson return new LiveInterval(reg, Weight); 8989a8b490735d216435862a3d52e669357f165550fAlkis Evlogimenos} 899f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng 9000a1fcce09230e9b4bd30a8f07447aa075dce7470Evan Cheng/// dupInterval - Duplicate a live interval. The caller is responsible for 9010a1fcce09230e9b4bd30a8f07447aa075dce7470Evan Cheng/// managing the allocated memory. 9020a1fcce09230e9b4bd30a8f07447aa075dce7470Evan ChengLiveInterval* LiveIntervals::dupInterval(LiveInterval *li) { 9030a1fcce09230e9b4bd30a8f07447aa075dce7470Evan Cheng LiveInterval *NewLI = createInterval(li->reg); 90490f95f88c6ce09c6744777dc9d140c3c77203b92Evan Cheng NewLI->Copy(*li, mri_, getVNInfoAllocator()); 9050a1fcce09230e9b4bd30a8f07447aa075dce7470Evan Cheng return NewLI; 9060a1fcce09230e9b4bd30a8f07447aa075dce7470Evan Cheng} 9070a1fcce09230e9b4bd30a8f07447aa075dce7470Evan Cheng 908c8d044e4f779fdcfc5e7d592927740fd8f672a70Evan Cheng/// getVNInfoSourceReg - Helper function that parses the specified VNInfo 909c8d044e4f779fdcfc5e7d592927740fd8f672a70Evan Cheng/// copy field and returns the source register that defines it. 910c8d044e4f779fdcfc5e7d592927740fd8f672a70Evan Chengunsigned LiveIntervals::getVNInfoSourceReg(const VNInfo *VNI) const { 911c8d044e4f779fdcfc5e7d592927740fd8f672a70Evan Cheng if (!VNI->copy) 912c8d044e4f779fdcfc5e7d592927740fd8f672a70Evan Cheng return 0; 913c8d044e4f779fdcfc5e7d592927740fd8f672a70Evan Cheng 9148f90b6eb2fd0125f5b779de80954944f9071fb87Evan Cheng if (VNI->copy->getOpcode() == TargetInstrInfo::EXTRACT_SUBREG) { 9158f90b6eb2fd0125f5b779de80954944f9071fb87Evan Cheng // If it's extracting out of a physical register, return the sub-register. 9168f90b6eb2fd0125f5b779de80954944f9071fb87Evan Cheng unsigned Reg = VNI->copy->getOperand(1).getReg(); 9178f90b6eb2fd0125f5b779de80954944f9071fb87Evan Cheng if (TargetRegisterInfo::isPhysicalRegister(Reg)) 9188f90b6eb2fd0125f5b779de80954944f9071fb87Evan Cheng Reg = tri_->getSubReg(Reg, VNI->copy->getOperand(2).getImm()); 9198f90b6eb2fd0125f5b779de80954944f9071fb87Evan Cheng return Reg; 92097121ba2afb8d566ff1bf5c4e8fc5d4077940a7fDan Gohman } else if (VNI->copy->getOpcode() == TargetInstrInfo::INSERT_SUBREG || 92197121ba2afb8d566ff1bf5c4e8fc5d4077940a7fDan Gohman VNI->copy->getOpcode() == TargetInstrInfo::SUBREG_TO_REG) 9227e073baedb8232b9519dbe15ea141ff98ccfe6aeEvan Cheng return VNI->copy->getOperand(2).getReg(); 9238f90b6eb2fd0125f5b779de80954944f9071fb87Evan Cheng 92404ee5a1d9267e5e6fab8f088095fcb83c3c5cbd1Evan Cheng unsigned SrcReg, DstReg, SrcSubReg, DstSubReg; 92504ee5a1d9267e5e6fab8f088095fcb83c3c5cbd1Evan Cheng if (tii_->isMoveInstr(*VNI->copy, SrcReg, DstReg, SrcSubReg, DstSubReg)) 926c8d044e4f779fdcfc5e7d592927740fd8f672a70Evan Cheng return SrcReg; 927c8d044e4f779fdcfc5e7d592927740fd8f672a70Evan Cheng assert(0 && "Unrecognized copy instruction!"); 928c8d044e4f779fdcfc5e7d592927740fd8f672a70Evan Cheng return 0; 929c8d044e4f779fdcfc5e7d592927740fd8f672a70Evan Cheng} 930f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng 931f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng//===----------------------------------------------------------------------===// 932f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng// Register allocator hooks. 933f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng// 934f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng 935d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng/// getReMatImplicitUse - If the remat definition MI has one (for now, we only 936d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng/// allow one) virtual register operand, then its uses are implicitly using 937d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng/// the register. Returns the virtual register. 938d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Chengunsigned LiveIntervals::getReMatImplicitUse(const LiveInterval &li, 939d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng MachineInstr *MI) const { 940d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng unsigned RegOp = 0; 941d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) { 942d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng MachineOperand &MO = MI->getOperand(i); 943d735b8019b0f297d7c14b55adcd887af24d8e602Dan Gohman if (!MO.isReg() || !MO.isUse()) 944d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng continue; 945d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng unsigned Reg = MO.getReg(); 946d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng if (Reg == 0 || Reg == li.reg) 947d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng continue; 948d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng // FIXME: For now, only remat MI with at most one register operand. 949d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng assert(!RegOp && 950d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng "Can't rematerialize instruction with multiple register operand!"); 951d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng RegOp = MO.getReg(); 9526d69ba8a6901c69d78488cbc41f8dbf080618fdeDan Gohman#ifndef NDEBUG 953d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng break; 9546d69ba8a6901c69d78488cbc41f8dbf080618fdeDan Gohman#endif 955d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng } 956d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng return RegOp; 957d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng} 958d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng 959d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng/// isValNoAvailableAt - Return true if the val# of the specified interval 960d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng/// which reaches the given instruction also reaches the specified use index. 961d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Chengbool LiveIntervals::isValNoAvailableAt(const LiveInterval &li, MachineInstr *MI, 962d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng unsigned UseIdx) const { 963d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng unsigned Index = getInstructionIndex(MI); 964d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng VNInfo *ValNo = li.FindLiveRangeContaining(Index)->valno; 965d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng LiveInterval::const_iterator UI = li.FindLiveRangeContaining(UseIdx); 966d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng return UI != li.end() && UI->valno == ValNo; 967d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng} 968d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng 969f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng/// isReMaterializable - Returns true if the definition MI of the specified 970f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng/// val# of the specified interval is re-materializable. 971f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Chengbool LiveIntervals::isReMaterializable(const LiveInterval &li, 9725ef3a04b542c4e585276768fa9ca2af698ef5c87Evan Cheng const VNInfo *ValNo, MachineInstr *MI, 973dc37786595beedd0a68d8e2cbd91ae53ad58d133Evan Cheng SmallVectorImpl<LiveInterval*> &SpillIs, 9745ef3a04b542c4e585276768fa9ca2af698ef5c87Evan Cheng bool &isLoad) { 975f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng if (DisableReMat) 976f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng return false; 977f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng 97820ccded7dec5b90e58f649f4fb95b166a642b8cbEvan Cheng if (MI->getOpcode() == TargetInstrInfo::IMPLICIT_DEF) 979d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng return true; 980dd3465eed17cdf226bdb465e604dfa851d36029dEvan Cheng 981dd3465eed17cdf226bdb465e604dfa851d36029dEvan Cheng int FrameIdx = 0; 982dd3465eed17cdf226bdb465e604dfa851d36029dEvan Cheng if (tii_->isLoadFromStackSlot(MI, FrameIdx) && 983249ded3fa8884f91fded869fb6e251b8aebb0376Evan Cheng mf_->getFrameInfo()->isImmutableObjectIndex(FrameIdx)) 98479a0c1e46c4f7d8a2a06f4ef3e2c54d883c7fe25Evan Cheng // FIXME: Let target specific isReallyTriviallyReMaterializable determines 98579a0c1e46c4f7d8a2a06f4ef3e2c54d883c7fe25Evan Cheng // this but remember this is not safe to fold into a two-address 98679a0c1e46c4f7d8a2a06f4ef3e2c54d883c7fe25Evan Cheng // instruction. 987249ded3fa8884f91fded869fb6e251b8aebb0376Evan Cheng // This is a load from fixed stack slot. It can be rematerialized. 988dd3465eed17cdf226bdb465e604dfa851d36029dEvan Cheng return true; 989dd3465eed17cdf226bdb465e604dfa851d36029dEvan Cheng 9906d69ba8a6901c69d78488cbc41f8dbf080618fdeDan Gohman // If the target-specific rules don't identify an instruction as 9916d69ba8a6901c69d78488cbc41f8dbf080618fdeDan Gohman // being trivially rematerializable, use some target-independent 9926d69ba8a6901c69d78488cbc41f8dbf080618fdeDan Gohman // rules. 9936d69ba8a6901c69d78488cbc41f8dbf080618fdeDan Gohman if (!MI->getDesc().isRematerializable() || 9946d69ba8a6901c69d78488cbc41f8dbf080618fdeDan Gohman !tii_->isTriviallyReMaterializable(MI)) { 9954c8f87038ddc0fbcce751f0e2e7c0e564abca096Dan Gohman if (!EnableAggressiveRemat) 9964c8f87038ddc0fbcce751f0e2e7c0e564abca096Dan Gohman return false; 9976d69ba8a6901c69d78488cbc41f8dbf080618fdeDan Gohman 9980471a79f2000eb1eb4458e7b3dcd254172fae739Dan Gohman // If the instruction accesses memory but the memoperands have been lost, 9996d69ba8a6901c69d78488cbc41f8dbf080618fdeDan Gohman // we can't analyze it. 100020ccded7dec5b90e58f649f4fb95b166a642b8cbEvan Cheng const TargetInstrDesc &TID = MI->getDesc(); 10016d69ba8a6901c69d78488cbc41f8dbf080618fdeDan Gohman if ((TID.mayLoad() || TID.mayStore()) && MI->memoperands_empty()) 10026d69ba8a6901c69d78488cbc41f8dbf080618fdeDan Gohman return false; 10036d69ba8a6901c69d78488cbc41f8dbf080618fdeDan Gohman 10046d69ba8a6901c69d78488cbc41f8dbf080618fdeDan Gohman // Avoid instructions obviously unsafe for remat. 10056d69ba8a6901c69d78488cbc41f8dbf080618fdeDan Gohman if (TID.hasUnmodeledSideEffects() || TID.isNotDuplicable()) 10066d69ba8a6901c69d78488cbc41f8dbf080618fdeDan Gohman return false; 10076d69ba8a6901c69d78488cbc41f8dbf080618fdeDan Gohman 10086d69ba8a6901c69d78488cbc41f8dbf080618fdeDan Gohman // If the instruction accesses memory and the memory could be non-constant, 10096d69ba8a6901c69d78488cbc41f8dbf080618fdeDan Gohman // assume the instruction is not rematerializable. 1010dc37786595beedd0a68d8e2cbd91ae53ad58d133Evan Cheng for (std::list<MachineMemOperand>::const_iterator 1011dc37786595beedd0a68d8e2cbd91ae53ad58d133Evan Cheng I = MI->memoperands_begin(), E = MI->memoperands_end(); I != E; ++I){ 10126d69ba8a6901c69d78488cbc41f8dbf080618fdeDan Gohman const MachineMemOperand &MMO = *I; 10136d69ba8a6901c69d78488cbc41f8dbf080618fdeDan Gohman if (MMO.isVolatile() || MMO.isStore()) 10146d69ba8a6901c69d78488cbc41f8dbf080618fdeDan Gohman return false; 10156d69ba8a6901c69d78488cbc41f8dbf080618fdeDan Gohman const Value *V = MMO.getValue(); 10166d69ba8a6901c69d78488cbc41f8dbf080618fdeDan Gohman if (!V) 10176d69ba8a6901c69d78488cbc41f8dbf080618fdeDan Gohman return false; 10186d69ba8a6901c69d78488cbc41f8dbf080618fdeDan Gohman if (const PseudoSourceValue *PSV = dyn_cast<PseudoSourceValue>(V)) { 10196d69ba8a6901c69d78488cbc41f8dbf080618fdeDan Gohman if (!PSV->isConstant(mf_->getFrameInfo())) 10206d69ba8a6901c69d78488cbc41f8dbf080618fdeDan Gohman return false; 10216d69ba8a6901c69d78488cbc41f8dbf080618fdeDan Gohman } else if (!aa_->pointsToConstantMemory(V)) 10226d69ba8a6901c69d78488cbc41f8dbf080618fdeDan Gohman return false; 10236d69ba8a6901c69d78488cbc41f8dbf080618fdeDan Gohman } 10246d69ba8a6901c69d78488cbc41f8dbf080618fdeDan Gohman 10256d69ba8a6901c69d78488cbc41f8dbf080618fdeDan Gohman // If any of the registers accessed are non-constant, conservatively assume 10266d69ba8a6901c69d78488cbc41f8dbf080618fdeDan Gohman // the instruction is not rematerializable. 10276d69ba8a6901c69d78488cbc41f8dbf080618fdeDan Gohman unsigned ImpUse = 0; 10286d69ba8a6901c69d78488cbc41f8dbf080618fdeDan Gohman for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) { 10296d69ba8a6901c69d78488cbc41f8dbf080618fdeDan Gohman const MachineOperand &MO = MI->getOperand(i); 1030d735b8019b0f297d7c14b55adcd887af24d8e602Dan Gohman if (MO.isReg()) { 10316d69ba8a6901c69d78488cbc41f8dbf080618fdeDan Gohman unsigned Reg = MO.getReg(); 10326d69ba8a6901c69d78488cbc41f8dbf080618fdeDan Gohman if (Reg == 0) 1033d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng continue; 10346d69ba8a6901c69d78488cbc41f8dbf080618fdeDan Gohman if (TargetRegisterInfo::isPhysicalRegister(Reg)) 10356d69ba8a6901c69d78488cbc41f8dbf080618fdeDan Gohman return false; 10366d69ba8a6901c69d78488cbc41f8dbf080618fdeDan Gohman 10376d69ba8a6901c69d78488cbc41f8dbf080618fdeDan Gohman // Only allow one def, and that in the first operand. 10386d69ba8a6901c69d78488cbc41f8dbf080618fdeDan Gohman if (MO.isDef() != (i == 0)) 1039d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng return false; 10406d69ba8a6901c69d78488cbc41f8dbf080618fdeDan Gohman 10416d69ba8a6901c69d78488cbc41f8dbf080618fdeDan Gohman // Only allow constant-valued registers. 10426d69ba8a6901c69d78488cbc41f8dbf080618fdeDan Gohman bool IsLiveIn = mri_->isLiveIn(Reg); 10436d69ba8a6901c69d78488cbc41f8dbf080618fdeDan Gohman MachineRegisterInfo::def_iterator I = mri_->def_begin(Reg), 10446d69ba8a6901c69d78488cbc41f8dbf080618fdeDan Gohman E = mri_->def_end(); 10456d69ba8a6901c69d78488cbc41f8dbf080618fdeDan Gohman 1046c93ced5b34b50a622ee8e49d90592f03ac7ff992Dan Gohman // For the def, it should be the only def of that register. 10476d69ba8a6901c69d78488cbc41f8dbf080618fdeDan Gohman if (MO.isDef() && (next(I) != E || IsLiveIn)) 10486d69ba8a6901c69d78488cbc41f8dbf080618fdeDan Gohman return false; 10496d69ba8a6901c69d78488cbc41f8dbf080618fdeDan Gohman 10506d69ba8a6901c69d78488cbc41f8dbf080618fdeDan Gohman if (MO.isUse()) { 10516d69ba8a6901c69d78488cbc41f8dbf080618fdeDan Gohman // Only allow one use other register use, as that's all the 10526d69ba8a6901c69d78488cbc41f8dbf080618fdeDan Gohman // remat mechanisms support currently. 10536d69ba8a6901c69d78488cbc41f8dbf080618fdeDan Gohman if (Reg != li.reg) { 10546d69ba8a6901c69d78488cbc41f8dbf080618fdeDan Gohman if (ImpUse == 0) 10556d69ba8a6901c69d78488cbc41f8dbf080618fdeDan Gohman ImpUse = Reg; 10566d69ba8a6901c69d78488cbc41f8dbf080618fdeDan Gohman else if (Reg != ImpUse) 10576d69ba8a6901c69d78488cbc41f8dbf080618fdeDan Gohman return false; 10586d69ba8a6901c69d78488cbc41f8dbf080618fdeDan Gohman } 1059c93ced5b34b50a622ee8e49d90592f03ac7ff992Dan Gohman // For the use, there should be only one associated def. 10606d69ba8a6901c69d78488cbc41f8dbf080618fdeDan Gohman if (I != E && (next(I) != E || IsLiveIn)) 10616d69ba8a6901c69d78488cbc41f8dbf080618fdeDan Gohman return false; 10626d69ba8a6901c69d78488cbc41f8dbf080618fdeDan Gohman } 1063d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng } 1064d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng } 10655ef3a04b542c4e585276768fa9ca2af698ef5c87Evan Cheng } 1066f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng 10676d69ba8a6901c69d78488cbc41f8dbf080618fdeDan Gohman unsigned ImpUse = getReMatImplicitUse(li, MI); 10686d69ba8a6901c69d78488cbc41f8dbf080618fdeDan Gohman if (ImpUse) { 10696d69ba8a6901c69d78488cbc41f8dbf080618fdeDan Gohman const LiveInterval &ImpLi = getInterval(ImpUse); 10706d69ba8a6901c69d78488cbc41f8dbf080618fdeDan Gohman for (MachineRegisterInfo::use_iterator ri = mri_->use_begin(li.reg), 10716d69ba8a6901c69d78488cbc41f8dbf080618fdeDan Gohman re = mri_->use_end(); ri != re; ++ri) { 10726d69ba8a6901c69d78488cbc41f8dbf080618fdeDan Gohman MachineInstr *UseMI = &*ri; 10736d69ba8a6901c69d78488cbc41f8dbf080618fdeDan Gohman unsigned UseIdx = getInstructionIndex(UseMI); 10746d69ba8a6901c69d78488cbc41f8dbf080618fdeDan Gohman if (li.FindLiveRangeContaining(UseIdx)->valno != ValNo) 10756d69ba8a6901c69d78488cbc41f8dbf080618fdeDan Gohman continue; 10766d69ba8a6901c69d78488cbc41f8dbf080618fdeDan Gohman if (!isValNoAvailableAt(ImpLi, MI, UseIdx)) 10776d69ba8a6901c69d78488cbc41f8dbf080618fdeDan Gohman return false; 10786d69ba8a6901c69d78488cbc41f8dbf080618fdeDan Gohman } 1079dc37786595beedd0a68d8e2cbd91ae53ad58d133Evan Cheng 1080dc37786595beedd0a68d8e2cbd91ae53ad58d133Evan Cheng // If a register operand of the re-materialized instruction is going to 1081dc37786595beedd0a68d8e2cbd91ae53ad58d133Evan Cheng // be spilled next, then it's not legal to re-materialize this instruction. 1082dc37786595beedd0a68d8e2cbd91ae53ad58d133Evan Cheng for (unsigned i = 0, e = SpillIs.size(); i != e; ++i) 1083dc37786595beedd0a68d8e2cbd91ae53ad58d133Evan Cheng if (ImpUse == SpillIs[i]->reg) 1084dc37786595beedd0a68d8e2cbd91ae53ad58d133Evan Cheng return false; 10856d69ba8a6901c69d78488cbc41f8dbf080618fdeDan Gohman } 10866d69ba8a6901c69d78488cbc41f8dbf080618fdeDan Gohman return true; 10875ef3a04b542c4e585276768fa9ca2af698ef5c87Evan Cheng} 10885ef3a04b542c4e585276768fa9ca2af698ef5c87Evan Cheng 108906587497dc1c39516f24784a2ac1d9323faae0a5Evan Cheng/// isReMaterializable - Returns true if the definition MI of the specified 109006587497dc1c39516f24784a2ac1d9323faae0a5Evan Cheng/// val# of the specified interval is re-materializable. 109106587497dc1c39516f24784a2ac1d9323faae0a5Evan Chengbool LiveIntervals::isReMaterializable(const LiveInterval &li, 109206587497dc1c39516f24784a2ac1d9323faae0a5Evan Cheng const VNInfo *ValNo, MachineInstr *MI) { 109306587497dc1c39516f24784a2ac1d9323faae0a5Evan Cheng SmallVector<LiveInterval*, 4> Dummy1; 109406587497dc1c39516f24784a2ac1d9323faae0a5Evan Cheng bool Dummy2; 109506587497dc1c39516f24784a2ac1d9323faae0a5Evan Cheng return isReMaterializable(li, ValNo, MI, Dummy1, Dummy2); 109606587497dc1c39516f24784a2ac1d9323faae0a5Evan Cheng} 109706587497dc1c39516f24784a2ac1d9323faae0a5Evan Cheng 10985ef3a04b542c4e585276768fa9ca2af698ef5c87Evan Cheng/// isReMaterializable - Returns true if every definition of MI of every 10995ef3a04b542c4e585276768fa9ca2af698ef5c87Evan Cheng/// val# of the specified interval is re-materializable. 1100dc37786595beedd0a68d8e2cbd91ae53ad58d133Evan Chengbool LiveIntervals::isReMaterializable(const LiveInterval &li, 1101dc37786595beedd0a68d8e2cbd91ae53ad58d133Evan Cheng SmallVectorImpl<LiveInterval*> &SpillIs, 1102dc37786595beedd0a68d8e2cbd91ae53ad58d133Evan Cheng bool &isLoad) { 11035ef3a04b542c4e585276768fa9ca2af698ef5c87Evan Cheng isLoad = false; 11045ef3a04b542c4e585276768fa9ca2af698ef5c87Evan Cheng for (LiveInterval::const_vni_iterator i = li.vni_begin(), e = li.vni_end(); 11055ef3a04b542c4e585276768fa9ca2af698ef5c87Evan Cheng i != e; ++i) { 11065ef3a04b542c4e585276768fa9ca2af698ef5c87Evan Cheng const VNInfo *VNI = *i; 1107857c4e01f85601cf2084adb860616256ee47c177Lang Hames if (VNI->isUnused()) 11085ef3a04b542c4e585276768fa9ca2af698ef5c87Evan Cheng continue; // Dead val#. 11095ef3a04b542c4e585276768fa9ca2af698ef5c87Evan Cheng // Is the def for the val# rematerializable? 1110857c4e01f85601cf2084adb860616256ee47c177Lang Hames if (!VNI->isDefAccurate()) 11115ef3a04b542c4e585276768fa9ca2af698ef5c87Evan Cheng return false; 1112857c4e01f85601cf2084adb860616256ee47c177Lang Hames MachineInstr *ReMatDefMI = getInstructionFromIndex(VNI->def); 11135ef3a04b542c4e585276768fa9ca2af698ef5c87Evan Cheng bool DefIsLoad = false; 1114d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng if (!ReMatDefMI || 1115dc37786595beedd0a68d8e2cbd91ae53ad58d133Evan Cheng !isReMaterializable(li, VNI, ReMatDefMI, SpillIs, DefIsLoad)) 1116f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng return false; 11175ef3a04b542c4e585276768fa9ca2af698ef5c87Evan Cheng isLoad |= DefIsLoad; 1118f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng } 1119f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng return true; 1120f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng} 1121f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng 112279a0c1e46c4f7d8a2a06f4ef3e2c54d883c7fe25Evan Cheng/// FilterFoldedOps - Filter out two-address use operands. Return 112379a0c1e46c4f7d8a2a06f4ef3e2c54d883c7fe25Evan Cheng/// true if it finds any issue with the operands that ought to prevent 112479a0c1e46c4f7d8a2a06f4ef3e2c54d883c7fe25Evan Cheng/// folding. 112579a0c1e46c4f7d8a2a06f4ef3e2c54d883c7fe25Evan Chengstatic bool FilterFoldedOps(MachineInstr *MI, 112679a0c1e46c4f7d8a2a06f4ef3e2c54d883c7fe25Evan Cheng SmallVector<unsigned, 2> &Ops, 112779a0c1e46c4f7d8a2a06f4ef3e2c54d883c7fe25Evan Cheng unsigned &MRInfo, 112879a0c1e46c4f7d8a2a06f4ef3e2c54d883c7fe25Evan Cheng SmallVector<unsigned, 2> &FoldOps) { 112979a0c1e46c4f7d8a2a06f4ef3e2c54d883c7fe25Evan Cheng MRInfo = 0; 1130aee4af68ae2016afc5b4ec0c430e539c5810a766Evan Cheng for (unsigned i = 0, e = Ops.size(); i != e; ++i) { 1131aee4af68ae2016afc5b4ec0c430e539c5810a766Evan Cheng unsigned OpIdx = Ops[i]; 1132d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng MachineOperand &MO = MI->getOperand(OpIdx); 1133aee4af68ae2016afc5b4ec0c430e539c5810a766Evan Cheng // FIXME: fold subreg use. 1134d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng if (MO.getSubReg()) 113579a0c1e46c4f7d8a2a06f4ef3e2c54d883c7fe25Evan Cheng return true; 1136d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng if (MO.isDef()) 1137aee4af68ae2016afc5b4ec0c430e539c5810a766Evan Cheng MRInfo |= (unsigned)VirtRegMap::isMod; 1138aee4af68ae2016afc5b4ec0c430e539c5810a766Evan Cheng else { 1139aee4af68ae2016afc5b4ec0c430e539c5810a766Evan Cheng // Filter out two-address use operand(s). 1140a24752ff43dc1ad8c18c5d9e78549c45f62b980eEvan Cheng if (MI->isRegTiedToDefOperand(OpIdx)) { 1141aee4af68ae2016afc5b4ec0c430e539c5810a766Evan Cheng MRInfo = VirtRegMap::isModRef; 1142aee4af68ae2016afc5b4ec0c430e539c5810a766Evan Cheng continue; 1143aee4af68ae2016afc5b4ec0c430e539c5810a766Evan Cheng } 1144aee4af68ae2016afc5b4ec0c430e539c5810a766Evan Cheng MRInfo |= (unsigned)VirtRegMap::isRef; 1145aee4af68ae2016afc5b4ec0c430e539c5810a766Evan Cheng } 1146aee4af68ae2016afc5b4ec0c430e539c5810a766Evan Cheng FoldOps.push_back(OpIdx); 1147e62f97c094dba44e4c259d20135167fa91912eeaEvan Cheng } 114879a0c1e46c4f7d8a2a06f4ef3e2c54d883c7fe25Evan Cheng return false; 114979a0c1e46c4f7d8a2a06f4ef3e2c54d883c7fe25Evan Cheng} 115079a0c1e46c4f7d8a2a06f4ef3e2c54d883c7fe25Evan Cheng 115179a0c1e46c4f7d8a2a06f4ef3e2c54d883c7fe25Evan Cheng 115279a0c1e46c4f7d8a2a06f4ef3e2c54d883c7fe25Evan Cheng/// tryFoldMemoryOperand - Attempts to fold either a spill / restore from 115379a0c1e46c4f7d8a2a06f4ef3e2c54d883c7fe25Evan Cheng/// slot / to reg or any rematerialized load into ith operand of specified 115479a0c1e46c4f7d8a2a06f4ef3e2c54d883c7fe25Evan Cheng/// MI. If it is successul, MI is updated with the newly created MI and 115579a0c1e46c4f7d8a2a06f4ef3e2c54d883c7fe25Evan Cheng/// returns true. 115679a0c1e46c4f7d8a2a06f4ef3e2c54d883c7fe25Evan Chengbool LiveIntervals::tryFoldMemoryOperand(MachineInstr* &MI, 115779a0c1e46c4f7d8a2a06f4ef3e2c54d883c7fe25Evan Cheng VirtRegMap &vrm, MachineInstr *DefMI, 115879a0c1e46c4f7d8a2a06f4ef3e2c54d883c7fe25Evan Cheng unsigned InstrIdx, 115979a0c1e46c4f7d8a2a06f4ef3e2c54d883c7fe25Evan Cheng SmallVector<unsigned, 2> &Ops, 116079a0c1e46c4f7d8a2a06f4ef3e2c54d883c7fe25Evan Cheng bool isSS, int Slot, unsigned Reg) { 116179a0c1e46c4f7d8a2a06f4ef3e2c54d883c7fe25Evan Cheng // If it is an implicit def instruction, just delete it. 116220ccded7dec5b90e58f649f4fb95b166a642b8cbEvan Cheng if (MI->getOpcode() == TargetInstrInfo::IMPLICIT_DEF) { 116379a0c1e46c4f7d8a2a06f4ef3e2c54d883c7fe25Evan Cheng RemoveMachineInstrFromMaps(MI); 116479a0c1e46c4f7d8a2a06f4ef3e2c54d883c7fe25Evan Cheng vrm.RemoveMachineInstrFromMaps(MI); 116579a0c1e46c4f7d8a2a06f4ef3e2c54d883c7fe25Evan Cheng MI->eraseFromParent(); 116679a0c1e46c4f7d8a2a06f4ef3e2c54d883c7fe25Evan Cheng ++numFolds; 116779a0c1e46c4f7d8a2a06f4ef3e2c54d883c7fe25Evan Cheng return true; 116879a0c1e46c4f7d8a2a06f4ef3e2c54d883c7fe25Evan Cheng } 116979a0c1e46c4f7d8a2a06f4ef3e2c54d883c7fe25Evan Cheng 117079a0c1e46c4f7d8a2a06f4ef3e2c54d883c7fe25Evan Cheng // Filter the list of operand indexes that are to be folded. Abort if 117179a0c1e46c4f7d8a2a06f4ef3e2c54d883c7fe25Evan Cheng // any operand will prevent folding. 117279a0c1e46c4f7d8a2a06f4ef3e2c54d883c7fe25Evan Cheng unsigned MRInfo = 0; 117379a0c1e46c4f7d8a2a06f4ef3e2c54d883c7fe25Evan Cheng SmallVector<unsigned, 2> FoldOps; 117479a0c1e46c4f7d8a2a06f4ef3e2c54d883c7fe25Evan Cheng if (FilterFoldedOps(MI, Ops, MRInfo, FoldOps)) 117579a0c1e46c4f7d8a2a06f4ef3e2c54d883c7fe25Evan Cheng return false; 1176cddbb83ea82e98658d9f530c50a7b9d23249afc2Evan Cheng 1177427f4c106ac14dcf323dc1bbaf1b8040da03c3c7Evan Cheng // The only time it's safe to fold into a two address instruction is when 1178427f4c106ac14dcf323dc1bbaf1b8040da03c3c7Evan Cheng // it's folding reload and spill from / into a spill stack slot. 1179427f4c106ac14dcf323dc1bbaf1b8040da03c3c7Evan Cheng if (DefMI && (MRInfo & VirtRegMap::isMod)) 1180249ded3fa8884f91fded869fb6e251b8aebb0376Evan Cheng return false; 1181249ded3fa8884f91fded869fb6e251b8aebb0376Evan Cheng 1182f2f8c2ae07b7d9bdbf1b89781c573c7af2bd5e1bEvan Cheng MachineInstr *fmi = isSS ? tii_->foldMemoryOperand(*mf_, MI, FoldOps, Slot) 1183f2f8c2ae07b7d9bdbf1b89781c573c7af2bd5e1bEvan Cheng : tii_->foldMemoryOperand(*mf_, MI, FoldOps, DefMI); 1184f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng if (fmi) { 1185d36531249a9a9500e516148e7e72d4c0a7a4d0eeEvan Cheng // Remember this instruction uses the spill slot. 1186d36531249a9a9500e516148e7e72d4c0a7a4d0eeEvan Cheng if (isSS) vrm.addSpillSlotUse(Slot, fmi); 1187d36531249a9a9500e516148e7e72d4c0a7a4d0eeEvan Cheng 1188f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng // Attempt to fold the memory reference into the instruction. If 1189f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng // we can do this, we don't need to insert spill code. 1190f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng MachineBasicBlock &MBB = *MI->getParent(); 11918480293f41c11c22762164449e41cd3adb0dd7d8Evan Cheng if (isSS && !mf_->getFrameInfo()->isImmutableObjectIndex(Slot)) 1192aee4af68ae2016afc5b4ec0c430e539c5810a766Evan Cheng vrm.virtFolded(Reg, MI, fmi, (VirtRegMap::ModRef)MRInfo); 119381a038218171860ee4c382849c647d3dc841fe8bEvan Cheng vrm.transferSpillPts(MI, fmi); 11940cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng vrm.transferRestorePts(MI, fmi); 1195c1f53c742620dd4f2460685477303002bba8a8d8Evan Cheng vrm.transferEmergencySpills(MI, fmi); 1196f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng mi2iMap_.erase(MI); 1197cddbb83ea82e98658d9f530c50a7b9d23249afc2Evan Cheng i2miMap_[InstrIdx /InstrSlots::NUM] = fmi; 1198cddbb83ea82e98658d9f530c50a7b9d23249afc2Evan Cheng mi2iMap_[fmi] = InstrIdx; 1199f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng MI = MBB.insert(MBB.erase(MI), fmi); 12000cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng ++numFolds; 1201f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng return true; 1202f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng } 1203f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng return false; 1204f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng} 1205f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng 1206018f9b020bb12b731b0a7081578e5f82fb35092dEvan Cheng/// canFoldMemoryOperand - Returns true if the specified load / store 1207018f9b020bb12b731b0a7081578e5f82fb35092dEvan Cheng/// folding is possible. 1208018f9b020bb12b731b0a7081578e5f82fb35092dEvan Chengbool LiveIntervals::canFoldMemoryOperand(MachineInstr *MI, 120979a0c1e46c4f7d8a2a06f4ef3e2c54d883c7fe25Evan Cheng SmallVector<unsigned, 2> &Ops, 12103c75ba858b4e2070993cc1241ba74ead17f647d6Evan Cheng bool ReMat) const { 121179a0c1e46c4f7d8a2a06f4ef3e2c54d883c7fe25Evan Cheng // Filter the list of operand indexes that are to be folded. Abort if 121279a0c1e46c4f7d8a2a06f4ef3e2c54d883c7fe25Evan Cheng // any operand will prevent folding. 121379a0c1e46c4f7d8a2a06f4ef3e2c54d883c7fe25Evan Cheng unsigned MRInfo = 0; 1214018f9b020bb12b731b0a7081578e5f82fb35092dEvan Cheng SmallVector<unsigned, 2> FoldOps; 121579a0c1e46c4f7d8a2a06f4ef3e2c54d883c7fe25Evan Cheng if (FilterFoldedOps(MI, Ops, MRInfo, FoldOps)) 121679a0c1e46c4f7d8a2a06f4ef3e2c54d883c7fe25Evan Cheng return false; 1217018f9b020bb12b731b0a7081578e5f82fb35092dEvan Cheng 12183c75ba858b4e2070993cc1241ba74ead17f647d6Evan Cheng // It's only legal to remat for a use, not a def. 12193c75ba858b4e2070993cc1241ba74ead17f647d6Evan Cheng if (ReMat && (MRInfo & VirtRegMap::isMod)) 122079a0c1e46c4f7d8a2a06f4ef3e2c54d883c7fe25Evan Cheng return false; 1221018f9b020bb12b731b0a7081578e5f82fb35092dEvan Cheng 1222d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng return tii_->canFoldMemoryOperand(MI, FoldOps); 1223d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng} 1224d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng 122581a038218171860ee4c382849c647d3dc841fe8bEvan Chengbool LiveIntervals::intervalIsInOneMBB(const LiveInterval &li) const { 122681a038218171860ee4c382849c647d3dc841fe8bEvan Cheng SmallPtrSet<MachineBasicBlock*, 4> MBBs; 122781a038218171860ee4c382849c647d3dc841fe8bEvan Cheng for (LiveInterval::Ranges::const_iterator 122881a038218171860ee4c382849c647d3dc841fe8bEvan Cheng I = li.ranges.begin(), E = li.ranges.end(); I != E; ++I) { 122981a038218171860ee4c382849c647d3dc841fe8bEvan Cheng std::vector<IdxMBBPair>::const_iterator II = 123081a038218171860ee4c382849c647d3dc841fe8bEvan Cheng std::lower_bound(Idx2MBBMap.begin(), Idx2MBBMap.end(), I->start); 123181a038218171860ee4c382849c647d3dc841fe8bEvan Cheng if (II == Idx2MBBMap.end()) 123281a038218171860ee4c382849c647d3dc841fe8bEvan Cheng continue; 123381a038218171860ee4c382849c647d3dc841fe8bEvan Cheng if (I->end > II->first) // crossing a MBB. 123481a038218171860ee4c382849c647d3dc841fe8bEvan Cheng return false; 123581a038218171860ee4c382849c647d3dc841fe8bEvan Cheng MBBs.insert(II->second); 123681a038218171860ee4c382849c647d3dc841fe8bEvan Cheng if (MBBs.size() > 1) 123781a038218171860ee4c382849c647d3dc841fe8bEvan Cheng return false; 123881a038218171860ee4c382849c647d3dc841fe8bEvan Cheng } 123981a038218171860ee4c382849c647d3dc841fe8bEvan Cheng return true; 124081a038218171860ee4c382849c647d3dc841fe8bEvan Cheng} 124181a038218171860ee4c382849c647d3dc841fe8bEvan Cheng 1242d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng/// rewriteImplicitOps - Rewrite implicit use operands of MI (i.e. uses of 1243d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng/// interval on to-be re-materialized operands of MI) with new register. 1244d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Chengvoid LiveIntervals::rewriteImplicitOps(const LiveInterval &li, 1245d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng MachineInstr *MI, unsigned NewVReg, 1246d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng VirtRegMap &vrm) { 1247d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng // There is an implicit use. That means one of the other operand is 1248d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng // being remat'ed and the remat'ed instruction has li.reg as an 1249d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng // use operand. Make sure we rewrite that as well. 1250d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) { 1251d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng MachineOperand &MO = MI->getOperand(i); 1252d735b8019b0f297d7c14b55adcd887af24d8e602Dan Gohman if (!MO.isReg()) 1253d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng continue; 1254d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng unsigned Reg = MO.getReg(); 1255d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng if (Reg == 0 || TargetRegisterInfo::isPhysicalRegister(Reg)) 1256d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng continue; 1257d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng if (!vrm.isReMaterialized(Reg)) 1258d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng continue; 1259d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng MachineInstr *ReMatMI = vrm.getReMaterializedMI(Reg); 12606130f66eaae89f8878590796977678afa8448926Evan Cheng MachineOperand *UseMO = ReMatMI->findRegisterUseOperand(li.reg); 12616130f66eaae89f8878590796977678afa8448926Evan Cheng if (UseMO) 12626130f66eaae89f8878590796977678afa8448926Evan Cheng UseMO->setReg(NewVReg); 1263d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng } 1264d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng} 1265d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng 1266f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng/// rewriteInstructionForSpills, rewriteInstructionsForSpills - Helper functions 1267f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng/// for addIntervalsForSpills to rewrite uses / defs for the given live range. 1268018f9b020bb12b731b0a7081578e5f82fb35092dEvan Chengbool LiveIntervals:: 1269d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan ChengrewriteInstructionForSpills(const LiveInterval &li, const VNInfo *VNI, 1270d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng bool TrySplit, unsigned index, unsigned end, MachineInstr *MI, 127181a038218171860ee4c382849c647d3dc841fe8bEvan Cheng MachineInstr *ReMatOrigDefMI, MachineInstr *ReMatDefMI, 1272f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng unsigned Slot, int LdSlot, 1273f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng bool isLoad, bool isLoadSS, bool DefIsReMat, bool CanDelete, 1274d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng VirtRegMap &vrm, 1275f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng const TargetRegisterClass* rc, 1276f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng SmallVector<int, 4> &ReMatIds, 127722f07ffd27d1d721634d502c37267721d2e025cfEvan Cheng const MachineLoopInfo *loopInfo, 1278313d4b809326f3e04814f94e5b8ae05649d8e0f6Evan Cheng unsigned &NewVReg, unsigned ImpUse, bool &HasDef, bool &HasUse, 1279289983123ba4170c8a27e9638935818f8142bc89Owen Anderson DenseMap<unsigned,unsigned> &MBBVRegsMap, 1280c781a243a3d17e7e763515794168d8fa6043f565Evan Cheng std::vector<LiveInterval*> &NewLIs) { 1281018f9b020bb12b731b0a7081578e5f82fb35092dEvan Cheng bool CanFold = false; 1282f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng RestartInstruction: 1283f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng for (unsigned i = 0; i != MI->getNumOperands(); ++i) { 1284f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng MachineOperand& mop = MI->getOperand(i); 1285d735b8019b0f297d7c14b55adcd887af24d8e602Dan Gohman if (!mop.isReg()) 1286f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng continue; 1287f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng unsigned Reg = mop.getReg(); 1288f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng unsigned RegI = Reg; 12896f0d024a534af18d9e60b3ea757376cd8a3a980eDan Gohman if (Reg == 0 || TargetRegisterInfo::isPhysicalRegister(Reg)) 1290f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng continue; 1291f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng if (Reg != li.reg) 1292f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng continue; 1293f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng 1294f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng bool TryFold = !DefIsReMat; 1295cb3c330d39442130d0587208d673ce9c33c7008fEvan Cheng bool FoldSS = true; // Default behavior unless it's a remat. 1296f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng int FoldSlot = Slot; 1297f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng if (DefIsReMat) { 1298f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng // If this is the rematerializable definition MI itself and 1299f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng // all of its uses are rematerialized, simply delete it. 130081a038218171860ee4c382849c647d3dc841fe8bEvan Cheng if (MI == ReMatOrigDefMI && CanDelete) { 1301cddbb83ea82e98658d9f530c50a7b9d23249afc2Evan Cheng DOUT << "\t\t\t\tErasing re-materlizable def: "; 1302cddbb83ea82e98658d9f530c50a7b9d23249afc2Evan Cheng DOUT << MI << '\n'; 1303f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng RemoveMachineInstrFromMaps(MI); 1304cada245d06959831b90f8c29f92e77beda4b71cbEvan Cheng vrm.RemoveMachineInstrFromMaps(MI); 1305f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng MI->eraseFromParent(); 1306f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng break; 1307f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng } 1308f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng 1309f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng // If def for this use can't be rematerialized, then try folding. 13100cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng // If def is rematerializable and it's a load, also try folding. 1311cb3c330d39442130d0587208d673ce9c33c7008fEvan Cheng TryFold = !ReMatDefMI || (ReMatDefMI && (MI == ReMatOrigDefMI || isLoad)); 1312f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng if (isLoad) { 1313f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng // Try fold loads (from stack slot, constant pool, etc.) into uses. 1314f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng FoldSS = isLoadSS; 1315f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng FoldSlot = LdSlot; 1316f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng } 1317f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng } 1318f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng 1319f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng // Scan all of the operands of this instruction rewriting operands 1320f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng // to use NewVReg instead of li.reg as appropriate. We do this for 1321f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng // two reasons: 1322f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng // 1323f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng // 1. If the instr reads the same spilled vreg multiple times, we 1324f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng // want to reuse the NewVReg. 1325f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng // 2. If the instr is a two-addr instruction, we are required to 1326f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng // keep the src/dst regs pinned. 1327f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng // 1328f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng // Keep track of whether we replace a use and/or def so that we can 1329f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng // create the spill interval with the appropriate range. 1330cddbb83ea82e98658d9f530c50a7b9d23249afc2Evan Cheng 133181a038218171860ee4c382849c647d3dc841fe8bEvan Cheng HasUse = mop.isUse(); 133281a038218171860ee4c382849c647d3dc841fe8bEvan Cheng HasDef = mop.isDef(); 1333aee4af68ae2016afc5b4ec0c430e539c5810a766Evan Cheng SmallVector<unsigned, 2> Ops; 1334aee4af68ae2016afc5b4ec0c430e539c5810a766Evan Cheng Ops.push_back(i); 1335f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng for (unsigned j = i+1, e = MI->getNumOperands(); j != e; ++j) { 1336aee4af68ae2016afc5b4ec0c430e539c5810a766Evan Cheng const MachineOperand &MOj = MI->getOperand(j); 1337d735b8019b0f297d7c14b55adcd887af24d8e602Dan Gohman if (!MOj.isReg()) 1338f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng continue; 1339aee4af68ae2016afc5b4ec0c430e539c5810a766Evan Cheng unsigned RegJ = MOj.getReg(); 13406f0d024a534af18d9e60b3ea757376cd8a3a980eDan Gohman if (RegJ == 0 || TargetRegisterInfo::isPhysicalRegister(RegJ)) 1341f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng continue; 1342f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng if (RegJ == RegI) { 1343aee4af68ae2016afc5b4ec0c430e539c5810a766Evan Cheng Ops.push_back(j); 1344aee4af68ae2016afc5b4ec0c430e539c5810a766Evan Cheng HasUse |= MOj.isUse(); 1345aee4af68ae2016afc5b4ec0c430e539c5810a766Evan Cheng HasDef |= MOj.isDef(); 1346f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng } 1347f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng } 1348f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng 134979a796c2b17c7ebd4dd489b5de1078fc2148adbaEvan Cheng if (HasUse && !li.liveAt(getUseIndex(index))) 135079a796c2b17c7ebd4dd489b5de1078fc2148adbaEvan Cheng // Must be defined by an implicit def. It should not be spilled. Note, 135179a796c2b17c7ebd4dd489b5de1078fc2148adbaEvan Cheng // this is for correctness reason. e.g. 135279a796c2b17c7ebd4dd489b5de1078fc2148adbaEvan Cheng // 8 %reg1024<def> = IMPLICIT_DEF 135379a796c2b17c7ebd4dd489b5de1078fc2148adbaEvan Cheng // 12 %reg1024<def> = INSERT_SUBREG %reg1024<kill>, %reg1025, 2 135479a796c2b17c7ebd4dd489b5de1078fc2148adbaEvan Cheng // The live range [12, 14) are not part of the r1024 live interval since 135579a796c2b17c7ebd4dd489b5de1078fc2148adbaEvan Cheng // it's defined by an implicit def. It will not conflicts with live 135679a796c2b17c7ebd4dd489b5de1078fc2148adbaEvan Cheng // interval of r1025. Now suppose both registers are spilled, you can 1357b9890ae3c35ad7d8e49261650d5b98f49f97a705Evan Cheng // easily see a situation where both registers are reloaded before 135879a796c2b17c7ebd4dd489b5de1078fc2148adbaEvan Cheng // the INSERT_SUBREG and both target registers that would overlap. 135979a796c2b17c7ebd4dd489b5de1078fc2148adbaEvan Cheng HasUse = false; 136079a796c2b17c7ebd4dd489b5de1078fc2148adbaEvan Cheng 136126b86a0b5676253040dc206b437536a24306fb76David Greene // Create a new virtual register for the spill interval. 136226b86a0b5676253040dc206b437536a24306fb76David Greene // Create the new register now so we can map the fold instruction 136326b86a0b5676253040dc206b437536a24306fb76David Greene // to the new register so when it is unfolded we get the correct 136426b86a0b5676253040dc206b437536a24306fb76David Greene // answer. 136526b86a0b5676253040dc206b437536a24306fb76David Greene bool CreatedNewVReg = false; 136626b86a0b5676253040dc206b437536a24306fb76David Greene if (NewVReg == 0) { 136726b86a0b5676253040dc206b437536a24306fb76David Greene NewVReg = mri_->createVirtualRegister(rc); 136826b86a0b5676253040dc206b437536a24306fb76David Greene vrm.grow(); 136926b86a0b5676253040dc206b437536a24306fb76David Greene CreatedNewVReg = true; 137026b86a0b5676253040dc206b437536a24306fb76David Greene } 137126b86a0b5676253040dc206b437536a24306fb76David Greene 13729c3c2213647e3f1b71722d61875ebac01b65cb91Evan Cheng if (!TryFold) 13739c3c2213647e3f1b71722d61875ebac01b65cb91Evan Cheng CanFold = false; 13749c3c2213647e3f1b71722d61875ebac01b65cb91Evan Cheng else { 1375018f9b020bb12b731b0a7081578e5f82fb35092dEvan Cheng // Do not fold load / store here if we are splitting. We'll find an 1376018f9b020bb12b731b0a7081578e5f82fb35092dEvan Cheng // optimal point to insert a load / store later. 1377018f9b020bb12b731b0a7081578e5f82fb35092dEvan Cheng if (!TrySplit) { 1378018f9b020bb12b731b0a7081578e5f82fb35092dEvan Cheng if (tryFoldMemoryOperand(MI, vrm, ReMatDefMI, index, 137926b86a0b5676253040dc206b437536a24306fb76David Greene Ops, FoldSS, FoldSlot, NewVReg)) { 1380018f9b020bb12b731b0a7081578e5f82fb35092dEvan Cheng // Folding the load/store can completely change the instruction in 1381018f9b020bb12b731b0a7081578e5f82fb35092dEvan Cheng // unpredictable ways, rescan it from the beginning. 138226b86a0b5676253040dc206b437536a24306fb76David Greene 138326b86a0b5676253040dc206b437536a24306fb76David Greene if (FoldSS) { 138426b86a0b5676253040dc206b437536a24306fb76David Greene // We need to give the new vreg the same stack slot as the 138526b86a0b5676253040dc206b437536a24306fb76David Greene // spilled interval. 138626b86a0b5676253040dc206b437536a24306fb76David Greene vrm.assignVirt2StackSlot(NewVReg, FoldSlot); 138726b86a0b5676253040dc206b437536a24306fb76David Greene } 138826b86a0b5676253040dc206b437536a24306fb76David Greene 1389018f9b020bb12b731b0a7081578e5f82fb35092dEvan Cheng HasUse = false; 1390018f9b020bb12b731b0a7081578e5f82fb35092dEvan Cheng HasDef = false; 1391018f9b020bb12b731b0a7081578e5f82fb35092dEvan Cheng CanFold = false; 1392c781a243a3d17e7e763515794168d8fa6043f565Evan Cheng if (isNotInMIMap(MI)) 13937e073baedb8232b9519dbe15ea141ff98ccfe6aeEvan Cheng break; 1394018f9b020bb12b731b0a7081578e5f82fb35092dEvan Cheng goto RestartInstruction; 1395018f9b020bb12b731b0a7081578e5f82fb35092dEvan Cheng } 1396018f9b020bb12b731b0a7081578e5f82fb35092dEvan Cheng } else { 13979c3c2213647e3f1b71722d61875ebac01b65cb91Evan Cheng // We'll try to fold it later if it's profitable. 13983c75ba858b4e2070993cc1241ba74ead17f647d6Evan Cheng CanFold = canFoldMemoryOperand(MI, Ops, DefIsReMat); 1399018f9b020bb12b731b0a7081578e5f82fb35092dEvan Cheng } 14009c3c2213647e3f1b71722d61875ebac01b65cb91Evan Cheng } 1401cddbb83ea82e98658d9f530c50a7b9d23249afc2Evan Cheng 1402cddbb83ea82e98658d9f530c50a7b9d23249afc2Evan Cheng mop.setReg(NewVReg); 1403d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng if (mop.isImplicit()) 1404d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng rewriteImplicitOps(li, MI, NewVReg, vrm); 1405cddbb83ea82e98658d9f530c50a7b9d23249afc2Evan Cheng 1406cddbb83ea82e98658d9f530c50a7b9d23249afc2Evan Cheng // Reuse NewVReg for other reads. 1407d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng for (unsigned j = 0, e = Ops.size(); j != e; ++j) { 1408d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng MachineOperand &mopj = MI->getOperand(Ops[j]); 1409d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng mopj.setReg(NewVReg); 1410d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng if (mopj.isImplicit()) 1411d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng rewriteImplicitOps(li, MI, NewVReg, vrm); 1412d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng } 1413cddbb83ea82e98658d9f530c50a7b9d23249afc2Evan Cheng 141481a038218171860ee4c382849c647d3dc841fe8bEvan Cheng if (CreatedNewVReg) { 141581a038218171860ee4c382849c647d3dc841fe8bEvan Cheng if (DefIsReMat) { 141681a038218171860ee4c382849c647d3dc841fe8bEvan Cheng vrm.setVirtIsReMaterialized(NewVReg, ReMatDefMI/*, CanDelete*/); 1417d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng if (ReMatIds[VNI->id] == VirtRegMap::MAX_STACK_SLOT) { 141881a038218171860ee4c382849c647d3dc841fe8bEvan Cheng // Each valnum may have its own remat id. 1419d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng ReMatIds[VNI->id] = vrm.assignVirtReMatId(NewVReg); 142081a038218171860ee4c382849c647d3dc841fe8bEvan Cheng } else { 1421d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng vrm.assignVirtReMatId(NewVReg, ReMatIds[VNI->id]); 142281a038218171860ee4c382849c647d3dc841fe8bEvan Cheng } 142381a038218171860ee4c382849c647d3dc841fe8bEvan Cheng if (!CanDelete || (HasUse && HasDef)) { 142481a038218171860ee4c382849c647d3dc841fe8bEvan Cheng // If this is a two-addr instruction then its use operands are 142581a038218171860ee4c382849c647d3dc841fe8bEvan Cheng // rematerializable but its def is not. It should be assigned a 142681a038218171860ee4c382849c647d3dc841fe8bEvan Cheng // stack slot. 142781a038218171860ee4c382849c647d3dc841fe8bEvan Cheng vrm.assignVirt2StackSlot(NewVReg, Slot); 142881a038218171860ee4c382849c647d3dc841fe8bEvan Cheng } 1429f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng } else { 1430f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng vrm.assignVirt2StackSlot(NewVReg, Slot); 1431f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng } 1432cb3c330d39442130d0587208d673ce9c33c7008fEvan Cheng } else if (HasUse && HasDef && 1433cb3c330d39442130d0587208d673ce9c33c7008fEvan Cheng vrm.getStackSlot(NewVReg) == VirtRegMap::NO_STACK_SLOT) { 1434cb3c330d39442130d0587208d673ce9c33c7008fEvan Cheng // If this interval hasn't been assigned a stack slot (because earlier 1435cb3c330d39442130d0587208d673ce9c33c7008fEvan Cheng // def is a deleted remat def), do it now. 1436cb3c330d39442130d0587208d673ce9c33c7008fEvan Cheng assert(Slot != VirtRegMap::NO_STACK_SLOT); 1437cb3c330d39442130d0587208d673ce9c33c7008fEvan Cheng vrm.assignVirt2StackSlot(NewVReg, Slot); 1438f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng } 1439f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng 1440313d4b809326f3e04814f94e5b8ae05649d8e0f6Evan Cheng // Re-matting an instruction with virtual register use. Add the 1441313d4b809326f3e04814f94e5b8ae05649d8e0f6Evan Cheng // register as an implicit use on the use MI. 1442313d4b809326f3e04814f94e5b8ae05649d8e0f6Evan Cheng if (DefIsReMat && ImpUse) 1443313d4b809326f3e04814f94e5b8ae05649d8e0f6Evan Cheng MI->addOperand(MachineOperand::CreateReg(ImpUse, false, true)); 1444313d4b809326f3e04814f94e5b8ae05649d8e0f6Evan Cheng 14455b69ebac857104770b1a751bf7a463fda4330a62Evan Cheng // Create a new register interval for this spill / remat. 1446f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng LiveInterval &nI = getOrCreateInterval(NewVReg); 144781a038218171860ee4c382849c647d3dc841fe8bEvan Cheng if (CreatedNewVReg) { 144881a038218171860ee4c382849c647d3dc841fe8bEvan Cheng NewLIs.push_back(&nI); 14491953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng MBBVRegsMap.insert(std::make_pair(MI->getParent()->getNumber(), NewVReg)); 145081a038218171860ee4c382849c647d3dc841fe8bEvan Cheng if (TrySplit) 145181a038218171860ee4c382849c647d3dc841fe8bEvan Cheng vrm.setIsSplitFromReg(NewVReg, li.reg); 145281a038218171860ee4c382849c647d3dc841fe8bEvan Cheng } 1453f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng 1454f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng if (HasUse) { 145581a038218171860ee4c382849c647d3dc841fe8bEvan Cheng if (CreatedNewVReg) { 145681a038218171860ee4c382849c647d3dc841fe8bEvan Cheng LiveRange LR(getLoadIndex(index), getUseIndex(index)+1, 1457857c4e01f85601cf2084adb860616256ee47c177Lang Hames nI.getNextValue(0, 0, false, VNInfoAllocator)); 145881a038218171860ee4c382849c647d3dc841fe8bEvan Cheng DOUT << " +" << LR; 145981a038218171860ee4c382849c647d3dc841fe8bEvan Cheng nI.addRange(LR); 146081a038218171860ee4c382849c647d3dc841fe8bEvan Cheng } else { 146181a038218171860ee4c382849c647d3dc841fe8bEvan Cheng // Extend the split live interval to this def / use. 146281a038218171860ee4c382849c647d3dc841fe8bEvan Cheng unsigned End = getUseIndex(index)+1; 146381a038218171860ee4c382849c647d3dc841fe8bEvan Cheng LiveRange LR(nI.ranges[nI.ranges.size()-1].end, End, 146481a038218171860ee4c382849c647d3dc841fe8bEvan Cheng nI.getValNumInfo(nI.getNumValNums()-1)); 146581a038218171860ee4c382849c647d3dc841fe8bEvan Cheng DOUT << " +" << LR; 146681a038218171860ee4c382849c647d3dc841fe8bEvan Cheng nI.addRange(LR); 146781a038218171860ee4c382849c647d3dc841fe8bEvan Cheng } 1468f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng } 1469f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng if (HasDef) { 1470f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng LiveRange LR(getDefIndex(index), getStoreIndex(index), 1471857c4e01f85601cf2084adb860616256ee47c177Lang Hames nI.getNextValue(0, 0, false, VNInfoAllocator)); 1472f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng DOUT << " +" << LR; 1473f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng nI.addRange(LR); 1474f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng } 147581a038218171860ee4c382849c647d3dc841fe8bEvan Cheng 1476f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng DOUT << "\t\t\t\tAdded new interval: "; 14776f0d024a534af18d9e60b3ea757376cd8a3a980eDan Gohman nI.print(DOUT, tri_); 1478f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng DOUT << '\n'; 1479f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng } 1480018f9b020bb12b731b0a7081578e5f82fb35092dEvan Cheng return CanFold; 1481f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng} 148281a038218171860ee4c382849c647d3dc841fe8bEvan Chengbool LiveIntervals::anyKillInMBBAfterIdx(const LiveInterval &li, 14830cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng const VNInfo *VNI, 14840cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng MachineBasicBlock *MBB, unsigned Idx) const { 148581a038218171860ee4c382849c647d3dc841fe8bEvan Cheng unsigned End = getMBBEndIdx(MBB); 14860cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng for (unsigned j = 0, ee = VNI->kills.size(); j != ee; ++j) { 14870cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng unsigned KillIdx = VNI->kills[j]; 14880cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng if (KillIdx > Idx && KillIdx < End) 14890cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng return true; 149081a038218171860ee4c382849c647d3dc841fe8bEvan Cheng } 149181a038218171860ee4c382849c647d3dc841fe8bEvan Cheng return false; 149281a038218171860ee4c382849c647d3dc841fe8bEvan Cheng} 149381a038218171860ee4c382849c647d3dc841fe8bEvan Cheng 1494063284c001666c0a3906acbe0a26dc7cae5f081cEvan Cheng/// RewriteInfo - Keep track of machine instrs that will be rewritten 1495063284c001666c0a3906acbe0a26dc7cae5f081cEvan Cheng/// during spilling. 1496844731a7f1909f55935e3514c9e713a62d67662eDan Gohmannamespace { 1497844731a7f1909f55935e3514c9e713a62d67662eDan Gohman struct RewriteInfo { 1498844731a7f1909f55935e3514c9e713a62d67662eDan Gohman unsigned Index; 1499844731a7f1909f55935e3514c9e713a62d67662eDan Gohman MachineInstr *MI; 1500844731a7f1909f55935e3514c9e713a62d67662eDan Gohman bool HasUse; 1501844731a7f1909f55935e3514c9e713a62d67662eDan Gohman bool HasDef; 1502844731a7f1909f55935e3514c9e713a62d67662eDan Gohman RewriteInfo(unsigned i, MachineInstr *mi, bool u, bool d) 1503844731a7f1909f55935e3514c9e713a62d67662eDan Gohman : Index(i), MI(mi), HasUse(u), HasDef(d) {} 1504844731a7f1909f55935e3514c9e713a62d67662eDan Gohman }; 1505844731a7f1909f55935e3514c9e713a62d67662eDan Gohman 1506844731a7f1909f55935e3514c9e713a62d67662eDan Gohman struct RewriteInfoCompare { 1507844731a7f1909f55935e3514c9e713a62d67662eDan Gohman bool operator()(const RewriteInfo &LHS, const RewriteInfo &RHS) const { 1508844731a7f1909f55935e3514c9e713a62d67662eDan Gohman return LHS.Index < RHS.Index; 1509844731a7f1909f55935e3514c9e713a62d67662eDan Gohman } 1510844731a7f1909f55935e3514c9e713a62d67662eDan Gohman }; 1511844731a7f1909f55935e3514c9e713a62d67662eDan Gohman} 1512063284c001666c0a3906acbe0a26dc7cae5f081cEvan Cheng 1513f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Chengvoid LiveIntervals:: 151481a038218171860ee4c382849c647d3dc841fe8bEvan ChengrewriteInstructionsForSpills(const LiveInterval &li, bool TrySplit, 1515f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng LiveInterval::Ranges::const_iterator &I, 151681a038218171860ee4c382849c647d3dc841fe8bEvan Cheng MachineInstr *ReMatOrigDefMI, MachineInstr *ReMatDefMI, 1517f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng unsigned Slot, int LdSlot, 1518f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng bool isLoad, bool isLoadSS, bool DefIsReMat, bool CanDelete, 1519d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng VirtRegMap &vrm, 1520f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng const TargetRegisterClass* rc, 1521f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng SmallVector<int, 4> &ReMatIds, 152222f07ffd27d1d721634d502c37267721d2e025cfEvan Cheng const MachineLoopInfo *loopInfo, 152381a038218171860ee4c382849c647d3dc841fe8bEvan Cheng BitVector &SpillMBBs, 1524289983123ba4170c8a27e9638935818f8142bc89Owen Anderson DenseMap<unsigned, std::vector<SRInfo> > &SpillIdxes, 15250cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng BitVector &RestoreMBBs, 1526289983123ba4170c8a27e9638935818f8142bc89Owen Anderson DenseMap<unsigned, std::vector<SRInfo> > &RestoreIdxes, 1527289983123ba4170c8a27e9638935818f8142bc89Owen Anderson DenseMap<unsigned,unsigned> &MBBVRegsMap, 1528c781a243a3d17e7e763515794168d8fa6043f565Evan Cheng std::vector<LiveInterval*> &NewLIs) { 1529018f9b020bb12b731b0a7081578e5f82fb35092dEvan Cheng bool AllCanFold = true; 153081a038218171860ee4c382849c647d3dc841fe8bEvan Cheng unsigned NewVReg = 0; 1531063284c001666c0a3906acbe0a26dc7cae5f081cEvan Cheng unsigned start = getBaseIndex(I->start); 1532f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng unsigned end = getBaseIndex(I->end-1) + InstrSlots::NUM; 1533f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng 1534063284c001666c0a3906acbe0a26dc7cae5f081cEvan Cheng // First collect all the def / use in this live range that will be rewritten. 15357e073baedb8232b9519dbe15ea141ff98ccfe6aeEvan Cheng // Make sure they are sorted according to instruction index. 1536063284c001666c0a3906acbe0a26dc7cae5f081cEvan Cheng std::vector<RewriteInfo> RewriteMIs; 1537d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng for (MachineRegisterInfo::reg_iterator ri = mri_->reg_begin(li.reg), 1538d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng re = mri_->reg_end(); ri != re; ) { 1539419852ca8a01aecde4c0e20af6b7bd6450e70f87Evan Cheng MachineInstr *MI = &*ri; 1540063284c001666c0a3906acbe0a26dc7cae5f081cEvan Cheng MachineOperand &O = ri.getOperand(); 1541063284c001666c0a3906acbe0a26dc7cae5f081cEvan Cheng ++ri; 154224d2f8a212f08bf21360122cc00acf2657af91f9Evan Cheng assert(!O.isImplicit() && "Spilling register that's used as implicit use?"); 1543063284c001666c0a3906acbe0a26dc7cae5f081cEvan Cheng unsigned index = getInstructionIndex(MI); 1544063284c001666c0a3906acbe0a26dc7cae5f081cEvan Cheng if (index < start || index >= end) 1545063284c001666c0a3906acbe0a26dc7cae5f081cEvan Cheng continue; 154679a796c2b17c7ebd4dd489b5de1078fc2148adbaEvan Cheng if (O.isUse() && !li.liveAt(getUseIndex(index))) 154779a796c2b17c7ebd4dd489b5de1078fc2148adbaEvan Cheng // Must be defined by an implicit def. It should not be spilled. Note, 154879a796c2b17c7ebd4dd489b5de1078fc2148adbaEvan Cheng // this is for correctness reason. e.g. 154979a796c2b17c7ebd4dd489b5de1078fc2148adbaEvan Cheng // 8 %reg1024<def> = IMPLICIT_DEF 155079a796c2b17c7ebd4dd489b5de1078fc2148adbaEvan Cheng // 12 %reg1024<def> = INSERT_SUBREG %reg1024<kill>, %reg1025, 2 155179a796c2b17c7ebd4dd489b5de1078fc2148adbaEvan Cheng // The live range [12, 14) are not part of the r1024 live interval since 155279a796c2b17c7ebd4dd489b5de1078fc2148adbaEvan Cheng // it's defined by an implicit def. It will not conflicts with live 155379a796c2b17c7ebd4dd489b5de1078fc2148adbaEvan Cheng // interval of r1025. Now suppose both registers are spilled, you can 1554b9890ae3c35ad7d8e49261650d5b98f49f97a705Evan Cheng // easily see a situation where both registers are reloaded before 155579a796c2b17c7ebd4dd489b5de1078fc2148adbaEvan Cheng // the INSERT_SUBREG and both target registers that would overlap. 155679a796c2b17c7ebd4dd489b5de1078fc2148adbaEvan Cheng continue; 1557063284c001666c0a3906acbe0a26dc7cae5f081cEvan Cheng RewriteMIs.push_back(RewriteInfo(index, MI, O.isUse(), O.isDef())); 1558063284c001666c0a3906acbe0a26dc7cae5f081cEvan Cheng } 1559063284c001666c0a3906acbe0a26dc7cae5f081cEvan Cheng std::sort(RewriteMIs.begin(), RewriteMIs.end(), RewriteInfoCompare()); 1560063284c001666c0a3906acbe0a26dc7cae5f081cEvan Cheng 1561313d4b809326f3e04814f94e5b8ae05649d8e0f6Evan Cheng unsigned ImpUse = DefIsReMat ? getReMatImplicitUse(li, ReMatDefMI) : 0; 1562063284c001666c0a3906acbe0a26dc7cae5f081cEvan Cheng // Now rewrite the defs and uses. 1563063284c001666c0a3906acbe0a26dc7cae5f081cEvan Cheng for (unsigned i = 0, e = RewriteMIs.size(); i != e; ) { 1564063284c001666c0a3906acbe0a26dc7cae5f081cEvan Cheng RewriteInfo &rwi = RewriteMIs[i]; 1565063284c001666c0a3906acbe0a26dc7cae5f081cEvan Cheng ++i; 1566063284c001666c0a3906acbe0a26dc7cae5f081cEvan Cheng unsigned index = rwi.Index; 1567063284c001666c0a3906acbe0a26dc7cae5f081cEvan Cheng bool MIHasUse = rwi.HasUse; 1568063284c001666c0a3906acbe0a26dc7cae5f081cEvan Cheng bool MIHasDef = rwi.HasDef; 1569063284c001666c0a3906acbe0a26dc7cae5f081cEvan Cheng MachineInstr *MI = rwi.MI; 1570063284c001666c0a3906acbe0a26dc7cae5f081cEvan Cheng // If MI def and/or use the same register multiple times, then there 1571063284c001666c0a3906acbe0a26dc7cae5f081cEvan Cheng // are multiple entries. 1572313d4b809326f3e04814f94e5b8ae05649d8e0f6Evan Cheng unsigned NumUses = MIHasUse; 1573063284c001666c0a3906acbe0a26dc7cae5f081cEvan Cheng while (i != e && RewriteMIs[i].MI == MI) { 1574063284c001666c0a3906acbe0a26dc7cae5f081cEvan Cheng assert(RewriteMIs[i].Index == index); 1575313d4b809326f3e04814f94e5b8ae05649d8e0f6Evan Cheng bool isUse = RewriteMIs[i].HasUse; 1576313d4b809326f3e04814f94e5b8ae05649d8e0f6Evan Cheng if (isUse) ++NumUses; 1577313d4b809326f3e04814f94e5b8ae05649d8e0f6Evan Cheng MIHasUse |= isUse; 1578063284c001666c0a3906acbe0a26dc7cae5f081cEvan Cheng MIHasDef |= RewriteMIs[i].HasDef; 1579063284c001666c0a3906acbe0a26dc7cae5f081cEvan Cheng ++i; 1580063284c001666c0a3906acbe0a26dc7cae5f081cEvan Cheng } 158181a038218171860ee4c382849c647d3dc841fe8bEvan Cheng MachineBasicBlock *MBB = MI->getParent(); 1582313d4b809326f3e04814f94e5b8ae05649d8e0f6Evan Cheng 15830a891ed7d5875a9ccdb93b4472b0f43947d8289bEvan Cheng if (ImpUse && MI != ReMatDefMI) { 1584313d4b809326f3e04814f94e5b8ae05649d8e0f6Evan Cheng // Re-matting an instruction with virtual register use. Update the 158524d2f8a212f08bf21360122cc00acf2657af91f9Evan Cheng // register interval's spill weight to HUGE_VALF to prevent it from 158624d2f8a212f08bf21360122cc00acf2657af91f9Evan Cheng // being spilled. 1587313d4b809326f3e04814f94e5b8ae05649d8e0f6Evan Cheng LiveInterval &ImpLi = getInterval(ImpUse); 158824d2f8a212f08bf21360122cc00acf2657af91f9Evan Cheng ImpLi.weight = HUGE_VALF; 1589313d4b809326f3e04814f94e5b8ae05649d8e0f6Evan Cheng } 1590313d4b809326f3e04814f94e5b8ae05649d8e0f6Evan Cheng 1591063284c001666c0a3906acbe0a26dc7cae5f081cEvan Cheng unsigned MBBId = MBB->getNumber(); 1592018f9b020bb12b731b0a7081578e5f82fb35092dEvan Cheng unsigned ThisVReg = 0; 159370306f8348f27c61cfed5a60e2fceac0f29746a2Evan Cheng if (TrySplit) { 1594289983123ba4170c8a27e9638935818f8142bc89Owen Anderson DenseMap<unsigned,unsigned>::iterator NVI = MBBVRegsMap.find(MBBId); 15951953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng if (NVI != MBBVRegsMap.end()) { 1596018f9b020bb12b731b0a7081578e5f82fb35092dEvan Cheng ThisVReg = NVI->second; 15971953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng // One common case: 15981953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng // x = use 15991953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng // ... 16001953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng // ... 16011953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng // def = ... 16021953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng // = use 16031953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng // It's better to start a new interval to avoid artifically 16041953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng // extend the new interval. 16051953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng if (MIHasDef && !MIHasUse) { 16061953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng MBBVRegsMap.erase(MBB->getNumber()); 1607018f9b020bb12b731b0a7081578e5f82fb35092dEvan Cheng ThisVReg = 0; 16081953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng } 16091953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng } 1610cada245d06959831b90f8c29f92e77beda4b71cbEvan Cheng } 1611018f9b020bb12b731b0a7081578e5f82fb35092dEvan Cheng 1612018f9b020bb12b731b0a7081578e5f82fb35092dEvan Cheng bool IsNew = ThisVReg == 0; 1613018f9b020bb12b731b0a7081578e5f82fb35092dEvan Cheng if (IsNew) { 1614018f9b020bb12b731b0a7081578e5f82fb35092dEvan Cheng // This ends the previous live interval. If all of its def / use 1615018f9b020bb12b731b0a7081578e5f82fb35092dEvan Cheng // can be folded, give it a low spill weight. 1616018f9b020bb12b731b0a7081578e5f82fb35092dEvan Cheng if (NewVReg && TrySplit && AllCanFold) { 1617018f9b020bb12b731b0a7081578e5f82fb35092dEvan Cheng LiveInterval &nI = getOrCreateInterval(NewVReg); 1618018f9b020bb12b731b0a7081578e5f82fb35092dEvan Cheng nI.weight /= 10.0F; 1619018f9b020bb12b731b0a7081578e5f82fb35092dEvan Cheng } 1620018f9b020bb12b731b0a7081578e5f82fb35092dEvan Cheng AllCanFold = true; 1621018f9b020bb12b731b0a7081578e5f82fb35092dEvan Cheng } 1622018f9b020bb12b731b0a7081578e5f82fb35092dEvan Cheng NewVReg = ThisVReg; 1623018f9b020bb12b731b0a7081578e5f82fb35092dEvan Cheng 162481a038218171860ee4c382849c647d3dc841fe8bEvan Cheng bool HasDef = false; 162581a038218171860ee4c382849c647d3dc841fe8bEvan Cheng bool HasUse = false; 1626d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng bool CanFold = rewriteInstructionForSpills(li, I->valno, TrySplit, 16279c3c2213647e3f1b71722d61875ebac01b65cb91Evan Cheng index, end, MI, ReMatOrigDefMI, ReMatDefMI, 16289c3c2213647e3f1b71722d61875ebac01b65cb91Evan Cheng Slot, LdSlot, isLoad, isLoadSS, DefIsReMat, 16299c3c2213647e3f1b71722d61875ebac01b65cb91Evan Cheng CanDelete, vrm, rc, ReMatIds, loopInfo, NewVReg, 1630c781a243a3d17e7e763515794168d8fa6043f565Evan Cheng ImpUse, HasDef, HasUse, MBBVRegsMap, NewLIs); 163181a038218171860ee4c382849c647d3dc841fe8bEvan Cheng if (!HasDef && !HasUse) 163281a038218171860ee4c382849c647d3dc841fe8bEvan Cheng continue; 163381a038218171860ee4c382849c647d3dc841fe8bEvan Cheng 1634018f9b020bb12b731b0a7081578e5f82fb35092dEvan Cheng AllCanFold &= CanFold; 1635018f9b020bb12b731b0a7081578e5f82fb35092dEvan Cheng 163681a038218171860ee4c382849c647d3dc841fe8bEvan Cheng // Update weight of spill interval. 163781a038218171860ee4c382849c647d3dc841fe8bEvan Cheng LiveInterval &nI = getOrCreateInterval(NewVReg); 163870306f8348f27c61cfed5a60e2fceac0f29746a2Evan Cheng if (!TrySplit) { 163981a038218171860ee4c382849c647d3dc841fe8bEvan Cheng // The spill weight is now infinity as it cannot be spilled again. 164081a038218171860ee4c382849c647d3dc841fe8bEvan Cheng nI.weight = HUGE_VALF; 16410cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng continue; 16420cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng } 16430cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng 16440cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng // Keep track of the last def and first use in each MBB. 16450cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng if (HasDef) { 16460cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng if (MI != ReMatOrigDefMI || !CanDelete) { 16470cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng bool HasKill = false; 16480cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng if (!HasUse) 16490cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng HasKill = anyKillInMBBAfterIdx(li, I->valno, MBB, getDefIndex(index)); 16500cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng else { 16511953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng // If this is a two-address code, then this index starts a new VNInfo. 16523f32d65912b4da23793dab618d981be2ce11c331Evan Cheng const VNInfo *VNI = li.findDefinedVNInfo(getDefIndex(index)); 16530cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng if (VNI) 16540cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng HasKill = anyKillInMBBAfterIdx(li, VNI, MBB, getDefIndex(index)); 165581a038218171860ee4c382849c647d3dc841fe8bEvan Cheng } 1656289983123ba4170c8a27e9638935818f8142bc89Owen Anderson DenseMap<unsigned, std::vector<SRInfo> >::iterator SII = 1657e3110d0825e6316fd2dd21d6a4e593295cd413f1Evan Cheng SpillIdxes.find(MBBId); 16580cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng if (!HasKill) { 16591953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng if (SII == SpillIdxes.end()) { 16601953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng std::vector<SRInfo> S; 16611953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng S.push_back(SRInfo(index, NewVReg, true)); 16621953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng SpillIdxes.insert(std::make_pair(MBBId, S)); 16631953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng } else if (SII->second.back().vreg != NewVReg) { 16641953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng SII->second.push_back(SRInfo(index, NewVReg, true)); 16651953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng } else if ((int)index > SII->second.back().index) { 16660cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng // If there is an earlier def and this is a two-address 16670cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng // instruction, then it's not possible to fold the store (which 16680cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng // would also fold the load). 16691953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng SRInfo &Info = SII->second.back(); 16701953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng Info.index = index; 16711953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng Info.canFold = !HasUse; 167281a038218171860ee4c382849c647d3dc841fe8bEvan Cheng } 16730cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng SpillMBBs.set(MBBId); 1674e3110d0825e6316fd2dd21d6a4e593295cd413f1Evan Cheng } else if (SII != SpillIdxes.end() && 1675e3110d0825e6316fd2dd21d6a4e593295cd413f1Evan Cheng SII->second.back().vreg == NewVReg && 1676e3110d0825e6316fd2dd21d6a4e593295cd413f1Evan Cheng (int)index > SII->second.back().index) { 1677e3110d0825e6316fd2dd21d6a4e593295cd413f1Evan Cheng // There is an earlier def that's not killed (must be two-address). 1678e3110d0825e6316fd2dd21d6a4e593295cd413f1Evan Cheng // The spill is no longer needed. 1679e3110d0825e6316fd2dd21d6a4e593295cd413f1Evan Cheng SII->second.pop_back(); 1680e3110d0825e6316fd2dd21d6a4e593295cd413f1Evan Cheng if (SII->second.empty()) { 1681e3110d0825e6316fd2dd21d6a4e593295cd413f1Evan Cheng SpillIdxes.erase(MBBId); 1682e3110d0825e6316fd2dd21d6a4e593295cd413f1Evan Cheng SpillMBBs.reset(MBBId); 1683e3110d0825e6316fd2dd21d6a4e593295cd413f1Evan Cheng } 168481a038218171860ee4c382849c647d3dc841fe8bEvan Cheng } 168581a038218171860ee4c382849c647d3dc841fe8bEvan Cheng } 16860cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng } 168781a038218171860ee4c382849c647d3dc841fe8bEvan Cheng 16880cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng if (HasUse) { 1689289983123ba4170c8a27e9638935818f8142bc89Owen Anderson DenseMap<unsigned, std::vector<SRInfo> >::iterator SII = 16900cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng SpillIdxes.find(MBBId); 16911953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng if (SII != SpillIdxes.end() && 16921953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng SII->second.back().vreg == NewVReg && 16931953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng (int)index > SII->second.back().index) 16940cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng // Use(s) following the last def, it's not safe to fold the spill. 16951953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng SII->second.back().canFold = false; 1696289983123ba4170c8a27e9638935818f8142bc89Owen Anderson DenseMap<unsigned, std::vector<SRInfo> >::iterator RII = 16970cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng RestoreIdxes.find(MBBId); 16981953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng if (RII != RestoreIdxes.end() && RII->second.back().vreg == NewVReg) 16990cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng // If we are splitting live intervals, only fold if it's the first 17000cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng // use and there isn't another use later in the MBB. 17011953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng RII->second.back().canFold = false; 17020cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng else if (IsNew) { 17030cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng // Only need a reload if there isn't an earlier def / use. 17041953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng if (RII == RestoreIdxes.end()) { 17051953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng std::vector<SRInfo> Infos; 17061953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng Infos.push_back(SRInfo(index, NewVReg, true)); 17071953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng RestoreIdxes.insert(std::make_pair(MBBId, Infos)); 17081953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng } else { 17091953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng RII->second.push_back(SRInfo(index, NewVReg, true)); 17101953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng } 17110cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng RestoreMBBs.set(MBBId); 17120cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng } 171381a038218171860ee4c382849c647d3dc841fe8bEvan Cheng } 17140cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng 17150cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng // Update spill weight. 171622f07ffd27d1d721634d502c37267721d2e025cfEvan Cheng unsigned loopDepth = loopInfo->getLoopDepth(MBB); 1717c3417609ae6e744a29be6962d4fb7811c0102d17Evan Cheng nI.weight += getSpillWeight(HasDef, HasUse, loopDepth); 1718f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng } 1719018f9b020bb12b731b0a7081578e5f82fb35092dEvan Cheng 1720018f9b020bb12b731b0a7081578e5f82fb35092dEvan Cheng if (NewVReg && TrySplit && AllCanFold) { 1721018f9b020bb12b731b0a7081578e5f82fb35092dEvan Cheng // If all of its def / use can be folded, give it a low spill weight. 1722018f9b020bb12b731b0a7081578e5f82fb35092dEvan Cheng LiveInterval &nI = getOrCreateInterval(NewVReg); 1723018f9b020bb12b731b0a7081578e5f82fb35092dEvan Cheng nI.weight /= 10.0F; 1724018f9b020bb12b731b0a7081578e5f82fb35092dEvan Cheng } 1725f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng} 1726f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng 17271953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Chengbool LiveIntervals::alsoFoldARestore(int Id, int index, unsigned vr, 17281953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng BitVector &RestoreMBBs, 1729289983123ba4170c8a27e9638935818f8142bc89Owen Anderson DenseMap<unsigned,std::vector<SRInfo> > &RestoreIdxes) { 17301953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng if (!RestoreMBBs[Id]) 17311953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng return false; 17321953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng std::vector<SRInfo> &Restores = RestoreIdxes[Id]; 17331953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng for (unsigned i = 0, e = Restores.size(); i != e; ++i) 17341953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng if (Restores[i].index == index && 17351953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng Restores[i].vreg == vr && 17361953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng Restores[i].canFold) 17371953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng return true; 17381953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng return false; 17391953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng} 17401953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng 17411953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Chengvoid LiveIntervals::eraseRestoreInfo(int Id, int index, unsigned vr, 17421953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng BitVector &RestoreMBBs, 1743289983123ba4170c8a27e9638935818f8142bc89Owen Anderson DenseMap<unsigned,std::vector<SRInfo> > &RestoreIdxes) { 17441953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng if (!RestoreMBBs[Id]) 17451953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng return; 17461953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng std::vector<SRInfo> &Restores = RestoreIdxes[Id]; 17471953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng for (unsigned i = 0, e = Restores.size(); i != e; ++i) 17481953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng if (Restores[i].index == index && Restores[i].vreg) 17491953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng Restores[i].index = -1; 17501953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng} 175181a038218171860ee4c382849c647d3dc841fe8bEvan Cheng 17524cce6b4c7882ef0cc993d931b90bf33985c96110Evan Cheng/// handleSpilledImpDefs - Remove IMPLICIT_DEF instructions which are being 17534cce6b4c7882ef0cc993d931b90bf33985c96110Evan Cheng/// spilled and create empty intervals for their uses. 17544cce6b4c7882ef0cc993d931b90bf33985c96110Evan Chengvoid 17554cce6b4c7882ef0cc993d931b90bf33985c96110Evan ChengLiveIntervals::handleSpilledImpDefs(const LiveInterval &li, VirtRegMap &vrm, 17564cce6b4c7882ef0cc993d931b90bf33985c96110Evan Cheng const TargetRegisterClass* rc, 17574cce6b4c7882ef0cc993d931b90bf33985c96110Evan Cheng std::vector<LiveInterval*> &NewLIs) { 1758419852ca8a01aecde4c0e20af6b7bd6450e70f87Evan Cheng for (MachineRegisterInfo::reg_iterator ri = mri_->reg_begin(li.reg), 1759419852ca8a01aecde4c0e20af6b7bd6450e70f87Evan Cheng re = mri_->reg_end(); ri != re; ) { 17604cce6b4c7882ef0cc993d931b90bf33985c96110Evan Cheng MachineOperand &O = ri.getOperand(); 1761419852ca8a01aecde4c0e20af6b7bd6450e70f87Evan Cheng MachineInstr *MI = &*ri; 1762419852ca8a01aecde4c0e20af6b7bd6450e70f87Evan Cheng ++ri; 17634cce6b4c7882ef0cc993d931b90bf33985c96110Evan Cheng if (O.isDef()) { 17644cce6b4c7882ef0cc993d931b90bf33985c96110Evan Cheng assert(MI->getOpcode() == TargetInstrInfo::IMPLICIT_DEF && 17654cce6b4c7882ef0cc993d931b90bf33985c96110Evan Cheng "Register def was not rewritten?"); 17664cce6b4c7882ef0cc993d931b90bf33985c96110Evan Cheng RemoveMachineInstrFromMaps(MI); 17674cce6b4c7882ef0cc993d931b90bf33985c96110Evan Cheng vrm.RemoveMachineInstrFromMaps(MI); 17684cce6b4c7882ef0cc993d931b90bf33985c96110Evan Cheng MI->eraseFromParent(); 17694cce6b4c7882ef0cc993d931b90bf33985c96110Evan Cheng } else { 17704cce6b4c7882ef0cc993d931b90bf33985c96110Evan Cheng // This must be an use of an implicit_def so it's not part of the live 17714cce6b4c7882ef0cc993d931b90bf33985c96110Evan Cheng // interval. Create a new empty live interval for it. 17724cce6b4c7882ef0cc993d931b90bf33985c96110Evan Cheng // FIXME: Can we simply erase some of the instructions? e.g. Stores? 17734cce6b4c7882ef0cc993d931b90bf33985c96110Evan Cheng unsigned NewVReg = mri_->createVirtualRegister(rc); 17744cce6b4c7882ef0cc993d931b90bf33985c96110Evan Cheng vrm.grow(); 17754cce6b4c7882ef0cc993d931b90bf33985c96110Evan Cheng vrm.setIsImplicitlyDefined(NewVReg); 17764cce6b4c7882ef0cc993d931b90bf33985c96110Evan Cheng NewLIs.push_back(&getOrCreateInterval(NewVReg)); 17774cce6b4c7882ef0cc993d931b90bf33985c96110Evan Cheng for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) { 17784cce6b4c7882ef0cc993d931b90bf33985c96110Evan Cheng MachineOperand &MO = MI->getOperand(i); 1779d735b8019b0f297d7c14b55adcd887af24d8e602Dan Gohman if (MO.isReg() && MO.getReg() == li.reg) 17804cce6b4c7882ef0cc993d931b90bf33985c96110Evan Cheng MO.setReg(NewVReg); 17814cce6b4c7882ef0cc993d931b90bf33985c96110Evan Cheng } 17824cce6b4c7882ef0cc993d931b90bf33985c96110Evan Cheng } 1783419852ca8a01aecde4c0e20af6b7bd6450e70f87Evan Cheng } 1784419852ca8a01aecde4c0e20af6b7bd6450e70f87Evan Cheng} 1785419852ca8a01aecde4c0e20af6b7bd6450e70f87Evan Cheng 1786f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Chengstd::vector<LiveInterval*> LiveIntervals:: 1787d6664311acbd05a8a710ccea8f9f5fdbfa35f834Owen AndersonaddIntervalsForSpillsFast(const LiveInterval &li, 1788d6664311acbd05a8a710ccea8f9f5fdbfa35f834Owen Anderson const MachineLoopInfo *loopInfo, 1789c781a243a3d17e7e763515794168d8fa6043f565Evan Cheng VirtRegMap &vrm) { 17901719731d3d8ab6a986d67912f35daaad4f6910dbOwen Anderson unsigned slot = vrm.assignVirt2StackSlot(li.reg); 1791d6664311acbd05a8a710ccea8f9f5fdbfa35f834Owen Anderson 1792d6664311acbd05a8a710ccea8f9f5fdbfa35f834Owen Anderson std::vector<LiveInterval*> added; 1793d6664311acbd05a8a710ccea8f9f5fdbfa35f834Owen Anderson 1794d6664311acbd05a8a710ccea8f9f5fdbfa35f834Owen Anderson assert(li.weight != HUGE_VALF && 1795d6664311acbd05a8a710ccea8f9f5fdbfa35f834Owen Anderson "attempt to spill already spilled interval!"); 1796d6664311acbd05a8a710ccea8f9f5fdbfa35f834Owen Anderson 1797d6664311acbd05a8a710ccea8f9f5fdbfa35f834Owen Anderson DOUT << "\t\t\t\tadding intervals for spills for interval: "; 1798d6664311acbd05a8a710ccea8f9f5fdbfa35f834Owen Anderson DEBUG(li.dump()); 1799d6664311acbd05a8a710ccea8f9f5fdbfa35f834Owen Anderson DOUT << '\n'; 1800d6664311acbd05a8a710ccea8f9f5fdbfa35f834Owen Anderson 1801d6664311acbd05a8a710ccea8f9f5fdbfa35f834Owen Anderson const TargetRegisterClass* rc = mri_->getRegClass(li.reg); 1802d6664311acbd05a8a710ccea8f9f5fdbfa35f834Owen Anderson 1803a41e47afc19d2beb741edae16e3918aadade325dOwen Anderson MachineRegisterInfo::reg_iterator RI = mri_->reg_begin(li.reg); 1804a41e47afc19d2beb741edae16e3918aadade325dOwen Anderson while (RI != mri_->reg_end()) { 1805a41e47afc19d2beb741edae16e3918aadade325dOwen Anderson MachineInstr* MI = &*RI; 18068dc2cbe793ff577f69c17426d6dfaef94ad69191Owen Anderson 1807a41e47afc19d2beb741edae16e3918aadade325dOwen Anderson SmallVector<unsigned, 2> Indices; 1808a41e47afc19d2beb741edae16e3918aadade325dOwen Anderson bool HasUse = false; 1809a41e47afc19d2beb741edae16e3918aadade325dOwen Anderson bool HasDef = false; 18108dc2cbe793ff577f69c17426d6dfaef94ad69191Owen Anderson 1811a41e47afc19d2beb741edae16e3918aadade325dOwen Anderson for (unsigned i = 0; i != MI->getNumOperands(); ++i) { 1812a41e47afc19d2beb741edae16e3918aadade325dOwen Anderson MachineOperand& mop = MI->getOperand(i); 1813d735b8019b0f297d7c14b55adcd887af24d8e602Dan Gohman if (!mop.isReg() || mop.getReg() != li.reg) continue; 1814a41e47afc19d2beb741edae16e3918aadade325dOwen Anderson 1815a41e47afc19d2beb741edae16e3918aadade325dOwen Anderson HasUse |= MI->getOperand(i).isUse(); 1816a41e47afc19d2beb741edae16e3918aadade325dOwen Anderson HasDef |= MI->getOperand(i).isDef(); 1817a41e47afc19d2beb741edae16e3918aadade325dOwen Anderson 1818a41e47afc19d2beb741edae16e3918aadade325dOwen Anderson Indices.push_back(i); 1819d6664311acbd05a8a710ccea8f9f5fdbfa35f834Owen Anderson } 18201719731d3d8ab6a986d67912f35daaad4f6910dbOwen Anderson 1821a41e47afc19d2beb741edae16e3918aadade325dOwen Anderson if (!tryFoldMemoryOperand(MI, vrm, NULL, getInstructionIndex(MI), 1822a41e47afc19d2beb741edae16e3918aadade325dOwen Anderson Indices, true, slot, li.reg)) { 1823a41e47afc19d2beb741edae16e3918aadade325dOwen Anderson unsigned NewVReg = mri_->createVirtualRegister(rc); 1824a41e47afc19d2beb741edae16e3918aadade325dOwen Anderson vrm.grow(); 1825a41e47afc19d2beb741edae16e3918aadade325dOwen Anderson vrm.assignVirt2StackSlot(NewVReg, slot); 1826a41e47afc19d2beb741edae16e3918aadade325dOwen Anderson 1827a41e47afc19d2beb741edae16e3918aadade325dOwen Anderson // create a new register for this spill 1828a41e47afc19d2beb741edae16e3918aadade325dOwen Anderson LiveInterval &nI = getOrCreateInterval(NewVReg); 1829a41e47afc19d2beb741edae16e3918aadade325dOwen Anderson 1830a41e47afc19d2beb741edae16e3918aadade325dOwen Anderson // the spill weight is now infinity as it 1831a41e47afc19d2beb741edae16e3918aadade325dOwen Anderson // cannot be spilled again 1832a41e47afc19d2beb741edae16e3918aadade325dOwen Anderson nI.weight = HUGE_VALF; 1833a41e47afc19d2beb741edae16e3918aadade325dOwen Anderson 1834a41e47afc19d2beb741edae16e3918aadade325dOwen Anderson // Rewrite register operands to use the new vreg. 1835a41e47afc19d2beb741edae16e3918aadade325dOwen Anderson for (SmallVectorImpl<unsigned>::iterator I = Indices.begin(), 1836a41e47afc19d2beb741edae16e3918aadade325dOwen Anderson E = Indices.end(); I != E; ++I) { 1837a41e47afc19d2beb741edae16e3918aadade325dOwen Anderson MI->getOperand(*I).setReg(NewVReg); 1838a41e47afc19d2beb741edae16e3918aadade325dOwen Anderson 1839a41e47afc19d2beb741edae16e3918aadade325dOwen Anderson if (MI->getOperand(*I).isUse()) 1840a41e47afc19d2beb741edae16e3918aadade325dOwen Anderson MI->getOperand(*I).setIsKill(true); 1841a41e47afc19d2beb741edae16e3918aadade325dOwen Anderson } 1842a41e47afc19d2beb741edae16e3918aadade325dOwen Anderson 1843a41e47afc19d2beb741edae16e3918aadade325dOwen Anderson // Fill in the new live interval. 1844a41e47afc19d2beb741edae16e3918aadade325dOwen Anderson unsigned index = getInstructionIndex(MI); 1845a41e47afc19d2beb741edae16e3918aadade325dOwen Anderson if (HasUse) { 1846a41e47afc19d2beb741edae16e3918aadade325dOwen Anderson LiveRange LR(getLoadIndex(index), getUseIndex(index), 1847857c4e01f85601cf2084adb860616256ee47c177Lang Hames nI.getNextValue(0, 0, false, getVNInfoAllocator())); 1848a41e47afc19d2beb741edae16e3918aadade325dOwen Anderson DOUT << " +" << LR; 1849a41e47afc19d2beb741edae16e3918aadade325dOwen Anderson nI.addRange(LR); 1850a41e47afc19d2beb741edae16e3918aadade325dOwen Anderson vrm.addRestorePoint(NewVReg, MI); 1851a41e47afc19d2beb741edae16e3918aadade325dOwen Anderson } 1852a41e47afc19d2beb741edae16e3918aadade325dOwen Anderson if (HasDef) { 1853a41e47afc19d2beb741edae16e3918aadade325dOwen Anderson LiveRange LR(getDefIndex(index), getStoreIndex(index), 1854857c4e01f85601cf2084adb860616256ee47c177Lang Hames nI.getNextValue(0, 0, false, getVNInfoAllocator())); 1855a41e47afc19d2beb741edae16e3918aadade325dOwen Anderson DOUT << " +" << LR; 1856a41e47afc19d2beb741edae16e3918aadade325dOwen Anderson nI.addRange(LR); 1857a41e47afc19d2beb741edae16e3918aadade325dOwen Anderson vrm.addSpillPoint(NewVReg, true, MI); 1858a41e47afc19d2beb741edae16e3918aadade325dOwen Anderson } 1859a41e47afc19d2beb741edae16e3918aadade325dOwen Anderson 18601719731d3d8ab6a986d67912f35daaad4f6910dbOwen Anderson added.push_back(&nI); 18618dc2cbe793ff577f69c17426d6dfaef94ad69191Owen Anderson 1862a41e47afc19d2beb741edae16e3918aadade325dOwen Anderson DOUT << "\t\t\t\tadded new interval: "; 1863a41e47afc19d2beb741edae16e3918aadade325dOwen Anderson DEBUG(nI.dump()); 1864a41e47afc19d2beb741edae16e3918aadade325dOwen Anderson DOUT << '\n'; 1865a41e47afc19d2beb741edae16e3918aadade325dOwen Anderson } 18669a032931453209505f6765a35be108ae5ea39b3bOwen Anderson 18679a032931453209505f6765a35be108ae5ea39b3bOwen Anderson 1868a41e47afc19d2beb741edae16e3918aadade325dOwen Anderson RI = mri_->reg_begin(li.reg); 1869d6664311acbd05a8a710ccea8f9f5fdbfa35f834Owen Anderson } 1870d6664311acbd05a8a710ccea8f9f5fdbfa35f834Owen Anderson 1871d6664311acbd05a8a710ccea8f9f5fdbfa35f834Owen Anderson return added; 1872d6664311acbd05a8a710ccea8f9f5fdbfa35f834Owen Anderson} 1873d6664311acbd05a8a710ccea8f9f5fdbfa35f834Owen Anderson 1874d6664311acbd05a8a710ccea8f9f5fdbfa35f834Owen Andersonstd::vector<LiveInterval*> LiveIntervals:: 187581a038218171860ee4c382849c647d3dc841fe8bEvan ChengaddIntervalsForSpills(const LiveInterval &li, 1876dc37786595beedd0a68d8e2cbd91ae53ad58d133Evan Cheng SmallVectorImpl<LiveInterval*> &SpillIs, 1877c781a243a3d17e7e763515794168d8fa6043f565Evan Cheng const MachineLoopInfo *loopInfo, VirtRegMap &vrm) { 1878ae339babb2a2445e7bb009912a39994718f10d54Owen Anderson 1879ae339babb2a2445e7bb009912a39994718f10d54Owen Anderson if (EnableFastSpilling) 1880c781a243a3d17e7e763515794168d8fa6043f565Evan Cheng return addIntervalsForSpillsFast(li, loopInfo, vrm); 1881ae339babb2a2445e7bb009912a39994718f10d54Owen Anderson 1882f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng assert(li.weight != HUGE_VALF && 1883f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng "attempt to spill already spilled interval!"); 1884f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng 1885f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng DOUT << "\t\t\t\tadding intervals for spills for interval: "; 18866f0d024a534af18d9e60b3ea757376cd8a3a980eDan Gohman li.print(DOUT, tri_); 1887f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng DOUT << '\n'; 1888f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng 188972eeb94fe1d69cd05bdbbe86b2bc9fa25c963c22Evan Cheng // Each bit specify whether a spill is required in the MBB. 189081a038218171860ee4c382849c647d3dc841fe8bEvan Cheng BitVector SpillMBBs(mf_->getNumBlockIDs()); 1891289983123ba4170c8a27e9638935818f8142bc89Owen Anderson DenseMap<unsigned, std::vector<SRInfo> > SpillIdxes; 18920cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng BitVector RestoreMBBs(mf_->getNumBlockIDs()); 1893289983123ba4170c8a27e9638935818f8142bc89Owen Anderson DenseMap<unsigned, std::vector<SRInfo> > RestoreIdxes; 1894289983123ba4170c8a27e9638935818f8142bc89Owen Anderson DenseMap<unsigned,unsigned> MBBVRegsMap; 1895f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng std::vector<LiveInterval*> NewLIs; 1896d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng const TargetRegisterClass* rc = mri_->getRegClass(li.reg); 1897f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng 1898f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng unsigned NumValNums = li.getNumValNums(); 1899f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng SmallVector<MachineInstr*, 4> ReMatDefs; 1900f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng ReMatDefs.resize(NumValNums, NULL); 1901f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng SmallVector<MachineInstr*, 4> ReMatOrigDefs; 1902f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng ReMatOrigDefs.resize(NumValNums, NULL); 1903f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng SmallVector<int, 4> ReMatIds; 1904f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng ReMatIds.resize(NumValNums, VirtRegMap::MAX_STACK_SLOT); 1905f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng BitVector ReMatDelete(NumValNums); 1906f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng unsigned Slot = VirtRegMap::MAX_STACK_SLOT; 1907f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng 190881a038218171860ee4c382849c647d3dc841fe8bEvan Cheng // Spilling a split live interval. It cannot be split any further. Also, 190981a038218171860ee4c382849c647d3dc841fe8bEvan Cheng // it's also guaranteed to be a single val# / range interval. 191081a038218171860ee4c382849c647d3dc841fe8bEvan Cheng if (vrm.getPreSplitReg(li.reg)) { 191181a038218171860ee4c382849c647d3dc841fe8bEvan Cheng vrm.setIsSplitFromReg(li.reg, 0); 1912d120ffd26f2715c600b028d4eac9a3c41a9f4653Evan Cheng // Unset the split kill marker on the last use. 1913d120ffd26f2715c600b028d4eac9a3c41a9f4653Evan Cheng unsigned KillIdx = vrm.getKillPoint(li.reg); 1914d120ffd26f2715c600b028d4eac9a3c41a9f4653Evan Cheng if (KillIdx) { 1915d120ffd26f2715c600b028d4eac9a3c41a9f4653Evan Cheng MachineInstr *KillMI = getInstructionFromIndex(KillIdx); 1916d120ffd26f2715c600b028d4eac9a3c41a9f4653Evan Cheng assert(KillMI && "Last use disappeared?"); 1917d120ffd26f2715c600b028d4eac9a3c41a9f4653Evan Cheng int KillOp = KillMI->findRegisterUseOperandIdx(li.reg, true); 1918d120ffd26f2715c600b028d4eac9a3c41a9f4653Evan Cheng assert(KillOp != -1 && "Last use disappeared?"); 1919f73823000e2d5d6e1cf65bdf5a107297e18d35fbChris Lattner KillMI->getOperand(KillOp).setIsKill(false); 1920d120ffd26f2715c600b028d4eac9a3c41a9f4653Evan Cheng } 1921adf85906906ebf85c57c333e8209f37ef11a6c99Evan Cheng vrm.removeKillPoint(li.reg); 192281a038218171860ee4c382849c647d3dc841fe8bEvan Cheng bool DefIsReMat = vrm.isReMaterialized(li.reg); 192381a038218171860ee4c382849c647d3dc841fe8bEvan Cheng Slot = vrm.getStackSlot(li.reg); 192481a038218171860ee4c382849c647d3dc841fe8bEvan Cheng assert(Slot != VirtRegMap::MAX_STACK_SLOT); 192581a038218171860ee4c382849c647d3dc841fe8bEvan Cheng MachineInstr *ReMatDefMI = DefIsReMat ? 192681a038218171860ee4c382849c647d3dc841fe8bEvan Cheng vrm.getReMaterializedMI(li.reg) : NULL; 192781a038218171860ee4c382849c647d3dc841fe8bEvan Cheng int LdSlot = 0; 192881a038218171860ee4c382849c647d3dc841fe8bEvan Cheng bool isLoadSS = DefIsReMat && tii_->isLoadFromStackSlot(ReMatDefMI, LdSlot); 192981a038218171860ee4c382849c647d3dc841fe8bEvan Cheng bool isLoad = isLoadSS || 193015511cf1660cfd6bb8b8e8fca2db9450f50430eeDan Gohman (DefIsReMat && (ReMatDefMI->getDesc().canFoldAsLoad())); 193181a038218171860ee4c382849c647d3dc841fe8bEvan Cheng bool IsFirstRange = true; 193281a038218171860ee4c382849c647d3dc841fe8bEvan Cheng for (LiveInterval::Ranges::const_iterator 193381a038218171860ee4c382849c647d3dc841fe8bEvan Cheng I = li.ranges.begin(), E = li.ranges.end(); I != E; ++I) { 193481a038218171860ee4c382849c647d3dc841fe8bEvan Cheng // If this is a split live interval with multiple ranges, it means there 193581a038218171860ee4c382849c647d3dc841fe8bEvan Cheng // are two-address instructions that re-defined the value. Only the 193681a038218171860ee4c382849c647d3dc841fe8bEvan Cheng // first def can be rematerialized! 193781a038218171860ee4c382849c647d3dc841fe8bEvan Cheng if (IsFirstRange) { 1938cb3c330d39442130d0587208d673ce9c33c7008fEvan Cheng // Note ReMatOrigDefMI has already been deleted. 193981a038218171860ee4c382849c647d3dc841fe8bEvan Cheng rewriteInstructionsForSpills(li, false, I, NULL, ReMatDefMI, 194081a038218171860ee4c382849c647d3dc841fe8bEvan Cheng Slot, LdSlot, isLoad, isLoadSS, DefIsReMat, 1941d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng false, vrm, rc, ReMatIds, loopInfo, 19420cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng SpillMBBs, SpillIdxes, RestoreMBBs, RestoreIdxes, 1943c781a243a3d17e7e763515794168d8fa6043f565Evan Cheng MBBVRegsMap, NewLIs); 194481a038218171860ee4c382849c647d3dc841fe8bEvan Cheng } else { 194581a038218171860ee4c382849c647d3dc841fe8bEvan Cheng rewriteInstructionsForSpills(li, false, I, NULL, 0, 194681a038218171860ee4c382849c647d3dc841fe8bEvan Cheng Slot, 0, false, false, false, 1947d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng false, vrm, rc, ReMatIds, loopInfo, 19480cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng SpillMBBs, SpillIdxes, RestoreMBBs, RestoreIdxes, 1949c781a243a3d17e7e763515794168d8fa6043f565Evan Cheng MBBVRegsMap, NewLIs); 195081a038218171860ee4c382849c647d3dc841fe8bEvan Cheng } 195181a038218171860ee4c382849c647d3dc841fe8bEvan Cheng IsFirstRange = false; 195281a038218171860ee4c382849c647d3dc841fe8bEvan Cheng } 1953419852ca8a01aecde4c0e20af6b7bd6450e70f87Evan Cheng 19544cce6b4c7882ef0cc993d931b90bf33985c96110Evan Cheng handleSpilledImpDefs(li, vrm, rc, NewLIs); 195581a038218171860ee4c382849c647d3dc841fe8bEvan Cheng return NewLIs; 195681a038218171860ee4c382849c647d3dc841fe8bEvan Cheng } 195781a038218171860ee4c382849c647d3dc841fe8bEvan Cheng 195881a038218171860ee4c382849c647d3dc841fe8bEvan Cheng bool TrySplit = SplitAtBB && !intervalIsInOneMBB(li); 19590cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng if (SplitLimit != -1 && (int)numSplits >= SplitLimit) 19600cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng TrySplit = false; 19610cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng if (TrySplit) 19620cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng ++numSplits; 1963f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng bool NeedStackSlot = false; 1964f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng for (LiveInterval::const_vni_iterator i = li.vni_begin(), e = li.vni_end(); 1965f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng i != e; ++i) { 1966f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng const VNInfo *VNI = *i; 1967f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng unsigned VN = VNI->id; 1968857c4e01f85601cf2084adb860616256ee47c177Lang Hames if (VNI->isUnused()) 1969f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng continue; // Dead val#. 1970f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng // Is the def for the val# rematerializable? 1971857c4e01f85601cf2084adb860616256ee47c177Lang Hames MachineInstr *ReMatDefMI = VNI->isDefAccurate() 1972857c4e01f85601cf2084adb860616256ee47c177Lang Hames ? getInstructionFromIndex(VNI->def) : 0; 19735ef3a04b542c4e585276768fa9ca2af698ef5c87Evan Cheng bool dummy; 1974dc37786595beedd0a68d8e2cbd91ae53ad58d133Evan Cheng if (ReMatDefMI && isReMaterializable(li, VNI, ReMatDefMI, SpillIs, dummy)) { 1975f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng // Remember how to remat the def of this val#. 197681a038218171860ee4c382849c647d3dc841fe8bEvan Cheng ReMatOrigDefs[VN] = ReMatDefMI; 19772c3f7ae3843bdc9dcfe85393e178211976c1f9bdDan Gohman // Original def may be modified so we have to make a copy here. 19781ed9922794cda9dbe295e74674b909287e544632Evan Cheng MachineInstr *Clone = mf_->CloneMachineInstr(ReMatDefMI); 19791ed9922794cda9dbe295e74674b909287e544632Evan Cheng ClonedMIs.push_back(Clone); 19801ed9922794cda9dbe295e74674b909287e544632Evan Cheng ReMatDefs[VN] = Clone; 1981f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng 1982f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng bool CanDelete = true; 1983857c4e01f85601cf2084adb860616256ee47c177Lang Hames if (VNI->hasPHIKill()) { 1984c3fc7d9ec9b495c8a88cd854247105c296d3aabdEvan Cheng // A kill is a phi node, not all of its uses can be rematerialized. 1985f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng // It must not be deleted. 1986c3fc7d9ec9b495c8a88cd854247105c296d3aabdEvan Cheng CanDelete = false; 1987c3fc7d9ec9b495c8a88cd854247105c296d3aabdEvan Cheng // Need a stack slot if there is any live range where uses cannot be 1988c3fc7d9ec9b495c8a88cd854247105c296d3aabdEvan Cheng // rematerialized. 1989c3fc7d9ec9b495c8a88cd854247105c296d3aabdEvan Cheng NeedStackSlot = true; 1990f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng } 1991f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng if (CanDelete) 1992f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng ReMatDelete.set(VN); 1993f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng } else { 1994f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng // Need a stack slot if there is any live range where uses cannot be 1995f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng // rematerialized. 1996f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng NeedStackSlot = true; 1997f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng } 1998f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng } 1999f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng 2000f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng // One stack slot per live interval. 2001b98bbb7597495fb401b020679a94389298175506Owen Anderson if (NeedStackSlot && vrm.getPreSplitReg(li.reg) == 0) { 2002b98bbb7597495fb401b020679a94389298175506Owen Anderson if (vrm.getStackSlot(li.reg) == VirtRegMap::NO_STACK_SLOT) 2003b98bbb7597495fb401b020679a94389298175506Owen Anderson Slot = vrm.assignVirt2StackSlot(li.reg); 2004b98bbb7597495fb401b020679a94389298175506Owen Anderson 2005b98bbb7597495fb401b020679a94389298175506Owen Anderson // This case only occurs when the prealloc splitter has already assigned 2006b98bbb7597495fb401b020679a94389298175506Owen Anderson // a stack slot to this vreg. 2007b98bbb7597495fb401b020679a94389298175506Owen Anderson else 2008b98bbb7597495fb401b020679a94389298175506Owen Anderson Slot = vrm.getStackSlot(li.reg); 2009b98bbb7597495fb401b020679a94389298175506Owen Anderson } 2010f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng 2011f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng // Create new intervals and rewrite defs and uses. 2012f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng for (LiveInterval::Ranges::const_iterator 2013f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng I = li.ranges.begin(), E = li.ranges.end(); I != E; ++I) { 201481a038218171860ee4c382849c647d3dc841fe8bEvan Cheng MachineInstr *ReMatDefMI = ReMatDefs[I->valno->id]; 201581a038218171860ee4c382849c647d3dc841fe8bEvan Cheng MachineInstr *ReMatOrigDefMI = ReMatOrigDefs[I->valno->id]; 201681a038218171860ee4c382849c647d3dc841fe8bEvan Cheng bool DefIsReMat = ReMatDefMI != NULL; 2017f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng bool CanDelete = ReMatDelete[I->valno->id]; 2018f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng int LdSlot = 0; 201981a038218171860ee4c382849c647d3dc841fe8bEvan Cheng bool isLoadSS = DefIsReMat && tii_->isLoadFromStackSlot(ReMatDefMI, LdSlot); 2020f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng bool isLoad = isLoadSS || 202115511cf1660cfd6bb8b8e8fca2db9450f50430eeDan Gohman (DefIsReMat && ReMatDefMI->getDesc().canFoldAsLoad()); 202281a038218171860ee4c382849c647d3dc841fe8bEvan Cheng rewriteInstructionsForSpills(li, TrySplit, I, ReMatOrigDefMI, ReMatDefMI, 20230cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng Slot, LdSlot, isLoad, isLoadSS, DefIsReMat, 2024d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng CanDelete, vrm, rc, ReMatIds, loopInfo, 20250cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng SpillMBBs, SpillIdxes, RestoreMBBs, RestoreIdxes, 2026c781a243a3d17e7e763515794168d8fa6043f565Evan Cheng MBBVRegsMap, NewLIs); 2027f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng } 2028f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng 20290cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng // Insert spills / restores if we are splitting. 2030419852ca8a01aecde4c0e20af6b7bd6450e70f87Evan Cheng if (!TrySplit) { 20314cce6b4c7882ef0cc993d931b90bf33985c96110Evan Cheng handleSpilledImpDefs(li, vrm, rc, NewLIs); 20321953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng return NewLIs; 2033419852ca8a01aecde4c0e20af6b7bd6450e70f87Evan Cheng } 20341953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng 2035b50bb8cf197709b3f49044740044c06d8f314564Evan Cheng SmallPtrSet<LiveInterval*, 4> AddedKill; 2036aee4af68ae2016afc5b4ec0c430e539c5810a766Evan Cheng SmallVector<unsigned, 2> Ops; 20371953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng if (NeedStackSlot) { 20381953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng int Id = SpillMBBs.find_first(); 20391953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng while (Id != -1) { 20401953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng std::vector<SRInfo> &spills = SpillIdxes[Id]; 20411953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng for (unsigned i = 0, e = spills.size(); i != e; ++i) { 20421953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng int index = spills[i].index; 20431953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng unsigned VReg = spills[i].vreg; 2044597d10d84fb6b34f7776121404d5ed802b21b2b6Evan Cheng LiveInterval &nI = getOrCreateInterval(VReg); 20450cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng bool isReMat = vrm.isReMaterialized(VReg); 20460cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng MachineInstr *MI = getInstructionFromIndex(index); 2047aee4af68ae2016afc5b4ec0c430e539c5810a766Evan Cheng bool CanFold = false; 2048aee4af68ae2016afc5b4ec0c430e539c5810a766Evan Cheng bool FoundUse = false; 2049aee4af68ae2016afc5b4ec0c430e539c5810a766Evan Cheng Ops.clear(); 2050cddbb83ea82e98658d9f530c50a7b9d23249afc2Evan Cheng if (spills[i].canFold) { 2051aee4af68ae2016afc5b4ec0c430e539c5810a766Evan Cheng CanFold = true; 20520cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng for (unsigned j = 0, ee = MI->getNumOperands(); j != ee; ++j) { 20530cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng MachineOperand &MO = MI->getOperand(j); 2054d735b8019b0f297d7c14b55adcd887af24d8e602Dan Gohman if (!MO.isReg() || MO.getReg() != VReg) 20550cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng continue; 2056aee4af68ae2016afc5b4ec0c430e539c5810a766Evan Cheng 2057aee4af68ae2016afc5b4ec0c430e539c5810a766Evan Cheng Ops.push_back(j); 2058aee4af68ae2016afc5b4ec0c430e539c5810a766Evan Cheng if (MO.isDef()) 2059cddbb83ea82e98658d9f530c50a7b9d23249afc2Evan Cheng continue; 2060aee4af68ae2016afc5b4ec0c430e539c5810a766Evan Cheng if (isReMat || 2061aee4af68ae2016afc5b4ec0c430e539c5810a766Evan Cheng (!FoundUse && !alsoFoldARestore(Id, index, VReg, 2062aee4af68ae2016afc5b4ec0c430e539c5810a766Evan Cheng RestoreMBBs, RestoreIdxes))) { 2063aee4af68ae2016afc5b4ec0c430e539c5810a766Evan Cheng // MI has two-address uses of the same register. If the use 2064aee4af68ae2016afc5b4ec0c430e539c5810a766Evan Cheng // isn't the first and only use in the BB, then we can't fold 2065aee4af68ae2016afc5b4ec0c430e539c5810a766Evan Cheng // it. FIXME: Move this to rewriteInstructionsForSpills. 2066aee4af68ae2016afc5b4ec0c430e539c5810a766Evan Cheng CanFold = false; 2067cddbb83ea82e98658d9f530c50a7b9d23249afc2Evan Cheng break; 2068cddbb83ea82e98658d9f530c50a7b9d23249afc2Evan Cheng } 2069aee4af68ae2016afc5b4ec0c430e539c5810a766Evan Cheng FoundUse = true; 20700cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng } 20710cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng } 20720cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng // Fold the store into the def if possible. 2073cddbb83ea82e98658d9f530c50a7b9d23249afc2Evan Cheng bool Folded = false; 2074aee4af68ae2016afc5b4ec0c430e539c5810a766Evan Cheng if (CanFold && !Ops.empty()) { 2075aee4af68ae2016afc5b4ec0c430e539c5810a766Evan Cheng if (tryFoldMemoryOperand(MI, vrm, NULL, index, Ops, true, Slot,VReg)){ 2076cddbb83ea82e98658d9f530c50a7b9d23249afc2Evan Cheng Folded = true; 207748fe63526e35ddaee7e98879596a569911f41319Sebastian Redl if (FoundUse) { 2078aee4af68ae2016afc5b4ec0c430e539c5810a766Evan Cheng // Also folded uses, do not issue a load. 2079aee4af68ae2016afc5b4ec0c430e539c5810a766Evan Cheng eraseRestoreInfo(Id, index, VReg, RestoreMBBs, RestoreIdxes); 2080f38d14f03e495ea98ae16bda6febbde276513294Evan Cheng nI.removeRange(getLoadIndex(index), getUseIndex(index)+1); 2081f38d14f03e495ea98ae16bda6febbde276513294Evan Cheng } 2082597d10d84fb6b34f7776121404d5ed802b21b2b6Evan Cheng nI.removeRange(getDefIndex(index), getStoreIndex(index)); 2083cddbb83ea82e98658d9f530c50a7b9d23249afc2Evan Cheng } 20840cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng } 20850cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng 20867e073baedb8232b9519dbe15ea141ff98ccfe6aeEvan Cheng // Otherwise tell the spiller to issue a spill. 2087b50bb8cf197709b3f49044740044c06d8f314564Evan Cheng if (!Folded) { 2088b50bb8cf197709b3f49044740044c06d8f314564Evan Cheng LiveRange *LR = &nI.ranges[nI.ranges.size()-1]; 2089b50bb8cf197709b3f49044740044c06d8f314564Evan Cheng bool isKill = LR->end == getStoreIndex(index); 2090b0a6f62c9b2e75fc509d84310a9795ffacbc6796Evan Cheng if (!MI->registerDefIsDead(nI.reg)) 2091b0a6f62c9b2e75fc509d84310a9795ffacbc6796Evan Cheng // No need to spill a dead def. 2092b0a6f62c9b2e75fc509d84310a9795ffacbc6796Evan Cheng vrm.addSpillPoint(VReg, isKill, MI); 2093b50bb8cf197709b3f49044740044c06d8f314564Evan Cheng if (isKill) 2094b50bb8cf197709b3f49044740044c06d8f314564Evan Cheng AddedKill.insert(&nI); 2095b50bb8cf197709b3f49044740044c06d8f314564Evan Cheng } 20960cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng } 20971953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng Id = SpillMBBs.find_next(Id); 20980cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng } 20991953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng } 21000cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng 21011953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng int Id = RestoreMBBs.find_first(); 21021953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng while (Id != -1) { 21031953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng std::vector<SRInfo> &restores = RestoreIdxes[Id]; 21041953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng for (unsigned i = 0, e = restores.size(); i != e; ++i) { 21051953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng int index = restores[i].index; 21061953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng if (index == -1) 21071953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng continue; 21081953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng unsigned VReg = restores[i].vreg; 2109597d10d84fb6b34f7776121404d5ed802b21b2b6Evan Cheng LiveInterval &nI = getOrCreateInterval(VReg); 21109c3c2213647e3f1b71722d61875ebac01b65cb91Evan Cheng bool isReMat = vrm.isReMaterialized(VReg); 211181a038218171860ee4c382849c647d3dc841fe8bEvan Cheng MachineInstr *MI = getInstructionFromIndex(index); 2112aee4af68ae2016afc5b4ec0c430e539c5810a766Evan Cheng bool CanFold = false; 2113aee4af68ae2016afc5b4ec0c430e539c5810a766Evan Cheng Ops.clear(); 2114cddbb83ea82e98658d9f530c50a7b9d23249afc2Evan Cheng if (restores[i].canFold) { 2115aee4af68ae2016afc5b4ec0c430e539c5810a766Evan Cheng CanFold = true; 211681a038218171860ee4c382849c647d3dc841fe8bEvan Cheng for (unsigned j = 0, ee = MI->getNumOperands(); j != ee; ++j) { 211781a038218171860ee4c382849c647d3dc841fe8bEvan Cheng MachineOperand &MO = MI->getOperand(j); 2118d735b8019b0f297d7c14b55adcd887af24d8e602Dan Gohman if (!MO.isReg() || MO.getReg() != VReg) 211981a038218171860ee4c382849c647d3dc841fe8bEvan Cheng continue; 2120aee4af68ae2016afc5b4ec0c430e539c5810a766Evan Cheng 21210cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng if (MO.isDef()) { 2122aee4af68ae2016afc5b4ec0c430e539c5810a766Evan Cheng // If this restore were to be folded, it would have been folded 2123aee4af68ae2016afc5b4ec0c430e539c5810a766Evan Cheng // already. 2124aee4af68ae2016afc5b4ec0c430e539c5810a766Evan Cheng CanFold = false; 212581a038218171860ee4c382849c647d3dc841fe8bEvan Cheng break; 212681a038218171860ee4c382849c647d3dc841fe8bEvan Cheng } 2127aee4af68ae2016afc5b4ec0c430e539c5810a766Evan Cheng Ops.push_back(j); 212881a038218171860ee4c382849c647d3dc841fe8bEvan Cheng } 212981a038218171860ee4c382849c647d3dc841fe8bEvan Cheng } 21300cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng 21310cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng // Fold the load into the use if possible. 2132cddbb83ea82e98658d9f530c50a7b9d23249afc2Evan Cheng bool Folded = false; 2133aee4af68ae2016afc5b4ec0c430e539c5810a766Evan Cheng if (CanFold && !Ops.empty()) { 21349c3c2213647e3f1b71722d61875ebac01b65cb91Evan Cheng if (!isReMat) 2135aee4af68ae2016afc5b4ec0c430e539c5810a766Evan Cheng Folded = tryFoldMemoryOperand(MI, vrm, NULL,index,Ops,true,Slot,VReg); 2136aee4af68ae2016afc5b4ec0c430e539c5810a766Evan Cheng else { 21370cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng MachineInstr *ReMatDefMI = vrm.getReMaterializedMI(VReg); 21380cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng int LdSlot = 0; 21390cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng bool isLoadSS = tii_->isLoadFromStackSlot(ReMatDefMI, LdSlot); 21400cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng // If the rematerializable def is a load, also try to fold it. 214115511cf1660cfd6bb8b8e8fca2db9450f50430eeDan Gohman if (isLoadSS || ReMatDefMI->getDesc().canFoldAsLoad()) 2142aee4af68ae2016afc5b4ec0c430e539c5810a766Evan Cheng Folded = tryFoldMemoryOperand(MI, vrm, ReMatDefMI, index, 2143aee4af68ae2016afc5b4ec0c430e539c5810a766Evan Cheng Ops, isLoadSS, LdSlot, VReg); 2144650d7f3ff4d22646def71b842f7f163c539e0aafEvan Cheng if (!Folded) { 2145650d7f3ff4d22646def71b842f7f163c539e0aafEvan Cheng unsigned ImpUse = getReMatImplicitUse(li, ReMatDefMI); 2146650d7f3ff4d22646def71b842f7f163c539e0aafEvan Cheng if (ImpUse) { 2147650d7f3ff4d22646def71b842f7f163c539e0aafEvan Cheng // Re-matting an instruction with virtual register use. Add the 2148650d7f3ff4d22646def71b842f7f163c539e0aafEvan Cheng // register as an implicit use on the use MI and update the register 2149650d7f3ff4d22646def71b842f7f163c539e0aafEvan Cheng // interval's spill weight to HUGE_VALF to prevent it from being 2150650d7f3ff4d22646def71b842f7f163c539e0aafEvan Cheng // spilled. 2151650d7f3ff4d22646def71b842f7f163c539e0aafEvan Cheng LiveInterval &ImpLi = getInterval(ImpUse); 2152650d7f3ff4d22646def71b842f7f163c539e0aafEvan Cheng ImpLi.weight = HUGE_VALF; 2153650d7f3ff4d22646def71b842f7f163c539e0aafEvan Cheng MI->addOperand(MachineOperand::CreateReg(ImpUse, false, true)); 2154650d7f3ff4d22646def71b842f7f163c539e0aafEvan Cheng } 2155d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng } 2156aee4af68ae2016afc5b4ec0c430e539c5810a766Evan Cheng } 21570cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng } 21580cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng // If folding is not possible / failed, then tell the spiller to issue a 21590cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng // load / rematerialization for us. 2160597d10d84fb6b34f7776121404d5ed802b21b2b6Evan Cheng if (Folded) 2161597d10d84fb6b34f7776121404d5ed802b21b2b6Evan Cheng nI.removeRange(getLoadIndex(index), getUseIndex(index)+1); 2162b50bb8cf197709b3f49044740044c06d8f314564Evan Cheng else 21630cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng vrm.addRestorePoint(VReg, MI); 216481a038218171860ee4c382849c647d3dc841fe8bEvan Cheng } 21651953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng Id = RestoreMBBs.find_next(Id); 216681a038218171860ee4c382849c647d3dc841fe8bEvan Cheng } 216781a038218171860ee4c382849c647d3dc841fe8bEvan Cheng 2168b50bb8cf197709b3f49044740044c06d8f314564Evan Cheng // Finalize intervals: add kills, finalize spill weights, and filter out 2169b50bb8cf197709b3f49044740044c06d8f314564Evan Cheng // dead intervals. 2170597d10d84fb6b34f7776121404d5ed802b21b2b6Evan Cheng std::vector<LiveInterval*> RetNewLIs; 2171597d10d84fb6b34f7776121404d5ed802b21b2b6Evan Cheng for (unsigned i = 0, e = NewLIs.size(); i != e; ++i) { 2172597d10d84fb6b34f7776121404d5ed802b21b2b6Evan Cheng LiveInterval *LI = NewLIs[i]; 2173597d10d84fb6b34f7776121404d5ed802b21b2b6Evan Cheng if (!LI->empty()) { 2174496bac5b084474ac33109bad24c1ef94c843e16fOwen Anderson LI->weight /= InstrSlots::NUM * getApproximateInstructionCount(*LI); 2175b50bb8cf197709b3f49044740044c06d8f314564Evan Cheng if (!AddedKill.count(LI)) { 2176b50bb8cf197709b3f49044740044c06d8f314564Evan Cheng LiveRange *LR = &LI->ranges[LI->ranges.size()-1]; 2177d120ffd26f2715c600b028d4eac9a3c41a9f4653Evan Cheng unsigned LastUseIdx = getBaseIndex(LR->end); 2178d120ffd26f2715c600b028d4eac9a3c41a9f4653Evan Cheng MachineInstr *LastUse = getInstructionFromIndex(LastUseIdx); 21796130f66eaae89f8878590796977678afa8448926Evan Cheng int UseIdx = LastUse->findRegisterUseOperandIdx(LI->reg, false); 2180b50bb8cf197709b3f49044740044c06d8f314564Evan Cheng assert(UseIdx != -1); 2181a24752ff43dc1ad8c18c5d9e78549c45f62b980eEvan Cheng if (!LastUse->isRegTiedToDefOperand(UseIdx)) { 2182b50bb8cf197709b3f49044740044c06d8f314564Evan Cheng LastUse->getOperand(UseIdx).setIsKill(); 2183d120ffd26f2715c600b028d4eac9a3c41a9f4653Evan Cheng vrm.addKillPoint(LI->reg, LastUseIdx); 2184adf85906906ebf85c57c333e8209f37ef11a6c99Evan Cheng } 2185b50bb8cf197709b3f49044740044c06d8f314564Evan Cheng } 2186597d10d84fb6b34f7776121404d5ed802b21b2b6Evan Cheng RetNewLIs.push_back(LI); 2187597d10d84fb6b34f7776121404d5ed802b21b2b6Evan Cheng } 2188597d10d84fb6b34f7776121404d5ed802b21b2b6Evan Cheng } 218981a038218171860ee4c382849c647d3dc841fe8bEvan Cheng 21904cce6b4c7882ef0cc993d931b90bf33985c96110Evan Cheng handleSpilledImpDefs(li, vrm, rc, RetNewLIs); 2191597d10d84fb6b34f7776121404d5ed802b21b2b6Evan Cheng return RetNewLIs; 2192f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng} 2193676dd7c80b6f91178452535ac45ca58feb23cc42Evan Cheng 2194676dd7c80b6f91178452535ac45ca58feb23cc42Evan Cheng/// hasAllocatableSuperReg - Return true if the specified physical register has 2195676dd7c80b6f91178452535ac45ca58feb23cc42Evan Cheng/// any super register that's allocatable. 2196676dd7c80b6f91178452535ac45ca58feb23cc42Evan Chengbool LiveIntervals::hasAllocatableSuperReg(unsigned Reg) const { 2197676dd7c80b6f91178452535ac45ca58feb23cc42Evan Cheng for (const unsigned* AS = tri_->getSuperRegisters(Reg); *AS; ++AS) 2198676dd7c80b6f91178452535ac45ca58feb23cc42Evan Cheng if (allocatableRegs_[*AS] && hasInterval(*AS)) 2199676dd7c80b6f91178452535ac45ca58feb23cc42Evan Cheng return true; 2200676dd7c80b6f91178452535ac45ca58feb23cc42Evan Cheng return false; 2201676dd7c80b6f91178452535ac45ca58feb23cc42Evan Cheng} 2202676dd7c80b6f91178452535ac45ca58feb23cc42Evan Cheng 2203676dd7c80b6f91178452535ac45ca58feb23cc42Evan Cheng/// getRepresentativeReg - Find the largest super register of the specified 2204676dd7c80b6f91178452535ac45ca58feb23cc42Evan Cheng/// physical register. 2205676dd7c80b6f91178452535ac45ca58feb23cc42Evan Chengunsigned LiveIntervals::getRepresentativeReg(unsigned Reg) const { 2206676dd7c80b6f91178452535ac45ca58feb23cc42Evan Cheng // Find the largest super-register that is allocatable. 2207676dd7c80b6f91178452535ac45ca58feb23cc42Evan Cheng unsigned BestReg = Reg; 2208676dd7c80b6f91178452535ac45ca58feb23cc42Evan Cheng for (const unsigned* AS = tri_->getSuperRegisters(Reg); *AS; ++AS) { 2209676dd7c80b6f91178452535ac45ca58feb23cc42Evan Cheng unsigned SuperReg = *AS; 2210676dd7c80b6f91178452535ac45ca58feb23cc42Evan Cheng if (!hasAllocatableSuperReg(SuperReg) && hasInterval(SuperReg)) { 2211676dd7c80b6f91178452535ac45ca58feb23cc42Evan Cheng BestReg = SuperReg; 2212676dd7c80b6f91178452535ac45ca58feb23cc42Evan Cheng break; 2213676dd7c80b6f91178452535ac45ca58feb23cc42Evan Cheng } 2214676dd7c80b6f91178452535ac45ca58feb23cc42Evan Cheng } 2215676dd7c80b6f91178452535ac45ca58feb23cc42Evan Cheng return BestReg; 2216676dd7c80b6f91178452535ac45ca58feb23cc42Evan Cheng} 2217676dd7c80b6f91178452535ac45ca58feb23cc42Evan Cheng 2218676dd7c80b6f91178452535ac45ca58feb23cc42Evan Cheng/// getNumConflictsWithPhysReg - Return the number of uses and defs of the 2219676dd7c80b6f91178452535ac45ca58feb23cc42Evan Cheng/// specified interval that conflicts with the specified physical register. 2220676dd7c80b6f91178452535ac45ca58feb23cc42Evan Chengunsigned LiveIntervals::getNumConflictsWithPhysReg(const LiveInterval &li, 2221676dd7c80b6f91178452535ac45ca58feb23cc42Evan Cheng unsigned PhysReg) const { 2222676dd7c80b6f91178452535ac45ca58feb23cc42Evan Cheng unsigned NumConflicts = 0; 2223676dd7c80b6f91178452535ac45ca58feb23cc42Evan Cheng const LiveInterval &pli = getInterval(getRepresentativeReg(PhysReg)); 2224676dd7c80b6f91178452535ac45ca58feb23cc42Evan Cheng for (MachineRegisterInfo::reg_iterator I = mri_->reg_begin(li.reg), 2225676dd7c80b6f91178452535ac45ca58feb23cc42Evan Cheng E = mri_->reg_end(); I != E; ++I) { 2226676dd7c80b6f91178452535ac45ca58feb23cc42Evan Cheng MachineOperand &O = I.getOperand(); 2227676dd7c80b6f91178452535ac45ca58feb23cc42Evan Cheng MachineInstr *MI = O.getParent(); 2228676dd7c80b6f91178452535ac45ca58feb23cc42Evan Cheng unsigned Index = getInstructionIndex(MI); 2229676dd7c80b6f91178452535ac45ca58feb23cc42Evan Cheng if (pli.liveAt(Index)) 2230676dd7c80b6f91178452535ac45ca58feb23cc42Evan Cheng ++NumConflicts; 2231676dd7c80b6f91178452535ac45ca58feb23cc42Evan Cheng } 2232676dd7c80b6f91178452535ac45ca58feb23cc42Evan Cheng return NumConflicts; 2233676dd7c80b6f91178452535ac45ca58feb23cc42Evan Cheng} 2234676dd7c80b6f91178452535ac45ca58feb23cc42Evan Cheng 2235676dd7c80b6f91178452535ac45ca58feb23cc42Evan Cheng/// spillPhysRegAroundRegDefsUses - Spill the specified physical register 22362824a655509577127d221eecd1425de196f80320Evan Cheng/// around all defs and uses of the specified interval. Return true if it 22372824a655509577127d221eecd1425de196f80320Evan Cheng/// was able to cut its interval. 22382824a655509577127d221eecd1425de196f80320Evan Chengbool LiveIntervals::spillPhysRegAroundRegDefsUses(const LiveInterval &li, 2239676dd7c80b6f91178452535ac45ca58feb23cc42Evan Cheng unsigned PhysReg, VirtRegMap &vrm) { 2240676dd7c80b6f91178452535ac45ca58feb23cc42Evan Cheng unsigned SpillReg = getRepresentativeReg(PhysReg); 2241676dd7c80b6f91178452535ac45ca58feb23cc42Evan Cheng 2242676dd7c80b6f91178452535ac45ca58feb23cc42Evan Cheng for (const unsigned *AS = tri_->getAliasSet(PhysReg); *AS; ++AS) 2243676dd7c80b6f91178452535ac45ca58feb23cc42Evan Cheng // If there are registers which alias PhysReg, but which are not a 2244676dd7c80b6f91178452535ac45ca58feb23cc42Evan Cheng // sub-register of the chosen representative super register. Assert 2245676dd7c80b6f91178452535ac45ca58feb23cc42Evan Cheng // since we can't handle it yet. 224670f2f65aacdbc96fe158b2860b5f0bad075ee548Dan Gohman assert(*AS == SpillReg || !allocatableRegs_[*AS] || !hasInterval(*AS) || 2247676dd7c80b6f91178452535ac45ca58feb23cc42Evan Cheng tri_->isSuperRegister(*AS, SpillReg)); 2248676dd7c80b6f91178452535ac45ca58feb23cc42Evan Cheng 22492824a655509577127d221eecd1425de196f80320Evan Cheng bool Cut = false; 2250676dd7c80b6f91178452535ac45ca58feb23cc42Evan Cheng LiveInterval &pli = getInterval(SpillReg); 2251676dd7c80b6f91178452535ac45ca58feb23cc42Evan Cheng SmallPtrSet<MachineInstr*, 8> SeenMIs; 2252676dd7c80b6f91178452535ac45ca58feb23cc42Evan Cheng for (MachineRegisterInfo::reg_iterator I = mri_->reg_begin(li.reg), 2253676dd7c80b6f91178452535ac45ca58feb23cc42Evan Cheng E = mri_->reg_end(); I != E; ++I) { 2254676dd7c80b6f91178452535ac45ca58feb23cc42Evan Cheng MachineOperand &O = I.getOperand(); 2255676dd7c80b6f91178452535ac45ca58feb23cc42Evan Cheng MachineInstr *MI = O.getParent(); 2256676dd7c80b6f91178452535ac45ca58feb23cc42Evan Cheng if (SeenMIs.count(MI)) 2257676dd7c80b6f91178452535ac45ca58feb23cc42Evan Cheng continue; 2258676dd7c80b6f91178452535ac45ca58feb23cc42Evan Cheng SeenMIs.insert(MI); 2259676dd7c80b6f91178452535ac45ca58feb23cc42Evan Cheng unsigned Index = getInstructionIndex(MI); 2260676dd7c80b6f91178452535ac45ca58feb23cc42Evan Cheng if (pli.liveAt(Index)) { 2261676dd7c80b6f91178452535ac45ca58feb23cc42Evan Cheng vrm.addEmergencySpill(SpillReg, MI); 22625a3c6a87b0173b9d367f7b55e7c99e5110ede057Evan Cheng unsigned StartIdx = getLoadIndex(Index); 22635a3c6a87b0173b9d367f7b55e7c99e5110ede057Evan Cheng unsigned EndIdx = getStoreIndex(Index)+1; 22642824a655509577127d221eecd1425de196f80320Evan Cheng if (pli.isInOneLiveRange(StartIdx, EndIdx)) { 22655a3c6a87b0173b9d367f7b55e7c99e5110ede057Evan Cheng pli.removeRange(StartIdx, EndIdx); 22662824a655509577127d221eecd1425de196f80320Evan Cheng Cut = true; 22672824a655509577127d221eecd1425de196f80320Evan Cheng } else { 22685a3c6a87b0173b9d367f7b55e7c99e5110ede057Evan Cheng cerr << "Ran out of registers during register allocation!\n"; 22695a3c6a87b0173b9d367f7b55e7c99e5110ede057Evan Cheng if (MI->getOpcode() == TargetInstrInfo::INLINEASM) { 22705a3c6a87b0173b9d367f7b55e7c99e5110ede057Evan Cheng cerr << "Please check your inline asm statement for invalid " 22715a3c6a87b0173b9d367f7b55e7c99e5110ede057Evan Cheng << "constraints:\n"; 22725a3c6a87b0173b9d367f7b55e7c99e5110ede057Evan Cheng MI->print(cerr.stream(), tm_); 22735a3c6a87b0173b9d367f7b55e7c99e5110ede057Evan Cheng } 22745a3c6a87b0173b9d367f7b55e7c99e5110ede057Evan Cheng exit(1); 22755a3c6a87b0173b9d367f7b55e7c99e5110ede057Evan Cheng } 2276676dd7c80b6f91178452535ac45ca58feb23cc42Evan Cheng for (const unsigned* AS = tri_->getSubRegisters(SpillReg); *AS; ++AS) { 2277676dd7c80b6f91178452535ac45ca58feb23cc42Evan Cheng if (!hasInterval(*AS)) 2278676dd7c80b6f91178452535ac45ca58feb23cc42Evan Cheng continue; 2279676dd7c80b6f91178452535ac45ca58feb23cc42Evan Cheng LiveInterval &spli = getInterval(*AS); 2280676dd7c80b6f91178452535ac45ca58feb23cc42Evan Cheng if (spli.liveAt(Index)) 2281676dd7c80b6f91178452535ac45ca58feb23cc42Evan Cheng spli.removeRange(getLoadIndex(Index), getStoreIndex(Index)+1); 2282676dd7c80b6f91178452535ac45ca58feb23cc42Evan Cheng } 2283676dd7c80b6f91178452535ac45ca58feb23cc42Evan Cheng } 2284676dd7c80b6f91178452535ac45ca58feb23cc42Evan Cheng } 22852824a655509577127d221eecd1425de196f80320Evan Cheng return Cut; 2286676dd7c80b6f91178452535ac45ca58feb23cc42Evan Cheng} 2287c4dc132c8a787fc41b6a162121251234aa618965Owen Anderson 2288c4dc132c8a787fc41b6a162121251234aa618965Owen AndersonLiveRange LiveIntervals::addLiveRangeToEndOfBlock(unsigned reg, 2289c4dc132c8a787fc41b6a162121251234aa618965Owen Anderson MachineInstr* startInst) { 2290c4dc132c8a787fc41b6a162121251234aa618965Owen Anderson LiveInterval& Interval = getOrCreateInterval(reg); 2291c4dc132c8a787fc41b6a162121251234aa618965Owen Anderson VNInfo* VN = Interval.getNextValue( 2292c4dc132c8a787fc41b6a162121251234aa618965Owen Anderson getInstructionIndex(startInst) + InstrSlots::DEF, 2293857c4e01f85601cf2084adb860616256ee47c177Lang Hames startInst, true, getVNInfoAllocator()); 2294857c4e01f85601cf2084adb860616256ee47c177Lang Hames VN->setHasPHIKill(true); 2295c4dc132c8a787fc41b6a162121251234aa618965Owen Anderson VN->kills.push_back(getMBBEndIdx(startInst->getParent())); 2296c4dc132c8a787fc41b6a162121251234aa618965Owen Anderson LiveRange LR(getInstructionIndex(startInst) + InstrSlots::DEF, 2297c4dc132c8a787fc41b6a162121251234aa618965Owen Anderson getMBBEndIdx(startInst->getParent()) + 1, VN); 2298c4dc132c8a787fc41b6a162121251234aa618965Owen Anderson Interval.addRange(LR); 2299c4dc132c8a787fc41b6a162121251234aa618965Owen Anderson 2300c4dc132c8a787fc41b6a162121251234aa618965Owen Anderson return LR; 2301c4dc132c8a787fc41b6a162121251234aa618965Owen Anderson} 2302