LiveIntervalAnalysis.cpp revision 8e5f2c6f65841542e2a7092553fe42a00048e4c7
1a3b8b5c0e0a1d0942288568b2012592184ca67c5Chris Lattner//===-- LiveIntervalAnalysis.cpp - Live Interval Analysis -----------------===// 2ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos// 3ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos// The LLVM Compiler Infrastructure 4ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos// 54ee451de366474b9c228b4e5fa573795a715216dChris Lattner// This file is distributed under the University of Illinois Open Source 64ee451de366474b9c228b4e5fa573795a715216dChris Lattner// License. See LICENSE.TXT for details. 7ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos// 8ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos//===----------------------------------------------------------------------===// 9ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos// 10ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos// This file implements the LiveInterval analysis pass which is used 11ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos// by the Linear Scan Register allocator. This pass linearizes the 12ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos// basic blocks of the function in DFS order and uses the 13ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos// LiveVariables pass to conservatively compute live intervals for 14ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos// each virtual and physical register. 15ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos// 16ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos//===----------------------------------------------------------------------===// 17ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos 18ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos#define DEBUG_TYPE "liveintervals" 193c3fe462f7978b429ecdd71750c26be25c3d1335Chris Lattner#include "llvm/CodeGen/LiveIntervalAnalysis.h" 2008a6c7614be9793754b17930ba619e875aef9585Misha Brukman#include "VirtRegMap.h" 21015959ee38e4fd4a920f6b0065c50e524762f580Chris Lattner#include "llvm/Value.h" 22ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos#include "llvm/CodeGen/LiveVariables.h" 23ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos#include "llvm/CodeGen/MachineFrameInfo.h" 24ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos#include "llvm/CodeGen/MachineInstr.h" 2522f07ffd27d1d721634d502c37267721d2e025cfEvan Cheng#include "llvm/CodeGen/MachineLoopInfo.h" 2684bc5427d6883f73cfeae3da640acd011d35c006Chris Lattner#include "llvm/CodeGen/MachineRegisterInfo.h" 27ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos#include "llvm/CodeGen/Passes.h" 286f0d024a534af18d9e60b3ea757376cd8a3a980eDan Gohman#include "llvm/Target/TargetRegisterInfo.h" 29ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos#include "llvm/Target/TargetInstrInfo.h" 30ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos#include "llvm/Target/TargetMachine.h" 31551ccae044b0ff658fe629dd67edd5ffe75d10e8Reid Spencer#include "llvm/Support/CommandLine.h" 32551ccae044b0ff658fe629dd67edd5ffe75d10e8Reid Spencer#include "llvm/Support/Debug.h" 33551ccae044b0ff658fe629dd67edd5ffe75d10e8Reid Spencer#include "llvm/ADT/Statistic.h" 34551ccae044b0ff658fe629dd67edd5ffe75d10e8Reid Spencer#include "llvm/ADT/STLExtras.h" 3520aa474f8fbebde588edc101b90e834df28ce4ceAlkis Evlogimenos#include <algorithm> 3697af751deb9b26fd42fbcee082da9ccc4ded5b45Jeff Cohen#include <cmath> 37ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenosusing namespace llvm; 38ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos 39844731a7f1909f55935e3514c9e713a62d67662eDan Gohman// Hidden options for help debugging. 40844731a7f1909f55935e3514c9e713a62d67662eDan Gohmanstatic cl::opt<bool> DisableReMat("disable-rematerialization", 41844731a7f1909f55935e3514c9e713a62d67662eDan Gohman cl::init(false), cl::Hidden); 42844731a7f1909f55935e3514c9e713a62d67662eDan Gohman 43844731a7f1909f55935e3514c9e713a62d67662eDan Gohmanstatic cl::opt<bool> SplitAtBB("split-intervals-at-bb", 44844731a7f1909f55935e3514c9e713a62d67662eDan Gohman cl::init(true), cl::Hidden); 45844731a7f1909f55935e3514c9e713a62d67662eDan Gohmanstatic cl::opt<int> SplitLimit("split-limit", 46844731a7f1909f55935e3514c9e713a62d67662eDan Gohman cl::init(-1), cl::Hidden); 47bc165e436beb02443abea9736c1b77e2dd7828b6Evan Cheng 48cd3245ac45c595da96bb768a55cddc356dff55feChris LattnerSTATISTIC(numIntervals, "Number of original intervals"); 49cd3245ac45c595da96bb768a55cddc356dff55feChris LattnerSTATISTIC(numIntervalsAfter, "Number of intervals after coalescing"); 500cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan ChengSTATISTIC(numFolds , "Number of loads/stores folded into instructions"); 510cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan ChengSTATISTIC(numSplits , "Number of intervals split"); 52cd3245ac45c595da96bb768a55cddc356dff55feChris Lattner 531997473cf72957d0e70322e2fe6fe2ab141c58a6Devang Patelchar LiveIntervals::ID = 0; 54844731a7f1909f55935e3514c9e713a62d67662eDan Gohmanstatic RegisterPass<LiveIntervals> X("liveintervals", "Live Interval Analysis"); 55ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos 56f7da2c7b0c6293c268881628fc351bed7763f1f4Chris Lattnervoid LiveIntervals::getAnalysisUsage(AnalysisUsage &AU) const { 572513330de8f8020d15d5bc96640a0957b7c733b9David Greene AU.addPreserved<LiveVariables>(); 581a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos AU.addRequired<LiveVariables>(); 5967d65bb69d5cad957cbb6d672dc0b4a19c211a42Bill Wendling AU.addPreservedID(MachineLoopInfoID); 6067d65bb69d5cad957cbb6d672dc0b4a19c211a42Bill Wendling AU.addPreservedID(MachineDominatorsID); 61fcc6350ac9b99d6590f5256d26bfa489b4531fb3Owen Anderson AU.addPreservedID(PHIEliminationID); 62fcc6350ac9b99d6590f5256d26bfa489b4531fb3Owen Anderson AU.addRequiredID(PHIEliminationID); 631a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos AU.addRequiredID(TwoAddressInstructionPassID); 641a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos MachineFunctionPass::getAnalysisUsage(AU); 65ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos} 66ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos 67f7da2c7b0c6293c268881628fc351bed7763f1f4Chris Lattnervoid LiveIntervals::releaseMemory() { 683f32d65912b4da23793dab618d981be2ce11c331Evan Cheng MBB2IdxMap.clear(); 694ca980e7f9ce7b78955307c2d07001a24d3b6befEvan Cheng Idx2MBBMap.clear(); 701a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos mi2iMap_.clear(); 711a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos i2miMap_.clear(); 721a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos r2iMap_.clear(); 73dd199d29b781bc713462f1255b63d3f153bfd9e9Evan Cheng // Release VNInfo memroy regions after all VNInfo objects are dtor'd. 74dd199d29b781bc713462f1255b63d3f153bfd9e9Evan Cheng VNInfoAllocator.Reset(); 75549f27d3070195d6647b796841a5291b4549e8e0Evan Cheng for (unsigned i = 0, e = ClonedMIs.size(); i != e; ++i) 768e5f2c6f65841542e2a7092553fe42a00048e4c7Dan Gohman mf_->DeleteMachineInstr(ClonedMIs[i]); 77993141402f57b4d4cbb7f8a3113f19c61688f9b7Evan Cheng} 78993141402f57b4d4cbb7f8a3113f19c61688f9b7Evan Cheng 7980b3ce65e294a28b88c882d44a5e749a2924c9e3Owen Andersonvoid LiveIntervals::computeNumbering() { 8080b3ce65e294a28b88c882d44a5e749a2924c9e3Owen Anderson Index2MiMap OldI2MI = i2miMap_; 8180b3ce65e294a28b88c882d44a5e749a2924c9e3Owen Anderson 8280b3ce65e294a28b88c882d44a5e749a2924c9e3Owen Anderson Idx2MBBMap.clear(); 8380b3ce65e294a28b88c882d44a5e749a2924c9e3Owen Anderson MBB2IdxMap.clear(); 8480b3ce65e294a28b88c882d44a5e749a2924c9e3Owen Anderson mi2iMap_.clear(); 8580b3ce65e294a28b88c882d44a5e749a2924c9e3Owen Anderson i2miMap_.clear(); 8680b3ce65e294a28b88c882d44a5e749a2924c9e3Owen Anderson 87428b92eb83b457b71d29d1d4b7900d36a0ce9a53Chris Lattner // Number MachineInstrs and MachineBasicBlocks. 88428b92eb83b457b71d29d1d4b7900d36a0ce9a53Chris Lattner // Initialize MBB indexes to a sentinal. 89549f27d3070195d6647b796841a5291b4549e8e0Evan Cheng MBB2IdxMap.resize(mf_->getNumBlockIDs(), std::make_pair(~0U,~0U)); 90428b92eb83b457b71d29d1d4b7900d36a0ce9a53Chris Lattner 91428b92eb83b457b71d29d1d4b7900d36a0ce9a53Chris Lattner unsigned MIIndex = 0; 92428b92eb83b457b71d29d1d4b7900d36a0ce9a53Chris Lattner for (MachineFunction::iterator MBB = mf_->begin(), E = mf_->end(); 93428b92eb83b457b71d29d1d4b7900d36a0ce9a53Chris Lattner MBB != E; ++MBB) { 94549f27d3070195d6647b796841a5291b4549e8e0Evan Cheng unsigned StartIdx = MIIndex; 950c9f92e1ff64ee56724eae444a0442b02f83d0a8Evan Cheng 96428b92eb83b457b71d29d1d4b7900d36a0ce9a53Chris Lattner for (MachineBasicBlock::iterator I = MBB->begin(), E = MBB->end(); 97428b92eb83b457b71d29d1d4b7900d36a0ce9a53Chris Lattner I != E; ++I) { 98428b92eb83b457b71d29d1d4b7900d36a0ce9a53Chris Lattner bool inserted = mi2iMap_.insert(std::make_pair(I, MIIndex)).second; 991a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos assert(inserted && "multiple MachineInstr -> index mappings"); 100428b92eb83b457b71d29d1d4b7900d36a0ce9a53Chris Lattner i2miMap_.push_back(I); 101428b92eb83b457b71d29d1d4b7900d36a0ce9a53Chris Lattner MIIndex += InstrSlots::NUM; 10229b039976fd682716c6b8ed1cb7084226b2ad84bOwen Anderson } 10329b039976fd682716c6b8ed1cb7084226b2ad84bOwen Anderson 10429b039976fd682716c6b8ed1cb7084226b2ad84bOwen Anderson if (StartIdx == MIIndex) { 10529b039976fd682716c6b8ed1cb7084226b2ad84bOwen Anderson // Empty MBB 1061fbb4545d41e65191ae66a7302276fa5424518c5Owen Anderson MIIndex += InstrSlots::NUM; 1071fbb4545d41e65191ae66a7302276fa5424518c5Owen Anderson i2miMap_.push_back(0); 108355780128986e375c7ac2a75025ac129bb8280bfOwen Anderson } 1091fbb4545d41e65191ae66a7302276fa5424518c5Owen Anderson // Set the MBB2IdxMap entry for this MBB. 1101fbb4545d41e65191ae66a7302276fa5424518c5Owen Anderson MBB2IdxMap[MBB->getNumber()] = std::make_pair(StartIdx, MIIndex - 1); 1111fbb4545d41e65191ae66a7302276fa5424518c5Owen Anderson Idx2MBBMap.push_back(std::make_pair(StartIdx, MBB)); 112428b92eb83b457b71d29d1d4b7900d36a0ce9a53Chris Lattner } 1134ca980e7f9ce7b78955307c2d07001a24d3b6befEvan Cheng std::sort(Idx2MBBMap.begin(), Idx2MBBMap.end(), Idx2MBBCompare()); 11480b3ce65e294a28b88c882d44a5e749a2924c9e3Owen Anderson 11580b3ce65e294a28b88c882d44a5e749a2924c9e3Owen Anderson if (!OldI2MI.empty()) 11629b039976fd682716c6b8ed1cb7084226b2ad84bOwen Anderson for (iterator I = begin(), E = end(); I != E; ++I) 11729b039976fd682716c6b8ed1cb7084226b2ad84bOwen Anderson for (LiveInterval::iterator LI = I->second.begin(), LE = I->second.end(); 11829b039976fd682716c6b8ed1cb7084226b2ad84bOwen Anderson LI != LE; ++LI) { 1197eec0c243320fb2629554681547d7384ea9d0c53Owen Anderson 1207eec0c243320fb2629554681547d7384ea9d0c53Owen Anderson // Remap the start index of the live range to the corresponding new 1217eec0c243320fb2629554681547d7384ea9d0c53Owen Anderson // number, or our best guess at what it _should_ correspond to if the 1227eec0c243320fb2629554681547d7384ea9d0c53Owen Anderson // original instruction has been erased. This is either the following 1237eec0c243320fb2629554681547d7384ea9d0c53Owen Anderson // instruction or its predecessor. 1244b5b209679f866d3ac6372f963aa7e9906f9a08bOwen Anderson unsigned offset = LI->start % InstrSlots::NUM; 12529b039976fd682716c6b8ed1cb7084226b2ad84bOwen Anderson if (OldI2MI[LI->start / InstrSlots::NUM]) 12629b039976fd682716c6b8ed1cb7084226b2ad84bOwen Anderson LI->start = mi2iMap_[OldI2MI[LI->start / InstrSlots::NUM]] + offset; 12729b039976fd682716c6b8ed1cb7084226b2ad84bOwen Anderson else { 12829b039976fd682716c6b8ed1cb7084226b2ad84bOwen Anderson unsigned i = 0; 12929b039976fd682716c6b8ed1cb7084226b2ad84bOwen Anderson MachineInstr* newInstr = 0; 13029b039976fd682716c6b8ed1cb7084226b2ad84bOwen Anderson do { 13129b039976fd682716c6b8ed1cb7084226b2ad84bOwen Anderson newInstr = OldI2MI[LI->start / InstrSlots::NUM + i]; 13229b039976fd682716c6b8ed1cb7084226b2ad84bOwen Anderson i++; 13329b039976fd682716c6b8ed1cb7084226b2ad84bOwen Anderson } while (!newInstr); 1347eec0c243320fb2629554681547d7384ea9d0c53Owen Anderson 13529b039976fd682716c6b8ed1cb7084226b2ad84bOwen Anderson if (mi2iMap_[newInstr] == 13629b039976fd682716c6b8ed1cb7084226b2ad84bOwen Anderson MBB2IdxMap[newInstr->getParent()->getNumber()].first) 13729b039976fd682716c6b8ed1cb7084226b2ad84bOwen Anderson LI->start = mi2iMap_[newInstr]; 13829b039976fd682716c6b8ed1cb7084226b2ad84bOwen Anderson else 13929b039976fd682716c6b8ed1cb7084226b2ad84bOwen Anderson LI->start = mi2iMap_[newInstr] - InstrSlots::NUM + offset; 1407eec0c243320fb2629554681547d7384ea9d0c53Owen Anderson } 1414b5b209679f866d3ac6372f963aa7e9906f9a08bOwen Anderson 1427eec0c243320fb2629554681547d7384ea9d0c53Owen Anderson // Remap the ending index in the same way that we remapped the start, 1437eec0c243320fb2629554681547d7384ea9d0c53Owen Anderson // except for the final step where we always map to the immediately 1447eec0c243320fb2629554681547d7384ea9d0c53Owen Anderson // following instruction. 14529b039976fd682716c6b8ed1cb7084226b2ad84bOwen Anderson if (LI->end / InstrSlots::NUM < OldI2MI.size()) { 14629b039976fd682716c6b8ed1cb7084226b2ad84bOwen Anderson offset = LI->end % InstrSlots::NUM; 14729b039976fd682716c6b8ed1cb7084226b2ad84bOwen Anderson if (OldI2MI[LI->end / InstrSlots::NUM]) 14829b039976fd682716c6b8ed1cb7084226b2ad84bOwen Anderson LI->end = mi2iMap_[OldI2MI[LI->end / InstrSlots::NUM]] + offset; 14929b039976fd682716c6b8ed1cb7084226b2ad84bOwen Anderson else { 15029b039976fd682716c6b8ed1cb7084226b2ad84bOwen Anderson unsigned i = 0; 15129b039976fd682716c6b8ed1cb7084226b2ad84bOwen Anderson MachineInstr* newInstr = 0; 15229b039976fd682716c6b8ed1cb7084226b2ad84bOwen Anderson do { 15329b039976fd682716c6b8ed1cb7084226b2ad84bOwen Anderson newInstr = OldI2MI[LI->end / InstrSlots::NUM + i]; 15429b039976fd682716c6b8ed1cb7084226b2ad84bOwen Anderson i++; 15529b039976fd682716c6b8ed1cb7084226b2ad84bOwen Anderson } while (!newInstr); 15629b039976fd682716c6b8ed1cb7084226b2ad84bOwen Anderson 15729b039976fd682716c6b8ed1cb7084226b2ad84bOwen Anderson LI->end = mi2iMap_[newInstr]; 15829b039976fd682716c6b8ed1cb7084226b2ad84bOwen Anderson } 1594b5b209679f866d3ac6372f963aa7e9906f9a08bOwen Anderson } else { 16029b039976fd682716c6b8ed1cb7084226b2ad84bOwen Anderson LI->end = i2miMap_.size() * InstrSlots::NUM; 1614b5b209679f866d3ac6372f963aa7e9906f9a08bOwen Anderson } 162745825f431920662e97bdab5c1bcfac62e48c52fOwen Anderson 1637eec0c243320fb2629554681547d7384ea9d0c53Owen Anderson // Remap the VNInfo def index, which works the same as the 1647eec0c243320fb2629554681547d7384ea9d0c53Owen Anderson // start indices above. 165745825f431920662e97bdab5c1bcfac62e48c52fOwen Anderson VNInfo* vni = LI->valno; 1664b5b209679f866d3ac6372f963aa7e9906f9a08bOwen Anderson offset = vni->def % InstrSlots::NUM; 16729b039976fd682716c6b8ed1cb7084226b2ad84bOwen Anderson if (OldI2MI[vni->def / InstrSlots::NUM]) 16829b039976fd682716c6b8ed1cb7084226b2ad84bOwen Anderson vni->def = mi2iMap_[OldI2MI[vni->def / InstrSlots::NUM]] + offset; 16929b039976fd682716c6b8ed1cb7084226b2ad84bOwen Anderson else { 17029b039976fd682716c6b8ed1cb7084226b2ad84bOwen Anderson unsigned i = 0; 17129b039976fd682716c6b8ed1cb7084226b2ad84bOwen Anderson MachineInstr* newInstr = 0; 17229b039976fd682716c6b8ed1cb7084226b2ad84bOwen Anderson do { 17329b039976fd682716c6b8ed1cb7084226b2ad84bOwen Anderson newInstr = OldI2MI[vni->def / InstrSlots::NUM + i]; 17429b039976fd682716c6b8ed1cb7084226b2ad84bOwen Anderson i++; 17529b039976fd682716c6b8ed1cb7084226b2ad84bOwen Anderson } while (!newInstr); 1767eec0c243320fb2629554681547d7384ea9d0c53Owen Anderson 17729b039976fd682716c6b8ed1cb7084226b2ad84bOwen Anderson if (mi2iMap_[newInstr] == 17829b039976fd682716c6b8ed1cb7084226b2ad84bOwen Anderson MBB2IdxMap[newInstr->getParent()->getNumber()].first) 17929b039976fd682716c6b8ed1cb7084226b2ad84bOwen Anderson vni->def = mi2iMap_[newInstr]; 18029b039976fd682716c6b8ed1cb7084226b2ad84bOwen Anderson else 18129b039976fd682716c6b8ed1cb7084226b2ad84bOwen Anderson vni->def = mi2iMap_[newInstr] - InstrSlots::NUM + offset; 1827eec0c243320fb2629554681547d7384ea9d0c53Owen Anderson } 183745825f431920662e97bdab5c1bcfac62e48c52fOwen Anderson 1847eec0c243320fb2629554681547d7384ea9d0c53Owen Anderson // Remap the VNInfo kill indices, which works the same as 1857eec0c243320fb2629554681547d7384ea9d0c53Owen Anderson // the end indices above. 1864b5b209679f866d3ac6372f963aa7e9906f9a08bOwen Anderson for (size_t i = 0; i < vni->kills.size(); ++i) { 1874b5b209679f866d3ac6372f963aa7e9906f9a08bOwen Anderson offset = vni->kills[i] % InstrSlots::NUM; 18829b039976fd682716c6b8ed1cb7084226b2ad84bOwen Anderson if (OldI2MI[vni->kills[i] / InstrSlots::NUM]) 18929b039976fd682716c6b8ed1cb7084226b2ad84bOwen Anderson vni->kills[i] = mi2iMap_[OldI2MI[vni->kills[i] / InstrSlots::NUM]] + 19029b039976fd682716c6b8ed1cb7084226b2ad84bOwen Anderson offset; 19129b039976fd682716c6b8ed1cb7084226b2ad84bOwen Anderson else { 19229b039976fd682716c6b8ed1cb7084226b2ad84bOwen Anderson unsigned e = 0; 19329b039976fd682716c6b8ed1cb7084226b2ad84bOwen Anderson MachineInstr* newInstr = 0; 19429b039976fd682716c6b8ed1cb7084226b2ad84bOwen Anderson do { 19529b039976fd682716c6b8ed1cb7084226b2ad84bOwen Anderson newInstr = OldI2MI[vni->kills[i] / InstrSlots::NUM + e]; 19629b039976fd682716c6b8ed1cb7084226b2ad84bOwen Anderson e++; 19729b039976fd682716c6b8ed1cb7084226b2ad84bOwen Anderson } while (!newInstr); 19829b039976fd682716c6b8ed1cb7084226b2ad84bOwen Anderson 19929b039976fd682716c6b8ed1cb7084226b2ad84bOwen Anderson vni->kills[i] = mi2iMap_[newInstr]; 2007eec0c243320fb2629554681547d7384ea9d0c53Owen Anderson } 2014b5b209679f866d3ac6372f963aa7e9906f9a08bOwen Anderson } 20280b3ce65e294a28b88c882d44a5e749a2924c9e3Owen Anderson } 20380b3ce65e294a28b88c882d44a5e749a2924c9e3Owen Anderson} 20480b3ce65e294a28b88c882d44a5e749a2924c9e3Owen Anderson 20580b3ce65e294a28b88c882d44a5e749a2924c9e3Owen Anderson/// runOnMachineFunction - Register allocate the whole function 20680b3ce65e294a28b88c882d44a5e749a2924c9e3Owen Anderson/// 20780b3ce65e294a28b88c882d44a5e749a2924c9e3Owen Andersonbool LiveIntervals::runOnMachineFunction(MachineFunction &fn) { 20880b3ce65e294a28b88c882d44a5e749a2924c9e3Owen Anderson mf_ = &fn; 20980b3ce65e294a28b88c882d44a5e749a2924c9e3Owen Anderson mri_ = &mf_->getRegInfo(); 21080b3ce65e294a28b88c882d44a5e749a2924c9e3Owen Anderson tm_ = &fn.getTarget(); 21180b3ce65e294a28b88c882d44a5e749a2924c9e3Owen Anderson tri_ = tm_->getRegisterInfo(); 21280b3ce65e294a28b88c882d44a5e749a2924c9e3Owen Anderson tii_ = tm_->getInstrInfo(); 21380b3ce65e294a28b88c882d44a5e749a2924c9e3Owen Anderson lv_ = &getAnalysis<LiveVariables>(); 21480b3ce65e294a28b88c882d44a5e749a2924c9e3Owen Anderson allocatableRegs_ = tri_->getAllocatableSet(fn); 215ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos 21680b3ce65e294a28b88c882d44a5e749a2924c9e3Owen Anderson computeNumbering(); 2171a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos computeIntervals(); 218ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos 2191a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos numIntervals += getNumIntervals(); 220843b160a2040b3ec4d3452678450afa11704c473Alkis Evlogimenos 221bdc679d564e67a81792e463f6614b0088f975025Bill Wendling DOUT << "********** INTERVALS **********\n"; 222bdc679d564e67a81792e463f6614b0088f975025Bill Wendling for (iterator I = begin(), E = end(); I != E; ++I) { 2236f0d024a534af18d9e60b3ea757376cd8a3a980eDan Gohman I->second.print(DOUT, tri_); 224bdc679d564e67a81792e463f6614b0088f975025Bill Wendling DOUT << "\n"; 225bdc679d564e67a81792e463f6614b0088f975025Bill Wendling } 2267ac2d3146a196fa0120c579ecd2ddd69652ad230Chris Lattner 2271a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos numIntervalsAfter += getNumIntervals(); 22870ca358b7d540b6061236ddf757085042873c12cChris Lattner DEBUG(dump()); 2291a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos return true; 230ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos} 231ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos 23270ca358b7d540b6061236ddf757085042873c12cChris Lattner/// print - Implement the dump method. 233ce9653ce449f1409815547e1bf60abcd1332d2c9Reid Spencervoid LiveIntervals::print(std::ostream &O, const Module* ) const { 23470ca358b7d540b6061236ddf757085042873c12cChris Lattner O << "********** INTERVALS **********\n"; 2358e7a70976deee78a84099b916591d40f7a1cdc34Chris Lattner for (const_iterator I = begin(), E = end(); I != E; ++I) { 2363f32d65912b4da23793dab618d981be2ce11c331Evan Cheng I->second.print(O, tri_); 2373f32d65912b4da23793dab618d981be2ce11c331Evan Cheng O << "\n"; 2388e7a70976deee78a84099b916591d40f7a1cdc34Chris Lattner } 23970ca358b7d540b6061236ddf757085042873c12cChris Lattner 24070ca358b7d540b6061236ddf757085042873c12cChris Lattner O << "********** MACHINEINSTRS **********\n"; 24170ca358b7d540b6061236ddf757085042873c12cChris Lattner for (MachineFunction::iterator mbbi = mf_->begin(), mbbe = mf_->end(); 24270ca358b7d540b6061236ddf757085042873c12cChris Lattner mbbi != mbbe; ++mbbi) { 24370ca358b7d540b6061236ddf757085042873c12cChris Lattner O << ((Value*)mbbi->getBasicBlock())->getName() << ":\n"; 24470ca358b7d540b6061236ddf757085042873c12cChris Lattner for (MachineBasicBlock::iterator mii = mbbi->begin(), 24570ca358b7d540b6061236ddf757085042873c12cChris Lattner mie = mbbi->end(); mii != mie; ++mii) { 246477e4555de341c5de780de3720d6f115ec133c4eChris Lattner O << getInstructionIndex(mii) << '\t' << *mii; 24770ca358b7d540b6061236ddf757085042873c12cChris Lattner } 24870ca358b7d540b6061236ddf757085042873c12cChris Lattner } 24970ca358b7d540b6061236ddf757085042873c12cChris Lattner} 25070ca358b7d540b6061236ddf757085042873c12cChris Lattner 251c92da3882ee4e18153bb36fcdf33af393aba8259Evan Cheng/// conflictsWithPhysRegDef - Returns true if the specified register 252c92da3882ee4e18153bb36fcdf33af393aba8259Evan Cheng/// is defined during the duration of the specified interval. 253c92da3882ee4e18153bb36fcdf33af393aba8259Evan Chengbool LiveIntervals::conflictsWithPhysRegDef(const LiveInterval &li, 254c92da3882ee4e18153bb36fcdf33af393aba8259Evan Cheng VirtRegMap &vrm, unsigned reg) { 255c92da3882ee4e18153bb36fcdf33af393aba8259Evan Cheng for (LiveInterval::Ranges::const_iterator 256c92da3882ee4e18153bb36fcdf33af393aba8259Evan Cheng I = li.ranges.begin(), E = li.ranges.end(); I != E; ++I) { 257c92da3882ee4e18153bb36fcdf33af393aba8259Evan Cheng for (unsigned index = getBaseIndex(I->start), 258c92da3882ee4e18153bb36fcdf33af393aba8259Evan Cheng end = getBaseIndex(I->end-1) + InstrSlots::NUM; index != end; 259c92da3882ee4e18153bb36fcdf33af393aba8259Evan Cheng index += InstrSlots::NUM) { 260c92da3882ee4e18153bb36fcdf33af393aba8259Evan Cheng // skip deleted instructions 261c92da3882ee4e18153bb36fcdf33af393aba8259Evan Cheng while (index != end && !getInstructionFromIndex(index)) 262c92da3882ee4e18153bb36fcdf33af393aba8259Evan Cheng index += InstrSlots::NUM; 263c92da3882ee4e18153bb36fcdf33af393aba8259Evan Cheng if (index == end) break; 264c92da3882ee4e18153bb36fcdf33af393aba8259Evan Cheng 265c92da3882ee4e18153bb36fcdf33af393aba8259Evan Cheng MachineInstr *MI = getInstructionFromIndex(index); 2665d446265c740c17ed12e693423f0363296670d60Evan Cheng unsigned SrcReg, DstReg; 2675d446265c740c17ed12e693423f0363296670d60Evan Cheng if (tii_->isMoveInstr(*MI, SrcReg, DstReg)) 2685d446265c740c17ed12e693423f0363296670d60Evan Cheng if (SrcReg == li.reg || DstReg == li.reg) 2695d446265c740c17ed12e693423f0363296670d60Evan Cheng continue; 270c92da3882ee4e18153bb36fcdf33af393aba8259Evan Cheng for (unsigned i = 0; i != MI->getNumOperands(); ++i) { 271c92da3882ee4e18153bb36fcdf33af393aba8259Evan Cheng MachineOperand& mop = MI->getOperand(i); 2725d446265c740c17ed12e693423f0363296670d60Evan Cheng if (!mop.isRegister()) 273c92da3882ee4e18153bb36fcdf33af393aba8259Evan Cheng continue; 274c92da3882ee4e18153bb36fcdf33af393aba8259Evan Cheng unsigned PhysReg = mop.getReg(); 2755d446265c740c17ed12e693423f0363296670d60Evan Cheng if (PhysReg == 0 || PhysReg == li.reg) 276c92da3882ee4e18153bb36fcdf33af393aba8259Evan Cheng continue; 2776f0d024a534af18d9e60b3ea757376cd8a3a980eDan Gohman if (TargetRegisterInfo::isVirtualRegister(PhysReg)) { 2785d446265c740c17ed12e693423f0363296670d60Evan Cheng if (!vrm.hasPhys(PhysReg)) 2795d446265c740c17ed12e693423f0363296670d60Evan Cheng continue; 280c92da3882ee4e18153bb36fcdf33af393aba8259Evan Cheng PhysReg = vrm.getPhys(PhysReg); 2815d446265c740c17ed12e693423f0363296670d60Evan Cheng } 2826f0d024a534af18d9e60b3ea757376cd8a3a980eDan Gohman if (PhysReg && tri_->regsOverlap(PhysReg, reg)) 283c92da3882ee4e18153bb36fcdf33af393aba8259Evan Cheng return true; 284c92da3882ee4e18153bb36fcdf33af393aba8259Evan Cheng } 285c92da3882ee4e18153bb36fcdf33af393aba8259Evan Cheng } 286c92da3882ee4e18153bb36fcdf33af393aba8259Evan Cheng } 287c92da3882ee4e18153bb36fcdf33af393aba8259Evan Cheng 288c92da3882ee4e18153bb36fcdf33af393aba8259Evan Cheng return false; 289c92da3882ee4e18153bb36fcdf33af393aba8259Evan Cheng} 290c92da3882ee4e18153bb36fcdf33af393aba8259Evan Cheng 291be4f88a8b8bb3311e0dc4cde8533763d7923c3eaChris Lattnervoid LiveIntervals::printRegName(unsigned reg) const { 2926f0d024a534af18d9e60b3ea757376cd8a3a980eDan Gohman if (TargetRegisterInfo::isPhysicalRegister(reg)) 293e6d088acc90e422451e098555d383d4d65b6ce6bBill Wendling cerr << tri_->getName(reg); 2941a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos else 295e81561909d128c6e2d8033cb5465a49b2596b26aBill Wendling cerr << "%reg" << reg; 296ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos} 297ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos 298be4f88a8b8bb3311e0dc4cde8533763d7923c3eaChris Lattnervoid LiveIntervals::handleVirtualRegisterDef(MachineBasicBlock *mbb, 299ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos MachineBasicBlock::iterator mi, 3006b098dee286cc6fe5a5a476464d92dec5602e406Owen Anderson unsigned MIIdx, MachineOperand& MO, 301be4f88a8b8bb3311e0dc4cde8533763d7923c3eaChris Lattner LiveInterval &interval) { 302bdc679d564e67a81792e463f6614b0088f975025Bill Wendling DOUT << "\t\tregister: "; DEBUG(printRegName(interval.reg)); 3031a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos LiveVariables::VarInfo& vi = lv_->getVarInfo(interval.reg); 3041a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos 305419852ca8a01aecde4c0e20af6b7bd6450e70f87Evan Cheng if (mi->getOpcode() == TargetInstrInfo::IMPLICIT_DEF) { 306419852ca8a01aecde4c0e20af6b7bd6450e70f87Evan Cheng DOUT << "is a implicit_def\n"; 307419852ca8a01aecde4c0e20af6b7bd6450e70f87Evan Cheng return; 308419852ca8a01aecde4c0e20af6b7bd6450e70f87Evan Cheng } 309419852ca8a01aecde4c0e20af6b7bd6450e70f87Evan Cheng 310706515727c6d024015fffded2b3109a4f0ac5299Alkis Evlogimenos // Virtual registers may be defined multiple times (due to phi 311706515727c6d024015fffded2b3109a4f0ac5299Alkis Evlogimenos // elimination and 2-addr elimination). Much of what we do only has to be 312706515727c6d024015fffded2b3109a4f0ac5299Alkis Evlogimenos // done once for the vreg. We use an empty interval to detect the first 3131a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // time we see a vreg. 3141a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos if (interval.empty()) { 3151a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // Get the Idx of the defining instructions. 3166b128bdc58a496e9f08e4d09416330320761baffChris Lattner unsigned defIndex = getDefIndex(MIIdx); 3177ecb38be0a533e7b9c7d3b8e9b5c8a6fa5f6b349Evan Cheng VNInfo *ValNo; 318c8d044e4f779fdcfc5e7d592927740fd8f672a70Evan Cheng MachineInstr *CopyMI = NULL; 31991725b75852443923b419fd23215194cfc65dd88Chris Lattner unsigned SrcReg, DstReg; 320c8d044e4f779fdcfc5e7d592927740fd8f672a70Evan Cheng if (mi->getOpcode() == TargetInstrInfo::EXTRACT_SUBREG || 3217e073baedb8232b9519dbe15ea141ff98ccfe6aeEvan Cheng mi->getOpcode() == TargetInstrInfo::INSERT_SUBREG || 322c8d044e4f779fdcfc5e7d592927740fd8f672a70Evan Cheng tii_->isMoveInstr(*mi, SrcReg, DstReg)) 323c8d044e4f779fdcfc5e7d592927740fd8f672a70Evan Cheng CopyMI = mi; 324c8d044e4f779fdcfc5e7d592927740fd8f672a70Evan Cheng ValNo = interval.getNextValue(defIndex, CopyMI, VNInfoAllocator); 3257ecb38be0a533e7b9c7d3b8e9b5c8a6fa5f6b349Evan Cheng 3267ecb38be0a533e7b9c7d3b8e9b5c8a6fa5f6b349Evan Cheng assert(ValNo->id == 0 && "First value in interval is not 0?"); 3271a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos 3281a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // Loop over all of the blocks that the vreg is defined in. There are 3291a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // two cases we have to handle here. The most common case is a vreg 3301a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // whose lifetime is contained within a basic block. In this case there 3311a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // will be a single kill, in MBB, which comes after the definition. 3321a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos if (vi.Kills.size() == 1 && vi.Kills[0]->getParent() == mbb) { 3331a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // FIXME: what about dead vars? 3341a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos unsigned killIdx; 3351a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos if (vi.Kills[0] != mi) 3361a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos killIdx = getUseIndex(getInstructionIndex(vi.Kills[0]))+1; 3371a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos else 3381a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos killIdx = defIndex+1; 3391a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos 3401a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // If the kill happens after the definition, we have an intra-block 3411a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // live range. 3421a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos if (killIdx > defIndex) { 34361de82d8853a02fe39c47302432abb70a586704fEvan Cheng assert(vi.AliveBlocks.none() && 3441a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos "Shouldn't be alive across any blocks!"); 3457ecb38be0a533e7b9c7d3b8e9b5c8a6fa5f6b349Evan Cheng LiveRange LR(defIndex, killIdx, ValNo); 3461a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos interval.addRange(LR); 347bdc679d564e67a81792e463f6614b0088f975025Bill Wendling DOUT << " +" << LR << "\n"; 348f3bb2e65d12857f83b273f4ecab013680310bbbcEvan Cheng interval.addKill(ValNo, killIdx); 3491a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos return; 3501a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos } 3511a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos } 3526097d13b2a624048dbe02e39e2dfb23bfa269b64Chris Lattner 3531a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // The other case we handle is when a virtual register lives to the end 3541a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // of the defining block, potentially live across some blocks, then is 3551a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // live into some number of blocks, but gets killed. Start by adding a 3561a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // range that goes from this definition to the end of the defining block. 35729b039976fd682716c6b8ed1cb7084226b2ad84bOwen Anderson LiveRange NewLR(defIndex, 35829b039976fd682716c6b8ed1cb7084226b2ad84bOwen Anderson getInstructionIndex(&mbb->back()) + InstrSlots::NUM, 35929b039976fd682716c6b8ed1cb7084226b2ad84bOwen Anderson ValNo); 360bdc679d564e67a81792e463f6614b0088f975025Bill Wendling DOUT << " +" << NewLR; 3611a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos interval.addRange(NewLR); 3621a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos 3631a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // Iterate over all of the blocks that the variable is completely 3641a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // live in, adding [insrtIndex(begin), instrIndex(end)+4) to the 3651a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // live interval. 3661a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos for (unsigned i = 0, e = vi.AliveBlocks.size(); i != e; ++i) { 3671a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos if (vi.AliveBlocks[i]) { 36831ec841be1f51a60f5b655aa2a008eb68e48c07aOwen Anderson LiveRange LR(getMBBStartIdx(i), 369f26e8557deccd5fb28b56548ca5f7ea25aee31c6Evan Cheng getMBBEndIdx(i)+1, // MBB ends at -1. 37031ec841be1f51a60f5b655aa2a008eb68e48c07aOwen Anderson ValNo); 37131ec841be1f51a60f5b655aa2a008eb68e48c07aOwen Anderson interval.addRange(LR); 37231ec841be1f51a60f5b655aa2a008eb68e48c07aOwen Anderson DOUT << " +" << LR; 3731a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos } 3741a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos } 3751a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos 3761a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // Finally, this virtual register is live from the start of any killing 3771a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // block to the 'use' slot of the killing instruction. 3781a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos for (unsigned i = 0, e = vi.Kills.size(); i != e; ++i) { 3791a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos MachineInstr *Kill = vi.Kills[i]; 3808df786012dc6b875f31ba4152e09c6e0098082eeEvan Cheng unsigned killIdx = getUseIndex(getInstructionIndex(Kill))+1; 381428b92eb83b457b71d29d1d4b7900d36a0ce9a53Chris Lattner LiveRange LR(getMBBStartIdx(Kill->getParent()), 3827ecb38be0a533e7b9c7d3b8e9b5c8a6fa5f6b349Evan Cheng killIdx, ValNo); 3831a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos interval.addRange(LR); 384f3bb2e65d12857f83b273f4ecab013680310bbbcEvan Cheng interval.addKill(ValNo, killIdx); 385bdc679d564e67a81792e463f6614b0088f975025Bill Wendling DOUT << " +" << LR; 3861a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos } 3871a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos 3881a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos } else { 3891a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // If this is the second time we see a virtual register definition, it 3901a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // must be due to phi elimination or two addr elimination. If this is 391bf105c842450d3308d024be203ddd533f37051ecEvan Cheng // the result of two address elimination, then the vreg is one of the 392bf105c842450d3308d024be203ddd533f37051ecEvan Cheng // def-and-use register operand. 39332dfbeada7292167bb488f36a71a5a6a519ddaffEvan Cheng if (mi->isRegReDefinedByTwoAddr(interval.reg)) { 3941a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // If this is a two-address definition, then we have already processed 3951a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // the live range. The only problem is that we didn't realize there 3961a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // are actually two values in the live interval. Because of this we 3971a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // need to take the LiveRegion that defines this register and split it 3981a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // into two values. 399a07cec9e24a286157541d2337cd66b24cd116586Evan Cheng assert(interval.containsOneValue()); 400a07cec9e24a286157541d2337cd66b24cd116586Evan Cheng unsigned DefIndex = getDefIndex(interval.getValNumInfo(0)->def); 4016b128bdc58a496e9f08e4d09416330320761baffChris Lattner unsigned RedefIndex = getDefIndex(MIIdx); 4021a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos 4034f8ff168de12eabdeb4b9437bf9402489ecf85cbEvan Cheng const LiveRange *OldLR = interval.getLiveRangeContaining(RedefIndex-1); 4047ecb38be0a533e7b9c7d3b8e9b5c8a6fa5f6b349Evan Cheng VNInfo *OldValNo = OldLR->valno; 4054f8ff168de12eabdeb4b9437bf9402489ecf85cbEvan Cheng 4061a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // Delete the initial value, which should be short and continuous, 407be4f88a8b8bb3311e0dc4cde8533763d7923c3eaChris Lattner // because the 2-addr copy must be in the same MBB as the redef. 4081a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos interval.removeRange(DefIndex, RedefIndex); 409706515727c6d024015fffded2b3109a4f0ac5299Alkis Evlogimenos 410be4f88a8b8bb3311e0dc4cde8533763d7923c3eaChris Lattner // Two-address vregs should always only be redefined once. This means 411be4f88a8b8bb3311e0dc4cde8533763d7923c3eaChris Lattner // that at this point, there should be exactly one value number in it. 412be4f88a8b8bb3311e0dc4cde8533763d7923c3eaChris Lattner assert(interval.containsOneValue() && "Unexpected 2-addr liveint!"); 413be4f88a8b8bb3311e0dc4cde8533763d7923c3eaChris Lattner 41491725b75852443923b419fd23215194cfc65dd88Chris Lattner // The new value number (#1) is defined by the instruction we claimed 41591725b75852443923b419fd23215194cfc65dd88Chris Lattner // defined value #0. 416c8d044e4f779fdcfc5e7d592927740fd8f672a70Evan Cheng VNInfo *ValNo = interval.getNextValue(OldValNo->def, OldValNo->copy, 417c8d044e4f779fdcfc5e7d592927740fd8f672a70Evan Cheng VNInfoAllocator); 418be4f88a8b8bb3311e0dc4cde8533763d7923c3eaChris Lattner 41991725b75852443923b419fd23215194cfc65dd88Chris Lattner // Value#0 is now defined by the 2-addr instruction. 420c8d044e4f779fdcfc5e7d592927740fd8f672a70Evan Cheng OldValNo->def = RedefIndex; 421c8d044e4f779fdcfc5e7d592927740fd8f672a70Evan Cheng OldValNo->copy = 0; 422be4f88a8b8bb3311e0dc4cde8533763d7923c3eaChris Lattner 423be4f88a8b8bb3311e0dc4cde8533763d7923c3eaChris Lattner // Add the new live interval which replaces the range for the input copy. 424be4f88a8b8bb3311e0dc4cde8533763d7923c3eaChris Lattner LiveRange LR(DefIndex, RedefIndex, ValNo); 425bdc679d564e67a81792e463f6614b0088f975025Bill Wendling DOUT << " replace range with " << LR; 4261a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos interval.addRange(LR); 427f3bb2e65d12857f83b273f4ecab013680310bbbcEvan Cheng interval.addKill(ValNo, RedefIndex); 4281a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos 4291a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // If this redefinition is dead, we need to add a dummy unit live 4301a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // range covering the def slot. 4316b098dee286cc6fe5a5a476464d92dec5602e406Owen Anderson if (MO.isDead()) 4327ecb38be0a533e7b9c7d3b8e9b5c8a6fa5f6b349Evan Cheng interval.addRange(LiveRange(RedefIndex, RedefIndex+1, OldValNo)); 4331a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos 43456fdd7af884a35673fb6dd3e01333960922c3ac2Evan Cheng DOUT << " RESULT: "; 4356f0d024a534af18d9e60b3ea757376cd8a3a980eDan Gohman interval.print(DOUT, tri_); 4361a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos 4371a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos } else { 4381a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // Otherwise, this must be because of phi elimination. If this is the 4391a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // first redefinition of the vreg that we have seen, go back and change 4401a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // the live range in the PHI block to be a different value number. 4411a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos if (interval.containsOneValue()) { 4421a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos assert(vi.Kills.size() == 1 && 4431a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos "PHI elimination vreg should have one kill, the PHI itself!"); 4441a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos 4451a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // Remove the old range that we now know has an incorrect number. 446f3bb2e65d12857f83b273f4ecab013680310bbbcEvan Cheng VNInfo *VNI = interval.getValNumInfo(0); 4471a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos MachineInstr *Killer = vi.Kills[0]; 448428b92eb83b457b71d29d1d4b7900d36a0ce9a53Chris Lattner unsigned Start = getMBBStartIdx(Killer->getParent()); 4491a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos unsigned End = getUseIndex(getInstructionIndex(Killer))+1; 45056fdd7af884a35673fb6dd3e01333960922c3ac2Evan Cheng DOUT << " Removing [" << Start << "," << End << "] from: "; 4516f0d024a534af18d9e60b3ea757376cd8a3a980eDan Gohman interval.print(DOUT, tri_); DOUT << "\n"; 4521a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos interval.removeRange(Start, End); 453c3fc7d9ec9b495c8a88cd854247105c296d3aabdEvan Cheng VNI->hasPHIKill = true; 4546f0d024a534af18d9e60b3ea757376cd8a3a980eDan Gohman DOUT << " RESULT: "; interval.print(DOUT, tri_); 4551a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos 456be4f88a8b8bb3311e0dc4cde8533763d7923c3eaChris Lattner // Replace the interval with one of a NEW value number. Note that this 457be4f88a8b8bb3311e0dc4cde8533763d7923c3eaChris Lattner // value number isn't actually defined by an instruction, weird huh? :) 458f3bb2e65d12857f83b273f4ecab013680310bbbcEvan Cheng LiveRange LR(Start, End, interval.getNextValue(~0, 0, VNInfoAllocator)); 459bdc679d564e67a81792e463f6614b0088f975025Bill Wendling DOUT << " replace range with " << LR; 4601a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos interval.addRange(LR); 461f3bb2e65d12857f83b273f4ecab013680310bbbcEvan Cheng interval.addKill(LR.valno, End); 4626f0d024a534af18d9e60b3ea757376cd8a3a980eDan Gohman DOUT << " RESULT: "; interval.print(DOUT, tri_); 4631a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos } 4641a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos 4651a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // In the case of PHI elimination, each variable definition is only 4661a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // live until the end of the block. We've already taken care of the 4671a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // rest of the live range. 4686b128bdc58a496e9f08e4d09416330320761baffChris Lattner unsigned defIndex = getDefIndex(MIIdx); 46991725b75852443923b419fd23215194cfc65dd88Chris Lattner 4707ecb38be0a533e7b9c7d3b8e9b5c8a6fa5f6b349Evan Cheng VNInfo *ValNo; 471c8d044e4f779fdcfc5e7d592927740fd8f672a70Evan Cheng MachineInstr *CopyMI = NULL; 47291725b75852443923b419fd23215194cfc65dd88Chris Lattner unsigned SrcReg, DstReg; 473c8d044e4f779fdcfc5e7d592927740fd8f672a70Evan Cheng if (mi->getOpcode() == TargetInstrInfo::EXTRACT_SUBREG || 4747e073baedb8232b9519dbe15ea141ff98ccfe6aeEvan Cheng mi->getOpcode() == TargetInstrInfo::INSERT_SUBREG || 475c8d044e4f779fdcfc5e7d592927740fd8f672a70Evan Cheng tii_->isMoveInstr(*mi, SrcReg, DstReg)) 476c8d044e4f779fdcfc5e7d592927740fd8f672a70Evan Cheng CopyMI = mi; 477c8d044e4f779fdcfc5e7d592927740fd8f672a70Evan Cheng ValNo = interval.getNextValue(defIndex, CopyMI, VNInfoAllocator); 47891725b75852443923b419fd23215194cfc65dd88Chris Lattner 47929b039976fd682716c6b8ed1cb7084226b2ad84bOwen Anderson unsigned killIndex = getInstructionIndex(&mbb->back()) + InstrSlots::NUM; 4807ecb38be0a533e7b9c7d3b8e9b5c8a6fa5f6b349Evan Cheng LiveRange LR(defIndex, killIndex, ValNo); 4811a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos interval.addRange(LR); 482c3fc7d9ec9b495c8a88cd854247105c296d3aabdEvan Cheng interval.addKill(ValNo, killIndex); 483c3fc7d9ec9b495c8a88cd854247105c296d3aabdEvan Cheng ValNo->hasPHIKill = true; 484bdc679d564e67a81792e463f6614b0088f975025Bill Wendling DOUT << " +" << LR; 485dd2cc65f34f9b7bfda1cd0c42becedfc361d46f8Alkis Evlogimenos } 4861a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos } 487ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos 488bdc679d564e67a81792e463f6614b0088f975025Bill Wendling DOUT << '\n'; 489ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos} 490ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos 491f35fef7060c465dd7b578bf6339a18e8a8911888Chris Lattnervoid LiveIntervals::handlePhysicalRegisterDef(MachineBasicBlock *MBB, 492ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos MachineBasicBlock::iterator mi, 4936b128bdc58a496e9f08e4d09416330320761baffChris Lattner unsigned MIIdx, 4946b098dee286cc6fe5a5a476464d92dec5602e406Owen Anderson MachineOperand& MO, 49591725b75852443923b419fd23215194cfc65dd88Chris Lattner LiveInterval &interval, 496c8d044e4f779fdcfc5e7d592927740fd8f672a70Evan Cheng MachineInstr *CopyMI) { 4971a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // A physical register cannot be live across basic block, so its 4981a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // lifetime must end somewhere in its defining basic block. 499bdc679d564e67a81792e463f6614b0088f975025Bill Wendling DOUT << "\t\tregister: "; DEBUG(printRegName(interval.reg)); 5001a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos 5016b128bdc58a496e9f08e4d09416330320761baffChris Lattner unsigned baseIndex = MIIdx; 5021a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos unsigned start = getDefIndex(baseIndex); 5031a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos unsigned end = start; 5041a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos 5051a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // If it is not used after definition, it is considered dead at 5061a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // the instruction defining it. Hence its interval is: 5071a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // [defSlot(def), defSlot(def)+1) 5086b098dee286cc6fe5a5a476464d92dec5602e406Owen Anderson if (MO.isDead()) { 509bdc679d564e67a81792e463f6614b0088f975025Bill Wendling DOUT << " dead"; 510ab4b66d4c279e8cd9e448687020fc838e7881dbcChris Lattner end = getDefIndex(start) + 1; 511ab4b66d4c279e8cd9e448687020fc838e7881dbcChris Lattner goto exit; 5121a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos } 513ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos 5141a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // If it is not dead on definition, it must be killed by a 5151a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // subsequent instruction. Hence its interval is: 5161a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // [defSlot(def), useSlot(kill)+1) 5175ab6f5fe666d0e3403d9b777324d1a1999118153Chris Lattner while (++mi != MBB->end()) { 51829b039976fd682716c6b8ed1cb7084226b2ad84bOwen Anderson baseIndex += InstrSlots::NUM; 5196130f66eaae89f8878590796977678afa8448926Evan Cheng if (mi->killsRegister(interval.reg, tri_)) { 520bdc679d564e67a81792e463f6614b0088f975025Bill Wendling DOUT << " killed"; 521ab4b66d4c279e8cd9e448687020fc838e7881dbcChris Lattner end = getUseIndex(baseIndex) + 1; 522ab4b66d4c279e8cd9e448687020fc838e7881dbcChris Lattner goto exit; 5236130f66eaae89f8878590796977678afa8448926Evan Cheng } else if (mi->modifiesRegister(interval.reg, tri_)) { 5249a1956ae6ad2d4892afbc9f1b97d645d220b6d4aEvan Cheng // Another instruction redefines the register before it is ever read. 5259a1956ae6ad2d4892afbc9f1b97d645d220b6d4aEvan Cheng // Then the register is essentially dead at the instruction that defines 5269a1956ae6ad2d4892afbc9f1b97d645d220b6d4aEvan Cheng // it. Hence its interval is: 5279a1956ae6ad2d4892afbc9f1b97d645d220b6d4aEvan Cheng // [defSlot(def), defSlot(def)+1) 528bdc679d564e67a81792e463f6614b0088f975025Bill Wendling DOUT << " dead"; 5299a1956ae6ad2d4892afbc9f1b97d645d220b6d4aEvan Cheng end = getDefIndex(start) + 1; 5309a1956ae6ad2d4892afbc9f1b97d645d220b6d4aEvan Cheng goto exit; 531f35fef7060c465dd7b578bf6339a18e8a8911888Chris Lattner } 5321a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos } 5335ab6f5fe666d0e3403d9b777324d1a1999118153Chris Lattner 5345ab6f5fe666d0e3403d9b777324d1a1999118153Chris Lattner // The only case we should have a dead physreg here without a killing or 5355ab6f5fe666d0e3403d9b777324d1a1999118153Chris Lattner // instruction where we know it's dead is if it is live-in to the function 5365ab6f5fe666d0e3403d9b777324d1a1999118153Chris Lattner // and never used. 537c8d044e4f779fdcfc5e7d592927740fd8f672a70Evan Cheng assert(!CopyMI && "physreg was not killed in defining block!"); 5385ab6f5fe666d0e3403d9b777324d1a1999118153Chris Lattner end = getDefIndex(start) + 1; // It's dead. 53902ba13c9897ae2b19f9201e57460d7ee2b753a0bAlkis Evlogimenos 540ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenosexit: 5411a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos assert(start < end && "did not find end of interval?"); 542f768bba43f5c036039851d2fcca8212edca18467Chris Lattner 54324a3cc4c83e5edb25fadf7b8979a26b4451795c6Evan Cheng // Already exists? Extend old live interval. 54424a3cc4c83e5edb25fadf7b8979a26b4451795c6Evan Cheng LiveInterval::iterator OldLR = interval.FindLiveRangeContaining(start); 5457ecb38be0a533e7b9c7d3b8e9b5c8a6fa5f6b349Evan Cheng VNInfo *ValNo = (OldLR != interval.end()) 546c8d044e4f779fdcfc5e7d592927740fd8f672a70Evan Cheng ? OldLR->valno : interval.getNextValue(start, CopyMI, VNInfoAllocator); 5477ecb38be0a533e7b9c7d3b8e9b5c8a6fa5f6b349Evan Cheng LiveRange LR(start, end, ValNo); 5481a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos interval.addRange(LR); 549f3bb2e65d12857f83b273f4ecab013680310bbbcEvan Cheng interval.addKill(LR.valno, end); 550bdc679d564e67a81792e463f6614b0088f975025Bill Wendling DOUT << " +" << LR << '\n'; 551ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos} 552ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos 553f35fef7060c465dd7b578bf6339a18e8a8911888Chris Lattnervoid LiveIntervals::handleRegisterDef(MachineBasicBlock *MBB, 554f35fef7060c465dd7b578bf6339a18e8a8911888Chris Lattner MachineBasicBlock::iterator MI, 5556b128bdc58a496e9f08e4d09416330320761baffChris Lattner unsigned MIIdx, 5566b098dee286cc6fe5a5a476464d92dec5602e406Owen Anderson MachineOperand& MO) { 5576b098dee286cc6fe5a5a476464d92dec5602e406Owen Anderson if (TargetRegisterInfo::isVirtualRegister(MO.getReg())) 5586b098dee286cc6fe5a5a476464d92dec5602e406Owen Anderson handleVirtualRegisterDef(MBB, MI, MIIdx, MO, 5596b098dee286cc6fe5a5a476464d92dec5602e406Owen Anderson getOrCreateInterval(MO.getReg())); 5606b098dee286cc6fe5a5a476464d92dec5602e406Owen Anderson else if (allocatableRegs_[MO.getReg()]) { 561c8d044e4f779fdcfc5e7d592927740fd8f672a70Evan Cheng MachineInstr *CopyMI = NULL; 56291725b75852443923b419fd23215194cfc65dd88Chris Lattner unsigned SrcReg, DstReg; 563c8d044e4f779fdcfc5e7d592927740fd8f672a70Evan Cheng if (MI->getOpcode() == TargetInstrInfo::EXTRACT_SUBREG || 5647e073baedb8232b9519dbe15ea141ff98ccfe6aeEvan Cheng MI->getOpcode() == TargetInstrInfo::INSERT_SUBREG || 565c8d044e4f779fdcfc5e7d592927740fd8f672a70Evan Cheng tii_->isMoveInstr(*MI, SrcReg, DstReg)) 566c8d044e4f779fdcfc5e7d592927740fd8f672a70Evan Cheng CopyMI = MI; 5676b098dee286cc6fe5a5a476464d92dec5602e406Owen Anderson handlePhysicalRegisterDef(MBB, MI, MIIdx, MO, 5686b098dee286cc6fe5a5a476464d92dec5602e406Owen Anderson getOrCreateInterval(MO.getReg()), CopyMI); 56924a3cc4c83e5edb25fadf7b8979a26b4451795c6Evan Cheng // Def of a register also defines its sub-registers. 5706b098dee286cc6fe5a5a476464d92dec5602e406Owen Anderson for (const unsigned* AS = tri_->getSubRegisters(MO.getReg()); *AS; ++AS) 5716130f66eaae89f8878590796977678afa8448926Evan Cheng // If MI also modifies the sub-register explicitly, avoid processing it 5726130f66eaae89f8878590796977678afa8448926Evan Cheng // more than once. Do not pass in TRI here so it checks for exact match. 5736130f66eaae89f8878590796977678afa8448926Evan Cheng if (!MI->modifiesRegister(*AS)) 5746b098dee286cc6fe5a5a476464d92dec5602e406Owen Anderson handlePhysicalRegisterDef(MBB, MI, MIIdx, MO, 5756b098dee286cc6fe5a5a476464d92dec5602e406Owen Anderson getOrCreateInterval(*AS), 0); 576f35fef7060c465dd7b578bf6339a18e8a8911888Chris Lattner } 5774d46e1e521c0df1990ea50f8146d22bd77ea71a6Alkis Evlogimenos} 5784d46e1e521c0df1990ea50f8146d22bd77ea71a6Alkis Evlogimenos 579b371f457b0ea4a652a9f526ba4375c80ae542252Evan Chengvoid LiveIntervals::handleLiveInRegister(MachineBasicBlock *MBB, 5809b25b8ca24d6df2e097741dcc15016772ee4eda7Jim Laskey unsigned MIIdx, 58124a3cc4c83e5edb25fadf7b8979a26b4451795c6Evan Cheng LiveInterval &interval, bool isAlias) { 582b371f457b0ea4a652a9f526ba4375c80ae542252Evan Cheng DOUT << "\t\tlivein register: "; DEBUG(printRegName(interval.reg)); 583b371f457b0ea4a652a9f526ba4375c80ae542252Evan Cheng 584b371f457b0ea4a652a9f526ba4375c80ae542252Evan Cheng // Look for kills, if it reaches a def before it's killed, then it shouldn't 585b371f457b0ea4a652a9f526ba4375c80ae542252Evan Cheng // be considered a livein. 586b371f457b0ea4a652a9f526ba4375c80ae542252Evan Cheng MachineBasicBlock::iterator mi = MBB->begin(); 5879b25b8ca24d6df2e097741dcc15016772ee4eda7Jim Laskey unsigned baseIndex = MIIdx; 5889b25b8ca24d6df2e097741dcc15016772ee4eda7Jim Laskey unsigned start = baseIndex; 589b371f457b0ea4a652a9f526ba4375c80ae542252Evan Cheng unsigned end = start; 590b371f457b0ea4a652a9f526ba4375c80ae542252Evan Cheng while (mi != MBB->end()) { 5916130f66eaae89f8878590796977678afa8448926Evan Cheng if (mi->killsRegister(interval.reg, tri_)) { 592b371f457b0ea4a652a9f526ba4375c80ae542252Evan Cheng DOUT << " killed"; 593b371f457b0ea4a652a9f526ba4375c80ae542252Evan Cheng end = getUseIndex(baseIndex) + 1; 594b371f457b0ea4a652a9f526ba4375c80ae542252Evan Cheng goto exit; 5956130f66eaae89f8878590796977678afa8448926Evan Cheng } else if (mi->modifiesRegister(interval.reg, tri_)) { 596b371f457b0ea4a652a9f526ba4375c80ae542252Evan Cheng // Another instruction redefines the register before it is ever read. 597b371f457b0ea4a652a9f526ba4375c80ae542252Evan Cheng // Then the register is essentially dead at the instruction that defines 598b371f457b0ea4a652a9f526ba4375c80ae542252Evan Cheng // it. Hence its interval is: 599b371f457b0ea4a652a9f526ba4375c80ae542252Evan Cheng // [defSlot(def), defSlot(def)+1) 600b371f457b0ea4a652a9f526ba4375c80ae542252Evan Cheng DOUT << " dead"; 601b371f457b0ea4a652a9f526ba4375c80ae542252Evan Cheng end = getDefIndex(start) + 1; 602b371f457b0ea4a652a9f526ba4375c80ae542252Evan Cheng goto exit; 603b371f457b0ea4a652a9f526ba4375c80ae542252Evan Cheng } 604b371f457b0ea4a652a9f526ba4375c80ae542252Evan Cheng 605b371f457b0ea4a652a9f526ba4375c80ae542252Evan Cheng baseIndex += InstrSlots::NUM; 606b371f457b0ea4a652a9f526ba4375c80ae542252Evan Cheng ++mi; 607b371f457b0ea4a652a9f526ba4375c80ae542252Evan Cheng } 608b371f457b0ea4a652a9f526ba4375c80ae542252Evan Cheng 609b371f457b0ea4a652a9f526ba4375c80ae542252Evan Chengexit: 61075611fb4e6ab253be30ac29a2b15e9bf8c1d146eEvan Cheng // Live-in register might not be used at all. 61175611fb4e6ab253be30ac29a2b15e9bf8c1d146eEvan Cheng if (end == MIIdx) { 612292da949f6c87d6499425d64d37d7c5870ec57adEvan Cheng if (isAlias) { 613292da949f6c87d6499425d64d37d7c5870ec57adEvan Cheng DOUT << " dead"; 61475611fb4e6ab253be30ac29a2b15e9bf8c1d146eEvan Cheng end = getDefIndex(MIIdx) + 1; 615292da949f6c87d6499425d64d37d7c5870ec57adEvan Cheng } else { 616292da949f6c87d6499425d64d37d7c5870ec57adEvan Cheng DOUT << " live through"; 617292da949f6c87d6499425d64d37d7c5870ec57adEvan Cheng end = baseIndex; 618292da949f6c87d6499425d64d37d7c5870ec57adEvan Cheng } 61924a3cc4c83e5edb25fadf7b8979a26b4451795c6Evan Cheng } 62024a3cc4c83e5edb25fadf7b8979a26b4451795c6Evan Cheng 621f3bb2e65d12857f83b273f4ecab013680310bbbcEvan Cheng LiveRange LR(start, end, interval.getNextValue(start, 0, VNInfoAllocator)); 6229b25b8ca24d6df2e097741dcc15016772ee4eda7Jim Laskey interval.addRange(LR); 623f3bb2e65d12857f83b273f4ecab013680310bbbcEvan Cheng interval.addKill(LR.valno, end); 62424c2e5cf7e926452ea5875d027ec0d24d9c19e39Evan Cheng DOUT << " +" << LR << '\n'; 625b371f457b0ea4a652a9f526ba4375c80ae542252Evan Cheng} 626b371f457b0ea4a652a9f526ba4375c80ae542252Evan Cheng 627ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos/// computeIntervals - computes the live intervals for virtual 6284d46e1e521c0df1990ea50f8146d22bd77ea71a6Alkis Evlogimenos/// registers. for some ordering of the machine instructions [1,N] a 62908cec00588ec1a8fa85b208555f006d7396ae7a4Alkis Evlogimenos/// live interval is an interval [i, j) where 1 <= i <= j < N for 630ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos/// which a variable is live 631f7da2c7b0c6293c268881628fc351bed7763f1f4Chris Lattnervoid LiveIntervals::computeIntervals() { 632bdc679d564e67a81792e463f6614b0088f975025Bill Wendling DOUT << "********** COMPUTING LIVE INTERVALS **********\n" 633bdc679d564e67a81792e463f6614b0088f975025Bill Wendling << "********** Function: " 634bdc679d564e67a81792e463f6614b0088f975025Bill Wendling << ((Value*)mf_->getFunction())->getName() << '\n'; 6356b128bdc58a496e9f08e4d09416330320761baffChris Lattner // Track the index of the current machine instr. 6366b128bdc58a496e9f08e4d09416330320761baffChris Lattner unsigned MIIndex = 0; 637428b92eb83b457b71d29d1d4b7900d36a0ce9a53Chris Lattner for (MachineFunction::iterator MBBI = mf_->begin(), E = mf_->end(); 638428b92eb83b457b71d29d1d4b7900d36a0ce9a53Chris Lattner MBBI != E; ++MBBI) { 639428b92eb83b457b71d29d1d4b7900d36a0ce9a53Chris Lattner MachineBasicBlock *MBB = MBBI; 640bdc679d564e67a81792e463f6614b0088f975025Bill Wendling DOUT << ((Value*)MBB->getBasicBlock())->getName() << ":\n"; 6411a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos 642428b92eb83b457b71d29d1d4b7900d36a0ce9a53Chris Lattner MachineBasicBlock::iterator MI = MBB->begin(), miEnd = MBB->end(); 6430c9f92e1ff64ee56724eae444a0442b02f83d0a8Evan Cheng 644cb406c25973b4e88a6c10ad839ef1beeb3664715Dan Gohman // Create intervals for live-ins to this BB first. 645cb406c25973b4e88a6c10ad839ef1beeb3664715Dan Gohman for (MachineBasicBlock::const_livein_iterator LI = MBB->livein_begin(), 646cb406c25973b4e88a6c10ad839ef1beeb3664715Dan Gohman LE = MBB->livein_end(); LI != LE; ++LI) { 647cb406c25973b4e88a6c10ad839ef1beeb3664715Dan Gohman handleLiveInRegister(MBB, MIIndex, getOrCreateInterval(*LI)); 648cb406c25973b4e88a6c10ad839ef1beeb3664715Dan Gohman // Multiple live-ins can alias the same register. 6496f0d024a534af18d9e60b3ea757376cd8a3a980eDan Gohman for (const unsigned* AS = tri_->getSubRegisters(*LI); *AS; ++AS) 650cb406c25973b4e88a6c10ad839ef1beeb3664715Dan Gohman if (!hasInterval(*AS)) 651cb406c25973b4e88a6c10ad839ef1beeb3664715Dan Gohman handleLiveInRegister(MBB, MIIndex, getOrCreateInterval(*AS), 652cb406c25973b4e88a6c10ad839ef1beeb3664715Dan Gohman true); 653dffb2e83ed2546226d09c40aa43524e2392322daChris Lattner } 654dffb2e83ed2546226d09c40aa43524e2392322daChris Lattner 655428b92eb83b457b71d29d1d4b7900d36a0ce9a53Chris Lattner for (; MI != miEnd; ++MI) { 656bdc679d564e67a81792e463f6614b0088f975025Bill Wendling DOUT << MIIndex << "\t" << *MI; 6571a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos 658438f7bc67cf235ccee7e6f7ac7f4ae2186eb8020Evan Cheng // Handle defs. 659428b92eb83b457b71d29d1d4b7900d36a0ce9a53Chris Lattner for (int i = MI->getNumOperands() - 1; i >= 0; --i) { 660428b92eb83b457b71d29d1d4b7900d36a0ce9a53Chris Lattner MachineOperand &MO = MI->getOperand(i); 6611a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos // handle register defs - build intervals 662428b92eb83b457b71d29d1d4b7900d36a0ce9a53Chris Lattner if (MO.isRegister() && MO.getReg() && MO.isDef()) 6636b098dee286cc6fe5a5a476464d92dec5602e406Owen Anderson handleRegisterDef(MBB, MI, MIIndex, MO); 6641a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos } 6656b128bdc58a496e9f08e4d09416330320761baffChris Lattner 6666b128bdc58a496e9f08e4d09416330320761baffChris Lattner MIIndex += InstrSlots::NUM; 667ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos } 66829b039976fd682716c6b8ed1cb7084226b2ad84bOwen Anderson 66929b039976fd682716c6b8ed1cb7084226b2ad84bOwen Anderson if (MBB->begin() == miEnd) MIIndex += InstrSlots::NUM; // Empty MBB 6701a8ea01f01b30e28e4e3ac0e3a344c4a4d579270Alkis Evlogimenos } 671ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos} 672b27ef248f579b354aab434f63c417ab1103e47e2Alkis Evlogimenos 6734ca980e7f9ce7b78955307c2d07001a24d3b6befEvan Chengbool LiveIntervals::findLiveInMBBs(const LiveRange &LR, 674a5bfc97da713ec9e185226d44e6adb4d3087b304Evan Cheng SmallVectorImpl<MachineBasicBlock*> &MBBs) const { 6754ca980e7f9ce7b78955307c2d07001a24d3b6befEvan Cheng std::vector<IdxMBBPair>::const_iterator I = 6764ca980e7f9ce7b78955307c2d07001a24d3b6befEvan Cheng std::lower_bound(Idx2MBBMap.begin(), Idx2MBBMap.end(), LR.start); 6774ca980e7f9ce7b78955307c2d07001a24d3b6befEvan Cheng 6784ca980e7f9ce7b78955307c2d07001a24d3b6befEvan Cheng bool ResVal = false; 6794ca980e7f9ce7b78955307c2d07001a24d3b6befEvan Cheng while (I != Idx2MBBMap.end()) { 6804ca980e7f9ce7b78955307c2d07001a24d3b6befEvan Cheng if (LR.end <= I->first) 6814ca980e7f9ce7b78955307c2d07001a24d3b6befEvan Cheng break; 6824ca980e7f9ce7b78955307c2d07001a24d3b6befEvan Cheng MBBs.push_back(I->second); 6834ca980e7f9ce7b78955307c2d07001a24d3b6befEvan Cheng ResVal = true; 6844ca980e7f9ce7b78955307c2d07001a24d3b6befEvan Cheng ++I; 6854ca980e7f9ce7b78955307c2d07001a24d3b6befEvan Cheng } 6864ca980e7f9ce7b78955307c2d07001a24d3b6befEvan Cheng return ResVal; 6874ca980e7f9ce7b78955307c2d07001a24d3b6befEvan Cheng} 6884ca980e7f9ce7b78955307c2d07001a24d3b6befEvan Cheng 6894ca980e7f9ce7b78955307c2d07001a24d3b6befEvan Cheng 690a1613db62fec94845aa8306232fb665273615badAlkis EvlogimenosLiveInterval LiveIntervals::createInterval(unsigned reg) { 6916f0d024a534af18d9e60b3ea757376cd8a3a980eDan Gohman float Weight = TargetRegisterInfo::isPhysicalRegister(reg) ? 6927902c75331fa8f38fc8380f5573d935c0d149ef5Jim Laskey HUGE_VALF : 0.0F; 693a1613db62fec94845aa8306232fb665273615badAlkis Evlogimenos return LiveInterval(reg, Weight); 6949a8b490735d216435862a3d52e669357f165550fAlkis Evlogimenos} 695f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng 696c8d044e4f779fdcfc5e7d592927740fd8f672a70Evan Cheng/// getVNInfoSourceReg - Helper function that parses the specified VNInfo 697c8d044e4f779fdcfc5e7d592927740fd8f672a70Evan Cheng/// copy field and returns the source register that defines it. 698c8d044e4f779fdcfc5e7d592927740fd8f672a70Evan Chengunsigned LiveIntervals::getVNInfoSourceReg(const VNInfo *VNI) const { 699c8d044e4f779fdcfc5e7d592927740fd8f672a70Evan Cheng if (!VNI->copy) 700c8d044e4f779fdcfc5e7d592927740fd8f672a70Evan Cheng return 0; 701c8d044e4f779fdcfc5e7d592927740fd8f672a70Evan Cheng 702c8d044e4f779fdcfc5e7d592927740fd8f672a70Evan Cheng if (VNI->copy->getOpcode() == TargetInstrInfo::EXTRACT_SUBREG) 703c8d044e4f779fdcfc5e7d592927740fd8f672a70Evan Cheng return VNI->copy->getOperand(1).getReg(); 7047e073baedb8232b9519dbe15ea141ff98ccfe6aeEvan Cheng if (VNI->copy->getOpcode() == TargetInstrInfo::INSERT_SUBREG) 7057e073baedb8232b9519dbe15ea141ff98ccfe6aeEvan Cheng return VNI->copy->getOperand(2).getReg(); 706c8d044e4f779fdcfc5e7d592927740fd8f672a70Evan Cheng unsigned SrcReg, DstReg; 707c8d044e4f779fdcfc5e7d592927740fd8f672a70Evan Cheng if (tii_->isMoveInstr(*VNI->copy, SrcReg, DstReg)) 708c8d044e4f779fdcfc5e7d592927740fd8f672a70Evan Cheng return SrcReg; 709c8d044e4f779fdcfc5e7d592927740fd8f672a70Evan Cheng assert(0 && "Unrecognized copy instruction!"); 710c8d044e4f779fdcfc5e7d592927740fd8f672a70Evan Cheng return 0; 711c8d044e4f779fdcfc5e7d592927740fd8f672a70Evan Cheng} 712f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng 713f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng//===----------------------------------------------------------------------===// 714f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng// Register allocator hooks. 715f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng// 716f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng 717d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng/// getReMatImplicitUse - If the remat definition MI has one (for now, we only 718d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng/// allow one) virtual register operand, then its uses are implicitly using 719d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng/// the register. Returns the virtual register. 720d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Chengunsigned LiveIntervals::getReMatImplicitUse(const LiveInterval &li, 721d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng MachineInstr *MI) const { 722d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng unsigned RegOp = 0; 723d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) { 724d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng MachineOperand &MO = MI->getOperand(i); 725d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng if (!MO.isRegister() || !MO.isUse()) 726d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng continue; 727d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng unsigned Reg = MO.getReg(); 728d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng if (Reg == 0 || Reg == li.reg) 729d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng continue; 730d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng // FIXME: For now, only remat MI with at most one register operand. 731d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng assert(!RegOp && 732d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng "Can't rematerialize instruction with multiple register operand!"); 733d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng RegOp = MO.getReg(); 734d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng break; 735d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng } 736d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng return RegOp; 737d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng} 738d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng 739d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng/// isValNoAvailableAt - Return true if the val# of the specified interval 740d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng/// which reaches the given instruction also reaches the specified use index. 741d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Chengbool LiveIntervals::isValNoAvailableAt(const LiveInterval &li, MachineInstr *MI, 742d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng unsigned UseIdx) const { 743d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng unsigned Index = getInstructionIndex(MI); 744d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng VNInfo *ValNo = li.FindLiveRangeContaining(Index)->valno; 745d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng LiveInterval::const_iterator UI = li.FindLiveRangeContaining(UseIdx); 746d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng return UI != li.end() && UI->valno == ValNo; 747d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng} 748d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng 749f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng/// isReMaterializable - Returns true if the definition MI of the specified 750f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng/// val# of the specified interval is re-materializable. 751f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Chengbool LiveIntervals::isReMaterializable(const LiveInterval &li, 7525ef3a04b542c4e585276768fa9ca2af698ef5c87Evan Cheng const VNInfo *ValNo, MachineInstr *MI, 7535ef3a04b542c4e585276768fa9ca2af698ef5c87Evan Cheng bool &isLoad) { 754f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng if (DisableReMat) 755f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng return false; 756f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng 7575ef3a04b542c4e585276768fa9ca2af698ef5c87Evan Cheng isLoad = false; 75820ccded7dec5b90e58f649f4fb95b166a642b8cbEvan Cheng if (MI->getOpcode() == TargetInstrInfo::IMPLICIT_DEF) 759d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng return true; 760dd3465eed17cdf226bdb465e604dfa851d36029dEvan Cheng 761dd3465eed17cdf226bdb465e604dfa851d36029dEvan Cheng int FrameIdx = 0; 762dd3465eed17cdf226bdb465e604dfa851d36029dEvan Cheng if (tii_->isLoadFromStackSlot(MI, FrameIdx) && 763249ded3fa8884f91fded869fb6e251b8aebb0376Evan Cheng mf_->getFrameInfo()->isImmutableObjectIndex(FrameIdx)) 76479a0c1e46c4f7d8a2a06f4ef3e2c54d883c7fe25Evan Cheng // FIXME: Let target specific isReallyTriviallyReMaterializable determines 76579a0c1e46c4f7d8a2a06f4ef3e2c54d883c7fe25Evan Cheng // this but remember this is not safe to fold into a two-address 76679a0c1e46c4f7d8a2a06f4ef3e2c54d883c7fe25Evan Cheng // instruction. 767249ded3fa8884f91fded869fb6e251b8aebb0376Evan Cheng // This is a load from fixed stack slot. It can be rematerialized. 768dd3465eed17cdf226bdb465e604dfa851d36029dEvan Cheng return true; 769dd3465eed17cdf226bdb465e604dfa851d36029dEvan Cheng 770d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng if (tii_->isTriviallyReMaterializable(MI)) { 77120ccded7dec5b90e58f649f4fb95b166a642b8cbEvan Cheng const TargetInstrDesc &TID = MI->getDesc(); 772749c6f6b5ed301c84aac562e414486549d7b98ebChris Lattner isLoad = TID.isSimpleLoad(); 773d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng 774d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng unsigned ImpUse = getReMatImplicitUse(li, MI); 775d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng if (ImpUse) { 776d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng const LiveInterval &ImpLi = getInterval(ImpUse); 777d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng for (MachineRegisterInfo::use_iterator ri = mri_->use_begin(li.reg), 778d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng re = mri_->use_end(); ri != re; ++ri) { 779d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng MachineInstr *UseMI = &*ri; 780d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng unsigned UseIdx = getInstructionIndex(UseMI); 781d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng if (li.FindLiveRangeContaining(UseIdx)->valno != ValNo) 782d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng continue; 783298bbe82cb390235f7b8ab4bd550feff909e0c3dEvan Cheng if (!isValNoAvailableAt(ImpLi, MI, UseIdx)) 784d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng return false; 785d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng } 786d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng } 787f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng return true; 7885ef3a04b542c4e585276768fa9ca2af698ef5c87Evan Cheng } 789f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng 790dd3465eed17cdf226bdb465e604dfa851d36029dEvan Cheng return false; 7915ef3a04b542c4e585276768fa9ca2af698ef5c87Evan Cheng} 7925ef3a04b542c4e585276768fa9ca2af698ef5c87Evan Cheng 7935ef3a04b542c4e585276768fa9ca2af698ef5c87Evan Cheng/// isReMaterializable - Returns true if every definition of MI of every 7945ef3a04b542c4e585276768fa9ca2af698ef5c87Evan Cheng/// val# of the specified interval is re-materializable. 7955ef3a04b542c4e585276768fa9ca2af698ef5c87Evan Chengbool LiveIntervals::isReMaterializable(const LiveInterval &li, bool &isLoad) { 7965ef3a04b542c4e585276768fa9ca2af698ef5c87Evan Cheng isLoad = false; 7975ef3a04b542c4e585276768fa9ca2af698ef5c87Evan Cheng for (LiveInterval::const_vni_iterator i = li.vni_begin(), e = li.vni_end(); 7985ef3a04b542c4e585276768fa9ca2af698ef5c87Evan Cheng i != e; ++i) { 7995ef3a04b542c4e585276768fa9ca2af698ef5c87Evan Cheng const VNInfo *VNI = *i; 8005ef3a04b542c4e585276768fa9ca2af698ef5c87Evan Cheng unsigned DefIdx = VNI->def; 8015ef3a04b542c4e585276768fa9ca2af698ef5c87Evan Cheng if (DefIdx == ~1U) 8025ef3a04b542c4e585276768fa9ca2af698ef5c87Evan Cheng continue; // Dead val#. 8035ef3a04b542c4e585276768fa9ca2af698ef5c87Evan Cheng // Is the def for the val# rematerializable? 8045ef3a04b542c4e585276768fa9ca2af698ef5c87Evan Cheng if (DefIdx == ~0u) 8055ef3a04b542c4e585276768fa9ca2af698ef5c87Evan Cheng return false; 8065ef3a04b542c4e585276768fa9ca2af698ef5c87Evan Cheng MachineInstr *ReMatDefMI = getInstructionFromIndex(DefIdx); 8075ef3a04b542c4e585276768fa9ca2af698ef5c87Evan Cheng bool DefIsLoad = false; 808d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng if (!ReMatDefMI || 809d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng !isReMaterializable(li, VNI, ReMatDefMI, DefIsLoad)) 810f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng return false; 8115ef3a04b542c4e585276768fa9ca2af698ef5c87Evan Cheng isLoad |= DefIsLoad; 812f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng } 813f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng return true; 814f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng} 815f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng 81679a0c1e46c4f7d8a2a06f4ef3e2c54d883c7fe25Evan Cheng/// FilterFoldedOps - Filter out two-address use operands. Return 81779a0c1e46c4f7d8a2a06f4ef3e2c54d883c7fe25Evan Cheng/// true if it finds any issue with the operands that ought to prevent 81879a0c1e46c4f7d8a2a06f4ef3e2c54d883c7fe25Evan Cheng/// folding. 81979a0c1e46c4f7d8a2a06f4ef3e2c54d883c7fe25Evan Chengstatic bool FilterFoldedOps(MachineInstr *MI, 82079a0c1e46c4f7d8a2a06f4ef3e2c54d883c7fe25Evan Cheng SmallVector<unsigned, 2> &Ops, 82179a0c1e46c4f7d8a2a06f4ef3e2c54d883c7fe25Evan Cheng unsigned &MRInfo, 82279a0c1e46c4f7d8a2a06f4ef3e2c54d883c7fe25Evan Cheng SmallVector<unsigned, 2> &FoldOps) { 823749c6f6b5ed301c84aac562e414486549d7b98ebChris Lattner const TargetInstrDesc &TID = MI->getDesc(); 8246e141fd04897e5eb4925bb6351297170ebd8a756Evan Cheng 82579a0c1e46c4f7d8a2a06f4ef3e2c54d883c7fe25Evan Cheng MRInfo = 0; 826aee4af68ae2016afc5b4ec0c430e539c5810a766Evan Cheng for (unsigned i = 0, e = Ops.size(); i != e; ++i) { 827aee4af68ae2016afc5b4ec0c430e539c5810a766Evan Cheng unsigned OpIdx = Ops[i]; 828d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng MachineOperand &MO = MI->getOperand(OpIdx); 829aee4af68ae2016afc5b4ec0c430e539c5810a766Evan Cheng // FIXME: fold subreg use. 830d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng if (MO.getSubReg()) 83179a0c1e46c4f7d8a2a06f4ef3e2c54d883c7fe25Evan Cheng return true; 832d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng if (MO.isDef()) 833aee4af68ae2016afc5b4ec0c430e539c5810a766Evan Cheng MRInfo |= (unsigned)VirtRegMap::isMod; 834aee4af68ae2016afc5b4ec0c430e539c5810a766Evan Cheng else { 835aee4af68ae2016afc5b4ec0c430e539c5810a766Evan Cheng // Filter out two-address use operand(s). 836d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng if (!MO.isImplicit() && 837d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng TID.getOperandConstraint(OpIdx, TOI::TIED_TO) != -1) { 838aee4af68ae2016afc5b4ec0c430e539c5810a766Evan Cheng MRInfo = VirtRegMap::isModRef; 839aee4af68ae2016afc5b4ec0c430e539c5810a766Evan Cheng continue; 840aee4af68ae2016afc5b4ec0c430e539c5810a766Evan Cheng } 841aee4af68ae2016afc5b4ec0c430e539c5810a766Evan Cheng MRInfo |= (unsigned)VirtRegMap::isRef; 842aee4af68ae2016afc5b4ec0c430e539c5810a766Evan Cheng } 843aee4af68ae2016afc5b4ec0c430e539c5810a766Evan Cheng FoldOps.push_back(OpIdx); 844e62f97c094dba44e4c259d20135167fa91912eeaEvan Cheng } 84579a0c1e46c4f7d8a2a06f4ef3e2c54d883c7fe25Evan Cheng return false; 84679a0c1e46c4f7d8a2a06f4ef3e2c54d883c7fe25Evan Cheng} 84779a0c1e46c4f7d8a2a06f4ef3e2c54d883c7fe25Evan Cheng 84879a0c1e46c4f7d8a2a06f4ef3e2c54d883c7fe25Evan Cheng 84979a0c1e46c4f7d8a2a06f4ef3e2c54d883c7fe25Evan Cheng/// tryFoldMemoryOperand - Attempts to fold either a spill / restore from 85079a0c1e46c4f7d8a2a06f4ef3e2c54d883c7fe25Evan Cheng/// slot / to reg or any rematerialized load into ith operand of specified 85179a0c1e46c4f7d8a2a06f4ef3e2c54d883c7fe25Evan Cheng/// MI. If it is successul, MI is updated with the newly created MI and 85279a0c1e46c4f7d8a2a06f4ef3e2c54d883c7fe25Evan Cheng/// returns true. 85379a0c1e46c4f7d8a2a06f4ef3e2c54d883c7fe25Evan Chengbool LiveIntervals::tryFoldMemoryOperand(MachineInstr* &MI, 85479a0c1e46c4f7d8a2a06f4ef3e2c54d883c7fe25Evan Cheng VirtRegMap &vrm, MachineInstr *DefMI, 85579a0c1e46c4f7d8a2a06f4ef3e2c54d883c7fe25Evan Cheng unsigned InstrIdx, 85679a0c1e46c4f7d8a2a06f4ef3e2c54d883c7fe25Evan Cheng SmallVector<unsigned, 2> &Ops, 85779a0c1e46c4f7d8a2a06f4ef3e2c54d883c7fe25Evan Cheng bool isSS, int Slot, unsigned Reg) { 85879a0c1e46c4f7d8a2a06f4ef3e2c54d883c7fe25Evan Cheng // If it is an implicit def instruction, just delete it. 85920ccded7dec5b90e58f649f4fb95b166a642b8cbEvan Cheng if (MI->getOpcode() == TargetInstrInfo::IMPLICIT_DEF) { 86079a0c1e46c4f7d8a2a06f4ef3e2c54d883c7fe25Evan Cheng RemoveMachineInstrFromMaps(MI); 86179a0c1e46c4f7d8a2a06f4ef3e2c54d883c7fe25Evan Cheng vrm.RemoveMachineInstrFromMaps(MI); 86279a0c1e46c4f7d8a2a06f4ef3e2c54d883c7fe25Evan Cheng MI->eraseFromParent(); 86379a0c1e46c4f7d8a2a06f4ef3e2c54d883c7fe25Evan Cheng ++numFolds; 86479a0c1e46c4f7d8a2a06f4ef3e2c54d883c7fe25Evan Cheng return true; 86579a0c1e46c4f7d8a2a06f4ef3e2c54d883c7fe25Evan Cheng } 86679a0c1e46c4f7d8a2a06f4ef3e2c54d883c7fe25Evan Cheng 86779a0c1e46c4f7d8a2a06f4ef3e2c54d883c7fe25Evan Cheng // Filter the list of operand indexes that are to be folded. Abort if 86879a0c1e46c4f7d8a2a06f4ef3e2c54d883c7fe25Evan Cheng // any operand will prevent folding. 86979a0c1e46c4f7d8a2a06f4ef3e2c54d883c7fe25Evan Cheng unsigned MRInfo = 0; 87079a0c1e46c4f7d8a2a06f4ef3e2c54d883c7fe25Evan Cheng SmallVector<unsigned, 2> FoldOps; 87179a0c1e46c4f7d8a2a06f4ef3e2c54d883c7fe25Evan Cheng if (FilterFoldedOps(MI, Ops, MRInfo, FoldOps)) 87279a0c1e46c4f7d8a2a06f4ef3e2c54d883c7fe25Evan Cheng return false; 873cddbb83ea82e98658d9f530c50a7b9d23249afc2Evan Cheng 874427f4c106ac14dcf323dc1bbaf1b8040da03c3c7Evan Cheng // The only time it's safe to fold into a two address instruction is when 875427f4c106ac14dcf323dc1bbaf1b8040da03c3c7Evan Cheng // it's folding reload and spill from / into a spill stack slot. 876427f4c106ac14dcf323dc1bbaf1b8040da03c3c7Evan Cheng if (DefMI && (MRInfo & VirtRegMap::isMod)) 877249ded3fa8884f91fded869fb6e251b8aebb0376Evan Cheng return false; 878249ded3fa8884f91fded869fb6e251b8aebb0376Evan Cheng 879f2f8c2ae07b7d9bdbf1b89781c573c7af2bd5e1bEvan Cheng MachineInstr *fmi = isSS ? tii_->foldMemoryOperand(*mf_, MI, FoldOps, Slot) 880f2f8c2ae07b7d9bdbf1b89781c573c7af2bd5e1bEvan Cheng : tii_->foldMemoryOperand(*mf_, MI, FoldOps, DefMI); 881f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng if (fmi) { 882d36531249a9a9500e516148e7e72d4c0a7a4d0eeEvan Cheng // Remember this instruction uses the spill slot. 883d36531249a9a9500e516148e7e72d4c0a7a4d0eeEvan Cheng if (isSS) vrm.addSpillSlotUse(Slot, fmi); 884d36531249a9a9500e516148e7e72d4c0a7a4d0eeEvan Cheng 885f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng // Attempt to fold the memory reference into the instruction. If 886f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng // we can do this, we don't need to insert spill code. 887f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng MachineBasicBlock &MBB = *MI->getParent(); 8888480293f41c11c22762164449e41cd3adb0dd7d8Evan Cheng if (isSS && !mf_->getFrameInfo()->isImmutableObjectIndex(Slot)) 889aee4af68ae2016afc5b4ec0c430e539c5810a766Evan Cheng vrm.virtFolded(Reg, MI, fmi, (VirtRegMap::ModRef)MRInfo); 89081a038218171860ee4c382849c647d3dc841fe8bEvan Cheng vrm.transferSpillPts(MI, fmi); 8910cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng vrm.transferRestorePts(MI, fmi); 892c1f53c742620dd4f2460685477303002bba8a8d8Evan Cheng vrm.transferEmergencySpills(MI, fmi); 893f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng mi2iMap_.erase(MI); 894cddbb83ea82e98658d9f530c50a7b9d23249afc2Evan Cheng i2miMap_[InstrIdx /InstrSlots::NUM] = fmi; 895cddbb83ea82e98658d9f530c50a7b9d23249afc2Evan Cheng mi2iMap_[fmi] = InstrIdx; 896f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng MI = MBB.insert(MBB.erase(MI), fmi); 8970cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng ++numFolds; 898f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng return true; 899f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng } 900f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng return false; 901f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng} 902f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng 903018f9b020bb12b731b0a7081578e5f82fb35092dEvan Cheng/// canFoldMemoryOperand - Returns true if the specified load / store 904018f9b020bb12b731b0a7081578e5f82fb35092dEvan Cheng/// folding is possible. 905018f9b020bb12b731b0a7081578e5f82fb35092dEvan Chengbool LiveIntervals::canFoldMemoryOperand(MachineInstr *MI, 90679a0c1e46c4f7d8a2a06f4ef3e2c54d883c7fe25Evan Cheng SmallVector<unsigned, 2> &Ops, 9073c75ba858b4e2070993cc1241ba74ead17f647d6Evan Cheng bool ReMat) const { 90879a0c1e46c4f7d8a2a06f4ef3e2c54d883c7fe25Evan Cheng // Filter the list of operand indexes that are to be folded. Abort if 90979a0c1e46c4f7d8a2a06f4ef3e2c54d883c7fe25Evan Cheng // any operand will prevent folding. 91079a0c1e46c4f7d8a2a06f4ef3e2c54d883c7fe25Evan Cheng unsigned MRInfo = 0; 911018f9b020bb12b731b0a7081578e5f82fb35092dEvan Cheng SmallVector<unsigned, 2> FoldOps; 91279a0c1e46c4f7d8a2a06f4ef3e2c54d883c7fe25Evan Cheng if (FilterFoldedOps(MI, Ops, MRInfo, FoldOps)) 91379a0c1e46c4f7d8a2a06f4ef3e2c54d883c7fe25Evan Cheng return false; 914018f9b020bb12b731b0a7081578e5f82fb35092dEvan Cheng 9153c75ba858b4e2070993cc1241ba74ead17f647d6Evan Cheng // It's only legal to remat for a use, not a def. 9163c75ba858b4e2070993cc1241ba74ead17f647d6Evan Cheng if (ReMat && (MRInfo & VirtRegMap::isMod)) 91779a0c1e46c4f7d8a2a06f4ef3e2c54d883c7fe25Evan Cheng return false; 918018f9b020bb12b731b0a7081578e5f82fb35092dEvan Cheng 919d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng return tii_->canFoldMemoryOperand(MI, FoldOps); 920d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng} 921d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng 92281a038218171860ee4c382849c647d3dc841fe8bEvan Chengbool LiveIntervals::intervalIsInOneMBB(const LiveInterval &li) const { 92381a038218171860ee4c382849c647d3dc841fe8bEvan Cheng SmallPtrSet<MachineBasicBlock*, 4> MBBs; 92481a038218171860ee4c382849c647d3dc841fe8bEvan Cheng for (LiveInterval::Ranges::const_iterator 92581a038218171860ee4c382849c647d3dc841fe8bEvan Cheng I = li.ranges.begin(), E = li.ranges.end(); I != E; ++I) { 92681a038218171860ee4c382849c647d3dc841fe8bEvan Cheng std::vector<IdxMBBPair>::const_iterator II = 92781a038218171860ee4c382849c647d3dc841fe8bEvan Cheng std::lower_bound(Idx2MBBMap.begin(), Idx2MBBMap.end(), I->start); 92881a038218171860ee4c382849c647d3dc841fe8bEvan Cheng if (II == Idx2MBBMap.end()) 92981a038218171860ee4c382849c647d3dc841fe8bEvan Cheng continue; 93081a038218171860ee4c382849c647d3dc841fe8bEvan Cheng if (I->end > II->first) // crossing a MBB. 93181a038218171860ee4c382849c647d3dc841fe8bEvan Cheng return false; 93281a038218171860ee4c382849c647d3dc841fe8bEvan Cheng MBBs.insert(II->second); 93381a038218171860ee4c382849c647d3dc841fe8bEvan Cheng if (MBBs.size() > 1) 93481a038218171860ee4c382849c647d3dc841fe8bEvan Cheng return false; 93581a038218171860ee4c382849c647d3dc841fe8bEvan Cheng } 93681a038218171860ee4c382849c647d3dc841fe8bEvan Cheng return true; 93781a038218171860ee4c382849c647d3dc841fe8bEvan Cheng} 93881a038218171860ee4c382849c647d3dc841fe8bEvan Cheng 939d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng/// rewriteImplicitOps - Rewrite implicit use operands of MI (i.e. uses of 940d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng/// interval on to-be re-materialized operands of MI) with new register. 941d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Chengvoid LiveIntervals::rewriteImplicitOps(const LiveInterval &li, 942d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng MachineInstr *MI, unsigned NewVReg, 943d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng VirtRegMap &vrm) { 944d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng // There is an implicit use. That means one of the other operand is 945d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng // being remat'ed and the remat'ed instruction has li.reg as an 946d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng // use operand. Make sure we rewrite that as well. 947d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) { 948d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng MachineOperand &MO = MI->getOperand(i); 949d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng if (!MO.isRegister()) 950d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng continue; 951d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng unsigned Reg = MO.getReg(); 952d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng if (Reg == 0 || TargetRegisterInfo::isPhysicalRegister(Reg)) 953d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng continue; 954d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng if (!vrm.isReMaterialized(Reg)) 955d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng continue; 956d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng MachineInstr *ReMatMI = vrm.getReMaterializedMI(Reg); 9576130f66eaae89f8878590796977678afa8448926Evan Cheng MachineOperand *UseMO = ReMatMI->findRegisterUseOperand(li.reg); 9586130f66eaae89f8878590796977678afa8448926Evan Cheng if (UseMO) 9596130f66eaae89f8878590796977678afa8448926Evan Cheng UseMO->setReg(NewVReg); 960d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng } 961d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng} 962d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng 963f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng/// rewriteInstructionForSpills, rewriteInstructionsForSpills - Helper functions 964f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng/// for addIntervalsForSpills to rewrite uses / defs for the given live range. 965018f9b020bb12b731b0a7081578e5f82fb35092dEvan Chengbool LiveIntervals:: 966d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan ChengrewriteInstructionForSpills(const LiveInterval &li, const VNInfo *VNI, 967d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng bool TrySplit, unsigned index, unsigned end, MachineInstr *MI, 96881a038218171860ee4c382849c647d3dc841fe8bEvan Cheng MachineInstr *ReMatOrigDefMI, MachineInstr *ReMatDefMI, 969f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng unsigned Slot, int LdSlot, 970f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng bool isLoad, bool isLoadSS, bool DefIsReMat, bool CanDelete, 971d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng VirtRegMap &vrm, 972f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng const TargetRegisterClass* rc, 973f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng SmallVector<int, 4> &ReMatIds, 97422f07ffd27d1d721634d502c37267721d2e025cfEvan Cheng const MachineLoopInfo *loopInfo, 975313d4b809326f3e04814f94e5b8ae05649d8e0f6Evan Cheng unsigned &NewVReg, unsigned ImpUse, bool &HasDef, bool &HasUse, 9761953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng std::map<unsigned,unsigned> &MBBVRegsMap, 9779c3c2213647e3f1b71722d61875ebac01b65cb91Evan Cheng std::vector<LiveInterval*> &NewLIs, float &SSWeight) { 9789c3c2213647e3f1b71722d61875ebac01b65cb91Evan Cheng MachineBasicBlock *MBB = MI->getParent(); 9799c3c2213647e3f1b71722d61875ebac01b65cb91Evan Cheng unsigned loopDepth = loopInfo->getLoopDepth(MBB); 980018f9b020bb12b731b0a7081578e5f82fb35092dEvan Cheng bool CanFold = false; 981f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng RestartInstruction: 982f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng for (unsigned i = 0; i != MI->getNumOperands(); ++i) { 983f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng MachineOperand& mop = MI->getOperand(i); 984f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng if (!mop.isRegister()) 985f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng continue; 986f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng unsigned Reg = mop.getReg(); 987f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng unsigned RegI = Reg; 9886f0d024a534af18d9e60b3ea757376cd8a3a980eDan Gohman if (Reg == 0 || TargetRegisterInfo::isPhysicalRegister(Reg)) 989f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng continue; 990f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng if (Reg != li.reg) 991f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng continue; 992f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng 993f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng bool TryFold = !DefIsReMat; 994cb3c330d39442130d0587208d673ce9c33c7008fEvan Cheng bool FoldSS = true; // Default behavior unless it's a remat. 995f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng int FoldSlot = Slot; 996f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng if (DefIsReMat) { 997f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng // If this is the rematerializable definition MI itself and 998f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng // all of its uses are rematerialized, simply delete it. 99981a038218171860ee4c382849c647d3dc841fe8bEvan Cheng if (MI == ReMatOrigDefMI && CanDelete) { 1000cddbb83ea82e98658d9f530c50a7b9d23249afc2Evan Cheng DOUT << "\t\t\t\tErasing re-materlizable def: "; 1001cddbb83ea82e98658d9f530c50a7b9d23249afc2Evan Cheng DOUT << MI << '\n'; 1002f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng RemoveMachineInstrFromMaps(MI); 1003cada245d06959831b90f8c29f92e77beda4b71cbEvan Cheng vrm.RemoveMachineInstrFromMaps(MI); 1004f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng MI->eraseFromParent(); 1005f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng break; 1006f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng } 1007f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng 1008f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng // If def for this use can't be rematerialized, then try folding. 10090cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng // If def is rematerializable and it's a load, also try folding. 1010cb3c330d39442130d0587208d673ce9c33c7008fEvan Cheng TryFold = !ReMatDefMI || (ReMatDefMI && (MI == ReMatOrigDefMI || isLoad)); 1011f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng if (isLoad) { 1012f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng // Try fold loads (from stack slot, constant pool, etc.) into uses. 1013f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng FoldSS = isLoadSS; 1014f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng FoldSlot = LdSlot; 1015f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng } 1016f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng } 1017f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng 1018f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng // Scan all of the operands of this instruction rewriting operands 1019f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng // to use NewVReg instead of li.reg as appropriate. We do this for 1020f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng // two reasons: 1021f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng // 1022f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng // 1. If the instr reads the same spilled vreg multiple times, we 1023f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng // want to reuse the NewVReg. 1024f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng // 2. If the instr is a two-addr instruction, we are required to 1025f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng // keep the src/dst regs pinned. 1026f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng // 1027f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng // Keep track of whether we replace a use and/or def so that we can 1028f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng // create the spill interval with the appropriate range. 1029cddbb83ea82e98658d9f530c50a7b9d23249afc2Evan Cheng 103081a038218171860ee4c382849c647d3dc841fe8bEvan Cheng HasUse = mop.isUse(); 103181a038218171860ee4c382849c647d3dc841fe8bEvan Cheng HasDef = mop.isDef(); 1032aee4af68ae2016afc5b4ec0c430e539c5810a766Evan Cheng SmallVector<unsigned, 2> Ops; 1033aee4af68ae2016afc5b4ec0c430e539c5810a766Evan Cheng Ops.push_back(i); 1034f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng for (unsigned j = i+1, e = MI->getNumOperands(); j != e; ++j) { 1035aee4af68ae2016afc5b4ec0c430e539c5810a766Evan Cheng const MachineOperand &MOj = MI->getOperand(j); 1036aee4af68ae2016afc5b4ec0c430e539c5810a766Evan Cheng if (!MOj.isRegister()) 1037f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng continue; 1038aee4af68ae2016afc5b4ec0c430e539c5810a766Evan Cheng unsigned RegJ = MOj.getReg(); 10396f0d024a534af18d9e60b3ea757376cd8a3a980eDan Gohman if (RegJ == 0 || TargetRegisterInfo::isPhysicalRegister(RegJ)) 1040f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng continue; 1041f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng if (RegJ == RegI) { 1042aee4af68ae2016afc5b4ec0c430e539c5810a766Evan Cheng Ops.push_back(j); 1043aee4af68ae2016afc5b4ec0c430e539c5810a766Evan Cheng HasUse |= MOj.isUse(); 1044aee4af68ae2016afc5b4ec0c430e539c5810a766Evan Cheng HasDef |= MOj.isDef(); 1045f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng } 1046f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng } 1047f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng 10489c3c2213647e3f1b71722d61875ebac01b65cb91Evan Cheng // Update stack slot spill weight if we are splitting. 1049c3417609ae6e744a29be6962d4fb7811c0102d17Evan Cheng float Weight = getSpillWeight(HasDef, HasUse, loopDepth); 10509c3c2213647e3f1b71722d61875ebac01b65cb91Evan Cheng if (!TrySplit) 10519c3c2213647e3f1b71722d61875ebac01b65cb91Evan Cheng SSWeight += Weight; 10529c3c2213647e3f1b71722d61875ebac01b65cb91Evan Cheng 10539c3c2213647e3f1b71722d61875ebac01b65cb91Evan Cheng if (!TryFold) 10549c3c2213647e3f1b71722d61875ebac01b65cb91Evan Cheng CanFold = false; 10559c3c2213647e3f1b71722d61875ebac01b65cb91Evan Cheng else { 1056018f9b020bb12b731b0a7081578e5f82fb35092dEvan Cheng // Do not fold load / store here if we are splitting. We'll find an 1057018f9b020bb12b731b0a7081578e5f82fb35092dEvan Cheng // optimal point to insert a load / store later. 1058018f9b020bb12b731b0a7081578e5f82fb35092dEvan Cheng if (!TrySplit) { 1059018f9b020bb12b731b0a7081578e5f82fb35092dEvan Cheng if (tryFoldMemoryOperand(MI, vrm, ReMatDefMI, index, 1060018f9b020bb12b731b0a7081578e5f82fb35092dEvan Cheng Ops, FoldSS, FoldSlot, Reg)) { 1061018f9b020bb12b731b0a7081578e5f82fb35092dEvan Cheng // Folding the load/store can completely change the instruction in 1062018f9b020bb12b731b0a7081578e5f82fb35092dEvan Cheng // unpredictable ways, rescan it from the beginning. 1063018f9b020bb12b731b0a7081578e5f82fb35092dEvan Cheng HasUse = false; 1064018f9b020bb12b731b0a7081578e5f82fb35092dEvan Cheng HasDef = false; 1065018f9b020bb12b731b0a7081578e5f82fb35092dEvan Cheng CanFold = false; 10669c3c2213647e3f1b71722d61875ebac01b65cb91Evan Cheng if (isRemoved(MI)) { 10679c3c2213647e3f1b71722d61875ebac01b65cb91Evan Cheng SSWeight -= Weight; 10687e073baedb8232b9519dbe15ea141ff98ccfe6aeEvan Cheng break; 10699c3c2213647e3f1b71722d61875ebac01b65cb91Evan Cheng } 1070018f9b020bb12b731b0a7081578e5f82fb35092dEvan Cheng goto RestartInstruction; 1071018f9b020bb12b731b0a7081578e5f82fb35092dEvan Cheng } 1072018f9b020bb12b731b0a7081578e5f82fb35092dEvan Cheng } else { 10739c3c2213647e3f1b71722d61875ebac01b65cb91Evan Cheng // We'll try to fold it later if it's profitable. 10743c75ba858b4e2070993cc1241ba74ead17f647d6Evan Cheng CanFold = canFoldMemoryOperand(MI, Ops, DefIsReMat); 1075018f9b020bb12b731b0a7081578e5f82fb35092dEvan Cheng } 10769c3c2213647e3f1b71722d61875ebac01b65cb91Evan Cheng } 1077cddbb83ea82e98658d9f530c50a7b9d23249afc2Evan Cheng 1078cddbb83ea82e98658d9f530c50a7b9d23249afc2Evan Cheng // Create a new virtual register for the spill interval. 1079cddbb83ea82e98658d9f530c50a7b9d23249afc2Evan Cheng bool CreatedNewVReg = false; 1080cddbb83ea82e98658d9f530c50a7b9d23249afc2Evan Cheng if (NewVReg == 0) { 1081d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng NewVReg = mri_->createVirtualRegister(rc); 1082cddbb83ea82e98658d9f530c50a7b9d23249afc2Evan Cheng vrm.grow(); 1083cddbb83ea82e98658d9f530c50a7b9d23249afc2Evan Cheng CreatedNewVReg = true; 1084cddbb83ea82e98658d9f530c50a7b9d23249afc2Evan Cheng } 1085cddbb83ea82e98658d9f530c50a7b9d23249afc2Evan Cheng mop.setReg(NewVReg); 1086d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng if (mop.isImplicit()) 1087d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng rewriteImplicitOps(li, MI, NewVReg, vrm); 1088cddbb83ea82e98658d9f530c50a7b9d23249afc2Evan Cheng 1089cddbb83ea82e98658d9f530c50a7b9d23249afc2Evan Cheng // Reuse NewVReg for other reads. 1090d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng for (unsigned j = 0, e = Ops.size(); j != e; ++j) { 1091d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng MachineOperand &mopj = MI->getOperand(Ops[j]); 1092d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng mopj.setReg(NewVReg); 1093d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng if (mopj.isImplicit()) 1094d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng rewriteImplicitOps(li, MI, NewVReg, vrm); 1095d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng } 1096cddbb83ea82e98658d9f530c50a7b9d23249afc2Evan Cheng 109781a038218171860ee4c382849c647d3dc841fe8bEvan Cheng if (CreatedNewVReg) { 109881a038218171860ee4c382849c647d3dc841fe8bEvan Cheng if (DefIsReMat) { 109981a038218171860ee4c382849c647d3dc841fe8bEvan Cheng vrm.setVirtIsReMaterialized(NewVReg, ReMatDefMI/*, CanDelete*/); 1100d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng if (ReMatIds[VNI->id] == VirtRegMap::MAX_STACK_SLOT) { 110181a038218171860ee4c382849c647d3dc841fe8bEvan Cheng // Each valnum may have its own remat id. 1102d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng ReMatIds[VNI->id] = vrm.assignVirtReMatId(NewVReg); 110381a038218171860ee4c382849c647d3dc841fe8bEvan Cheng } else { 1104d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng vrm.assignVirtReMatId(NewVReg, ReMatIds[VNI->id]); 110581a038218171860ee4c382849c647d3dc841fe8bEvan Cheng } 110681a038218171860ee4c382849c647d3dc841fe8bEvan Cheng if (!CanDelete || (HasUse && HasDef)) { 110781a038218171860ee4c382849c647d3dc841fe8bEvan Cheng // If this is a two-addr instruction then its use operands are 110881a038218171860ee4c382849c647d3dc841fe8bEvan Cheng // rematerializable but its def is not. It should be assigned a 110981a038218171860ee4c382849c647d3dc841fe8bEvan Cheng // stack slot. 111081a038218171860ee4c382849c647d3dc841fe8bEvan Cheng vrm.assignVirt2StackSlot(NewVReg, Slot); 111181a038218171860ee4c382849c647d3dc841fe8bEvan Cheng } 1112f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng } else { 1113f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng vrm.assignVirt2StackSlot(NewVReg, Slot); 1114f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng } 1115cb3c330d39442130d0587208d673ce9c33c7008fEvan Cheng } else if (HasUse && HasDef && 1116cb3c330d39442130d0587208d673ce9c33c7008fEvan Cheng vrm.getStackSlot(NewVReg) == VirtRegMap::NO_STACK_SLOT) { 1117cb3c330d39442130d0587208d673ce9c33c7008fEvan Cheng // If this interval hasn't been assigned a stack slot (because earlier 1118cb3c330d39442130d0587208d673ce9c33c7008fEvan Cheng // def is a deleted remat def), do it now. 1119cb3c330d39442130d0587208d673ce9c33c7008fEvan Cheng assert(Slot != VirtRegMap::NO_STACK_SLOT); 1120cb3c330d39442130d0587208d673ce9c33c7008fEvan Cheng vrm.assignVirt2StackSlot(NewVReg, Slot); 1121f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng } 1122f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng 1123313d4b809326f3e04814f94e5b8ae05649d8e0f6Evan Cheng // Re-matting an instruction with virtual register use. Add the 1124313d4b809326f3e04814f94e5b8ae05649d8e0f6Evan Cheng // register as an implicit use on the use MI. 1125313d4b809326f3e04814f94e5b8ae05649d8e0f6Evan Cheng if (DefIsReMat && ImpUse) 1126313d4b809326f3e04814f94e5b8ae05649d8e0f6Evan Cheng MI->addOperand(MachineOperand::CreateReg(ImpUse, false, true)); 1127313d4b809326f3e04814f94e5b8ae05649d8e0f6Evan Cheng 1128f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng // create a new register interval for this spill / remat. 1129f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng LiveInterval &nI = getOrCreateInterval(NewVReg); 113081a038218171860ee4c382849c647d3dc841fe8bEvan Cheng if (CreatedNewVReg) { 113181a038218171860ee4c382849c647d3dc841fe8bEvan Cheng NewLIs.push_back(&nI); 11321953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng MBBVRegsMap.insert(std::make_pair(MI->getParent()->getNumber(), NewVReg)); 113381a038218171860ee4c382849c647d3dc841fe8bEvan Cheng if (TrySplit) 113481a038218171860ee4c382849c647d3dc841fe8bEvan Cheng vrm.setIsSplitFromReg(NewVReg, li.reg); 113581a038218171860ee4c382849c647d3dc841fe8bEvan Cheng } 1136f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng 1137f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng if (HasUse) { 113881a038218171860ee4c382849c647d3dc841fe8bEvan Cheng if (CreatedNewVReg) { 113981a038218171860ee4c382849c647d3dc841fe8bEvan Cheng LiveRange LR(getLoadIndex(index), getUseIndex(index)+1, 114081a038218171860ee4c382849c647d3dc841fe8bEvan Cheng nI.getNextValue(~0U, 0, VNInfoAllocator)); 114181a038218171860ee4c382849c647d3dc841fe8bEvan Cheng DOUT << " +" << LR; 114281a038218171860ee4c382849c647d3dc841fe8bEvan Cheng nI.addRange(LR); 114381a038218171860ee4c382849c647d3dc841fe8bEvan Cheng } else { 114481a038218171860ee4c382849c647d3dc841fe8bEvan Cheng // Extend the split live interval to this def / use. 114581a038218171860ee4c382849c647d3dc841fe8bEvan Cheng unsigned End = getUseIndex(index)+1; 114681a038218171860ee4c382849c647d3dc841fe8bEvan Cheng LiveRange LR(nI.ranges[nI.ranges.size()-1].end, End, 114781a038218171860ee4c382849c647d3dc841fe8bEvan Cheng nI.getValNumInfo(nI.getNumValNums()-1)); 114881a038218171860ee4c382849c647d3dc841fe8bEvan Cheng DOUT << " +" << LR; 114981a038218171860ee4c382849c647d3dc841fe8bEvan Cheng nI.addRange(LR); 115081a038218171860ee4c382849c647d3dc841fe8bEvan Cheng } 1151f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng } 1152f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng if (HasDef) { 1153f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng LiveRange LR(getDefIndex(index), getStoreIndex(index), 1154f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng nI.getNextValue(~0U, 0, VNInfoAllocator)); 1155f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng DOUT << " +" << LR; 1156f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng nI.addRange(LR); 1157f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng } 115881a038218171860ee4c382849c647d3dc841fe8bEvan Cheng 1159f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng DOUT << "\t\t\t\tAdded new interval: "; 11606f0d024a534af18d9e60b3ea757376cd8a3a980eDan Gohman nI.print(DOUT, tri_); 1161f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng DOUT << '\n'; 1162f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng } 1163018f9b020bb12b731b0a7081578e5f82fb35092dEvan Cheng return CanFold; 1164f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng} 116581a038218171860ee4c382849c647d3dc841fe8bEvan Chengbool LiveIntervals::anyKillInMBBAfterIdx(const LiveInterval &li, 11660cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng const VNInfo *VNI, 11670cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng MachineBasicBlock *MBB, unsigned Idx) const { 116881a038218171860ee4c382849c647d3dc841fe8bEvan Cheng unsigned End = getMBBEndIdx(MBB); 11690cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng for (unsigned j = 0, ee = VNI->kills.size(); j != ee; ++j) { 11700cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng unsigned KillIdx = VNI->kills[j]; 11710cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng if (KillIdx > Idx && KillIdx < End) 11720cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng return true; 117381a038218171860ee4c382849c647d3dc841fe8bEvan Cheng } 117481a038218171860ee4c382849c647d3dc841fe8bEvan Cheng return false; 117581a038218171860ee4c382849c647d3dc841fe8bEvan Cheng} 117681a038218171860ee4c382849c647d3dc841fe8bEvan Cheng 1177063284c001666c0a3906acbe0a26dc7cae5f081cEvan Cheng/// RewriteInfo - Keep track of machine instrs that will be rewritten 1178063284c001666c0a3906acbe0a26dc7cae5f081cEvan Cheng/// during spilling. 1179844731a7f1909f55935e3514c9e713a62d67662eDan Gohmannamespace { 1180844731a7f1909f55935e3514c9e713a62d67662eDan Gohman struct RewriteInfo { 1181844731a7f1909f55935e3514c9e713a62d67662eDan Gohman unsigned Index; 1182844731a7f1909f55935e3514c9e713a62d67662eDan Gohman MachineInstr *MI; 1183844731a7f1909f55935e3514c9e713a62d67662eDan Gohman bool HasUse; 1184844731a7f1909f55935e3514c9e713a62d67662eDan Gohman bool HasDef; 1185844731a7f1909f55935e3514c9e713a62d67662eDan Gohman RewriteInfo(unsigned i, MachineInstr *mi, bool u, bool d) 1186844731a7f1909f55935e3514c9e713a62d67662eDan Gohman : Index(i), MI(mi), HasUse(u), HasDef(d) {} 1187844731a7f1909f55935e3514c9e713a62d67662eDan Gohman }; 1188844731a7f1909f55935e3514c9e713a62d67662eDan Gohman 1189844731a7f1909f55935e3514c9e713a62d67662eDan Gohman struct RewriteInfoCompare { 1190844731a7f1909f55935e3514c9e713a62d67662eDan Gohman bool operator()(const RewriteInfo &LHS, const RewriteInfo &RHS) const { 1191844731a7f1909f55935e3514c9e713a62d67662eDan Gohman return LHS.Index < RHS.Index; 1192844731a7f1909f55935e3514c9e713a62d67662eDan Gohman } 1193844731a7f1909f55935e3514c9e713a62d67662eDan Gohman }; 1194844731a7f1909f55935e3514c9e713a62d67662eDan Gohman} 1195063284c001666c0a3906acbe0a26dc7cae5f081cEvan Cheng 1196f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Chengvoid LiveIntervals:: 119781a038218171860ee4c382849c647d3dc841fe8bEvan ChengrewriteInstructionsForSpills(const LiveInterval &li, bool TrySplit, 1198f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng LiveInterval::Ranges::const_iterator &I, 119981a038218171860ee4c382849c647d3dc841fe8bEvan Cheng MachineInstr *ReMatOrigDefMI, MachineInstr *ReMatDefMI, 1200f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng unsigned Slot, int LdSlot, 1201f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng bool isLoad, bool isLoadSS, bool DefIsReMat, bool CanDelete, 1202d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng VirtRegMap &vrm, 1203f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng const TargetRegisterClass* rc, 1204f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng SmallVector<int, 4> &ReMatIds, 120522f07ffd27d1d721634d502c37267721d2e025cfEvan Cheng const MachineLoopInfo *loopInfo, 120681a038218171860ee4c382849c647d3dc841fe8bEvan Cheng BitVector &SpillMBBs, 12071953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng std::map<unsigned, std::vector<SRInfo> > &SpillIdxes, 12080cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng BitVector &RestoreMBBs, 12091953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng std::map<unsigned, std::vector<SRInfo> > &RestoreIdxes, 12101953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng std::map<unsigned,unsigned> &MBBVRegsMap, 12119c3c2213647e3f1b71722d61875ebac01b65cb91Evan Cheng std::vector<LiveInterval*> &NewLIs, float &SSWeight) { 1212018f9b020bb12b731b0a7081578e5f82fb35092dEvan Cheng bool AllCanFold = true; 121381a038218171860ee4c382849c647d3dc841fe8bEvan Cheng unsigned NewVReg = 0; 1214063284c001666c0a3906acbe0a26dc7cae5f081cEvan Cheng unsigned start = getBaseIndex(I->start); 1215f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng unsigned end = getBaseIndex(I->end-1) + InstrSlots::NUM; 1216f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng 1217063284c001666c0a3906acbe0a26dc7cae5f081cEvan Cheng // First collect all the def / use in this live range that will be rewritten. 12187e073baedb8232b9519dbe15ea141ff98ccfe6aeEvan Cheng // Make sure they are sorted according to instruction index. 1219063284c001666c0a3906acbe0a26dc7cae5f081cEvan Cheng std::vector<RewriteInfo> RewriteMIs; 1220d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng for (MachineRegisterInfo::reg_iterator ri = mri_->reg_begin(li.reg), 1221d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng re = mri_->reg_end(); ri != re; ) { 1222419852ca8a01aecde4c0e20af6b7bd6450e70f87Evan Cheng MachineInstr *MI = &*ri; 1223063284c001666c0a3906acbe0a26dc7cae5f081cEvan Cheng MachineOperand &O = ri.getOperand(); 1224063284c001666c0a3906acbe0a26dc7cae5f081cEvan Cheng ++ri; 122524d2f8a212f08bf21360122cc00acf2657af91f9Evan Cheng assert(!O.isImplicit() && "Spilling register that's used as implicit use?"); 1226063284c001666c0a3906acbe0a26dc7cae5f081cEvan Cheng unsigned index = getInstructionIndex(MI); 1227063284c001666c0a3906acbe0a26dc7cae5f081cEvan Cheng if (index < start || index >= end) 1228063284c001666c0a3906acbe0a26dc7cae5f081cEvan Cheng continue; 1229063284c001666c0a3906acbe0a26dc7cae5f081cEvan Cheng RewriteMIs.push_back(RewriteInfo(index, MI, O.isUse(), O.isDef())); 1230063284c001666c0a3906acbe0a26dc7cae5f081cEvan Cheng } 1231063284c001666c0a3906acbe0a26dc7cae5f081cEvan Cheng std::sort(RewriteMIs.begin(), RewriteMIs.end(), RewriteInfoCompare()); 1232063284c001666c0a3906acbe0a26dc7cae5f081cEvan Cheng 1233313d4b809326f3e04814f94e5b8ae05649d8e0f6Evan Cheng unsigned ImpUse = DefIsReMat ? getReMatImplicitUse(li, ReMatDefMI) : 0; 1234063284c001666c0a3906acbe0a26dc7cae5f081cEvan Cheng // Now rewrite the defs and uses. 1235063284c001666c0a3906acbe0a26dc7cae5f081cEvan Cheng for (unsigned i = 0, e = RewriteMIs.size(); i != e; ) { 1236063284c001666c0a3906acbe0a26dc7cae5f081cEvan Cheng RewriteInfo &rwi = RewriteMIs[i]; 1237063284c001666c0a3906acbe0a26dc7cae5f081cEvan Cheng ++i; 1238063284c001666c0a3906acbe0a26dc7cae5f081cEvan Cheng unsigned index = rwi.Index; 1239063284c001666c0a3906acbe0a26dc7cae5f081cEvan Cheng bool MIHasUse = rwi.HasUse; 1240063284c001666c0a3906acbe0a26dc7cae5f081cEvan Cheng bool MIHasDef = rwi.HasDef; 1241063284c001666c0a3906acbe0a26dc7cae5f081cEvan Cheng MachineInstr *MI = rwi.MI; 1242063284c001666c0a3906acbe0a26dc7cae5f081cEvan Cheng // If MI def and/or use the same register multiple times, then there 1243063284c001666c0a3906acbe0a26dc7cae5f081cEvan Cheng // are multiple entries. 1244313d4b809326f3e04814f94e5b8ae05649d8e0f6Evan Cheng unsigned NumUses = MIHasUse; 1245063284c001666c0a3906acbe0a26dc7cae5f081cEvan Cheng while (i != e && RewriteMIs[i].MI == MI) { 1246063284c001666c0a3906acbe0a26dc7cae5f081cEvan Cheng assert(RewriteMIs[i].Index == index); 1247313d4b809326f3e04814f94e5b8ae05649d8e0f6Evan Cheng bool isUse = RewriteMIs[i].HasUse; 1248313d4b809326f3e04814f94e5b8ae05649d8e0f6Evan Cheng if (isUse) ++NumUses; 1249313d4b809326f3e04814f94e5b8ae05649d8e0f6Evan Cheng MIHasUse |= isUse; 1250063284c001666c0a3906acbe0a26dc7cae5f081cEvan Cheng MIHasDef |= RewriteMIs[i].HasDef; 1251063284c001666c0a3906acbe0a26dc7cae5f081cEvan Cheng ++i; 1252063284c001666c0a3906acbe0a26dc7cae5f081cEvan Cheng } 125381a038218171860ee4c382849c647d3dc841fe8bEvan Cheng MachineBasicBlock *MBB = MI->getParent(); 1254313d4b809326f3e04814f94e5b8ae05649d8e0f6Evan Cheng 12550a891ed7d5875a9ccdb93b4472b0f43947d8289bEvan Cheng if (ImpUse && MI != ReMatDefMI) { 1256313d4b809326f3e04814f94e5b8ae05649d8e0f6Evan Cheng // Re-matting an instruction with virtual register use. Update the 125724d2f8a212f08bf21360122cc00acf2657af91f9Evan Cheng // register interval's spill weight to HUGE_VALF to prevent it from 125824d2f8a212f08bf21360122cc00acf2657af91f9Evan Cheng // being spilled. 1259313d4b809326f3e04814f94e5b8ae05649d8e0f6Evan Cheng LiveInterval &ImpLi = getInterval(ImpUse); 126024d2f8a212f08bf21360122cc00acf2657af91f9Evan Cheng ImpLi.weight = HUGE_VALF; 1261313d4b809326f3e04814f94e5b8ae05649d8e0f6Evan Cheng } 1262313d4b809326f3e04814f94e5b8ae05649d8e0f6Evan Cheng 1263063284c001666c0a3906acbe0a26dc7cae5f081cEvan Cheng unsigned MBBId = MBB->getNumber(); 1264018f9b020bb12b731b0a7081578e5f82fb35092dEvan Cheng unsigned ThisVReg = 0; 126570306f8348f27c61cfed5a60e2fceac0f29746a2Evan Cheng if (TrySplit) { 1266063284c001666c0a3906acbe0a26dc7cae5f081cEvan Cheng std::map<unsigned,unsigned>::const_iterator NVI = MBBVRegsMap.find(MBBId); 12671953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng if (NVI != MBBVRegsMap.end()) { 1268018f9b020bb12b731b0a7081578e5f82fb35092dEvan Cheng ThisVReg = NVI->second; 12691953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng // One common case: 12701953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng // x = use 12711953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng // ... 12721953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng // ... 12731953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng // def = ... 12741953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng // = use 12751953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng // It's better to start a new interval to avoid artifically 12761953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng // extend the new interval. 12771953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng if (MIHasDef && !MIHasUse) { 12781953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng MBBVRegsMap.erase(MBB->getNumber()); 1279018f9b020bb12b731b0a7081578e5f82fb35092dEvan Cheng ThisVReg = 0; 12801953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng } 12811953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng } 1282cada245d06959831b90f8c29f92e77beda4b71cbEvan Cheng } 1283018f9b020bb12b731b0a7081578e5f82fb35092dEvan Cheng 1284018f9b020bb12b731b0a7081578e5f82fb35092dEvan Cheng bool IsNew = ThisVReg == 0; 1285018f9b020bb12b731b0a7081578e5f82fb35092dEvan Cheng if (IsNew) { 1286018f9b020bb12b731b0a7081578e5f82fb35092dEvan Cheng // This ends the previous live interval. If all of its def / use 1287018f9b020bb12b731b0a7081578e5f82fb35092dEvan Cheng // can be folded, give it a low spill weight. 1288018f9b020bb12b731b0a7081578e5f82fb35092dEvan Cheng if (NewVReg && TrySplit && AllCanFold) { 1289018f9b020bb12b731b0a7081578e5f82fb35092dEvan Cheng LiveInterval &nI = getOrCreateInterval(NewVReg); 1290018f9b020bb12b731b0a7081578e5f82fb35092dEvan Cheng nI.weight /= 10.0F; 1291018f9b020bb12b731b0a7081578e5f82fb35092dEvan Cheng } 1292018f9b020bb12b731b0a7081578e5f82fb35092dEvan Cheng AllCanFold = true; 1293018f9b020bb12b731b0a7081578e5f82fb35092dEvan Cheng } 1294018f9b020bb12b731b0a7081578e5f82fb35092dEvan Cheng NewVReg = ThisVReg; 1295018f9b020bb12b731b0a7081578e5f82fb35092dEvan Cheng 129681a038218171860ee4c382849c647d3dc841fe8bEvan Cheng bool HasDef = false; 129781a038218171860ee4c382849c647d3dc841fe8bEvan Cheng bool HasUse = false; 1298d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng bool CanFold = rewriteInstructionForSpills(li, I->valno, TrySplit, 12999c3c2213647e3f1b71722d61875ebac01b65cb91Evan Cheng index, end, MI, ReMatOrigDefMI, ReMatDefMI, 13009c3c2213647e3f1b71722d61875ebac01b65cb91Evan Cheng Slot, LdSlot, isLoad, isLoadSS, DefIsReMat, 13019c3c2213647e3f1b71722d61875ebac01b65cb91Evan Cheng CanDelete, vrm, rc, ReMatIds, loopInfo, NewVReg, 13029c3c2213647e3f1b71722d61875ebac01b65cb91Evan Cheng ImpUse, HasDef, HasUse, MBBVRegsMap, NewLIs, SSWeight); 130381a038218171860ee4c382849c647d3dc841fe8bEvan Cheng if (!HasDef && !HasUse) 130481a038218171860ee4c382849c647d3dc841fe8bEvan Cheng continue; 130581a038218171860ee4c382849c647d3dc841fe8bEvan Cheng 1306018f9b020bb12b731b0a7081578e5f82fb35092dEvan Cheng AllCanFold &= CanFold; 1307018f9b020bb12b731b0a7081578e5f82fb35092dEvan Cheng 130881a038218171860ee4c382849c647d3dc841fe8bEvan Cheng // Update weight of spill interval. 130981a038218171860ee4c382849c647d3dc841fe8bEvan Cheng LiveInterval &nI = getOrCreateInterval(NewVReg); 131070306f8348f27c61cfed5a60e2fceac0f29746a2Evan Cheng if (!TrySplit) { 131181a038218171860ee4c382849c647d3dc841fe8bEvan Cheng // The spill weight is now infinity as it cannot be spilled again. 131281a038218171860ee4c382849c647d3dc841fe8bEvan Cheng nI.weight = HUGE_VALF; 13130cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng continue; 13140cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng } 13150cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng 13160cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng // Keep track of the last def and first use in each MBB. 13170cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng if (HasDef) { 13180cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng if (MI != ReMatOrigDefMI || !CanDelete) { 13190cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng bool HasKill = false; 13200cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng if (!HasUse) 13210cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng HasKill = anyKillInMBBAfterIdx(li, I->valno, MBB, getDefIndex(index)); 13220cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng else { 13231953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng // If this is a two-address code, then this index starts a new VNInfo. 13243f32d65912b4da23793dab618d981be2ce11c331Evan Cheng const VNInfo *VNI = li.findDefinedVNInfo(getDefIndex(index)); 13250cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng if (VNI) 13260cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng HasKill = anyKillInMBBAfterIdx(li, VNI, MBB, getDefIndex(index)); 132781a038218171860ee4c382849c647d3dc841fe8bEvan Cheng } 1328e3110d0825e6316fd2dd21d6a4e593295cd413f1Evan Cheng std::map<unsigned, std::vector<SRInfo> >::iterator SII = 1329e3110d0825e6316fd2dd21d6a4e593295cd413f1Evan Cheng SpillIdxes.find(MBBId); 13300cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng if (!HasKill) { 13311953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng if (SII == SpillIdxes.end()) { 13321953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng std::vector<SRInfo> S; 13331953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng S.push_back(SRInfo(index, NewVReg, true)); 13341953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng SpillIdxes.insert(std::make_pair(MBBId, S)); 13351953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng } else if (SII->second.back().vreg != NewVReg) { 13361953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng SII->second.push_back(SRInfo(index, NewVReg, true)); 13371953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng } else if ((int)index > SII->second.back().index) { 13380cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng // If there is an earlier def and this is a two-address 13390cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng // instruction, then it's not possible to fold the store (which 13400cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng // would also fold the load). 13411953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng SRInfo &Info = SII->second.back(); 13421953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng Info.index = index; 13431953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng Info.canFold = !HasUse; 134481a038218171860ee4c382849c647d3dc841fe8bEvan Cheng } 13450cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng SpillMBBs.set(MBBId); 1346e3110d0825e6316fd2dd21d6a4e593295cd413f1Evan Cheng } else if (SII != SpillIdxes.end() && 1347e3110d0825e6316fd2dd21d6a4e593295cd413f1Evan Cheng SII->second.back().vreg == NewVReg && 1348e3110d0825e6316fd2dd21d6a4e593295cd413f1Evan Cheng (int)index > SII->second.back().index) { 1349e3110d0825e6316fd2dd21d6a4e593295cd413f1Evan Cheng // There is an earlier def that's not killed (must be two-address). 1350e3110d0825e6316fd2dd21d6a4e593295cd413f1Evan Cheng // The spill is no longer needed. 1351e3110d0825e6316fd2dd21d6a4e593295cd413f1Evan Cheng SII->second.pop_back(); 1352e3110d0825e6316fd2dd21d6a4e593295cd413f1Evan Cheng if (SII->second.empty()) { 1353e3110d0825e6316fd2dd21d6a4e593295cd413f1Evan Cheng SpillIdxes.erase(MBBId); 1354e3110d0825e6316fd2dd21d6a4e593295cd413f1Evan Cheng SpillMBBs.reset(MBBId); 1355e3110d0825e6316fd2dd21d6a4e593295cd413f1Evan Cheng } 135681a038218171860ee4c382849c647d3dc841fe8bEvan Cheng } 135781a038218171860ee4c382849c647d3dc841fe8bEvan Cheng } 13580cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng } 135981a038218171860ee4c382849c647d3dc841fe8bEvan Cheng 13600cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng if (HasUse) { 13611953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng std::map<unsigned, std::vector<SRInfo> >::iterator SII = 13620cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng SpillIdxes.find(MBBId); 13631953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng if (SII != SpillIdxes.end() && 13641953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng SII->second.back().vreg == NewVReg && 13651953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng (int)index > SII->second.back().index) 13660cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng // Use(s) following the last def, it's not safe to fold the spill. 13671953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng SII->second.back().canFold = false; 13681953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng std::map<unsigned, std::vector<SRInfo> >::iterator RII = 13690cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng RestoreIdxes.find(MBBId); 13701953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng if (RII != RestoreIdxes.end() && RII->second.back().vreg == NewVReg) 13710cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng // If we are splitting live intervals, only fold if it's the first 13720cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng // use and there isn't another use later in the MBB. 13731953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng RII->second.back().canFold = false; 13740cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng else if (IsNew) { 13750cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng // Only need a reload if there isn't an earlier def / use. 13761953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng if (RII == RestoreIdxes.end()) { 13771953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng std::vector<SRInfo> Infos; 13781953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng Infos.push_back(SRInfo(index, NewVReg, true)); 13791953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng RestoreIdxes.insert(std::make_pair(MBBId, Infos)); 13801953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng } else { 13811953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng RII->second.push_back(SRInfo(index, NewVReg, true)); 13821953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng } 13830cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng RestoreMBBs.set(MBBId); 13840cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng } 138581a038218171860ee4c382849c647d3dc841fe8bEvan Cheng } 13860cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng 13870cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng // Update spill weight. 138822f07ffd27d1d721634d502c37267721d2e025cfEvan Cheng unsigned loopDepth = loopInfo->getLoopDepth(MBB); 1389c3417609ae6e744a29be6962d4fb7811c0102d17Evan Cheng nI.weight += getSpillWeight(HasDef, HasUse, loopDepth); 1390f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng } 1391018f9b020bb12b731b0a7081578e5f82fb35092dEvan Cheng 1392018f9b020bb12b731b0a7081578e5f82fb35092dEvan Cheng if (NewVReg && TrySplit && AllCanFold) { 1393018f9b020bb12b731b0a7081578e5f82fb35092dEvan Cheng // If all of its def / use can be folded, give it a low spill weight. 1394018f9b020bb12b731b0a7081578e5f82fb35092dEvan Cheng LiveInterval &nI = getOrCreateInterval(NewVReg); 1395018f9b020bb12b731b0a7081578e5f82fb35092dEvan Cheng nI.weight /= 10.0F; 1396018f9b020bb12b731b0a7081578e5f82fb35092dEvan Cheng } 1397f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng} 1398f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng 13991953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Chengbool LiveIntervals::alsoFoldARestore(int Id, int index, unsigned vr, 14001953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng BitVector &RestoreMBBs, 14011953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng std::map<unsigned,std::vector<SRInfo> > &RestoreIdxes) { 14021953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng if (!RestoreMBBs[Id]) 14031953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng return false; 14041953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng std::vector<SRInfo> &Restores = RestoreIdxes[Id]; 14051953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng for (unsigned i = 0, e = Restores.size(); i != e; ++i) 14061953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng if (Restores[i].index == index && 14071953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng Restores[i].vreg == vr && 14081953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng Restores[i].canFold) 14091953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng return true; 14101953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng return false; 14111953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng} 14121953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng 14131953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Chengvoid LiveIntervals::eraseRestoreInfo(int Id, int index, unsigned vr, 14141953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng BitVector &RestoreMBBs, 14151953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng std::map<unsigned,std::vector<SRInfo> > &RestoreIdxes) { 14161953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng if (!RestoreMBBs[Id]) 14171953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng return; 14181953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng std::vector<SRInfo> &Restores = RestoreIdxes[Id]; 14191953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng for (unsigned i = 0, e = Restores.size(); i != e; ++i) 14201953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng if (Restores[i].index == index && Restores[i].vreg) 14211953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng Restores[i].index = -1; 14221953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng} 142381a038218171860ee4c382849c647d3dc841fe8bEvan Cheng 14244cce6b4c7882ef0cc993d931b90bf33985c96110Evan Cheng/// handleSpilledImpDefs - Remove IMPLICIT_DEF instructions which are being 14254cce6b4c7882ef0cc993d931b90bf33985c96110Evan Cheng/// spilled and create empty intervals for their uses. 14264cce6b4c7882ef0cc993d931b90bf33985c96110Evan Chengvoid 14274cce6b4c7882ef0cc993d931b90bf33985c96110Evan ChengLiveIntervals::handleSpilledImpDefs(const LiveInterval &li, VirtRegMap &vrm, 14284cce6b4c7882ef0cc993d931b90bf33985c96110Evan Cheng const TargetRegisterClass* rc, 14294cce6b4c7882ef0cc993d931b90bf33985c96110Evan Cheng std::vector<LiveInterval*> &NewLIs) { 1430419852ca8a01aecde4c0e20af6b7bd6450e70f87Evan Cheng for (MachineRegisterInfo::reg_iterator ri = mri_->reg_begin(li.reg), 1431419852ca8a01aecde4c0e20af6b7bd6450e70f87Evan Cheng re = mri_->reg_end(); ri != re; ) { 14324cce6b4c7882ef0cc993d931b90bf33985c96110Evan Cheng MachineOperand &O = ri.getOperand(); 1433419852ca8a01aecde4c0e20af6b7bd6450e70f87Evan Cheng MachineInstr *MI = &*ri; 1434419852ca8a01aecde4c0e20af6b7bd6450e70f87Evan Cheng ++ri; 14354cce6b4c7882ef0cc993d931b90bf33985c96110Evan Cheng if (O.isDef()) { 14364cce6b4c7882ef0cc993d931b90bf33985c96110Evan Cheng assert(MI->getOpcode() == TargetInstrInfo::IMPLICIT_DEF && 14374cce6b4c7882ef0cc993d931b90bf33985c96110Evan Cheng "Register def was not rewritten?"); 14384cce6b4c7882ef0cc993d931b90bf33985c96110Evan Cheng RemoveMachineInstrFromMaps(MI); 14394cce6b4c7882ef0cc993d931b90bf33985c96110Evan Cheng vrm.RemoveMachineInstrFromMaps(MI); 14404cce6b4c7882ef0cc993d931b90bf33985c96110Evan Cheng MI->eraseFromParent(); 14414cce6b4c7882ef0cc993d931b90bf33985c96110Evan Cheng } else { 14424cce6b4c7882ef0cc993d931b90bf33985c96110Evan Cheng // This must be an use of an implicit_def so it's not part of the live 14434cce6b4c7882ef0cc993d931b90bf33985c96110Evan Cheng // interval. Create a new empty live interval for it. 14444cce6b4c7882ef0cc993d931b90bf33985c96110Evan Cheng // FIXME: Can we simply erase some of the instructions? e.g. Stores? 14454cce6b4c7882ef0cc993d931b90bf33985c96110Evan Cheng unsigned NewVReg = mri_->createVirtualRegister(rc); 14464cce6b4c7882ef0cc993d931b90bf33985c96110Evan Cheng vrm.grow(); 14474cce6b4c7882ef0cc993d931b90bf33985c96110Evan Cheng vrm.setIsImplicitlyDefined(NewVReg); 14484cce6b4c7882ef0cc993d931b90bf33985c96110Evan Cheng NewLIs.push_back(&getOrCreateInterval(NewVReg)); 14494cce6b4c7882ef0cc993d931b90bf33985c96110Evan Cheng for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) { 14504cce6b4c7882ef0cc993d931b90bf33985c96110Evan Cheng MachineOperand &MO = MI->getOperand(i); 14514cce6b4c7882ef0cc993d931b90bf33985c96110Evan Cheng if (MO.isReg() && MO.getReg() == li.reg) 14524cce6b4c7882ef0cc993d931b90bf33985c96110Evan Cheng MO.setReg(NewVReg); 14534cce6b4c7882ef0cc993d931b90bf33985c96110Evan Cheng } 14544cce6b4c7882ef0cc993d931b90bf33985c96110Evan Cheng } 1455419852ca8a01aecde4c0e20af6b7bd6450e70f87Evan Cheng } 1456419852ca8a01aecde4c0e20af6b7bd6450e70f87Evan Cheng} 1457419852ca8a01aecde4c0e20af6b7bd6450e70f87Evan Cheng 145881a038218171860ee4c382849c647d3dc841fe8bEvan Cheng 1459f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Chengstd::vector<LiveInterval*> LiveIntervals:: 146081a038218171860ee4c382849c647d3dc841fe8bEvan ChengaddIntervalsForSpills(const LiveInterval &li, 14619c3c2213647e3f1b71722d61875ebac01b65cb91Evan Cheng const MachineLoopInfo *loopInfo, VirtRegMap &vrm, 14629c3c2213647e3f1b71722d61875ebac01b65cb91Evan Cheng float &SSWeight) { 1463f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng assert(li.weight != HUGE_VALF && 1464f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng "attempt to spill already spilled interval!"); 1465f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng 1466f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng DOUT << "\t\t\t\tadding intervals for spills for interval: "; 14676f0d024a534af18d9e60b3ea757376cd8a3a980eDan Gohman li.print(DOUT, tri_); 1468f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng DOUT << '\n'; 1469f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng 14709c3c2213647e3f1b71722d61875ebac01b65cb91Evan Cheng // Spill slot weight. 14719c3c2213647e3f1b71722d61875ebac01b65cb91Evan Cheng SSWeight = 0.0f; 14729c3c2213647e3f1b71722d61875ebac01b65cb91Evan Cheng 147381a038218171860ee4c382849c647d3dc841fe8bEvan Cheng // Each bit specify whether it a spill is required in the MBB. 147481a038218171860ee4c382849c647d3dc841fe8bEvan Cheng BitVector SpillMBBs(mf_->getNumBlockIDs()); 14751953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng std::map<unsigned, std::vector<SRInfo> > SpillIdxes; 14760cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng BitVector RestoreMBBs(mf_->getNumBlockIDs()); 14771953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng std::map<unsigned, std::vector<SRInfo> > RestoreIdxes; 14781953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng std::map<unsigned,unsigned> MBBVRegsMap; 1479f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng std::vector<LiveInterval*> NewLIs; 1480d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng const TargetRegisterClass* rc = mri_->getRegClass(li.reg); 1481f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng 1482f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng unsigned NumValNums = li.getNumValNums(); 1483f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng SmallVector<MachineInstr*, 4> ReMatDefs; 1484f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng ReMatDefs.resize(NumValNums, NULL); 1485f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng SmallVector<MachineInstr*, 4> ReMatOrigDefs; 1486f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng ReMatOrigDefs.resize(NumValNums, NULL); 1487f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng SmallVector<int, 4> ReMatIds; 1488f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng ReMatIds.resize(NumValNums, VirtRegMap::MAX_STACK_SLOT); 1489f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng BitVector ReMatDelete(NumValNums); 1490f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng unsigned Slot = VirtRegMap::MAX_STACK_SLOT; 1491f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng 149281a038218171860ee4c382849c647d3dc841fe8bEvan Cheng // Spilling a split live interval. It cannot be split any further. Also, 149381a038218171860ee4c382849c647d3dc841fe8bEvan Cheng // it's also guaranteed to be a single val# / range interval. 149481a038218171860ee4c382849c647d3dc841fe8bEvan Cheng if (vrm.getPreSplitReg(li.reg)) { 149581a038218171860ee4c382849c647d3dc841fe8bEvan Cheng vrm.setIsSplitFromReg(li.reg, 0); 1496d120ffd26f2715c600b028d4eac9a3c41a9f4653Evan Cheng // Unset the split kill marker on the last use. 1497d120ffd26f2715c600b028d4eac9a3c41a9f4653Evan Cheng unsigned KillIdx = vrm.getKillPoint(li.reg); 1498d120ffd26f2715c600b028d4eac9a3c41a9f4653Evan Cheng if (KillIdx) { 1499d120ffd26f2715c600b028d4eac9a3c41a9f4653Evan Cheng MachineInstr *KillMI = getInstructionFromIndex(KillIdx); 1500d120ffd26f2715c600b028d4eac9a3c41a9f4653Evan Cheng assert(KillMI && "Last use disappeared?"); 1501d120ffd26f2715c600b028d4eac9a3c41a9f4653Evan Cheng int KillOp = KillMI->findRegisterUseOperandIdx(li.reg, true); 1502d120ffd26f2715c600b028d4eac9a3c41a9f4653Evan Cheng assert(KillOp != -1 && "Last use disappeared?"); 1503f73823000e2d5d6e1cf65bdf5a107297e18d35fbChris Lattner KillMI->getOperand(KillOp).setIsKill(false); 1504d120ffd26f2715c600b028d4eac9a3c41a9f4653Evan Cheng } 1505adf85906906ebf85c57c333e8209f37ef11a6c99Evan Cheng vrm.removeKillPoint(li.reg); 150681a038218171860ee4c382849c647d3dc841fe8bEvan Cheng bool DefIsReMat = vrm.isReMaterialized(li.reg); 150781a038218171860ee4c382849c647d3dc841fe8bEvan Cheng Slot = vrm.getStackSlot(li.reg); 150881a038218171860ee4c382849c647d3dc841fe8bEvan Cheng assert(Slot != VirtRegMap::MAX_STACK_SLOT); 150981a038218171860ee4c382849c647d3dc841fe8bEvan Cheng MachineInstr *ReMatDefMI = DefIsReMat ? 151081a038218171860ee4c382849c647d3dc841fe8bEvan Cheng vrm.getReMaterializedMI(li.reg) : NULL; 151181a038218171860ee4c382849c647d3dc841fe8bEvan Cheng int LdSlot = 0; 151281a038218171860ee4c382849c647d3dc841fe8bEvan Cheng bool isLoadSS = DefIsReMat && tii_->isLoadFromStackSlot(ReMatDefMI, LdSlot); 151381a038218171860ee4c382849c647d3dc841fe8bEvan Cheng bool isLoad = isLoadSS || 1514749c6f6b5ed301c84aac562e414486549d7b98ebChris Lattner (DefIsReMat && (ReMatDefMI->getDesc().isSimpleLoad())); 151581a038218171860ee4c382849c647d3dc841fe8bEvan Cheng bool IsFirstRange = true; 151681a038218171860ee4c382849c647d3dc841fe8bEvan Cheng for (LiveInterval::Ranges::const_iterator 151781a038218171860ee4c382849c647d3dc841fe8bEvan Cheng I = li.ranges.begin(), E = li.ranges.end(); I != E; ++I) { 151881a038218171860ee4c382849c647d3dc841fe8bEvan Cheng // If this is a split live interval with multiple ranges, it means there 151981a038218171860ee4c382849c647d3dc841fe8bEvan Cheng // are two-address instructions that re-defined the value. Only the 152081a038218171860ee4c382849c647d3dc841fe8bEvan Cheng // first def can be rematerialized! 152181a038218171860ee4c382849c647d3dc841fe8bEvan Cheng if (IsFirstRange) { 1522cb3c330d39442130d0587208d673ce9c33c7008fEvan Cheng // Note ReMatOrigDefMI has already been deleted. 152381a038218171860ee4c382849c647d3dc841fe8bEvan Cheng rewriteInstructionsForSpills(li, false, I, NULL, ReMatDefMI, 152481a038218171860ee4c382849c647d3dc841fe8bEvan Cheng Slot, LdSlot, isLoad, isLoadSS, DefIsReMat, 1525d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng false, vrm, rc, ReMatIds, loopInfo, 15260cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng SpillMBBs, SpillIdxes, RestoreMBBs, RestoreIdxes, 15279c3c2213647e3f1b71722d61875ebac01b65cb91Evan Cheng MBBVRegsMap, NewLIs, SSWeight); 152881a038218171860ee4c382849c647d3dc841fe8bEvan Cheng } else { 152981a038218171860ee4c382849c647d3dc841fe8bEvan Cheng rewriteInstructionsForSpills(li, false, I, NULL, 0, 153081a038218171860ee4c382849c647d3dc841fe8bEvan Cheng Slot, 0, false, false, false, 1531d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng false, vrm, rc, ReMatIds, loopInfo, 15320cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng SpillMBBs, SpillIdxes, RestoreMBBs, RestoreIdxes, 15339c3c2213647e3f1b71722d61875ebac01b65cb91Evan Cheng MBBVRegsMap, NewLIs, SSWeight); 153481a038218171860ee4c382849c647d3dc841fe8bEvan Cheng } 153581a038218171860ee4c382849c647d3dc841fe8bEvan Cheng IsFirstRange = false; 153681a038218171860ee4c382849c647d3dc841fe8bEvan Cheng } 1537419852ca8a01aecde4c0e20af6b7bd6450e70f87Evan Cheng 15389c3c2213647e3f1b71722d61875ebac01b65cb91Evan Cheng SSWeight = 0.0f; // Already accounted for when split. 15394cce6b4c7882ef0cc993d931b90bf33985c96110Evan Cheng handleSpilledImpDefs(li, vrm, rc, NewLIs); 154081a038218171860ee4c382849c647d3dc841fe8bEvan Cheng return NewLIs; 154181a038218171860ee4c382849c647d3dc841fe8bEvan Cheng } 154281a038218171860ee4c382849c647d3dc841fe8bEvan Cheng 154381a038218171860ee4c382849c647d3dc841fe8bEvan Cheng bool TrySplit = SplitAtBB && !intervalIsInOneMBB(li); 15440cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng if (SplitLimit != -1 && (int)numSplits >= SplitLimit) 15450cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng TrySplit = false; 15460cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng if (TrySplit) 15470cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng ++numSplits; 1548f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng bool NeedStackSlot = false; 1549f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng for (LiveInterval::const_vni_iterator i = li.vni_begin(), e = li.vni_end(); 1550f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng i != e; ++i) { 1551f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng const VNInfo *VNI = *i; 1552f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng unsigned VN = VNI->id; 1553f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng unsigned DefIdx = VNI->def; 1554f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng if (DefIdx == ~1U) 1555f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng continue; // Dead val#. 1556f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng // Is the def for the val# rematerializable? 155781a038218171860ee4c382849c647d3dc841fe8bEvan Cheng MachineInstr *ReMatDefMI = (DefIdx == ~0u) 155881a038218171860ee4c382849c647d3dc841fe8bEvan Cheng ? 0 : getInstructionFromIndex(DefIdx); 15595ef3a04b542c4e585276768fa9ca2af698ef5c87Evan Cheng bool dummy; 15605ef3a04b542c4e585276768fa9ca2af698ef5c87Evan Cheng if (ReMatDefMI && isReMaterializable(li, VNI, ReMatDefMI, dummy)) { 1561f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng // Remember how to remat the def of this val#. 156281a038218171860ee4c382849c647d3dc841fe8bEvan Cheng ReMatOrigDefs[VN] = ReMatDefMI; 1563f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng // Original def may be modified so we have to make a copy here. vrm must 1564f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng // delete these! 15658e5f2c6f65841542e2a7092553fe42a00048e4c7Dan Gohman ReMatDefs[VN] = ReMatDefMI = mf_->CloneMachineInstr(ReMatDefMI); 1566f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng 1567f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng bool CanDelete = true; 1568c3fc7d9ec9b495c8a88cd854247105c296d3aabdEvan Cheng if (VNI->hasPHIKill) { 1569c3fc7d9ec9b495c8a88cd854247105c296d3aabdEvan Cheng // A kill is a phi node, not all of its uses can be rematerialized. 1570f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng // It must not be deleted. 1571c3fc7d9ec9b495c8a88cd854247105c296d3aabdEvan Cheng CanDelete = false; 1572c3fc7d9ec9b495c8a88cd854247105c296d3aabdEvan Cheng // Need a stack slot if there is any live range where uses cannot be 1573c3fc7d9ec9b495c8a88cd854247105c296d3aabdEvan Cheng // rematerialized. 1574c3fc7d9ec9b495c8a88cd854247105c296d3aabdEvan Cheng NeedStackSlot = true; 1575f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng } 1576f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng if (CanDelete) 1577f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng ReMatDelete.set(VN); 1578f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng } else { 1579f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng // Need a stack slot if there is any live range where uses cannot be 1580f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng // rematerialized. 1581f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng NeedStackSlot = true; 1582f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng } 1583f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng } 1584f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng 1585f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng // One stack slot per live interval. 158681a038218171860ee4c382849c647d3dc841fe8bEvan Cheng if (NeedStackSlot && vrm.getPreSplitReg(li.reg) == 0) 1587f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng Slot = vrm.assignVirt2StackSlot(li.reg); 1588f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng 1589f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng // Create new intervals and rewrite defs and uses. 1590f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng for (LiveInterval::Ranges::const_iterator 1591f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng I = li.ranges.begin(), E = li.ranges.end(); I != E; ++I) { 159281a038218171860ee4c382849c647d3dc841fe8bEvan Cheng MachineInstr *ReMatDefMI = ReMatDefs[I->valno->id]; 159381a038218171860ee4c382849c647d3dc841fe8bEvan Cheng MachineInstr *ReMatOrigDefMI = ReMatOrigDefs[I->valno->id]; 159481a038218171860ee4c382849c647d3dc841fe8bEvan Cheng bool DefIsReMat = ReMatDefMI != NULL; 1595f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng bool CanDelete = ReMatDelete[I->valno->id]; 1596f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng int LdSlot = 0; 159781a038218171860ee4c382849c647d3dc841fe8bEvan Cheng bool isLoadSS = DefIsReMat && tii_->isLoadFromStackSlot(ReMatDefMI, LdSlot); 1598f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng bool isLoad = isLoadSS || 1599749c6f6b5ed301c84aac562e414486549d7b98ebChris Lattner (DefIsReMat && ReMatDefMI->getDesc().isSimpleLoad()); 160081a038218171860ee4c382849c647d3dc841fe8bEvan Cheng rewriteInstructionsForSpills(li, TrySplit, I, ReMatOrigDefMI, ReMatDefMI, 16010cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng Slot, LdSlot, isLoad, isLoadSS, DefIsReMat, 1602d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng CanDelete, vrm, rc, ReMatIds, loopInfo, 16030cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng SpillMBBs, SpillIdxes, RestoreMBBs, RestoreIdxes, 16049c3c2213647e3f1b71722d61875ebac01b65cb91Evan Cheng MBBVRegsMap, NewLIs, SSWeight); 1605f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng } 1606f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng 16070cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng // Insert spills / restores if we are splitting. 1608419852ca8a01aecde4c0e20af6b7bd6450e70f87Evan Cheng if (!TrySplit) { 16094cce6b4c7882ef0cc993d931b90bf33985c96110Evan Cheng handleSpilledImpDefs(li, vrm, rc, NewLIs); 16101953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng return NewLIs; 1611419852ca8a01aecde4c0e20af6b7bd6450e70f87Evan Cheng } 16121953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng 1613b50bb8cf197709b3f49044740044c06d8f314564Evan Cheng SmallPtrSet<LiveInterval*, 4> AddedKill; 1614aee4af68ae2016afc5b4ec0c430e539c5810a766Evan Cheng SmallVector<unsigned, 2> Ops; 16151953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng if (NeedStackSlot) { 16161953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng int Id = SpillMBBs.find_first(); 16171953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng while (Id != -1) { 16189c3c2213647e3f1b71722d61875ebac01b65cb91Evan Cheng MachineBasicBlock *MBB = mf_->getBlockNumbered(Id); 16199c3c2213647e3f1b71722d61875ebac01b65cb91Evan Cheng unsigned loopDepth = loopInfo->getLoopDepth(MBB); 16201953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng std::vector<SRInfo> &spills = SpillIdxes[Id]; 16211953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng for (unsigned i = 0, e = spills.size(); i != e; ++i) { 16221953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng int index = spills[i].index; 16231953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng unsigned VReg = spills[i].vreg; 1624597d10d84fb6b34f7776121404d5ed802b21b2b6Evan Cheng LiveInterval &nI = getOrCreateInterval(VReg); 16250cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng bool isReMat = vrm.isReMaterialized(VReg); 16260cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng MachineInstr *MI = getInstructionFromIndex(index); 1627aee4af68ae2016afc5b4ec0c430e539c5810a766Evan Cheng bool CanFold = false; 1628aee4af68ae2016afc5b4ec0c430e539c5810a766Evan Cheng bool FoundUse = false; 1629aee4af68ae2016afc5b4ec0c430e539c5810a766Evan Cheng Ops.clear(); 1630cddbb83ea82e98658d9f530c50a7b9d23249afc2Evan Cheng if (spills[i].canFold) { 1631aee4af68ae2016afc5b4ec0c430e539c5810a766Evan Cheng CanFold = true; 16320cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng for (unsigned j = 0, ee = MI->getNumOperands(); j != ee; ++j) { 16330cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng MachineOperand &MO = MI->getOperand(j); 16340cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng if (!MO.isRegister() || MO.getReg() != VReg) 16350cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng continue; 1636aee4af68ae2016afc5b4ec0c430e539c5810a766Evan Cheng 1637aee4af68ae2016afc5b4ec0c430e539c5810a766Evan Cheng Ops.push_back(j); 1638aee4af68ae2016afc5b4ec0c430e539c5810a766Evan Cheng if (MO.isDef()) 1639cddbb83ea82e98658d9f530c50a7b9d23249afc2Evan Cheng continue; 1640aee4af68ae2016afc5b4ec0c430e539c5810a766Evan Cheng if (isReMat || 1641aee4af68ae2016afc5b4ec0c430e539c5810a766Evan Cheng (!FoundUse && !alsoFoldARestore(Id, index, VReg, 1642aee4af68ae2016afc5b4ec0c430e539c5810a766Evan Cheng RestoreMBBs, RestoreIdxes))) { 1643aee4af68ae2016afc5b4ec0c430e539c5810a766Evan Cheng // MI has two-address uses of the same register. If the use 1644aee4af68ae2016afc5b4ec0c430e539c5810a766Evan Cheng // isn't the first and only use in the BB, then we can't fold 1645aee4af68ae2016afc5b4ec0c430e539c5810a766Evan Cheng // it. FIXME: Move this to rewriteInstructionsForSpills. 1646aee4af68ae2016afc5b4ec0c430e539c5810a766Evan Cheng CanFold = false; 1647cddbb83ea82e98658d9f530c50a7b9d23249afc2Evan Cheng break; 1648cddbb83ea82e98658d9f530c50a7b9d23249afc2Evan Cheng } 1649aee4af68ae2016afc5b4ec0c430e539c5810a766Evan Cheng FoundUse = true; 16500cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng } 16510cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng } 16520cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng // Fold the store into the def if possible. 1653cddbb83ea82e98658d9f530c50a7b9d23249afc2Evan Cheng bool Folded = false; 1654aee4af68ae2016afc5b4ec0c430e539c5810a766Evan Cheng if (CanFold && !Ops.empty()) { 1655aee4af68ae2016afc5b4ec0c430e539c5810a766Evan Cheng if (tryFoldMemoryOperand(MI, vrm, NULL, index, Ops, true, Slot,VReg)){ 1656cddbb83ea82e98658d9f530c50a7b9d23249afc2Evan Cheng Folded = true; 1657f38d14f03e495ea98ae16bda6febbde276513294Evan Cheng if (FoundUse > 0) { 1658aee4af68ae2016afc5b4ec0c430e539c5810a766Evan Cheng // Also folded uses, do not issue a load. 1659aee4af68ae2016afc5b4ec0c430e539c5810a766Evan Cheng eraseRestoreInfo(Id, index, VReg, RestoreMBBs, RestoreIdxes); 1660f38d14f03e495ea98ae16bda6febbde276513294Evan Cheng nI.removeRange(getLoadIndex(index), getUseIndex(index)+1); 1661f38d14f03e495ea98ae16bda6febbde276513294Evan Cheng } 1662597d10d84fb6b34f7776121404d5ed802b21b2b6Evan Cheng nI.removeRange(getDefIndex(index), getStoreIndex(index)); 1663cddbb83ea82e98658d9f530c50a7b9d23249afc2Evan Cheng } 16640cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng } 16650cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng 16667e073baedb8232b9519dbe15ea141ff98ccfe6aeEvan Cheng // Otherwise tell the spiller to issue a spill. 1667b50bb8cf197709b3f49044740044c06d8f314564Evan Cheng if (!Folded) { 1668b50bb8cf197709b3f49044740044c06d8f314564Evan Cheng LiveRange *LR = &nI.ranges[nI.ranges.size()-1]; 1669b50bb8cf197709b3f49044740044c06d8f314564Evan Cheng bool isKill = LR->end == getStoreIndex(index); 1670b0a6f62c9b2e75fc509d84310a9795ffacbc6796Evan Cheng if (!MI->registerDefIsDead(nI.reg)) 1671b0a6f62c9b2e75fc509d84310a9795ffacbc6796Evan Cheng // No need to spill a dead def. 1672b0a6f62c9b2e75fc509d84310a9795ffacbc6796Evan Cheng vrm.addSpillPoint(VReg, isKill, MI); 1673b50bb8cf197709b3f49044740044c06d8f314564Evan Cheng if (isKill) 1674b50bb8cf197709b3f49044740044c06d8f314564Evan Cheng AddedKill.insert(&nI); 1675b50bb8cf197709b3f49044740044c06d8f314564Evan Cheng } 16769c3c2213647e3f1b71722d61875ebac01b65cb91Evan Cheng 16779c3c2213647e3f1b71722d61875ebac01b65cb91Evan Cheng // Update spill slot weight. 16789c3c2213647e3f1b71722d61875ebac01b65cb91Evan Cheng if (!isReMat) 1679c3417609ae6e744a29be6962d4fb7811c0102d17Evan Cheng SSWeight += getSpillWeight(true, false, loopDepth); 16800cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng } 16811953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng Id = SpillMBBs.find_next(Id); 16820cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng } 16831953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng } 16840cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng 16851953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng int Id = RestoreMBBs.find_first(); 16861953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng while (Id != -1) { 16879c3c2213647e3f1b71722d61875ebac01b65cb91Evan Cheng MachineBasicBlock *MBB = mf_->getBlockNumbered(Id); 16889c3c2213647e3f1b71722d61875ebac01b65cb91Evan Cheng unsigned loopDepth = loopInfo->getLoopDepth(MBB); 16899c3c2213647e3f1b71722d61875ebac01b65cb91Evan Cheng 16901953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng std::vector<SRInfo> &restores = RestoreIdxes[Id]; 16911953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng for (unsigned i = 0, e = restores.size(); i != e; ++i) { 16921953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng int index = restores[i].index; 16931953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng if (index == -1) 16941953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng continue; 16951953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng unsigned VReg = restores[i].vreg; 1696597d10d84fb6b34f7776121404d5ed802b21b2b6Evan Cheng LiveInterval &nI = getOrCreateInterval(VReg); 16979c3c2213647e3f1b71722d61875ebac01b65cb91Evan Cheng bool isReMat = vrm.isReMaterialized(VReg); 169881a038218171860ee4c382849c647d3dc841fe8bEvan Cheng MachineInstr *MI = getInstructionFromIndex(index); 1699aee4af68ae2016afc5b4ec0c430e539c5810a766Evan Cheng bool CanFold = false; 1700aee4af68ae2016afc5b4ec0c430e539c5810a766Evan Cheng Ops.clear(); 1701cddbb83ea82e98658d9f530c50a7b9d23249afc2Evan Cheng if (restores[i].canFold) { 1702aee4af68ae2016afc5b4ec0c430e539c5810a766Evan Cheng CanFold = true; 170381a038218171860ee4c382849c647d3dc841fe8bEvan Cheng for (unsigned j = 0, ee = MI->getNumOperands(); j != ee; ++j) { 170481a038218171860ee4c382849c647d3dc841fe8bEvan Cheng MachineOperand &MO = MI->getOperand(j); 170581a038218171860ee4c382849c647d3dc841fe8bEvan Cheng if (!MO.isRegister() || MO.getReg() != VReg) 170681a038218171860ee4c382849c647d3dc841fe8bEvan Cheng continue; 1707aee4af68ae2016afc5b4ec0c430e539c5810a766Evan Cheng 17080cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng if (MO.isDef()) { 1709aee4af68ae2016afc5b4ec0c430e539c5810a766Evan Cheng // If this restore were to be folded, it would have been folded 1710aee4af68ae2016afc5b4ec0c430e539c5810a766Evan Cheng // already. 1711aee4af68ae2016afc5b4ec0c430e539c5810a766Evan Cheng CanFold = false; 171281a038218171860ee4c382849c647d3dc841fe8bEvan Cheng break; 171381a038218171860ee4c382849c647d3dc841fe8bEvan Cheng } 1714aee4af68ae2016afc5b4ec0c430e539c5810a766Evan Cheng Ops.push_back(j); 171581a038218171860ee4c382849c647d3dc841fe8bEvan Cheng } 171681a038218171860ee4c382849c647d3dc841fe8bEvan Cheng } 17170cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng 17180cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng // Fold the load into the use if possible. 1719cddbb83ea82e98658d9f530c50a7b9d23249afc2Evan Cheng bool Folded = false; 1720aee4af68ae2016afc5b4ec0c430e539c5810a766Evan Cheng if (CanFold && !Ops.empty()) { 17219c3c2213647e3f1b71722d61875ebac01b65cb91Evan Cheng if (!isReMat) 1722aee4af68ae2016afc5b4ec0c430e539c5810a766Evan Cheng Folded = tryFoldMemoryOperand(MI, vrm, NULL,index,Ops,true,Slot,VReg); 1723aee4af68ae2016afc5b4ec0c430e539c5810a766Evan Cheng else { 17240cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng MachineInstr *ReMatDefMI = vrm.getReMaterializedMI(VReg); 17250cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng int LdSlot = 0; 17260cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng bool isLoadSS = tii_->isLoadFromStackSlot(ReMatDefMI, LdSlot); 17270cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng // If the rematerializable def is a load, also try to fold it. 1728749c6f6b5ed301c84aac562e414486549d7b98ebChris Lattner if (isLoadSS || ReMatDefMI->getDesc().isSimpleLoad()) 1729aee4af68ae2016afc5b4ec0c430e539c5810a766Evan Cheng Folded = tryFoldMemoryOperand(MI, vrm, ReMatDefMI, index, 1730aee4af68ae2016afc5b4ec0c430e539c5810a766Evan Cheng Ops, isLoadSS, LdSlot, VReg); 1731d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng unsigned ImpUse = getReMatImplicitUse(li, ReMatDefMI); 1732d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng if (ImpUse) { 1733d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng // Re-matting an instruction with virtual register use. Add the 1734d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng // register as an implicit use on the use MI and update the register 173524d2f8a212f08bf21360122cc00acf2657af91f9Evan Cheng // interval's spill weight to HUGE_VALF to prevent it from being 173624d2f8a212f08bf21360122cc00acf2657af91f9Evan Cheng // spilled. 1737d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng LiveInterval &ImpLi = getInterval(ImpUse); 173824d2f8a212f08bf21360122cc00acf2657af91f9Evan Cheng ImpLi.weight = HUGE_VALF; 1739d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng MI->addOperand(MachineOperand::CreateReg(ImpUse, false, true)); 1740d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng } 1741aee4af68ae2016afc5b4ec0c430e539c5810a766Evan Cheng } 17420cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng } 17430cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng // If folding is not possible / failed, then tell the spiller to issue a 17440cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng // load / rematerialization for us. 1745597d10d84fb6b34f7776121404d5ed802b21b2b6Evan Cheng if (Folded) 1746597d10d84fb6b34f7776121404d5ed802b21b2b6Evan Cheng nI.removeRange(getLoadIndex(index), getUseIndex(index)+1); 1747b50bb8cf197709b3f49044740044c06d8f314564Evan Cheng else 17480cbb1164b3227f25f5e5d3681800a8e50e6b9865Evan Cheng vrm.addRestorePoint(VReg, MI); 17499c3c2213647e3f1b71722d61875ebac01b65cb91Evan Cheng 17509c3c2213647e3f1b71722d61875ebac01b65cb91Evan Cheng // Update spill slot weight. 17519c3c2213647e3f1b71722d61875ebac01b65cb91Evan Cheng if (!isReMat) 1752c3417609ae6e744a29be6962d4fb7811c0102d17Evan Cheng SSWeight += getSpillWeight(false, true, loopDepth); 175381a038218171860ee4c382849c647d3dc841fe8bEvan Cheng } 17541953d0cb7d6d27da3ad067468a7ad6dd7c4fa46eEvan Cheng Id = RestoreMBBs.find_next(Id); 175581a038218171860ee4c382849c647d3dc841fe8bEvan Cheng } 175681a038218171860ee4c382849c647d3dc841fe8bEvan Cheng 1757b50bb8cf197709b3f49044740044c06d8f314564Evan Cheng // Finalize intervals: add kills, finalize spill weights, and filter out 1758b50bb8cf197709b3f49044740044c06d8f314564Evan Cheng // dead intervals. 1759597d10d84fb6b34f7776121404d5ed802b21b2b6Evan Cheng std::vector<LiveInterval*> RetNewLIs; 1760597d10d84fb6b34f7776121404d5ed802b21b2b6Evan Cheng for (unsigned i = 0, e = NewLIs.size(); i != e; ++i) { 1761597d10d84fb6b34f7776121404d5ed802b21b2b6Evan Cheng LiveInterval *LI = NewLIs[i]; 1762597d10d84fb6b34f7776121404d5ed802b21b2b6Evan Cheng if (!LI->empty()) { 1763597d10d84fb6b34f7776121404d5ed802b21b2b6Evan Cheng LI->weight /= LI->getSize(); 1764b50bb8cf197709b3f49044740044c06d8f314564Evan Cheng if (!AddedKill.count(LI)) { 1765b50bb8cf197709b3f49044740044c06d8f314564Evan Cheng LiveRange *LR = &LI->ranges[LI->ranges.size()-1]; 1766d120ffd26f2715c600b028d4eac9a3c41a9f4653Evan Cheng unsigned LastUseIdx = getBaseIndex(LR->end); 1767d120ffd26f2715c600b028d4eac9a3c41a9f4653Evan Cheng MachineInstr *LastUse = getInstructionFromIndex(LastUseIdx); 17686130f66eaae89f8878590796977678afa8448926Evan Cheng int UseIdx = LastUse->findRegisterUseOperandIdx(LI->reg, false); 1769b50bb8cf197709b3f49044740044c06d8f314564Evan Cheng assert(UseIdx != -1); 1770d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng if (LastUse->getOperand(UseIdx).isImplicit() || 1771d70dbb5d627a0408eccf88033143efa62ee0e6c0Evan Cheng LastUse->getDesc().getOperandConstraint(UseIdx,TOI::TIED_TO) == -1){ 1772b50bb8cf197709b3f49044740044c06d8f314564Evan Cheng LastUse->getOperand(UseIdx).setIsKill(); 1773d120ffd26f2715c600b028d4eac9a3c41a9f4653Evan Cheng vrm.addKillPoint(LI->reg, LastUseIdx); 1774adf85906906ebf85c57c333e8209f37ef11a6c99Evan Cheng } 1775b50bb8cf197709b3f49044740044c06d8f314564Evan Cheng } 1776597d10d84fb6b34f7776121404d5ed802b21b2b6Evan Cheng RetNewLIs.push_back(LI); 1777597d10d84fb6b34f7776121404d5ed802b21b2b6Evan Cheng } 1778597d10d84fb6b34f7776121404d5ed802b21b2b6Evan Cheng } 177981a038218171860ee4c382849c647d3dc841fe8bEvan Cheng 17804cce6b4c7882ef0cc993d931b90bf33985c96110Evan Cheng handleSpilledImpDefs(li, vrm, rc, RetNewLIs); 1781597d10d84fb6b34f7776121404d5ed802b21b2b6Evan Cheng return RetNewLIs; 1782f2fbca68f868122d6df0bfc9952b4e4c3dfb60b7Evan Cheng} 1783676dd7c80b6f91178452535ac45ca58feb23cc42Evan Cheng 1784676dd7c80b6f91178452535ac45ca58feb23cc42Evan Cheng/// hasAllocatableSuperReg - Return true if the specified physical register has 1785676dd7c80b6f91178452535ac45ca58feb23cc42Evan Cheng/// any super register that's allocatable. 1786676dd7c80b6f91178452535ac45ca58feb23cc42Evan Chengbool LiveIntervals::hasAllocatableSuperReg(unsigned Reg) const { 1787676dd7c80b6f91178452535ac45ca58feb23cc42Evan Cheng for (const unsigned* AS = tri_->getSuperRegisters(Reg); *AS; ++AS) 1788676dd7c80b6f91178452535ac45ca58feb23cc42Evan Cheng if (allocatableRegs_[*AS] && hasInterval(*AS)) 1789676dd7c80b6f91178452535ac45ca58feb23cc42Evan Cheng return true; 1790676dd7c80b6f91178452535ac45ca58feb23cc42Evan Cheng return false; 1791676dd7c80b6f91178452535ac45ca58feb23cc42Evan Cheng} 1792676dd7c80b6f91178452535ac45ca58feb23cc42Evan Cheng 1793676dd7c80b6f91178452535ac45ca58feb23cc42Evan Cheng/// getRepresentativeReg - Find the largest super register of the specified 1794676dd7c80b6f91178452535ac45ca58feb23cc42Evan Cheng/// physical register. 1795676dd7c80b6f91178452535ac45ca58feb23cc42Evan Chengunsigned LiveIntervals::getRepresentativeReg(unsigned Reg) const { 1796676dd7c80b6f91178452535ac45ca58feb23cc42Evan Cheng // Find the largest super-register that is allocatable. 1797676dd7c80b6f91178452535ac45ca58feb23cc42Evan Cheng unsigned BestReg = Reg; 1798676dd7c80b6f91178452535ac45ca58feb23cc42Evan Cheng for (const unsigned* AS = tri_->getSuperRegisters(Reg); *AS; ++AS) { 1799676dd7c80b6f91178452535ac45ca58feb23cc42Evan Cheng unsigned SuperReg = *AS; 1800676dd7c80b6f91178452535ac45ca58feb23cc42Evan Cheng if (!hasAllocatableSuperReg(SuperReg) && hasInterval(SuperReg)) { 1801676dd7c80b6f91178452535ac45ca58feb23cc42Evan Cheng BestReg = SuperReg; 1802676dd7c80b6f91178452535ac45ca58feb23cc42Evan Cheng break; 1803676dd7c80b6f91178452535ac45ca58feb23cc42Evan Cheng } 1804676dd7c80b6f91178452535ac45ca58feb23cc42Evan Cheng } 1805676dd7c80b6f91178452535ac45ca58feb23cc42Evan Cheng return BestReg; 1806676dd7c80b6f91178452535ac45ca58feb23cc42Evan Cheng} 1807676dd7c80b6f91178452535ac45ca58feb23cc42Evan Cheng 1808676dd7c80b6f91178452535ac45ca58feb23cc42Evan Cheng/// getNumConflictsWithPhysReg - Return the number of uses and defs of the 1809676dd7c80b6f91178452535ac45ca58feb23cc42Evan Cheng/// specified interval that conflicts with the specified physical register. 1810676dd7c80b6f91178452535ac45ca58feb23cc42Evan Chengunsigned LiveIntervals::getNumConflictsWithPhysReg(const LiveInterval &li, 1811676dd7c80b6f91178452535ac45ca58feb23cc42Evan Cheng unsigned PhysReg) const { 1812676dd7c80b6f91178452535ac45ca58feb23cc42Evan Cheng unsigned NumConflicts = 0; 1813676dd7c80b6f91178452535ac45ca58feb23cc42Evan Cheng const LiveInterval &pli = getInterval(getRepresentativeReg(PhysReg)); 1814676dd7c80b6f91178452535ac45ca58feb23cc42Evan Cheng for (MachineRegisterInfo::reg_iterator I = mri_->reg_begin(li.reg), 1815676dd7c80b6f91178452535ac45ca58feb23cc42Evan Cheng E = mri_->reg_end(); I != E; ++I) { 1816676dd7c80b6f91178452535ac45ca58feb23cc42Evan Cheng MachineOperand &O = I.getOperand(); 1817676dd7c80b6f91178452535ac45ca58feb23cc42Evan Cheng MachineInstr *MI = O.getParent(); 1818676dd7c80b6f91178452535ac45ca58feb23cc42Evan Cheng unsigned Index = getInstructionIndex(MI); 1819676dd7c80b6f91178452535ac45ca58feb23cc42Evan Cheng if (pli.liveAt(Index)) 1820676dd7c80b6f91178452535ac45ca58feb23cc42Evan Cheng ++NumConflicts; 1821676dd7c80b6f91178452535ac45ca58feb23cc42Evan Cheng } 1822676dd7c80b6f91178452535ac45ca58feb23cc42Evan Cheng return NumConflicts; 1823676dd7c80b6f91178452535ac45ca58feb23cc42Evan Cheng} 1824676dd7c80b6f91178452535ac45ca58feb23cc42Evan Cheng 1825676dd7c80b6f91178452535ac45ca58feb23cc42Evan Cheng/// spillPhysRegAroundRegDefsUses - Spill the specified physical register 1826676dd7c80b6f91178452535ac45ca58feb23cc42Evan Cheng/// around all defs and uses of the specified interval. 1827676dd7c80b6f91178452535ac45ca58feb23cc42Evan Chengvoid LiveIntervals::spillPhysRegAroundRegDefsUses(const LiveInterval &li, 1828676dd7c80b6f91178452535ac45ca58feb23cc42Evan Cheng unsigned PhysReg, VirtRegMap &vrm) { 1829676dd7c80b6f91178452535ac45ca58feb23cc42Evan Cheng unsigned SpillReg = getRepresentativeReg(PhysReg); 1830676dd7c80b6f91178452535ac45ca58feb23cc42Evan Cheng 1831676dd7c80b6f91178452535ac45ca58feb23cc42Evan Cheng for (const unsigned *AS = tri_->getAliasSet(PhysReg); *AS; ++AS) 1832676dd7c80b6f91178452535ac45ca58feb23cc42Evan Cheng // If there are registers which alias PhysReg, but which are not a 1833676dd7c80b6f91178452535ac45ca58feb23cc42Evan Cheng // sub-register of the chosen representative super register. Assert 1834676dd7c80b6f91178452535ac45ca58feb23cc42Evan Cheng // since we can't handle it yet. 1835676dd7c80b6f91178452535ac45ca58feb23cc42Evan Cheng assert(*AS == SpillReg || !allocatableRegs_[*AS] || 1836676dd7c80b6f91178452535ac45ca58feb23cc42Evan Cheng tri_->isSuperRegister(*AS, SpillReg)); 1837676dd7c80b6f91178452535ac45ca58feb23cc42Evan Cheng 1838676dd7c80b6f91178452535ac45ca58feb23cc42Evan Cheng LiveInterval &pli = getInterval(SpillReg); 1839676dd7c80b6f91178452535ac45ca58feb23cc42Evan Cheng SmallPtrSet<MachineInstr*, 8> SeenMIs; 1840676dd7c80b6f91178452535ac45ca58feb23cc42Evan Cheng for (MachineRegisterInfo::reg_iterator I = mri_->reg_begin(li.reg), 1841676dd7c80b6f91178452535ac45ca58feb23cc42Evan Cheng E = mri_->reg_end(); I != E; ++I) { 1842676dd7c80b6f91178452535ac45ca58feb23cc42Evan Cheng MachineOperand &O = I.getOperand(); 1843676dd7c80b6f91178452535ac45ca58feb23cc42Evan Cheng MachineInstr *MI = O.getParent(); 1844676dd7c80b6f91178452535ac45ca58feb23cc42Evan Cheng if (SeenMIs.count(MI)) 1845676dd7c80b6f91178452535ac45ca58feb23cc42Evan Cheng continue; 1846676dd7c80b6f91178452535ac45ca58feb23cc42Evan Cheng SeenMIs.insert(MI); 1847676dd7c80b6f91178452535ac45ca58feb23cc42Evan Cheng unsigned Index = getInstructionIndex(MI); 1848676dd7c80b6f91178452535ac45ca58feb23cc42Evan Cheng if (pli.liveAt(Index)) { 1849676dd7c80b6f91178452535ac45ca58feb23cc42Evan Cheng vrm.addEmergencySpill(SpillReg, MI); 1850676dd7c80b6f91178452535ac45ca58feb23cc42Evan Cheng pli.removeRange(getLoadIndex(Index), getStoreIndex(Index)+1); 1851676dd7c80b6f91178452535ac45ca58feb23cc42Evan Cheng for (const unsigned* AS = tri_->getSubRegisters(SpillReg); *AS; ++AS) { 1852676dd7c80b6f91178452535ac45ca58feb23cc42Evan Cheng if (!hasInterval(*AS)) 1853676dd7c80b6f91178452535ac45ca58feb23cc42Evan Cheng continue; 1854676dd7c80b6f91178452535ac45ca58feb23cc42Evan Cheng LiveInterval &spli = getInterval(*AS); 1855676dd7c80b6f91178452535ac45ca58feb23cc42Evan Cheng if (spli.liveAt(Index)) 1856676dd7c80b6f91178452535ac45ca58feb23cc42Evan Cheng spli.removeRange(getLoadIndex(Index), getStoreIndex(Index)+1); 1857676dd7c80b6f91178452535ac45ca58feb23cc42Evan Cheng } 1858676dd7c80b6f91178452535ac45ca58feb23cc42Evan Cheng } 1859676dd7c80b6f91178452535ac45ca58feb23cc42Evan Cheng } 1860676dd7c80b6f91178452535ac45ca58feb23cc42Evan Cheng} 1861c4dc132c8a787fc41b6a162121251234aa618965Owen Anderson 1862c4dc132c8a787fc41b6a162121251234aa618965Owen AndersonLiveRange LiveIntervals::addLiveRangeToEndOfBlock(unsigned reg, 1863c4dc132c8a787fc41b6a162121251234aa618965Owen Anderson MachineInstr* startInst) { 1864c4dc132c8a787fc41b6a162121251234aa618965Owen Anderson LiveInterval& Interval = getOrCreateInterval(reg); 1865c4dc132c8a787fc41b6a162121251234aa618965Owen Anderson VNInfo* VN = Interval.getNextValue( 1866c4dc132c8a787fc41b6a162121251234aa618965Owen Anderson getInstructionIndex(startInst) + InstrSlots::DEF, 1867c4dc132c8a787fc41b6a162121251234aa618965Owen Anderson startInst, getVNInfoAllocator()); 1868c4dc132c8a787fc41b6a162121251234aa618965Owen Anderson VN->hasPHIKill = true; 1869c4dc132c8a787fc41b6a162121251234aa618965Owen Anderson VN->kills.push_back(getMBBEndIdx(startInst->getParent())); 1870c4dc132c8a787fc41b6a162121251234aa618965Owen Anderson LiveRange LR(getInstructionIndex(startInst) + InstrSlots::DEF, 1871c4dc132c8a787fc41b6a162121251234aa618965Owen Anderson getMBBEndIdx(startInst->getParent()) + 1, VN); 1872c4dc132c8a787fc41b6a162121251234aa618965Owen Anderson Interval.addRange(LR); 1873c4dc132c8a787fc41b6a162121251234aa618965Owen Anderson 1874c4dc132c8a787fc41b6a162121251234aa618965Owen Anderson return LR; 1875c4dc132c8a787fc41b6a162121251234aa618965Owen Anderson} 1876