LiveIntervalAnalysis.cpp revision e1b9536d546b78f8cffc7efbb2ff75d7e15f9749
1ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos//===-- LiveIntervals.cpp - Live Interval Analysis ------------------------===// 2ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos// 3ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos// The LLVM Compiler Infrastructure 4ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos// 5ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos// This file was developed by the LLVM research group and is distributed under 6ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos// the University of Illinois Open Source 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" 1998e17cf54345a4e9ab0ded690cdb41c0cd219c8eAlkis Evlogimenos#include "LiveIntervals.h" 20015959ee38e4fd4a920f6b0065c50e524762f580Chris Lattner#include "llvm/Value.h" 216b4edbaaf9021e0434f0ce0c3724eb43ed41b770Alkis Evlogimenos#include "llvm/Analysis/LoopInfo.h" 22ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos#include "llvm/CodeGen/LiveVariables.h" 23ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos#include "llvm/CodeGen/MachineFrameInfo.h" 24ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos#include "llvm/CodeGen/MachineInstr.h" 25ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos#include "llvm/CodeGen/Passes.h" 26ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos#include "llvm/CodeGen/SSARegMap.h" 27ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos#include "llvm/Target/MRegisterInfo.h" 28ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos#include "llvm/Target/TargetInstrInfo.h" 29ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos#include "llvm/Target/TargetMachine.h" 30e88280a4224730dcf8076e0d9a20973c5761fd06Alkis Evlogimenos#include "Support/CommandLine.h" 31ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos#include "Support/Debug.h" 32ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos#include "Support/Statistic.h" 33843b160a2040b3ec4d3452678450afa11704c473Alkis Evlogimenos#include "Support/STLExtras.h" 345f37502bfbadfa65de087627bd67fd58bb03725cAlkis Evlogimenos#include "VirtRegMap.h" 354d46e1e521c0df1990ea50f8146d22bd77ea71a6Alkis Evlogimenos#include <cmath> 36ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos#include <iostream> 37ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos 38ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenosusing namespace llvm; 39ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos 40ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenosnamespace { 41ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos RegisterAnalysis<LiveIntervals> X("liveintervals", 42ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos "Live Interval Analysis"); 43ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos 44007726ca6f64ea74c20ddb90093ee8d6801733afAlkis Evlogimenos Statistic<> numIntervals 45007726ca6f64ea74c20ddb90093ee8d6801733afAlkis Evlogimenos ("liveintervals", "Number of original intervals"); 46007726ca6f64ea74c20ddb90093ee8d6801733afAlkis Evlogimenos 47007726ca6f64ea74c20ddb90093ee8d6801733afAlkis Evlogimenos Statistic<> numIntervalsAfter 48007726ca6f64ea74c20ddb90093ee8d6801733afAlkis Evlogimenos ("liveintervals", "Number of intervals after coalescing"); 49007726ca6f64ea74c20ddb90093ee8d6801733afAlkis Evlogimenos 50007726ca6f64ea74c20ddb90093ee8d6801733afAlkis Evlogimenos Statistic<> numJoins 51007726ca6f64ea74c20ddb90093ee8d6801733afAlkis Evlogimenos ("liveintervals", "Number of interval joins performed"); 52007726ca6f64ea74c20ddb90093ee8d6801733afAlkis Evlogimenos 53007726ca6f64ea74c20ddb90093ee8d6801733afAlkis Evlogimenos Statistic<> numPeep 54007726ca6f64ea74c20ddb90093ee8d6801733afAlkis Evlogimenos ("liveintervals", "Number of identity moves eliminated after coalescing"); 55007726ca6f64ea74c20ddb90093ee8d6801733afAlkis Evlogimenos 56007726ca6f64ea74c20ddb90093ee8d6801733afAlkis Evlogimenos Statistic<> numFolded 57d6f6d1a80daf89ad0bddc4b8335e1b2ae1ec3410Alkis Evlogimenos ("liveintervals", "Number of loads/stores folded into instructions"); 58007726ca6f64ea74c20ddb90093ee8d6801733afAlkis Evlogimenos 59e88280a4224730dcf8076e0d9a20973c5761fd06Alkis Evlogimenos cl::opt<bool> 60e1b9536d546b78f8cffc7efbb2ff75d7e15f9749Chris Lattner EnableJoining("join-liveintervals", 61e1b9536d546b78f8cffc7efbb2ff75d7e15f9749Chris Lattner cl::desc("Join compatible live intervals"), 62e1b9536d546b78f8cffc7efbb2ff75d7e15f9749Chris Lattner cl::init(true)); 63e1b9536d546b78f8cffc7efbb2ff75d7e15f9749Chris Lattner cl::opt<bool> 64e1b9536d546b78f8cffc7efbb2ff75d7e15f9749Chris Lattner EnableVirtVirtJoining("join-liveintervals-virtvirtjoining", 65e1b9536d546b78f8cffc7efbb2ff75d7e15f9749Chris Lattner cl::desc("Join live intervals for virtreg pairs (buggy)"), 66e1b9536d546b78f8cffc7efbb2ff75d7e15f9749Chris Lattner cl::init(false)); 67ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos}; 68ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos 69ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenosvoid LiveIntervals::getAnalysisUsage(AnalysisUsage &AU) const 70ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos{ 71f6f91bf6680668990ff3804b14cf05beedc56ec4Alkis Evlogimenos AU.addPreserved<LiveVariables>(); 72ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos AU.addRequired<LiveVariables>(); 73f6f91bf6680668990ff3804b14cf05beedc56ec4Alkis Evlogimenos AU.addPreservedID(PHIEliminationID); 74ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos AU.addRequiredID(PHIEliminationID); 754c080863de86448d905beab27686da823b6d44c1Alkis Evlogimenos AU.addRequiredID(TwoAddressInstructionPassID); 766b4edbaaf9021e0434f0ce0c3724eb43ed41b770Alkis Evlogimenos AU.addRequired<LoopInfo>(); 77ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos MachineFunctionPass::getAnalysisUsage(AU); 78ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos} 79ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos 8008cec00588ec1a8fa85b208555f006d7396ae7a4Alkis Evlogimenosvoid LiveIntervals::releaseMemory() 8108cec00588ec1a8fa85b208555f006d7396ae7a4Alkis Evlogimenos{ 8208cec00588ec1a8fa85b208555f006d7396ae7a4Alkis Evlogimenos mbbi2mbbMap_.clear(); 8308cec00588ec1a8fa85b208555f006d7396ae7a4Alkis Evlogimenos mi2iMap_.clear(); 84843b160a2040b3ec4d3452678450afa11704c473Alkis Evlogimenos i2miMap_.clear(); 8508cec00588ec1a8fa85b208555f006d7396ae7a4Alkis Evlogimenos r2iMap_.clear(); 8608cec00588ec1a8fa85b208555f006d7396ae7a4Alkis Evlogimenos r2rMap_.clear(); 8708cec00588ec1a8fa85b208555f006d7396ae7a4Alkis Evlogimenos intervals_.clear(); 8808cec00588ec1a8fa85b208555f006d7396ae7a4Alkis Evlogimenos} 8908cec00588ec1a8fa85b208555f006d7396ae7a4Alkis Evlogimenos 9008cec00588ec1a8fa85b208555f006d7396ae7a4Alkis Evlogimenos 91ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos/// runOnMachineFunction - Register allocate the whole function 92ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos/// 93ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenosbool LiveIntervals::runOnMachineFunction(MachineFunction &fn) { 94ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos mf_ = &fn; 95ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos tm_ = &fn.getTarget(); 96ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos mri_ = tm_->getRegisterInfo(); 97ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos lv_ = &getAnalysis<LiveVariables>(); 98ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos 99ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos // number MachineInstrs 100ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos unsigned miIndex = 0; 101ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos for (MachineFunction::iterator mbb = mf_->begin(), mbbEnd = mf_->end(); 102ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos mbb != mbbEnd; ++mbb) { 1038ba9771549bcff6109ad45ff3944a1b6c3c54b46Chris Lattner unsigned mbbIdx = mbb->getNumber(); 104015959ee38e4fd4a920f6b0065c50e524762f580Chris Lattner bool inserted = mbbi2mbbMap_.insert(std::make_pair(mbbIdx, 105015959ee38e4fd4a920f6b0065c50e524762f580Chris Lattner mbb)).second; 106ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos assert(inserted && "multiple index -> MachineBasicBlock"); 107ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos 108ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos for (MachineBasicBlock::iterator mi = mbb->begin(), miEnd = mbb->end(); 109ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos mi != miEnd; ++mi) { 110c0b9dc5be79f009d260edb5cd5e1d8346587aaa2Alkis Evlogimenos inserted = mi2iMap_.insert(std::make_pair(mi, miIndex)).second; 111ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos assert(inserted && "multiple MachineInstr -> index mappings"); 112843b160a2040b3ec4d3452678450afa11704c473Alkis Evlogimenos i2miMap_.push_back(mi); 11339a0d5c1123cfe4ddf826690b6744cc7248e3149Alkis Evlogimenos miIndex += InstrSlots::NUM; 114ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos } 115ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos } 116ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos 117ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos computeIntervals(); 118ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos 119843b160a2040b3ec4d3452678450afa11704c473Alkis Evlogimenos numIntervals += intervals_.size(); 120843b160a2040b3ec4d3452678450afa11704c473Alkis Evlogimenos 121843b160a2040b3ec4d3452678450afa11704c473Alkis Evlogimenos // join intervals if requested 122e1b9536d546b78f8cffc7efbb2ff75d7e15f9749Chris Lattner if (EnableJoining) joinIntervals(); 123843b160a2040b3ec4d3452678450afa11704c473Alkis Evlogimenos 124007726ca6f64ea74c20ddb90093ee8d6801733afAlkis Evlogimenos numIntervalsAfter += intervals_.size(); 125007726ca6f64ea74c20ddb90093ee8d6801733afAlkis Evlogimenos 126843b160a2040b3ec4d3452678450afa11704c473Alkis Evlogimenos // perform a final pass over the instructions and compute spill 127843b160a2040b3ec4d3452678450afa11704c473Alkis Evlogimenos // weights, coalesce virtual registers and remove identity moves 1287a40eaaceec0af76d5b97610f3d4e7a47a19d245Alkis Evlogimenos const LoopInfo& loopInfo = getAnalysis<LoopInfo>(); 1299bcdcd17c7219dbc68de2f11ca2de86471c8c390Chris Lattner const TargetInstrInfo& tii = *tm_->getInstrInfo(); 1307a40eaaceec0af76d5b97610f3d4e7a47a19d245Alkis Evlogimenos 131843b160a2040b3ec4d3452678450afa11704c473Alkis Evlogimenos for (MachineFunction::iterator mbbi = mf_->begin(), mbbe = mf_->end(); 132843b160a2040b3ec4d3452678450afa11704c473Alkis Evlogimenos mbbi != mbbe; ++mbbi) { 133843b160a2040b3ec4d3452678450afa11704c473Alkis Evlogimenos MachineBasicBlock* mbb = mbbi; 1347a40eaaceec0af76d5b97610f3d4e7a47a19d245Alkis Evlogimenos unsigned loopDepth = loopInfo.getLoopDepth(mbb->getBasicBlock()); 1357a40eaaceec0af76d5b97610f3d4e7a47a19d245Alkis Evlogimenos 136843b160a2040b3ec4d3452678450afa11704c473Alkis Evlogimenos for (MachineBasicBlock::iterator mii = mbb->begin(), mie = mbb->end(); 137843b160a2040b3ec4d3452678450afa11704c473Alkis Evlogimenos mii != mie; ) { 13843b61f724ef68810c63fc54c99e88f9b278f05c0Alkis Evlogimenos // if the move will be an identity move delete it 139843b160a2040b3ec4d3452678450afa11704c473Alkis Evlogimenos unsigned srcReg, dstReg; 14043b61f724ef68810c63fc54c99e88f9b278f05c0Alkis Evlogimenos if (tii.isMoveInstr(*mii, srcReg, dstReg) && 14143b61f724ef68810c63fc54c99e88f9b278f05c0Alkis Evlogimenos rep(srcReg) == rep(dstReg)) { 1429a8b490735d216435862a3d52e669357f165550fAlkis Evlogimenos // remove from def list 143418da55c89c9ba355b51dceecb16f4388ef35119Chris Lattner LiveInterval& interval = getOrCreateInterval(rep(dstReg)); 144843b160a2040b3ec4d3452678450afa11704c473Alkis Evlogimenos // remove index -> MachineInstr and 145843b160a2040b3ec4d3452678450afa11704c473Alkis Evlogimenos // MachineInstr -> index mappings 146843b160a2040b3ec4d3452678450afa11704c473Alkis Evlogimenos Mi2IndexMap::iterator mi2i = mi2iMap_.find(mii); 147843b160a2040b3ec4d3452678450afa11704c473Alkis Evlogimenos if (mi2i != mi2iMap_.end()) { 14839a0d5c1123cfe4ddf826690b6744cc7248e3149Alkis Evlogimenos i2miMap_[mi2i->second/InstrSlots::NUM] = 0; 149843b160a2040b3ec4d3452678450afa11704c473Alkis Evlogimenos mi2iMap_.erase(mi2i); 15008cec00588ec1a8fa85b208555f006d7396ae7a4Alkis Evlogimenos } 151843b160a2040b3ec4d3452678450afa11704c473Alkis Evlogimenos mii = mbbi->erase(mii); 152843b160a2040b3ec4d3452678450afa11704c473Alkis Evlogimenos ++numPeep; 1537a40eaaceec0af76d5b97610f3d4e7a47a19d245Alkis Evlogimenos } 15443b61f724ef68810c63fc54c99e88f9b278f05c0Alkis Evlogimenos else { 15543b61f724ef68810c63fc54c99e88f9b278f05c0Alkis Evlogimenos for (unsigned i = 0; i < mii->getNumOperands(); ++i) { 15643b61f724ef68810c63fc54c99e88f9b278f05c0Alkis Evlogimenos const MachineOperand& mop = mii->getOperand(i); 15743b61f724ef68810c63fc54c99e88f9b278f05c0Alkis Evlogimenos if (mop.isRegister() && mop.getReg() && 15843b61f724ef68810c63fc54c99e88f9b278f05c0Alkis Evlogimenos MRegisterInfo::isVirtualRegister(mop.getReg())) { 15943b61f724ef68810c63fc54c99e88f9b278f05c0Alkis Evlogimenos // replace register with representative register 16043b61f724ef68810c63fc54c99e88f9b278f05c0Alkis Evlogimenos unsigned reg = rep(mop.getReg()); 16143b61f724ef68810c63fc54c99e88f9b278f05c0Alkis Evlogimenos mii->SetMachineOperandReg(i, reg); 16243b61f724ef68810c63fc54c99e88f9b278f05c0Alkis Evlogimenos 16343b61f724ef68810c63fc54c99e88f9b278f05c0Alkis Evlogimenos Reg2IntervalMap::iterator r2iit = r2iMap_.find(reg); 16443b61f724ef68810c63fc54c99e88f9b278f05c0Alkis Evlogimenos assert(r2iit != r2iMap_.end()); 16543b61f724ef68810c63fc54c99e88f9b278f05c0Alkis Evlogimenos r2iit->second->weight += 16643b61f724ef68810c63fc54c99e88f9b278f05c0Alkis Evlogimenos (mop.isUse() + mop.isDef()) * pow(10.0F, loopDepth); 16743b61f724ef68810c63fc54c99e88f9b278f05c0Alkis Evlogimenos } 16843b61f724ef68810c63fc54c99e88f9b278f05c0Alkis Evlogimenos } 169843b160a2040b3ec4d3452678450afa11704c473Alkis Evlogimenos ++mii; 17043b61f724ef68810c63fc54c99e88f9b278f05c0Alkis Evlogimenos } 1717a40eaaceec0af76d5b97610f3d4e7a47a19d245Alkis Evlogimenos } 1727a40eaaceec0af76d5b97610f3d4e7a47a19d245Alkis Evlogimenos } 1737a40eaaceec0af76d5b97610f3d4e7a47a19d245Alkis Evlogimenos 1746924063bf2fdcc455bcb87807ab452ab7fc69773Alkis Evlogimenos intervals_.sort(); 17539a0d5c1123cfe4ddf826690b6744cc7248e3149Alkis Evlogimenos DEBUG(std::cerr << "********** INTERVALS **********\n"); 17601e74a2aab64c5901a62d9ba9e1c263759929390Alkis Evlogimenos DEBUG(std::copy(intervals_.begin(), intervals_.end(), 177418da55c89c9ba355b51dceecb16f4388ef35119Chris Lattner std::ostream_iterator<LiveInterval>(std::cerr, "\n"))); 17839a0d5c1123cfe4ddf826690b6744cc7248e3149Alkis Evlogimenos DEBUG(std::cerr << "********** MACHINEINSTRS **********\n"); 179843b160a2040b3ec4d3452678450afa11704c473Alkis Evlogimenos DEBUG( 1800f338a1e8cd8167d22e2d011e0bec7eaadc6154aAlkis Evlogimenos for (MachineFunction::iterator mbbi = mf_->begin(), mbbe = mf_->end(); 1810f338a1e8cd8167d22e2d011e0bec7eaadc6154aAlkis Evlogimenos mbbi != mbbe; ++mbbi) { 182015959ee38e4fd4a920f6b0065c50e524762f580Chris Lattner std::cerr << ((Value*)mbbi->getBasicBlock())->getName() << ":\n"; 1830f338a1e8cd8167d22e2d011e0bec7eaadc6154aAlkis Evlogimenos for (MachineBasicBlock::iterator mii = mbbi->begin(), 1840f338a1e8cd8167d22e2d011e0bec7eaadc6154aAlkis Evlogimenos mie = mbbi->end(); mii != mie; ++mii) { 1850f338a1e8cd8167d22e2d011e0bec7eaadc6154aAlkis Evlogimenos std::cerr << getInstructionIndex(mii) << '\t'; 186b140762a45d21aaed054f15adaff0fc2274d939dTanya Lattner mii->print(std::cerr, tm_); 187843b160a2040b3ec4d3452678450afa11704c473Alkis Evlogimenos } 188843b160a2040b3ec4d3452678450afa11704c473Alkis Evlogimenos }); 189843b160a2040b3ec4d3452678450afa11704c473Alkis Evlogimenos 190ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos return true; 191ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos} 192ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos 193418da55c89c9ba355b51dceecb16f4388ef35119Chris Lattnerstd::vector<LiveInterval*> LiveIntervals::addIntervalsForSpills( 194418da55c89c9ba355b51dceecb16f4388ef35119Chris Lattner const LiveInterval& li, 195418da55c89c9ba355b51dceecb16f4388ef35119Chris Lattner VirtRegMap& vrm, 196418da55c89c9ba355b51dceecb16f4388ef35119Chris Lattner int slot) 197843b160a2040b3ec4d3452678450afa11704c473Alkis Evlogimenos{ 198418da55c89c9ba355b51dceecb16f4388ef35119Chris Lattner std::vector<LiveInterval*> added; 19926f5a69e52b64e035d26c135979a39b39fd6ba3eAlkis Evlogimenos 200a19eedeb7aafc418ef2f017b8215ceafa7f1a76cChris Lattner assert(li.weight != HUGE_VAL && 201843b160a2040b3ec4d3452678450afa11704c473Alkis Evlogimenos "attempt to spill already spilled interval!"); 202843b160a2040b3ec4d3452678450afa11704c473Alkis Evlogimenos 20326f5a69e52b64e035d26c135979a39b39fd6ba3eAlkis Evlogimenos DEBUG(std::cerr << "\t\t\t\tadding intervals for spills for interval: " 20426f5a69e52b64e035d26c135979a39b39fd6ba3eAlkis Evlogimenos << li << '\n'); 20526f5a69e52b64e035d26c135979a39b39fd6ba3eAlkis Evlogimenos 20626f5a69e52b64e035d26c135979a39b39fd6ba3eAlkis Evlogimenos const TargetRegisterClass* rc = mf_->getSSARegMap()->getRegClass(li.reg); 20739a0d5c1123cfe4ddf826690b6744cc7248e3149Alkis Evlogimenos 208418da55c89c9ba355b51dceecb16f4388ef35119Chris Lattner for (LiveInterval::Ranges::const_iterator 20926f5a69e52b64e035d26c135979a39b39fd6ba3eAlkis Evlogimenos i = li.ranges.begin(), e = li.ranges.end(); i != e; ++i) { 21039a0d5c1123cfe4ddf826690b6744cc7248e3149Alkis Evlogimenos unsigned index = getBaseIndex(i->first); 21139a0d5c1123cfe4ddf826690b6744cc7248e3149Alkis Evlogimenos unsigned end = getBaseIndex(i->second-1) + InstrSlots::NUM; 21239a0d5c1123cfe4ddf826690b6744cc7248e3149Alkis Evlogimenos for (; index < end; index += InstrSlots::NUM) { 213843b160a2040b3ec4d3452678450afa11704c473Alkis Evlogimenos // skip deleted instructions 21439a0d5c1123cfe4ddf826690b6744cc7248e3149Alkis Evlogimenos while (!getInstructionFromIndex(index)) index += InstrSlots::NUM; 21539a0d5c1123cfe4ddf826690b6744cc7248e3149Alkis Evlogimenos MachineBasicBlock::iterator mi = getInstructionFromIndex(index); 21639a0d5c1123cfe4ddf826690b6744cc7248e3149Alkis Evlogimenos 2175f37502bfbadfa65de087627bd67fd58bb03725cAlkis Evlogimenos for_operand: 218843b160a2040b3ec4d3452678450afa11704c473Alkis Evlogimenos for (unsigned i = 0; i < mi->getNumOperands(); ++i) { 219843b160a2040b3ec4d3452678450afa11704c473Alkis Evlogimenos MachineOperand& mop = mi->getOperand(i); 22039a0d5c1123cfe4ddf826690b6744cc7248e3149Alkis Evlogimenos if (mop.isRegister() && mop.getReg() == li.reg) { 22139354c99a158685d8bc91b0836c283e936a29cb2Alkis Evlogimenos if (MachineInstr* fmi = 22239354c99a158685d8bc91b0836c283e936a29cb2Alkis Evlogimenos mri_->foldMemoryOperand(mi, i, slot)) { 22339354c99a158685d8bc91b0836c283e936a29cb2Alkis Evlogimenos lv_->instructionChanged(mi, fmi); 22439354c99a158685d8bc91b0836c283e936a29cb2Alkis Evlogimenos vrm.virtFolded(li.reg, mi, fmi); 22539354c99a158685d8bc91b0836c283e936a29cb2Alkis Evlogimenos mi2iMap_.erase(mi); 22639354c99a158685d8bc91b0836c283e936a29cb2Alkis Evlogimenos i2miMap_[index/InstrSlots::NUM] = fmi; 22739354c99a158685d8bc91b0836c283e936a29cb2Alkis Evlogimenos mi2iMap_[fmi] = index; 22839354c99a158685d8bc91b0836c283e936a29cb2Alkis Evlogimenos MachineBasicBlock& mbb = *mi->getParent(); 22939354c99a158685d8bc91b0836c283e936a29cb2Alkis Evlogimenos mi = mbb.insert(mbb.erase(mi), fmi); 2305f37502bfbadfa65de087627bd67fd58bb03725cAlkis Evlogimenos ++numFolded; 2315f37502bfbadfa65de087627bd67fd58bb03725cAlkis Evlogimenos goto for_operand; 2325f37502bfbadfa65de087627bd67fd58bb03725cAlkis Evlogimenos } 2335f37502bfbadfa65de087627bd67fd58bb03725cAlkis Evlogimenos else { 2345f37502bfbadfa65de087627bd67fd58bb03725cAlkis Evlogimenos // This is tricky. We need to add information in 2355f37502bfbadfa65de087627bd67fd58bb03725cAlkis Evlogimenos // the interval about the spill code so we have to 2365f37502bfbadfa65de087627bd67fd58bb03725cAlkis Evlogimenos // use our extra load/store slots. 2375f37502bfbadfa65de087627bd67fd58bb03725cAlkis Evlogimenos // 2385f37502bfbadfa65de087627bd67fd58bb03725cAlkis Evlogimenos // If we have a use we are going to have a load so 2395f37502bfbadfa65de087627bd67fd58bb03725cAlkis Evlogimenos // we start the interval from the load slot 2405f37502bfbadfa65de087627bd67fd58bb03725cAlkis Evlogimenos // onwards. Otherwise we start from the def slot. 2415f37502bfbadfa65de087627bd67fd58bb03725cAlkis Evlogimenos unsigned start = (mop.isUse() ? 2425f37502bfbadfa65de087627bd67fd58bb03725cAlkis Evlogimenos getLoadIndex(index) : 2435f37502bfbadfa65de087627bd67fd58bb03725cAlkis Evlogimenos getDefIndex(index)); 2445f37502bfbadfa65de087627bd67fd58bb03725cAlkis Evlogimenos // If we have a def we are going to have a store 2455f37502bfbadfa65de087627bd67fd58bb03725cAlkis Evlogimenos // right after it so we end the interval after the 2465f37502bfbadfa65de087627bd67fd58bb03725cAlkis Evlogimenos // use of the next instruction. Otherwise we end 2475f37502bfbadfa65de087627bd67fd58bb03725cAlkis Evlogimenos // after the use of this instruction. 2485f37502bfbadfa65de087627bd67fd58bb03725cAlkis Evlogimenos unsigned end = 1 + (mop.isDef() ? 2495f37502bfbadfa65de087627bd67fd58bb03725cAlkis Evlogimenos getUseIndex(index+InstrSlots::NUM) : 2505f37502bfbadfa65de087627bd67fd58bb03725cAlkis Evlogimenos getUseIndex(index)); 25126f5a69e52b64e035d26c135979a39b39fd6ba3eAlkis Evlogimenos 25226f5a69e52b64e035d26c135979a39b39fd6ba3eAlkis Evlogimenos // create a new register for this spill 25326f5a69e52b64e035d26c135979a39b39fd6ba3eAlkis Evlogimenos unsigned nReg = 25426f5a69e52b64e035d26c135979a39b39fd6ba3eAlkis Evlogimenos mf_->getSSARegMap()->createVirtualRegister(rc); 25526f5a69e52b64e035d26c135979a39b39fd6ba3eAlkis Evlogimenos mi->SetMachineOperandReg(i, nReg); 25626f5a69e52b64e035d26c135979a39b39fd6ba3eAlkis Evlogimenos vrm.grow(); 25726f5a69e52b64e035d26c135979a39b39fd6ba3eAlkis Evlogimenos vrm.assignVirt2StackSlot(nReg, slot); 258418da55c89c9ba355b51dceecb16f4388ef35119Chris Lattner LiveInterval& nI = getOrCreateInterval(nReg); 25926f5a69e52b64e035d26c135979a39b39fd6ba3eAlkis Evlogimenos assert(nI.empty()); 26026f5a69e52b64e035d26c135979a39b39fd6ba3eAlkis Evlogimenos // the spill weight is now infinity as it 26126f5a69e52b64e035d26c135979a39b39fd6ba3eAlkis Evlogimenos // cannot be spilled again 26226f5a69e52b64e035d26c135979a39b39fd6ba3eAlkis Evlogimenos nI.weight = HUGE_VAL; 26326f5a69e52b64e035d26c135979a39b39fd6ba3eAlkis Evlogimenos nI.addRange(start, end); 26426f5a69e52b64e035d26c135979a39b39fd6ba3eAlkis Evlogimenos added.push_back(&nI); 26526f5a69e52b64e035d26c135979a39b39fd6ba3eAlkis Evlogimenos // update live variables 26626f5a69e52b64e035d26c135979a39b39fd6ba3eAlkis Evlogimenos lv_->addVirtualRegisterKilled(nReg, mi->getParent(),mi); 26726f5a69e52b64e035d26c135979a39b39fd6ba3eAlkis Evlogimenos DEBUG(std::cerr << "\t\t\t\tadded new interval: " 26826f5a69e52b64e035d26c135979a39b39fd6ba3eAlkis Evlogimenos << nI << '\n'); 2695f37502bfbadfa65de087627bd67fd58bb03725cAlkis Evlogimenos } 270843b160a2040b3ec4d3452678450afa11704c473Alkis Evlogimenos } 271843b160a2040b3ec4d3452678450afa11704c473Alkis Evlogimenos } 272843b160a2040b3ec4d3452678450afa11704c473Alkis Evlogimenos } 273843b160a2040b3ec4d3452678450afa11704c473Alkis Evlogimenos } 27426f5a69e52b64e035d26c135979a39b39fd6ba3eAlkis Evlogimenos 27526f5a69e52b64e035d26c135979a39b39fd6ba3eAlkis Evlogimenos return added; 276843b160a2040b3ec4d3452678450afa11704c473Alkis Evlogimenos} 277843b160a2040b3ec4d3452678450afa11704c473Alkis Evlogimenos 278ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenosvoid LiveIntervals::printRegName(unsigned reg) const 279ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos{ 2804f67b8664889d9e93b452a9a5f099d41d1bd235aAlkis Evlogimenos if (MRegisterInfo::isPhysicalRegister(reg)) 281ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos std::cerr << mri_->getName(reg); 282ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos else 28339a0d5c1123cfe4ddf826690b6744cc7248e3149Alkis Evlogimenos std::cerr << "%reg" << reg; 284ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos} 285ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos 286ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenosvoid LiveIntervals::handleVirtualRegisterDef(MachineBasicBlock* mbb, 287ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos MachineBasicBlock::iterator mi, 288418da55c89c9ba355b51dceecb16f4388ef35119Chris Lattner LiveInterval& interval) 289ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos{ 2909a8b490735d216435862a3d52e669357f165550fAlkis Evlogimenos DEBUG(std::cerr << "\t\tregister: "; printRegName(interval.reg)); 2919a8b490735d216435862a3d52e669357f165550fAlkis Evlogimenos LiveVariables::VarInfo& vi = lv_->getVarInfo(interval.reg); 292ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos 293607baea7d2f3155a4ca391a1d9fb1f4b0178ebb2Alkis Evlogimenos // Iterate over all of the blocks that the variable is completely 294607baea7d2f3155a4ca391a1d9fb1f4b0178ebb2Alkis Evlogimenos // live in, adding [insrtIndex(begin), instrIndex(end)+4) to the 295607baea7d2f3155a4ca391a1d9fb1f4b0178ebb2Alkis Evlogimenos // live interval. Obviously we only need to do this once. 2969a8b490735d216435862a3d52e669357f165550fAlkis Evlogimenos if (interval.empty()) { 297ad48cd6327df13ad4b8530733bbf115224bf9562Alkis Evlogimenos for (unsigned i = 0, e = vi.AliveBlocks.size(); i != e; ++i) { 298ad48cd6327df13ad4b8530733bbf115224bf9562Alkis Evlogimenos if (vi.AliveBlocks[i]) { 2998490f9c92e354fd9cd242bae89b24e6c59e5c794Chris Lattner MachineBasicBlock* mbb = mf_->getBlockNumbered(i); 300ad48cd6327df13ad4b8530733bbf115224bf9562Alkis Evlogimenos if (!mbb->empty()) { 3019a8b490735d216435862a3d52e669357f165550fAlkis Evlogimenos interval.addRange( 30239a0d5c1123cfe4ddf826690b6744cc7248e3149Alkis Evlogimenos getInstructionIndex(&mbb->front()), 30339a0d5c1123cfe4ddf826690b6744cc7248e3149Alkis Evlogimenos getInstructionIndex(&mbb->back()) + InstrSlots::NUM); 304ad48cd6327df13ad4b8530733bbf115224bf9562Alkis Evlogimenos } 30552220f61bba91ab787d4cc0aee47df4e2ca55c04Alkis Evlogimenos } 306ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos } 307dd2cc65f34f9b7bfda1cd0c42becedfc361d46f8Alkis Evlogimenos } 308ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos 30939a0d5c1123cfe4ddf826690b6744cc7248e3149Alkis Evlogimenos unsigned baseIndex = getInstructionIndex(mi); 3100b8cb2bc47a6bee59c8c3f46d4cc047badf7f8acAlkis Evlogimenos 311dd2cc65f34f9b7bfda1cd0c42becedfc361d46f8Alkis Evlogimenos bool killedInDefiningBasicBlock = false; 312dd2cc65f34f9b7bfda1cd0c42becedfc361d46f8Alkis Evlogimenos for (int i = 0, e = vi.Kills.size(); i != e; ++i) { 313dd2cc65f34f9b7bfda1cd0c42becedfc361d46f8Alkis Evlogimenos MachineBasicBlock* killerBlock = vi.Kills[i].first; 314dd2cc65f34f9b7bfda1cd0c42becedfc361d46f8Alkis Evlogimenos MachineInstr* killerInstr = vi.Kills[i].second; 315dd2cc65f34f9b7bfda1cd0c42becedfc361d46f8Alkis Evlogimenos unsigned start = (mbb == killerBlock ? 31639a0d5c1123cfe4ddf826690b6744cc7248e3149Alkis Evlogimenos getDefIndex(baseIndex) : 317c0b9dc5be79f009d260edb5cd5e1d8346587aaa2Alkis Evlogimenos getInstructionIndex(&killerBlock->front())); 318c0b9dc5be79f009d260edb5cd5e1d8346587aaa2Alkis Evlogimenos unsigned end = (killerInstr == mi ? 31939a0d5c1123cfe4ddf826690b6744cc7248e3149Alkis Evlogimenos // dead 32039a0d5c1123cfe4ddf826690b6744cc7248e3149Alkis Evlogimenos start + 1 : 32139a0d5c1123cfe4ddf826690b6744cc7248e3149Alkis Evlogimenos // killed 32239a0d5c1123cfe4ddf826690b6744cc7248e3149Alkis Evlogimenos getUseIndex(getInstructionIndex(killerInstr))+1); 32308cec00588ec1a8fa85b208555f006d7396ae7a4Alkis Evlogimenos // we do not want to add invalid ranges. these can happen when 32408cec00588ec1a8fa85b208555f006d7396ae7a4Alkis Evlogimenos // a variable has its latest use and is redefined later on in 32508cec00588ec1a8fa85b208555f006d7396ae7a4Alkis Evlogimenos // the same basic block (common with variables introduced by 32608cec00588ec1a8fa85b208555f006d7396ae7a4Alkis Evlogimenos // PHI elimination) 32743f692f90f6b27304570e1b1807542dff4b8e847Alkis Evlogimenos if (start < end) { 32843f692f90f6b27304570e1b1807542dff4b8e847Alkis Evlogimenos killedInDefiningBasicBlock |= mbb == killerBlock; 3299a8b490735d216435862a3d52e669357f165550fAlkis Evlogimenos interval.addRange(start, end); 33043f692f90f6b27304570e1b1807542dff4b8e847Alkis Evlogimenos } 331dd2cc65f34f9b7bfda1cd0c42becedfc361d46f8Alkis Evlogimenos } 332ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos 333dd2cc65f34f9b7bfda1cd0c42becedfc361d46f8Alkis Evlogimenos if (!killedInDefiningBasicBlock) { 33439a0d5c1123cfe4ddf826690b6744cc7248e3149Alkis Evlogimenos unsigned end = getInstructionIndex(&mbb->back()) + InstrSlots::NUM; 3359a8b490735d216435862a3d52e669357f165550fAlkis Evlogimenos interval.addRange(getDefIndex(baseIndex), end); 336ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos } 33739a0d5c1123cfe4ddf826690b6744cc7248e3149Alkis Evlogimenos DEBUG(std::cerr << '\n'); 338ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos} 339ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos 340ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenosvoid LiveIntervals::handlePhysicalRegisterDef(MachineBasicBlock* mbb, 341ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos MachineBasicBlock::iterator mi, 342418da55c89c9ba355b51dceecb16f4388ef35119Chris Lattner LiveInterval& interval) 343ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos{ 344607baea7d2f3155a4ca391a1d9fb1f4b0178ebb2Alkis Evlogimenos // A physical register cannot be live across basic block, so its 345607baea7d2f3155a4ca391a1d9fb1f4b0178ebb2Alkis Evlogimenos // lifetime must end somewhere in its defining basic block. 3469a8b490735d216435862a3d52e669357f165550fAlkis Evlogimenos DEBUG(std::cerr << "\t\tregister: "; printRegName(interval.reg)); 34739a0d5c1123cfe4ddf826690b6744cc7248e3149Alkis Evlogimenos typedef LiveVariables::killed_iterator KillIter; 348ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos 34902ba13c9897ae2b19f9201e57460d7ee2b753a0bAlkis Evlogimenos MachineBasicBlock::iterator e = mbb->end(); 35039a0d5c1123cfe4ddf826690b6744cc7248e3149Alkis Evlogimenos unsigned baseIndex = getInstructionIndex(mi); 35139a0d5c1123cfe4ddf826690b6744cc7248e3149Alkis Evlogimenos unsigned start = getDefIndex(baseIndex); 35239a0d5c1123cfe4ddf826690b6744cc7248e3149Alkis Evlogimenos unsigned end = start; 3534d46e1e521c0df1990ea50f8146d22bd77ea71a6Alkis Evlogimenos 354607baea7d2f3155a4ca391a1d9fb1f4b0178ebb2Alkis Evlogimenos // If it is not used after definition, it is considered dead at 355607baea7d2f3155a4ca391a1d9fb1f4b0178ebb2Alkis Evlogimenos // the instruction defining it. Hence its interval is: 356607baea7d2f3155a4ca391a1d9fb1f4b0178ebb2Alkis Evlogimenos // [defSlot(def), defSlot(def)+1) 357c0b9dc5be79f009d260edb5cd5e1d8346587aaa2Alkis Evlogimenos for (KillIter ki = lv_->dead_begin(mi), ke = lv_->dead_end(mi); 358af25473d5e99e0c0968746e12d8827e4b712bd31Alkis Evlogimenos ki != ke; ++ki) { 3599a8b490735d216435862a3d52e669357f165550fAlkis Evlogimenos if (interval.reg == ki->second) { 36039a0d5c1123cfe4ddf826690b6744cc7248e3149Alkis Evlogimenos DEBUG(std::cerr << " dead"); 36139a0d5c1123cfe4ddf826690b6744cc7248e3149Alkis Evlogimenos end = getDefIndex(start) + 1; 362af25473d5e99e0c0968746e12d8827e4b712bd31Alkis Evlogimenos goto exit; 363af25473d5e99e0c0968746e12d8827e4b712bd31Alkis Evlogimenos } 364af25473d5e99e0c0968746e12d8827e4b712bd31Alkis Evlogimenos } 365ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos 366607baea7d2f3155a4ca391a1d9fb1f4b0178ebb2Alkis Evlogimenos // If it is not dead on definition, it must be killed by a 367607baea7d2f3155a4ca391a1d9fb1f4b0178ebb2Alkis Evlogimenos // subsequent instruction. Hence its interval is: 36880b27ced2d5e6340bb62d75a8c6f23198e69a1afAlkis Evlogimenos // [defSlot(def), useSlot(kill)+1) 369230b4fb8a0d7b2b0e0d533cf37b05a084d140a5cChris Lattner do { 370230b4fb8a0d7b2b0e0d533cf37b05a084d140a5cChris Lattner ++mi; 37139a0d5c1123cfe4ddf826690b6744cc7248e3149Alkis Evlogimenos baseIndex += InstrSlots::NUM; 372c0b9dc5be79f009d260edb5cd5e1d8346587aaa2Alkis Evlogimenos for (KillIter ki = lv_->killed_begin(mi), ke = lv_->killed_end(mi); 3734d46e1e521c0df1990ea50f8146d22bd77ea71a6Alkis Evlogimenos ki != ke; ++ki) { 3749a8b490735d216435862a3d52e669357f165550fAlkis Evlogimenos if (interval.reg == ki->second) { 37539a0d5c1123cfe4ddf826690b6744cc7248e3149Alkis Evlogimenos DEBUG(std::cerr << " killed"); 37639a0d5c1123cfe4ddf826690b6744cc7248e3149Alkis Evlogimenos end = getUseIndex(baseIndex) + 1; 3774d46e1e521c0df1990ea50f8146d22bd77ea71a6Alkis Evlogimenos goto exit; 378ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos } 3794d46e1e521c0df1990ea50f8146d22bd77ea71a6Alkis Evlogimenos } 380230b4fb8a0d7b2b0e0d533cf37b05a084d140a5cChris Lattner } while (mi != e); 38102ba13c9897ae2b19f9201e57460d7ee2b753a0bAlkis Evlogimenos 382ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenosexit: 383230b4fb8a0d7b2b0e0d533cf37b05a084d140a5cChris Lattner assert(start < end && "did not find end of interval?"); 3849a8b490735d216435862a3d52e669357f165550fAlkis Evlogimenos interval.addRange(start, end); 38539a0d5c1123cfe4ddf826690b6744cc7248e3149Alkis Evlogimenos DEBUG(std::cerr << '\n'); 386ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos} 387ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos 388ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenosvoid LiveIntervals::handleRegisterDef(MachineBasicBlock* mbb, 389ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos MachineBasicBlock::iterator mi, 390ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos unsigned reg) 391ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos{ 3924f67b8664889d9e93b452a9a5f099d41d1bd235aAlkis Evlogimenos if (MRegisterInfo::isPhysicalRegister(reg)) { 3931a119e24106810310825f44c7bfd232d3272e639Alkis Evlogimenos if (lv_->getAllocatablePhysicalRegisters()[reg]) { 3949a8b490735d216435862a3d52e669357f165550fAlkis Evlogimenos handlePhysicalRegisterDef(mbb, mi, getOrCreateInterval(reg)); 39519b6486d3891c8a02a301aa1b44348a420772fcfAlkis Evlogimenos for (const unsigned* as = mri_->getAliasSet(reg); *as; ++as) 3969a8b490735d216435862a3d52e669357f165550fAlkis Evlogimenos handlePhysicalRegisterDef(mbb, mi, getOrCreateInterval(*as)); 397ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos } 398ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos } 3999a8b490735d216435862a3d52e669357f165550fAlkis Evlogimenos else 4009a8b490735d216435862a3d52e669357f165550fAlkis Evlogimenos handleVirtualRegisterDef(mbb, mi, getOrCreateInterval(reg)); 401ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos} 402ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos 4034d46e1e521c0df1990ea50f8146d22bd77ea71a6Alkis Evlogimenosunsigned LiveIntervals::getInstructionIndex(MachineInstr* instr) const 4044d46e1e521c0df1990ea50f8146d22bd77ea71a6Alkis Evlogimenos{ 405843b160a2040b3ec4d3452678450afa11704c473Alkis Evlogimenos Mi2IndexMap::const_iterator it = mi2iMap_.find(instr); 40639a0d5c1123cfe4ddf826690b6744cc7248e3149Alkis Evlogimenos return (it == mi2iMap_.end() ? 40739a0d5c1123cfe4ddf826690b6744cc7248e3149Alkis Evlogimenos std::numeric_limits<unsigned>::max() : 40839a0d5c1123cfe4ddf826690b6744cc7248e3149Alkis Evlogimenos it->second); 409843b160a2040b3ec4d3452678450afa11704c473Alkis Evlogimenos} 410843b160a2040b3ec4d3452678450afa11704c473Alkis Evlogimenos 411843b160a2040b3ec4d3452678450afa11704c473Alkis EvlogimenosMachineInstr* LiveIntervals::getInstructionFromIndex(unsigned index) const 412843b160a2040b3ec4d3452678450afa11704c473Alkis Evlogimenos{ 41339a0d5c1123cfe4ddf826690b6744cc7248e3149Alkis Evlogimenos index /= InstrSlots::NUM; // convert index to vector index 414843b160a2040b3ec4d3452678450afa11704c473Alkis Evlogimenos assert(index < i2miMap_.size() && 415843b160a2040b3ec4d3452678450afa11704c473Alkis Evlogimenos "index does not correspond to an instruction"); 416843b160a2040b3ec4d3452678450afa11704c473Alkis Evlogimenos return i2miMap_[index]; 4174d46e1e521c0df1990ea50f8146d22bd77ea71a6Alkis Evlogimenos} 4184d46e1e521c0df1990ea50f8146d22bd77ea71a6Alkis Evlogimenos 419ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos/// computeIntervals - computes the live intervals for virtual 4204d46e1e521c0df1990ea50f8146d22bd77ea71a6Alkis Evlogimenos/// registers. for some ordering of the machine instructions [1,N] a 42108cec00588ec1a8fa85b208555f006d7396ae7a4Alkis Evlogimenos/// live interval is an interval [i, j) where 1 <= i <= j < N for 422ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos/// which a variable is live 423ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenosvoid LiveIntervals::computeIntervals() 424ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos{ 42539a0d5c1123cfe4ddf826690b6744cc7248e3149Alkis Evlogimenos DEBUG(std::cerr << "********** COMPUTING LIVE INTERVALS **********\n"); 42639a0d5c1123cfe4ddf826690b6744cc7248e3149Alkis Evlogimenos DEBUG(std::cerr << "********** Function: " 427015959ee38e4fd4a920f6b0065c50e524762f580Chris Lattner << ((Value*)mf_->getFunction())->getName() << '\n'); 428ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos 429ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos for (MbbIndex2MbbMap::iterator 430ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos it = mbbi2mbbMap_.begin(), itEnd = mbbi2mbbMap_.end(); 431ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos it != itEnd; ++it) { 432ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos MachineBasicBlock* mbb = it->second; 433015959ee38e4fd4a920f6b0065c50e524762f580Chris Lattner DEBUG(std::cerr << ((Value*)mbb->getBasicBlock())->getName() << ":\n"); 4346b4edbaaf9021e0434f0ce0c3724eb43ed41b770Alkis Evlogimenos 435ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos for (MachineBasicBlock::iterator mi = mbb->begin(), miEnd = mbb->end(); 436ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos mi != miEnd; ++mi) { 437ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos const TargetInstrDescriptor& tid = 4389bcdcd17c7219dbc68de2f11ca2de86471c8c390Chris Lattner tm_->getInstrInfo()->get(mi->getOpcode()); 43939a0d5c1123cfe4ddf826690b6744cc7248e3149Alkis Evlogimenos DEBUG(std::cerr << getInstructionIndex(mi) << "\t"; 440b140762a45d21aaed054f15adaff0fc2274d939dTanya Lattner mi->print(std::cerr, tm_)); 441ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos 442ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos // handle implicit defs 44319b6486d3891c8a02a301aa1b44348a420772fcfAlkis Evlogimenos for (const unsigned* id = tid.ImplicitDefs; *id; ++id) 44419b6486d3891c8a02a301aa1b44348a420772fcfAlkis Evlogimenos handleRegisterDef(mbb, mi, *id); 445ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos 446ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos // handle explicit defs 447c0b9dc5be79f009d260edb5cd5e1d8346587aaa2Alkis Evlogimenos for (int i = mi->getNumOperands() - 1; i >= 0; --i) { 448c0b9dc5be79f009d260edb5cd5e1d8346587aaa2Alkis Evlogimenos MachineOperand& mop = mi->getOperand(i); 44908cec00588ec1a8fa85b208555f006d7396ae7a4Alkis Evlogimenos // handle register defs - build intervals 45071e353ed3530a5da48c3dd3257c410f6c4ce2e3eAlkis Evlogimenos if (mop.isRegister() && mop.getReg() && mop.isDef()) 451be766c72464116a445a02b542a450c4274bab5d0Alkis Evlogimenos handleRegisterDef(mbb, mi, mop.getReg()); 452ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos } 453ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos } 454ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos } 455ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos} 456b27ef248f579b354aab434f63c417ab1103e47e2Alkis Evlogimenos 457e88280a4224730dcf8076e0d9a20973c5761fd06Alkis Evlogimenosunsigned LiveIntervals::rep(unsigned reg) 458169cfd01964fc03828a7f2cad5d710890fbb08d8Alkis Evlogimenos{ 459e88280a4224730dcf8076e0d9a20973c5761fd06Alkis Evlogimenos Reg2RegMap::iterator it = r2rMap_.find(reg); 460e88280a4224730dcf8076e0d9a20973c5761fd06Alkis Evlogimenos if (it != r2rMap_.end()) 461e88280a4224730dcf8076e0d9a20973c5761fd06Alkis Evlogimenos return it->second = rep(it->second); 462e88280a4224730dcf8076e0d9a20973c5761fd06Alkis Evlogimenos return reg; 463169cfd01964fc03828a7f2cad5d710890fbb08d8Alkis Evlogimenos} 464169cfd01964fc03828a7f2cad5d710890fbb08d8Alkis Evlogimenos 465e88280a4224730dcf8076e0d9a20973c5761fd06Alkis Evlogimenosvoid LiveIntervals::joinIntervals() 466dd2cc65f34f9b7bfda1cd0c42becedfc361d46f8Alkis Evlogimenos{ 46739a0d5c1123cfe4ddf826690b6744cc7248e3149Alkis Evlogimenos DEBUG(std::cerr << "********** JOINING INTERVALS ***********\n"); 468dd2cc65f34f9b7bfda1cd0c42becedfc361d46f8Alkis Evlogimenos 4699bcdcd17c7219dbc68de2f11ca2de86471c8c390Chris Lattner const TargetInstrInfo& tii = *tm_->getInstrInfo(); 470dd2cc65f34f9b7bfda1cd0c42becedfc361d46f8Alkis Evlogimenos 471c0b9dc5be79f009d260edb5cd5e1d8346587aaa2Alkis Evlogimenos for (MachineFunction::iterator mbbi = mf_->begin(), mbbe = mf_->end(); 472c0b9dc5be79f009d260edb5cd5e1d8346587aaa2Alkis Evlogimenos mbbi != mbbe; ++mbbi) { 473c0b9dc5be79f009d260edb5cd5e1d8346587aaa2Alkis Evlogimenos MachineBasicBlock* mbb = mbbi; 474015959ee38e4fd4a920f6b0065c50e524762f580Chris Lattner DEBUG(std::cerr << ((Value*)mbb->getBasicBlock())->getName() << ":\n"); 475e88280a4224730dcf8076e0d9a20973c5761fd06Alkis Evlogimenos 476c0b9dc5be79f009d260edb5cd5e1d8346587aaa2Alkis Evlogimenos for (MachineBasicBlock::iterator mi = mbb->begin(), mie = mbb->end(); 477c0b9dc5be79f009d260edb5cd5e1d8346587aaa2Alkis Evlogimenos mi != mie; ++mi) { 4789bcdcd17c7219dbc68de2f11ca2de86471c8c390Chris Lattner const TargetInstrDescriptor& tid = tii.get(mi->getOpcode()); 47939a0d5c1123cfe4ddf826690b6744cc7248e3149Alkis Evlogimenos DEBUG(std::cerr << getInstructionIndex(mi) << '\t'; 480b140762a45d21aaed054f15adaff0fc2274d939dTanya Lattner mi->print(std::cerr, tm_);); 481e88280a4224730dcf8076e0d9a20973c5761fd06Alkis Evlogimenos 48201e74a2aab64c5901a62d9ba9e1c263759929390Alkis Evlogimenos // we only join virtual registers with allocatable 48301e74a2aab64c5901a62d9ba9e1c263759929390Alkis Evlogimenos // physical registers since we do not have liveness information 48401e74a2aab64c5901a62d9ba9e1c263759929390Alkis Evlogimenos // on not allocatable physical registers 48501e74a2aab64c5901a62d9ba9e1c263759929390Alkis Evlogimenos unsigned regA, regB; 48601e74a2aab64c5901a62d9ba9e1c263759929390Alkis Evlogimenos if (tii.isMoveInstr(*mi, regA, regB) && 48701e74a2aab64c5901a62d9ba9e1c263759929390Alkis Evlogimenos (MRegisterInfo::isVirtualRegister(regA) || 48801e74a2aab64c5901a62d9ba9e1c263759929390Alkis Evlogimenos lv_->getAllocatablePhysicalRegisters()[regA]) && 48901e74a2aab64c5901a62d9ba9e1c263759929390Alkis Evlogimenos (MRegisterInfo::isVirtualRegister(regB) || 49001e74a2aab64c5901a62d9ba9e1c263759929390Alkis Evlogimenos lv_->getAllocatablePhysicalRegisters()[regB])) { 491e88280a4224730dcf8076e0d9a20973c5761fd06Alkis Evlogimenos 492e88280a4224730dcf8076e0d9a20973c5761fd06Alkis Evlogimenos // get representative registers 49301e74a2aab64c5901a62d9ba9e1c263759929390Alkis Evlogimenos regA = rep(regA); 49401e74a2aab64c5901a62d9ba9e1c263759929390Alkis Evlogimenos regB = rep(regB); 495e88280a4224730dcf8076e0d9a20973c5761fd06Alkis Evlogimenos 496e88280a4224730dcf8076e0d9a20973c5761fd06Alkis Evlogimenos // if they are already joined we continue 49701e74a2aab64c5901a62d9ba9e1c263759929390Alkis Evlogimenos if (regA == regB) 498e88280a4224730dcf8076e0d9a20973c5761fd06Alkis Evlogimenos continue; 499e88280a4224730dcf8076e0d9a20973c5761fd06Alkis Evlogimenos 50001e74a2aab64c5901a62d9ba9e1c263759929390Alkis Evlogimenos Reg2IntervalMap::iterator r2iA = r2iMap_.find(regA); 501e1b9536d546b78f8cffc7efbb2ff75d7e15f9749Chris Lattner assert(r2iA != r2iMap_.end() && 502e1b9536d546b78f8cffc7efbb2ff75d7e15f9749Chris Lattner "Found unknown vreg in 'isMoveInstr' instruction"); 50301e74a2aab64c5901a62d9ba9e1c263759929390Alkis Evlogimenos Reg2IntervalMap::iterator r2iB = r2iMap_.find(regB); 504e1b9536d546b78f8cffc7efbb2ff75d7e15f9749Chris Lattner assert(r2iB != r2iMap_.end() && 505e1b9536d546b78f8cffc7efbb2ff75d7e15f9749Chris Lattner "Found unknown vreg in 'isMoveInstr' instruction"); 50601e74a2aab64c5901a62d9ba9e1c263759929390Alkis Evlogimenos 50701e74a2aab64c5901a62d9ba9e1c263759929390Alkis Evlogimenos Intervals::iterator intA = r2iA->second; 50801e74a2aab64c5901a62d9ba9e1c263759929390Alkis Evlogimenos Intervals::iterator intB = r2iB->second; 50901e74a2aab64c5901a62d9ba9e1c263759929390Alkis Evlogimenos 51001e74a2aab64c5901a62d9ba9e1c263759929390Alkis Evlogimenos // both A and B are virtual registers 511e1b9536d546b78f8cffc7efbb2ff75d7e15f9749Chris Lattner 512e1b9536d546b78f8cffc7efbb2ff75d7e15f9749Chris Lattner // FIXME: coallescing two virtual registers together is 513e1b9536d546b78f8cffc7efbb2ff75d7e15f9749Chris Lattner // apparently broken. 514e1b9536d546b78f8cffc7efbb2ff75d7e15f9749Chris Lattner if (EnableVirtVirtJoining && 515e1b9536d546b78f8cffc7efbb2ff75d7e15f9749Chris Lattner MRegisterInfo::isVirtualRegister(intA->reg) && 51601e74a2aab64c5901a62d9ba9e1c263759929390Alkis Evlogimenos MRegisterInfo::isVirtualRegister(intB->reg)) { 51701e74a2aab64c5901a62d9ba9e1c263759929390Alkis Evlogimenos 51801e74a2aab64c5901a62d9ba9e1c263759929390Alkis Evlogimenos const TargetRegisterClass *rcA, *rcB; 51901e74a2aab64c5901a62d9ba9e1c263759929390Alkis Evlogimenos rcA = mf_->getSSARegMap()->getRegClass(intA->reg); 52001e74a2aab64c5901a62d9ba9e1c263759929390Alkis Evlogimenos rcB = mf_->getSSARegMap()->getRegClass(intB->reg); 5215de868b0b2daf145d7991bc9b3bf25807bcc7ca7Alkis Evlogimenos // if they are not of the same register class we continue 5225de868b0b2daf145d7991bc9b3bf25807bcc7ca7Alkis Evlogimenos if (rcA != rcB) 5235de868b0b2daf145d7991bc9b3bf25807bcc7ca7Alkis Evlogimenos continue; 52401e74a2aab64c5901a62d9ba9e1c263759929390Alkis Evlogimenos 52501e74a2aab64c5901a62d9ba9e1c263759929390Alkis Evlogimenos // if their intervals do not overlap we join them 52601e74a2aab64c5901a62d9ba9e1c263759929390Alkis Evlogimenos if (!intB->overlaps(*intA)) { 52701e74a2aab64c5901a62d9ba9e1c263759929390Alkis Evlogimenos intA->join(*intB); 52801e74a2aab64c5901a62d9ba9e1c263759929390Alkis Evlogimenos r2iB->second = r2iA->second; 52901e74a2aab64c5901a62d9ba9e1c263759929390Alkis Evlogimenos r2rMap_.insert(std::make_pair(intB->reg, intA->reg)); 53001e74a2aab64c5901a62d9ba9e1c263759929390Alkis Evlogimenos intervals_.erase(intB); 531e88280a4224730dcf8076e0d9a20973c5761fd06Alkis Evlogimenos } 532e1b9536d546b78f8cffc7efbb2ff75d7e15f9749Chris Lattner } else if (MRegisterInfo::isPhysicalRegister(intA->reg) ^ 533e1b9536d546b78f8cffc7efbb2ff75d7e15f9749Chris Lattner MRegisterInfo::isPhysicalRegister(intB->reg)) { 53401e74a2aab64c5901a62d9ba9e1c263759929390Alkis Evlogimenos if (MRegisterInfo::isPhysicalRegister(intB->reg)) { 53501e74a2aab64c5901a62d9ba9e1c263759929390Alkis Evlogimenos std::swap(regA, regB); 53601e74a2aab64c5901a62d9ba9e1c263759929390Alkis Evlogimenos std::swap(intA, intB); 53701e74a2aab64c5901a62d9ba9e1c263759929390Alkis Evlogimenos std::swap(r2iA, r2iB); 538e88280a4224730dcf8076e0d9a20973c5761fd06Alkis Evlogimenos } 53901e74a2aab64c5901a62d9ba9e1c263759929390Alkis Evlogimenos 54001e74a2aab64c5901a62d9ba9e1c263759929390Alkis Evlogimenos assert(MRegisterInfo::isPhysicalRegister(intA->reg) && 54101e74a2aab64c5901a62d9ba9e1c263759929390Alkis Evlogimenos MRegisterInfo::isVirtualRegister(intB->reg) && 54201e74a2aab64c5901a62d9ba9e1c263759929390Alkis Evlogimenos "A must be physical and B must be virtual"); 543676cf8cb1d613d626f826a45b44658ae35f58c7cAlkis Evlogimenos 5445de868b0b2daf145d7991bc9b3bf25807bcc7ca7Alkis Evlogimenos const TargetRegisterClass *rcA, *rcB; 5455de868b0b2daf145d7991bc9b3bf25807bcc7ca7Alkis Evlogimenos rcA = mri_->getRegClass(intA->reg); 5465de868b0b2daf145d7991bc9b3bf25807bcc7ca7Alkis Evlogimenos rcB = mf_->getSSARegMap()->getRegClass(intB->reg); 5475de868b0b2daf145d7991bc9b3bf25807bcc7ca7Alkis Evlogimenos // if they are not of the same register class we continue 5485de868b0b2daf145d7991bc9b3bf25807bcc7ca7Alkis Evlogimenos if (rcA != rcB) 5495de868b0b2daf145d7991bc9b3bf25807bcc7ca7Alkis Evlogimenos continue; 5505de868b0b2daf145d7991bc9b3bf25807bcc7ca7Alkis Evlogimenos 55101e74a2aab64c5901a62d9ba9e1c263759929390Alkis Evlogimenos if (!intA->overlaps(*intB) && 5529a8b490735d216435862a3d52e669357f165550fAlkis Evlogimenos !overlapsAliases(*intA, *intB)) { 55301e74a2aab64c5901a62d9ba9e1c263759929390Alkis Evlogimenos intA->join(*intB); 55401e74a2aab64c5901a62d9ba9e1c263759929390Alkis Evlogimenos r2iB->second = r2iA->second; 55501e74a2aab64c5901a62d9ba9e1c263759929390Alkis Evlogimenos r2rMap_.insert(std::make_pair(intB->reg, intA->reg)); 55601e74a2aab64c5901a62d9ba9e1c263759929390Alkis Evlogimenos intervals_.erase(intB); 557e88280a4224730dcf8076e0d9a20973c5761fd06Alkis Evlogimenos } 558e88280a4224730dcf8076e0d9a20973c5761fd06Alkis Evlogimenos } 559e88280a4224730dcf8076e0d9a20973c5761fd06Alkis Evlogimenos } 560e88280a4224730dcf8076e0d9a20973c5761fd06Alkis Evlogimenos } 561dd2cc65f34f9b7bfda1cd0c42becedfc361d46f8Alkis Evlogimenos } 562dd2cc65f34f9b7bfda1cd0c42becedfc361d46f8Alkis Evlogimenos} 563dd2cc65f34f9b7bfda1cd0c42becedfc361d46f8Alkis Evlogimenos 564418da55c89c9ba355b51dceecb16f4388ef35119Chris Lattnerbool LiveIntervals::overlapsAliases(const LiveInterval& lhs, 565418da55c89c9ba355b51dceecb16f4388ef35119Chris Lattner const LiveInterval& rhs) const 56679b0c3f0b9d91bbda354a2c6f22b6578655a5143Alkis Evlogimenos{ 5674f67b8664889d9e93b452a9a5f099d41d1bd235aAlkis Evlogimenos assert(MRegisterInfo::isPhysicalRegister(lhs.reg) && 56879b0c3f0b9d91bbda354a2c6f22b6578655a5143Alkis Evlogimenos "first interval must describe a physical register"); 56979b0c3f0b9d91bbda354a2c6f22b6578655a5143Alkis Evlogimenos 57079b0c3f0b9d91bbda354a2c6f22b6578655a5143Alkis Evlogimenos for (const unsigned* as = mri_->getAliasSet(lhs.reg); *as; ++as) { 57179b0c3f0b9d91bbda354a2c6f22b6578655a5143Alkis Evlogimenos Reg2IntervalMap::const_iterator r2i = r2iMap_.find(*as); 57279b0c3f0b9d91bbda354a2c6f22b6578655a5143Alkis Evlogimenos assert(r2i != r2iMap_.end() && "alias does not have interval?"); 57379b0c3f0b9d91bbda354a2c6f22b6578655a5143Alkis Evlogimenos if (rhs.overlaps(*r2i->second)) 57479b0c3f0b9d91bbda354a2c6f22b6578655a5143Alkis Evlogimenos return true; 57579b0c3f0b9d91bbda354a2c6f22b6578655a5143Alkis Evlogimenos } 57679b0c3f0b9d91bbda354a2c6f22b6578655a5143Alkis Evlogimenos 57779b0c3f0b9d91bbda354a2c6f22b6578655a5143Alkis Evlogimenos return false; 57879b0c3f0b9d91bbda354a2c6f22b6578655a5143Alkis Evlogimenos} 57979b0c3f0b9d91bbda354a2c6f22b6578655a5143Alkis Evlogimenos 580418da55c89c9ba355b51dceecb16f4388ef35119Chris LattnerLiveInterval& LiveIntervals::getOrCreateInterval(unsigned reg) 5819a8b490735d216435862a3d52e669357f165550fAlkis Evlogimenos{ 5829a8b490735d216435862a3d52e669357f165550fAlkis Evlogimenos Reg2IntervalMap::iterator r2iit = r2iMap_.lower_bound(reg); 5839a8b490735d216435862a3d52e669357f165550fAlkis Evlogimenos if (r2iit == r2iMap_.end() || r2iit->first != reg) { 584418da55c89c9ba355b51dceecb16f4388ef35119Chris Lattner intervals_.push_back(LiveInterval(reg)); 5859a8b490735d216435862a3d52e669357f165550fAlkis Evlogimenos r2iit = r2iMap_.insert(r2iit, std::make_pair(reg, --intervals_.end())); 5869a8b490735d216435862a3d52e669357f165550fAlkis Evlogimenos } 5879a8b490735d216435862a3d52e669357f165550fAlkis Evlogimenos 5889a8b490735d216435862a3d52e669357f165550fAlkis Evlogimenos return *r2iit->second; 5899a8b490735d216435862a3d52e669357f165550fAlkis Evlogimenos} 5909a8b490735d216435862a3d52e669357f165550fAlkis Evlogimenos 591418da55c89c9ba355b51dceecb16f4388ef35119Chris LattnerLiveInterval::LiveInterval(unsigned r) 592e88280a4224730dcf8076e0d9a20973c5761fd06Alkis Evlogimenos : reg(r), 593a19eedeb7aafc418ef2f017b8215ceafa7f1a76cChris Lattner weight((MRegisterInfo::isPhysicalRegister(r) ? HUGE_VAL : 0.0F)) 594dd2cc65f34f9b7bfda1cd0c42becedfc361d46f8Alkis Evlogimenos{ 595dd2cc65f34f9b7bfda1cd0c42becedfc361d46f8Alkis Evlogimenos} 596dd2cc65f34f9b7bfda1cd0c42becedfc361d46f8Alkis Evlogimenos 597418da55c89c9ba355b51dceecb16f4388ef35119Chris Lattnerbool LiveInterval::spilled() const 59839a0d5c1123cfe4ddf826690b6744cc7248e3149Alkis Evlogimenos{ 599a19eedeb7aafc418ef2f017b8215ceafa7f1a76cChris Lattner return (weight == HUGE_VAL && 60039a0d5c1123cfe4ddf826690b6744cc7248e3149Alkis Evlogimenos MRegisterInfo::isVirtualRegister(reg)); 60139a0d5c1123cfe4ddf826690b6744cc7248e3149Alkis Evlogimenos} 60239a0d5c1123cfe4ddf826690b6744cc7248e3149Alkis Evlogimenos 6030b8cb2bc47a6bee59c8c3f46d4cc047badf7f8acAlkis Evlogimenos// An example for liveAt(): 60408cec00588ec1a8fa85b208555f006d7396ae7a4Alkis Evlogimenos// 60539a0d5c1123cfe4ddf826690b6744cc7248e3149Alkis Evlogimenos// this = [1,4), liveAt(0) will return false. The instruction defining 60639a0d5c1123cfe4ddf826690b6744cc7248e3149Alkis Evlogimenos// this spans slots [0,3]. The interval belongs to an spilled 60739a0d5c1123cfe4ddf826690b6744cc7248e3149Alkis Evlogimenos// definition of the variable it represents. This is because slot 1 is 60839a0d5c1123cfe4ddf826690b6744cc7248e3149Alkis Evlogimenos// used (def slot) and spans up to slot 3 (store slot). 60908cec00588ec1a8fa85b208555f006d7396ae7a4Alkis Evlogimenos// 610418da55c89c9ba355b51dceecb16f4388ef35119Chris Lattnerbool LiveInterval::liveAt(unsigned index) const 611169cfd01964fc03828a7f2cad5d710890fbb08d8Alkis Evlogimenos{ 61297017de1872e08ffcdde2fccdfd399647c1ccc4aAlkis Evlogimenos Range dummy(index, index+1); 61397017de1872e08ffcdde2fccdfd399647c1ccc4aAlkis Evlogimenos Ranges::const_iterator r = std::upper_bound(ranges.begin(), 61497017de1872e08ffcdde2fccdfd399647c1ccc4aAlkis Evlogimenos ranges.end(), 61597017de1872e08ffcdde2fccdfd399647c1ccc4aAlkis Evlogimenos dummy); 61697017de1872e08ffcdde2fccdfd399647c1ccc4aAlkis Evlogimenos if (r == ranges.begin()) 61797017de1872e08ffcdde2fccdfd399647c1ccc4aAlkis Evlogimenos return false; 61897017de1872e08ffcdde2fccdfd399647c1ccc4aAlkis Evlogimenos 61997017de1872e08ffcdde2fccdfd399647c1ccc4aAlkis Evlogimenos --r; 6200b8cb2bc47a6bee59c8c3f46d4cc047badf7f8acAlkis Evlogimenos return index >= r->first && index < r->second; 621169cfd01964fc03828a7f2cad5d710890fbb08d8Alkis Evlogimenos} 622169cfd01964fc03828a7f2cad5d710890fbb08d8Alkis Evlogimenos 6230b8cb2bc47a6bee59c8c3f46d4cc047badf7f8acAlkis Evlogimenos// An example for overlaps(): 62408cec00588ec1a8fa85b208555f006d7396ae7a4Alkis Evlogimenos// 62508cec00588ec1a8fa85b208555f006d7396ae7a4Alkis Evlogimenos// 0: A = ... 62639a0d5c1123cfe4ddf826690b6744cc7248e3149Alkis Evlogimenos// 4: B = ... 62739a0d5c1123cfe4ddf826690b6744cc7248e3149Alkis Evlogimenos// 8: C = A + B ;; last use of A 62808cec00588ec1a8fa85b208555f006d7396ae7a4Alkis Evlogimenos// 62908cec00588ec1a8fa85b208555f006d7396ae7a4Alkis Evlogimenos// The live intervals should look like: 63008cec00588ec1a8fa85b208555f006d7396ae7a4Alkis Evlogimenos// 63139a0d5c1123cfe4ddf826690b6744cc7248e3149Alkis Evlogimenos// A = [3, 11) 63239a0d5c1123cfe4ddf826690b6744cc7248e3149Alkis Evlogimenos// B = [7, x) 63339a0d5c1123cfe4ddf826690b6744cc7248e3149Alkis Evlogimenos// C = [11, y) 63408cec00588ec1a8fa85b208555f006d7396ae7a4Alkis Evlogimenos// 63508cec00588ec1a8fa85b208555f006d7396ae7a4Alkis Evlogimenos// A->overlaps(C) should return false since we want to be able to join 63608cec00588ec1a8fa85b208555f006d7396ae7a4Alkis Evlogimenos// A and C. 637418da55c89c9ba355b51dceecb16f4388ef35119Chris Lattnerbool LiveInterval::overlaps(const LiveInterval& other) const 638169cfd01964fc03828a7f2cad5d710890fbb08d8Alkis Evlogimenos{ 63980b378cf7c3dce77029dc3118e1f63bc6d389da1Alkis Evlogimenos Ranges::const_iterator i = ranges.begin(); 64097017de1872e08ffcdde2fccdfd399647c1ccc4aAlkis Evlogimenos Ranges::const_iterator ie = ranges.end(); 64180b378cf7c3dce77029dc3118e1f63bc6d389da1Alkis Evlogimenos Ranges::const_iterator j = other.ranges.begin(); 64297017de1872e08ffcdde2fccdfd399647c1ccc4aAlkis Evlogimenos Ranges::const_iterator je = other.ranges.end(); 64397017de1872e08ffcdde2fccdfd399647c1ccc4aAlkis Evlogimenos if (i->first < j->first) { 64497017de1872e08ffcdde2fccdfd399647c1ccc4aAlkis Evlogimenos i = std::upper_bound(i, ie, *j); 64597017de1872e08ffcdde2fccdfd399647c1ccc4aAlkis Evlogimenos if (i != ranges.begin()) --i; 64697017de1872e08ffcdde2fccdfd399647c1ccc4aAlkis Evlogimenos } 64797017de1872e08ffcdde2fccdfd399647c1ccc4aAlkis Evlogimenos else if (j->first < i->first) { 64897017de1872e08ffcdde2fccdfd399647c1ccc4aAlkis Evlogimenos j = std::upper_bound(j, je, *i); 64997017de1872e08ffcdde2fccdfd399647c1ccc4aAlkis Evlogimenos if (j != other.ranges.begin()) --j; 65097017de1872e08ffcdde2fccdfd399647c1ccc4aAlkis Evlogimenos } 65197017de1872e08ffcdde2fccdfd399647c1ccc4aAlkis Evlogimenos 65297017de1872e08ffcdde2fccdfd399647c1ccc4aAlkis Evlogimenos while (i != ie && j != je) { 65397017de1872e08ffcdde2fccdfd399647c1ccc4aAlkis Evlogimenos if (i->first == j->first) { 65497017de1872e08ffcdde2fccdfd399647c1ccc4aAlkis Evlogimenos return true; 65597017de1872e08ffcdde2fccdfd399647c1ccc4aAlkis Evlogimenos } 65697017de1872e08ffcdde2fccdfd399647c1ccc4aAlkis Evlogimenos else { 65797017de1872e08ffcdde2fccdfd399647c1ccc4aAlkis Evlogimenos if (i->first > j->first) { 65897017de1872e08ffcdde2fccdfd399647c1ccc4aAlkis Evlogimenos swap(i, j); 65997017de1872e08ffcdde2fccdfd399647c1ccc4aAlkis Evlogimenos swap(ie, je); 66097017de1872e08ffcdde2fccdfd399647c1ccc4aAlkis Evlogimenos } 66197017de1872e08ffcdde2fccdfd399647c1ccc4aAlkis Evlogimenos assert(i->first < j->first); 66280b378cf7c3dce77029dc3118e1f63bc6d389da1Alkis Evlogimenos 6630b8cb2bc47a6bee59c8c3f46d4cc047badf7f8acAlkis Evlogimenos if (i->second > j->first) { 66480b378cf7c3dce77029dc3118e1f63bc6d389da1Alkis Evlogimenos return true; 66580b378cf7c3dce77029dc3118e1f63bc6d389da1Alkis Evlogimenos } 66680b378cf7c3dce77029dc3118e1f63bc6d389da1Alkis Evlogimenos else { 66780b378cf7c3dce77029dc3118e1f63bc6d389da1Alkis Evlogimenos ++i; 66880b378cf7c3dce77029dc3118e1f63bc6d389da1Alkis Evlogimenos } 66980b378cf7c3dce77029dc3118e1f63bc6d389da1Alkis Evlogimenos } 670169cfd01964fc03828a7f2cad5d710890fbb08d8Alkis Evlogimenos } 671169cfd01964fc03828a7f2cad5d710890fbb08d8Alkis Evlogimenos 672169cfd01964fc03828a7f2cad5d710890fbb08d8Alkis Evlogimenos return false; 673169cfd01964fc03828a7f2cad5d710890fbb08d8Alkis Evlogimenos} 674169cfd01964fc03828a7f2cad5d710890fbb08d8Alkis Evlogimenos 675418da55c89c9ba355b51dceecb16f4388ef35119Chris Lattnervoid LiveInterval::addRange(unsigned start, unsigned end) 676e88280a4224730dcf8076e0d9a20973c5761fd06Alkis Evlogimenos{ 67708cec00588ec1a8fa85b208555f006d7396ae7a4Alkis Evlogimenos assert(start < end && "Invalid range to add!"); 67839a0d5c1123cfe4ddf826690b6744cc7248e3149Alkis Evlogimenos DEBUG(std::cerr << " +[" << start << ',' << end << ")"); 679e88280a4224730dcf8076e0d9a20973c5761fd06Alkis Evlogimenos //assert(start < end && "invalid range?"); 680e88280a4224730dcf8076e0d9a20973c5761fd06Alkis Evlogimenos Range range = std::make_pair(start, end); 681e88280a4224730dcf8076e0d9a20973c5761fd06Alkis Evlogimenos Ranges::iterator it = 682e88280a4224730dcf8076e0d9a20973c5761fd06Alkis Evlogimenos ranges.insert(std::upper_bound(ranges.begin(), ranges.end(), range), 683e88280a4224730dcf8076e0d9a20973c5761fd06Alkis Evlogimenos range); 684e88280a4224730dcf8076e0d9a20973c5761fd06Alkis Evlogimenos 685e88280a4224730dcf8076e0d9a20973c5761fd06Alkis Evlogimenos it = mergeRangesForward(it); 686e88280a4224730dcf8076e0d9a20973c5761fd06Alkis Evlogimenos it = mergeRangesBackward(it); 687e88280a4224730dcf8076e0d9a20973c5761fd06Alkis Evlogimenos} 688e88280a4224730dcf8076e0d9a20973c5761fd06Alkis Evlogimenos 689418da55c89c9ba355b51dceecb16f4388ef35119Chris Lattnervoid LiveInterval::join(const LiveInterval& other) 690e88280a4224730dcf8076e0d9a20973c5761fd06Alkis Evlogimenos{ 69139a0d5c1123cfe4ddf826690b6744cc7248e3149Alkis Evlogimenos DEBUG(std::cerr << "\t\tjoining " << *this << " with " << other << '\n'); 692e88280a4224730dcf8076e0d9a20973c5761fd06Alkis Evlogimenos Ranges::iterator cur = ranges.begin(); 693e88280a4224730dcf8076e0d9a20973c5761fd06Alkis Evlogimenos 694e88280a4224730dcf8076e0d9a20973c5761fd06Alkis Evlogimenos for (Ranges::const_iterator i = other.ranges.begin(), 695e88280a4224730dcf8076e0d9a20973c5761fd06Alkis Evlogimenos e = other.ranges.end(); i != e; ++i) { 696e88280a4224730dcf8076e0d9a20973c5761fd06Alkis Evlogimenos cur = ranges.insert(std::upper_bound(cur, ranges.end(), *i), *i); 697e88280a4224730dcf8076e0d9a20973c5761fd06Alkis Evlogimenos cur = mergeRangesForward(cur); 698e88280a4224730dcf8076e0d9a20973c5761fd06Alkis Evlogimenos cur = mergeRangesBackward(cur); 699e88280a4224730dcf8076e0d9a20973c5761fd06Alkis Evlogimenos } 700cea44711203cfcb3b18528401ac1ad170677ebfeAlkis Evlogimenos weight += other.weight; 701cea44711203cfcb3b18528401ac1ad170677ebfeAlkis Evlogimenos ++numJoins; 702e88280a4224730dcf8076e0d9a20973c5761fd06Alkis Evlogimenos} 703e88280a4224730dcf8076e0d9a20973c5761fd06Alkis Evlogimenos 704418da55c89c9ba355b51dceecb16f4388ef35119Chris LattnerLiveInterval::Ranges::iterator LiveInterval:: 705418da55c89c9ba355b51dceecb16f4388ef35119Chris LattnermergeRangesForward(Ranges::iterator it) 706e88280a4224730dcf8076e0d9a20973c5761fd06Alkis Evlogimenos{ 7077200c6b82acb8401048a2bc8a423f23b48db6731Alkis Evlogimenos Ranges::iterator n; 7087200c6b82acb8401048a2bc8a423f23b48db6731Alkis Evlogimenos while ((n = next(it)) != ranges.end()) { 7097200c6b82acb8401048a2bc8a423f23b48db6731Alkis Evlogimenos if (n->first > it->second) 7107200c6b82acb8401048a2bc8a423f23b48db6731Alkis Evlogimenos break; 71123c114fd3bec342ac1a2a45801b892d6b4517afcAlkis Evlogimenos it->second = std::max(it->second, n->second); 71223c114fd3bec342ac1a2a45801b892d6b4517afcAlkis Evlogimenos n = ranges.erase(n); 713e88280a4224730dcf8076e0d9a20973c5761fd06Alkis Evlogimenos } 714e88280a4224730dcf8076e0d9a20973c5761fd06Alkis Evlogimenos return it; 715e88280a4224730dcf8076e0d9a20973c5761fd06Alkis Evlogimenos} 716e88280a4224730dcf8076e0d9a20973c5761fd06Alkis Evlogimenos 717418da55c89c9ba355b51dceecb16f4388ef35119Chris LattnerLiveInterval::Ranges::iterator LiveInterval:: 718418da55c89c9ba355b51dceecb16f4388ef35119Chris LattnermergeRangesBackward(Ranges::iterator it) 719e88280a4224730dcf8076e0d9a20973c5761fd06Alkis Evlogimenos{ 72008cec00588ec1a8fa85b208555f006d7396ae7a4Alkis Evlogimenos while (it != ranges.begin()) { 72123c114fd3bec342ac1a2a45801b892d6b4517afcAlkis Evlogimenos Ranges::iterator p = prior(it); 7227200c6b82acb8401048a2bc8a423f23b48db6731Alkis Evlogimenos if (it->first > p->second) 7237200c6b82acb8401048a2bc8a423f23b48db6731Alkis Evlogimenos break; 72408cec00588ec1a8fa85b208555f006d7396ae7a4Alkis Evlogimenos 72523c114fd3bec342ac1a2a45801b892d6b4517afcAlkis Evlogimenos it->first = std::min(it->first, p->first); 72623c114fd3bec342ac1a2a45801b892d6b4517afcAlkis Evlogimenos it->second = std::max(it->second, p->second); 72723c114fd3bec342ac1a2a45801b892d6b4517afcAlkis Evlogimenos it = ranges.erase(p); 728e88280a4224730dcf8076e0d9a20973c5761fd06Alkis Evlogimenos } 729e88280a4224730dcf8076e0d9a20973c5761fd06Alkis Evlogimenos 730e88280a4224730dcf8076e0d9a20973c5761fd06Alkis Evlogimenos return it; 731e88280a4224730dcf8076e0d9a20973c5761fd06Alkis Evlogimenos} 732e88280a4224730dcf8076e0d9a20973c5761fd06Alkis Evlogimenos 733418da55c89c9ba355b51dceecb16f4388ef35119Chris Lattnerstd::ostream& llvm::operator<<(std::ostream& os, const LiveInterval& li) 734b27ef248f579b354aab434f63c417ab1103e47e2Alkis Evlogimenos{ 7359a8b490735d216435862a3d52e669357f165550fAlkis Evlogimenos os << "%reg" << li.reg << ',' << li.weight; 73639a0d5c1123cfe4ddf826690b6744cc7248e3149Alkis Evlogimenos if (li.empty()) 73739a0d5c1123cfe4ddf826690b6744cc7248e3149Alkis Evlogimenos return os << "EMPTY"; 7389a8b490735d216435862a3d52e669357f165550fAlkis Evlogimenos 7399a8b490735d216435862a3d52e669357f165550fAlkis Evlogimenos os << " = "; 740418da55c89c9ba355b51dceecb16f4388ef35119Chris Lattner for (LiveInterval::Ranges::const_iterator 741b27ef248f579b354aab434f63c417ab1103e47e2Alkis Evlogimenos i = li.ranges.begin(), e = li.ranges.end(); i != e; ++i) { 74263841bc85d15ca0ce1b3208084f4262f3d33ef21Alkis Evlogimenos os << "[" << i->first << "," << i->second << ")"; 743b27ef248f579b354aab434f63c417ab1103e47e2Alkis Evlogimenos } 744b27ef248f579b354aab434f63c417ab1103e47e2Alkis Evlogimenos return os; 745b27ef248f579b354aab434f63c417ab1103e47e2Alkis Evlogimenos} 746