LiveIntervalAnalysis.cpp revision f41538d1b54f55e8900394929b50f7ce3e61125f
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. 202912923925f790427a77781b8a0469fa832c7740dOwen Anderson if (vni->def != ~0U && vni->def != ~1U) { 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. 450c8d044e4f779fdcfc5e7d592927740fd8f672a70Evan Cheng ValNo = interval.getNextValue(defIndex, CopyMI, 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, 542c8d044e4f779fdcfc5e7d592927740fd8f672a70Evan Cheng VNInfoAllocator); 543be4f88a8b8bb3311e0dc4cde8533763d7923c3eaChris Lattner 54491725b75852443923b419fd23215194cfc65dd88Chris Lattner // Value#0 is now defined by the 2-addr instruction. 545c8d044e4f779fdcfc5e7d592927740fd8f672a70Evan Cheng OldValNo->def = RedefIndex; 546c8d044e4f779fdcfc5e7d592927740fd8f672a70Evan Cheng OldValNo->copy = 0; 547fb11288109329cb736d9f49769581a0d0c23fe19Evan Cheng if (MO.isEarlyClobber()) 548fb11288109329cb736d9f49769581a0d0c23fe19Evan Cheng OldValNo->redefByEC = true; 549be4f88a8b8bb3311e0dc4cde8533763d7923c3eaChris Lattner 550be4f88a8b8bb3311e0dc4cde8533763d7923c3eaChris Lattner // Add the new live interval which replaces the range for the input copy. 551be4f88a8b8bb3311e0dc4cde8533763d7923c3eaChris Lattner LiveRange LR(DefIndex, RedefIndex, ValNo); 552bdc679d564e67a81792e463f6614b0088f975025Bill Wendling DOUT << " replace range with " << LR; 5531a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos interval.addRange(LR); 554f3bb2e65d12857f83b273f4ecab013680310bbbcEvan Cheng interval.addKill(ValNo, RedefIndex); 5551a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos 5561a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // If this redefinition is dead, we need to add a dummy unit live 5571a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // range covering the def slot. 5586b098dee286cc6fe5a5a476464d92dec5602e406Owen Anderson if (MO.isDead()) 5597ecb38be0a533e7b9c7d3b8e9b5c8a6fa5f6b349Evan Cheng interval.addRange(LiveRange(RedefIndex, RedefIndex+1, OldValNo)); 5601a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos 56156fdd7af884a35673fb6dd3e01333960922c3ac2Evan Cheng DOUT << " RESULT: "; 5626f0d024a534af18d9e60b3ea757376cd8a3a980eDan Gohman interval.print(DOUT, tri_); 5631a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos 5641a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos } else { 5651a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // Otherwise, this must be because of phi elimination. If this is the 5661a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // first redefinition of the vreg that we have seen, go back and change 5671a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // the live range in the PHI block to be a different value number. 5681a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos if (interval.containsOneValue()) { 5691a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos assert(vi.Kills.size() == 1 && 5701a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos "PHI elimination vreg should have one kill, the PHI itself!"); 5711a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos 5721a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // Remove the old range that we now know has an incorrect number. 573f3bb2e65d12857f83b273f4ecab013680310bbbcEvan Cheng VNInfo *VNI = interval.getValNumInfo(0); 5741a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos MachineInstr *Killer = vi.Kills[0]; 575428b92eb83b457b71d29d1d4b7900d36a0ce9a53Chris Lattner unsigned Start = getMBBStartIdx(Killer->getParent()); 5761a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos unsigned End = getUseIndex(getInstructionIndex(Killer))+1; 57756fdd7af884a35673fb6dd3e01333960922c3ac2Evan Cheng DOUT << " Removing [" << Start << "," << End << "] from: "; 5786f0d024a534af18d9e60b3ea757376cd8a3a980eDan Gohman interval.print(DOUT, tri_); DOUT << "\n"; 5791a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos interval.removeRange(Start, End); 580c3fc7d9ec9b495c8a88cd854247105c296d3aabdEvan Cheng VNI->hasPHIKill = true; 5816f0d024a534af18d9e60b3ea757376cd8a3a980eDan Gohman DOUT << " RESULT: "; interval.print(DOUT, tri_); 5821a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos 583be4f88a8b8bb3311e0dc4cde8533763d7923c3eaChris Lattner // Replace the interval with one of a NEW value number. Note that this 584be4f88a8b8bb3311e0dc4cde8533763d7923c3eaChris Lattner // value number isn't actually defined by an instruction, weird huh? :) 585f3bb2e65d12857f83b273f4ecab013680310bbbcEvan Cheng LiveRange LR(Start, End, interval.getNextValue(~0, 0, VNInfoAllocator)); 586bdc679d564e67a81792e463f6614b0088f975025Bill Wendling DOUT << " replace range with " << LR; 5871a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos interval.addRange(LR); 588f3bb2e65d12857f83b273f4ecab013680310bbbcEvan Cheng interval.addKill(LR.valno, End); 5896f0d024a534af18d9e60b3ea757376cd8a3a980eDan Gohman DOUT << " RESULT: "; interval.print(DOUT, tri_); 5901a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos } 5911a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos 5921a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // In the case of PHI elimination, each variable definition is only 5931a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // live until the end of the block. We've already taken care of the 5941a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // rest of the live range. 5956b128bdc58a496e9f08e4d09416330320761baffChris Lattner unsigned defIndex = getDefIndex(MIIdx); 596fb11288109329cb736d9f49769581a0d0c23fe19Evan Cheng if (MO.isEarlyClobber()) 597fb11288109329cb736d9f49769581a0d0c23fe19Evan Cheng defIndex = getUseIndex(MIIdx); 59891725b75852443923b419fd23215194cfc65dd88Chris Lattner 5997ecb38be0a533e7b9c7d3b8e9b5c8a6fa5f6b349Evan Cheng VNInfo *ValNo; 600c8d044e4f779fdcfc5e7d592927740fd8f672a70Evan Cheng MachineInstr *CopyMI = NULL; 60104ee5a1d9267e5e6fab8f088095fcb83c3c5cbd1Evan Cheng unsigned SrcReg, DstReg, SrcSubReg, DstSubReg; 602c8d044e4f779fdcfc5e7d592927740fd8f672a70Evan Cheng if (mi->getOpcode() == TargetInstrInfo::EXTRACT_SUBREG || 6037e073baedb8232b9519dbe15ea141ff98ccfe6aeEvan Cheng mi->getOpcode() == TargetInstrInfo::INSERT_SUBREG || 60497121ba2afb8d566ff1bf5c4e8fc5d4077940a7fDan Gohman mi->getOpcode() == TargetInstrInfo::SUBREG_TO_REG || 60504ee5a1d9267e5e6fab8f088095fcb83c3c5cbd1Evan Cheng tii_->isMoveInstr(*mi, SrcReg, DstReg, SrcSubReg, DstSubReg)) 606c8d044e4f779fdcfc5e7d592927740fd8f672a70Evan Cheng CopyMI = mi; 607c8d044e4f779fdcfc5e7d592927740fd8f672a70Evan Cheng ValNo = interval.getNextValue(defIndex, CopyMI, VNInfoAllocator); 60891725b75852443923b419fd23215194cfc65dd88Chris Lattner 6097fbad27cfb7298c707e50af10609d463900d7211Owen Anderson unsigned killIndex = getMBBEndIdx(mbb) + 1; 6107ecb38be0a533e7b9c7d3b8e9b5c8a6fa5f6b349Evan Cheng LiveRange LR(defIndex, killIndex, ValNo); 6111a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos interval.addRange(LR); 612c3fc7d9ec9b495c8a88cd854247105c296d3aabdEvan Cheng interval.addKill(ValNo, killIndex); 613c3fc7d9ec9b495c8a88cd854247105c296d3aabdEvan Cheng ValNo->hasPHIKill = true; 614bdc679d564e67a81792e463f6614b0088f975025Bill Wendling DOUT << " +" << LR; 615dd2cc65f34f9b7bfda1cd0c42becedfc361d46f8Alkis Evlogimenos } 6161a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos } 617ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos 618bdc679d564e67a81792e463f6614b0088f975025Bill Wendling DOUT << '\n'; 619ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos} 620ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos 621f35fef7060c465dd7b578bf6339a18e8a8911888Chris Lattnervoid LiveIntervals::handlePhysicalRegisterDef(MachineBasicBlock *MBB, 622ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos MachineBasicBlock::iterator mi, 6236b128bdc58a496e9f08e4d09416330320761baffChris Lattner unsigned MIIdx, 6246b098dee286cc6fe5a5a476464d92dec5602e406Owen Anderson MachineOperand& MO, 62591725b75852443923b419fd23215194cfc65dd88Chris Lattner LiveInterval &interval, 626c8d044e4f779fdcfc5e7d592927740fd8f672a70Evan Cheng MachineInstr *CopyMI) { 6271a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // A physical register cannot be live across basic block, so its 6281a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // lifetime must end somewhere in its defining basic block. 629bdc679d564e67a81792e463f6614b0088f975025Bill Wendling DOUT << "\t\tregister: "; DEBUG(printRegName(interval.reg)); 6301a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos 6316b128bdc58a496e9f08e4d09416330320761baffChris Lattner unsigned baseIndex = MIIdx; 6321a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos unsigned start = getDefIndex(baseIndex); 63386b49f8e2de796cb46c7c8b6a4c4900533fd53f4Dale Johannesen // Earlyclobbers move back one. 63486b49f8e2de796cb46c7c8b6a4c4900533fd53f4Dale Johannesen if (MO.isEarlyClobber()) 63586b49f8e2de796cb46c7c8b6a4c4900533fd53f4Dale Johannesen start = getUseIndex(MIIdx); 6361a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos unsigned end = start; 6371a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos 6381a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // If it is not used after definition, it is considered dead at 6391a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // the instruction defining it. Hence its interval is: 6401a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // [defSlot(def), defSlot(def)+1) 6416b098dee286cc6fe5a5a476464d92dec5602e406Owen Anderson if (MO.isDead()) { 642bdc679d564e67a81792e463f6614b0088f975025Bill Wendling DOUT << " dead"; 64386b49f8e2de796cb46c7c8b6a4c4900533fd53f4Dale Johannesen end = start + 1; 644ab4b66d4c279e8cd9e448687020fc838e7881dbcChris Lattner goto exit; 6451a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos } 646ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos 6471a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // If it is not dead on definition, it must be killed by a 6481a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // subsequent instruction. Hence its interval is: 6491a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // [defSlot(def), useSlot(kill)+1) 6507fbad27cfb7298c707e50af10609d463900d7211Owen Anderson baseIndex += InstrSlots::NUM; 6515ab6f5fe666d0e3403d9b777324d1a1999118153Chris Lattner while (++mi != MBB->end()) { 6527fbad27cfb7298c707e50af10609d463900d7211Owen Anderson while (baseIndex / InstrSlots::NUM < i2miMap_.size() && 6537fbad27cfb7298c707e50af10609d463900d7211Owen Anderson getInstructionFromIndex(baseIndex) == 0) 6547fbad27cfb7298c707e50af10609d463900d7211Owen Anderson baseIndex += InstrSlots::NUM; 6556130f66eaae89f8878590796977678afa8448926Evan Cheng if (mi->killsRegister(interval.reg, tri_)) { 656bdc679d564e67a81792e463f6614b0088f975025Bill Wendling DOUT << " killed"; 657ab4b66d4c279e8cd9e448687020fc838e7881dbcChris Lattner end = getUseIndex(baseIndex) + 1; 658ab4b66d4c279e8cd9e448687020fc838e7881dbcChris Lattner goto exit; 659c45288e06bfe7d0b0e74eff350d280fa6c944373Evan Cheng } else { 660c45288e06bfe7d0b0e74eff350d280fa6c944373Evan Cheng int DefIdx = mi->findRegisterDefOperandIdx(interval.reg, false, tri_); 661c45288e06bfe7d0b0e74eff350d280fa6c944373Evan Cheng if (DefIdx != -1) { 662c45288e06bfe7d0b0e74eff350d280fa6c944373Evan Cheng if (mi->isRegTiedToUseOperand(DefIdx)) { 663c45288e06bfe7d0b0e74eff350d280fa6c944373Evan Cheng // Two-address instruction. 664c45288e06bfe7d0b0e74eff350d280fa6c944373Evan Cheng end = getDefIndex(baseIndex); 665c45288e06bfe7d0b0e74eff350d280fa6c944373Evan Cheng if (mi->getOperand(DefIdx).isEarlyClobber()) 666c45288e06bfe7d0b0e74eff350d280fa6c944373Evan Cheng end = getUseIndex(baseIndex); 667c45288e06bfe7d0b0e74eff350d280fa6c944373Evan Cheng } else { 668c45288e06bfe7d0b0e74eff350d280fa6c944373Evan Cheng // Another instruction redefines the register before it is ever read. 669c45288e06bfe7d0b0e74eff350d280fa6c944373Evan Cheng // Then the register is essentially dead at the instruction that defines 670c45288e06bfe7d0b0e74eff350d280fa6c944373Evan Cheng // it. Hence its interval is: 671c45288e06bfe7d0b0e74eff350d280fa6c944373Evan Cheng // [defSlot(def), defSlot(def)+1) 672c45288e06bfe7d0b0e74eff350d280fa6c944373Evan Cheng DOUT << " dead"; 673c45288e06bfe7d0b0e74eff350d280fa6c944373Evan Cheng end = start + 1; 674c45288e06bfe7d0b0e74eff350d280fa6c944373Evan Cheng } 675c45288e06bfe7d0b0e74eff350d280fa6c944373Evan Cheng goto exit; 676c45288e06bfe7d0b0e74eff350d280fa6c944373Evan Cheng } 677f35fef7060c465dd7b578bf6339a18e8a8911888Chris Lattner } 6787fbad27cfb7298c707e50af10609d463900d7211Owen Anderson 6797fbad27cfb7298c707e50af10609d463900d7211Owen Anderson baseIndex += InstrSlots::NUM; 6801a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos } 6815ab6f5fe666d0e3403d9b777324d1a1999118153Chris Lattner 6825ab6f5fe666d0e3403d9b777324d1a1999118153Chris Lattner // The only case we should have a dead physreg here without a killing or 6835ab6f5fe666d0e3403d9b777324d1a1999118153Chris Lattner // instruction where we know it's dead is if it is live-in to the function 684d521bc983b32da71b85d42dd30da87079afa5728Evan Cheng // and never used. Another possible case is the implicit use of the 685d521bc983b32da71b85d42dd30da87079afa5728Evan Cheng // physical register has been deleted by two-address pass. 68686b49f8e2de796cb46c7c8b6a4c4900533fd53f4Dale Johannesen end = start + 1; 68702ba13c9897ae2b19f9201e57460d7ee2b753a0bAlkis Evlogimenos 688ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenosexit: 6891a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos assert(start < end && "did not find end of interval?"); 690f768bba43f5c036039851d2fcca8212edca18467Chris Lattner 69124a3cc4c83e5edb25fadf7b8979a26b4451795c6Evan Cheng // Already exists? Extend old live interval. 69224a3cc4c83e5edb25fadf7b8979a26b4451795c6Evan Cheng LiveInterval::iterator OldLR = interval.FindLiveRangeContaining(start); 6935379f412bc6ac6171f3bd73930197bfce88c2faaEvan Cheng bool Extend = OldLR != interval.end(); 6945379f412bc6ac6171f3bd73930197bfce88c2faaEvan Cheng VNInfo *ValNo = Extend 695c8d044e4f779fdcfc5e7d592927740fd8f672a70Evan Cheng ? OldLR->valno : interval.getNextValue(start, CopyMI, VNInfoAllocator); 6965379f412bc6ac6171f3bd73930197bfce88c2faaEvan Cheng if (MO.isEarlyClobber() && Extend) 6975379f412bc6ac6171f3bd73930197bfce88c2faaEvan Cheng ValNo->redefByEC = true; 6987ecb38be0a533e7b9c7d3b8e9b5c8a6fa5f6b349Evan Cheng LiveRange LR(start, end, ValNo); 6991a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos interval.addRange(LR); 700f3bb2e65d12857f83b273f4ecab013680310bbbcEvan Cheng interval.addKill(LR.valno, end); 701bdc679d564e67a81792e463f6614b0088f975025Bill Wendling DOUT << " +" << LR << '\n'; 702ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos} 703ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos 704f35fef7060c465dd7b578bf6339a18e8a8911888Chris Lattnervoid LiveIntervals::handleRegisterDef(MachineBasicBlock *MBB, 705f35fef7060c465dd7b578bf6339a18e8a8911888Chris Lattner MachineBasicBlock::iterator MI, 7066b128bdc58a496e9f08e4d09416330320761baffChris Lattner unsigned MIIdx, 707ef0732d25a9882c947984ae3f2afbef5463ba00fEvan Cheng MachineOperand& MO, 708ef0732d25a9882c947984ae3f2afbef5463ba00fEvan Cheng unsigned MOIdx) { 7096b098dee286cc6fe5a5a476464d92dec5602e406Owen Anderson if (TargetRegisterInfo::isVirtualRegister(MO.getReg())) 710ef0732d25a9882c947984ae3f2afbef5463ba00fEvan Cheng handleVirtualRegisterDef(MBB, MI, MIIdx, MO, MOIdx, 7116b098dee286cc6fe5a5a476464d92dec5602e406Owen Anderson getOrCreateInterval(MO.getReg())); 7126b098dee286cc6fe5a5a476464d92dec5602e406Owen Anderson else if (allocatableRegs_[MO.getReg()]) { 713c8d044e4f779fdcfc5e7d592927740fd8f672a70Evan Cheng MachineInstr *CopyMI = NULL; 71404ee5a1d9267e5e6fab8f088095fcb83c3c5cbd1Evan Cheng unsigned SrcReg, DstReg, SrcSubReg, DstSubReg; 715c8d044e4f779fdcfc5e7d592927740fd8f672a70Evan Cheng if (MI->getOpcode() == TargetInstrInfo::EXTRACT_SUBREG || 7167e073baedb8232b9519dbe15ea141ff98ccfe6aeEvan Cheng MI->getOpcode() == TargetInstrInfo::INSERT_SUBREG || 71797121ba2afb8d566ff1bf5c4e8fc5d4077940a7fDan Gohman MI->getOpcode() == TargetInstrInfo::SUBREG_TO_REG || 71804ee5a1d9267e5e6fab8f088095fcb83c3c5cbd1Evan Cheng tii_->isMoveInstr(*MI, SrcReg, DstReg, SrcSubReg, DstSubReg)) 719c8d044e4f779fdcfc5e7d592927740fd8f672a70Evan Cheng CopyMI = MI; 720c45288e06bfe7d0b0e74eff350d280fa6c944373Evan Cheng handlePhysicalRegisterDef(MBB, MI, MIIdx, MO, 7216b098dee286cc6fe5a5a476464d92dec5602e406Owen Anderson getOrCreateInterval(MO.getReg()), CopyMI); 72224a3cc4c83e5edb25fadf7b8979a26b4451795c6Evan Cheng // Def of a register also defines its sub-registers. 7236b098dee286cc6fe5a5a476464d92dec5602e406Owen Anderson for (const unsigned* AS = tri_->getSubRegisters(MO.getReg()); *AS; ++AS) 7246130f66eaae89f8878590796977678afa8448926Evan Cheng // If MI also modifies the sub-register explicitly, avoid processing it 7256130f66eaae89f8878590796977678afa8448926Evan Cheng // more than once. Do not pass in TRI here so it checks for exact match. 7266130f66eaae89f8878590796977678afa8448926Evan Cheng if (!MI->modifiesRegister(*AS)) 727c45288e06bfe7d0b0e74eff350d280fa6c944373Evan Cheng handlePhysicalRegisterDef(MBB, MI, MIIdx, MO, 7286b098dee286cc6fe5a5a476464d92dec5602e406Owen Anderson getOrCreateInterval(*AS), 0); 729f35fef7060c465dd7b578bf6339a18e8a8911888Chris Lattner } 7304d46e1e521c0df1990ea50f8146d22bd77ea71a6Alkis Evlogimenos} 7314d46e1e521c0df1990ea50f8146d22bd77ea71a6Alkis Evlogimenos 732b371f457b0ea4a652a9f526ba4375c80ae542252Evan Chengvoid LiveIntervals::handleLiveInRegister(MachineBasicBlock *MBB, 7339b25b8ca24d6df2e097741dcc15016772ee4eda7Jim Laskey unsigned MIIdx, 73424a3cc4c83e5edb25fadf7b8979a26b4451795c6Evan Cheng LiveInterval &interval, bool isAlias) { 735b371f457b0ea4a652a9f526ba4375c80ae542252Evan Cheng DOUT << "\t\tlivein register: "; DEBUG(printRegName(interval.reg)); 736b371f457b0ea4a652a9f526ba4375c80ae542252Evan Cheng 737b371f457b0ea4a652a9f526ba4375c80ae542252Evan Cheng // Look for kills, if it reaches a def before it's killed, then it shouldn't 738b371f457b0ea4a652a9f526ba4375c80ae542252Evan Cheng // be considered a livein. 739b371f457b0ea4a652a9f526ba4375c80ae542252Evan Cheng MachineBasicBlock::iterator mi = MBB->begin(); 7409b25b8ca24d6df2e097741dcc15016772ee4eda7Jim Laskey unsigned baseIndex = MIIdx; 7419b25b8ca24d6df2e097741dcc15016772ee4eda7Jim Laskey unsigned start = baseIndex; 74299500aeb7c9a05db57e228544a3f81de2faf24efOwen Anderson while (baseIndex / InstrSlots::NUM < i2miMap_.size() && 74399500aeb7c9a05db57e228544a3f81de2faf24efOwen Anderson getInstructionFromIndex(baseIndex) == 0) 74499500aeb7c9a05db57e228544a3f81de2faf24efOwen Anderson baseIndex += InstrSlots::NUM; 74599500aeb7c9a05db57e228544a3f81de2faf24efOwen Anderson unsigned end = baseIndex; 7460076c616e8abc2ecf36600a7ac20ec784420cdc4Evan Cheng bool SeenDefUse = false; 74799500aeb7c9a05db57e228544a3f81de2faf24efOwen Anderson 748b371f457b0ea4a652a9f526ba4375c80ae542252Evan Cheng while (mi != MBB->end()) { 7496130f66eaae89f8878590796977678afa8448926Evan Cheng if (mi->killsRegister(interval.reg, tri_)) { 750b371f457b0ea4a652a9f526ba4375c80ae542252Evan Cheng DOUT << " killed"; 751b371f457b0ea4a652a9f526ba4375c80ae542252Evan Cheng end = getUseIndex(baseIndex) + 1; 7520076c616e8abc2ecf36600a7ac20ec784420cdc4Evan Cheng SeenDefUse = true; 753b371f457b0ea4a652a9f526ba4375c80ae542252Evan Cheng goto exit; 7546130f66eaae89f8878590796977678afa8448926Evan Cheng } else if (mi->modifiesRegister(interval.reg, tri_)) { 755b371f457b0ea4a652a9f526ba4375c80ae542252Evan Cheng // Another instruction redefines the register before it is ever read. 756b371f457b0ea4a652a9f526ba4375c80ae542252Evan Cheng // Then the register is essentially dead at the instruction that defines 757b371f457b0ea4a652a9f526ba4375c80ae542252Evan Cheng // it. Hence its interval is: 758b371f457b0ea4a652a9f526ba4375c80ae542252Evan Cheng // [defSlot(def), defSlot(def)+1) 759b371f457b0ea4a652a9f526ba4375c80ae542252Evan Cheng DOUT << " dead"; 760b371f457b0ea4a652a9f526ba4375c80ae542252Evan Cheng end = getDefIndex(start) + 1; 7610076c616e8abc2ecf36600a7ac20ec784420cdc4Evan Cheng SeenDefUse = true; 762b371f457b0ea4a652a9f526ba4375c80ae542252Evan Cheng goto exit; 763b371f457b0ea4a652a9f526ba4375c80ae542252Evan Cheng } 764b371f457b0ea4a652a9f526ba4375c80ae542252Evan Cheng 765b371f457b0ea4a652a9f526ba4375c80ae542252Evan Cheng baseIndex += InstrSlots::NUM; 766b371f457b0ea4a652a9f526ba4375c80ae542252Evan Cheng ++mi; 7670076c616e8abc2ecf36600a7ac20ec784420cdc4Evan Cheng if (mi != MBB->end()) { 7680076c616e8abc2ecf36600a7ac20ec784420cdc4Evan Cheng while (baseIndex / InstrSlots::NUM < i2miMap_.size() && 7690076c616e8abc2ecf36600a7ac20ec784420cdc4Evan Cheng getInstructionFromIndex(baseIndex) == 0) 7700076c616e8abc2ecf36600a7ac20ec784420cdc4Evan Cheng baseIndex += InstrSlots::NUM; 7710076c616e8abc2ecf36600a7ac20ec784420cdc4Evan Cheng } 772b371f457b0ea4a652a9f526ba4375c80ae542252Evan Cheng } 773b371f457b0ea4a652a9f526ba4375c80ae542252Evan Cheng 774b371f457b0ea4a652a9f526ba4375c80ae542252Evan Chengexit: 77575611fb4e6ab253be30ac29a2b15e9bf8c1d146eEvan Cheng // Live-in register might not be used at all. 7760076c616e8abc2ecf36600a7ac20ec784420cdc4Evan Cheng if (!SeenDefUse) { 777292da949f6c87d6499425d64d37d7c5870ec57adEvan Cheng if (isAlias) { 778292da949f6c87d6499425d64d37d7c5870ec57adEvan Cheng DOUT << " dead"; 77975611fb4e6ab253be30ac29a2b15e9bf8c1d146eEvan Cheng end = getDefIndex(MIIdx) + 1; 780292da949f6c87d6499425d64d37d7c5870ec57adEvan Cheng } else { 781292da949f6c87d6499425d64d37d7c5870ec57adEvan Cheng DOUT << " live through"; 782292da949f6c87d6499425d64d37d7c5870ec57adEvan Cheng end = baseIndex; 783292da949f6c87d6499425d64d37d7c5870ec57adEvan Cheng } 78424a3cc4c83e5edb25fadf7b8979a26b4451795c6Evan Cheng } 78524a3cc4c83e5edb25fadf7b8979a26b4451795c6Evan Cheng 78699500aeb7c9a05db57e228544a3f81de2faf24efOwen Anderson LiveRange LR(start, end, interval.getNextValue(~0U, 0, VNInfoAllocator)); 7879b25b8ca24d6df2e097741dcc15016772ee4eda7Jim Laskey interval.addRange(LR); 788f3bb2e65d12857f83b273f4ecab013680310bbbcEvan Cheng interval.addKill(LR.valno, end); 78924c2e5cf7e926452ea5875d027ec0d24d9c19e39Evan Cheng DOUT << " +" << LR << '\n'; 790b371f457b0ea4a652a9f526ba4375c80ae542252Evan Cheng} 791b371f457b0ea4a652a9f526ba4375c80ae542252Evan Cheng 792ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos/// computeIntervals - computes the live intervals for virtual 7934d46e1e521c0df1990ea50f8146d22bd77ea71a6Alkis Evlogimenos/// registers. for some ordering of the machine instructions [1,N] a 79408cec00588ec1a8fa85b208555f006d7396ae7a4Alkis Evlogimenos/// live interval is an interval [i, j) where 1 <= i <= j < N for 795ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos/// which a variable is live 79691aac1015e6714d959801dd8d60f55a72827dc4dDale Johannesenvoid LiveIntervals::computeIntervals() { 79791aac1015e6714d959801dd8d60f55a72827dc4dDale Johannesen 798bdc679d564e67a81792e463f6614b0088f975025Bill Wendling DOUT << "********** COMPUTING LIVE INTERVALS **********\n" 799bdc679d564e67a81792e463f6614b0088f975025Bill Wendling << "********** Function: " 800bdc679d564e67a81792e463f6614b0088f975025Bill Wendling << ((Value*)mf_->getFunction())->getName() << '\n'; 8017fbad27cfb7298c707e50af10609d463900d7211Owen Anderson 802428b92eb83b457b71d29d1d4b7900d36a0ce9a53Chris Lattner for (MachineFunction::iterator MBBI = mf_->begin(), E = mf_->end(); 803428b92eb83b457b71d29d1d4b7900d36a0ce9a53Chris Lattner MBBI != E; ++MBBI) { 804428b92eb83b457b71d29d1d4b7900d36a0ce9a53Chris Lattner MachineBasicBlock *MBB = MBBI; 805134eb73fc35e6ead3cfd3ed5024d0d7efa507441Owen Anderson // Track the index of the current machine instr. 806134eb73fc35e6ead3cfd3ed5024d0d7efa507441Owen Anderson unsigned MIIndex = getMBBStartIdx(MBB); 807bdc679d564e67a81792e463f6614b0088f975025Bill Wendling DOUT << ((Value*)MBB->getBasicBlock())->getName() << ":\n"; 8081a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos 809428b92eb83b457b71d29d1d4b7900d36a0ce9a53Chris Lattner MachineBasicBlock::iterator MI = MBB->begin(), miEnd = MBB->end(); 8100c9f92e1ff64ee56724eae444a0442b02f83d0a8Evan Cheng 811cb406c25973b4e88a6c10ad839ef1beeb3664715Dan Gohman // Create intervals for live-ins to this BB first. 812cb406c25973b4e88a6c10ad839ef1beeb3664715Dan Gohman for (MachineBasicBlock::const_livein_iterator LI = MBB->livein_begin(), 813cb406c25973b4e88a6c10ad839ef1beeb3664715Dan Gohman LE = MBB->livein_end(); LI != LE; ++LI) { 814cb406c25973b4e88a6c10ad839ef1beeb3664715Dan Gohman handleLiveInRegister(MBB, MIIndex, getOrCreateInterval(*LI)); 815cb406c25973b4e88a6c10ad839ef1beeb3664715Dan Gohman // Multiple live-ins can alias the same register. 8166f0d024a534af18d9e60b3ea757376cd8a3a980eDan Gohman for (const unsigned* AS = tri_->getSubRegisters(*LI); *AS; ++AS) 817cb406c25973b4e88a6c10ad839ef1beeb3664715Dan Gohman if (!hasInterval(*AS)) 818cb406c25973b4e88a6c10ad839ef1beeb3664715Dan Gohman handleLiveInRegister(MBB, MIIndex, getOrCreateInterval(*AS), 819cb406c25973b4e88a6c10ad839ef1beeb3664715Dan Gohman true); 820dffb2e83ed2546226d09c40aa43524e2392322daChris Lattner } 821dffb2e83ed2546226d09c40aa43524e2392322daChris Lattner 82299500aeb7c9a05db57e228544a3f81de2faf24efOwen Anderson // Skip over empty initial indices. 82399500aeb7c9a05db57e228544a3f81de2faf24efOwen Anderson while (MIIndex / InstrSlots::NUM < i2miMap_.size() && 82499500aeb7c9a05db57e228544a3f81de2faf24efOwen Anderson getInstructionFromIndex(MIIndex) == 0) 82599500aeb7c9a05db57e228544a3f81de2faf24efOwen Anderson MIIndex += InstrSlots::NUM; 82699500aeb7c9a05db57e228544a3f81de2faf24efOwen Anderson 827428b92eb83b457b71d29d1d4b7900d36a0ce9a53Chris Lattner for (; MI != miEnd; ++MI) { 828bdc679d564e67a81792e463f6614b0088f975025Bill Wendling DOUT << MIIndex << "\t" << *MI; 8291a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos 830438f7bc67cf235ccee7e6f7ac7f4ae2186eb8020Evan Cheng // Handle defs. 831428b92eb83b457b71d29d1d4b7900d36a0ce9a53Chris Lattner for (int i = MI->getNumOperands() - 1; i >= 0; --i) { 832428b92eb83b457b71d29d1d4b7900d36a0ce9a53Chris Lattner MachineOperand &MO = MI->getOperand(i); 8331a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // handle register defs - build intervals 834d735b8019b0f297d7c14b55adcd887af24d8e602Dan Gohman if (MO.isReg() && MO.getReg() && MO.isDef()) { 835ef0732d25a9882c947984ae3f2afbef5463ba00fEvan Cheng handleRegisterDef(MBB, MI, MIIndex, MO, i); 83691aac1015e6714d959801dd8d60f55a72827dc4dDale Johannesen } 8371a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos } 83899fe34b9b2bb8786da6c7f6134ae17d4c2cd8bf7Evan Cheng 83999fe34b9b2bb8786da6c7f6134ae17d4c2cd8bf7Evan Cheng // Skip over the empty slots after each instruction. 84099fe34b9b2bb8786da6c7f6134ae17d4c2cd8bf7Evan Cheng unsigned Slots = MI->getDesc().getNumDefs(); 84199fe34b9b2bb8786da6c7f6134ae17d4c2cd8bf7Evan Cheng if (Slots == 0) 84299fe34b9b2bb8786da6c7f6134ae17d4c2cd8bf7Evan Cheng Slots = 1; 84399fe34b9b2bb8786da6c7f6134ae17d4c2cd8bf7Evan Cheng MIIndex += InstrSlots::NUM * Slots; 8447fbad27cfb7298c707e50af10609d463900d7211Owen Anderson 8457fbad27cfb7298c707e50af10609d463900d7211Owen Anderson // Skip over empty indices. 8467fbad27cfb7298c707e50af10609d463900d7211Owen Anderson while (MIIndex / InstrSlots::NUM < i2miMap_.size() && 8477fbad27cfb7298c707e50af10609d463900d7211Owen Anderson getInstructionFromIndex(MIIndex) == 0) 8487fbad27cfb7298c707e50af10609d463900d7211Owen Anderson MIIndex += InstrSlots::NUM; 849ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos } 8501a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos } 851ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos} 852b27ef248f579b354aab434f63c417ab1103e47e2Alkis Evlogimenos 853d0e32c5d5c1bb03bc0cc8aeef52728724cab1c51Evan Chengbool LiveIntervals::findLiveInMBBs(unsigned Start, unsigned End, 854a5bfc97da713ec9e185226d44e6adb4d3087b304Evan Cheng SmallVectorImpl<MachineBasicBlock*> &MBBs) const { 8554ca980e7f9ce7b78955307c2d07001a24d3b6befEvan Cheng std::vector<IdxMBBPair>::const_iterator I = 856d0e32c5d5c1bb03bc0cc8aeef52728724cab1c51Evan Cheng std::lower_bound(Idx2MBBMap.begin(), Idx2MBBMap.end(), Start); 8574ca980e7f9ce7b78955307c2d07001a24d3b6befEvan Cheng 8584ca980e7f9ce7b78955307c2d07001a24d3b6befEvan Cheng bool ResVal = false; 8594ca980e7f9ce7b78955307c2d07001a24d3b6befEvan Cheng while (I != Idx2MBBMap.end()) { 8602ad8245566a3c92d4559727a877d57ecf5d078c8Dan Gohman if (I->first >= End) 8614ca980e7f9ce7b78955307c2d07001a24d3b6befEvan Cheng break; 8624ca980e7f9ce7b78955307c2d07001a24d3b6befEvan Cheng MBBs.push_back(I->second); 8634ca980e7f9ce7b78955307c2d07001a24d3b6befEvan Cheng ResVal = true; 8644ca980e7f9ce7b78955307c2d07001a24d3b6befEvan Cheng ++I; 8654ca980e7f9ce7b78955307c2d07001a24d3b6befEvan Cheng } 8664ca980e7f9ce7b78955307c2d07001a24d3b6befEvan Cheng return ResVal; 8674ca980e7f9ce7b78955307c2d07001a24d3b6befEvan Cheng} 8684ca980e7f9ce7b78955307c2d07001a24d3b6befEvan Cheng 869d0e32c5d5c1bb03bc0cc8aeef52728724cab1c51Evan Chengbool LiveIntervals::findReachableMBBs(unsigned Start, unsigned End, 870d0e32c5d5c1bb03bc0cc8aeef52728724cab1c51Evan Cheng SmallVectorImpl<MachineBasicBlock*> &MBBs) const { 871d0e32c5d5c1bb03bc0cc8aeef52728724cab1c51Evan Cheng std::vector<IdxMBBPair>::const_iterator I = 872d0e32c5d5c1bb03bc0cc8aeef52728724cab1c51Evan Cheng std::lower_bound(Idx2MBBMap.begin(), Idx2MBBMap.end(), Start); 873d0e32c5d5c1bb03bc0cc8aeef52728724cab1c51Evan Cheng 874d0e32c5d5c1bb03bc0cc8aeef52728724cab1c51Evan Cheng bool ResVal = false; 875d0e32c5d5c1bb03bc0cc8aeef52728724cab1c51Evan Cheng while (I != Idx2MBBMap.end()) { 876d0e32c5d5c1bb03bc0cc8aeef52728724cab1c51Evan Cheng if (I->first > End) 877d0e32c5d5c1bb03bc0cc8aeef52728724cab1c51Evan Cheng break; 878d0e32c5d5c1bb03bc0cc8aeef52728724cab1c51Evan Cheng MachineBasicBlock *MBB = I->second; 879d0e32c5d5c1bb03bc0cc8aeef52728724cab1c51Evan Cheng if (getMBBEndIdx(MBB) > End) 880d0e32c5d5c1bb03bc0cc8aeef52728724cab1c51Evan Cheng break; 881d0e32c5d5c1bb03bc0cc8aeef52728724cab1c51Evan Cheng for (MachineBasicBlock::succ_iterator SI = MBB->succ_begin(), 882d0e32c5d5c1bb03bc0cc8aeef52728724cab1c51Evan Cheng SE = MBB->succ_end(); SI != SE; ++SI) 883d0e32c5d5c1bb03bc0cc8aeef52728724cab1c51Evan Cheng MBBs.push_back(*SI); 884d0e32c5d5c1bb03bc0cc8aeef52728724cab1c51Evan Cheng ResVal = true; 885d0e32c5d5c1bb03bc0cc8aeef52728724cab1c51Evan Cheng ++I; 886d0e32c5d5c1bb03bc0cc8aeef52728724cab1c51Evan Cheng } 887d0e32c5d5c1bb03bc0cc8aeef52728724cab1c51Evan Cheng return ResVal; 888d0e32c5d5c1bb03bc0cc8aeef52728724cab1c51Evan Cheng} 889d0e32c5d5c1bb03bc0cc8aeef52728724cab1c51Evan Cheng 89003857b29d8271a23943254579e6cf7b7df4b1bd3Owen AndersonLiveInterval* LiveIntervals::createInterval(unsigned reg) { 8910a1fcce09230e9b4bd30a8f07447aa075dce7470Evan Cheng float Weight = TargetRegisterInfo::isPhysicalRegister(reg) ? HUGE_VALF : 0.0F; 89203857b29d8271a23943254579e6cf7b7df4b1bd3Owen Anderson return new LiveInterval(reg, Weight); 8939a8b490735d216435862a3d52e669357f165550fAlkis Evlogimenos} 894f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng 8950a1fcce09230e9b4bd30a8f07447aa075dce7470Evan Cheng/// dupInterval - Duplicate a live interval. The caller is responsible for 8960a1fcce09230e9b4bd30a8f07447aa075dce7470Evan Cheng/// managing the allocated memory. 8970a1fcce09230e9b4bd30a8f07447aa075dce7470Evan ChengLiveInterval* LiveIntervals::dupInterval(LiveInterval *li) { 8980a1fcce09230e9b4bd30a8f07447aa075dce7470Evan Cheng LiveInterval *NewLI = createInterval(li->reg); 8990a1fcce09230e9b4bd30a8f07447aa075dce7470Evan Cheng NewLI->Copy(*li, getVNInfoAllocator()); 9000a1fcce09230e9b4bd30a8f07447aa075dce7470Evan Cheng return NewLI; 9010a1fcce09230e9b4bd30a8f07447aa075dce7470Evan Cheng} 9020a1fcce09230e9b4bd30a8f07447aa075dce7470Evan Cheng 903c8d044e4f779fdcfc5e7d592927740fd8f672a70Evan Cheng/// getVNInfoSourceReg - Helper function that parses the specified VNInfo 904c8d044e4f779fdcfc5e7d592927740fd8f672a70Evan Cheng/// copy field and returns the source register that defines it. 905c8d044e4f779fdcfc5e7d592927740fd8f672a70Evan Chengunsigned LiveIntervals::getVNInfoSourceReg(const VNInfo *VNI) const { 906c8d044e4f779fdcfc5e7d592927740fd8f672a70Evan Cheng if (!VNI->copy) 907c8d044e4f779fdcfc5e7d592927740fd8f672a70Evan Cheng return 0; 908c8d044e4f779fdcfc5e7d592927740fd8f672a70Evan Cheng 9098f90b6eb2fd0125f5b779de80954944f9071fb87Evan Cheng if (VNI->copy->getOpcode() == TargetInstrInfo::EXTRACT_SUBREG) { 9108f90b6eb2fd0125f5b779de80954944f9071fb87Evan Cheng // If it's extracting out of a physical register, return the sub-register. 9118f90b6eb2fd0125f5b779de80954944f9071fb87Evan Cheng unsigned Reg = VNI->copy->getOperand(1).getReg(); 9128f90b6eb2fd0125f5b779de80954944f9071fb87Evan Cheng if (TargetRegisterInfo::isPhysicalRegister(Reg)) 9138f90b6eb2fd0125f5b779de80954944f9071fb87Evan Cheng Reg = tri_->getSubReg(Reg, VNI->copy->getOperand(2).getImm()); 9148f90b6eb2fd0125f5b779de80954944f9071fb87Evan Cheng return Reg; 91597121ba2afb8d566ff1bf5c4e8fc5d4077940a7fDan Gohman } else if (VNI->copy->getOpcode() == TargetInstrInfo::INSERT_SUBREG || 91697121ba2afb8d566ff1bf5c4e8fc5d4077940a7fDan Gohman VNI->copy->getOpcode() == TargetInstrInfo::SUBREG_TO_REG) 9177e073baedb8232b9519dbe15ea141ff98ccfe6aeEvan Cheng return VNI->copy->getOperand(2).getReg(); 9188f90b6eb2fd0125f5b779de80954944f9071fb87Evan Cheng 91904ee5a1d9267e5e6fab8f088095fcb83c3c5cbd1Evan Cheng unsigned SrcReg, DstReg, SrcSubReg, DstSubReg; 92004ee5a1d9267e5e6fab8f088095fcb83c3c5cbd1Evan Cheng if (tii_->isMoveInstr(*VNI->copy, SrcReg, DstReg, SrcSubReg, DstSubReg)) 921c8d044e4f779fdcfc5e7d592927740fd8f672a70Evan Cheng return SrcReg; 922c8d044e4f779fdcfc5e7d592927740fd8f672a70Evan Cheng assert(0 && "Unrecognized copy instruction!"); 923c8d044e4f779fdcfc5e7d592927740fd8f672a70Evan Cheng return 0; 924c8d044e4f779fdcfc5e7d592927740fd8f672a70Evan Cheng} 925f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng 926f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng//===----------------------------------------------------------------------===// 927f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng// Register allocator hooks. 928f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng// 929f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng 930d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng/// getReMatImplicitUse - If the remat definition MI has one (for now, we only 931d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng/// allow one) virtual register operand, then its uses are implicitly using 932d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng/// the register. Returns the virtual register. 933d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Chengunsigned LiveIntervals::getReMatImplicitUse(const LiveInterval &li, 934d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng MachineInstr *MI) const { 935d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng unsigned RegOp = 0; 936d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) { 937d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng MachineOperand &MO = MI->getOperand(i); 938d735b8019b0f297d7c14b55adcd887af24d8e602Dan Gohman if (!MO.isReg() || !MO.isUse()) 939d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng continue; 940d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng unsigned Reg = MO.getReg(); 941d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng if (Reg == 0 || Reg == li.reg) 942d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng continue; 943d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng // FIXME: For now, only remat MI with at most one register operand. 944d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng assert(!RegOp && 945d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng "Can't rematerialize instruction with multiple register operand!"); 946d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng RegOp = MO.getReg(); 9476d69ba8a6901c69d78488cbc41f8dbf080618fdeDan Gohman#ifndef NDEBUG 948d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng break; 9496d69ba8a6901c69d78488cbc41f8dbf080618fdeDan Gohman#endif 950d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng } 951d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng return RegOp; 952d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng} 953d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng 954d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng/// isValNoAvailableAt - Return true if the val# of the specified interval 955d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng/// which reaches the given instruction also reaches the specified use index. 956d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Chengbool LiveIntervals::isValNoAvailableAt(const LiveInterval &li, MachineInstr *MI, 957d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng unsigned UseIdx) const { 958d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng unsigned Index = getInstructionIndex(MI); 959d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng VNInfo *ValNo = li.FindLiveRangeContaining(Index)->valno; 960d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng LiveInterval::const_iterator UI = li.FindLiveRangeContaining(UseIdx); 961d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng return UI != li.end() && UI->valno == ValNo; 962d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng} 963d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng 964f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng/// isReMaterializable - Returns true if the definition MI of the specified 965f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng/// val# of the specified interval is re-materializable. 966f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Chengbool LiveIntervals::isReMaterializable(const LiveInterval &li, 9675ef3a04b542c4e585276768fa9ca2af698ef5c87Evan Cheng const VNInfo *ValNo, MachineInstr *MI, 968dc37786595beedd0a68d8e2cbd91ae53ad58d133Evan Cheng SmallVectorImpl<LiveInterval*> &SpillIs, 9695ef3a04b542c4e585276768fa9ca2af698ef5c87Evan Cheng bool &isLoad) { 970f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng if (DisableReMat) 971f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng return false; 972f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng 97320ccded7dec5b90e58f649f4fb95b166a642b8cbEvan Cheng if (MI->getOpcode() == TargetInstrInfo::IMPLICIT_DEF) 974d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng return true; 975dd3465eed17cdf226bdb465e604dfa851d36029dEvan Cheng 976dd3465eed17cdf226bdb465e604dfa851d36029dEvan Cheng int FrameIdx = 0; 977dd3465eed17cdf226bdb465e604dfa851d36029dEvan Cheng if (tii_->isLoadFromStackSlot(MI, FrameIdx) && 978249ded3fa8884f91fded869fb6e251b8aebb0376Evan Cheng mf_->getFrameInfo()->isImmutableObjectIndex(FrameIdx)) 97979a0c1e46c4f7d8a2a06f4ef3e2c54d883c7fe25Evan Cheng // FIXME: Let target specific isReallyTriviallyReMaterializable determines 98079a0c1e46c4f7d8a2a06f4ef3e2c54d883c7fe25Evan Cheng // this but remember this is not safe to fold into a two-address 98179a0c1e46c4f7d8a2a06f4ef3e2c54d883c7fe25Evan Cheng // instruction. 982249ded3fa8884f91fded869fb6e251b8aebb0376Evan Cheng // This is a load from fixed stack slot. It can be rematerialized. 983dd3465eed17cdf226bdb465e604dfa851d36029dEvan Cheng return true; 984dd3465eed17cdf226bdb465e604dfa851d36029dEvan Cheng 9856d69ba8a6901c69d78488cbc41f8dbf080618fdeDan Gohman // If the target-specific rules don't identify an instruction as 9866d69ba8a6901c69d78488cbc41f8dbf080618fdeDan Gohman // being trivially rematerializable, use some target-independent 9876d69ba8a6901c69d78488cbc41f8dbf080618fdeDan Gohman // rules. 9886d69ba8a6901c69d78488cbc41f8dbf080618fdeDan Gohman if (!MI->getDesc().isRematerializable() || 9896d69ba8a6901c69d78488cbc41f8dbf080618fdeDan Gohman !tii_->isTriviallyReMaterializable(MI)) { 9904c8f87038ddc0fbcce751f0e2e7c0e564abca096Dan Gohman if (!EnableAggressiveRemat) 9914c8f87038ddc0fbcce751f0e2e7c0e564abca096Dan Gohman return false; 9926d69ba8a6901c69d78488cbc41f8dbf080618fdeDan Gohman 9930471a79f2000eb1eb4458e7b3dcd254172fae739Dan Gohman // If the instruction accesses memory but the memoperands have been lost, 9946d69ba8a6901c69d78488cbc41f8dbf080618fdeDan Gohman // we can't analyze it. 99520ccded7dec5b90e58f649f4fb95b166a642b8cbEvan Cheng const TargetInstrDesc &TID = MI->getDesc(); 9966d69ba8a6901c69d78488cbc41f8dbf080618fdeDan Gohman if ((TID.mayLoad() || TID.mayStore()) && MI->memoperands_empty()) 9976d69ba8a6901c69d78488cbc41f8dbf080618fdeDan Gohman return false; 9986d69ba8a6901c69d78488cbc41f8dbf080618fdeDan Gohman 9996d69ba8a6901c69d78488cbc41f8dbf080618fdeDan Gohman // Avoid instructions obviously unsafe for remat. 10006d69ba8a6901c69d78488cbc41f8dbf080618fdeDan Gohman if (TID.hasUnmodeledSideEffects() || TID.isNotDuplicable()) 10016d69ba8a6901c69d78488cbc41f8dbf080618fdeDan Gohman return false; 10026d69ba8a6901c69d78488cbc41f8dbf080618fdeDan Gohman 10036d69ba8a6901c69d78488cbc41f8dbf080618fdeDan Gohman // If the instruction accesses memory and the memory could be non-constant, 10046d69ba8a6901c69d78488cbc41f8dbf080618fdeDan Gohman // assume the instruction is not rematerializable. 1005dc37786595beedd0a68d8e2cbd91ae53ad58d133Evan Cheng for (std::list<MachineMemOperand>::const_iterator 1006dc37786595beedd0a68d8e2cbd91ae53ad58d133Evan Cheng I = MI->memoperands_begin(), E = MI->memoperands_end(); I != E; ++I){ 10076d69ba8a6901c69d78488cbc41f8dbf080618fdeDan Gohman const MachineMemOperand &MMO = *I; 10086d69ba8a6901c69d78488cbc41f8dbf080618fdeDan Gohman if (MMO.isVolatile() || MMO.isStore()) 10096d69ba8a6901c69d78488cbc41f8dbf080618fdeDan Gohman return false; 10106d69ba8a6901c69d78488cbc41f8dbf080618fdeDan Gohman const Value *V = MMO.getValue(); 10116d69ba8a6901c69d78488cbc41f8dbf080618fdeDan Gohman if (!V) 10126d69ba8a6901c69d78488cbc41f8dbf080618fdeDan Gohman return false; 10136d69ba8a6901c69d78488cbc41f8dbf080618fdeDan Gohman if (const PseudoSourceValue *PSV = dyn_cast<PseudoSourceValue>(V)) { 10146d69ba8a6901c69d78488cbc41f8dbf080618fdeDan Gohman if (!PSV->isConstant(mf_->getFrameInfo())) 10156d69ba8a6901c69d78488cbc41f8dbf080618fdeDan Gohman return false; 10166d69ba8a6901c69d78488cbc41f8dbf080618fdeDan Gohman } else if (!aa_->pointsToConstantMemory(V)) 10176d69ba8a6901c69d78488cbc41f8dbf080618fdeDan Gohman return false; 10186d69ba8a6901c69d78488cbc41f8dbf080618fdeDan Gohman } 10196d69ba8a6901c69d78488cbc41f8dbf080618fdeDan Gohman 10206d69ba8a6901c69d78488cbc41f8dbf080618fdeDan Gohman // If any of the registers accessed are non-constant, conservatively assume 10216d69ba8a6901c69d78488cbc41f8dbf080618fdeDan Gohman // the instruction is not rematerializable. 10226d69ba8a6901c69d78488cbc41f8dbf080618fdeDan Gohman unsigned ImpUse = 0; 10236d69ba8a6901c69d78488cbc41f8dbf080618fdeDan Gohman for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) { 10246d69ba8a6901c69d78488cbc41f8dbf080618fdeDan Gohman const MachineOperand &MO = MI->getOperand(i); 1025d735b8019b0f297d7c14b55adcd887af24d8e602Dan Gohman if (MO.isReg()) { 10266d69ba8a6901c69d78488cbc41f8dbf080618fdeDan Gohman unsigned Reg = MO.getReg(); 10276d69ba8a6901c69d78488cbc41f8dbf080618fdeDan Gohman if (Reg == 0) 1028d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng continue; 10296d69ba8a6901c69d78488cbc41f8dbf080618fdeDan Gohman if (TargetRegisterInfo::isPhysicalRegister(Reg)) 10306d69ba8a6901c69d78488cbc41f8dbf080618fdeDan Gohman return false; 10316d69ba8a6901c69d78488cbc41f8dbf080618fdeDan Gohman 10326d69ba8a6901c69d78488cbc41f8dbf080618fdeDan Gohman // Only allow one def, and that in the first operand. 10336d69ba8a6901c69d78488cbc41f8dbf080618fdeDan Gohman if (MO.isDef() != (i == 0)) 1034d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng return false; 10356d69ba8a6901c69d78488cbc41f8dbf080618fdeDan Gohman 10366d69ba8a6901c69d78488cbc41f8dbf080618fdeDan Gohman // Only allow constant-valued registers. 10376d69ba8a6901c69d78488cbc41f8dbf080618fdeDan Gohman bool IsLiveIn = mri_->isLiveIn(Reg); 10386d69ba8a6901c69d78488cbc41f8dbf080618fdeDan Gohman MachineRegisterInfo::def_iterator I = mri_->def_begin(Reg), 10396d69ba8a6901c69d78488cbc41f8dbf080618fdeDan Gohman E = mri_->def_end(); 10406d69ba8a6901c69d78488cbc41f8dbf080618fdeDan Gohman 1041c93ced5b34b50a622ee8e49d90592f03ac7ff992Dan Gohman // For the def, it should be the only def of that register. 10426d69ba8a6901c69d78488cbc41f8dbf080618fdeDan Gohman if (MO.isDef() && (next(I) != E || IsLiveIn)) 10436d69ba8a6901c69d78488cbc41f8dbf080618fdeDan Gohman return false; 10446d69ba8a6901c69d78488cbc41f8dbf080618fdeDan Gohman 10456d69ba8a6901c69d78488cbc41f8dbf080618fdeDan Gohman if (MO.isUse()) { 10466d69ba8a6901c69d78488cbc41f8dbf080618fdeDan Gohman // Only allow one use other register use, as that's all the 10476d69ba8a6901c69d78488cbc41f8dbf080618fdeDan Gohman // remat mechanisms support currently. 10486d69ba8a6901c69d78488cbc41f8dbf080618fdeDan Gohman if (Reg != li.reg) { 10496d69ba8a6901c69d78488cbc41f8dbf080618fdeDan Gohman if (ImpUse == 0) 10506d69ba8a6901c69d78488cbc41f8dbf080618fdeDan Gohman ImpUse = Reg; 10516d69ba8a6901c69d78488cbc41f8dbf080618fdeDan Gohman else if (Reg != ImpUse) 10526d69ba8a6901c69d78488cbc41f8dbf080618fdeDan Gohman return false; 10536d69ba8a6901c69d78488cbc41f8dbf080618fdeDan Gohman } 1054c93ced5b34b50a622ee8e49d90592f03ac7ff992Dan Gohman // For the use, there should be only one associated def. 10556d69ba8a6901c69d78488cbc41f8dbf080618fdeDan Gohman if (I != E && (next(I) != E || IsLiveIn)) 10566d69ba8a6901c69d78488cbc41f8dbf080618fdeDan Gohman return false; 10576d69ba8a6901c69d78488cbc41f8dbf080618fdeDan Gohman } 1058d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng } 1059d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng } 10605ef3a04b542c4e585276768fa9ca2af698ef5c87Evan Cheng } 1061f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng 10626d69ba8a6901c69d78488cbc41f8dbf080618fdeDan Gohman unsigned ImpUse = getReMatImplicitUse(li, MI); 10636d69ba8a6901c69d78488cbc41f8dbf080618fdeDan Gohman if (ImpUse) { 10646d69ba8a6901c69d78488cbc41f8dbf080618fdeDan Gohman const LiveInterval &ImpLi = getInterval(ImpUse); 10656d69ba8a6901c69d78488cbc41f8dbf080618fdeDan Gohman for (MachineRegisterInfo::use_iterator ri = mri_->use_begin(li.reg), 10666d69ba8a6901c69d78488cbc41f8dbf080618fdeDan Gohman re = mri_->use_end(); ri != re; ++ri) { 10676d69ba8a6901c69d78488cbc41f8dbf080618fdeDan Gohman MachineInstr *UseMI = &*ri; 10686d69ba8a6901c69d78488cbc41f8dbf080618fdeDan Gohman unsigned UseIdx = getInstructionIndex(UseMI); 10696d69ba8a6901c69d78488cbc41f8dbf080618fdeDan Gohman if (li.FindLiveRangeContaining(UseIdx)->valno != ValNo) 10706d69ba8a6901c69d78488cbc41f8dbf080618fdeDan Gohman continue; 10716d69ba8a6901c69d78488cbc41f8dbf080618fdeDan Gohman if (!isValNoAvailableAt(ImpLi, MI, UseIdx)) 10726d69ba8a6901c69d78488cbc41f8dbf080618fdeDan Gohman return false; 10736d69ba8a6901c69d78488cbc41f8dbf080618fdeDan Gohman } 1074dc37786595beedd0a68d8e2cbd91ae53ad58d133Evan Cheng 1075dc37786595beedd0a68d8e2cbd91ae53ad58d133Evan Cheng // If a register operand of the re-materialized instruction is going to 1076dc37786595beedd0a68d8e2cbd91ae53ad58d133Evan Cheng // be spilled next, then it's not legal to re-materialize this instruction. 1077dc37786595beedd0a68d8e2cbd91ae53ad58d133Evan Cheng for (unsigned i = 0, e = SpillIs.size(); i != e; ++i) 1078dc37786595beedd0a68d8e2cbd91ae53ad58d133Evan Cheng if (ImpUse == SpillIs[i]->reg) 1079dc37786595beedd0a68d8e2cbd91ae53ad58d133Evan Cheng return false; 10806d69ba8a6901c69d78488cbc41f8dbf080618fdeDan Gohman } 10816d69ba8a6901c69d78488cbc41f8dbf080618fdeDan Gohman return true; 10825ef3a04b542c4e585276768fa9ca2af698ef5c87Evan Cheng} 10835ef3a04b542c4e585276768fa9ca2af698ef5c87Evan Cheng 108406587497dc1c39516f24784a2ac1d9323faae0a5Evan Cheng/// isReMaterializable - Returns true if the definition MI of the specified 108506587497dc1c39516f24784a2ac1d9323faae0a5Evan Cheng/// val# of the specified interval is re-materializable. 108606587497dc1c39516f24784a2ac1d9323faae0a5Evan Chengbool LiveIntervals::isReMaterializable(const LiveInterval &li, 108706587497dc1c39516f24784a2ac1d9323faae0a5Evan Cheng const VNInfo *ValNo, MachineInstr *MI) { 108806587497dc1c39516f24784a2ac1d9323faae0a5Evan Cheng SmallVector<LiveInterval*, 4> Dummy1; 108906587497dc1c39516f24784a2ac1d9323faae0a5Evan Cheng bool Dummy2; 109006587497dc1c39516f24784a2ac1d9323faae0a5Evan Cheng return isReMaterializable(li, ValNo, MI, Dummy1, Dummy2); 109106587497dc1c39516f24784a2ac1d9323faae0a5Evan Cheng} 109206587497dc1c39516f24784a2ac1d9323faae0a5Evan Cheng 10935ef3a04b542c4e585276768fa9ca2af698ef5c87Evan Cheng/// isReMaterializable - Returns true if every definition of MI of every 10945ef3a04b542c4e585276768fa9ca2af698ef5c87Evan Cheng/// val# of the specified interval is re-materializable. 1095dc37786595beedd0a68d8e2cbd91ae53ad58d133Evan Chengbool LiveIntervals::isReMaterializable(const LiveInterval &li, 1096dc37786595beedd0a68d8e2cbd91ae53ad58d133Evan Cheng SmallVectorImpl<LiveInterval*> &SpillIs, 1097dc37786595beedd0a68d8e2cbd91ae53ad58d133Evan Cheng bool &isLoad) { 10985ef3a04b542c4e585276768fa9ca2af698ef5c87Evan Cheng isLoad = false; 10995ef3a04b542c4e585276768fa9ca2af698ef5c87Evan Cheng for (LiveInterval::const_vni_iterator i = li.vni_begin(), e = li.vni_end(); 11005ef3a04b542c4e585276768fa9ca2af698ef5c87Evan Cheng i != e; ++i) { 11015ef3a04b542c4e585276768fa9ca2af698ef5c87Evan Cheng const VNInfo *VNI = *i; 11025ef3a04b542c4e585276768fa9ca2af698ef5c87Evan Cheng unsigned DefIdx = VNI->def; 11035ef3a04b542c4e585276768fa9ca2af698ef5c87Evan Cheng if (DefIdx == ~1U) 11045ef3a04b542c4e585276768fa9ca2af698ef5c87Evan Cheng continue; // Dead val#. 11055ef3a04b542c4e585276768fa9ca2af698ef5c87Evan Cheng // Is the def for the val# rematerializable? 11065ef3a04b542c4e585276768fa9ca2af698ef5c87Evan Cheng if (DefIdx == ~0u) 11075ef3a04b542c4e585276768fa9ca2af698ef5c87Evan Cheng return false; 11085ef3a04b542c4e585276768fa9ca2af698ef5c87Evan Cheng MachineInstr *ReMatDefMI = getInstructionFromIndex(DefIdx); 11095ef3a04b542c4e585276768fa9ca2af698ef5c87Evan Cheng bool DefIsLoad = false; 1110d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng if (!ReMatDefMI || 1111dc37786595beedd0a68d8e2cbd91ae53ad58d133Evan Cheng !isReMaterializable(li, VNI, ReMatDefMI, SpillIs, DefIsLoad)) 1112f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng return false; 11135ef3a04b542c4e585276768fa9ca2af698ef5c87Evan Cheng isLoad |= DefIsLoad; 1114f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng } 1115f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng return true; 1116f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng} 1117f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng 111879a0c1e46c4f7d8a2a06f4ef3e2c54d883c7fe25Evan Cheng/// FilterFoldedOps - Filter out two-address use operands. Return 111979a0c1e46c4f7d8a2a06f4ef3e2c54d883c7fe25Evan Cheng/// true if it finds any issue with the operands that ought to prevent 112079a0c1e46c4f7d8a2a06f4ef3e2c54d883c7fe25Evan Cheng/// folding. 112179a0c1e46c4f7d8a2a06f4ef3e2c54d883c7fe25Evan Chengstatic bool FilterFoldedOps(MachineInstr *MI, 112279a0c1e46c4f7d8a2a06f4ef3e2c54d883c7fe25Evan Cheng SmallVector<unsigned, 2> &Ops, 112379a0c1e46c4f7d8a2a06f4ef3e2c54d883c7fe25Evan Cheng unsigned &MRInfo, 112479a0c1e46c4f7d8a2a06f4ef3e2c54d883c7fe25Evan Cheng SmallVector<unsigned, 2> &FoldOps) { 112579a0c1e46c4f7d8a2a06f4ef3e2c54d883c7fe25Evan Cheng MRInfo = 0; 1126aee4af68ae2016afc5b4ec0c430e539c5810a766Evan Cheng for (unsigned i = 0, e = Ops.size(); i != e; ++i) { 1127aee4af68ae2016afc5b4ec0c430e539c5810a766Evan Cheng unsigned OpIdx = Ops[i]; 1128d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng MachineOperand &MO = MI->getOperand(OpIdx); 1129aee4af68ae2016afc5b4ec0c430e539c5810a766Evan Cheng // FIXME: fold subreg use. 1130d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng if (MO.getSubReg()) 113179a0c1e46c4f7d8a2a06f4ef3e2c54d883c7fe25Evan Cheng return true; 1132d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng if (MO.isDef()) 1133aee4af68ae2016afc5b4ec0c430e539c5810a766Evan Cheng MRInfo |= (unsigned)VirtRegMap::isMod; 1134aee4af68ae2016afc5b4ec0c430e539c5810a766Evan Cheng else { 1135aee4af68ae2016afc5b4ec0c430e539c5810a766Evan Cheng // Filter out two-address use operand(s). 1136a24752ff43dc1ad8c18c5d9e78549c45f62b980eEvan Cheng if (MI->isRegTiedToDefOperand(OpIdx)) { 1137aee4af68ae2016afc5b4ec0c430e539c5810a766Evan Cheng MRInfo = VirtRegMap::isModRef; 1138aee4af68ae2016afc5b4ec0c430e539c5810a766Evan Cheng continue; 1139aee4af68ae2016afc5b4ec0c430e539c5810a766Evan Cheng } 1140aee4af68ae2016afc5b4ec0c430e539c5810a766Evan Cheng MRInfo |= (unsigned)VirtRegMap::isRef; 1141aee4af68ae2016afc5b4ec0c430e539c5810a766Evan Cheng } 1142aee4af68ae2016afc5b4ec0c430e539c5810a766Evan Cheng FoldOps.push_back(OpIdx); 1143e62f97c094dba44e4c259d20135167fa91912eeaEvan Cheng } 114479a0c1e46c4f7d8a2a06f4ef3e2c54d883c7fe25Evan Cheng return false; 114579a0c1e46c4f7d8a2a06f4ef3e2c54d883c7fe25Evan Cheng} 114679a0c1e46c4f7d8a2a06f4ef3e2c54d883c7fe25Evan Cheng 114779a0c1e46c4f7d8a2a06f4ef3e2c54d883c7fe25Evan Cheng 114879a0c1e46c4f7d8a2a06f4ef3e2c54d883c7fe25Evan Cheng/// tryFoldMemoryOperand - Attempts to fold either a spill / restore from 114979a0c1e46c4f7d8a2a06f4ef3e2c54d883c7fe25Evan Cheng/// slot / to reg or any rematerialized load into ith operand of specified 115079a0c1e46c4f7d8a2a06f4ef3e2c54d883c7fe25Evan Cheng/// MI. If it is successul, MI is updated with the newly created MI and 115179a0c1e46c4f7d8a2a06f4ef3e2c54d883c7fe25Evan Cheng/// returns true. 115279a0c1e46c4f7d8a2a06f4ef3e2c54d883c7fe25Evan Chengbool LiveIntervals::tryFoldMemoryOperand(MachineInstr* &MI, 115379a0c1e46c4f7d8a2a06f4ef3e2c54d883c7fe25Evan Cheng VirtRegMap &vrm, MachineInstr *DefMI, 115479a0c1e46c4f7d8a2a06f4ef3e2c54d883c7fe25Evan Cheng unsigned InstrIdx, 115579a0c1e46c4f7d8a2a06f4ef3e2c54d883c7fe25Evan Cheng SmallVector<unsigned, 2> &Ops, 115679a0c1e46c4f7d8a2a06f4ef3e2c54d883c7fe25Evan Cheng bool isSS, int Slot, unsigned Reg) { 115779a0c1e46c4f7d8a2a06f4ef3e2c54d883c7fe25Evan Cheng // If it is an implicit def instruction, just delete it. 115820ccded7dec5b90e58f649f4fb95b166a642b8cbEvan Cheng if (MI->getOpcode() == TargetInstrInfo::IMPLICIT_DEF) { 115979a0c1e46c4f7d8a2a06f4ef3e2c54d883c7fe25Evan Cheng RemoveMachineInstrFromMaps(MI); 116079a0c1e46c4f7d8a2a06f4ef3e2c54d883c7fe25Evan Cheng vrm.RemoveMachineInstrFromMaps(MI); 116179a0c1e46c4f7d8a2a06f4ef3e2c54d883c7fe25Evan Cheng MI->eraseFromParent(); 116279a0c1e46c4f7d8a2a06f4ef3e2c54d883c7fe25Evan Cheng ++numFolds; 116379a0c1e46c4f7d8a2a06f4ef3e2c54d883c7fe25Evan Cheng return true; 116479a0c1e46c4f7d8a2a06f4ef3e2c54d883c7fe25Evan Cheng } 116579a0c1e46c4f7d8a2a06f4ef3e2c54d883c7fe25Evan Cheng 116679a0c1e46c4f7d8a2a06f4ef3e2c54d883c7fe25Evan Cheng // Filter the list of operand indexes that are to be folded. Abort if 116779a0c1e46c4f7d8a2a06f4ef3e2c54d883c7fe25Evan Cheng // any operand will prevent folding. 116879a0c1e46c4f7d8a2a06f4ef3e2c54d883c7fe25Evan Cheng unsigned MRInfo = 0; 116979a0c1e46c4f7d8a2a06f4ef3e2c54d883c7fe25Evan Cheng SmallVector<unsigned, 2> FoldOps; 117079a0c1e46c4f7d8a2a06f4ef3e2c54d883c7fe25Evan Cheng if (FilterFoldedOps(MI, Ops, MRInfo, FoldOps)) 117179a0c1e46c4f7d8a2a06f4ef3e2c54d883c7fe25Evan Cheng return false; 1172cddbb83ea82e98658d9f530c50a7b9d23249afc2Evan Cheng 1173427f4c106ac14dcf323dc1bbaf1b8040da03c3c7Evan Cheng // The only time it's safe to fold into a two address instruction is when 1174427f4c106ac14dcf323dc1bbaf1b8040da03c3c7Evan Cheng // it's folding reload and spill from / into a spill stack slot. 1175427f4c106ac14dcf323dc1bbaf1b8040da03c3c7Evan Cheng if (DefMI && (MRInfo & VirtRegMap::isMod)) 1176249ded3fa8884f91fded869fb6e251b8aebb0376Evan Cheng return false; 1177249ded3fa8884f91fded869fb6e251b8aebb0376Evan Cheng 1178f2f8c2ae07b7d9bdbf1b89781c573c7af2bd5e1bEvan Cheng MachineInstr *fmi = isSS ? tii_->foldMemoryOperand(*mf_, MI, FoldOps, Slot) 1179f2f8c2ae07b7d9bdbf1b89781c573c7af2bd5e1bEvan Cheng : tii_->foldMemoryOperand(*mf_, MI, FoldOps, DefMI); 1180f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng if (fmi) { 1181d36531249a9a9500e516148e7e72d4c0a7a4d0eeEvan Cheng // Remember this instruction uses the spill slot. 1182d36531249a9a9500e516148e7e72d4c0a7a4d0eeEvan Cheng if (isSS) vrm.addSpillSlotUse(Slot, fmi); 1183d36531249a9a9500e516148e7e72d4c0a7a4d0eeEvan Cheng 1184f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng // Attempt to fold the memory reference into the instruction. If 1185f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng // we can do this, we don't need to insert spill code. 1186f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng MachineBasicBlock &MBB = *MI->getParent(); 11878480293f41c11c22762164449e41cd3adb0dd7d8Evan Cheng if (isSS && !mf_->getFrameInfo()->isImmutableObjectIndex(Slot)) 1188aee4af68ae2016afc5b4ec0c430e539c5810a766Evan Cheng vrm.virtFolded(Reg, MI, fmi, (VirtRegMap::ModRef)MRInfo); 118981a038218171860ee4c382849c647d3dc841fe8bEvan Cheng vrm.transferSpillPts(MI, fmi); 11900cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng vrm.transferRestorePts(MI, fmi); 1191c1f53c742620dd4f2460685477303002bba8a8d8Evan Cheng vrm.transferEmergencySpills(MI, fmi); 1192f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng mi2iMap_.erase(MI); 1193cddbb83ea82e98658d9f530c50a7b9d23249afc2Evan Cheng i2miMap_[InstrIdx /InstrSlots::NUM] = fmi; 1194cddbb83ea82e98658d9f530c50a7b9d23249afc2Evan Cheng mi2iMap_[fmi] = InstrIdx; 1195f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng MI = MBB.insert(MBB.erase(MI), fmi); 11960cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng ++numFolds; 1197f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng return true; 1198f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng } 1199f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng return false; 1200f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng} 1201f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng 1202018f9b020bb12b731b0a7081578e5f82fb35092dEvan Cheng/// canFoldMemoryOperand - Returns true if the specified load / store 1203018f9b020bb12b731b0a7081578e5f82fb35092dEvan Cheng/// folding is possible. 1204018f9b020bb12b731b0a7081578e5f82fb35092dEvan Chengbool LiveIntervals::canFoldMemoryOperand(MachineInstr *MI, 120579a0c1e46c4f7d8a2a06f4ef3e2c54d883c7fe25Evan Cheng SmallVector<unsigned, 2> &Ops, 12063c75ba858b4e2070993cc1241ba74ead17f647d6Evan Cheng bool ReMat) const { 120779a0c1e46c4f7d8a2a06f4ef3e2c54d883c7fe25Evan Cheng // Filter the list of operand indexes that are to be folded. Abort if 120879a0c1e46c4f7d8a2a06f4ef3e2c54d883c7fe25Evan Cheng // any operand will prevent folding. 120979a0c1e46c4f7d8a2a06f4ef3e2c54d883c7fe25Evan Cheng unsigned MRInfo = 0; 1210018f9b020bb12b731b0a7081578e5f82fb35092dEvan Cheng SmallVector<unsigned, 2> FoldOps; 121179a0c1e46c4f7d8a2a06f4ef3e2c54d883c7fe25Evan Cheng if (FilterFoldedOps(MI, Ops, MRInfo, FoldOps)) 121279a0c1e46c4f7d8a2a06f4ef3e2c54d883c7fe25Evan Cheng return false; 1213018f9b020bb12b731b0a7081578e5f82fb35092dEvan Cheng 12143c75ba858b4e2070993cc1241ba74ead17f647d6Evan Cheng // It's only legal to remat for a use, not a def. 12153c75ba858b4e2070993cc1241ba74ead17f647d6Evan Cheng if (ReMat && (MRInfo & VirtRegMap::isMod)) 121679a0c1e46c4f7d8a2a06f4ef3e2c54d883c7fe25Evan Cheng return false; 1217018f9b020bb12b731b0a7081578e5f82fb35092dEvan Cheng 1218d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng return tii_->canFoldMemoryOperand(MI, FoldOps); 1219d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng} 1220d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng 122181a038218171860ee4c382849c647d3dc841fe8bEvan Chengbool LiveIntervals::intervalIsInOneMBB(const LiveInterval &li) const { 122281a038218171860ee4c382849c647d3dc841fe8bEvan Cheng SmallPtrSet<MachineBasicBlock*, 4> MBBs; 122381a038218171860ee4c382849c647d3dc841fe8bEvan Cheng for (LiveInterval::Ranges::const_iterator 122481a038218171860ee4c382849c647d3dc841fe8bEvan Cheng I = li.ranges.begin(), E = li.ranges.end(); I != E; ++I) { 122581a038218171860ee4c382849c647d3dc841fe8bEvan Cheng std::vector<IdxMBBPair>::const_iterator II = 122681a038218171860ee4c382849c647d3dc841fe8bEvan Cheng std::lower_bound(Idx2MBBMap.begin(), Idx2MBBMap.end(), I->start); 122781a038218171860ee4c382849c647d3dc841fe8bEvan Cheng if (II == Idx2MBBMap.end()) 122881a038218171860ee4c382849c647d3dc841fe8bEvan Cheng continue; 122981a038218171860ee4c382849c647d3dc841fe8bEvan Cheng if (I->end > II->first) // crossing a MBB. 123081a038218171860ee4c382849c647d3dc841fe8bEvan Cheng return false; 123181a038218171860ee4c382849c647d3dc841fe8bEvan Cheng MBBs.insert(II->second); 123281a038218171860ee4c382849c647d3dc841fe8bEvan Cheng if (MBBs.size() > 1) 123381a038218171860ee4c382849c647d3dc841fe8bEvan Cheng return false; 123481a038218171860ee4c382849c647d3dc841fe8bEvan Cheng } 123581a038218171860ee4c382849c647d3dc841fe8bEvan Cheng return true; 123681a038218171860ee4c382849c647d3dc841fe8bEvan Cheng} 123781a038218171860ee4c382849c647d3dc841fe8bEvan Cheng 1238d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng/// rewriteImplicitOps - Rewrite implicit use operands of MI (i.e. uses of 1239d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng/// interval on to-be re-materialized operands of MI) with new register. 1240d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Chengvoid LiveIntervals::rewriteImplicitOps(const LiveInterval &li, 1241d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng MachineInstr *MI, unsigned NewVReg, 1242d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng VirtRegMap &vrm) { 1243d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng // There is an implicit use. That means one of the other operand is 1244d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng // being remat'ed and the remat'ed instruction has li.reg as an 1245d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng // use operand. Make sure we rewrite that as well. 1246d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) { 1247d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng MachineOperand &MO = MI->getOperand(i); 1248d735b8019b0f297d7c14b55adcd887af24d8e602Dan Gohman if (!MO.isReg()) 1249d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng continue; 1250d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng unsigned Reg = MO.getReg(); 1251d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng if (Reg == 0 || TargetRegisterInfo::isPhysicalRegister(Reg)) 1252d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng continue; 1253d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng if (!vrm.isReMaterialized(Reg)) 1254d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng continue; 1255d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng MachineInstr *ReMatMI = vrm.getReMaterializedMI(Reg); 12566130f66eaae89f8878590796977678afa8448926Evan Cheng MachineOperand *UseMO = ReMatMI->findRegisterUseOperand(li.reg); 12576130f66eaae89f8878590796977678afa8448926Evan Cheng if (UseMO) 12586130f66eaae89f8878590796977678afa8448926Evan Cheng UseMO->setReg(NewVReg); 1259d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng } 1260d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng} 1261d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng 1262f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng/// rewriteInstructionForSpills, rewriteInstructionsForSpills - Helper functions 1263f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng/// for addIntervalsForSpills to rewrite uses / defs for the given live range. 1264018f9b020bb12b731b0a7081578e5f82fb35092dEvan Chengbool LiveIntervals:: 1265d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan ChengrewriteInstructionForSpills(const LiveInterval &li, const VNInfo *VNI, 1266d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng bool TrySplit, unsigned index, unsigned end, MachineInstr *MI, 126781a038218171860ee4c382849c647d3dc841fe8bEvan Cheng MachineInstr *ReMatOrigDefMI, MachineInstr *ReMatDefMI, 1268f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng unsigned Slot, int LdSlot, 1269f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng bool isLoad, bool isLoadSS, bool DefIsReMat, bool CanDelete, 1270d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng VirtRegMap &vrm, 1271f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng const TargetRegisterClass* rc, 1272f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng SmallVector<int, 4> &ReMatIds, 127322f07ffd27d1d721634d502c37267721d2e025cfEvan Cheng const MachineLoopInfo *loopInfo, 1274313d4b809326f3e04814f94e5b8ae05649d8e0f6Evan Cheng unsigned &NewVReg, unsigned ImpUse, bool &HasDef, bool &HasUse, 1275289983123ba4170c8a27e9638935818f8142bc89Owen Anderson DenseMap<unsigned,unsigned> &MBBVRegsMap, 1276c781a243a3d17e7e763515794168d8fa6043f565Evan Cheng std::vector<LiveInterval*> &NewLIs) { 1277018f9b020bb12b731b0a7081578e5f82fb35092dEvan Cheng bool CanFold = false; 1278f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng RestartInstruction: 1279f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng for (unsigned i = 0; i != MI->getNumOperands(); ++i) { 1280f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng MachineOperand& mop = MI->getOperand(i); 1281d735b8019b0f297d7c14b55adcd887af24d8e602Dan Gohman if (!mop.isReg()) 1282f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng continue; 1283f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng unsigned Reg = mop.getReg(); 1284f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng unsigned RegI = Reg; 12856f0d024a534af18d9e60b3ea757376cd8a3a980eDan Gohman if (Reg == 0 || TargetRegisterInfo::isPhysicalRegister(Reg)) 1286f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng continue; 1287f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng if (Reg != li.reg) 1288f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng continue; 1289f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng 1290f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng bool TryFold = !DefIsReMat; 1291cb3c330d39442130d0587208d673ce9c33c7008fEvan Cheng bool FoldSS = true; // Default behavior unless it's a remat. 1292f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng int FoldSlot = Slot; 1293f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng if (DefIsReMat) { 1294f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng // If this is the rematerializable definition MI itself and 1295f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng // all of its uses are rematerialized, simply delete it. 129681a038218171860ee4c382849c647d3dc841fe8bEvan Cheng if (MI == ReMatOrigDefMI && CanDelete) { 1297cddbb83ea82e98658d9f530c50a7b9d23249afc2Evan Cheng DOUT << "\t\t\t\tErasing re-materlizable def: "; 1298cddbb83ea82e98658d9f530c50a7b9d23249afc2Evan Cheng DOUT << MI << '\n'; 1299f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng RemoveMachineInstrFromMaps(MI); 1300cada245d06959831b90f8c29f92e77beda4b71cbEvan Cheng vrm.RemoveMachineInstrFromMaps(MI); 1301f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng MI->eraseFromParent(); 1302f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng break; 1303f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng } 1304f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng 1305f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng // If def for this use can't be rematerialized, then try folding. 13060cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng // If def is rematerializable and it's a load, also try folding. 1307cb3c330d39442130d0587208d673ce9c33c7008fEvan Cheng TryFold = !ReMatDefMI || (ReMatDefMI && (MI == ReMatOrigDefMI || isLoad)); 1308f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng if (isLoad) { 1309f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng // Try fold loads (from stack slot, constant pool, etc.) into uses. 1310f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng FoldSS = isLoadSS; 1311f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng FoldSlot = LdSlot; 1312f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng } 1313f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng } 1314f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng 1315f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng // Scan all of the operands of this instruction rewriting operands 1316f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng // to use NewVReg instead of li.reg as appropriate. We do this for 1317f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng // two reasons: 1318f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng // 1319f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng // 1. If the instr reads the same spilled vreg multiple times, we 1320f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng // want to reuse the NewVReg. 1321f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng // 2. If the instr is a two-addr instruction, we are required to 1322f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng // keep the src/dst regs pinned. 1323f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng // 1324f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng // Keep track of whether we replace a use and/or def so that we can 1325f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng // create the spill interval with the appropriate range. 1326cddbb83ea82e98658d9f530c50a7b9d23249afc2Evan Cheng 132781a038218171860ee4c382849c647d3dc841fe8bEvan Cheng HasUse = mop.isUse(); 132881a038218171860ee4c382849c647d3dc841fe8bEvan Cheng HasDef = mop.isDef(); 1329aee4af68ae2016afc5b4ec0c430e539c5810a766Evan Cheng SmallVector<unsigned, 2> Ops; 1330aee4af68ae2016afc5b4ec0c430e539c5810a766Evan Cheng Ops.push_back(i); 1331f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng for (unsigned j = i+1, e = MI->getNumOperands(); j != e; ++j) { 1332aee4af68ae2016afc5b4ec0c430e539c5810a766Evan Cheng const MachineOperand &MOj = MI->getOperand(j); 1333d735b8019b0f297d7c14b55adcd887af24d8e602Dan Gohman if (!MOj.isReg()) 1334f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng continue; 1335aee4af68ae2016afc5b4ec0c430e539c5810a766Evan Cheng unsigned RegJ = MOj.getReg(); 13366f0d024a534af18d9e60b3ea757376cd8a3a980eDan Gohman if (RegJ == 0 || TargetRegisterInfo::isPhysicalRegister(RegJ)) 1337f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng continue; 1338f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng if (RegJ == RegI) { 1339aee4af68ae2016afc5b4ec0c430e539c5810a766Evan Cheng Ops.push_back(j); 1340aee4af68ae2016afc5b4ec0c430e539c5810a766Evan Cheng HasUse |= MOj.isUse(); 1341aee4af68ae2016afc5b4ec0c430e539c5810a766Evan Cheng HasDef |= MOj.isDef(); 1342f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng } 1343f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng } 1344f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng 134579a796c2b17c7ebd4dd489b5de1078fc2148adbaEvan Cheng if (HasUse && !li.liveAt(getUseIndex(index))) 134679a796c2b17c7ebd4dd489b5de1078fc2148adbaEvan Cheng // Must be defined by an implicit def. It should not be spilled. Note, 134779a796c2b17c7ebd4dd489b5de1078fc2148adbaEvan Cheng // this is for correctness reason. e.g. 134879a796c2b17c7ebd4dd489b5de1078fc2148adbaEvan Cheng // 8 %reg1024<def> = IMPLICIT_DEF 134979a796c2b17c7ebd4dd489b5de1078fc2148adbaEvan Cheng // 12 %reg1024<def> = INSERT_SUBREG %reg1024<kill>, %reg1025, 2 135079a796c2b17c7ebd4dd489b5de1078fc2148adbaEvan Cheng // The live range [12, 14) are not part of the r1024 live interval since 135179a796c2b17c7ebd4dd489b5de1078fc2148adbaEvan Cheng // it's defined by an implicit def. It will not conflicts with live 135279a796c2b17c7ebd4dd489b5de1078fc2148adbaEvan Cheng // interval of r1025. Now suppose both registers are spilled, you can 1353b9890ae3c35ad7d8e49261650d5b98f49f97a705Evan Cheng // easily see a situation where both registers are reloaded before 135479a796c2b17c7ebd4dd489b5de1078fc2148adbaEvan Cheng // the INSERT_SUBREG and both target registers that would overlap. 135579a796c2b17c7ebd4dd489b5de1078fc2148adbaEvan Cheng HasUse = false; 135679a796c2b17c7ebd4dd489b5de1078fc2148adbaEvan Cheng 135726b86a0b5676253040dc206b437536a24306fb76David Greene // Create a new virtual register for the spill interval. 135826b86a0b5676253040dc206b437536a24306fb76David Greene // Create the new register now so we can map the fold instruction 135926b86a0b5676253040dc206b437536a24306fb76David Greene // to the new register so when it is unfolded we get the correct 136026b86a0b5676253040dc206b437536a24306fb76David Greene // answer. 136126b86a0b5676253040dc206b437536a24306fb76David Greene bool CreatedNewVReg = false; 136226b86a0b5676253040dc206b437536a24306fb76David Greene if (NewVReg == 0) { 136326b86a0b5676253040dc206b437536a24306fb76David Greene NewVReg = mri_->createVirtualRegister(rc); 136426b86a0b5676253040dc206b437536a24306fb76David Greene vrm.grow(); 136526b86a0b5676253040dc206b437536a24306fb76David Greene CreatedNewVReg = true; 136626b86a0b5676253040dc206b437536a24306fb76David Greene } 136726b86a0b5676253040dc206b437536a24306fb76David Greene 13689c3c2213647e3f1b71722d61875ebac01b65cb91Evan Cheng if (!TryFold) 13699c3c2213647e3f1b71722d61875ebac01b65cb91Evan Cheng CanFold = false; 13709c3c2213647e3f1b71722d61875ebac01b65cb91Evan Cheng else { 1371018f9b020bb12b731b0a7081578e5f82fb35092dEvan Cheng // Do not fold load / store here if we are splitting. We'll find an 1372018f9b020bb12b731b0a7081578e5f82fb35092dEvan Cheng // optimal point to insert a load / store later. 1373018f9b020bb12b731b0a7081578e5f82fb35092dEvan Cheng if (!TrySplit) { 1374018f9b020bb12b731b0a7081578e5f82fb35092dEvan Cheng if (tryFoldMemoryOperand(MI, vrm, ReMatDefMI, index, 137526b86a0b5676253040dc206b437536a24306fb76David Greene Ops, FoldSS, FoldSlot, NewVReg)) { 1376018f9b020bb12b731b0a7081578e5f82fb35092dEvan Cheng // Folding the load/store can completely change the instruction in 1377018f9b020bb12b731b0a7081578e5f82fb35092dEvan Cheng // unpredictable ways, rescan it from the beginning. 137826b86a0b5676253040dc206b437536a24306fb76David Greene 137926b86a0b5676253040dc206b437536a24306fb76David Greene if (FoldSS) { 138026b86a0b5676253040dc206b437536a24306fb76David Greene // We need to give the new vreg the same stack slot as the 138126b86a0b5676253040dc206b437536a24306fb76David Greene // spilled interval. 138226b86a0b5676253040dc206b437536a24306fb76David Greene vrm.assignVirt2StackSlot(NewVReg, FoldSlot); 138326b86a0b5676253040dc206b437536a24306fb76David Greene } 138426b86a0b5676253040dc206b437536a24306fb76David Greene 1385018f9b020bb12b731b0a7081578e5f82fb35092dEvan Cheng HasUse = false; 1386018f9b020bb12b731b0a7081578e5f82fb35092dEvan Cheng HasDef = false; 1387018f9b020bb12b731b0a7081578e5f82fb35092dEvan Cheng CanFold = false; 1388c781a243a3d17e7e763515794168d8fa6043f565Evan Cheng if (isNotInMIMap(MI)) 13897e073baedb8232b9519dbe15ea141ff98ccfe6aeEvan Cheng break; 1390018f9b020bb12b731b0a7081578e5f82fb35092dEvan Cheng goto RestartInstruction; 1391018f9b020bb12b731b0a7081578e5f82fb35092dEvan Cheng } 1392018f9b020bb12b731b0a7081578e5f82fb35092dEvan Cheng } else { 13939c3c2213647e3f1b71722d61875ebac01b65cb91Evan Cheng // We'll try to fold it later if it's profitable. 13943c75ba858b4e2070993cc1241ba74ead17f647d6Evan Cheng CanFold = canFoldMemoryOperand(MI, Ops, DefIsReMat); 1395018f9b020bb12b731b0a7081578e5f82fb35092dEvan Cheng } 13969c3c2213647e3f1b71722d61875ebac01b65cb91Evan Cheng } 1397cddbb83ea82e98658d9f530c50a7b9d23249afc2Evan Cheng 1398cddbb83ea82e98658d9f530c50a7b9d23249afc2Evan Cheng mop.setReg(NewVReg); 1399d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng if (mop.isImplicit()) 1400d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng rewriteImplicitOps(li, MI, NewVReg, vrm); 1401cddbb83ea82e98658d9f530c50a7b9d23249afc2Evan Cheng 1402cddbb83ea82e98658d9f530c50a7b9d23249afc2Evan Cheng // Reuse NewVReg for other reads. 1403d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng for (unsigned j = 0, e = Ops.size(); j != e; ++j) { 1404d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng MachineOperand &mopj = MI->getOperand(Ops[j]); 1405d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng mopj.setReg(NewVReg); 1406d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng if (mopj.isImplicit()) 1407d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng rewriteImplicitOps(li, MI, NewVReg, vrm); 1408d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng } 1409cddbb83ea82e98658d9f530c50a7b9d23249afc2Evan Cheng 141081a038218171860ee4c382849c647d3dc841fe8bEvan Cheng if (CreatedNewVReg) { 141181a038218171860ee4c382849c647d3dc841fe8bEvan Cheng if (DefIsReMat) { 141281a038218171860ee4c382849c647d3dc841fe8bEvan Cheng vrm.setVirtIsReMaterialized(NewVReg, ReMatDefMI/*, CanDelete*/); 1413d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng if (ReMatIds[VNI->id] == VirtRegMap::MAX_STACK_SLOT) { 141481a038218171860ee4c382849c647d3dc841fe8bEvan Cheng // Each valnum may have its own remat id. 1415d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng ReMatIds[VNI->id] = vrm.assignVirtReMatId(NewVReg); 141681a038218171860ee4c382849c647d3dc841fe8bEvan Cheng } else { 1417d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng vrm.assignVirtReMatId(NewVReg, ReMatIds[VNI->id]); 141881a038218171860ee4c382849c647d3dc841fe8bEvan Cheng } 141981a038218171860ee4c382849c647d3dc841fe8bEvan Cheng if (!CanDelete || (HasUse && HasDef)) { 142081a038218171860ee4c382849c647d3dc841fe8bEvan Cheng // If this is a two-addr instruction then its use operands are 142181a038218171860ee4c382849c647d3dc841fe8bEvan Cheng // rematerializable but its def is not. It should be assigned a 142281a038218171860ee4c382849c647d3dc841fe8bEvan Cheng // stack slot. 142381a038218171860ee4c382849c647d3dc841fe8bEvan Cheng vrm.assignVirt2StackSlot(NewVReg, Slot); 142481a038218171860ee4c382849c647d3dc841fe8bEvan Cheng } 1425f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng } else { 1426f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng vrm.assignVirt2StackSlot(NewVReg, Slot); 1427f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng } 1428cb3c330d39442130d0587208d673ce9c33c7008fEvan Cheng } else if (HasUse && HasDef && 1429cb3c330d39442130d0587208d673ce9c33c7008fEvan Cheng vrm.getStackSlot(NewVReg) == VirtRegMap::NO_STACK_SLOT) { 1430cb3c330d39442130d0587208d673ce9c33c7008fEvan Cheng // If this interval hasn't been assigned a stack slot (because earlier 1431cb3c330d39442130d0587208d673ce9c33c7008fEvan Cheng // def is a deleted remat def), do it now. 1432cb3c330d39442130d0587208d673ce9c33c7008fEvan Cheng assert(Slot != VirtRegMap::NO_STACK_SLOT); 1433cb3c330d39442130d0587208d673ce9c33c7008fEvan Cheng vrm.assignVirt2StackSlot(NewVReg, Slot); 1434f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng } 1435f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng 1436313d4b809326f3e04814f94e5b8ae05649d8e0f6Evan Cheng // Re-matting an instruction with virtual register use. Add the 1437313d4b809326f3e04814f94e5b8ae05649d8e0f6Evan Cheng // register as an implicit use on the use MI. 1438313d4b809326f3e04814f94e5b8ae05649d8e0f6Evan Cheng if (DefIsReMat && ImpUse) 1439313d4b809326f3e04814f94e5b8ae05649d8e0f6Evan Cheng MI->addOperand(MachineOperand::CreateReg(ImpUse, false, true)); 1440313d4b809326f3e04814f94e5b8ae05649d8e0f6Evan Cheng 14415b69ebac857104770b1a751bf7a463fda4330a62Evan Cheng // Create a new register interval for this spill / remat. 1442f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng LiveInterval &nI = getOrCreateInterval(NewVReg); 144381a038218171860ee4c382849c647d3dc841fe8bEvan Cheng if (CreatedNewVReg) { 144481a038218171860ee4c382849c647d3dc841fe8bEvan Cheng NewLIs.push_back(&nI); 14451953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng MBBVRegsMap.insert(std::make_pair(MI->getParent()->getNumber(), NewVReg)); 144681a038218171860ee4c382849c647d3dc841fe8bEvan Cheng if (TrySplit) 144781a038218171860ee4c382849c647d3dc841fe8bEvan Cheng vrm.setIsSplitFromReg(NewVReg, li.reg); 144881a038218171860ee4c382849c647d3dc841fe8bEvan Cheng } 1449f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng 1450f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng if (HasUse) { 145181a038218171860ee4c382849c647d3dc841fe8bEvan Cheng if (CreatedNewVReg) { 145281a038218171860ee4c382849c647d3dc841fe8bEvan Cheng LiveRange LR(getLoadIndex(index), getUseIndex(index)+1, 145381a038218171860ee4c382849c647d3dc841fe8bEvan Cheng nI.getNextValue(~0U, 0, VNInfoAllocator)); 145481a038218171860ee4c382849c647d3dc841fe8bEvan Cheng DOUT << " +" << LR; 145581a038218171860ee4c382849c647d3dc841fe8bEvan Cheng nI.addRange(LR); 145681a038218171860ee4c382849c647d3dc841fe8bEvan Cheng } else { 145781a038218171860ee4c382849c647d3dc841fe8bEvan Cheng // Extend the split live interval to this def / use. 145881a038218171860ee4c382849c647d3dc841fe8bEvan Cheng unsigned End = getUseIndex(index)+1; 145981a038218171860ee4c382849c647d3dc841fe8bEvan Cheng LiveRange LR(nI.ranges[nI.ranges.size()-1].end, End, 146081a038218171860ee4c382849c647d3dc841fe8bEvan Cheng nI.getValNumInfo(nI.getNumValNums()-1)); 146181a038218171860ee4c382849c647d3dc841fe8bEvan Cheng DOUT << " +" << LR; 146281a038218171860ee4c382849c647d3dc841fe8bEvan Cheng nI.addRange(LR); 146381a038218171860ee4c382849c647d3dc841fe8bEvan Cheng } 1464f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng } 1465f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng if (HasDef) { 1466f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng LiveRange LR(getDefIndex(index), getStoreIndex(index), 1467f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng nI.getNextValue(~0U, 0, VNInfoAllocator)); 1468f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng DOUT << " +" << LR; 1469f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng nI.addRange(LR); 1470f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng } 147181a038218171860ee4c382849c647d3dc841fe8bEvan Cheng 1472f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng DOUT << "\t\t\t\tAdded new interval: "; 14736f0d024a534af18d9e60b3ea757376cd8a3a980eDan Gohman nI.print(DOUT, tri_); 1474f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng DOUT << '\n'; 1475f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng } 1476018f9b020bb12b731b0a7081578e5f82fb35092dEvan Cheng return CanFold; 1477f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng} 147881a038218171860ee4c382849c647d3dc841fe8bEvan Chengbool LiveIntervals::anyKillInMBBAfterIdx(const LiveInterval &li, 14790cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng const VNInfo *VNI, 14800cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng MachineBasicBlock *MBB, unsigned Idx) const { 148181a038218171860ee4c382849c647d3dc841fe8bEvan Cheng unsigned End = getMBBEndIdx(MBB); 14820cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng for (unsigned j = 0, ee = VNI->kills.size(); j != ee; ++j) { 14830cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng unsigned KillIdx = VNI->kills[j]; 14840cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng if (KillIdx > Idx && KillIdx < End) 14850cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng return true; 148681a038218171860ee4c382849c647d3dc841fe8bEvan Cheng } 148781a038218171860ee4c382849c647d3dc841fe8bEvan Cheng return false; 148881a038218171860ee4c382849c647d3dc841fe8bEvan Cheng} 148981a038218171860ee4c382849c647d3dc841fe8bEvan Cheng 1490063284c001666c0a3906acbe0a26dc7cae5f081cEvan Cheng/// RewriteInfo - Keep track of machine instrs that will be rewritten 1491063284c001666c0a3906acbe0a26dc7cae5f081cEvan Cheng/// during spilling. 1492844731a7f1909f55935e3514c9e713a62d67662eDan Gohmannamespace { 1493844731a7f1909f55935e3514c9e713a62d67662eDan Gohman struct RewriteInfo { 1494844731a7f1909f55935e3514c9e713a62d67662eDan Gohman unsigned Index; 1495844731a7f1909f55935e3514c9e713a62d67662eDan Gohman MachineInstr *MI; 1496844731a7f1909f55935e3514c9e713a62d67662eDan Gohman bool HasUse; 1497844731a7f1909f55935e3514c9e713a62d67662eDan Gohman bool HasDef; 1498844731a7f1909f55935e3514c9e713a62d67662eDan Gohman RewriteInfo(unsigned i, MachineInstr *mi, bool u, bool d) 1499844731a7f1909f55935e3514c9e713a62d67662eDan Gohman : Index(i), MI(mi), HasUse(u), HasDef(d) {} 1500844731a7f1909f55935e3514c9e713a62d67662eDan Gohman }; 1501844731a7f1909f55935e3514c9e713a62d67662eDan Gohman 1502844731a7f1909f55935e3514c9e713a62d67662eDan Gohman struct RewriteInfoCompare { 1503844731a7f1909f55935e3514c9e713a62d67662eDan Gohman bool operator()(const RewriteInfo &LHS, const RewriteInfo &RHS) const { 1504844731a7f1909f55935e3514c9e713a62d67662eDan Gohman return LHS.Index < RHS.Index; 1505844731a7f1909f55935e3514c9e713a62d67662eDan Gohman } 1506844731a7f1909f55935e3514c9e713a62d67662eDan Gohman }; 1507844731a7f1909f55935e3514c9e713a62d67662eDan Gohman} 1508063284c001666c0a3906acbe0a26dc7cae5f081cEvan Cheng 1509f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Chengvoid LiveIntervals:: 151081a038218171860ee4c382849c647d3dc841fe8bEvan ChengrewriteInstructionsForSpills(const LiveInterval &li, bool TrySplit, 1511f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng LiveInterval::Ranges::const_iterator &I, 151281a038218171860ee4c382849c647d3dc841fe8bEvan Cheng MachineInstr *ReMatOrigDefMI, MachineInstr *ReMatDefMI, 1513f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng unsigned Slot, int LdSlot, 1514f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng bool isLoad, bool isLoadSS, bool DefIsReMat, bool CanDelete, 1515d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng VirtRegMap &vrm, 1516f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng const TargetRegisterClass* rc, 1517f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng SmallVector<int, 4> &ReMatIds, 151822f07ffd27d1d721634d502c37267721d2e025cfEvan Cheng const MachineLoopInfo *loopInfo, 151981a038218171860ee4c382849c647d3dc841fe8bEvan Cheng BitVector &SpillMBBs, 1520289983123ba4170c8a27e9638935818f8142bc89Owen Anderson DenseMap<unsigned, std::vector<SRInfo> > &SpillIdxes, 15210cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng BitVector &RestoreMBBs, 1522289983123ba4170c8a27e9638935818f8142bc89Owen Anderson DenseMap<unsigned, std::vector<SRInfo> > &RestoreIdxes, 1523289983123ba4170c8a27e9638935818f8142bc89Owen Anderson DenseMap<unsigned,unsigned> &MBBVRegsMap, 1524c781a243a3d17e7e763515794168d8fa6043f565Evan Cheng std::vector<LiveInterval*> &NewLIs) { 1525018f9b020bb12b731b0a7081578e5f82fb35092dEvan Cheng bool AllCanFold = true; 152681a038218171860ee4c382849c647d3dc841fe8bEvan Cheng unsigned NewVReg = 0; 1527063284c001666c0a3906acbe0a26dc7cae5f081cEvan Cheng unsigned start = getBaseIndex(I->start); 1528f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng unsigned end = getBaseIndex(I->end-1) + InstrSlots::NUM; 1529f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng 1530063284c001666c0a3906acbe0a26dc7cae5f081cEvan Cheng // First collect all the def / use in this live range that will be rewritten. 15317e073baedb8232b9519dbe15ea141ff98ccfe6aeEvan Cheng // Make sure they are sorted according to instruction index. 1532063284c001666c0a3906acbe0a26dc7cae5f081cEvan Cheng std::vector<RewriteInfo> RewriteMIs; 1533d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng for (MachineRegisterInfo::reg_iterator ri = mri_->reg_begin(li.reg), 1534d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng re = mri_->reg_end(); ri != re; ) { 1535419852ca8a01aecde4c0e20af6b7bd6450e70f87Evan Cheng MachineInstr *MI = &*ri; 1536063284c001666c0a3906acbe0a26dc7cae5f081cEvan Cheng MachineOperand &O = ri.getOperand(); 1537063284c001666c0a3906acbe0a26dc7cae5f081cEvan Cheng ++ri; 153824d2f8a212f08bf21360122cc00acf2657af91f9Evan Cheng assert(!O.isImplicit() && "Spilling register that's used as implicit use?"); 1539063284c001666c0a3906acbe0a26dc7cae5f081cEvan Cheng unsigned index = getInstructionIndex(MI); 1540063284c001666c0a3906acbe0a26dc7cae5f081cEvan Cheng if (index < start || index >= end) 1541063284c001666c0a3906acbe0a26dc7cae5f081cEvan Cheng continue; 154279a796c2b17c7ebd4dd489b5de1078fc2148adbaEvan Cheng if (O.isUse() && !li.liveAt(getUseIndex(index))) 154379a796c2b17c7ebd4dd489b5de1078fc2148adbaEvan Cheng // Must be defined by an implicit def. It should not be spilled. Note, 154479a796c2b17c7ebd4dd489b5de1078fc2148adbaEvan Cheng // this is for correctness reason. e.g. 154579a796c2b17c7ebd4dd489b5de1078fc2148adbaEvan Cheng // 8 %reg1024<def> = IMPLICIT_DEF 154679a796c2b17c7ebd4dd489b5de1078fc2148adbaEvan Cheng // 12 %reg1024<def> = INSERT_SUBREG %reg1024<kill>, %reg1025, 2 154779a796c2b17c7ebd4dd489b5de1078fc2148adbaEvan Cheng // The live range [12, 14) are not part of the r1024 live interval since 154879a796c2b17c7ebd4dd489b5de1078fc2148adbaEvan Cheng // it's defined by an implicit def. It will not conflicts with live 154979a796c2b17c7ebd4dd489b5de1078fc2148adbaEvan Cheng // interval of r1025. Now suppose both registers are spilled, you can 1550b9890ae3c35ad7d8e49261650d5b98f49f97a705Evan Cheng // easily see a situation where both registers are reloaded before 155179a796c2b17c7ebd4dd489b5de1078fc2148adbaEvan Cheng // the INSERT_SUBREG and both target registers that would overlap. 155279a796c2b17c7ebd4dd489b5de1078fc2148adbaEvan Cheng continue; 1553063284c001666c0a3906acbe0a26dc7cae5f081cEvan Cheng RewriteMIs.push_back(RewriteInfo(index, MI, O.isUse(), O.isDef())); 1554063284c001666c0a3906acbe0a26dc7cae5f081cEvan Cheng } 1555063284c001666c0a3906acbe0a26dc7cae5f081cEvan Cheng std::sort(RewriteMIs.begin(), RewriteMIs.end(), RewriteInfoCompare()); 1556063284c001666c0a3906acbe0a26dc7cae5f081cEvan Cheng 1557313d4b809326f3e04814f94e5b8ae05649d8e0f6Evan Cheng unsigned ImpUse = DefIsReMat ? getReMatImplicitUse(li, ReMatDefMI) : 0; 1558063284c001666c0a3906acbe0a26dc7cae5f081cEvan Cheng // Now rewrite the defs and uses. 1559063284c001666c0a3906acbe0a26dc7cae5f081cEvan Cheng for (unsigned i = 0, e = RewriteMIs.size(); i != e; ) { 1560063284c001666c0a3906acbe0a26dc7cae5f081cEvan Cheng RewriteInfo &rwi = RewriteMIs[i]; 1561063284c001666c0a3906acbe0a26dc7cae5f081cEvan Cheng ++i; 1562063284c001666c0a3906acbe0a26dc7cae5f081cEvan Cheng unsigned index = rwi.Index; 1563063284c001666c0a3906acbe0a26dc7cae5f081cEvan Cheng bool MIHasUse = rwi.HasUse; 1564063284c001666c0a3906acbe0a26dc7cae5f081cEvan Cheng bool MIHasDef = rwi.HasDef; 1565063284c001666c0a3906acbe0a26dc7cae5f081cEvan Cheng MachineInstr *MI = rwi.MI; 1566063284c001666c0a3906acbe0a26dc7cae5f081cEvan Cheng // If MI def and/or use the same register multiple times, then there 1567063284c001666c0a3906acbe0a26dc7cae5f081cEvan Cheng // are multiple entries. 1568313d4b809326f3e04814f94e5b8ae05649d8e0f6Evan Cheng unsigned NumUses = MIHasUse; 1569063284c001666c0a3906acbe0a26dc7cae5f081cEvan Cheng while (i != e && RewriteMIs[i].MI == MI) { 1570063284c001666c0a3906acbe0a26dc7cae5f081cEvan Cheng assert(RewriteMIs[i].Index == index); 1571313d4b809326f3e04814f94e5b8ae05649d8e0f6Evan Cheng bool isUse = RewriteMIs[i].HasUse; 1572313d4b809326f3e04814f94e5b8ae05649d8e0f6Evan Cheng if (isUse) ++NumUses; 1573313d4b809326f3e04814f94e5b8ae05649d8e0f6Evan Cheng MIHasUse |= isUse; 1574063284c001666c0a3906acbe0a26dc7cae5f081cEvan Cheng MIHasDef |= RewriteMIs[i].HasDef; 1575063284c001666c0a3906acbe0a26dc7cae5f081cEvan Cheng ++i; 1576063284c001666c0a3906acbe0a26dc7cae5f081cEvan Cheng } 157781a038218171860ee4c382849c647d3dc841fe8bEvan Cheng MachineBasicBlock *MBB = MI->getParent(); 1578313d4b809326f3e04814f94e5b8ae05649d8e0f6Evan Cheng 15790a891ed7d5875a9ccdb93b4472b0f43947d8289bEvan Cheng if (ImpUse && MI != ReMatDefMI) { 1580313d4b809326f3e04814f94e5b8ae05649d8e0f6Evan Cheng // Re-matting an instruction with virtual register use. Update the 158124d2f8a212f08bf21360122cc00acf2657af91f9Evan Cheng // register interval's spill weight to HUGE_VALF to prevent it from 158224d2f8a212f08bf21360122cc00acf2657af91f9Evan Cheng // being spilled. 1583313d4b809326f3e04814f94e5b8ae05649d8e0f6Evan Cheng LiveInterval &ImpLi = getInterval(ImpUse); 158424d2f8a212f08bf21360122cc00acf2657af91f9Evan Cheng ImpLi.weight = HUGE_VALF; 1585313d4b809326f3e04814f94e5b8ae05649d8e0f6Evan Cheng } 1586313d4b809326f3e04814f94e5b8ae05649d8e0f6Evan Cheng 1587063284c001666c0a3906acbe0a26dc7cae5f081cEvan Cheng unsigned MBBId = MBB->getNumber(); 1588018f9b020bb12b731b0a7081578e5f82fb35092dEvan Cheng unsigned ThisVReg = 0; 158970306f8348f27c61cfed5a60e2fceac0f29746a2Evan Cheng if (TrySplit) { 1590289983123ba4170c8a27e9638935818f8142bc89Owen Anderson DenseMap<unsigned,unsigned>::iterator NVI = MBBVRegsMap.find(MBBId); 15911953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng if (NVI != MBBVRegsMap.end()) { 1592018f9b020bb12b731b0a7081578e5f82fb35092dEvan Cheng ThisVReg = NVI->second; 15931953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng // One common case: 15941953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng // x = use 15951953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng // ... 15961953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng // ... 15971953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng // def = ... 15981953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng // = use 15991953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng // It's better to start a new interval to avoid artifically 16001953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng // extend the new interval. 16011953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng if (MIHasDef && !MIHasUse) { 16021953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng MBBVRegsMap.erase(MBB->getNumber()); 1603018f9b020bb12b731b0a7081578e5f82fb35092dEvan Cheng ThisVReg = 0; 16041953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng } 16051953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng } 1606cada245d06959831b90f8c29f92e77beda4b71cbEvan Cheng } 1607018f9b020bb12b731b0a7081578e5f82fb35092dEvan Cheng 1608018f9b020bb12b731b0a7081578e5f82fb35092dEvan Cheng bool IsNew = ThisVReg == 0; 1609018f9b020bb12b731b0a7081578e5f82fb35092dEvan Cheng if (IsNew) { 1610018f9b020bb12b731b0a7081578e5f82fb35092dEvan Cheng // This ends the previous live interval. If all of its def / use 1611018f9b020bb12b731b0a7081578e5f82fb35092dEvan Cheng // can be folded, give it a low spill weight. 1612018f9b020bb12b731b0a7081578e5f82fb35092dEvan Cheng if (NewVReg && TrySplit && AllCanFold) { 1613018f9b020bb12b731b0a7081578e5f82fb35092dEvan Cheng LiveInterval &nI = getOrCreateInterval(NewVReg); 1614018f9b020bb12b731b0a7081578e5f82fb35092dEvan Cheng nI.weight /= 10.0F; 1615018f9b020bb12b731b0a7081578e5f82fb35092dEvan Cheng } 1616018f9b020bb12b731b0a7081578e5f82fb35092dEvan Cheng AllCanFold = true; 1617018f9b020bb12b731b0a7081578e5f82fb35092dEvan Cheng } 1618018f9b020bb12b731b0a7081578e5f82fb35092dEvan Cheng NewVReg = ThisVReg; 1619018f9b020bb12b731b0a7081578e5f82fb35092dEvan Cheng 162081a038218171860ee4c382849c647d3dc841fe8bEvan Cheng bool HasDef = false; 162181a038218171860ee4c382849c647d3dc841fe8bEvan Cheng bool HasUse = false; 1622d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng bool CanFold = rewriteInstructionForSpills(li, I->valno, TrySplit, 16239c3c2213647e3f1b71722d61875ebac01b65cb91Evan Cheng index, end, MI, ReMatOrigDefMI, ReMatDefMI, 16249c3c2213647e3f1b71722d61875ebac01b65cb91Evan Cheng Slot, LdSlot, isLoad, isLoadSS, DefIsReMat, 16259c3c2213647e3f1b71722d61875ebac01b65cb91Evan Cheng CanDelete, vrm, rc, ReMatIds, loopInfo, NewVReg, 1626c781a243a3d17e7e763515794168d8fa6043f565Evan Cheng ImpUse, HasDef, HasUse, MBBVRegsMap, NewLIs); 162781a038218171860ee4c382849c647d3dc841fe8bEvan Cheng if (!HasDef && !HasUse) 162881a038218171860ee4c382849c647d3dc841fe8bEvan Cheng continue; 162981a038218171860ee4c382849c647d3dc841fe8bEvan Cheng 1630018f9b020bb12b731b0a7081578e5f82fb35092dEvan Cheng AllCanFold &= CanFold; 1631018f9b020bb12b731b0a7081578e5f82fb35092dEvan Cheng 163281a038218171860ee4c382849c647d3dc841fe8bEvan Cheng // Update weight of spill interval. 163381a038218171860ee4c382849c647d3dc841fe8bEvan Cheng LiveInterval &nI = getOrCreateInterval(NewVReg); 163470306f8348f27c61cfed5a60e2fceac0f29746a2Evan Cheng if (!TrySplit) { 163581a038218171860ee4c382849c647d3dc841fe8bEvan Cheng // The spill weight is now infinity as it cannot be spilled again. 163681a038218171860ee4c382849c647d3dc841fe8bEvan Cheng nI.weight = HUGE_VALF; 16370cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng continue; 16380cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng } 16390cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng 16400cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng // Keep track of the last def and first use in each MBB. 16410cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng if (HasDef) { 16420cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng if (MI != ReMatOrigDefMI || !CanDelete) { 16430cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng bool HasKill = false; 16440cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng if (!HasUse) 16450cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng HasKill = anyKillInMBBAfterIdx(li, I->valno, MBB, getDefIndex(index)); 16460cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng else { 16471953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng // If this is a two-address code, then this index starts a new VNInfo. 16483f32d65912b4da23793dab618d981be2ce11c331Evan Cheng const VNInfo *VNI = li.findDefinedVNInfo(getDefIndex(index)); 16490cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng if (VNI) 16500cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng HasKill = anyKillInMBBAfterIdx(li, VNI, MBB, getDefIndex(index)); 165181a038218171860ee4c382849c647d3dc841fe8bEvan Cheng } 1652289983123ba4170c8a27e9638935818f8142bc89Owen Anderson DenseMap<unsigned, std::vector<SRInfo> >::iterator SII = 1653e3110d0825e6316fd2dd21d6a4e593295cd413f1Evan Cheng SpillIdxes.find(MBBId); 16540cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng if (!HasKill) { 16551953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng if (SII == SpillIdxes.end()) { 16561953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng std::vector<SRInfo> S; 16571953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng S.push_back(SRInfo(index, NewVReg, true)); 16581953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng SpillIdxes.insert(std::make_pair(MBBId, S)); 16591953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng } else if (SII->second.back().vreg != NewVReg) { 16601953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng SII->second.push_back(SRInfo(index, NewVReg, true)); 16611953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng } else if ((int)index > SII->second.back().index) { 16620cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng // If there is an earlier def and this is a two-address 16630cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng // instruction, then it's not possible to fold the store (which 16640cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng // would also fold the load). 16651953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng SRInfo &Info = SII->second.back(); 16661953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng Info.index = index; 16671953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng Info.canFold = !HasUse; 166881a038218171860ee4c382849c647d3dc841fe8bEvan Cheng } 16690cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng SpillMBBs.set(MBBId); 1670e3110d0825e6316fd2dd21d6a4e593295cd413f1Evan Cheng } else if (SII != SpillIdxes.end() && 1671e3110d0825e6316fd2dd21d6a4e593295cd413f1Evan Cheng SII->second.back().vreg == NewVReg && 1672e3110d0825e6316fd2dd21d6a4e593295cd413f1Evan Cheng (int)index > SII->second.back().index) { 1673e3110d0825e6316fd2dd21d6a4e593295cd413f1Evan Cheng // There is an earlier def that's not killed (must be two-address). 1674e3110d0825e6316fd2dd21d6a4e593295cd413f1Evan Cheng // The spill is no longer needed. 1675e3110d0825e6316fd2dd21d6a4e593295cd413f1Evan Cheng SII->second.pop_back(); 1676e3110d0825e6316fd2dd21d6a4e593295cd413f1Evan Cheng if (SII->second.empty()) { 1677e3110d0825e6316fd2dd21d6a4e593295cd413f1Evan Cheng SpillIdxes.erase(MBBId); 1678e3110d0825e6316fd2dd21d6a4e593295cd413f1Evan Cheng SpillMBBs.reset(MBBId); 1679e3110d0825e6316fd2dd21d6a4e593295cd413f1Evan Cheng } 168081a038218171860ee4c382849c647d3dc841fe8bEvan Cheng } 168181a038218171860ee4c382849c647d3dc841fe8bEvan Cheng } 16820cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng } 168381a038218171860ee4c382849c647d3dc841fe8bEvan Cheng 16840cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng if (HasUse) { 1685289983123ba4170c8a27e9638935818f8142bc89Owen Anderson DenseMap<unsigned, std::vector<SRInfo> >::iterator SII = 16860cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng SpillIdxes.find(MBBId); 16871953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng if (SII != SpillIdxes.end() && 16881953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng SII->second.back().vreg == NewVReg && 16891953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng (int)index > SII->second.back().index) 16900cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng // Use(s) following the last def, it's not safe to fold the spill. 16911953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng SII->second.back().canFold = false; 1692289983123ba4170c8a27e9638935818f8142bc89Owen Anderson DenseMap<unsigned, std::vector<SRInfo> >::iterator RII = 16930cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng RestoreIdxes.find(MBBId); 16941953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng if (RII != RestoreIdxes.end() && RII->second.back().vreg == NewVReg) 16950cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng // If we are splitting live intervals, only fold if it's the first 16960cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng // use and there isn't another use later in the MBB. 16971953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng RII->second.back().canFold = false; 16980cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng else if (IsNew) { 16990cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng // Only need a reload if there isn't an earlier def / use. 17001953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng if (RII == RestoreIdxes.end()) { 17011953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng std::vector<SRInfo> Infos; 17021953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng Infos.push_back(SRInfo(index, NewVReg, true)); 17031953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng RestoreIdxes.insert(std::make_pair(MBBId, Infos)); 17041953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng } else { 17051953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng RII->second.push_back(SRInfo(index, NewVReg, true)); 17061953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng } 17070cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng RestoreMBBs.set(MBBId); 17080cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng } 170981a038218171860ee4c382849c647d3dc841fe8bEvan Cheng } 17100cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng 17110cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng // Update spill weight. 171222f07ffd27d1d721634d502c37267721d2e025cfEvan Cheng unsigned loopDepth = loopInfo->getLoopDepth(MBB); 1713c3417609ae6e744a29be6962d4fb7811c0102d17Evan Cheng nI.weight += getSpillWeight(HasDef, HasUse, loopDepth); 1714f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng } 1715018f9b020bb12b731b0a7081578e5f82fb35092dEvan Cheng 1716018f9b020bb12b731b0a7081578e5f82fb35092dEvan Cheng if (NewVReg && TrySplit && AllCanFold) { 1717018f9b020bb12b731b0a7081578e5f82fb35092dEvan Cheng // If all of its def / use can be folded, give it a low spill weight. 1718018f9b020bb12b731b0a7081578e5f82fb35092dEvan Cheng LiveInterval &nI = getOrCreateInterval(NewVReg); 1719018f9b020bb12b731b0a7081578e5f82fb35092dEvan Cheng nI.weight /= 10.0F; 1720018f9b020bb12b731b0a7081578e5f82fb35092dEvan Cheng } 1721f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng} 1722f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng 17231953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Chengbool LiveIntervals::alsoFoldARestore(int Id, int index, unsigned vr, 17241953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng BitVector &RestoreMBBs, 1725289983123ba4170c8a27e9638935818f8142bc89Owen Anderson DenseMap<unsigned,std::vector<SRInfo> > &RestoreIdxes) { 17261953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng if (!RestoreMBBs[Id]) 17271953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng return false; 17281953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng std::vector<SRInfo> &Restores = RestoreIdxes[Id]; 17291953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng for (unsigned i = 0, e = Restores.size(); i != e; ++i) 17301953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng if (Restores[i].index == index && 17311953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng Restores[i].vreg == vr && 17321953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng Restores[i].canFold) 17331953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng return true; 17341953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng return false; 17351953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng} 17361953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng 17371953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Chengvoid LiveIntervals::eraseRestoreInfo(int Id, int index, unsigned vr, 17381953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng BitVector &RestoreMBBs, 1739289983123ba4170c8a27e9638935818f8142bc89Owen Anderson DenseMap<unsigned,std::vector<SRInfo> > &RestoreIdxes) { 17401953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng if (!RestoreMBBs[Id]) 17411953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng return; 17421953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng std::vector<SRInfo> &Restores = RestoreIdxes[Id]; 17431953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng for (unsigned i = 0, e = Restores.size(); i != e; ++i) 17441953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng if (Restores[i].index == index && Restores[i].vreg) 17451953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng Restores[i].index = -1; 17461953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng} 174781a038218171860ee4c382849c647d3dc841fe8bEvan Cheng 17484cce6b4c7882ef0cc993d931b90bf33985c96110Evan Cheng/// handleSpilledImpDefs - Remove IMPLICIT_DEF instructions which are being 17494cce6b4c7882ef0cc993d931b90bf33985c96110Evan Cheng/// spilled and create empty intervals for their uses. 17504cce6b4c7882ef0cc993d931b90bf33985c96110Evan Chengvoid 17514cce6b4c7882ef0cc993d931b90bf33985c96110Evan ChengLiveIntervals::handleSpilledImpDefs(const LiveInterval &li, VirtRegMap &vrm, 17524cce6b4c7882ef0cc993d931b90bf33985c96110Evan Cheng const TargetRegisterClass* rc, 17534cce6b4c7882ef0cc993d931b90bf33985c96110Evan Cheng std::vector<LiveInterval*> &NewLIs) { 1754419852ca8a01aecde4c0e20af6b7bd6450e70f87Evan Cheng for (MachineRegisterInfo::reg_iterator ri = mri_->reg_begin(li.reg), 1755419852ca8a01aecde4c0e20af6b7bd6450e70f87Evan Cheng re = mri_->reg_end(); ri != re; ) { 17564cce6b4c7882ef0cc993d931b90bf33985c96110Evan Cheng MachineOperand &O = ri.getOperand(); 1757419852ca8a01aecde4c0e20af6b7bd6450e70f87Evan Cheng MachineInstr *MI = &*ri; 1758419852ca8a01aecde4c0e20af6b7bd6450e70f87Evan Cheng ++ri; 17594cce6b4c7882ef0cc993d931b90bf33985c96110Evan Cheng if (O.isDef()) { 17604cce6b4c7882ef0cc993d931b90bf33985c96110Evan Cheng assert(MI->getOpcode() == TargetInstrInfo::IMPLICIT_DEF && 17614cce6b4c7882ef0cc993d931b90bf33985c96110Evan Cheng "Register def was not rewritten?"); 17624cce6b4c7882ef0cc993d931b90bf33985c96110Evan Cheng RemoveMachineInstrFromMaps(MI); 17634cce6b4c7882ef0cc993d931b90bf33985c96110Evan Cheng vrm.RemoveMachineInstrFromMaps(MI); 17644cce6b4c7882ef0cc993d931b90bf33985c96110Evan Cheng MI->eraseFromParent(); 17654cce6b4c7882ef0cc993d931b90bf33985c96110Evan Cheng } else { 17664cce6b4c7882ef0cc993d931b90bf33985c96110Evan Cheng // This must be an use of an implicit_def so it's not part of the live 17674cce6b4c7882ef0cc993d931b90bf33985c96110Evan Cheng // interval. Create a new empty live interval for it. 17684cce6b4c7882ef0cc993d931b90bf33985c96110Evan Cheng // FIXME: Can we simply erase some of the instructions? e.g. Stores? 17694cce6b4c7882ef0cc993d931b90bf33985c96110Evan Cheng unsigned NewVReg = mri_->createVirtualRegister(rc); 17704cce6b4c7882ef0cc993d931b90bf33985c96110Evan Cheng vrm.grow(); 17714cce6b4c7882ef0cc993d931b90bf33985c96110Evan Cheng vrm.setIsImplicitlyDefined(NewVReg); 17724cce6b4c7882ef0cc993d931b90bf33985c96110Evan Cheng NewLIs.push_back(&getOrCreateInterval(NewVReg)); 17734cce6b4c7882ef0cc993d931b90bf33985c96110Evan Cheng for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) { 17744cce6b4c7882ef0cc993d931b90bf33985c96110Evan Cheng MachineOperand &MO = MI->getOperand(i); 1775d735b8019b0f297d7c14b55adcd887af24d8e602Dan Gohman if (MO.isReg() && MO.getReg() == li.reg) 17764cce6b4c7882ef0cc993d931b90bf33985c96110Evan Cheng MO.setReg(NewVReg); 17774cce6b4c7882ef0cc993d931b90bf33985c96110Evan Cheng } 17784cce6b4c7882ef0cc993d931b90bf33985c96110Evan Cheng } 1779419852ca8a01aecde4c0e20af6b7bd6450e70f87Evan Cheng } 1780419852ca8a01aecde4c0e20af6b7bd6450e70f87Evan Cheng} 1781419852ca8a01aecde4c0e20af6b7bd6450e70f87Evan Cheng 1782f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Chengstd::vector<LiveInterval*> LiveIntervals:: 1783d6664311acbd05a8a710ccea8f9f5fdbfa35f834Owen AndersonaddIntervalsForSpillsFast(const LiveInterval &li, 1784d6664311acbd05a8a710ccea8f9f5fdbfa35f834Owen Anderson const MachineLoopInfo *loopInfo, 1785c781a243a3d17e7e763515794168d8fa6043f565Evan Cheng VirtRegMap &vrm) { 17861719731d3d8ab6a986d67912f35daaad4f6910dbOwen Anderson unsigned slot = vrm.assignVirt2StackSlot(li.reg); 1787d6664311acbd05a8a710ccea8f9f5fdbfa35f834Owen Anderson 1788d6664311acbd05a8a710ccea8f9f5fdbfa35f834Owen Anderson std::vector<LiveInterval*> added; 1789d6664311acbd05a8a710ccea8f9f5fdbfa35f834Owen Anderson 1790d6664311acbd05a8a710ccea8f9f5fdbfa35f834Owen Anderson assert(li.weight != HUGE_VALF && 1791d6664311acbd05a8a710ccea8f9f5fdbfa35f834Owen Anderson "attempt to spill already spilled interval!"); 1792d6664311acbd05a8a710ccea8f9f5fdbfa35f834Owen Anderson 1793d6664311acbd05a8a710ccea8f9f5fdbfa35f834Owen Anderson DOUT << "\t\t\t\tadding intervals for spills for interval: "; 1794d6664311acbd05a8a710ccea8f9f5fdbfa35f834Owen Anderson DEBUG(li.dump()); 1795d6664311acbd05a8a710ccea8f9f5fdbfa35f834Owen Anderson DOUT << '\n'; 1796d6664311acbd05a8a710ccea8f9f5fdbfa35f834Owen Anderson 1797d6664311acbd05a8a710ccea8f9f5fdbfa35f834Owen Anderson const TargetRegisterClass* rc = mri_->getRegClass(li.reg); 1798d6664311acbd05a8a710ccea8f9f5fdbfa35f834Owen Anderson 1799a41e47afc19d2beb741edae16e3918aadade325dOwen Anderson MachineRegisterInfo::reg_iterator RI = mri_->reg_begin(li.reg); 1800a41e47afc19d2beb741edae16e3918aadade325dOwen Anderson while (RI != mri_->reg_end()) { 1801a41e47afc19d2beb741edae16e3918aadade325dOwen Anderson MachineInstr* MI = &*RI; 18028dc2cbe793ff577f69c17426d6dfaef94ad69191Owen Anderson 1803a41e47afc19d2beb741edae16e3918aadade325dOwen Anderson SmallVector<unsigned, 2> Indices; 1804a41e47afc19d2beb741edae16e3918aadade325dOwen Anderson bool HasUse = false; 1805a41e47afc19d2beb741edae16e3918aadade325dOwen Anderson bool HasDef = false; 18068dc2cbe793ff577f69c17426d6dfaef94ad69191Owen Anderson 1807a41e47afc19d2beb741edae16e3918aadade325dOwen Anderson for (unsigned i = 0; i != MI->getNumOperands(); ++i) { 1808a41e47afc19d2beb741edae16e3918aadade325dOwen Anderson MachineOperand& mop = MI->getOperand(i); 1809d735b8019b0f297d7c14b55adcd887af24d8e602Dan Gohman if (!mop.isReg() || mop.getReg() != li.reg) continue; 1810a41e47afc19d2beb741edae16e3918aadade325dOwen Anderson 1811a41e47afc19d2beb741edae16e3918aadade325dOwen Anderson HasUse |= MI->getOperand(i).isUse(); 1812a41e47afc19d2beb741edae16e3918aadade325dOwen Anderson HasDef |= MI->getOperand(i).isDef(); 1813a41e47afc19d2beb741edae16e3918aadade325dOwen Anderson 1814a41e47afc19d2beb741edae16e3918aadade325dOwen Anderson Indices.push_back(i); 1815d6664311acbd05a8a710ccea8f9f5fdbfa35f834Owen Anderson } 18161719731d3d8ab6a986d67912f35daaad4f6910dbOwen Anderson 1817a41e47afc19d2beb741edae16e3918aadade325dOwen Anderson if (!tryFoldMemoryOperand(MI, vrm, NULL, getInstructionIndex(MI), 1818a41e47afc19d2beb741edae16e3918aadade325dOwen Anderson Indices, true, slot, li.reg)) { 1819a41e47afc19d2beb741edae16e3918aadade325dOwen Anderson unsigned NewVReg = mri_->createVirtualRegister(rc); 1820a41e47afc19d2beb741edae16e3918aadade325dOwen Anderson vrm.grow(); 1821a41e47afc19d2beb741edae16e3918aadade325dOwen Anderson vrm.assignVirt2StackSlot(NewVReg, slot); 1822a41e47afc19d2beb741edae16e3918aadade325dOwen Anderson 1823a41e47afc19d2beb741edae16e3918aadade325dOwen Anderson // create a new register for this spill 1824a41e47afc19d2beb741edae16e3918aadade325dOwen Anderson LiveInterval &nI = getOrCreateInterval(NewVReg); 1825a41e47afc19d2beb741edae16e3918aadade325dOwen Anderson 1826a41e47afc19d2beb741edae16e3918aadade325dOwen Anderson // the spill weight is now infinity as it 1827a41e47afc19d2beb741edae16e3918aadade325dOwen Anderson // cannot be spilled again 1828a41e47afc19d2beb741edae16e3918aadade325dOwen Anderson nI.weight = HUGE_VALF; 1829a41e47afc19d2beb741edae16e3918aadade325dOwen Anderson 1830a41e47afc19d2beb741edae16e3918aadade325dOwen Anderson // Rewrite register operands to use the new vreg. 1831a41e47afc19d2beb741edae16e3918aadade325dOwen Anderson for (SmallVectorImpl<unsigned>::iterator I = Indices.begin(), 1832a41e47afc19d2beb741edae16e3918aadade325dOwen Anderson E = Indices.end(); I != E; ++I) { 1833a41e47afc19d2beb741edae16e3918aadade325dOwen Anderson MI->getOperand(*I).setReg(NewVReg); 1834a41e47afc19d2beb741edae16e3918aadade325dOwen Anderson 1835a41e47afc19d2beb741edae16e3918aadade325dOwen Anderson if (MI->getOperand(*I).isUse()) 1836a41e47afc19d2beb741edae16e3918aadade325dOwen Anderson MI->getOperand(*I).setIsKill(true); 1837a41e47afc19d2beb741edae16e3918aadade325dOwen Anderson } 1838a41e47afc19d2beb741edae16e3918aadade325dOwen Anderson 1839a41e47afc19d2beb741edae16e3918aadade325dOwen Anderson // Fill in the new live interval. 1840a41e47afc19d2beb741edae16e3918aadade325dOwen Anderson unsigned index = getInstructionIndex(MI); 1841a41e47afc19d2beb741edae16e3918aadade325dOwen Anderson if (HasUse) { 1842a41e47afc19d2beb741edae16e3918aadade325dOwen Anderson LiveRange LR(getLoadIndex(index), getUseIndex(index), 1843a41e47afc19d2beb741edae16e3918aadade325dOwen Anderson nI.getNextValue(~0U, 0, getVNInfoAllocator())); 1844a41e47afc19d2beb741edae16e3918aadade325dOwen Anderson DOUT << " +" << LR; 1845a41e47afc19d2beb741edae16e3918aadade325dOwen Anderson nI.addRange(LR); 1846a41e47afc19d2beb741edae16e3918aadade325dOwen Anderson vrm.addRestorePoint(NewVReg, MI); 1847a41e47afc19d2beb741edae16e3918aadade325dOwen Anderson } 1848a41e47afc19d2beb741edae16e3918aadade325dOwen Anderson if (HasDef) { 1849a41e47afc19d2beb741edae16e3918aadade325dOwen Anderson LiveRange LR(getDefIndex(index), getStoreIndex(index), 1850a41e47afc19d2beb741edae16e3918aadade325dOwen Anderson nI.getNextValue(~0U, 0, getVNInfoAllocator())); 1851a41e47afc19d2beb741edae16e3918aadade325dOwen Anderson DOUT << " +" << LR; 1852a41e47afc19d2beb741edae16e3918aadade325dOwen Anderson nI.addRange(LR); 1853a41e47afc19d2beb741edae16e3918aadade325dOwen Anderson vrm.addSpillPoint(NewVReg, true, MI); 1854a41e47afc19d2beb741edae16e3918aadade325dOwen Anderson } 1855a41e47afc19d2beb741edae16e3918aadade325dOwen Anderson 18561719731d3d8ab6a986d67912f35daaad4f6910dbOwen Anderson added.push_back(&nI); 18578dc2cbe793ff577f69c17426d6dfaef94ad69191Owen Anderson 1858a41e47afc19d2beb741edae16e3918aadade325dOwen Anderson DOUT << "\t\t\t\tadded new interval: "; 1859a41e47afc19d2beb741edae16e3918aadade325dOwen Anderson DEBUG(nI.dump()); 1860a41e47afc19d2beb741edae16e3918aadade325dOwen Anderson DOUT << '\n'; 1861a41e47afc19d2beb741edae16e3918aadade325dOwen Anderson } 18629a032931453209505f6765a35be108ae5ea39b3bOwen Anderson 18639a032931453209505f6765a35be108ae5ea39b3bOwen Anderson 1864a41e47afc19d2beb741edae16e3918aadade325dOwen Anderson RI = mri_->reg_begin(li.reg); 1865d6664311acbd05a8a710ccea8f9f5fdbfa35f834Owen Anderson } 1866d6664311acbd05a8a710ccea8f9f5fdbfa35f834Owen Anderson 1867d6664311acbd05a8a710ccea8f9f5fdbfa35f834Owen Anderson return added; 1868d6664311acbd05a8a710ccea8f9f5fdbfa35f834Owen Anderson} 1869d6664311acbd05a8a710ccea8f9f5fdbfa35f834Owen Anderson 1870d6664311acbd05a8a710ccea8f9f5fdbfa35f834Owen Andersonstd::vector<LiveInterval*> LiveIntervals:: 187181a038218171860ee4c382849c647d3dc841fe8bEvan ChengaddIntervalsForSpills(const LiveInterval &li, 1872dc37786595beedd0a68d8e2cbd91ae53ad58d133Evan Cheng SmallVectorImpl<LiveInterval*> &SpillIs, 1873c781a243a3d17e7e763515794168d8fa6043f565Evan Cheng const MachineLoopInfo *loopInfo, VirtRegMap &vrm) { 1874ae339babb2a2445e7bb009912a39994718f10d54Owen Anderson 1875ae339babb2a2445e7bb009912a39994718f10d54Owen Anderson if (EnableFastSpilling) 1876c781a243a3d17e7e763515794168d8fa6043f565Evan Cheng return addIntervalsForSpillsFast(li, loopInfo, vrm); 1877ae339babb2a2445e7bb009912a39994718f10d54Owen Anderson 1878f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng assert(li.weight != HUGE_VALF && 1879f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng "attempt to spill already spilled interval!"); 1880f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng 1881f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng DOUT << "\t\t\t\tadding intervals for spills for interval: "; 18826f0d024a534af18d9e60b3ea757376cd8a3a980eDan Gohman li.print(DOUT, tri_); 1883f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng DOUT << '\n'; 1884f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng 188572eeb94fe1d69cd05bdbbe86b2bc9fa25c963c22Evan Cheng // Each bit specify whether a spill is required in the MBB. 188681a038218171860ee4c382849c647d3dc841fe8bEvan Cheng BitVector SpillMBBs(mf_->getNumBlockIDs()); 1887289983123ba4170c8a27e9638935818f8142bc89Owen Anderson DenseMap<unsigned, std::vector<SRInfo> > SpillIdxes; 18880cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng BitVector RestoreMBBs(mf_->getNumBlockIDs()); 1889289983123ba4170c8a27e9638935818f8142bc89Owen Anderson DenseMap<unsigned, std::vector<SRInfo> > RestoreIdxes; 1890289983123ba4170c8a27e9638935818f8142bc89Owen Anderson DenseMap<unsigned,unsigned> MBBVRegsMap; 1891f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng std::vector<LiveInterval*> NewLIs; 1892d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng const TargetRegisterClass* rc = mri_->getRegClass(li.reg); 1893f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng 1894f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng unsigned NumValNums = li.getNumValNums(); 1895f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng SmallVector<MachineInstr*, 4> ReMatDefs; 1896f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng ReMatDefs.resize(NumValNums, NULL); 1897f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng SmallVector<MachineInstr*, 4> ReMatOrigDefs; 1898f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng ReMatOrigDefs.resize(NumValNums, NULL); 1899f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng SmallVector<int, 4> ReMatIds; 1900f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng ReMatIds.resize(NumValNums, VirtRegMap::MAX_STACK_SLOT); 1901f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng BitVector ReMatDelete(NumValNums); 1902f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng unsigned Slot = VirtRegMap::MAX_STACK_SLOT; 1903f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng 190481a038218171860ee4c382849c647d3dc841fe8bEvan Cheng // Spilling a split live interval. It cannot be split any further. Also, 190581a038218171860ee4c382849c647d3dc841fe8bEvan Cheng // it's also guaranteed to be a single val# / range interval. 190681a038218171860ee4c382849c647d3dc841fe8bEvan Cheng if (vrm.getPreSplitReg(li.reg)) { 190781a038218171860ee4c382849c647d3dc841fe8bEvan Cheng vrm.setIsSplitFromReg(li.reg, 0); 1908d120ffd26f2715c600b028d4eac9a3c41a9f4653Evan Cheng // Unset the split kill marker on the last use. 1909d120ffd26f2715c600b028d4eac9a3c41a9f4653Evan Cheng unsigned KillIdx = vrm.getKillPoint(li.reg); 1910d120ffd26f2715c600b028d4eac9a3c41a9f4653Evan Cheng if (KillIdx) { 1911d120ffd26f2715c600b028d4eac9a3c41a9f4653Evan Cheng MachineInstr *KillMI = getInstructionFromIndex(KillIdx); 1912d120ffd26f2715c600b028d4eac9a3c41a9f4653Evan Cheng assert(KillMI && "Last use disappeared?"); 1913d120ffd26f2715c600b028d4eac9a3c41a9f4653Evan Cheng int KillOp = KillMI->findRegisterUseOperandIdx(li.reg, true); 1914d120ffd26f2715c600b028d4eac9a3c41a9f4653Evan Cheng assert(KillOp != -1 && "Last use disappeared?"); 1915f73823000e2d5d6e1cf65bdf5a107297e18d35fbChris Lattner KillMI->getOperand(KillOp).setIsKill(false); 1916d120ffd26f2715c600b028d4eac9a3c41a9f4653Evan Cheng } 1917adf85906906ebf85c57c333e8209f37ef11a6c99Evan Cheng vrm.removeKillPoint(li.reg); 191881a038218171860ee4c382849c647d3dc841fe8bEvan Cheng bool DefIsReMat = vrm.isReMaterialized(li.reg); 191981a038218171860ee4c382849c647d3dc841fe8bEvan Cheng Slot = vrm.getStackSlot(li.reg); 192081a038218171860ee4c382849c647d3dc841fe8bEvan Cheng assert(Slot != VirtRegMap::MAX_STACK_SLOT); 192181a038218171860ee4c382849c647d3dc841fe8bEvan Cheng MachineInstr *ReMatDefMI = DefIsReMat ? 192281a038218171860ee4c382849c647d3dc841fe8bEvan Cheng vrm.getReMaterializedMI(li.reg) : NULL; 192381a038218171860ee4c382849c647d3dc841fe8bEvan Cheng int LdSlot = 0; 192481a038218171860ee4c382849c647d3dc841fe8bEvan Cheng bool isLoadSS = DefIsReMat && tii_->isLoadFromStackSlot(ReMatDefMI, LdSlot); 192581a038218171860ee4c382849c647d3dc841fe8bEvan Cheng bool isLoad = isLoadSS || 192615511cf1660cfd6bb8b8e8fca2db9450f50430eeDan Gohman (DefIsReMat && (ReMatDefMI->getDesc().canFoldAsLoad())); 192781a038218171860ee4c382849c647d3dc841fe8bEvan Cheng bool IsFirstRange = true; 192881a038218171860ee4c382849c647d3dc841fe8bEvan Cheng for (LiveInterval::Ranges::const_iterator 192981a038218171860ee4c382849c647d3dc841fe8bEvan Cheng I = li.ranges.begin(), E = li.ranges.end(); I != E; ++I) { 193081a038218171860ee4c382849c647d3dc841fe8bEvan Cheng // If this is a split live interval with multiple ranges, it means there 193181a038218171860ee4c382849c647d3dc841fe8bEvan Cheng // are two-address instructions that re-defined the value. Only the 193281a038218171860ee4c382849c647d3dc841fe8bEvan Cheng // first def can be rematerialized! 193381a038218171860ee4c382849c647d3dc841fe8bEvan Cheng if (IsFirstRange) { 1934cb3c330d39442130d0587208d673ce9c33c7008fEvan Cheng // Note ReMatOrigDefMI has already been deleted. 193581a038218171860ee4c382849c647d3dc841fe8bEvan Cheng rewriteInstructionsForSpills(li, false, I, NULL, ReMatDefMI, 193681a038218171860ee4c382849c647d3dc841fe8bEvan Cheng Slot, LdSlot, isLoad, isLoadSS, DefIsReMat, 1937d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng false, vrm, rc, ReMatIds, loopInfo, 19380cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng SpillMBBs, SpillIdxes, RestoreMBBs, RestoreIdxes, 1939c781a243a3d17e7e763515794168d8fa6043f565Evan Cheng MBBVRegsMap, NewLIs); 194081a038218171860ee4c382849c647d3dc841fe8bEvan Cheng } else { 194181a038218171860ee4c382849c647d3dc841fe8bEvan Cheng rewriteInstructionsForSpills(li, false, I, NULL, 0, 194281a038218171860ee4c382849c647d3dc841fe8bEvan Cheng Slot, 0, false, false, false, 1943d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng false, vrm, rc, ReMatIds, loopInfo, 19440cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng SpillMBBs, SpillIdxes, RestoreMBBs, RestoreIdxes, 1945c781a243a3d17e7e763515794168d8fa6043f565Evan Cheng MBBVRegsMap, NewLIs); 194681a038218171860ee4c382849c647d3dc841fe8bEvan Cheng } 194781a038218171860ee4c382849c647d3dc841fe8bEvan Cheng IsFirstRange = false; 194881a038218171860ee4c382849c647d3dc841fe8bEvan Cheng } 1949419852ca8a01aecde4c0e20af6b7bd6450e70f87Evan Cheng 19504cce6b4c7882ef0cc993d931b90bf33985c96110Evan Cheng handleSpilledImpDefs(li, vrm, rc, NewLIs); 195181a038218171860ee4c382849c647d3dc841fe8bEvan Cheng return NewLIs; 195281a038218171860ee4c382849c647d3dc841fe8bEvan Cheng } 195381a038218171860ee4c382849c647d3dc841fe8bEvan Cheng 195481a038218171860ee4c382849c647d3dc841fe8bEvan Cheng bool TrySplit = SplitAtBB && !intervalIsInOneMBB(li); 19550cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng if (SplitLimit != -1 && (int)numSplits >= SplitLimit) 19560cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng TrySplit = false; 19570cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng if (TrySplit) 19580cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng ++numSplits; 1959f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng bool NeedStackSlot = false; 1960f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng for (LiveInterval::const_vni_iterator i = li.vni_begin(), e = li.vni_end(); 1961f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng i != e; ++i) { 1962f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng const VNInfo *VNI = *i; 1963f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng unsigned VN = VNI->id; 1964f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng unsigned DefIdx = VNI->def; 1965f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng if (DefIdx == ~1U) 1966f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng continue; // Dead val#. 1967f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng // Is the def for the val# rematerializable? 196881a038218171860ee4c382849c647d3dc841fe8bEvan Cheng MachineInstr *ReMatDefMI = (DefIdx == ~0u) 196981a038218171860ee4c382849c647d3dc841fe8bEvan Cheng ? 0 : getInstructionFromIndex(DefIdx); 19705ef3a04b542c4e585276768fa9ca2af698ef5c87Evan Cheng bool dummy; 1971dc37786595beedd0a68d8e2cbd91ae53ad58d133Evan Cheng if (ReMatDefMI && isReMaterializable(li, VNI, ReMatDefMI, SpillIs, dummy)) { 1972f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng // Remember how to remat the def of this val#. 197381a038218171860ee4c382849c647d3dc841fe8bEvan Cheng ReMatOrigDefs[VN] = ReMatDefMI; 19742c3f7ae3843bdc9dcfe85393e178211976c1f9bdDan Gohman // Original def may be modified so we have to make a copy here. 19751ed9922794cda9dbe295e74674b909287e544632Evan Cheng MachineInstr *Clone = mf_->CloneMachineInstr(ReMatDefMI); 19761ed9922794cda9dbe295e74674b909287e544632Evan Cheng ClonedMIs.push_back(Clone); 19771ed9922794cda9dbe295e74674b909287e544632Evan Cheng ReMatDefs[VN] = Clone; 1978f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng 1979f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng bool CanDelete = true; 1980c3fc7d9ec9b495c8a88cd854247105c296d3aabdEvan Cheng if (VNI->hasPHIKill) { 1981c3fc7d9ec9b495c8a88cd854247105c296d3aabdEvan Cheng // A kill is a phi node, not all of its uses can be rematerialized. 1982f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng // It must not be deleted. 1983c3fc7d9ec9b495c8a88cd854247105c296d3aabdEvan Cheng CanDelete = false; 1984c3fc7d9ec9b495c8a88cd854247105c296d3aabdEvan Cheng // Need a stack slot if there is any live range where uses cannot be 1985c3fc7d9ec9b495c8a88cd854247105c296d3aabdEvan Cheng // rematerialized. 1986c3fc7d9ec9b495c8a88cd854247105c296d3aabdEvan Cheng NeedStackSlot = true; 1987f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng } 1988f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng if (CanDelete) 1989f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng ReMatDelete.set(VN); 1990f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng } else { 1991f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng // Need a stack slot if there is any live range where uses cannot be 1992f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng // rematerialized. 1993f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng NeedStackSlot = true; 1994f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng } 1995f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng } 1996f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng 1997f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng // One stack slot per live interval. 1998b98bbb7597495fb401b020679a94389298175506Owen Anderson if (NeedStackSlot && vrm.getPreSplitReg(li.reg) == 0) { 1999b98bbb7597495fb401b020679a94389298175506Owen Anderson if (vrm.getStackSlot(li.reg) == VirtRegMap::NO_STACK_SLOT) 2000b98bbb7597495fb401b020679a94389298175506Owen Anderson Slot = vrm.assignVirt2StackSlot(li.reg); 2001b98bbb7597495fb401b020679a94389298175506Owen Anderson 2002b98bbb7597495fb401b020679a94389298175506Owen Anderson // This case only occurs when the prealloc splitter has already assigned 2003b98bbb7597495fb401b020679a94389298175506Owen Anderson // a stack slot to this vreg. 2004b98bbb7597495fb401b020679a94389298175506Owen Anderson else 2005b98bbb7597495fb401b020679a94389298175506Owen Anderson Slot = vrm.getStackSlot(li.reg); 2006b98bbb7597495fb401b020679a94389298175506Owen Anderson } 2007f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng 2008f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng // Create new intervals and rewrite defs and uses. 2009f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng for (LiveInterval::Ranges::const_iterator 2010f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng I = li.ranges.begin(), E = li.ranges.end(); I != E; ++I) { 201181a038218171860ee4c382849c647d3dc841fe8bEvan Cheng MachineInstr *ReMatDefMI = ReMatDefs[I->valno->id]; 201281a038218171860ee4c382849c647d3dc841fe8bEvan Cheng MachineInstr *ReMatOrigDefMI = ReMatOrigDefs[I->valno->id]; 201381a038218171860ee4c382849c647d3dc841fe8bEvan Cheng bool DefIsReMat = ReMatDefMI != NULL; 2014f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng bool CanDelete = ReMatDelete[I->valno->id]; 2015f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng int LdSlot = 0; 201681a038218171860ee4c382849c647d3dc841fe8bEvan Cheng bool isLoadSS = DefIsReMat && tii_->isLoadFromStackSlot(ReMatDefMI, LdSlot); 2017f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng bool isLoad = isLoadSS || 201815511cf1660cfd6bb8b8e8fca2db9450f50430eeDan Gohman (DefIsReMat && ReMatDefMI->getDesc().canFoldAsLoad()); 201981a038218171860ee4c382849c647d3dc841fe8bEvan Cheng rewriteInstructionsForSpills(li, TrySplit, I, ReMatOrigDefMI, ReMatDefMI, 20200cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng Slot, LdSlot, isLoad, isLoadSS, DefIsReMat, 2021d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng CanDelete, vrm, rc, ReMatIds, loopInfo, 20220cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng SpillMBBs, SpillIdxes, RestoreMBBs, RestoreIdxes, 2023c781a243a3d17e7e763515794168d8fa6043f565Evan Cheng MBBVRegsMap, NewLIs); 2024f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng } 2025f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng 20260cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng // Insert spills / restores if we are splitting. 2027419852ca8a01aecde4c0e20af6b7bd6450e70f87Evan Cheng if (!TrySplit) { 20284cce6b4c7882ef0cc993d931b90bf33985c96110Evan Cheng handleSpilledImpDefs(li, vrm, rc, NewLIs); 20291953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng return NewLIs; 2030419852ca8a01aecde4c0e20af6b7bd6450e70f87Evan Cheng } 20311953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng 2032b50bb8cf197709b3f49044740044c06d8f314564Evan Cheng SmallPtrSet<LiveInterval*, 4> AddedKill; 2033aee4af68ae2016afc5b4ec0c430e539c5810a766Evan Cheng SmallVector<unsigned, 2> Ops; 20341953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng if (NeedStackSlot) { 20351953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng int Id = SpillMBBs.find_first(); 20361953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng while (Id != -1) { 20371953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng std::vector<SRInfo> &spills = SpillIdxes[Id]; 20381953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng for (unsigned i = 0, e = spills.size(); i != e; ++i) { 20391953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng int index = spills[i].index; 20401953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng unsigned VReg = spills[i].vreg; 2041597d10d84fb6b34f7776121404d5ed802b21b2b6Evan Cheng LiveInterval &nI = getOrCreateInterval(VReg); 20420cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng bool isReMat = vrm.isReMaterialized(VReg); 20430cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng MachineInstr *MI = getInstructionFromIndex(index); 2044aee4af68ae2016afc5b4ec0c430e539c5810a766Evan Cheng bool CanFold = false; 2045aee4af68ae2016afc5b4ec0c430e539c5810a766Evan Cheng bool FoundUse = false; 2046aee4af68ae2016afc5b4ec0c430e539c5810a766Evan Cheng Ops.clear(); 2047cddbb83ea82e98658d9f530c50a7b9d23249afc2Evan Cheng if (spills[i].canFold) { 2048aee4af68ae2016afc5b4ec0c430e539c5810a766Evan Cheng CanFold = true; 20490cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng for (unsigned j = 0, ee = MI->getNumOperands(); j != ee; ++j) { 20500cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng MachineOperand &MO = MI->getOperand(j); 2051d735b8019b0f297d7c14b55adcd887af24d8e602Dan Gohman if (!MO.isReg() || MO.getReg() != VReg) 20520cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng continue; 2053aee4af68ae2016afc5b4ec0c430e539c5810a766Evan Cheng 2054aee4af68ae2016afc5b4ec0c430e539c5810a766Evan Cheng Ops.push_back(j); 2055aee4af68ae2016afc5b4ec0c430e539c5810a766Evan Cheng if (MO.isDef()) 2056cddbb83ea82e98658d9f530c50a7b9d23249afc2Evan Cheng continue; 2057aee4af68ae2016afc5b4ec0c430e539c5810a766Evan Cheng if (isReMat || 2058aee4af68ae2016afc5b4ec0c430e539c5810a766Evan Cheng (!FoundUse && !alsoFoldARestore(Id, index, VReg, 2059aee4af68ae2016afc5b4ec0c430e539c5810a766Evan Cheng RestoreMBBs, RestoreIdxes))) { 2060aee4af68ae2016afc5b4ec0c430e539c5810a766Evan Cheng // MI has two-address uses of the same register. If the use 2061aee4af68ae2016afc5b4ec0c430e539c5810a766Evan Cheng // isn't the first and only use in the BB, then we can't fold 2062aee4af68ae2016afc5b4ec0c430e539c5810a766Evan Cheng // it. FIXME: Move this to rewriteInstructionsForSpills. 2063aee4af68ae2016afc5b4ec0c430e539c5810a766Evan Cheng CanFold = false; 2064cddbb83ea82e98658d9f530c50a7b9d23249afc2Evan Cheng break; 2065cddbb83ea82e98658d9f530c50a7b9d23249afc2Evan Cheng } 2066aee4af68ae2016afc5b4ec0c430e539c5810a766Evan Cheng FoundUse = true; 20670cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng } 20680cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng } 20690cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng // Fold the store into the def if possible. 2070cddbb83ea82e98658d9f530c50a7b9d23249afc2Evan Cheng bool Folded = false; 2071aee4af68ae2016afc5b4ec0c430e539c5810a766Evan Cheng if (CanFold && !Ops.empty()) { 2072aee4af68ae2016afc5b4ec0c430e539c5810a766Evan Cheng if (tryFoldMemoryOperand(MI, vrm, NULL, index, Ops, true, Slot,VReg)){ 2073cddbb83ea82e98658d9f530c50a7b9d23249afc2Evan Cheng Folded = true; 207448fe63526e35ddaee7e98879596a569911f41319Sebastian Redl if (FoundUse) { 2075aee4af68ae2016afc5b4ec0c430e539c5810a766Evan Cheng // Also folded uses, do not issue a load. 2076aee4af68ae2016afc5b4ec0c430e539c5810a766Evan Cheng eraseRestoreInfo(Id, index, VReg, RestoreMBBs, RestoreIdxes); 2077f38d14f03e495ea98ae16bda6febbde276513294Evan Cheng nI.removeRange(getLoadIndex(index), getUseIndex(index)+1); 2078f38d14f03e495ea98ae16bda6febbde276513294Evan Cheng } 2079597d10d84fb6b34f7776121404d5ed802b21b2b6Evan Cheng nI.removeRange(getDefIndex(index), getStoreIndex(index)); 2080cddbb83ea82e98658d9f530c50a7b9d23249afc2Evan Cheng } 20810cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng } 20820cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng 20837e073baedb8232b9519dbe15ea141ff98ccfe6aeEvan Cheng // Otherwise tell the spiller to issue a spill. 2084b50bb8cf197709b3f49044740044c06d8f314564Evan Cheng if (!Folded) { 2085b50bb8cf197709b3f49044740044c06d8f314564Evan Cheng LiveRange *LR = &nI.ranges[nI.ranges.size()-1]; 2086b50bb8cf197709b3f49044740044c06d8f314564Evan Cheng bool isKill = LR->end == getStoreIndex(index); 2087b0a6f62c9b2e75fc509d84310a9795ffacbc6796Evan Cheng if (!MI->registerDefIsDead(nI.reg)) 2088b0a6f62c9b2e75fc509d84310a9795ffacbc6796Evan Cheng // No need to spill a dead def. 2089b0a6f62c9b2e75fc509d84310a9795ffacbc6796Evan Cheng vrm.addSpillPoint(VReg, isKill, MI); 2090b50bb8cf197709b3f49044740044c06d8f314564Evan Cheng if (isKill) 2091b50bb8cf197709b3f49044740044c06d8f314564Evan Cheng AddedKill.insert(&nI); 2092b50bb8cf197709b3f49044740044c06d8f314564Evan Cheng } 20930cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng } 20941953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng Id = SpillMBBs.find_next(Id); 20950cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng } 20961953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng } 20970cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng 20981953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng int Id = RestoreMBBs.find_first(); 20991953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng while (Id != -1) { 21001953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng std::vector<SRInfo> &restores = RestoreIdxes[Id]; 21011953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng for (unsigned i = 0, e = restores.size(); i != e; ++i) { 21021953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng int index = restores[i].index; 21031953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng if (index == -1) 21041953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng continue; 21051953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng unsigned VReg = restores[i].vreg; 2106597d10d84fb6b34f7776121404d5ed802b21b2b6Evan Cheng LiveInterval &nI = getOrCreateInterval(VReg); 21079c3c2213647e3f1b71722d61875ebac01b65cb91Evan Cheng bool isReMat = vrm.isReMaterialized(VReg); 210881a038218171860ee4c382849c647d3dc841fe8bEvan Cheng MachineInstr *MI = getInstructionFromIndex(index); 2109aee4af68ae2016afc5b4ec0c430e539c5810a766Evan Cheng bool CanFold = false; 2110aee4af68ae2016afc5b4ec0c430e539c5810a766Evan Cheng Ops.clear(); 2111cddbb83ea82e98658d9f530c50a7b9d23249afc2Evan Cheng if (restores[i].canFold) { 2112aee4af68ae2016afc5b4ec0c430e539c5810a766Evan Cheng CanFold = true; 211381a038218171860ee4c382849c647d3dc841fe8bEvan Cheng for (unsigned j = 0, ee = MI->getNumOperands(); j != ee; ++j) { 211481a038218171860ee4c382849c647d3dc841fe8bEvan Cheng MachineOperand &MO = MI->getOperand(j); 2115d735b8019b0f297d7c14b55adcd887af24d8e602Dan Gohman if (!MO.isReg() || MO.getReg() != VReg) 211681a038218171860ee4c382849c647d3dc841fe8bEvan Cheng continue; 2117aee4af68ae2016afc5b4ec0c430e539c5810a766Evan Cheng 21180cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng if (MO.isDef()) { 2119aee4af68ae2016afc5b4ec0c430e539c5810a766Evan Cheng // If this restore were to be folded, it would have been folded 2120aee4af68ae2016afc5b4ec0c430e539c5810a766Evan Cheng // already. 2121aee4af68ae2016afc5b4ec0c430e539c5810a766Evan Cheng CanFold = false; 212281a038218171860ee4c382849c647d3dc841fe8bEvan Cheng break; 212381a038218171860ee4c382849c647d3dc841fe8bEvan Cheng } 2124aee4af68ae2016afc5b4ec0c430e539c5810a766Evan Cheng Ops.push_back(j); 212581a038218171860ee4c382849c647d3dc841fe8bEvan Cheng } 212681a038218171860ee4c382849c647d3dc841fe8bEvan Cheng } 21270cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng 21280cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng // Fold the load into the use if possible. 2129cddbb83ea82e98658d9f530c50a7b9d23249afc2Evan Cheng bool Folded = false; 2130aee4af68ae2016afc5b4ec0c430e539c5810a766Evan Cheng if (CanFold && !Ops.empty()) { 21319c3c2213647e3f1b71722d61875ebac01b65cb91Evan Cheng if (!isReMat) 2132aee4af68ae2016afc5b4ec0c430e539c5810a766Evan Cheng Folded = tryFoldMemoryOperand(MI, vrm, NULL,index,Ops,true,Slot,VReg); 2133aee4af68ae2016afc5b4ec0c430e539c5810a766Evan Cheng else { 21340cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng MachineInstr *ReMatDefMI = vrm.getReMaterializedMI(VReg); 21350cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng int LdSlot = 0; 21360cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng bool isLoadSS = tii_->isLoadFromStackSlot(ReMatDefMI, LdSlot); 21370cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng // If the rematerializable def is a load, also try to fold it. 213815511cf1660cfd6bb8b8e8fca2db9450f50430eeDan Gohman if (isLoadSS || ReMatDefMI->getDesc().canFoldAsLoad()) 2139aee4af68ae2016afc5b4ec0c430e539c5810a766Evan Cheng Folded = tryFoldMemoryOperand(MI, vrm, ReMatDefMI, index, 2140aee4af68ae2016afc5b4ec0c430e539c5810a766Evan Cheng Ops, isLoadSS, LdSlot, VReg); 2141650d7f3ff4d22646def71b842f7f163c539e0aafEvan Cheng if (!Folded) { 2142650d7f3ff4d22646def71b842f7f163c539e0aafEvan Cheng unsigned ImpUse = getReMatImplicitUse(li, ReMatDefMI); 2143650d7f3ff4d22646def71b842f7f163c539e0aafEvan Cheng if (ImpUse) { 2144650d7f3ff4d22646def71b842f7f163c539e0aafEvan Cheng // Re-matting an instruction with virtual register use. Add the 2145650d7f3ff4d22646def71b842f7f163c539e0aafEvan Cheng // register as an implicit use on the use MI and update the register 2146650d7f3ff4d22646def71b842f7f163c539e0aafEvan Cheng // interval's spill weight to HUGE_VALF to prevent it from being 2147650d7f3ff4d22646def71b842f7f163c539e0aafEvan Cheng // spilled. 2148650d7f3ff4d22646def71b842f7f163c539e0aafEvan Cheng LiveInterval &ImpLi = getInterval(ImpUse); 2149650d7f3ff4d22646def71b842f7f163c539e0aafEvan Cheng ImpLi.weight = HUGE_VALF; 2150650d7f3ff4d22646def71b842f7f163c539e0aafEvan Cheng MI->addOperand(MachineOperand::CreateReg(ImpUse, false, true)); 2151650d7f3ff4d22646def71b842f7f163c539e0aafEvan Cheng } 2152d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng } 2153aee4af68ae2016afc5b4ec0c430e539c5810a766Evan Cheng } 21540cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng } 21550cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng // If folding is not possible / failed, then tell the spiller to issue a 21560cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng // load / rematerialization for us. 2157597d10d84fb6b34f7776121404d5ed802b21b2b6Evan Cheng if (Folded) 2158597d10d84fb6b34f7776121404d5ed802b21b2b6Evan Cheng nI.removeRange(getLoadIndex(index), getUseIndex(index)+1); 2159b50bb8cf197709b3f49044740044c06d8f314564Evan Cheng else 21600cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng vrm.addRestorePoint(VReg, MI); 216181a038218171860ee4c382849c647d3dc841fe8bEvan Cheng } 21621953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng Id = RestoreMBBs.find_next(Id); 216381a038218171860ee4c382849c647d3dc841fe8bEvan Cheng } 216481a038218171860ee4c382849c647d3dc841fe8bEvan Cheng 2165b50bb8cf197709b3f49044740044c06d8f314564Evan Cheng // Finalize intervals: add kills, finalize spill weights, and filter out 2166b50bb8cf197709b3f49044740044c06d8f314564Evan Cheng // dead intervals. 2167597d10d84fb6b34f7776121404d5ed802b21b2b6Evan Cheng std::vector<LiveInterval*> RetNewLIs; 2168597d10d84fb6b34f7776121404d5ed802b21b2b6Evan Cheng for (unsigned i = 0, e = NewLIs.size(); i != e; ++i) { 2169597d10d84fb6b34f7776121404d5ed802b21b2b6Evan Cheng LiveInterval *LI = NewLIs[i]; 2170597d10d84fb6b34f7776121404d5ed802b21b2b6Evan Cheng if (!LI->empty()) { 2171496bac5b084474ac33109bad24c1ef94c843e16fOwen Anderson LI->weight /= InstrSlots::NUM * getApproximateInstructionCount(*LI); 2172b50bb8cf197709b3f49044740044c06d8f314564Evan Cheng if (!AddedKill.count(LI)) { 2173b50bb8cf197709b3f49044740044c06d8f314564Evan Cheng LiveRange *LR = &LI->ranges[LI->ranges.size()-1]; 2174d120ffd26f2715c600b028d4eac9a3c41a9f4653Evan Cheng unsigned LastUseIdx = getBaseIndex(LR->end); 2175d120ffd26f2715c600b028d4eac9a3c41a9f4653Evan Cheng MachineInstr *LastUse = getInstructionFromIndex(LastUseIdx); 21766130f66eaae89f8878590796977678afa8448926Evan Cheng int UseIdx = LastUse->findRegisterUseOperandIdx(LI->reg, false); 2177b50bb8cf197709b3f49044740044c06d8f314564Evan Cheng assert(UseIdx != -1); 2178a24752ff43dc1ad8c18c5d9e78549c45f62b980eEvan Cheng if (!LastUse->isRegTiedToDefOperand(UseIdx)) { 2179b50bb8cf197709b3f49044740044c06d8f314564Evan Cheng LastUse->getOperand(UseIdx).setIsKill(); 2180d120ffd26f2715c600b028d4eac9a3c41a9f4653Evan Cheng vrm.addKillPoint(LI->reg, LastUseIdx); 2181adf85906906ebf85c57c333e8209f37ef11a6c99Evan Cheng } 2182b50bb8cf197709b3f49044740044c06d8f314564Evan Cheng } 2183597d10d84fb6b34f7776121404d5ed802b21b2b6Evan Cheng RetNewLIs.push_back(LI); 2184597d10d84fb6b34f7776121404d5ed802b21b2b6Evan Cheng } 2185597d10d84fb6b34f7776121404d5ed802b21b2b6Evan Cheng } 218681a038218171860ee4c382849c647d3dc841fe8bEvan Cheng 21874cce6b4c7882ef0cc993d931b90bf33985c96110Evan Cheng handleSpilledImpDefs(li, vrm, rc, RetNewLIs); 2188597d10d84fb6b34f7776121404d5ed802b21b2b6Evan Cheng return RetNewLIs; 2189f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng} 2190676dd7c80b6f91178452535ac45ca58feb23cc42Evan Cheng 2191676dd7c80b6f91178452535ac45ca58feb23cc42Evan Cheng/// hasAllocatableSuperReg - Return true if the specified physical register has 2192676dd7c80b6f91178452535ac45ca58feb23cc42Evan Cheng/// any super register that's allocatable. 2193676dd7c80b6f91178452535ac45ca58feb23cc42Evan Chengbool LiveIntervals::hasAllocatableSuperReg(unsigned Reg) const { 2194676dd7c80b6f91178452535ac45ca58feb23cc42Evan Cheng for (const unsigned* AS = tri_->getSuperRegisters(Reg); *AS; ++AS) 2195676dd7c80b6f91178452535ac45ca58feb23cc42Evan Cheng if (allocatableRegs_[*AS] && hasInterval(*AS)) 2196676dd7c80b6f91178452535ac45ca58feb23cc42Evan Cheng return true; 2197676dd7c80b6f91178452535ac45ca58feb23cc42Evan Cheng return false; 2198676dd7c80b6f91178452535ac45ca58feb23cc42Evan Cheng} 2199676dd7c80b6f91178452535ac45ca58feb23cc42Evan Cheng 2200676dd7c80b6f91178452535ac45ca58feb23cc42Evan Cheng/// getRepresentativeReg - Find the largest super register of the specified 2201676dd7c80b6f91178452535ac45ca58feb23cc42Evan Cheng/// physical register. 2202676dd7c80b6f91178452535ac45ca58feb23cc42Evan Chengunsigned LiveIntervals::getRepresentativeReg(unsigned Reg) const { 2203676dd7c80b6f91178452535ac45ca58feb23cc42Evan Cheng // Find the largest super-register that is allocatable. 2204676dd7c80b6f91178452535ac45ca58feb23cc42Evan Cheng unsigned BestReg = Reg; 2205676dd7c80b6f91178452535ac45ca58feb23cc42Evan Cheng for (const unsigned* AS = tri_->getSuperRegisters(Reg); *AS; ++AS) { 2206676dd7c80b6f91178452535ac45ca58feb23cc42Evan Cheng unsigned SuperReg = *AS; 2207676dd7c80b6f91178452535ac45ca58feb23cc42Evan Cheng if (!hasAllocatableSuperReg(SuperReg) && hasInterval(SuperReg)) { 2208676dd7c80b6f91178452535ac45ca58feb23cc42Evan Cheng BestReg = SuperReg; 2209676dd7c80b6f91178452535ac45ca58feb23cc42Evan Cheng break; 2210676dd7c80b6f91178452535ac45ca58feb23cc42Evan Cheng } 2211676dd7c80b6f91178452535ac45ca58feb23cc42Evan Cheng } 2212676dd7c80b6f91178452535ac45ca58feb23cc42Evan Cheng return BestReg; 2213676dd7c80b6f91178452535ac45ca58feb23cc42Evan Cheng} 2214676dd7c80b6f91178452535ac45ca58feb23cc42Evan Cheng 2215676dd7c80b6f91178452535ac45ca58feb23cc42Evan Cheng/// getNumConflictsWithPhysReg - Return the number of uses and defs of the 2216676dd7c80b6f91178452535ac45ca58feb23cc42Evan Cheng/// specified interval that conflicts with the specified physical register. 2217676dd7c80b6f91178452535ac45ca58feb23cc42Evan Chengunsigned LiveIntervals::getNumConflictsWithPhysReg(const LiveInterval &li, 2218676dd7c80b6f91178452535ac45ca58feb23cc42Evan Cheng unsigned PhysReg) const { 2219676dd7c80b6f91178452535ac45ca58feb23cc42Evan Cheng unsigned NumConflicts = 0; 2220676dd7c80b6f91178452535ac45ca58feb23cc42Evan Cheng const LiveInterval &pli = getInterval(getRepresentativeReg(PhysReg)); 2221676dd7c80b6f91178452535ac45ca58feb23cc42Evan Cheng for (MachineRegisterInfo::reg_iterator I = mri_->reg_begin(li.reg), 2222676dd7c80b6f91178452535ac45ca58feb23cc42Evan Cheng E = mri_->reg_end(); I != E; ++I) { 2223676dd7c80b6f91178452535ac45ca58feb23cc42Evan Cheng MachineOperand &O = I.getOperand(); 2224676dd7c80b6f91178452535ac45ca58feb23cc42Evan Cheng MachineInstr *MI = O.getParent(); 2225676dd7c80b6f91178452535ac45ca58feb23cc42Evan Cheng unsigned Index = getInstructionIndex(MI); 2226676dd7c80b6f91178452535ac45ca58feb23cc42Evan Cheng if (pli.liveAt(Index)) 2227676dd7c80b6f91178452535ac45ca58feb23cc42Evan Cheng ++NumConflicts; 2228676dd7c80b6f91178452535ac45ca58feb23cc42Evan Cheng } 2229676dd7c80b6f91178452535ac45ca58feb23cc42Evan Cheng return NumConflicts; 2230676dd7c80b6f91178452535ac45ca58feb23cc42Evan Cheng} 2231676dd7c80b6f91178452535ac45ca58feb23cc42Evan Cheng 2232676dd7c80b6f91178452535ac45ca58feb23cc42Evan Cheng/// spillPhysRegAroundRegDefsUses - Spill the specified physical register 22332824a655509577127d221eecd1425de196f80320Evan Cheng/// around all defs and uses of the specified interval. Return true if it 22342824a655509577127d221eecd1425de196f80320Evan Cheng/// was able to cut its interval. 22352824a655509577127d221eecd1425de196f80320Evan Chengbool LiveIntervals::spillPhysRegAroundRegDefsUses(const LiveInterval &li, 2236676dd7c80b6f91178452535ac45ca58feb23cc42Evan Cheng unsigned PhysReg, VirtRegMap &vrm) { 2237676dd7c80b6f91178452535ac45ca58feb23cc42Evan Cheng unsigned SpillReg = getRepresentativeReg(PhysReg); 2238676dd7c80b6f91178452535ac45ca58feb23cc42Evan Cheng 2239676dd7c80b6f91178452535ac45ca58feb23cc42Evan Cheng for (const unsigned *AS = tri_->getAliasSet(PhysReg); *AS; ++AS) 2240676dd7c80b6f91178452535ac45ca58feb23cc42Evan Cheng // If there are registers which alias PhysReg, but which are not a 2241676dd7c80b6f91178452535ac45ca58feb23cc42Evan Cheng // sub-register of the chosen representative super register. Assert 2242676dd7c80b6f91178452535ac45ca58feb23cc42Evan Cheng // since we can't handle it yet. 224370f2f65aacdbc96fe158b2860b5f0bad075ee548Dan Gohman assert(*AS == SpillReg || !allocatableRegs_[*AS] || !hasInterval(*AS) || 2244676dd7c80b6f91178452535ac45ca58feb23cc42Evan Cheng tri_->isSuperRegister(*AS, SpillReg)); 2245676dd7c80b6f91178452535ac45ca58feb23cc42Evan Cheng 22462824a655509577127d221eecd1425de196f80320Evan Cheng bool Cut = false; 2247676dd7c80b6f91178452535ac45ca58feb23cc42Evan Cheng LiveInterval &pli = getInterval(SpillReg); 2248676dd7c80b6f91178452535ac45ca58feb23cc42Evan Cheng SmallPtrSet<MachineInstr*, 8> SeenMIs; 2249676dd7c80b6f91178452535ac45ca58feb23cc42Evan Cheng for (MachineRegisterInfo::reg_iterator I = mri_->reg_begin(li.reg), 2250676dd7c80b6f91178452535ac45ca58feb23cc42Evan Cheng E = mri_->reg_end(); I != E; ++I) { 2251676dd7c80b6f91178452535ac45ca58feb23cc42Evan Cheng MachineOperand &O = I.getOperand(); 2252676dd7c80b6f91178452535ac45ca58feb23cc42Evan Cheng MachineInstr *MI = O.getParent(); 2253676dd7c80b6f91178452535ac45ca58feb23cc42Evan Cheng if (SeenMIs.count(MI)) 2254676dd7c80b6f91178452535ac45ca58feb23cc42Evan Cheng continue; 2255676dd7c80b6f91178452535ac45ca58feb23cc42Evan Cheng SeenMIs.insert(MI); 2256676dd7c80b6f91178452535ac45ca58feb23cc42Evan Cheng unsigned Index = getInstructionIndex(MI); 2257676dd7c80b6f91178452535ac45ca58feb23cc42Evan Cheng if (pli.liveAt(Index)) { 2258676dd7c80b6f91178452535ac45ca58feb23cc42Evan Cheng vrm.addEmergencySpill(SpillReg, MI); 22595a3c6a87b0173b9d367f7b55e7c99e5110ede057Evan Cheng unsigned StartIdx = getLoadIndex(Index); 22605a3c6a87b0173b9d367f7b55e7c99e5110ede057Evan Cheng unsigned EndIdx = getStoreIndex(Index)+1; 22612824a655509577127d221eecd1425de196f80320Evan Cheng if (pli.isInOneLiveRange(StartIdx, EndIdx)) { 22625a3c6a87b0173b9d367f7b55e7c99e5110ede057Evan Cheng pli.removeRange(StartIdx, EndIdx); 22632824a655509577127d221eecd1425de196f80320Evan Cheng Cut = true; 22642824a655509577127d221eecd1425de196f80320Evan Cheng } else { 22655a3c6a87b0173b9d367f7b55e7c99e5110ede057Evan Cheng cerr << "Ran out of registers during register allocation!\n"; 22665a3c6a87b0173b9d367f7b55e7c99e5110ede057Evan Cheng if (MI->getOpcode() == TargetInstrInfo::INLINEASM) { 22675a3c6a87b0173b9d367f7b55e7c99e5110ede057Evan Cheng cerr << "Please check your inline asm statement for invalid " 22685a3c6a87b0173b9d367f7b55e7c99e5110ede057Evan Cheng << "constraints:\n"; 22695a3c6a87b0173b9d367f7b55e7c99e5110ede057Evan Cheng MI->print(cerr.stream(), tm_); 22705a3c6a87b0173b9d367f7b55e7c99e5110ede057Evan Cheng } 22715a3c6a87b0173b9d367f7b55e7c99e5110ede057Evan Cheng exit(1); 22725a3c6a87b0173b9d367f7b55e7c99e5110ede057Evan Cheng } 2273676dd7c80b6f91178452535ac45ca58feb23cc42Evan Cheng for (const unsigned* AS = tri_->getSubRegisters(SpillReg); *AS; ++AS) { 2274676dd7c80b6f91178452535ac45ca58feb23cc42Evan Cheng if (!hasInterval(*AS)) 2275676dd7c80b6f91178452535ac45ca58feb23cc42Evan Cheng continue; 2276676dd7c80b6f91178452535ac45ca58feb23cc42Evan Cheng LiveInterval &spli = getInterval(*AS); 2277676dd7c80b6f91178452535ac45ca58feb23cc42Evan Cheng if (spli.liveAt(Index)) 2278676dd7c80b6f91178452535ac45ca58feb23cc42Evan Cheng spli.removeRange(getLoadIndex(Index), getStoreIndex(Index)+1); 2279676dd7c80b6f91178452535ac45ca58feb23cc42Evan Cheng } 2280676dd7c80b6f91178452535ac45ca58feb23cc42Evan Cheng } 2281676dd7c80b6f91178452535ac45ca58feb23cc42Evan Cheng } 22822824a655509577127d221eecd1425de196f80320Evan Cheng return Cut; 2283676dd7c80b6f91178452535ac45ca58feb23cc42Evan Cheng} 2284c4dc132c8a787fc41b6a162121251234aa618965Owen Anderson 2285c4dc132c8a787fc41b6a162121251234aa618965Owen AndersonLiveRange LiveIntervals::addLiveRangeToEndOfBlock(unsigned reg, 2286c4dc132c8a787fc41b6a162121251234aa618965Owen Anderson MachineInstr* startInst) { 2287c4dc132c8a787fc41b6a162121251234aa618965Owen Anderson LiveInterval& Interval = getOrCreateInterval(reg); 2288c4dc132c8a787fc41b6a162121251234aa618965Owen Anderson VNInfo* VN = Interval.getNextValue( 2289c4dc132c8a787fc41b6a162121251234aa618965Owen Anderson getInstructionIndex(startInst) + InstrSlots::DEF, 2290c4dc132c8a787fc41b6a162121251234aa618965Owen Anderson startInst, getVNInfoAllocator()); 2291c4dc132c8a787fc41b6a162121251234aa618965Owen Anderson VN->hasPHIKill = true; 2292c4dc132c8a787fc41b6a162121251234aa618965Owen Anderson VN->kills.push_back(getMBBEndIdx(startInst->getParent())); 2293c4dc132c8a787fc41b6a162121251234aa618965Owen Anderson LiveRange LR(getInstructionIndex(startInst) + InstrSlots::DEF, 2294c4dc132c8a787fc41b6a162121251234aa618965Owen Anderson getMBBEndIdx(startInst->getParent()) + 1, VN); 2295c4dc132c8a787fc41b6a162121251234aa618965Owen Anderson Interval.addRange(LR); 2296c4dc132c8a787fc41b6a162121251234aa618965Owen Anderson 2297c4dc132c8a787fc41b6a162121251234aa618965Owen Anderson return LR; 2298c4dc132c8a787fc41b6a162121251234aa618965Owen Anderson} 2299