LiveIntervalAnalysis.cpp revision cea44711203cfcb3b18528401ac1ad170677ebfe
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" 19ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos#include "llvm/CodeGen/LiveIntervals.h" 206b4edbaaf9021e0434f0ce0c3724eb43ed41b770Alkis Evlogimenos#include "llvm/Analysis/LoopInfo.h" 21ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos#include "llvm/CodeGen/LiveVariables.h" 22ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos#include "llvm/CodeGen/MachineFrameInfo.h" 23ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos#include "llvm/CodeGen/MachineInstr.h" 24ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos#include "llvm/CodeGen/Passes.h" 25ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos#include "llvm/CodeGen/SSARegMap.h" 26ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos#include "llvm/Target/MRegisterInfo.h" 27ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos#include "llvm/Target/TargetInstrInfo.h" 28ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos#include "llvm/Target/TargetMachine.h" 29ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos#include "llvm/Support/CFG.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" 344d46e1e521c0df1990ea50f8146d22bd77ea71a6Alkis Evlogimenos#include <cmath> 35ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos#include <iostream> 366b4edbaaf9021e0434f0ce0c3724eb43ed41b770Alkis Evlogimenos#include <limits> 37ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos 38ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenosusing namespace llvm; 39ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos 40ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenosnamespace { 41ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos RegisterAnalysis<LiveIntervals> X("liveintervals", 42ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos "Live Interval Analysis"); 43ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos 44ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos Statistic<> numIntervals("liveintervals", "Number of intervals"); 45cea44711203cfcb3b18528401ac1ad170677ebfeAlkis Evlogimenos Statistic<> numJoined ("liveintervals", "Number of intervals after " 46cea44711203cfcb3b18528401ac1ad170677ebfeAlkis Evlogimenos "coalescing"); 47cea44711203cfcb3b18528401ac1ad170677ebfeAlkis Evlogimenos Statistic<> numJoins ("liveintervals", "Number of interval joins " 48cea44711203cfcb3b18528401ac1ad170677ebfeAlkis Evlogimenos "performed"); 49843b160a2040b3ec4d3452678450afa11704c473Alkis Evlogimenos Statistic<> numPeep ("liveintervals", "Number of identity moves " 50843b160a2040b3ec4d3452678450afa11704c473Alkis Evlogimenos "eliminated after coalescing"); 5139a0d5c1123cfe4ddf826690b6744cc7248e3149Alkis Evlogimenos Statistic<> numFolded ("liveintervals", "Number of register operands " 5239a0d5c1123cfe4ddf826690b6744cc7248e3149Alkis Evlogimenos "folded"); 53e88280a4224730dcf8076e0d9a20973c5761fd06Alkis Evlogimenos cl::opt<bool> 54e88280a4224730dcf8076e0d9a20973c5761fd06Alkis Evlogimenos join("join-liveintervals", 55e88280a4224730dcf8076e0d9a20973c5761fd06Alkis Evlogimenos cl::desc("Join compatible live intervals"), 5679b0c3f0b9d91bbda354a2c6f22b6578655a5143Alkis Evlogimenos cl::init(true)); 57ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos}; 58ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos 59ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenosvoid LiveIntervals::getAnalysisUsage(AnalysisUsage &AU) const 60ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos{ 61f6f91bf6680668990ff3804b14cf05beedc56ec4Alkis Evlogimenos AU.addPreserved<LiveVariables>(); 62ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos AU.addRequired<LiveVariables>(); 63f6f91bf6680668990ff3804b14cf05beedc56ec4Alkis Evlogimenos AU.addPreservedID(PHIEliminationID); 64ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos AU.addRequiredID(PHIEliminationID); 654c080863de86448d905beab27686da823b6d44c1Alkis Evlogimenos AU.addRequiredID(TwoAddressInstructionPassID); 666b4edbaaf9021e0434f0ce0c3724eb43ed41b770Alkis Evlogimenos AU.addRequired<LoopInfo>(); 67ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos MachineFunctionPass::getAnalysisUsage(AU); 68ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos} 69ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos 7008cec00588ec1a8fa85b208555f006d7396ae7a4Alkis Evlogimenosvoid LiveIntervals::releaseMemory() 7108cec00588ec1a8fa85b208555f006d7396ae7a4Alkis Evlogimenos{ 7208cec00588ec1a8fa85b208555f006d7396ae7a4Alkis Evlogimenos mbbi2mbbMap_.clear(); 7308cec00588ec1a8fa85b208555f006d7396ae7a4Alkis Evlogimenos mi2iMap_.clear(); 74843b160a2040b3ec4d3452678450afa11704c473Alkis Evlogimenos i2miMap_.clear(); 7508cec00588ec1a8fa85b208555f006d7396ae7a4Alkis Evlogimenos r2iMap_.clear(); 7608cec00588ec1a8fa85b208555f006d7396ae7a4Alkis Evlogimenos r2rMap_.clear(); 7708cec00588ec1a8fa85b208555f006d7396ae7a4Alkis Evlogimenos intervals_.clear(); 7808cec00588ec1a8fa85b208555f006d7396ae7a4Alkis Evlogimenos} 7908cec00588ec1a8fa85b208555f006d7396ae7a4Alkis Evlogimenos 8008cec00588ec1a8fa85b208555f006d7396ae7a4Alkis Evlogimenos 81ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos/// runOnMachineFunction - Register allocate the whole function 82ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos/// 83ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenosbool LiveIntervals::runOnMachineFunction(MachineFunction &fn) { 84ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos mf_ = &fn; 85ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos tm_ = &fn.getTarget(); 86ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos mri_ = tm_->getRegisterInfo(); 87ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos lv_ = &getAnalysis<LiveVariables>(); 88ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos 89ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos // number MachineInstrs 90ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos unsigned miIndex = 0; 91ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos for (MachineFunction::iterator mbb = mf_->begin(), mbbEnd = mf_->end(); 92ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos mbb != mbbEnd; ++mbb) { 93ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos const std::pair<MachineBasicBlock*, unsigned>& entry = 9408cec00588ec1a8fa85b208555f006d7396ae7a4Alkis Evlogimenos lv_->getMachineBasicBlockInfo(mbb); 95ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos bool inserted = mbbi2mbbMap_.insert(std::make_pair(entry.second, 96ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos entry.first)).second; 97ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos assert(inserted && "multiple index -> MachineBasicBlock"); 98ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos 99ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos for (MachineBasicBlock::iterator mi = mbb->begin(), miEnd = mbb->end(); 100ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos mi != miEnd; ++mi) { 101c0b9dc5be79f009d260edb5cd5e1d8346587aaa2Alkis Evlogimenos inserted = mi2iMap_.insert(std::make_pair(mi, miIndex)).second; 102ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos assert(inserted && "multiple MachineInstr -> index mappings"); 103843b160a2040b3ec4d3452678450afa11704c473Alkis Evlogimenos i2miMap_.push_back(mi); 10439a0d5c1123cfe4ddf826690b6744cc7248e3149Alkis Evlogimenos miIndex += InstrSlots::NUM; 105ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos } 106ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos } 107ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos 108ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos computeIntervals(); 109ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos 110843b160a2040b3ec4d3452678450afa11704c473Alkis Evlogimenos numIntervals += intervals_.size(); 111843b160a2040b3ec4d3452678450afa11704c473Alkis Evlogimenos 112843b160a2040b3ec4d3452678450afa11704c473Alkis Evlogimenos // join intervals if requested 113843b160a2040b3ec4d3452678450afa11704c473Alkis Evlogimenos if (join) joinIntervals(); 114843b160a2040b3ec4d3452678450afa11704c473Alkis Evlogimenos 115843b160a2040b3ec4d3452678450afa11704c473Alkis Evlogimenos // perform a final pass over the instructions and compute spill 116843b160a2040b3ec4d3452678450afa11704c473Alkis Evlogimenos // weights, coalesce virtual registers and remove identity moves 1177a40eaaceec0af76d5b97610f3d4e7a47a19d245Alkis Evlogimenos const LoopInfo& loopInfo = getAnalysis<LoopInfo>(); 11826bfc08b80c904c71487ac1ab49a8b3a15a8d3e9Alkis Evlogimenos const TargetInstrInfo& tii = tm_->getInstrInfo(); 1197a40eaaceec0af76d5b97610f3d4e7a47a19d245Alkis Evlogimenos 120843b160a2040b3ec4d3452678450afa11704c473Alkis Evlogimenos for (MachineFunction::iterator mbbi = mf_->begin(), mbbe = mf_->end(); 121843b160a2040b3ec4d3452678450afa11704c473Alkis Evlogimenos mbbi != mbbe; ++mbbi) { 122843b160a2040b3ec4d3452678450afa11704c473Alkis Evlogimenos MachineBasicBlock* mbb = mbbi; 1237a40eaaceec0af76d5b97610f3d4e7a47a19d245Alkis Evlogimenos unsigned loopDepth = loopInfo.getLoopDepth(mbb->getBasicBlock()); 1247a40eaaceec0af76d5b97610f3d4e7a47a19d245Alkis Evlogimenos 125843b160a2040b3ec4d3452678450afa11704c473Alkis Evlogimenos for (MachineBasicBlock::iterator mii = mbb->begin(), mie = mbb->end(); 126843b160a2040b3ec4d3452678450afa11704c473Alkis Evlogimenos mii != mie; ) { 127843b160a2040b3ec4d3452678450afa11704c473Alkis Evlogimenos for (unsigned i = 0; i < mii->getNumOperands(); ++i) { 128843b160a2040b3ec4d3452678450afa11704c473Alkis Evlogimenos const MachineOperand& mop = mii->getOperand(i); 129843b160a2040b3ec4d3452678450afa11704c473Alkis Evlogimenos if (mop.isRegister()) { 130843b160a2040b3ec4d3452678450afa11704c473Alkis Evlogimenos // replace register with representative register 131843b160a2040b3ec4d3452678450afa11704c473Alkis Evlogimenos unsigned reg = rep(mop.getReg()); 132843b160a2040b3ec4d3452678450afa11704c473Alkis Evlogimenos mii->SetMachineOperandReg(i, reg); 133843b160a2040b3ec4d3452678450afa11704c473Alkis Evlogimenos 134843b160a2040b3ec4d3452678450afa11704c473Alkis Evlogimenos if (MRegisterInfo::isVirtualRegister(reg)) { 135843b160a2040b3ec4d3452678450afa11704c473Alkis Evlogimenos Reg2IntervalMap::iterator r2iit = r2iMap_.find(reg); 136843b160a2040b3ec4d3452678450afa11704c473Alkis Evlogimenos assert(r2iit != r2iMap_.end()); 137843b160a2040b3ec4d3452678450afa11704c473Alkis Evlogimenos r2iit->second->weight += pow(10.0F, loopDepth); 138843b160a2040b3ec4d3452678450afa11704c473Alkis Evlogimenos } 139843b160a2040b3ec4d3452678450afa11704c473Alkis Evlogimenos } 140843b160a2040b3ec4d3452678450afa11704c473Alkis Evlogimenos } 141843b160a2040b3ec4d3452678450afa11704c473Alkis Evlogimenos 142843b160a2040b3ec4d3452678450afa11704c473Alkis Evlogimenos // if the move is now an identity move delete it 143843b160a2040b3ec4d3452678450afa11704c473Alkis Evlogimenos unsigned srcReg, dstReg; 144843b160a2040b3ec4d3452678450afa11704c473Alkis Evlogimenos if (tii.isMoveInstr(*mii, srcReg, dstReg) && srcReg == dstReg) { 145843b160a2040b3ec4d3452678450afa11704c473Alkis Evlogimenos // remove index -> MachineInstr and 146843b160a2040b3ec4d3452678450afa11704c473Alkis Evlogimenos // MachineInstr -> index mappings 147843b160a2040b3ec4d3452678450afa11704c473Alkis Evlogimenos Mi2IndexMap::iterator mi2i = mi2iMap_.find(mii); 148843b160a2040b3ec4d3452678450afa11704c473Alkis Evlogimenos if (mi2i != mi2iMap_.end()) { 14939a0d5c1123cfe4ddf826690b6744cc7248e3149Alkis Evlogimenos i2miMap_[mi2i->second/InstrSlots::NUM] = 0; 150843b160a2040b3ec4d3452678450afa11704c473Alkis Evlogimenos mi2iMap_.erase(mi2i); 15108cec00588ec1a8fa85b208555f006d7396ae7a4Alkis Evlogimenos } 152843b160a2040b3ec4d3452678450afa11704c473Alkis Evlogimenos mii = mbbi->erase(mii); 153843b160a2040b3ec4d3452678450afa11704c473Alkis Evlogimenos ++numPeep; 1547a40eaaceec0af76d5b97610f3d4e7a47a19d245Alkis Evlogimenos } 155843b160a2040b3ec4d3452678450afa11704c473Alkis Evlogimenos else 156843b160a2040b3ec4d3452678450afa11704c473Alkis Evlogimenos ++mii; 1577a40eaaceec0af76d5b97610f3d4e7a47a19d245Alkis Evlogimenos } 1587a40eaaceec0af76d5b97610f3d4e7a47a19d245Alkis Evlogimenos } 1597a40eaaceec0af76d5b97610f3d4e7a47a19d245Alkis Evlogimenos 16001e74a2aab64c5901a62d9ba9e1c263759929390Alkis Evlogimenos intervals_.sort(StartPointComp()); 16139a0d5c1123cfe4ddf826690b6744cc7248e3149Alkis Evlogimenos DEBUG(std::cerr << "********** INTERVALS **********\n"); 16201e74a2aab64c5901a62d9ba9e1c263759929390Alkis Evlogimenos DEBUG(std::copy(intervals_.begin(), intervals_.end(), 16301e74a2aab64c5901a62d9ba9e1c263759929390Alkis Evlogimenos std::ostream_iterator<Interval>(std::cerr, "\n"))); 16439a0d5c1123cfe4ddf826690b6744cc7248e3149Alkis Evlogimenos DEBUG(std::cerr << "********** MACHINEINSTRS **********\n"); 165843b160a2040b3ec4d3452678450afa11704c473Alkis Evlogimenos DEBUG( 166843b160a2040b3ec4d3452678450afa11704c473Alkis Evlogimenos for (unsigned i = 0; i != i2miMap_.size(); ++i) { 167843b160a2040b3ec4d3452678450afa11704c473Alkis Evlogimenos if (const MachineInstr* mi = i2miMap_[i]) { 16839a0d5c1123cfe4ddf826690b6744cc7248e3149Alkis Evlogimenos std:: cerr << i * InstrSlots::NUM << '\t'; 169843b160a2040b3ec4d3452678450afa11704c473Alkis Evlogimenos mi->print(std::cerr, *tm_); 170843b160a2040b3ec4d3452678450afa11704c473Alkis Evlogimenos } 171843b160a2040b3ec4d3452678450afa11704c473Alkis Evlogimenos }); 172843b160a2040b3ec4d3452678450afa11704c473Alkis Evlogimenos 173ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos return true; 174ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos} 175ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos 17639a0d5c1123cfe4ddf826690b6744cc7248e3149Alkis Evlogimenosvoid LiveIntervals::updateSpilledInterval(Interval& li, int slot) 177843b160a2040b3ec4d3452678450afa11704c473Alkis Evlogimenos{ 178843b160a2040b3ec4d3452678450afa11704c473Alkis Evlogimenos assert(li.weight != std::numeric_limits<float>::infinity() && 179843b160a2040b3ec4d3452678450afa11704c473Alkis Evlogimenos "attempt to spill already spilled interval!"); 180843b160a2040b3ec4d3452678450afa11704c473Alkis Evlogimenos Interval::Ranges oldRanges; 181843b160a2040b3ec4d3452678450afa11704c473Alkis Evlogimenos swap(oldRanges, li.ranges); 182843b160a2040b3ec4d3452678450afa11704c473Alkis Evlogimenos 18339a0d5c1123cfe4ddf826690b6744cc7248e3149Alkis Evlogimenos DEBUG(std::cerr << "\t\t\t\tupdating interval: " << li); 18439a0d5c1123cfe4ddf826690b6744cc7248e3149Alkis Evlogimenos 185843b160a2040b3ec4d3452678450afa11704c473Alkis Evlogimenos for (Interval::Ranges::iterator i = oldRanges.begin(), e = oldRanges.end(); 186843b160a2040b3ec4d3452678450afa11704c473Alkis Evlogimenos i != e; ++i) { 18739a0d5c1123cfe4ddf826690b6744cc7248e3149Alkis Evlogimenos unsigned index = getBaseIndex(i->first); 18839a0d5c1123cfe4ddf826690b6744cc7248e3149Alkis Evlogimenos unsigned end = getBaseIndex(i->second-1) + InstrSlots::NUM; 18939a0d5c1123cfe4ddf826690b6744cc7248e3149Alkis Evlogimenos for (; index < end; index += InstrSlots::NUM) { 190843b160a2040b3ec4d3452678450afa11704c473Alkis Evlogimenos // skip deleted instructions 19139a0d5c1123cfe4ddf826690b6744cc7248e3149Alkis Evlogimenos while (!getInstructionFromIndex(index)) index += InstrSlots::NUM; 19239a0d5c1123cfe4ddf826690b6744cc7248e3149Alkis Evlogimenos MachineBasicBlock::iterator mi = getInstructionFromIndex(index); 19339a0d5c1123cfe4ddf826690b6744cc7248e3149Alkis Evlogimenos 194843b160a2040b3ec4d3452678450afa11704c473Alkis Evlogimenos for (unsigned i = 0; i < mi->getNumOperands(); ++i) { 195843b160a2040b3ec4d3452678450afa11704c473Alkis Evlogimenos MachineOperand& mop = mi->getOperand(i); 19639a0d5c1123cfe4ddf826690b6744cc7248e3149Alkis Evlogimenos if (mop.isRegister() && mop.getReg() == li.reg) { 19739a0d5c1123cfe4ddf826690b6744cc7248e3149Alkis Evlogimenos // This is tricky. We need to add information in 19839a0d5c1123cfe4ddf826690b6744cc7248e3149Alkis Evlogimenos // the interval about the spill code so we have to 19939a0d5c1123cfe4ddf826690b6744cc7248e3149Alkis Evlogimenos // use our extra load/store slots. 20039a0d5c1123cfe4ddf826690b6744cc7248e3149Alkis Evlogimenos // 20139a0d5c1123cfe4ddf826690b6744cc7248e3149Alkis Evlogimenos // If we have a use we are going to have a load so 20239a0d5c1123cfe4ddf826690b6744cc7248e3149Alkis Evlogimenos // we start the interval from the load slot 20339a0d5c1123cfe4ddf826690b6744cc7248e3149Alkis Evlogimenos // onwards. Otherwise we start from the def slot. 20439a0d5c1123cfe4ddf826690b6744cc7248e3149Alkis Evlogimenos unsigned start = (mop.isUse() ? 20539a0d5c1123cfe4ddf826690b6744cc7248e3149Alkis Evlogimenos getLoadIndex(index) : 20639a0d5c1123cfe4ddf826690b6744cc7248e3149Alkis Evlogimenos getDefIndex(index)); 20739a0d5c1123cfe4ddf826690b6744cc7248e3149Alkis Evlogimenos // If we have a def we are going to have a store 20839a0d5c1123cfe4ddf826690b6744cc7248e3149Alkis Evlogimenos // right after it so we end the interval after the 20939a0d5c1123cfe4ddf826690b6744cc7248e3149Alkis Evlogimenos // use of the next instruction. Otherwise we end 21039a0d5c1123cfe4ddf826690b6744cc7248e3149Alkis Evlogimenos // after the use of this instruction. 21139a0d5c1123cfe4ddf826690b6744cc7248e3149Alkis Evlogimenos unsigned end = 1 + (mop.isDef() ? 21239a0d5c1123cfe4ddf826690b6744cc7248e3149Alkis Evlogimenos getUseIndex(index+InstrSlots::NUM) : 21339a0d5c1123cfe4ddf826690b6744cc7248e3149Alkis Evlogimenos getUseIndex(index)); 21439a0d5c1123cfe4ddf826690b6744cc7248e3149Alkis Evlogimenos li.addRange(start, end); 215843b160a2040b3ec4d3452678450afa11704c473Alkis Evlogimenos } 216843b160a2040b3ec4d3452678450afa11704c473Alkis Evlogimenos } 217843b160a2040b3ec4d3452678450afa11704c473Alkis Evlogimenos } 218843b160a2040b3ec4d3452678450afa11704c473Alkis Evlogimenos } 219843b160a2040b3ec4d3452678450afa11704c473Alkis Evlogimenos // the new spill weight is now infinity as it cannot be spilled again 220843b160a2040b3ec4d3452678450afa11704c473Alkis Evlogimenos li.weight = std::numeric_limits<float>::infinity(); 22139a0d5c1123cfe4ddf826690b6744cc7248e3149Alkis Evlogimenos DEBUG(std::cerr << '\n'); 222843b160a2040b3ec4d3452678450afa11704c473Alkis Evlogimenos} 223843b160a2040b3ec4d3452678450afa11704c473Alkis Evlogimenos 224ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenosvoid LiveIntervals::printRegName(unsigned reg) const 225ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos{ 2264f67b8664889d9e93b452a9a5f099d41d1bd235aAlkis Evlogimenos if (MRegisterInfo::isPhysicalRegister(reg)) 227ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos std::cerr << mri_->getName(reg); 228ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos else 22939a0d5c1123cfe4ddf826690b6744cc7248e3149Alkis Evlogimenos std::cerr << "%reg" << reg; 230ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos} 231ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos 232ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenosvoid LiveIntervals::handleVirtualRegisterDef(MachineBasicBlock* mbb, 233ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos MachineBasicBlock::iterator mi, 234ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos unsigned reg) 235ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos{ 23639a0d5c1123cfe4ddf826690b6744cc7248e3149Alkis Evlogimenos DEBUG(std::cerr << "\t\tregister: "; printRegName(reg)); 237ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos LiveVariables::VarInfo& vi = lv_->getVarInfo(reg); 238ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos 239dd2cc65f34f9b7bfda1cd0c42becedfc361d46f8Alkis Evlogimenos Interval* interval = 0; 24008cec00588ec1a8fa85b208555f006d7396ae7a4Alkis Evlogimenos Reg2IntervalMap::iterator r2iit = r2iMap_.lower_bound(reg); 24108cec00588ec1a8fa85b208555f006d7396ae7a4Alkis Evlogimenos if (r2iit == r2iMap_.end() || r2iit->first != reg) { 242ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos // add new interval 243ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos intervals_.push_back(Interval(reg)); 244ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos // update interval index for this register 24508cec00588ec1a8fa85b208555f006d7396ae7a4Alkis Evlogimenos r2iMap_.insert(r2iit, std::make_pair(reg, --intervals_.end())); 246dd2cc65f34f9b7bfda1cd0c42becedfc361d46f8Alkis Evlogimenos interval = &intervals_.back(); 247ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos 248ad48cd6327df13ad4b8530733bbf115224bf9562Alkis Evlogimenos // iterate over all of the blocks that the variable is 249ad48cd6327df13ad4b8530733bbf115224bf9562Alkis Evlogimenos // completely live in, adding them to the live 250ad48cd6327df13ad4b8530733bbf115224bf9562Alkis Evlogimenos // interval. obviously we only need to do this once. 251ad48cd6327df13ad4b8530733bbf115224bf9562Alkis Evlogimenos for (unsigned i = 0, e = vi.AliveBlocks.size(); i != e; ++i) { 252ad48cd6327df13ad4b8530733bbf115224bf9562Alkis Evlogimenos if (vi.AliveBlocks[i]) { 253ad48cd6327df13ad4b8530733bbf115224bf9562Alkis Evlogimenos MachineBasicBlock* mbb = lv_->getIndexMachineBasicBlock(i); 254ad48cd6327df13ad4b8530733bbf115224bf9562Alkis Evlogimenos if (!mbb->empty()) { 25539a0d5c1123cfe4ddf826690b6744cc7248e3149Alkis Evlogimenos interval->addRange( 25639a0d5c1123cfe4ddf826690b6744cc7248e3149Alkis Evlogimenos getInstructionIndex(&mbb->front()), 25739a0d5c1123cfe4ddf826690b6744cc7248e3149Alkis Evlogimenos getInstructionIndex(&mbb->back()) + InstrSlots::NUM); 258ad48cd6327df13ad4b8530733bbf115224bf9562Alkis Evlogimenos } 25952220f61bba91ab787d4cc0aee47df4e2ca55c04Alkis Evlogimenos } 260ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos } 261dd2cc65f34f9b7bfda1cd0c42becedfc361d46f8Alkis Evlogimenos } 262ad48cd6327df13ad4b8530733bbf115224bf9562Alkis Evlogimenos else { 263ad48cd6327df13ad4b8530733bbf115224bf9562Alkis Evlogimenos interval = &*r2iit->second; 264ad48cd6327df13ad4b8530733bbf115224bf9562Alkis Evlogimenos } 265ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos 26639a0d5c1123cfe4ddf826690b6744cc7248e3149Alkis Evlogimenos unsigned baseIndex = getInstructionIndex(mi); 2670b8cb2bc47a6bee59c8c3f46d4cc047badf7f8acAlkis Evlogimenos 268dd2cc65f34f9b7bfda1cd0c42becedfc361d46f8Alkis Evlogimenos bool killedInDefiningBasicBlock = false; 269dd2cc65f34f9b7bfda1cd0c42becedfc361d46f8Alkis Evlogimenos for (int i = 0, e = vi.Kills.size(); i != e; ++i) { 270dd2cc65f34f9b7bfda1cd0c42becedfc361d46f8Alkis Evlogimenos MachineBasicBlock* killerBlock = vi.Kills[i].first; 271dd2cc65f34f9b7bfda1cd0c42becedfc361d46f8Alkis Evlogimenos MachineInstr* killerInstr = vi.Kills[i].second; 272dd2cc65f34f9b7bfda1cd0c42becedfc361d46f8Alkis Evlogimenos unsigned start = (mbb == killerBlock ? 27339a0d5c1123cfe4ddf826690b6744cc7248e3149Alkis Evlogimenos getDefIndex(baseIndex) : 274c0b9dc5be79f009d260edb5cd5e1d8346587aaa2Alkis Evlogimenos getInstructionIndex(&killerBlock->front())); 275c0b9dc5be79f009d260edb5cd5e1d8346587aaa2Alkis Evlogimenos unsigned end = (killerInstr == mi ? 27639a0d5c1123cfe4ddf826690b6744cc7248e3149Alkis Evlogimenos // dead 27739a0d5c1123cfe4ddf826690b6744cc7248e3149Alkis Evlogimenos start + 1 : 27839a0d5c1123cfe4ddf826690b6744cc7248e3149Alkis Evlogimenos // killed 27939a0d5c1123cfe4ddf826690b6744cc7248e3149Alkis Evlogimenos getUseIndex(getInstructionIndex(killerInstr))+1); 28008cec00588ec1a8fa85b208555f006d7396ae7a4Alkis Evlogimenos // we do not want to add invalid ranges. these can happen when 28108cec00588ec1a8fa85b208555f006d7396ae7a4Alkis Evlogimenos // a variable has its latest use and is redefined later on in 28208cec00588ec1a8fa85b208555f006d7396ae7a4Alkis Evlogimenos // the same basic block (common with variables introduced by 28308cec00588ec1a8fa85b208555f006d7396ae7a4Alkis Evlogimenos // PHI elimination) 28443f692f90f6b27304570e1b1807542dff4b8e847Alkis Evlogimenos if (start < end) { 28543f692f90f6b27304570e1b1807542dff4b8e847Alkis Evlogimenos killedInDefiningBasicBlock |= mbb == killerBlock; 28643f692f90f6b27304570e1b1807542dff4b8e847Alkis Evlogimenos interval->addRange(start, end); 28743f692f90f6b27304570e1b1807542dff4b8e847Alkis Evlogimenos } 288dd2cc65f34f9b7bfda1cd0c42becedfc361d46f8Alkis Evlogimenos } 289ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos 290dd2cc65f34f9b7bfda1cd0c42becedfc361d46f8Alkis Evlogimenos if (!killedInDefiningBasicBlock) { 29139a0d5c1123cfe4ddf826690b6744cc7248e3149Alkis Evlogimenos unsigned end = getInstructionIndex(&mbb->back()) + InstrSlots::NUM; 29239a0d5c1123cfe4ddf826690b6744cc7248e3149Alkis Evlogimenos interval->addRange(getDefIndex(baseIndex), end); 293ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos } 29439a0d5c1123cfe4ddf826690b6744cc7248e3149Alkis Evlogimenos DEBUG(std::cerr << '\n'); 295ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos} 296ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos 297ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenosvoid LiveIntervals::handlePhysicalRegisterDef(MachineBasicBlock* mbb, 298ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos MachineBasicBlock::iterator mi, 299ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos unsigned reg) 300ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos{ 3011a119e24106810310825f44c7bfd232d3272e639Alkis Evlogimenos DEBUG(std::cerr << "\t\tregister: "; printRegName(reg)); 30239a0d5c1123cfe4ddf826690b6744cc7248e3149Alkis Evlogimenos typedef LiveVariables::killed_iterator KillIter; 303ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos 30402ba13c9897ae2b19f9201e57460d7ee2b753a0bAlkis Evlogimenos MachineBasicBlock::iterator e = mbb->end(); 30539a0d5c1123cfe4ddf826690b6744cc7248e3149Alkis Evlogimenos unsigned baseIndex = getInstructionIndex(mi); 30639a0d5c1123cfe4ddf826690b6744cc7248e3149Alkis Evlogimenos unsigned start = getDefIndex(baseIndex); 30739a0d5c1123cfe4ddf826690b6744cc7248e3149Alkis Evlogimenos unsigned end = start; 3084d46e1e521c0df1990ea50f8146d22bd77ea71a6Alkis Evlogimenos 30902ba13c9897ae2b19f9201e57460d7ee2b753a0bAlkis Evlogimenos // a variable can be dead by the instruction defining it 310c0b9dc5be79f009d260edb5cd5e1d8346587aaa2Alkis Evlogimenos for (KillIter ki = lv_->dead_begin(mi), ke = lv_->dead_end(mi); 311af25473d5e99e0c0968746e12d8827e4b712bd31Alkis Evlogimenos ki != ke; ++ki) { 312af25473d5e99e0c0968746e12d8827e4b712bd31Alkis Evlogimenos if (reg == ki->second) { 31339a0d5c1123cfe4ddf826690b6744cc7248e3149Alkis Evlogimenos DEBUG(std::cerr << " dead"); 31439a0d5c1123cfe4ddf826690b6744cc7248e3149Alkis Evlogimenos end = getDefIndex(start) + 1; 315af25473d5e99e0c0968746e12d8827e4b712bd31Alkis Evlogimenos goto exit; 316af25473d5e99e0c0968746e12d8827e4b712bd31Alkis Evlogimenos } 317af25473d5e99e0c0968746e12d8827e4b712bd31Alkis Evlogimenos } 318ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos 31902ba13c9897ae2b19f9201e57460d7ee2b753a0bAlkis Evlogimenos // a variable can only be killed by subsequent instructions 32002ba13c9897ae2b19f9201e57460d7ee2b753a0bAlkis Evlogimenos do { 32102ba13c9897ae2b19f9201e57460d7ee2b753a0bAlkis Evlogimenos ++mi; 32239a0d5c1123cfe4ddf826690b6744cc7248e3149Alkis Evlogimenos baseIndex += InstrSlots::NUM; 323c0b9dc5be79f009d260edb5cd5e1d8346587aaa2Alkis Evlogimenos for (KillIter ki = lv_->killed_begin(mi), ke = lv_->killed_end(mi); 3244d46e1e521c0df1990ea50f8146d22bd77ea71a6Alkis Evlogimenos ki != ke; ++ki) { 3254d46e1e521c0df1990ea50f8146d22bd77ea71a6Alkis Evlogimenos if (reg == ki->second) { 32639a0d5c1123cfe4ddf826690b6744cc7248e3149Alkis Evlogimenos DEBUG(std::cerr << " killed"); 32739a0d5c1123cfe4ddf826690b6744cc7248e3149Alkis Evlogimenos end = getUseIndex(baseIndex) + 1; 3284d46e1e521c0df1990ea50f8146d22bd77ea71a6Alkis Evlogimenos goto exit; 329ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos } 3304d46e1e521c0df1990ea50f8146d22bd77ea71a6Alkis Evlogimenos } 33102ba13c9897ae2b19f9201e57460d7ee2b753a0bAlkis Evlogimenos } while (mi != e); 33202ba13c9897ae2b19f9201e57460d7ee2b753a0bAlkis Evlogimenos 333ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenosexit: 334ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos assert(start < end && "did not find end of interval?"); 335ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos 33608cec00588ec1a8fa85b208555f006d7396ae7a4Alkis Evlogimenos Reg2IntervalMap::iterator r2iit = r2iMap_.lower_bound(reg); 33708cec00588ec1a8fa85b208555f006d7396ae7a4Alkis Evlogimenos if (r2iit != r2iMap_.end() && r2iit->first == reg) { 33808cec00588ec1a8fa85b208555f006d7396ae7a4Alkis Evlogimenos r2iit->second->addRange(start, end); 339ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos } 340ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos else { 341ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos intervals_.push_back(Interval(reg)); 342ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos // update interval index for this register 34308cec00588ec1a8fa85b208555f006d7396ae7a4Alkis Evlogimenos r2iMap_.insert(r2iit, std::make_pair(reg, --intervals_.end())); 34408cec00588ec1a8fa85b208555f006d7396ae7a4Alkis Evlogimenos intervals_.back().addRange(start, end); 345ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos } 34639a0d5c1123cfe4ddf826690b6744cc7248e3149Alkis Evlogimenos DEBUG(std::cerr << '\n'); 347ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos} 348ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos 349ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenosvoid LiveIntervals::handleRegisterDef(MachineBasicBlock* mbb, 350ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos MachineBasicBlock::iterator mi, 351ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos unsigned reg) 352ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos{ 3534f67b8664889d9e93b452a9a5f099d41d1bd235aAlkis Evlogimenos if (MRegisterInfo::isPhysicalRegister(reg)) { 3541a119e24106810310825f44c7bfd232d3272e639Alkis Evlogimenos if (lv_->getAllocatablePhysicalRegisters()[reg]) { 355ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos handlePhysicalRegisterDef(mbb, mi, reg); 35619b6486d3891c8a02a301aa1b44348a420772fcfAlkis Evlogimenos for (const unsigned* as = mri_->getAliasSet(reg); *as; ++as) 35719b6486d3891c8a02a301aa1b44348a420772fcfAlkis Evlogimenos handlePhysicalRegisterDef(mbb, mi, *as); 358ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos } 359ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos } 360ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos else { 361ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos handleVirtualRegisterDef(mbb, mi, reg); 362ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos } 363ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos} 364ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos 3654d46e1e521c0df1990ea50f8146d22bd77ea71a6Alkis Evlogimenosunsigned LiveIntervals::getInstructionIndex(MachineInstr* instr) const 3664d46e1e521c0df1990ea50f8146d22bd77ea71a6Alkis Evlogimenos{ 367843b160a2040b3ec4d3452678450afa11704c473Alkis Evlogimenos Mi2IndexMap::const_iterator it = mi2iMap_.find(instr); 36839a0d5c1123cfe4ddf826690b6744cc7248e3149Alkis Evlogimenos return (it == mi2iMap_.end() ? 36939a0d5c1123cfe4ddf826690b6744cc7248e3149Alkis Evlogimenos std::numeric_limits<unsigned>::max() : 37039a0d5c1123cfe4ddf826690b6744cc7248e3149Alkis Evlogimenos it->second); 371843b160a2040b3ec4d3452678450afa11704c473Alkis Evlogimenos} 372843b160a2040b3ec4d3452678450afa11704c473Alkis Evlogimenos 373843b160a2040b3ec4d3452678450afa11704c473Alkis EvlogimenosMachineInstr* LiveIntervals::getInstructionFromIndex(unsigned index) const 374843b160a2040b3ec4d3452678450afa11704c473Alkis Evlogimenos{ 37539a0d5c1123cfe4ddf826690b6744cc7248e3149Alkis Evlogimenos index /= InstrSlots::NUM; // convert index to vector index 376843b160a2040b3ec4d3452678450afa11704c473Alkis Evlogimenos assert(index < i2miMap_.size() && 377843b160a2040b3ec4d3452678450afa11704c473Alkis Evlogimenos "index does not correspond to an instruction"); 378843b160a2040b3ec4d3452678450afa11704c473Alkis Evlogimenos return i2miMap_[index]; 3794d46e1e521c0df1990ea50f8146d22bd77ea71a6Alkis Evlogimenos} 3804d46e1e521c0df1990ea50f8146d22bd77ea71a6Alkis Evlogimenos 381ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos/// computeIntervals - computes the live intervals for virtual 3824d46e1e521c0df1990ea50f8146d22bd77ea71a6Alkis Evlogimenos/// registers. for some ordering of the machine instructions [1,N] a 38308cec00588ec1a8fa85b208555f006d7396ae7a4Alkis Evlogimenos/// live interval is an interval [i, j) where 1 <= i <= j < N for 384ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos/// which a variable is live 385ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenosvoid LiveIntervals::computeIntervals() 386ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos{ 38739a0d5c1123cfe4ddf826690b6744cc7248e3149Alkis Evlogimenos DEBUG(std::cerr << "********** COMPUTING LIVE INTERVALS **********\n"); 38839a0d5c1123cfe4ddf826690b6744cc7248e3149Alkis Evlogimenos DEBUG(std::cerr << "********** Function: " 38939a0d5c1123cfe4ddf826690b6744cc7248e3149Alkis Evlogimenos << mf_->getFunction()->getName() << '\n'); 390ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos 391ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos for (MbbIndex2MbbMap::iterator 392ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos it = mbbi2mbbMap_.begin(), itEnd = mbbi2mbbMap_.end(); 393ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos it != itEnd; ++it) { 394ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos MachineBasicBlock* mbb = it->second; 395843b160a2040b3ec4d3452678450afa11704c473Alkis Evlogimenos DEBUG(std::cerr << mbb->getBasicBlock()->getName() << ":\n"); 3966b4edbaaf9021e0434f0ce0c3724eb43ed41b770Alkis Evlogimenos 397ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos for (MachineBasicBlock::iterator mi = mbb->begin(), miEnd = mbb->end(); 398ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos mi != miEnd; ++mi) { 399ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos const TargetInstrDescriptor& tid = 400c0b9dc5be79f009d260edb5cd5e1d8346587aaa2Alkis Evlogimenos tm_->getInstrInfo().get(mi->getOpcode()); 40139a0d5c1123cfe4ddf826690b6744cc7248e3149Alkis Evlogimenos DEBUG(std::cerr << getInstructionIndex(mi) << "\t"; 40239a0d5c1123cfe4ddf826690b6744cc7248e3149Alkis Evlogimenos mi->print(std::cerr, *tm_)); 403ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos 404ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos // handle implicit defs 40519b6486d3891c8a02a301aa1b44348a420772fcfAlkis Evlogimenos for (const unsigned* id = tid.ImplicitDefs; *id; ++id) 40619b6486d3891c8a02a301aa1b44348a420772fcfAlkis Evlogimenos handleRegisterDef(mbb, mi, *id); 407ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos 408ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos // handle explicit defs 409c0b9dc5be79f009d260edb5cd5e1d8346587aaa2Alkis Evlogimenos for (int i = mi->getNumOperands() - 1; i >= 0; --i) { 410c0b9dc5be79f009d260edb5cd5e1d8346587aaa2Alkis Evlogimenos MachineOperand& mop = mi->getOperand(i); 41108cec00588ec1a8fa85b208555f006d7396ae7a4Alkis Evlogimenos // handle register defs - build intervals 41208cec00588ec1a8fa85b208555f006d7396ae7a4Alkis Evlogimenos if (mop.isRegister() && mop.isDef()) 413be766c72464116a445a02b542a450c4274bab5d0Alkis Evlogimenos handleRegisterDef(mbb, mi, mop.getReg()); 414ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos } 415ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos } 416ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos } 417ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos} 418b27ef248f579b354aab434f63c417ab1103e47e2Alkis Evlogimenos 419e88280a4224730dcf8076e0d9a20973c5761fd06Alkis Evlogimenosunsigned LiveIntervals::rep(unsigned reg) 420169cfd01964fc03828a7f2cad5d710890fbb08d8Alkis Evlogimenos{ 421e88280a4224730dcf8076e0d9a20973c5761fd06Alkis Evlogimenos Reg2RegMap::iterator it = r2rMap_.find(reg); 422e88280a4224730dcf8076e0d9a20973c5761fd06Alkis Evlogimenos if (it != r2rMap_.end()) 423e88280a4224730dcf8076e0d9a20973c5761fd06Alkis Evlogimenos return it->second = rep(it->second); 424e88280a4224730dcf8076e0d9a20973c5761fd06Alkis Evlogimenos return reg; 425169cfd01964fc03828a7f2cad5d710890fbb08d8Alkis Evlogimenos} 426169cfd01964fc03828a7f2cad5d710890fbb08d8Alkis Evlogimenos 427e88280a4224730dcf8076e0d9a20973c5761fd06Alkis Evlogimenosvoid LiveIntervals::joinIntervals() 428dd2cc65f34f9b7bfda1cd0c42becedfc361d46f8Alkis Evlogimenos{ 42939a0d5c1123cfe4ddf826690b6744cc7248e3149Alkis Evlogimenos DEBUG(std::cerr << "********** JOINING INTERVALS ***********\n"); 430dd2cc65f34f9b7bfda1cd0c42becedfc361d46f8Alkis Evlogimenos 431e88280a4224730dcf8076e0d9a20973c5761fd06Alkis Evlogimenos const TargetInstrInfo& tii = tm_->getInstrInfo(); 432dd2cc65f34f9b7bfda1cd0c42becedfc361d46f8Alkis Evlogimenos 433c0b9dc5be79f009d260edb5cd5e1d8346587aaa2Alkis Evlogimenos for (MachineFunction::iterator mbbi = mf_->begin(), mbbe = mf_->end(); 434c0b9dc5be79f009d260edb5cd5e1d8346587aaa2Alkis Evlogimenos mbbi != mbbe; ++mbbi) { 435c0b9dc5be79f009d260edb5cd5e1d8346587aaa2Alkis Evlogimenos MachineBasicBlock* mbb = mbbi; 436843b160a2040b3ec4d3452678450afa11704c473Alkis Evlogimenos DEBUG(std::cerr << mbb->getBasicBlock()->getName() << ":\n"); 437e88280a4224730dcf8076e0d9a20973c5761fd06Alkis Evlogimenos 438c0b9dc5be79f009d260edb5cd5e1d8346587aaa2Alkis Evlogimenos for (MachineBasicBlock::iterator mi = mbb->begin(), mie = mbb->end(); 439c0b9dc5be79f009d260edb5cd5e1d8346587aaa2Alkis Evlogimenos mi != mie; ++mi) { 440e88280a4224730dcf8076e0d9a20973c5761fd06Alkis Evlogimenos const TargetInstrDescriptor& tid = 441e88280a4224730dcf8076e0d9a20973c5761fd06Alkis Evlogimenos tm_->getInstrInfo().get(mi->getOpcode()); 44239a0d5c1123cfe4ddf826690b6744cc7248e3149Alkis Evlogimenos DEBUG(std::cerr << getInstructionIndex(mi) << '\t'; 443e88280a4224730dcf8076e0d9a20973c5761fd06Alkis Evlogimenos mi->print(std::cerr, *tm_);); 444e88280a4224730dcf8076e0d9a20973c5761fd06Alkis Evlogimenos 44501e74a2aab64c5901a62d9ba9e1c263759929390Alkis Evlogimenos // we only join virtual registers with allocatable 44601e74a2aab64c5901a62d9ba9e1c263759929390Alkis Evlogimenos // physical registers since we do not have liveness information 44701e74a2aab64c5901a62d9ba9e1c263759929390Alkis Evlogimenos // on not allocatable physical registers 44801e74a2aab64c5901a62d9ba9e1c263759929390Alkis Evlogimenos unsigned regA, regB; 44901e74a2aab64c5901a62d9ba9e1c263759929390Alkis Evlogimenos if (tii.isMoveInstr(*mi, regA, regB) && 45001e74a2aab64c5901a62d9ba9e1c263759929390Alkis Evlogimenos (MRegisterInfo::isVirtualRegister(regA) || 45101e74a2aab64c5901a62d9ba9e1c263759929390Alkis Evlogimenos lv_->getAllocatablePhysicalRegisters()[regA]) && 45201e74a2aab64c5901a62d9ba9e1c263759929390Alkis Evlogimenos (MRegisterInfo::isVirtualRegister(regB) || 45301e74a2aab64c5901a62d9ba9e1c263759929390Alkis Evlogimenos lv_->getAllocatablePhysicalRegisters()[regB])) { 454e88280a4224730dcf8076e0d9a20973c5761fd06Alkis Evlogimenos 455e88280a4224730dcf8076e0d9a20973c5761fd06Alkis Evlogimenos // get representative registers 45601e74a2aab64c5901a62d9ba9e1c263759929390Alkis Evlogimenos regA = rep(regA); 45701e74a2aab64c5901a62d9ba9e1c263759929390Alkis Evlogimenos regB = rep(regB); 458e88280a4224730dcf8076e0d9a20973c5761fd06Alkis Evlogimenos 459e88280a4224730dcf8076e0d9a20973c5761fd06Alkis Evlogimenos // if they are already joined we continue 46001e74a2aab64c5901a62d9ba9e1c263759929390Alkis Evlogimenos if (regA == regB) 461e88280a4224730dcf8076e0d9a20973c5761fd06Alkis Evlogimenos continue; 462e88280a4224730dcf8076e0d9a20973c5761fd06Alkis Evlogimenos 46301e74a2aab64c5901a62d9ba9e1c263759929390Alkis Evlogimenos Reg2IntervalMap::iterator r2iA = r2iMap_.find(regA); 46401e74a2aab64c5901a62d9ba9e1c263759929390Alkis Evlogimenos assert(r2iA != r2iMap_.end()); 46501e74a2aab64c5901a62d9ba9e1c263759929390Alkis Evlogimenos Reg2IntervalMap::iterator r2iB = r2iMap_.find(regB); 46601e74a2aab64c5901a62d9ba9e1c263759929390Alkis Evlogimenos assert(r2iB != r2iMap_.end()); 46701e74a2aab64c5901a62d9ba9e1c263759929390Alkis Evlogimenos 46801e74a2aab64c5901a62d9ba9e1c263759929390Alkis Evlogimenos Intervals::iterator intA = r2iA->second; 46901e74a2aab64c5901a62d9ba9e1c263759929390Alkis Evlogimenos Intervals::iterator intB = r2iB->second; 47001e74a2aab64c5901a62d9ba9e1c263759929390Alkis Evlogimenos 47101e74a2aab64c5901a62d9ba9e1c263759929390Alkis Evlogimenos // both A and B are virtual registers 47201e74a2aab64c5901a62d9ba9e1c263759929390Alkis Evlogimenos if (MRegisterInfo::isVirtualRegister(intA->reg) && 47301e74a2aab64c5901a62d9ba9e1c263759929390Alkis Evlogimenos MRegisterInfo::isVirtualRegister(intB->reg)) { 47401e74a2aab64c5901a62d9ba9e1c263759929390Alkis Evlogimenos 47501e74a2aab64c5901a62d9ba9e1c263759929390Alkis Evlogimenos const TargetRegisterClass *rcA, *rcB; 47601e74a2aab64c5901a62d9ba9e1c263759929390Alkis Evlogimenos rcA = mf_->getSSARegMap()->getRegClass(intA->reg); 47701e74a2aab64c5901a62d9ba9e1c263759929390Alkis Evlogimenos rcB = mf_->getSSARegMap()->getRegClass(intB->reg); 47801e74a2aab64c5901a62d9ba9e1c263759929390Alkis Evlogimenos assert(rcA == rcB && "registers must be of the same class"); 47901e74a2aab64c5901a62d9ba9e1c263759929390Alkis Evlogimenos 48001e74a2aab64c5901a62d9ba9e1c263759929390Alkis Evlogimenos // if their intervals do not overlap we join them 48101e74a2aab64c5901a62d9ba9e1c263759929390Alkis Evlogimenos if (!intB->overlaps(*intA)) { 48201e74a2aab64c5901a62d9ba9e1c263759929390Alkis Evlogimenos intA->join(*intB); 48301e74a2aab64c5901a62d9ba9e1c263759929390Alkis Evlogimenos r2iB->second = r2iA->second; 48401e74a2aab64c5901a62d9ba9e1c263759929390Alkis Evlogimenos r2rMap_.insert(std::make_pair(intB->reg, intA->reg)); 48501e74a2aab64c5901a62d9ba9e1c263759929390Alkis Evlogimenos intervals_.erase(intB); 48601e74a2aab64c5901a62d9ba9e1c263759929390Alkis Evlogimenos ++numJoined; 487e88280a4224730dcf8076e0d9a20973c5761fd06Alkis Evlogimenos } 488e88280a4224730dcf8076e0d9a20973c5761fd06Alkis Evlogimenos } 489b0b0ebaac09a930f7cbd302255fa23c5d8107e66Alkis Evlogimenos else if (MRegisterInfo::isPhysicalRegister(intA->reg) ^ 49001e74a2aab64c5901a62d9ba9e1c263759929390Alkis Evlogimenos MRegisterInfo::isPhysicalRegister(intB->reg)) { 49101e74a2aab64c5901a62d9ba9e1c263759929390Alkis Evlogimenos if (MRegisterInfo::isPhysicalRegister(intB->reg)) { 49201e74a2aab64c5901a62d9ba9e1c263759929390Alkis Evlogimenos std::swap(regA, regB); 49301e74a2aab64c5901a62d9ba9e1c263759929390Alkis Evlogimenos std::swap(intA, intB); 49401e74a2aab64c5901a62d9ba9e1c263759929390Alkis Evlogimenos std::swap(r2iA, r2iB); 495e88280a4224730dcf8076e0d9a20973c5761fd06Alkis Evlogimenos } 49601e74a2aab64c5901a62d9ba9e1c263759929390Alkis Evlogimenos 49701e74a2aab64c5901a62d9ba9e1c263759929390Alkis Evlogimenos assert(MRegisterInfo::isPhysicalRegister(intA->reg) && 49801e74a2aab64c5901a62d9ba9e1c263759929390Alkis Evlogimenos MRegisterInfo::isVirtualRegister(intB->reg) && 49901e74a2aab64c5901a62d9ba9e1c263759929390Alkis Evlogimenos "A must be physical and B must be virtual"); 500676cf8cb1d613d626f826a45b44658ae35f58c7cAlkis Evlogimenos 50101e74a2aab64c5901a62d9ba9e1c263759929390Alkis Evlogimenos if (!intA->overlaps(*intB) && 50201e74a2aab64c5901a62d9ba9e1c263759929390Alkis Evlogimenos !overlapsAliases(*intA, *intB)) { 50301e74a2aab64c5901a62d9ba9e1c263759929390Alkis Evlogimenos intA->join(*intB); 50401e74a2aab64c5901a62d9ba9e1c263759929390Alkis Evlogimenos r2iB->second = r2iA->second; 50501e74a2aab64c5901a62d9ba9e1c263759929390Alkis Evlogimenos r2rMap_.insert(std::make_pair(intB->reg, intA->reg)); 50601e74a2aab64c5901a62d9ba9e1c263759929390Alkis Evlogimenos intervals_.erase(intB); 50701e74a2aab64c5901a62d9ba9e1c263759929390Alkis Evlogimenos ++numJoined; 508e88280a4224730dcf8076e0d9a20973c5761fd06Alkis Evlogimenos } 509e88280a4224730dcf8076e0d9a20973c5761fd06Alkis Evlogimenos } 510e88280a4224730dcf8076e0d9a20973c5761fd06Alkis Evlogimenos } 511e88280a4224730dcf8076e0d9a20973c5761fd06Alkis Evlogimenos } 512dd2cc65f34f9b7bfda1cd0c42becedfc361d46f8Alkis Evlogimenos } 513dd2cc65f34f9b7bfda1cd0c42becedfc361d46f8Alkis Evlogimenos} 514dd2cc65f34f9b7bfda1cd0c42becedfc361d46f8Alkis Evlogimenos 51579b0c3f0b9d91bbda354a2c6f22b6578655a5143Alkis Evlogimenosbool LiveIntervals::overlapsAliases(const Interval& lhs, 51679b0c3f0b9d91bbda354a2c6f22b6578655a5143Alkis Evlogimenos const Interval& rhs) const 51779b0c3f0b9d91bbda354a2c6f22b6578655a5143Alkis Evlogimenos{ 5184f67b8664889d9e93b452a9a5f099d41d1bd235aAlkis Evlogimenos assert(MRegisterInfo::isPhysicalRegister(lhs.reg) && 51979b0c3f0b9d91bbda354a2c6f22b6578655a5143Alkis Evlogimenos "first interval must describe a physical register"); 52079b0c3f0b9d91bbda354a2c6f22b6578655a5143Alkis Evlogimenos 52179b0c3f0b9d91bbda354a2c6f22b6578655a5143Alkis Evlogimenos for (const unsigned* as = mri_->getAliasSet(lhs.reg); *as; ++as) { 52279b0c3f0b9d91bbda354a2c6f22b6578655a5143Alkis Evlogimenos Reg2IntervalMap::const_iterator r2i = r2iMap_.find(*as); 52379b0c3f0b9d91bbda354a2c6f22b6578655a5143Alkis Evlogimenos assert(r2i != r2iMap_.end() && "alias does not have interval?"); 52479b0c3f0b9d91bbda354a2c6f22b6578655a5143Alkis Evlogimenos if (rhs.overlaps(*r2i->second)) 52579b0c3f0b9d91bbda354a2c6f22b6578655a5143Alkis Evlogimenos return true; 52679b0c3f0b9d91bbda354a2c6f22b6578655a5143Alkis Evlogimenos } 52779b0c3f0b9d91bbda354a2c6f22b6578655a5143Alkis Evlogimenos 52879b0c3f0b9d91bbda354a2c6f22b6578655a5143Alkis Evlogimenos return false; 52979b0c3f0b9d91bbda354a2c6f22b6578655a5143Alkis Evlogimenos} 53079b0c3f0b9d91bbda354a2c6f22b6578655a5143Alkis Evlogimenos 531e88280a4224730dcf8076e0d9a20973c5761fd06Alkis EvlogimenosLiveIntervals::Interval::Interval(unsigned r) 532e88280a4224730dcf8076e0d9a20973c5761fd06Alkis Evlogimenos : reg(r), 5334f67b8664889d9e93b452a9a5f099d41d1bd235aAlkis Evlogimenos weight((MRegisterInfo::isPhysicalRegister(r) ? 5346ab5c15962cb16402713747f1fbe85e001318e7dAlkis Evlogimenos std::numeric_limits<float>::infinity() : 0.0F)) 535dd2cc65f34f9b7bfda1cd0c42becedfc361d46f8Alkis Evlogimenos{ 536e88280a4224730dcf8076e0d9a20973c5761fd06Alkis Evlogimenos 537dd2cc65f34f9b7bfda1cd0c42becedfc361d46f8Alkis Evlogimenos} 538dd2cc65f34f9b7bfda1cd0c42becedfc361d46f8Alkis Evlogimenos 53939a0d5c1123cfe4ddf826690b6744cc7248e3149Alkis Evlogimenosbool LiveIntervals::Interval::spilled() const 54039a0d5c1123cfe4ddf826690b6744cc7248e3149Alkis Evlogimenos{ 54139a0d5c1123cfe4ddf826690b6744cc7248e3149Alkis Evlogimenos return (weight == std::numeric_limits<float>::infinity() && 54239a0d5c1123cfe4ddf826690b6744cc7248e3149Alkis Evlogimenos MRegisterInfo::isVirtualRegister(reg)); 54339a0d5c1123cfe4ddf826690b6744cc7248e3149Alkis Evlogimenos} 54439a0d5c1123cfe4ddf826690b6744cc7248e3149Alkis Evlogimenos 5450b8cb2bc47a6bee59c8c3f46d4cc047badf7f8acAlkis Evlogimenos// An example for liveAt(): 54608cec00588ec1a8fa85b208555f006d7396ae7a4Alkis Evlogimenos// 54739a0d5c1123cfe4ddf826690b6744cc7248e3149Alkis Evlogimenos// this = [1,4), liveAt(0) will return false. The instruction defining 54839a0d5c1123cfe4ddf826690b6744cc7248e3149Alkis Evlogimenos// this spans slots [0,3]. The interval belongs to an spilled 54939a0d5c1123cfe4ddf826690b6744cc7248e3149Alkis Evlogimenos// definition of the variable it represents. This is because slot 1 is 55039a0d5c1123cfe4ddf826690b6744cc7248e3149Alkis Evlogimenos// used (def slot) and spans up to slot 3 (store slot). 55108cec00588ec1a8fa85b208555f006d7396ae7a4Alkis Evlogimenos// 552169cfd01964fc03828a7f2cad5d710890fbb08d8Alkis Evlogimenosbool LiveIntervals::Interval::liveAt(unsigned index) const 553169cfd01964fc03828a7f2cad5d710890fbb08d8Alkis Evlogimenos{ 55497017de1872e08ffcdde2fccdfd399647c1ccc4aAlkis Evlogimenos Range dummy(index, index+1); 55597017de1872e08ffcdde2fccdfd399647c1ccc4aAlkis Evlogimenos Ranges::const_iterator r = std::upper_bound(ranges.begin(), 55697017de1872e08ffcdde2fccdfd399647c1ccc4aAlkis Evlogimenos ranges.end(), 55797017de1872e08ffcdde2fccdfd399647c1ccc4aAlkis Evlogimenos dummy); 55897017de1872e08ffcdde2fccdfd399647c1ccc4aAlkis Evlogimenos if (r == ranges.begin()) 55997017de1872e08ffcdde2fccdfd399647c1ccc4aAlkis Evlogimenos return false; 56097017de1872e08ffcdde2fccdfd399647c1ccc4aAlkis Evlogimenos 56197017de1872e08ffcdde2fccdfd399647c1ccc4aAlkis Evlogimenos --r; 5620b8cb2bc47a6bee59c8c3f46d4cc047badf7f8acAlkis Evlogimenos return index >= r->first && index < r->second; 563169cfd01964fc03828a7f2cad5d710890fbb08d8Alkis Evlogimenos} 564169cfd01964fc03828a7f2cad5d710890fbb08d8Alkis Evlogimenos 5650b8cb2bc47a6bee59c8c3f46d4cc047badf7f8acAlkis Evlogimenos// An example for overlaps(): 56608cec00588ec1a8fa85b208555f006d7396ae7a4Alkis Evlogimenos// 56708cec00588ec1a8fa85b208555f006d7396ae7a4Alkis Evlogimenos// 0: A = ... 56839a0d5c1123cfe4ddf826690b6744cc7248e3149Alkis Evlogimenos// 4: B = ... 56939a0d5c1123cfe4ddf826690b6744cc7248e3149Alkis Evlogimenos// 8: C = A + B ;; last use of A 57008cec00588ec1a8fa85b208555f006d7396ae7a4Alkis Evlogimenos// 57108cec00588ec1a8fa85b208555f006d7396ae7a4Alkis Evlogimenos// The live intervals should look like: 57208cec00588ec1a8fa85b208555f006d7396ae7a4Alkis Evlogimenos// 57339a0d5c1123cfe4ddf826690b6744cc7248e3149Alkis Evlogimenos// A = [3, 11) 57439a0d5c1123cfe4ddf826690b6744cc7248e3149Alkis Evlogimenos// B = [7, x) 57539a0d5c1123cfe4ddf826690b6744cc7248e3149Alkis Evlogimenos// C = [11, y) 57608cec00588ec1a8fa85b208555f006d7396ae7a4Alkis Evlogimenos// 57708cec00588ec1a8fa85b208555f006d7396ae7a4Alkis Evlogimenos// A->overlaps(C) should return false since we want to be able to join 57808cec00588ec1a8fa85b208555f006d7396ae7a4Alkis Evlogimenos// A and C. 579169cfd01964fc03828a7f2cad5d710890fbb08d8Alkis Evlogimenosbool LiveIntervals::Interval::overlaps(const Interval& other) const 580169cfd01964fc03828a7f2cad5d710890fbb08d8Alkis Evlogimenos{ 58180b378cf7c3dce77029dc3118e1f63bc6d389da1Alkis Evlogimenos Ranges::const_iterator i = ranges.begin(); 58297017de1872e08ffcdde2fccdfd399647c1ccc4aAlkis Evlogimenos Ranges::const_iterator ie = ranges.end(); 58380b378cf7c3dce77029dc3118e1f63bc6d389da1Alkis Evlogimenos Ranges::const_iterator j = other.ranges.begin(); 58497017de1872e08ffcdde2fccdfd399647c1ccc4aAlkis Evlogimenos Ranges::const_iterator je = other.ranges.end(); 58597017de1872e08ffcdde2fccdfd399647c1ccc4aAlkis Evlogimenos if (i->first < j->first) { 58697017de1872e08ffcdde2fccdfd399647c1ccc4aAlkis Evlogimenos i = std::upper_bound(i, ie, *j); 58797017de1872e08ffcdde2fccdfd399647c1ccc4aAlkis Evlogimenos if (i != ranges.begin()) --i; 58897017de1872e08ffcdde2fccdfd399647c1ccc4aAlkis Evlogimenos } 58997017de1872e08ffcdde2fccdfd399647c1ccc4aAlkis Evlogimenos else if (j->first < i->first) { 59097017de1872e08ffcdde2fccdfd399647c1ccc4aAlkis Evlogimenos j = std::upper_bound(j, je, *i); 59197017de1872e08ffcdde2fccdfd399647c1ccc4aAlkis Evlogimenos if (j != other.ranges.begin()) --j; 59297017de1872e08ffcdde2fccdfd399647c1ccc4aAlkis Evlogimenos } 59397017de1872e08ffcdde2fccdfd399647c1ccc4aAlkis Evlogimenos 59497017de1872e08ffcdde2fccdfd399647c1ccc4aAlkis Evlogimenos while (i != ie && j != je) { 59597017de1872e08ffcdde2fccdfd399647c1ccc4aAlkis Evlogimenos if (i->first == j->first) { 59697017de1872e08ffcdde2fccdfd399647c1ccc4aAlkis Evlogimenos return true; 59797017de1872e08ffcdde2fccdfd399647c1ccc4aAlkis Evlogimenos } 59897017de1872e08ffcdde2fccdfd399647c1ccc4aAlkis Evlogimenos else { 59997017de1872e08ffcdde2fccdfd399647c1ccc4aAlkis Evlogimenos if (i->first > j->first) { 60097017de1872e08ffcdde2fccdfd399647c1ccc4aAlkis Evlogimenos swap(i, j); 60197017de1872e08ffcdde2fccdfd399647c1ccc4aAlkis Evlogimenos swap(ie, je); 60297017de1872e08ffcdde2fccdfd399647c1ccc4aAlkis Evlogimenos } 60397017de1872e08ffcdde2fccdfd399647c1ccc4aAlkis Evlogimenos assert(i->first < j->first); 60480b378cf7c3dce77029dc3118e1f63bc6d389da1Alkis Evlogimenos 6050b8cb2bc47a6bee59c8c3f46d4cc047badf7f8acAlkis Evlogimenos if (i->second > j->first) { 60680b378cf7c3dce77029dc3118e1f63bc6d389da1Alkis Evlogimenos return true; 60780b378cf7c3dce77029dc3118e1f63bc6d389da1Alkis Evlogimenos } 60880b378cf7c3dce77029dc3118e1f63bc6d389da1Alkis Evlogimenos else { 60980b378cf7c3dce77029dc3118e1f63bc6d389da1Alkis Evlogimenos ++i; 61080b378cf7c3dce77029dc3118e1f63bc6d389da1Alkis Evlogimenos } 61180b378cf7c3dce77029dc3118e1f63bc6d389da1Alkis Evlogimenos } 612169cfd01964fc03828a7f2cad5d710890fbb08d8Alkis Evlogimenos } 613169cfd01964fc03828a7f2cad5d710890fbb08d8Alkis Evlogimenos 614169cfd01964fc03828a7f2cad5d710890fbb08d8Alkis Evlogimenos return false; 615169cfd01964fc03828a7f2cad5d710890fbb08d8Alkis Evlogimenos} 616169cfd01964fc03828a7f2cad5d710890fbb08d8Alkis Evlogimenos 617e88280a4224730dcf8076e0d9a20973c5761fd06Alkis Evlogimenosvoid LiveIntervals::Interval::addRange(unsigned start, unsigned end) 618e88280a4224730dcf8076e0d9a20973c5761fd06Alkis Evlogimenos{ 61908cec00588ec1a8fa85b208555f006d7396ae7a4Alkis Evlogimenos assert(start < end && "Invalid range to add!"); 62039a0d5c1123cfe4ddf826690b6744cc7248e3149Alkis Evlogimenos DEBUG(std::cerr << " +[" << start << ',' << end << ")"); 621e88280a4224730dcf8076e0d9a20973c5761fd06Alkis Evlogimenos //assert(start < end && "invalid range?"); 622e88280a4224730dcf8076e0d9a20973c5761fd06Alkis Evlogimenos Range range = std::make_pair(start, end); 623e88280a4224730dcf8076e0d9a20973c5761fd06Alkis Evlogimenos Ranges::iterator it = 624e88280a4224730dcf8076e0d9a20973c5761fd06Alkis Evlogimenos ranges.insert(std::upper_bound(ranges.begin(), ranges.end(), range), 625e88280a4224730dcf8076e0d9a20973c5761fd06Alkis Evlogimenos range); 626e88280a4224730dcf8076e0d9a20973c5761fd06Alkis Evlogimenos 627e88280a4224730dcf8076e0d9a20973c5761fd06Alkis Evlogimenos it = mergeRangesForward(it); 628e88280a4224730dcf8076e0d9a20973c5761fd06Alkis Evlogimenos it = mergeRangesBackward(it); 629e88280a4224730dcf8076e0d9a20973c5761fd06Alkis Evlogimenos} 630e88280a4224730dcf8076e0d9a20973c5761fd06Alkis Evlogimenos 631e88280a4224730dcf8076e0d9a20973c5761fd06Alkis Evlogimenosvoid LiveIntervals::Interval::join(const LiveIntervals::Interval& other) 632e88280a4224730dcf8076e0d9a20973c5761fd06Alkis Evlogimenos{ 63339a0d5c1123cfe4ddf826690b6744cc7248e3149Alkis Evlogimenos DEBUG(std::cerr << "\t\tjoining " << *this << " with " << other << '\n'); 634e88280a4224730dcf8076e0d9a20973c5761fd06Alkis Evlogimenos Ranges::iterator cur = ranges.begin(); 635e88280a4224730dcf8076e0d9a20973c5761fd06Alkis Evlogimenos 636e88280a4224730dcf8076e0d9a20973c5761fd06Alkis Evlogimenos for (Ranges::const_iterator i = other.ranges.begin(), 637e88280a4224730dcf8076e0d9a20973c5761fd06Alkis Evlogimenos e = other.ranges.end(); i != e; ++i) { 638e88280a4224730dcf8076e0d9a20973c5761fd06Alkis Evlogimenos cur = ranges.insert(std::upper_bound(cur, ranges.end(), *i), *i); 639e88280a4224730dcf8076e0d9a20973c5761fd06Alkis Evlogimenos cur = mergeRangesForward(cur); 640e88280a4224730dcf8076e0d9a20973c5761fd06Alkis Evlogimenos cur = mergeRangesBackward(cur); 641e88280a4224730dcf8076e0d9a20973c5761fd06Alkis Evlogimenos } 642cea44711203cfcb3b18528401ac1ad170677ebfeAlkis Evlogimenos weight += other.weight; 643cea44711203cfcb3b18528401ac1ad170677ebfeAlkis Evlogimenos ++numJoins; 644e88280a4224730dcf8076e0d9a20973c5761fd06Alkis Evlogimenos} 645e88280a4224730dcf8076e0d9a20973c5761fd06Alkis Evlogimenos 646e88280a4224730dcf8076e0d9a20973c5761fd06Alkis EvlogimenosLiveIntervals::Interval::Ranges::iterator 647e88280a4224730dcf8076e0d9a20973c5761fd06Alkis EvlogimenosLiveIntervals::Interval::mergeRangesForward(Ranges::iterator it) 648e88280a4224730dcf8076e0d9a20973c5761fd06Alkis Evlogimenos{ 64923c114fd3bec342ac1a2a45801b892d6b4517afcAlkis Evlogimenos for (Ranges::iterator n = next(it); 65023c114fd3bec342ac1a2a45801b892d6b4517afcAlkis Evlogimenos n != ranges.end() && ((it->second & 1) + it->second) >= n->first; ) { 65123c114fd3bec342ac1a2a45801b892d6b4517afcAlkis Evlogimenos it->second = std::max(it->second, n->second); 65223c114fd3bec342ac1a2a45801b892d6b4517afcAlkis Evlogimenos n = ranges.erase(n); 653e88280a4224730dcf8076e0d9a20973c5761fd06Alkis Evlogimenos } 654e88280a4224730dcf8076e0d9a20973c5761fd06Alkis Evlogimenos return it; 655e88280a4224730dcf8076e0d9a20973c5761fd06Alkis Evlogimenos} 656e88280a4224730dcf8076e0d9a20973c5761fd06Alkis Evlogimenos 657e88280a4224730dcf8076e0d9a20973c5761fd06Alkis EvlogimenosLiveIntervals::Interval::Ranges::iterator 658e88280a4224730dcf8076e0d9a20973c5761fd06Alkis EvlogimenosLiveIntervals::Interval::mergeRangesBackward(Ranges::iterator it) 659e88280a4224730dcf8076e0d9a20973c5761fd06Alkis Evlogimenos{ 66008cec00588ec1a8fa85b208555f006d7396ae7a4Alkis Evlogimenos while (it != ranges.begin()) { 66123c114fd3bec342ac1a2a45801b892d6b4517afcAlkis Evlogimenos Ranges::iterator p = prior(it); 66223c114fd3bec342ac1a2a45801b892d6b4517afcAlkis Evlogimenos if (it->first > ((p->second & 1) + p->second)) break; 66308cec00588ec1a8fa85b208555f006d7396ae7a4Alkis Evlogimenos 66423c114fd3bec342ac1a2a45801b892d6b4517afcAlkis Evlogimenos it->first = std::min(it->first, p->first); 66523c114fd3bec342ac1a2a45801b892d6b4517afcAlkis Evlogimenos it->second = std::max(it->second, p->second); 66623c114fd3bec342ac1a2a45801b892d6b4517afcAlkis Evlogimenos it = ranges.erase(p); 667e88280a4224730dcf8076e0d9a20973c5761fd06Alkis Evlogimenos } 668e88280a4224730dcf8076e0d9a20973c5761fd06Alkis Evlogimenos 669e88280a4224730dcf8076e0d9a20973c5761fd06Alkis Evlogimenos return it; 670e88280a4224730dcf8076e0d9a20973c5761fd06Alkis Evlogimenos} 671e88280a4224730dcf8076e0d9a20973c5761fd06Alkis Evlogimenos 672b27ef248f579b354aab434f63c417ab1103e47e2Alkis Evlogimenosstd::ostream& llvm::operator<<(std::ostream& os, 673b27ef248f579b354aab434f63c417ab1103e47e2Alkis Evlogimenos const LiveIntervals::Interval& li) 674b27ef248f579b354aab434f63c417ab1103e47e2Alkis Evlogimenos{ 675169cfd01964fc03828a7f2cad5d710890fbb08d8Alkis Evlogimenos os << "%reg" << li.reg << ',' << li.weight << " = "; 67639a0d5c1123cfe4ddf826690b6744cc7248e3149Alkis Evlogimenos if (li.empty()) 67739a0d5c1123cfe4ddf826690b6744cc7248e3149Alkis Evlogimenos return os << "EMPTY"; 678b27ef248f579b354aab434f63c417ab1103e47e2Alkis Evlogimenos for (LiveIntervals::Interval::Ranges::const_iterator 679b27ef248f579b354aab434f63c417ab1103e47e2Alkis Evlogimenos i = li.ranges.begin(), e = li.ranges.end(); i != e; ++i) { 68063841bc85d15ca0ce1b3208084f4262f3d33ef21Alkis Evlogimenos os << "[" << i->first << "," << i->second << ")"; 681b27ef248f579b354aab434f63c417ab1103e47e2Alkis Evlogimenos } 682b27ef248f579b354aab434f63c417ab1103e47e2Alkis Evlogimenos return os; 683b27ef248f579b354aab434f63c417ab1103e47e2Alkis Evlogimenos} 684