LiveIntervalAnalysis.cpp revision 97017de1872e08ffcdde2fccdfd399647c1ccc4a
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" 204d46e1e521c0df1990ea50f8146d22bd77ea71a6Alkis 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" 244d46e1e521c0df1990ea50f8146d22bd77ea71a6Alkis 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" 314d46e1e521c0df1990ea50f8146d22bd77ea71a6Alkis Evlogimenos#include "llvm/Target/TargetRegInfo.h" 32ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos#include "llvm/Support/CFG.h" 33e88280a4224730dcf8076e0d9a20973c5761fd06Alkis Evlogimenos#include "Support/CommandLine.h" 34ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos#include "Support/Debug.h" 354d46e1e521c0df1990ea50f8146d22bd77ea71a6Alkis Evlogimenos#include "Support/DepthFirstIterator.h" 36ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos#include "Support/Statistic.h" 374d46e1e521c0df1990ea50f8146d22bd77ea71a6Alkis Evlogimenos#include <cmath> 38ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos#include <iostream> 396b4edbaaf9021e0434f0ce0c3724eb43ed41b770Alkis Evlogimenos#include <limits> 40ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos 41ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenosusing namespace llvm; 42ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos 43ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenosnamespace { 44ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos RegisterAnalysis<LiveIntervals> X("liveintervals", 45ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos "Live Interval Analysis"); 46ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos 47ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos Statistic<> numIntervals("liveintervals", "Number of intervals"); 48e88280a4224730dcf8076e0d9a20973c5761fd06Alkis Evlogimenos 49e88280a4224730dcf8076e0d9a20973c5761fd06Alkis Evlogimenos cl::opt<bool> 50e88280a4224730dcf8076e0d9a20973c5761fd06Alkis Evlogimenos join("join-liveintervals", 51e88280a4224730dcf8076e0d9a20973c5761fd06Alkis Evlogimenos cl::desc("Join compatible live intervals"), 5279b0c3f0b9d91bbda354a2c6f22b6578655a5143Alkis Evlogimenos cl::init(true)); 53ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos}; 54ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos 55ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenosvoid LiveIntervals::getAnalysisUsage(AnalysisUsage &AU) const 56ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos{ 57f6f91bf6680668990ff3804b14cf05beedc56ec4Alkis Evlogimenos AU.addPreserved<LiveVariables>(); 58ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos AU.addRequired<LiveVariables>(); 59f6f91bf6680668990ff3804b14cf05beedc56ec4Alkis Evlogimenos AU.addPreservedID(PHIEliminationID); 60ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos AU.addRequiredID(PHIEliminationID); 614c080863de86448d905beab27686da823b6d44c1Alkis Evlogimenos AU.addRequiredID(TwoAddressInstructionPassID); 626b4edbaaf9021e0434f0ce0c3724eb43ed41b770Alkis Evlogimenos AU.addRequired<LoopInfo>(); 63ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos MachineFunctionPass::getAnalysisUsage(AU); 64ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos} 65ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos 66ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos/// runOnMachineFunction - Register allocate the whole function 67ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos/// 68ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenosbool LiveIntervals::runOnMachineFunction(MachineFunction &fn) { 69ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos DEBUG(std::cerr << "Machine Function\n"); 70ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos mf_ = &fn; 71ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos tm_ = &fn.getTarget(); 72ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos mri_ = tm_->getRegisterInfo(); 73ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos lv_ = &getAnalysis<LiveVariables>(); 744d46e1e521c0df1990ea50f8146d22bd77ea71a6Alkis Evlogimenos mbbi2mbbMap_.clear(); 754d46e1e521c0df1990ea50f8146d22bd77ea71a6Alkis Evlogimenos mi2iMap_.clear(); 764d46e1e521c0df1990ea50f8146d22bd77ea71a6Alkis Evlogimenos r2iMap_.clear(); 774d46e1e521c0df1990ea50f8146d22bd77ea71a6Alkis Evlogimenos r2iMap_.clear(); 784d46e1e521c0df1990ea50f8146d22bd77ea71a6Alkis Evlogimenos r2rMap_.clear(); 794d46e1e521c0df1990ea50f8146d22bd77ea71a6Alkis Evlogimenos intervals_.clear(); 80ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos 81ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos // number MachineInstrs 82ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos unsigned miIndex = 0; 83ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos for (MachineFunction::iterator mbb = mf_->begin(), mbbEnd = mf_->end(); 84ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos mbb != mbbEnd; ++mbb) { 85ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos const std::pair<MachineBasicBlock*, unsigned>& entry = 864d46e1e521c0df1990ea50f8146d22bd77ea71a6Alkis Evlogimenos lv_->getMachineBasicBlockInfo(&*mbb); 87ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos bool inserted = mbbi2mbbMap_.insert(std::make_pair(entry.second, 88ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos entry.first)).second; 89ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos assert(inserted && "multiple index -> MachineBasicBlock"); 90ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos 91ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos for (MachineBasicBlock::iterator mi = mbb->begin(), miEnd = mbb->end(); 92ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos mi != miEnd; ++mi) { 93ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos inserted = mi2iMap_.insert(std::make_pair(*mi, miIndex)).second; 94ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos assert(inserted && "multiple MachineInstr -> index mappings"); 95ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos ++miIndex; 96ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos } 97ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos } 98ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos 99ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos computeIntervals(); 100ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos 1017a40eaaceec0af76d5b97610f3d4e7a47a19d245Alkis Evlogimenos // compute spill weights 1027a40eaaceec0af76d5b97610f3d4e7a47a19d245Alkis Evlogimenos const LoopInfo& loopInfo = getAnalysis<LoopInfo>(); 10326bfc08b80c904c71487ac1ab49a8b3a15a8d3e9Alkis Evlogimenos const TargetInstrInfo& tii = tm_->getInstrInfo(); 1047a40eaaceec0af76d5b97610f3d4e7a47a19d245Alkis Evlogimenos 105e88280a4224730dcf8076e0d9a20973c5761fd06Alkis Evlogimenos for (MachineFunction::const_iterator mbbi = mf_->begin(), 106e88280a4224730dcf8076e0d9a20973c5761fd06Alkis Evlogimenos mbbe = mf_->end(); mbbi != mbbe; ++mbbi) { 107e88280a4224730dcf8076e0d9a20973c5761fd06Alkis Evlogimenos const MachineBasicBlock* mbb = mbbi; 1087a40eaaceec0af76d5b97610f3d4e7a47a19d245Alkis Evlogimenos unsigned loopDepth = loopInfo.getLoopDepth(mbb->getBasicBlock()); 1097a40eaaceec0af76d5b97610f3d4e7a47a19d245Alkis Evlogimenos 1104d46e1e521c0df1990ea50f8146d22bd77ea71a6Alkis Evlogimenos for (MachineBasicBlock::const_iterator mii = mbb->begin(), 1114d46e1e521c0df1990ea50f8146d22bd77ea71a6Alkis Evlogimenos mie = mbb->end(); mii != mie; ++mii) { 1124d46e1e521c0df1990ea50f8146d22bd77ea71a6Alkis Evlogimenos MachineInstr* mi = *mii; 113e88280a4224730dcf8076e0d9a20973c5761fd06Alkis Evlogimenos 1144d46e1e521c0df1990ea50f8146d22bd77ea71a6Alkis Evlogimenos for (int i = mi->getNumOperands() - 1; i >= 0; --i) { 1154d46e1e521c0df1990ea50f8146d22bd77ea71a6Alkis Evlogimenos MachineOperand& mop = mi->getOperand(i); 1167a40eaaceec0af76d5b97610f3d4e7a47a19d245Alkis Evlogimenos 1174d46e1e521c0df1990ea50f8146d22bd77ea71a6Alkis Evlogimenos if (!mop.isVirtualRegister()) 1184d46e1e521c0df1990ea50f8146d22bd77ea71a6Alkis Evlogimenos continue; 1197a40eaaceec0af76d5b97610f3d4e7a47a19d245Alkis Evlogimenos 1204d46e1e521c0df1990ea50f8146d22bd77ea71a6Alkis Evlogimenos unsigned reg = mop.getAllocatedRegNum(); 1214d46e1e521c0df1990ea50f8146d22bd77ea71a6Alkis Evlogimenos Reg2IntervalMap::iterator r2iit = r2iMap_.find(reg); 1224d46e1e521c0df1990ea50f8146d22bd77ea71a6Alkis Evlogimenos assert(r2iit != r2iMap_.end()); 1234d46e1e521c0df1990ea50f8146d22bd77ea71a6Alkis Evlogimenos r2iit->second->weight += pow(10.0F, loopDepth); 1247a40eaaceec0af76d5b97610f3d4e7a47a19d245Alkis Evlogimenos } 1257a40eaaceec0af76d5b97610f3d4e7a47a19d245Alkis Evlogimenos } 1267a40eaaceec0af76d5b97610f3d4e7a47a19d245Alkis Evlogimenos } 1277a40eaaceec0af76d5b97610f3d4e7a47a19d245Alkis Evlogimenos 128e88280a4224730dcf8076e0d9a20973c5761fd06Alkis Evlogimenos // join intervals if requested 129e88280a4224730dcf8076e0d9a20973c5761fd06Alkis Evlogimenos if (join) joinIntervals(); 130e88280a4224730dcf8076e0d9a20973c5761fd06Alkis Evlogimenos 131d6e40a6cbced8265334ee0375f5996098dfdccb2Alkis Evlogimenos numIntervals += intervals_.size(); 132d6e40a6cbced8265334ee0375f5996098dfdccb2Alkis Evlogimenos 133ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos return true; 134ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos} 135ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos 136ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenosvoid LiveIntervals::printRegName(unsigned reg) const 137ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos{ 138ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos if (reg < MRegisterInfo::FirstVirtualRegister) 139ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos std::cerr << mri_->getName(reg); 140ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos else 141ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos std::cerr << '%' << reg; 142ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos} 143ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos 144ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenosvoid LiveIntervals::handleVirtualRegisterDef(MachineBasicBlock* mbb, 145ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos MachineBasicBlock::iterator mi, 146ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos unsigned reg) 147ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos{ 148a3a6524965416647883bc0b78ff6f18fb3f7b5fcAlkis Evlogimenos DEBUG(std::cerr << "\t\tregister: ";printRegName(reg); std::cerr << '\n'); 149ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos 150ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos unsigned instrIndex = getInstructionIndex(*mi); 151ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos 152ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos LiveVariables::VarInfo& vi = lv_->getVarInfo(reg); 153ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos 154dd2cc65f34f9b7bfda1cd0c42becedfc361d46f8Alkis Evlogimenos Interval* interval = 0; 1554d46e1e521c0df1990ea50f8146d22bd77ea71a6Alkis Evlogimenos Reg2IntervalMap::iterator r2iit = r2iMap_.find(reg); 1564d46e1e521c0df1990ea50f8146d22bd77ea71a6Alkis Evlogimenos if (r2iit == r2iMap_.end()) { 157ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos // add new interval 158ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos intervals_.push_back(Interval(reg)); 159ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos // update interval index for this register 1604d46e1e521c0df1990ea50f8146d22bd77ea71a6Alkis Evlogimenos bool inserted = 1614d46e1e521c0df1990ea50f8146d22bd77ea71a6Alkis Evlogimenos r2iMap_.insert(std::make_pair(reg, --intervals_.end())).second; 1624d46e1e521c0df1990ea50f8146d22bd77ea71a6Alkis Evlogimenos assert(inserted); 163dd2cc65f34f9b7bfda1cd0c42becedfc361d46f8Alkis Evlogimenos interval = &intervals_.back(); 164dd2cc65f34f9b7bfda1cd0c42becedfc361d46f8Alkis Evlogimenos } 165dd2cc65f34f9b7bfda1cd0c42becedfc361d46f8Alkis Evlogimenos else { 166f5f1689ed28025cef601034052ef9c214797e8afAlkis Evlogimenos interval = &*r2iit->second; 167dd2cc65f34f9b7bfda1cd0c42becedfc361d46f8Alkis Evlogimenos } 168ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos 1694d46e1e521c0df1990ea50f8146d22bd77ea71a6Alkis Evlogimenos for (MbbIndex2MbbMap::iterator 1704d46e1e521c0df1990ea50f8146d22bd77ea71a6Alkis Evlogimenos it = mbbi2mbbMap_.begin(), itEnd = mbbi2mbbMap_.end(); 1714d46e1e521c0df1990ea50f8146d22bd77ea71a6Alkis Evlogimenos it != itEnd; ++it) { 1724d46e1e521c0df1990ea50f8146d22bd77ea71a6Alkis Evlogimenos unsigned liveBlockIndex = it->first; 1734d46e1e521c0df1990ea50f8146d22bd77ea71a6Alkis Evlogimenos MachineBasicBlock* liveBlock = it->second; 1744d46e1e521c0df1990ea50f8146d22bd77ea71a6Alkis Evlogimenos if (liveBlockIndex < vi.AliveBlocks.size() && 1754d46e1e521c0df1990ea50f8146d22bd77ea71a6Alkis Evlogimenos vi.AliveBlocks[liveBlockIndex] && 1764d46e1e521c0df1990ea50f8146d22bd77ea71a6Alkis Evlogimenos !liveBlock->empty()) { 1774d46e1e521c0df1990ea50f8146d22bd77ea71a6Alkis Evlogimenos unsigned start = getInstructionIndex(liveBlock->front()); 1784d46e1e521c0df1990ea50f8146d22bd77ea71a6Alkis Evlogimenos unsigned end = getInstructionIndex(liveBlock->back()) + 1; 1794d46e1e521c0df1990ea50f8146d22bd77ea71a6Alkis Evlogimenos interval->addRange(start, end); 180ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos } 181dd2cc65f34f9b7bfda1cd0c42becedfc361d46f8Alkis Evlogimenos } 182ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos 183dd2cc65f34f9b7bfda1cd0c42becedfc361d46f8Alkis Evlogimenos bool killedInDefiningBasicBlock = false; 184dd2cc65f34f9b7bfda1cd0c42becedfc361d46f8Alkis Evlogimenos for (int i = 0, e = vi.Kills.size(); i != e; ++i) { 185dd2cc65f34f9b7bfda1cd0c42becedfc361d46f8Alkis Evlogimenos MachineBasicBlock* killerBlock = vi.Kills[i].first; 186dd2cc65f34f9b7bfda1cd0c42becedfc361d46f8Alkis Evlogimenos MachineInstr* killerInstr = vi.Kills[i].second; 187dd2cc65f34f9b7bfda1cd0c42becedfc361d46f8Alkis Evlogimenos unsigned start = (mbb == killerBlock ? 188dd2cc65f34f9b7bfda1cd0c42becedfc361d46f8Alkis Evlogimenos instrIndex : 189dd2cc65f34f9b7bfda1cd0c42becedfc361d46f8Alkis Evlogimenos getInstructionIndex(killerBlock->front())); 190dd2cc65f34f9b7bfda1cd0c42becedfc361d46f8Alkis Evlogimenos unsigned end = getInstructionIndex(killerInstr) + 1; 19143f692f90f6b27304570e1b1807542dff4b8e847Alkis Evlogimenos if (start < end) { 19243f692f90f6b27304570e1b1807542dff4b8e847Alkis Evlogimenos killedInDefiningBasicBlock |= mbb == killerBlock; 19343f692f90f6b27304570e1b1807542dff4b8e847Alkis Evlogimenos interval->addRange(start, end); 19443f692f90f6b27304570e1b1807542dff4b8e847Alkis Evlogimenos } 195dd2cc65f34f9b7bfda1cd0c42becedfc361d46f8Alkis Evlogimenos } 196ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos 197dd2cc65f34f9b7bfda1cd0c42becedfc361d46f8Alkis Evlogimenos if (!killedInDefiningBasicBlock) { 198dd2cc65f34f9b7bfda1cd0c42becedfc361d46f8Alkis Evlogimenos unsigned end = getInstructionIndex(mbb->back()) + 1; 199dd2cc65f34f9b7bfda1cd0c42becedfc361d46f8Alkis Evlogimenos interval->addRange(instrIndex, end); 200ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos } 201ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos} 202ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos 203ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenosvoid LiveIntervals::handlePhysicalRegisterDef(MachineBasicBlock* mbb, 204ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos MachineBasicBlock::iterator mi, 205ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos unsigned reg) 206ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos{ 2071a119e24106810310825f44c7bfd232d3272e639Alkis Evlogimenos DEBUG(std::cerr << "\t\tregister: "; printRegName(reg)); 208ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos 209ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos unsigned start = getInstructionIndex(*mi); 2104d46e1e521c0df1990ea50f8146d22bd77ea71a6Alkis Evlogimenos unsigned end = start; 211ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos 212af25473d5e99e0c0968746e12d8827e4b712bd31Alkis Evlogimenos // register can be dead by the instruction defining it but it can 213af25473d5e99e0c0968746e12d8827e4b712bd31Alkis Evlogimenos // only be killed by subsequent instructions 2144d46e1e521c0df1990ea50f8146d22bd77ea71a6Alkis Evlogimenos 215af25473d5e99e0c0968746e12d8827e4b712bd31Alkis Evlogimenos for (LiveVariables::killed_iterator 216af25473d5e99e0c0968746e12d8827e4b712bd31Alkis Evlogimenos ki = lv_->dead_begin(*mi), 217af25473d5e99e0c0968746e12d8827e4b712bd31Alkis Evlogimenos ke = lv_->dead_end(*mi); 218af25473d5e99e0c0968746e12d8827e4b712bd31Alkis Evlogimenos ki != ke; ++ki) { 219af25473d5e99e0c0968746e12d8827e4b712bd31Alkis Evlogimenos if (reg == ki->second) { 2204d46e1e521c0df1990ea50f8146d22bd77ea71a6Alkis Evlogimenos end = getInstructionIndex(ki->first) + 1; 221af25473d5e99e0c0968746e12d8827e4b712bd31Alkis Evlogimenos DEBUG(std::cerr << " dead\n"); 222af25473d5e99e0c0968746e12d8827e4b712bd31Alkis Evlogimenos goto exit; 223af25473d5e99e0c0968746e12d8827e4b712bd31Alkis Evlogimenos } 224af25473d5e99e0c0968746e12d8827e4b712bd31Alkis Evlogimenos } 2254d46e1e521c0df1990ea50f8146d22bd77ea71a6Alkis Evlogimenos ++mi; 2264d46e1e521c0df1990ea50f8146d22bd77ea71a6Alkis Evlogimenos 2274d46e1e521c0df1990ea50f8146d22bd77ea71a6Alkis Evlogimenos for (MachineBasicBlock::iterator e = mbb->end(); mi != e; ++mi) { 2284d46e1e521c0df1990ea50f8146d22bd77ea71a6Alkis Evlogimenos for (LiveVariables::killed_iterator 2294d46e1e521c0df1990ea50f8146d22bd77ea71a6Alkis Evlogimenos ki = lv_->dead_begin(*mi), 2304d46e1e521c0df1990ea50f8146d22bd77ea71a6Alkis Evlogimenos ke = lv_->dead_end(*mi); 2314d46e1e521c0df1990ea50f8146d22bd77ea71a6Alkis Evlogimenos ki != ke; ++ki) { 2324d46e1e521c0df1990ea50f8146d22bd77ea71a6Alkis Evlogimenos if (reg == ki->second) { 2334d46e1e521c0df1990ea50f8146d22bd77ea71a6Alkis Evlogimenos end = getInstructionIndex(ki->first) + 1; 2344d46e1e521c0df1990ea50f8146d22bd77ea71a6Alkis Evlogimenos DEBUG(std::cerr << " dead\n"); 2354d46e1e521c0df1990ea50f8146d22bd77ea71a6Alkis Evlogimenos goto exit; 2364d46e1e521c0df1990ea50f8146d22bd77ea71a6Alkis Evlogimenos } 2374d46e1e521c0df1990ea50f8146d22bd77ea71a6Alkis Evlogimenos } 238ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos 2394d46e1e521c0df1990ea50f8146d22bd77ea71a6Alkis Evlogimenos for (LiveVariables::killed_iterator 2404d46e1e521c0df1990ea50f8146d22bd77ea71a6Alkis Evlogimenos ki = lv_->killed_begin(*mi), 2414d46e1e521c0df1990ea50f8146d22bd77ea71a6Alkis Evlogimenos ke = lv_->killed_end(*mi); 2424d46e1e521c0df1990ea50f8146d22bd77ea71a6Alkis Evlogimenos ki != ke; ++ki) { 2434d46e1e521c0df1990ea50f8146d22bd77ea71a6Alkis Evlogimenos if (reg == ki->second) { 2444d46e1e521c0df1990ea50f8146d22bd77ea71a6Alkis Evlogimenos end = getInstructionIndex(ki->first) + 1; 2454d46e1e521c0df1990ea50f8146d22bd77ea71a6Alkis Evlogimenos DEBUG(std::cerr << " killed\n"); 2464d46e1e521c0df1990ea50f8146d22bd77ea71a6Alkis Evlogimenos goto exit; 247ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos } 2484d46e1e521c0df1990ea50f8146d22bd77ea71a6Alkis Evlogimenos } 249ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos } 250ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenosexit: 251ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos assert(start < end && "did not find end of interval?"); 252ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos 2534d46e1e521c0df1990ea50f8146d22bd77ea71a6Alkis Evlogimenos Reg2IntervalMap::iterator r2iit = r2iMap_.find(reg); 2544d46e1e521c0df1990ea50f8146d22bd77ea71a6Alkis Evlogimenos if (r2iit != r2iMap_.end()) { 2554d46e1e521c0df1990ea50f8146d22bd77ea71a6Alkis Evlogimenos Interval& interval = *r2iit->second; 2564d46e1e521c0df1990ea50f8146d22bd77ea71a6Alkis Evlogimenos interval.addRange(start, end); 257ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos } 258ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos else { 259ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos intervals_.push_back(Interval(reg)); 2604d46e1e521c0df1990ea50f8146d22bd77ea71a6Alkis Evlogimenos Interval& interval = intervals_.back(); 261ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos // update interval index for this register 2624d46e1e521c0df1990ea50f8146d22bd77ea71a6Alkis Evlogimenos bool inserted = 2634d46e1e521c0df1990ea50f8146d22bd77ea71a6Alkis Evlogimenos r2iMap_.insert(std::make_pair(reg, --intervals_.end())).second; 2644d46e1e521c0df1990ea50f8146d22bd77ea71a6Alkis Evlogimenos assert(inserted); 2654d46e1e521c0df1990ea50f8146d22bd77ea71a6Alkis Evlogimenos interval.addRange(start, end); 266ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos } 267ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos} 268ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos 269ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenosvoid LiveIntervals::handleRegisterDef(MachineBasicBlock* mbb, 270ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos MachineBasicBlock::iterator mi, 271ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos unsigned reg) 272ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos{ 273ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos if (reg < MRegisterInfo::FirstVirtualRegister) { 2741a119e24106810310825f44c7bfd232d3272e639Alkis Evlogimenos if (lv_->getAllocatablePhysicalRegisters()[reg]) { 275ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos handlePhysicalRegisterDef(mbb, mi, reg); 27619b6486d3891c8a02a301aa1b44348a420772fcfAlkis Evlogimenos for (const unsigned* as = mri_->getAliasSet(reg); *as; ++as) 27719b6486d3891c8a02a301aa1b44348a420772fcfAlkis Evlogimenos handlePhysicalRegisterDef(mbb, mi, *as); 278ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos } 279ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos } 280ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos else { 281ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos handleVirtualRegisterDef(mbb, mi, reg); 282ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos } 283ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos} 284ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos 2854d46e1e521c0df1990ea50f8146d22bd77ea71a6Alkis Evlogimenosunsigned LiveIntervals::getInstructionIndex(MachineInstr* instr) const 2864d46e1e521c0df1990ea50f8146d22bd77ea71a6Alkis Evlogimenos{ 2874d46e1e521c0df1990ea50f8146d22bd77ea71a6Alkis Evlogimenos assert(mi2iMap_.find(instr) != mi2iMap_.end() && 2884d46e1e521c0df1990ea50f8146d22bd77ea71a6Alkis Evlogimenos "instruction not assigned a number"); 2894d46e1e521c0df1990ea50f8146d22bd77ea71a6Alkis Evlogimenos return mi2iMap_.find(instr)->second; 2904d46e1e521c0df1990ea50f8146d22bd77ea71a6Alkis Evlogimenos} 2914d46e1e521c0df1990ea50f8146d22bd77ea71a6Alkis Evlogimenos 292ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos/// computeIntervals - computes the live intervals for virtual 2934d46e1e521c0df1990ea50f8146d22bd77ea71a6Alkis Evlogimenos/// registers. for some ordering of the machine instructions [1,N] a 2944d46e1e521c0df1990ea50f8146d22bd77ea71a6Alkis Evlogimenos/// live interval is an interval [i, j] where 1 <= i <= j <= N for 295ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos/// which a variable is live 296ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenosvoid LiveIntervals::computeIntervals() 297ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos{ 298ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos DEBUG(std::cerr << "computing live intervals:\n"); 299ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos 300ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos for (MbbIndex2MbbMap::iterator 301ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos it = mbbi2mbbMap_.begin(), itEnd = mbbi2mbbMap_.end(); 302ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos it != itEnd; ++it) { 303ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos MachineBasicBlock* mbb = it->second; 304ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos DEBUG(std::cerr << "machine basic block: " 305ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos << mbb->getBasicBlock()->getName() << "\n"); 3066b4edbaaf9021e0434f0ce0c3724eb43ed41b770Alkis Evlogimenos 307ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos for (MachineBasicBlock::iterator mi = mbb->begin(), miEnd = mbb->end(); 308ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos mi != miEnd; ++mi) { 309ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos MachineInstr* instr = *mi; 310ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos const TargetInstrDescriptor& tid = 311ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos tm_->getInstrInfo().get(instr->getOpcode()); 312a3a6524965416647883bc0b78ff6f18fb3f7b5fcAlkis Evlogimenos DEBUG(std::cerr << "\t[" << getInstructionIndex(instr) << "] "; 313ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos instr->print(std::cerr, *tm_);); 314ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos 315ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos // handle implicit defs 31619b6486d3891c8a02a301aa1b44348a420772fcfAlkis Evlogimenos for (const unsigned* id = tid.ImplicitDefs; *id; ++id) 31719b6486d3891c8a02a301aa1b44348a420772fcfAlkis Evlogimenos handleRegisterDef(mbb, mi, *id); 318ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos 319ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos // handle explicit defs 320ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos for (int i = instr->getNumOperands() - 1; i >= 0; --i) { 321ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos MachineOperand& mop = instr->getOperand(i); 3224d46e1e521c0df1990ea50f8146d22bd77ea71a6Alkis Evlogimenos 3234d46e1e521c0df1990ea50f8146d22bd77ea71a6Alkis Evlogimenos if (!mop.isRegister()) 3244d46e1e521c0df1990ea50f8146d22bd77ea71a6Alkis Evlogimenos continue; 3254d46e1e521c0df1990ea50f8146d22bd77ea71a6Alkis Evlogimenos 3264d46e1e521c0df1990ea50f8146d22bd77ea71a6Alkis Evlogimenos // handle defs - build intervals 3274d46e1e521c0df1990ea50f8146d22bd77ea71a6Alkis Evlogimenos if (mop.isDef()) 32819b6486d3891c8a02a301aa1b44348a420772fcfAlkis Evlogimenos handleRegisterDef(mbb, mi, mop.getAllocatedRegNum()); 329ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos } 330ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos } 331ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos } 332ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos 333f5f1689ed28025cef601034052ef9c214797e8afAlkis Evlogimenos intervals_.sort(StartPointComp()); 334ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos DEBUG(std::copy(intervals_.begin(), intervals_.end(), 335ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos std::ostream_iterator<Interval>(std::cerr, "\n"))); 336ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos} 337b27ef248f579b354aab434f63c417ab1103e47e2Alkis Evlogimenos 338e88280a4224730dcf8076e0d9a20973c5761fd06Alkis Evlogimenosunsigned LiveIntervals::rep(unsigned reg) 339169cfd01964fc03828a7f2cad5d710890fbb08d8Alkis Evlogimenos{ 340e88280a4224730dcf8076e0d9a20973c5761fd06Alkis Evlogimenos Reg2RegMap::iterator it = r2rMap_.find(reg); 341e88280a4224730dcf8076e0d9a20973c5761fd06Alkis Evlogimenos if (it != r2rMap_.end()) 342e88280a4224730dcf8076e0d9a20973c5761fd06Alkis Evlogimenos return it->second = rep(it->second); 343e88280a4224730dcf8076e0d9a20973c5761fd06Alkis Evlogimenos return reg; 344169cfd01964fc03828a7f2cad5d710890fbb08d8Alkis Evlogimenos} 345169cfd01964fc03828a7f2cad5d710890fbb08d8Alkis Evlogimenos 346e88280a4224730dcf8076e0d9a20973c5761fd06Alkis Evlogimenosvoid LiveIntervals::joinIntervals() 347dd2cc65f34f9b7bfda1cd0c42becedfc361d46f8Alkis Evlogimenos{ 348e88280a4224730dcf8076e0d9a20973c5761fd06Alkis Evlogimenos DEBUG(std::cerr << "joining compatible intervals:\n"); 349dd2cc65f34f9b7bfda1cd0c42becedfc361d46f8Alkis Evlogimenos 350e88280a4224730dcf8076e0d9a20973c5761fd06Alkis Evlogimenos const TargetInstrInfo& tii = tm_->getInstrInfo(); 351dd2cc65f34f9b7bfda1cd0c42becedfc361d46f8Alkis Evlogimenos 352e88280a4224730dcf8076e0d9a20973c5761fd06Alkis Evlogimenos for (MachineFunction::const_iterator mbbi = mf_->begin(), 353e88280a4224730dcf8076e0d9a20973c5761fd06Alkis Evlogimenos mbbe = mf_->end(); mbbi != mbbe; ++mbbi) { 354e88280a4224730dcf8076e0d9a20973c5761fd06Alkis Evlogimenos const MachineBasicBlock* mbb = mbbi; 355e88280a4224730dcf8076e0d9a20973c5761fd06Alkis Evlogimenos DEBUG(std::cerr << "machine basic block: " 356e88280a4224730dcf8076e0d9a20973c5761fd06Alkis Evlogimenos << mbb->getBasicBlock()->getName() << "\n"); 357e88280a4224730dcf8076e0d9a20973c5761fd06Alkis Evlogimenos 358e88280a4224730dcf8076e0d9a20973c5761fd06Alkis Evlogimenos for (MachineBasicBlock::const_iterator mii = mbb->begin(), 359e88280a4224730dcf8076e0d9a20973c5761fd06Alkis Evlogimenos mie = mbb->end(); mii != mie; ++mii) { 360e88280a4224730dcf8076e0d9a20973c5761fd06Alkis Evlogimenos MachineInstr* mi = *mii; 361e88280a4224730dcf8076e0d9a20973c5761fd06Alkis Evlogimenos const TargetInstrDescriptor& tid = 362e88280a4224730dcf8076e0d9a20973c5761fd06Alkis Evlogimenos tm_->getInstrInfo().get(mi->getOpcode()); 363e88280a4224730dcf8076e0d9a20973c5761fd06Alkis Evlogimenos DEBUG(std::cerr << "\t\tinstruction[" 364e88280a4224730dcf8076e0d9a20973c5761fd06Alkis Evlogimenos << getInstructionIndex(mi) << "]: "; 365e88280a4224730dcf8076e0d9a20973c5761fd06Alkis Evlogimenos mi->print(std::cerr, *tm_);); 366e88280a4224730dcf8076e0d9a20973c5761fd06Alkis Evlogimenos 367e88280a4224730dcf8076e0d9a20973c5761fd06Alkis Evlogimenos unsigned srcReg, dstReg; 368e88280a4224730dcf8076e0d9a20973c5761fd06Alkis Evlogimenos if (tii.isMoveInstr(*mi, srcReg, dstReg) && 369e88280a4224730dcf8076e0d9a20973c5761fd06Alkis Evlogimenos (srcReg >= MRegisterInfo::FirstVirtualRegister || 370e88280a4224730dcf8076e0d9a20973c5761fd06Alkis Evlogimenos lv_->getAllocatablePhysicalRegisters()[srcReg]) && 371e88280a4224730dcf8076e0d9a20973c5761fd06Alkis Evlogimenos (dstReg >= MRegisterInfo::FirstVirtualRegister || 372e88280a4224730dcf8076e0d9a20973c5761fd06Alkis Evlogimenos lv_->getAllocatablePhysicalRegisters()[dstReg])) { 373e88280a4224730dcf8076e0d9a20973c5761fd06Alkis Evlogimenos 374e88280a4224730dcf8076e0d9a20973c5761fd06Alkis Evlogimenos // get representative registers 375e88280a4224730dcf8076e0d9a20973c5761fd06Alkis Evlogimenos srcReg = rep(srcReg); 376e88280a4224730dcf8076e0d9a20973c5761fd06Alkis Evlogimenos dstReg = rep(dstReg); 377e88280a4224730dcf8076e0d9a20973c5761fd06Alkis Evlogimenos 378e88280a4224730dcf8076e0d9a20973c5761fd06Alkis Evlogimenos // if they are already joined we continue 379e88280a4224730dcf8076e0d9a20973c5761fd06Alkis Evlogimenos if (srcReg == dstReg) 380e88280a4224730dcf8076e0d9a20973c5761fd06Alkis Evlogimenos continue; 381e88280a4224730dcf8076e0d9a20973c5761fd06Alkis Evlogimenos 382e88280a4224730dcf8076e0d9a20973c5761fd06Alkis Evlogimenos Reg2IntervalMap::iterator r2iSrc = r2iMap_.find(srcReg); 383e88280a4224730dcf8076e0d9a20973c5761fd06Alkis Evlogimenos assert(r2iSrc != r2iMap_.end()); 384e88280a4224730dcf8076e0d9a20973c5761fd06Alkis Evlogimenos Reg2IntervalMap::iterator r2iDst = r2iMap_.find(dstReg); 385e88280a4224730dcf8076e0d9a20973c5761fd06Alkis Evlogimenos assert(r2iDst != r2iMap_.end()); 386e88280a4224730dcf8076e0d9a20973c5761fd06Alkis Evlogimenos 387e88280a4224730dcf8076e0d9a20973c5761fd06Alkis Evlogimenos Intervals::iterator srcInt = r2iSrc->second; 388e88280a4224730dcf8076e0d9a20973c5761fd06Alkis Evlogimenos Intervals::iterator dstInt = r2iDst->second; 389e88280a4224730dcf8076e0d9a20973c5761fd06Alkis Evlogimenos 39079b0c3f0b9d91bbda354a2c6f22b6578655a5143Alkis Evlogimenos // src is a physical register 391e88280a4224730dcf8076e0d9a20973c5761fd06Alkis Evlogimenos if (srcInt->reg < MRegisterInfo::FirstVirtualRegister) { 392e88280a4224730dcf8076e0d9a20973c5761fd06Alkis Evlogimenos if (dstInt->reg == srcInt->reg || 393e88280a4224730dcf8076e0d9a20973c5761fd06Alkis Evlogimenos (dstInt->reg >= MRegisterInfo::FirstVirtualRegister && 39479b0c3f0b9d91bbda354a2c6f22b6578655a5143Alkis Evlogimenos !srcInt->overlaps(*dstInt) && 39579b0c3f0b9d91bbda354a2c6f22b6578655a5143Alkis Evlogimenos !overlapsAliases(*srcInt, *dstInt))) { 396e88280a4224730dcf8076e0d9a20973c5761fd06Alkis Evlogimenos srcInt->join(*dstInt); 397e88280a4224730dcf8076e0d9a20973c5761fd06Alkis Evlogimenos r2iDst->second = r2iSrc->second; 398e88280a4224730dcf8076e0d9a20973c5761fd06Alkis Evlogimenos r2rMap_.insert(std::make_pair(dstInt->reg, srcInt->reg)); 399e88280a4224730dcf8076e0d9a20973c5761fd06Alkis Evlogimenos intervals_.erase(dstInt); 400e88280a4224730dcf8076e0d9a20973c5761fd06Alkis Evlogimenos } 401e88280a4224730dcf8076e0d9a20973c5761fd06Alkis Evlogimenos } 40279b0c3f0b9d91bbda354a2c6f22b6578655a5143Alkis Evlogimenos // dst is a physical register 403e88280a4224730dcf8076e0d9a20973c5761fd06Alkis Evlogimenos else if (dstInt->reg < MRegisterInfo::FirstVirtualRegister) { 404e88280a4224730dcf8076e0d9a20973c5761fd06Alkis Evlogimenos if (srcInt->reg == dstInt->reg || 405e88280a4224730dcf8076e0d9a20973c5761fd06Alkis Evlogimenos (srcInt->reg >= MRegisterInfo::FirstVirtualRegister && 40679b0c3f0b9d91bbda354a2c6f22b6578655a5143Alkis Evlogimenos !dstInt->overlaps(*srcInt) && 40779b0c3f0b9d91bbda354a2c6f22b6578655a5143Alkis Evlogimenos !overlapsAliases(*dstInt, *srcInt))) { 408e88280a4224730dcf8076e0d9a20973c5761fd06Alkis Evlogimenos dstInt->join(*srcInt); 409e88280a4224730dcf8076e0d9a20973c5761fd06Alkis Evlogimenos r2iSrc->second = r2iDst->second; 410e88280a4224730dcf8076e0d9a20973c5761fd06Alkis Evlogimenos r2rMap_.insert(std::make_pair(srcInt->reg, dstInt->reg)); 411e88280a4224730dcf8076e0d9a20973c5761fd06Alkis Evlogimenos intervals_.erase(srcInt); 412e88280a4224730dcf8076e0d9a20973c5761fd06Alkis Evlogimenos } 413e88280a4224730dcf8076e0d9a20973c5761fd06Alkis Evlogimenos } 41479b0c3f0b9d91bbda354a2c6f22b6578655a5143Alkis Evlogimenos // neither src nor dst are physical registers 415e88280a4224730dcf8076e0d9a20973c5761fd06Alkis Evlogimenos else { 416e88280a4224730dcf8076e0d9a20973c5761fd06Alkis Evlogimenos const TargetRegisterClass *srcRc, *dstRc; 417e88280a4224730dcf8076e0d9a20973c5761fd06Alkis Evlogimenos srcRc = mf_->getSSARegMap()->getRegClass(srcInt->reg); 418e88280a4224730dcf8076e0d9a20973c5761fd06Alkis Evlogimenos dstRc = mf_->getSSARegMap()->getRegClass(dstInt->reg); 419e88280a4224730dcf8076e0d9a20973c5761fd06Alkis Evlogimenos 420e88280a4224730dcf8076e0d9a20973c5761fd06Alkis Evlogimenos if (srcRc == dstRc && !dstInt->overlaps(*srcInt)) { 421e88280a4224730dcf8076e0d9a20973c5761fd06Alkis Evlogimenos srcInt->join(*dstInt); 422e88280a4224730dcf8076e0d9a20973c5761fd06Alkis Evlogimenos r2iDst->second = r2iSrc->second; 423e88280a4224730dcf8076e0d9a20973c5761fd06Alkis Evlogimenos r2rMap_.insert(std::make_pair(dstInt->reg, srcInt->reg)); 424e88280a4224730dcf8076e0d9a20973c5761fd06Alkis Evlogimenos intervals_.erase(dstInt); 425e88280a4224730dcf8076e0d9a20973c5761fd06Alkis Evlogimenos } 426e88280a4224730dcf8076e0d9a20973c5761fd06Alkis Evlogimenos } 427e88280a4224730dcf8076e0d9a20973c5761fd06Alkis Evlogimenos } 428e88280a4224730dcf8076e0d9a20973c5761fd06Alkis Evlogimenos } 429dd2cc65f34f9b7bfda1cd0c42becedfc361d46f8Alkis Evlogimenos } 430e88280a4224730dcf8076e0d9a20973c5761fd06Alkis Evlogimenos 431e88280a4224730dcf8076e0d9a20973c5761fd06Alkis Evlogimenos intervals_.sort(StartPointComp()); 432e88280a4224730dcf8076e0d9a20973c5761fd06Alkis Evlogimenos DEBUG(std::copy(intervals_.begin(), intervals_.end(), 433e88280a4224730dcf8076e0d9a20973c5761fd06Alkis Evlogimenos std::ostream_iterator<Interval>(std::cerr, "\n"))); 434e88280a4224730dcf8076e0d9a20973c5761fd06Alkis Evlogimenos DEBUG(for (Reg2RegMap::const_iterator i = r2rMap_.begin(), 435e88280a4224730dcf8076e0d9a20973c5761fd06Alkis Evlogimenos e = r2rMap_.end(); i != e; ++i) 436e88280a4224730dcf8076e0d9a20973c5761fd06Alkis Evlogimenos std::cerr << i->first << " -> " << i->second << '\n';); 4374d46e1e521c0df1990ea50f8146d22bd77ea71a6Alkis Evlogimenos 438dd2cc65f34f9b7bfda1cd0c42becedfc361d46f8Alkis Evlogimenos} 439dd2cc65f34f9b7bfda1cd0c42becedfc361d46f8Alkis Evlogimenos 44079b0c3f0b9d91bbda354a2c6f22b6578655a5143Alkis Evlogimenosbool LiveIntervals::overlapsAliases(const Interval& lhs, 44179b0c3f0b9d91bbda354a2c6f22b6578655a5143Alkis Evlogimenos const Interval& rhs) const 44279b0c3f0b9d91bbda354a2c6f22b6578655a5143Alkis Evlogimenos{ 44379b0c3f0b9d91bbda354a2c6f22b6578655a5143Alkis Evlogimenos assert(lhs.reg < MRegisterInfo::FirstVirtualRegister && 44479b0c3f0b9d91bbda354a2c6f22b6578655a5143Alkis Evlogimenos "first interval must describe a physical register"); 44579b0c3f0b9d91bbda354a2c6f22b6578655a5143Alkis Evlogimenos 44679b0c3f0b9d91bbda354a2c6f22b6578655a5143Alkis Evlogimenos for (const unsigned* as = mri_->getAliasSet(lhs.reg); *as; ++as) { 44779b0c3f0b9d91bbda354a2c6f22b6578655a5143Alkis Evlogimenos Reg2IntervalMap::const_iterator r2i = r2iMap_.find(*as); 44879b0c3f0b9d91bbda354a2c6f22b6578655a5143Alkis Evlogimenos assert(r2i != r2iMap_.end() && "alias does not have interval?"); 44979b0c3f0b9d91bbda354a2c6f22b6578655a5143Alkis Evlogimenos if (rhs.overlaps(*r2i->second)) 45079b0c3f0b9d91bbda354a2c6f22b6578655a5143Alkis Evlogimenos return true; 45179b0c3f0b9d91bbda354a2c6f22b6578655a5143Alkis Evlogimenos } 45279b0c3f0b9d91bbda354a2c6f22b6578655a5143Alkis Evlogimenos 45379b0c3f0b9d91bbda354a2c6f22b6578655a5143Alkis Evlogimenos return false; 45479b0c3f0b9d91bbda354a2c6f22b6578655a5143Alkis Evlogimenos} 45579b0c3f0b9d91bbda354a2c6f22b6578655a5143Alkis Evlogimenos 456e88280a4224730dcf8076e0d9a20973c5761fd06Alkis EvlogimenosLiveIntervals::Interval::Interval(unsigned r) 457e88280a4224730dcf8076e0d9a20973c5761fd06Alkis Evlogimenos : reg(r), 458e88280a4224730dcf8076e0d9a20973c5761fd06Alkis Evlogimenos weight((r < MRegisterInfo::FirstVirtualRegister ? 459e88280a4224730dcf8076e0d9a20973c5761fd06Alkis Evlogimenos std::numeric_limits<float>::max() : 0.0F)) 460dd2cc65f34f9b7bfda1cd0c42becedfc361d46f8Alkis Evlogimenos{ 461e88280a4224730dcf8076e0d9a20973c5761fd06Alkis Evlogimenos 462dd2cc65f34f9b7bfda1cd0c42becedfc361d46f8Alkis Evlogimenos} 463dd2cc65f34f9b7bfda1cd0c42becedfc361d46f8Alkis Evlogimenos 464169cfd01964fc03828a7f2cad5d710890fbb08d8Alkis Evlogimenosbool LiveIntervals::Interval::liveAt(unsigned index) const 465169cfd01964fc03828a7f2cad5d710890fbb08d8Alkis Evlogimenos{ 46697017de1872e08ffcdde2fccdfd399647c1ccc4aAlkis Evlogimenos Range dummy(index, index+1); 46797017de1872e08ffcdde2fccdfd399647c1ccc4aAlkis Evlogimenos Ranges::const_iterator r = std::upper_bound(ranges.begin(), 46897017de1872e08ffcdde2fccdfd399647c1ccc4aAlkis Evlogimenos ranges.end(), 46997017de1872e08ffcdde2fccdfd399647c1ccc4aAlkis Evlogimenos dummy); 47097017de1872e08ffcdde2fccdfd399647c1ccc4aAlkis Evlogimenos if (r == ranges.begin()) 47197017de1872e08ffcdde2fccdfd399647c1ccc4aAlkis Evlogimenos return false; 47297017de1872e08ffcdde2fccdfd399647c1ccc4aAlkis Evlogimenos 47397017de1872e08ffcdde2fccdfd399647c1ccc4aAlkis Evlogimenos --r; 47497017de1872e08ffcdde2fccdfd399647c1ccc4aAlkis Evlogimenos return index >= r->first && index < (r->second - 1); 475169cfd01964fc03828a7f2cad5d710890fbb08d8Alkis Evlogimenos} 476169cfd01964fc03828a7f2cad5d710890fbb08d8Alkis Evlogimenos 477169cfd01964fc03828a7f2cad5d710890fbb08d8Alkis Evlogimenosbool LiveIntervals::Interval::overlaps(const Interval& other) const 478169cfd01964fc03828a7f2cad5d710890fbb08d8Alkis Evlogimenos{ 47980b378cf7c3dce77029dc3118e1f63bc6d389da1Alkis Evlogimenos Ranges::const_iterator i = ranges.begin(); 48097017de1872e08ffcdde2fccdfd399647c1ccc4aAlkis Evlogimenos Ranges::const_iterator ie = ranges.end(); 48180b378cf7c3dce77029dc3118e1f63bc6d389da1Alkis Evlogimenos Ranges::const_iterator j = other.ranges.begin(); 48297017de1872e08ffcdde2fccdfd399647c1ccc4aAlkis Evlogimenos Ranges::const_iterator je = other.ranges.end(); 48397017de1872e08ffcdde2fccdfd399647c1ccc4aAlkis Evlogimenos if (i->first < j->first) { 48497017de1872e08ffcdde2fccdfd399647c1ccc4aAlkis Evlogimenos i = std::upper_bound(i, ie, *j); 48597017de1872e08ffcdde2fccdfd399647c1ccc4aAlkis Evlogimenos if (i != ranges.begin()) --i; 48697017de1872e08ffcdde2fccdfd399647c1ccc4aAlkis Evlogimenos } 48797017de1872e08ffcdde2fccdfd399647c1ccc4aAlkis Evlogimenos else if (j->first < i->first) { 48897017de1872e08ffcdde2fccdfd399647c1ccc4aAlkis Evlogimenos j = std::upper_bound(j, je, *i); 48997017de1872e08ffcdde2fccdfd399647c1ccc4aAlkis Evlogimenos if (j != other.ranges.begin()) --j; 49097017de1872e08ffcdde2fccdfd399647c1ccc4aAlkis Evlogimenos } 49197017de1872e08ffcdde2fccdfd399647c1ccc4aAlkis Evlogimenos 49297017de1872e08ffcdde2fccdfd399647c1ccc4aAlkis Evlogimenos while (i != ie && j != je) { 49397017de1872e08ffcdde2fccdfd399647c1ccc4aAlkis Evlogimenos if (i->first == j->first) { 49497017de1872e08ffcdde2fccdfd399647c1ccc4aAlkis Evlogimenos return true; 49597017de1872e08ffcdde2fccdfd399647c1ccc4aAlkis Evlogimenos } 49697017de1872e08ffcdde2fccdfd399647c1ccc4aAlkis Evlogimenos else { 49797017de1872e08ffcdde2fccdfd399647c1ccc4aAlkis Evlogimenos if (i->first > j->first) { 49897017de1872e08ffcdde2fccdfd399647c1ccc4aAlkis Evlogimenos swap(i, j); 49997017de1872e08ffcdde2fccdfd399647c1ccc4aAlkis Evlogimenos swap(ie, je); 50097017de1872e08ffcdde2fccdfd399647c1ccc4aAlkis Evlogimenos } 50197017de1872e08ffcdde2fccdfd399647c1ccc4aAlkis Evlogimenos assert(i->first < j->first); 50280b378cf7c3dce77029dc3118e1f63bc6d389da1Alkis Evlogimenos 5039739736b94b1116be2043e05567aa8899593ab29Alkis Evlogimenos if ((i->second - 1) > j->first) { 50480b378cf7c3dce77029dc3118e1f63bc6d389da1Alkis Evlogimenos return true; 50580b378cf7c3dce77029dc3118e1f63bc6d389da1Alkis Evlogimenos } 50680b378cf7c3dce77029dc3118e1f63bc6d389da1Alkis Evlogimenos else { 50780b378cf7c3dce77029dc3118e1f63bc6d389da1Alkis Evlogimenos ++i; 50880b378cf7c3dce77029dc3118e1f63bc6d389da1Alkis Evlogimenos } 50980b378cf7c3dce77029dc3118e1f63bc6d389da1Alkis Evlogimenos } 510169cfd01964fc03828a7f2cad5d710890fbb08d8Alkis Evlogimenos } 511169cfd01964fc03828a7f2cad5d710890fbb08d8Alkis Evlogimenos 512169cfd01964fc03828a7f2cad5d710890fbb08d8Alkis Evlogimenos return false; 513169cfd01964fc03828a7f2cad5d710890fbb08d8Alkis Evlogimenos} 514169cfd01964fc03828a7f2cad5d710890fbb08d8Alkis Evlogimenos 515e88280a4224730dcf8076e0d9a20973c5761fd06Alkis Evlogimenosvoid LiveIntervals::Interval::addRange(unsigned start, unsigned end) 516e88280a4224730dcf8076e0d9a20973c5761fd06Alkis Evlogimenos{ 517e88280a4224730dcf8076e0d9a20973c5761fd06Alkis Evlogimenos DEBUG(std::cerr << "\t\t\tadding range: [" << start <<','<< end << ") -> "); 518e88280a4224730dcf8076e0d9a20973c5761fd06Alkis Evlogimenos //assert(start < end && "invalid range?"); 519e88280a4224730dcf8076e0d9a20973c5761fd06Alkis Evlogimenos Range range = std::make_pair(start, end); 520e88280a4224730dcf8076e0d9a20973c5761fd06Alkis Evlogimenos Ranges::iterator it = 521e88280a4224730dcf8076e0d9a20973c5761fd06Alkis Evlogimenos ranges.insert(std::upper_bound(ranges.begin(), ranges.end(), range), 522e88280a4224730dcf8076e0d9a20973c5761fd06Alkis Evlogimenos range); 523e88280a4224730dcf8076e0d9a20973c5761fd06Alkis Evlogimenos 524e88280a4224730dcf8076e0d9a20973c5761fd06Alkis Evlogimenos it = mergeRangesForward(it); 525e88280a4224730dcf8076e0d9a20973c5761fd06Alkis Evlogimenos it = mergeRangesBackward(it); 526e88280a4224730dcf8076e0d9a20973c5761fd06Alkis Evlogimenos DEBUG(std::cerr << "\t\t\t\tafter merging: " << *this << '\n'); 527e88280a4224730dcf8076e0d9a20973c5761fd06Alkis Evlogimenos} 528e88280a4224730dcf8076e0d9a20973c5761fd06Alkis Evlogimenos 529e88280a4224730dcf8076e0d9a20973c5761fd06Alkis Evlogimenosvoid LiveIntervals::Interval::join(const LiveIntervals::Interval& other) 530e88280a4224730dcf8076e0d9a20973c5761fd06Alkis Evlogimenos{ 531e88280a4224730dcf8076e0d9a20973c5761fd06Alkis Evlogimenos DEBUG(std::cerr << "\t\t\t\tjoining intervals: " 532e88280a4224730dcf8076e0d9a20973c5761fd06Alkis Evlogimenos << other << " and " << *this << '\n'); 533e88280a4224730dcf8076e0d9a20973c5761fd06Alkis Evlogimenos Ranges::iterator cur = ranges.begin(); 534e88280a4224730dcf8076e0d9a20973c5761fd06Alkis Evlogimenos 535e88280a4224730dcf8076e0d9a20973c5761fd06Alkis Evlogimenos for (Ranges::const_iterator i = other.ranges.begin(), 536e88280a4224730dcf8076e0d9a20973c5761fd06Alkis Evlogimenos e = other.ranges.end(); i != e; ++i) { 537e88280a4224730dcf8076e0d9a20973c5761fd06Alkis Evlogimenos cur = ranges.insert(std::upper_bound(cur, ranges.end(), *i), *i); 538e88280a4224730dcf8076e0d9a20973c5761fd06Alkis Evlogimenos cur = mergeRangesForward(cur); 539e88280a4224730dcf8076e0d9a20973c5761fd06Alkis Evlogimenos cur = mergeRangesBackward(cur); 540e88280a4224730dcf8076e0d9a20973c5761fd06Alkis Evlogimenos } 541e88280a4224730dcf8076e0d9a20973c5761fd06Alkis Evlogimenos if (reg >= MRegisterInfo::FirstVirtualRegister) 542e88280a4224730dcf8076e0d9a20973c5761fd06Alkis Evlogimenos weight += other.weight; 543e88280a4224730dcf8076e0d9a20973c5761fd06Alkis Evlogimenos 544e88280a4224730dcf8076e0d9a20973c5761fd06Alkis Evlogimenos DEBUG(std::cerr << "\t\t\t\tafter merging: " << *this << '\n'); 545e88280a4224730dcf8076e0d9a20973c5761fd06Alkis Evlogimenos} 546e88280a4224730dcf8076e0d9a20973c5761fd06Alkis Evlogimenos 547e88280a4224730dcf8076e0d9a20973c5761fd06Alkis EvlogimenosLiveIntervals::Interval::Ranges::iterator 548e88280a4224730dcf8076e0d9a20973c5761fd06Alkis EvlogimenosLiveIntervals::Interval::mergeRangesForward(Ranges::iterator it) 549e88280a4224730dcf8076e0d9a20973c5761fd06Alkis Evlogimenos{ 550e88280a4224730dcf8076e0d9a20973c5761fd06Alkis Evlogimenos for (Ranges::iterator next = it + 1; 551e88280a4224730dcf8076e0d9a20973c5761fd06Alkis Evlogimenos next != ranges.end() && it->second >= next->first; ) { 552e88280a4224730dcf8076e0d9a20973c5761fd06Alkis Evlogimenos it->second = std::max(it->second, next->second); 553e88280a4224730dcf8076e0d9a20973c5761fd06Alkis Evlogimenos next = ranges.erase(next); 554e88280a4224730dcf8076e0d9a20973c5761fd06Alkis Evlogimenos } 555e88280a4224730dcf8076e0d9a20973c5761fd06Alkis Evlogimenos return it; 556e88280a4224730dcf8076e0d9a20973c5761fd06Alkis Evlogimenos} 557e88280a4224730dcf8076e0d9a20973c5761fd06Alkis Evlogimenos 558e88280a4224730dcf8076e0d9a20973c5761fd06Alkis EvlogimenosLiveIntervals::Interval::Ranges::iterator 559e88280a4224730dcf8076e0d9a20973c5761fd06Alkis EvlogimenosLiveIntervals::Interval::mergeRangesBackward(Ranges::iterator it) 560e88280a4224730dcf8076e0d9a20973c5761fd06Alkis Evlogimenos{ 5614d46e1e521c0df1990ea50f8146d22bd77ea71a6Alkis Evlogimenos for (Ranges::iterator prev = it - 1; 5624d46e1e521c0df1990ea50f8146d22bd77ea71a6Alkis Evlogimenos it != ranges.begin() && it->first <= prev->second; ) { 563e88280a4224730dcf8076e0d9a20973c5761fd06Alkis Evlogimenos it->first = std::min(it->first, prev->first); 564e88280a4224730dcf8076e0d9a20973c5761fd06Alkis Evlogimenos it->second = std::max(it->second, prev->second); 565e88280a4224730dcf8076e0d9a20973c5761fd06Alkis Evlogimenos it = ranges.erase(prev); 5664d46e1e521c0df1990ea50f8146d22bd77ea71a6Alkis Evlogimenos prev = it - 1; 567e88280a4224730dcf8076e0d9a20973c5761fd06Alkis Evlogimenos } 568e88280a4224730dcf8076e0d9a20973c5761fd06Alkis Evlogimenos 569e88280a4224730dcf8076e0d9a20973c5761fd06Alkis Evlogimenos return it; 570e88280a4224730dcf8076e0d9a20973c5761fd06Alkis Evlogimenos} 571e88280a4224730dcf8076e0d9a20973c5761fd06Alkis Evlogimenos 572b27ef248f579b354aab434f63c417ab1103e47e2Alkis Evlogimenosstd::ostream& llvm::operator<<(std::ostream& os, 573b27ef248f579b354aab434f63c417ab1103e47e2Alkis Evlogimenos const LiveIntervals::Interval& li) 574b27ef248f579b354aab434f63c417ab1103e47e2Alkis Evlogimenos{ 575169cfd01964fc03828a7f2cad5d710890fbb08d8Alkis Evlogimenos os << "%reg" << li.reg << ',' << li.weight << " = "; 576b27ef248f579b354aab434f63c417ab1103e47e2Alkis Evlogimenos for (LiveIntervals::Interval::Ranges::const_iterator 577b27ef248f579b354aab434f63c417ab1103e47e2Alkis Evlogimenos i = li.ranges.begin(), e = li.ranges.end(); i != e; ++i) { 57863841bc85d15ca0ce1b3208084f4262f3d33ef21Alkis Evlogimenos os << "[" << i->first << "," << i->second << ")"; 579b27ef248f579b354aab434f63c417ab1103e47e2Alkis Evlogimenos } 580b27ef248f579b354aab434f63c417ab1103e47e2Alkis Evlogimenos return os; 581b27ef248f579b354aab434f63c417ab1103e47e2Alkis Evlogimenos} 582