LiveIntervalAnalysis.cpp revision 63841bc85d15ca0ce1b3208084f4262f3d33ef21
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" 20ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos#include "llvm/Function.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/MachineFunctionPass.h" 25ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos#include "llvm/CodeGen/MachineInstr.h" 26ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos#include "llvm/CodeGen/Passes.h" 27ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos#include "llvm/CodeGen/SSARegMap.h" 28ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos#include "llvm/Target/MRegisterInfo.h" 29ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos#include "llvm/Target/TargetInstrInfo.h" 30ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos#include "llvm/Target/TargetMachine.h" 31ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos#include "llvm/Target/TargetRegInfo.h" 32ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos#include "llvm/Support/CFG.h" 33ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos#include "Support/Debug.h" 34ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos#include "Support/DepthFirstIterator.h" 35ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos#include "Support/Statistic.h" 366b4edbaaf9021e0434f0ce0c3724eb43ed41b770Alkis Evlogimenos#include <cmath> 37ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos#include <iostream> 386b4edbaaf9021e0434f0ce0c3724eb43ed41b770Alkis Evlogimenos#include <limits> 39ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos 40ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenosusing namespace llvm; 41ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos 42ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenosnamespace { 43ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos RegisterAnalysis<LiveIntervals> X("liveintervals", 44ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos "Live Interval Analysis"); 45ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos 46ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos Statistic<> numIntervals("liveintervals", "Number of intervals"); 47ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos}; 48ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos 49ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenosvoid LiveIntervals::getAnalysisUsage(AnalysisUsage &AU) const 50ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos{ 51f6f91bf6680668990ff3804b14cf05beedc56ec4Alkis Evlogimenos AU.addPreserved<LiveVariables>(); 52ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos AU.addRequired<LiveVariables>(); 53f6f91bf6680668990ff3804b14cf05beedc56ec4Alkis Evlogimenos AU.addPreservedID(PHIEliminationID); 54ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos AU.addRequiredID(PHIEliminationID); 554c080863de86448d905beab27686da823b6d44c1Alkis Evlogimenos AU.addRequiredID(TwoAddressInstructionPassID); 566b4edbaaf9021e0434f0ce0c3724eb43ed41b770Alkis Evlogimenos AU.addRequired<LoopInfo>(); 57ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos MachineFunctionPass::getAnalysisUsage(AU); 58ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos} 59ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos 60ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos/// runOnMachineFunction - Register allocate the whole function 61ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos/// 62ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenosbool LiveIntervals::runOnMachineFunction(MachineFunction &fn) { 63ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos DEBUG(std::cerr << "Machine Function\n"); 64ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos mf_ = &fn; 65ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos tm_ = &fn.getTarget(); 66ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos mri_ = tm_->getRegisterInfo(); 67ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos lv_ = &getAnalysis<LiveVariables>(); 68ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos allocatableRegisters_.clear(); 69ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos mbbi2mbbMap_.clear(); 70ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos mi2iMap_.clear(); 71ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos r2iMap_.clear(); 72ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos r2iMap_.clear(); 73ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos intervals_.clear(); 74ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos 75ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos // mark allocatable registers 76ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos allocatableRegisters_.resize(MRegisterInfo::FirstVirtualRegister); 77ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos // Loop over all of the register classes... 78ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos for (MRegisterInfo::regclass_iterator 79ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos rci = mri_->regclass_begin(), rce = mri_->regclass_end(); 80ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos rci != rce; ++rci) { 81ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos // Loop over all of the allocatable registers in the function... 82ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos for (TargetRegisterClass::iterator 83ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos i = (*rci)->allocation_order_begin(*mf_), 84ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos e = (*rci)->allocation_order_end(*mf_); i != e; ++i) { 85ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos allocatableRegisters_[*i] = true; // The reg is allocatable! 86ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos } 87ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos } 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 = 94ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis 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) { 101ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos inserted = mi2iMap_.insert(std::make_pair(*mi, miIndex)).second; 102ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos assert(inserted && "multiple MachineInstr -> index mappings"); 103ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos ++miIndex; 104ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos } 105ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos } 106ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos 107ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos computeIntervals(); 108ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos 1097a40eaaceec0af76d5b97610f3d4e7a47a19d245Alkis Evlogimenos // compute spill weights 1107a40eaaceec0af76d5b97610f3d4e7a47a19d245Alkis Evlogimenos const LoopInfo& loopInfo = getAnalysis<LoopInfo>(); 11126bfc08b80c904c71487ac1ab49a8b3a15a8d3e9Alkis Evlogimenos const TargetInstrInfo& tii = tm_->getInstrInfo(); 1127a40eaaceec0af76d5b97610f3d4e7a47a19d245Alkis Evlogimenos 1137a40eaaceec0af76d5b97610f3d4e7a47a19d245Alkis Evlogimenos for (MbbIndex2MbbMap::iterator 1147a40eaaceec0af76d5b97610f3d4e7a47a19d245Alkis Evlogimenos it = mbbi2mbbMap_.begin(), itEnd = mbbi2mbbMap_.end(); 1157a40eaaceec0af76d5b97610f3d4e7a47a19d245Alkis Evlogimenos it != itEnd; ++it) { 1167a40eaaceec0af76d5b97610f3d4e7a47a19d245Alkis Evlogimenos MachineBasicBlock* mbb = it->second; 1177a40eaaceec0af76d5b97610f3d4e7a47a19d245Alkis Evlogimenos 1187a40eaaceec0af76d5b97610f3d4e7a47a19d245Alkis Evlogimenos unsigned loopDepth = loopInfo.getLoopDepth(mbb->getBasicBlock()); 1197a40eaaceec0af76d5b97610f3d4e7a47a19d245Alkis Evlogimenos 1207a40eaaceec0af76d5b97610f3d4e7a47a19d245Alkis Evlogimenos for (MachineBasicBlock::iterator mi = mbb->begin(), miEnd = mbb->end(); 1217a40eaaceec0af76d5b97610f3d4e7a47a19d245Alkis Evlogimenos mi != miEnd; ++mi) { 1227a40eaaceec0af76d5b97610f3d4e7a47a19d245Alkis Evlogimenos MachineInstr* instr = *mi; 1237a40eaaceec0af76d5b97610f3d4e7a47a19d245Alkis Evlogimenos for (int i = instr->getNumOperands() - 1; i >= 0; --i) { 1247a40eaaceec0af76d5b97610f3d4e7a47a19d245Alkis Evlogimenos MachineOperand& mop = instr->getOperand(i); 1257a40eaaceec0af76d5b97610f3d4e7a47a19d245Alkis Evlogimenos 1267a40eaaceec0af76d5b97610f3d4e7a47a19d245Alkis Evlogimenos if (!mop.isVirtualRegister()) 1277a40eaaceec0af76d5b97610f3d4e7a47a19d245Alkis Evlogimenos continue; 1287a40eaaceec0af76d5b97610f3d4e7a47a19d245Alkis Evlogimenos 1297a40eaaceec0af76d5b97610f3d4e7a47a19d245Alkis Evlogimenos unsigned reg = mop.getAllocatedRegNum(); 1307a40eaaceec0af76d5b97610f3d4e7a47a19d245Alkis Evlogimenos Reg2IntervalMap::iterator r2iit = r2iMap_.find(reg); 1317a40eaaceec0af76d5b97610f3d4e7a47a19d245Alkis Evlogimenos assert(r2iit != r2iMap_.end()); 1327a40eaaceec0af76d5b97610f3d4e7a47a19d245Alkis Evlogimenos intervals_[r2iit->second].weight += pow(10.0F, loopDepth); 1337a40eaaceec0af76d5b97610f3d4e7a47a19d245Alkis Evlogimenos } 1347a40eaaceec0af76d5b97610f3d4e7a47a19d245Alkis Evlogimenos } 1357a40eaaceec0af76d5b97610f3d4e7a47a19d245Alkis Evlogimenos } 1367a40eaaceec0af76d5b97610f3d4e7a47a19d245Alkis Evlogimenos 137ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos return true; 138ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos} 139ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos 140ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenosvoid LiveIntervals::printRegName(unsigned reg) const 141ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos{ 142ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos if (reg < MRegisterInfo::FirstVirtualRegister) 143ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos std::cerr << mri_->getName(reg); 144ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos else 145ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos std::cerr << '%' << reg; 146ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos} 147ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos 148ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenosvoid LiveIntervals::handleVirtualRegisterDef(MachineBasicBlock* mbb, 149ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos MachineBasicBlock::iterator mi, 150ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos unsigned reg) 151ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos{ 152ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos DEBUG(std::cerr << "\t\t\tregister: ";printRegName(reg); std::cerr << '\n'); 153ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos 154ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos unsigned instrIndex = getInstructionIndex(*mi); 155ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos 156ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos LiveVariables::VarInfo& vi = lv_->getVarInfo(reg); 157ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos 158dd2cc65f34f9b7bfda1cd0c42becedfc361d46f8Alkis Evlogimenos Interval* interval = 0; 159ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos Reg2IntervalMap::iterator r2iit = r2iMap_.find(reg); 160dd2cc65f34f9b7bfda1cd0c42becedfc361d46f8Alkis Evlogimenos if (r2iit == r2iMap_.end()) { 161ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos // add new interval 162ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos intervals_.push_back(Interval(reg)); 163ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos // update interval index for this register 164ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos r2iMap_[reg] = intervals_.size() - 1; 165dd2cc65f34f9b7bfda1cd0c42becedfc361d46f8Alkis Evlogimenos interval = &intervals_.back(); 166dd2cc65f34f9b7bfda1cd0c42becedfc361d46f8Alkis Evlogimenos } 167dd2cc65f34f9b7bfda1cd0c42becedfc361d46f8Alkis Evlogimenos else { 168dd2cc65f34f9b7bfda1cd0c42becedfc361d46f8Alkis Evlogimenos interval = &intervals_[r2iit->second]; 169dd2cc65f34f9b7bfda1cd0c42becedfc361d46f8Alkis Evlogimenos } 170ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos 171dd2cc65f34f9b7bfda1cd0c42becedfc361d46f8Alkis Evlogimenos for (MbbIndex2MbbMap::iterator 172dd2cc65f34f9b7bfda1cd0c42becedfc361d46f8Alkis Evlogimenos it = mbbi2mbbMap_.begin(), itEnd = mbbi2mbbMap_.end(); 173dd2cc65f34f9b7bfda1cd0c42becedfc361d46f8Alkis Evlogimenos it != itEnd; ++it) { 174dd2cc65f34f9b7bfda1cd0c42becedfc361d46f8Alkis Evlogimenos unsigned liveBlockIndex = it->first; 175dd2cc65f34f9b7bfda1cd0c42becedfc361d46f8Alkis Evlogimenos MachineBasicBlock* liveBlock = it->second; 176dd2cc65f34f9b7bfda1cd0c42becedfc361d46f8Alkis Evlogimenos if (liveBlockIndex < vi.AliveBlocks.size() && 177056063e2645d86b11a441abfff4bfd96dc4edf8cAlkis Evlogimenos vi.AliveBlocks[liveBlockIndex] && 178056063e2645d86b11a441abfff4bfd96dc4edf8cAlkis Evlogimenos !liveBlock->empty()) { 179dd2cc65f34f9b7bfda1cd0c42becedfc361d46f8Alkis Evlogimenos unsigned start = getInstructionIndex(liveBlock->front()); 180dd2cc65f34f9b7bfda1cd0c42becedfc361d46f8Alkis Evlogimenos unsigned end = getInstructionIndex(liveBlock->back()) + 1; 181dd2cc65f34f9b7bfda1cd0c42becedfc361d46f8Alkis Evlogimenos interval->addRange(start, end); 182ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos } 183dd2cc65f34f9b7bfda1cd0c42becedfc361d46f8Alkis Evlogimenos } 184ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos 185dd2cc65f34f9b7bfda1cd0c42becedfc361d46f8Alkis Evlogimenos bool killedInDefiningBasicBlock = false; 186dd2cc65f34f9b7bfda1cd0c42becedfc361d46f8Alkis Evlogimenos for (int i = 0, e = vi.Kills.size(); i != e; ++i) { 187dd2cc65f34f9b7bfda1cd0c42becedfc361d46f8Alkis Evlogimenos MachineBasicBlock* killerBlock = vi.Kills[i].first; 188dd2cc65f34f9b7bfda1cd0c42becedfc361d46f8Alkis Evlogimenos MachineInstr* killerInstr = vi.Kills[i].second; 189dd2cc65f34f9b7bfda1cd0c42becedfc361d46f8Alkis Evlogimenos unsigned start = (mbb == killerBlock ? 190dd2cc65f34f9b7bfda1cd0c42becedfc361d46f8Alkis Evlogimenos instrIndex : 191dd2cc65f34f9b7bfda1cd0c42becedfc361d46f8Alkis Evlogimenos getInstructionIndex(killerBlock->front())); 192dd2cc65f34f9b7bfda1cd0c42becedfc361d46f8Alkis Evlogimenos unsigned end = getInstructionIndex(killerInstr) + 1; 19343f692f90f6b27304570e1b1807542dff4b8e847Alkis Evlogimenos if (start < end) { 19443f692f90f6b27304570e1b1807542dff4b8e847Alkis Evlogimenos killedInDefiningBasicBlock |= mbb == killerBlock; 19543f692f90f6b27304570e1b1807542dff4b8e847Alkis Evlogimenos interval->addRange(start, end); 19643f692f90f6b27304570e1b1807542dff4b8e847Alkis Evlogimenos } 197dd2cc65f34f9b7bfda1cd0c42becedfc361d46f8Alkis Evlogimenos } 198ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos 199dd2cc65f34f9b7bfda1cd0c42becedfc361d46f8Alkis Evlogimenos if (!killedInDefiningBasicBlock) { 200dd2cc65f34f9b7bfda1cd0c42becedfc361d46f8Alkis Evlogimenos unsigned end = getInstructionIndex(mbb->back()) + 1; 201dd2cc65f34f9b7bfda1cd0c42becedfc361d46f8Alkis Evlogimenos interval->addRange(instrIndex, end); 202ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos } 203ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos} 204ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos 205ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenosvoid LiveIntervals::handlePhysicalRegisterDef(MachineBasicBlock* mbb, 206ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos MachineBasicBlock::iterator mi, 207ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos unsigned reg) 208ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos{ 209ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos DEBUG(std::cerr << "\t\t\tregister: ";printRegName(reg); std::cerr << '\n'); 2104c214d2bf0da92a7973bb7902c0d6d055b1fa991Alkis Evlogimenos if (!lv_->getAllocatablePhysicalRegisters()[reg]) { 2114c214d2bf0da92a7973bb7902c0d6d055b1fa991Alkis Evlogimenos DEBUG(std::cerr << "\t\t\t\tnon allocatable register: ignoring\n"); 2124c214d2bf0da92a7973bb7902c0d6d055b1fa991Alkis Evlogimenos return; 2134c214d2bf0da92a7973bb7902c0d6d055b1fa991Alkis Evlogimenos } 214ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos 215ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos unsigned start = getInstructionIndex(*mi); 216ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos unsigned end = start; 217ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos 218ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos for (MachineBasicBlock::iterator e = mbb->end(); mi != e; ++mi) { 219ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos for (LiveVariables::killed_iterator 220ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos ki = lv_->dead_begin(*mi), 221ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos ke = lv_->dead_end(*mi); 222ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos ki != ke; ++ki) { 223ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos if (reg == ki->second) { 224ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos end = getInstructionIndex(ki->first) + 1; 225ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos goto exit; 226ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos } 227ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos } 228ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos 229ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos for (LiveVariables::killed_iterator 230ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos ki = lv_->killed_begin(*mi), 231ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos ke = lv_->killed_end(*mi); 232ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos ki != ke; ++ki) { 233ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos if (reg == ki->second) { 234ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos end = getInstructionIndex(ki->first) + 1; 235ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos goto exit; 236ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos } 237ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos } 238ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos } 239ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenosexit: 240ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos assert(start < end && "did not find end of interval?"); 241ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos 242ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos Reg2IntervalMap::iterator r2iit = r2iMap_.find(reg); 243ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos if (r2iit != r2iMap_.end()) { 244ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos unsigned ii = r2iit->second; 245ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos Interval& interval = intervals_[ii]; 246ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos interval.addRange(start, end); 247ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos } 248ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos else { 249ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos intervals_.push_back(Interval(reg)); 250ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos Interval& interval = intervals_.back(); 251ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos // update interval index for this register 252ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos r2iMap_[reg] = intervals_.size() - 1; 253ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos interval.addRange(start, end); 254ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos } 255ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos} 256ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos 257ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenosvoid LiveIntervals::handleRegisterDef(MachineBasicBlock* mbb, 258ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos MachineBasicBlock::iterator mi, 259ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos unsigned reg) 260ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos{ 261ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos if (reg < MRegisterInfo::FirstVirtualRegister) { 262ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos if (allocatableRegisters_[reg]) { 263ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos handlePhysicalRegisterDef(mbb, mi, reg); 26419b6486d3891c8a02a301aa1b44348a420772fcfAlkis Evlogimenos for (const unsigned* as = mri_->getAliasSet(reg); *as; ++as) 26519b6486d3891c8a02a301aa1b44348a420772fcfAlkis Evlogimenos handlePhysicalRegisterDef(mbb, mi, *as); 266ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos } 267ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos } 268ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos else { 269ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos handleVirtualRegisterDef(mbb, mi, reg); 270ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos } 271ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos} 272ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos 273ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenosunsigned LiveIntervals::getInstructionIndex(MachineInstr* instr) const 274ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos{ 275ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos assert(mi2iMap_.find(instr) != mi2iMap_.end() && 276ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos "instruction not assigned a number"); 277ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos return mi2iMap_.find(instr)->second; 278ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos} 279ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos 280ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos/// computeIntervals - computes the live intervals for virtual 281ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos/// registers. for some ordering of the machine instructions [1,N] a 282ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos/// live interval is an interval [i, j] where 1 <= i <= j <= N for 283ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos/// which a variable is live 284ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenosvoid LiveIntervals::computeIntervals() 285ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos{ 286ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos DEBUG(std::cerr << "computing live intervals:\n"); 287ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos 288ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos for (MbbIndex2MbbMap::iterator 289ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos it = mbbi2mbbMap_.begin(), itEnd = mbbi2mbbMap_.end(); 290ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos it != itEnd; ++it) { 291ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos MachineBasicBlock* mbb = it->second; 292ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos DEBUG(std::cerr << "machine basic block: " 293ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos << mbb->getBasicBlock()->getName() << "\n"); 2946b4edbaaf9021e0434f0ce0c3724eb43ed41b770Alkis Evlogimenos 295ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos for (MachineBasicBlock::iterator mi = mbb->begin(), miEnd = mbb->end(); 296ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos mi != miEnd; ++mi) { 297ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos MachineInstr* instr = *mi; 298ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos const TargetInstrDescriptor& tid = 299ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos tm_->getInstrInfo().get(instr->getOpcode()); 300ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos DEBUG(std::cerr << "\t\tinstruction[" 301ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos << getInstructionIndex(instr) << "]: "; 302ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos instr->print(std::cerr, *tm_);); 303ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos 304ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos // handle implicit defs 30519b6486d3891c8a02a301aa1b44348a420772fcfAlkis Evlogimenos for (const unsigned* id = tid.ImplicitDefs; *id; ++id) 30619b6486d3891c8a02a301aa1b44348a420772fcfAlkis Evlogimenos handleRegisterDef(mbb, mi, *id); 307ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos 308ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos // handle explicit defs 309ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos for (int i = instr->getNumOperands() - 1; i >= 0; --i) { 310ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos MachineOperand& mop = instr->getOperand(i); 311ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos 3129435eda6993944e74419d2f586fdd25635293760Alkis Evlogimenos if (!mop.isRegister()) 313ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos continue; 314ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos 315169cfd01964fc03828a7f2cad5d710890fbb08d8Alkis Evlogimenos // handle defs - build intervals 31619b6486d3891c8a02a301aa1b44348a420772fcfAlkis Evlogimenos if (mop.isDef()) 31719b6486d3891c8a02a301aa1b44348a420772fcfAlkis Evlogimenos handleRegisterDef(mbb, mi, mop.getAllocatedRegNum()); 318ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos } 319ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos } 320ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos } 321ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos 32291ceae6d2060367a5212b15b26faa804ea0448a5Alkis Evlogimenos std::sort(intervals_.begin(), intervals_.end(), StartPointComp()); 323ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos DEBUG(std::copy(intervals_.begin(), intervals_.end(), 324ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos std::ostream_iterator<Interval>(std::cerr, "\n"))); 325ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos} 326b27ef248f579b354aab434f63c417ab1103e47e2Alkis Evlogimenos 327169cfd01964fc03828a7f2cad5d710890fbb08d8Alkis EvlogimenosLiveIntervals::Interval::Interval(unsigned r) 32826bfc08b80c904c71487ac1ab49a8b3a15a8d3e9Alkis Evlogimenos : reg(r), hint(0), 329169cfd01964fc03828a7f2cad5d710890fbb08d8Alkis Evlogimenos weight((r < MRegisterInfo::FirstVirtualRegister ? 3306b4edbaaf9021e0434f0ce0c3724eb43ed41b770Alkis Evlogimenos std::numeric_limits<float>::max() : 0.0F)) 331169cfd01964fc03828a7f2cad5d710890fbb08d8Alkis Evlogimenos{ 332169cfd01964fc03828a7f2cad5d710890fbb08d8Alkis Evlogimenos 333169cfd01964fc03828a7f2cad5d710890fbb08d8Alkis Evlogimenos} 334169cfd01964fc03828a7f2cad5d710890fbb08d8Alkis Evlogimenos 335dd2cc65f34f9b7bfda1cd0c42becedfc361d46f8Alkis Evlogimenosvoid LiveIntervals::Interval::addRange(unsigned start, unsigned end) 336dd2cc65f34f9b7bfda1cd0c42becedfc361d46f8Alkis Evlogimenos{ 337dd2cc65f34f9b7bfda1cd0c42becedfc361d46f8Alkis Evlogimenos DEBUG(std::cerr << "\t\t\t\tadding range: [" << start <<','<< end << "]\n"); 338dd2cc65f34f9b7bfda1cd0c42becedfc361d46f8Alkis Evlogimenos //assert(start < end && "invalid range?"); 339dd2cc65f34f9b7bfda1cd0c42becedfc361d46f8Alkis Evlogimenos Range range = std::make_pair(start, end); 340dd2cc65f34f9b7bfda1cd0c42becedfc361d46f8Alkis Evlogimenos Ranges::iterator it = 341dd2cc65f34f9b7bfda1cd0c42becedfc361d46f8Alkis Evlogimenos ranges.insert(std::upper_bound(ranges.begin(), ranges.end(), range), 342dd2cc65f34f9b7bfda1cd0c42becedfc361d46f8Alkis Evlogimenos range); 343dd2cc65f34f9b7bfda1cd0c42becedfc361d46f8Alkis Evlogimenos 344dd2cc65f34f9b7bfda1cd0c42becedfc361d46f8Alkis Evlogimenos DEBUG(std::cerr << "\t\t\t\tbefore merge forward: " << *this << '\n'); 345dd2cc65f34f9b7bfda1cd0c42becedfc361d46f8Alkis Evlogimenos mergeRangesForward(it); 346dd2cc65f34f9b7bfda1cd0c42becedfc361d46f8Alkis Evlogimenos DEBUG(std::cerr << "\t\t\t\tbefore merge backward: " << *this << '\n'); 347dd2cc65f34f9b7bfda1cd0c42becedfc361d46f8Alkis Evlogimenos mergeRangesBackward(it); 348dd2cc65f34f9b7bfda1cd0c42becedfc361d46f8Alkis Evlogimenos DEBUG(std::cerr << "\t\t\t\tafter merging: " << *this << '\n'); 349dd2cc65f34f9b7bfda1cd0c42becedfc361d46f8Alkis Evlogimenos} 350dd2cc65f34f9b7bfda1cd0c42becedfc361d46f8Alkis Evlogimenos 351dd2cc65f34f9b7bfda1cd0c42becedfc361d46f8Alkis Evlogimenosvoid LiveIntervals::Interval::mergeRangesForward(Ranges::iterator it) 352dd2cc65f34f9b7bfda1cd0c42becedfc361d46f8Alkis Evlogimenos{ 353dd2cc65f34f9b7bfda1cd0c42becedfc361d46f8Alkis Evlogimenos for (Ranges::iterator next = it + 1; 354dd2cc65f34f9b7bfda1cd0c42becedfc361d46f8Alkis Evlogimenos next != ranges.end() && it->second >= next->first; ) { 355dd2cc65f34f9b7bfda1cd0c42becedfc361d46f8Alkis Evlogimenos it->second = std::max(it->second, next->second); 356dd2cc65f34f9b7bfda1cd0c42becedfc361d46f8Alkis Evlogimenos next = ranges.erase(next); 357dd2cc65f34f9b7bfda1cd0c42becedfc361d46f8Alkis Evlogimenos } 358dd2cc65f34f9b7bfda1cd0c42becedfc361d46f8Alkis Evlogimenos} 359dd2cc65f34f9b7bfda1cd0c42becedfc361d46f8Alkis Evlogimenos 360dd2cc65f34f9b7bfda1cd0c42becedfc361d46f8Alkis Evlogimenosvoid LiveIntervals::Interval::mergeRangesBackward(Ranges::iterator it) 361dd2cc65f34f9b7bfda1cd0c42becedfc361d46f8Alkis Evlogimenos{ 362dd2cc65f34f9b7bfda1cd0c42becedfc361d46f8Alkis Evlogimenos for (Ranges::iterator prev = it - 1; 363dd2cc65f34f9b7bfda1cd0c42becedfc361d46f8Alkis Evlogimenos it != ranges.begin() && it->first <= prev->second; ) { 364dd2cc65f34f9b7bfda1cd0c42becedfc361d46f8Alkis Evlogimenos it->first = std::min(it->first, prev->first); 365dd2cc65f34f9b7bfda1cd0c42becedfc361d46f8Alkis Evlogimenos it->second = std::max(it->second, prev->second); 366dd2cc65f34f9b7bfda1cd0c42becedfc361d46f8Alkis Evlogimenos it = ranges.erase(prev); 367dd2cc65f34f9b7bfda1cd0c42becedfc361d46f8Alkis Evlogimenos prev = it - 1; 368dd2cc65f34f9b7bfda1cd0c42becedfc361d46f8Alkis Evlogimenos } 369dd2cc65f34f9b7bfda1cd0c42becedfc361d46f8Alkis Evlogimenos} 370dd2cc65f34f9b7bfda1cd0c42becedfc361d46f8Alkis Evlogimenos 371169cfd01964fc03828a7f2cad5d710890fbb08d8Alkis Evlogimenosbool LiveIntervals::Interval::liveAt(unsigned index) const 372169cfd01964fc03828a7f2cad5d710890fbb08d8Alkis Evlogimenos{ 373169cfd01964fc03828a7f2cad5d710890fbb08d8Alkis Evlogimenos Ranges::const_iterator r = ranges.begin(); 374169cfd01964fc03828a7f2cad5d710890fbb08d8Alkis Evlogimenos while (r != ranges.end() && index < r->second) { 375169cfd01964fc03828a7f2cad5d710890fbb08d8Alkis Evlogimenos if (index >= r->first) 376169cfd01964fc03828a7f2cad5d710890fbb08d8Alkis Evlogimenos return true; 377169cfd01964fc03828a7f2cad5d710890fbb08d8Alkis Evlogimenos ++r; 378169cfd01964fc03828a7f2cad5d710890fbb08d8Alkis Evlogimenos } 379169cfd01964fc03828a7f2cad5d710890fbb08d8Alkis Evlogimenos return false; 380169cfd01964fc03828a7f2cad5d710890fbb08d8Alkis Evlogimenos} 381169cfd01964fc03828a7f2cad5d710890fbb08d8Alkis Evlogimenos 382169cfd01964fc03828a7f2cad5d710890fbb08d8Alkis Evlogimenosbool LiveIntervals::Interval::overlaps(const Interval& other) const 383169cfd01964fc03828a7f2cad5d710890fbb08d8Alkis Evlogimenos{ 38480b378cf7c3dce77029dc3118e1f63bc6d389da1Alkis Evlogimenos Ranges::const_iterator i = ranges.begin(); 38580b378cf7c3dce77029dc3118e1f63bc6d389da1Alkis Evlogimenos Ranges::const_iterator j = other.ranges.begin(); 38680b378cf7c3dce77029dc3118e1f63bc6d389da1Alkis Evlogimenos 38780b378cf7c3dce77029dc3118e1f63bc6d389da1Alkis Evlogimenos while (i != ranges.end() && j != other.ranges.end()) { 38880b378cf7c3dce77029dc3118e1f63bc6d389da1Alkis Evlogimenos if (i->first < j->first) { 38980b378cf7c3dce77029dc3118e1f63bc6d389da1Alkis Evlogimenos if (i->second > j->first) { 39080b378cf7c3dce77029dc3118e1f63bc6d389da1Alkis Evlogimenos return true; 39180b378cf7c3dce77029dc3118e1f63bc6d389da1Alkis Evlogimenos } 39280b378cf7c3dce77029dc3118e1f63bc6d389da1Alkis Evlogimenos else { 39380b378cf7c3dce77029dc3118e1f63bc6d389da1Alkis Evlogimenos ++i; 39480b378cf7c3dce77029dc3118e1f63bc6d389da1Alkis Evlogimenos } 39580b378cf7c3dce77029dc3118e1f63bc6d389da1Alkis Evlogimenos } 39680b378cf7c3dce77029dc3118e1f63bc6d389da1Alkis Evlogimenos else if (j->first < i->first) { 39780b378cf7c3dce77029dc3118e1f63bc6d389da1Alkis Evlogimenos if (j->second > i->first) { 398169cfd01964fc03828a7f2cad5d710890fbb08d8Alkis Evlogimenos return true; 39980b378cf7c3dce77029dc3118e1f63bc6d389da1Alkis Evlogimenos } 40080b378cf7c3dce77029dc3118e1f63bc6d389da1Alkis Evlogimenos else { 40180b378cf7c3dce77029dc3118e1f63bc6d389da1Alkis Evlogimenos ++j; 40280b378cf7c3dce77029dc3118e1f63bc6d389da1Alkis Evlogimenos } 40380b378cf7c3dce77029dc3118e1f63bc6d389da1Alkis Evlogimenos } 40480b378cf7c3dce77029dc3118e1f63bc6d389da1Alkis Evlogimenos else { 40580b378cf7c3dce77029dc3118e1f63bc6d389da1Alkis Evlogimenos return true; 40680b378cf7c3dce77029dc3118e1f63bc6d389da1Alkis Evlogimenos } 407169cfd01964fc03828a7f2cad5d710890fbb08d8Alkis Evlogimenos } 408169cfd01964fc03828a7f2cad5d710890fbb08d8Alkis Evlogimenos 409169cfd01964fc03828a7f2cad5d710890fbb08d8Alkis Evlogimenos return false; 410169cfd01964fc03828a7f2cad5d710890fbb08d8Alkis Evlogimenos} 411169cfd01964fc03828a7f2cad5d710890fbb08d8Alkis Evlogimenos 412b27ef248f579b354aab434f63c417ab1103e47e2Alkis Evlogimenosstd::ostream& llvm::operator<<(std::ostream& os, 413b27ef248f579b354aab434f63c417ab1103e47e2Alkis Evlogimenos const LiveIntervals::Interval& li) 414b27ef248f579b354aab434f63c417ab1103e47e2Alkis Evlogimenos{ 415169cfd01964fc03828a7f2cad5d710890fbb08d8Alkis Evlogimenos os << "%reg" << li.reg << ',' << li.weight << " = "; 416b27ef248f579b354aab434f63c417ab1103e47e2Alkis Evlogimenos for (LiveIntervals::Interval::Ranges::const_iterator 417b27ef248f579b354aab434f63c417ab1103e47e2Alkis Evlogimenos i = li.ranges.begin(), e = li.ranges.end(); i != e; ++i) { 41863841bc85d15ca0ce1b3208084f4262f3d33ef21Alkis Evlogimenos os << "[" << i->first << "," << i->second << ")"; 419b27ef248f579b354aab434f63c417ab1103e47e2Alkis Evlogimenos } 420b27ef248f579b354aab434f63c417ab1103e47e2Alkis Evlogimenos return os; 421b27ef248f579b354aab434f63c417ab1103e47e2Alkis Evlogimenos} 422