LiveIntervalAnalysis.cpp revision be766c72464116a445a02b542a450c4274bab5d0
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" 334d46e1e521c0df1990ea50f8146d22bd77ea71a6Alkis Evlogimenos#include <cmath> 34ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos#include <iostream> 356b4edbaaf9021e0434f0ce0c3724eb43ed41b770Alkis Evlogimenos#include <limits> 36ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos 37ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenosusing namespace llvm; 38ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos 39ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenosnamespace { 40ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos RegisterAnalysis<LiveIntervals> X("liveintervals", 41ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos "Live Interval Analysis"); 42ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos 43ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos Statistic<> numIntervals("liveintervals", "Number of intervals"); 44b180e3e92ba8783b1f93995c98dfe1634c5f9205Alkis Evlogimenos Statistic<> numJoined ("liveintervals", "Number of joined intervals"); 45e88280a4224730dcf8076e0d9a20973c5761fd06Alkis Evlogimenos 46e88280a4224730dcf8076e0d9a20973c5761fd06Alkis Evlogimenos cl::opt<bool> 47e88280a4224730dcf8076e0d9a20973c5761fd06Alkis Evlogimenos join("join-liveintervals", 48e88280a4224730dcf8076e0d9a20973c5761fd06Alkis Evlogimenos cl::desc("Join compatible live intervals"), 4979b0c3f0b9d91bbda354a2c6f22b6578655a5143Alkis Evlogimenos cl::init(true)); 50ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos}; 51ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos 52ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenosvoid LiveIntervals::getAnalysisUsage(AnalysisUsage &AU) const 53ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos{ 54f6f91bf6680668990ff3804b14cf05beedc56ec4Alkis Evlogimenos AU.addPreserved<LiveVariables>(); 55ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos AU.addRequired<LiveVariables>(); 56f6f91bf6680668990ff3804b14cf05beedc56ec4Alkis Evlogimenos AU.addPreservedID(PHIEliminationID); 57ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos AU.addRequiredID(PHIEliminationID); 584c080863de86448d905beab27686da823b6d44c1Alkis Evlogimenos AU.addRequiredID(TwoAddressInstructionPassID); 596b4edbaaf9021e0434f0ce0c3724eb43ed41b770Alkis Evlogimenos AU.addRequired<LoopInfo>(); 60ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos MachineFunctionPass::getAnalysisUsage(AU); 61ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos} 62ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos 6308cec00588ec1a8fa85b208555f006d7396ae7a4Alkis Evlogimenosvoid LiveIntervals::releaseMemory() 6408cec00588ec1a8fa85b208555f006d7396ae7a4Alkis Evlogimenos{ 6508cec00588ec1a8fa85b208555f006d7396ae7a4Alkis Evlogimenos mbbi2mbbMap_.clear(); 6608cec00588ec1a8fa85b208555f006d7396ae7a4Alkis Evlogimenos mi2iMap_.clear(); 6708cec00588ec1a8fa85b208555f006d7396ae7a4Alkis Evlogimenos r2iMap_.clear(); 6808cec00588ec1a8fa85b208555f006d7396ae7a4Alkis Evlogimenos r2iMap_.clear(); 6908cec00588ec1a8fa85b208555f006d7396ae7a4Alkis Evlogimenos r2rMap_.clear(); 7008cec00588ec1a8fa85b208555f006d7396ae7a4Alkis Evlogimenos intervals_.clear(); 7108cec00588ec1a8fa85b208555f006d7396ae7a4Alkis Evlogimenos} 7208cec00588ec1a8fa85b208555f006d7396ae7a4Alkis Evlogimenos 7308cec00588ec1a8fa85b208555f006d7396ae7a4Alkis Evlogimenos 74ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos/// runOnMachineFunction - Register allocate the whole function 75ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos/// 76ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenosbool LiveIntervals::runOnMachineFunction(MachineFunction &fn) { 77ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos DEBUG(std::cerr << "Machine Function\n"); 78ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos mf_ = &fn; 79ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos tm_ = &fn.getTarget(); 80ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos mri_ = tm_->getRegisterInfo(); 81ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos lv_ = &getAnalysis<LiveVariables>(); 82ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos 83ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos // number MachineInstrs 84ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos unsigned miIndex = 0; 85ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos for (MachineFunction::iterator mbb = mf_->begin(), mbbEnd = mf_->end(); 86ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos mbb != mbbEnd; ++mbb) { 87ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos const std::pair<MachineBasicBlock*, unsigned>& entry = 8808cec00588ec1a8fa85b208555f006d7396ae7a4Alkis Evlogimenos lv_->getMachineBasicBlockInfo(mbb); 89ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos bool inserted = mbbi2mbbMap_.insert(std::make_pair(entry.second, 90ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos entry.first)).second; 91ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos assert(inserted && "multiple index -> MachineBasicBlock"); 92ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos 93ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos for (MachineBasicBlock::iterator mi = mbb->begin(), miEnd = mbb->end(); 94ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos mi != miEnd; ++mi) { 95c0b9dc5be79f009d260edb5cd5e1d8346587aaa2Alkis Evlogimenos inserted = mi2iMap_.insert(std::make_pair(mi, miIndex)).second; 96ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos assert(inserted && "multiple MachineInstr -> index mappings"); 970b8cb2bc47a6bee59c8c3f46d4cc047badf7f8acAlkis Evlogimenos miIndex += 2; 98ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos } 99ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos } 100ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos 101ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos computeIntervals(); 102ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos 1037a40eaaceec0af76d5b97610f3d4e7a47a19d245Alkis Evlogimenos // compute spill weights 1047a40eaaceec0af76d5b97610f3d4e7a47a19d245Alkis Evlogimenos const LoopInfo& loopInfo = getAnalysis<LoopInfo>(); 10526bfc08b80c904c71487ac1ab49a8b3a15a8d3e9Alkis Evlogimenos const TargetInstrInfo& tii = tm_->getInstrInfo(); 1067a40eaaceec0af76d5b97610f3d4e7a47a19d245Alkis Evlogimenos 107e88280a4224730dcf8076e0d9a20973c5761fd06Alkis Evlogimenos for (MachineFunction::const_iterator mbbi = mf_->begin(), 108e88280a4224730dcf8076e0d9a20973c5761fd06Alkis Evlogimenos mbbe = mf_->end(); mbbi != mbbe; ++mbbi) { 109e88280a4224730dcf8076e0d9a20973c5761fd06Alkis Evlogimenos const MachineBasicBlock* mbb = mbbi; 1107a40eaaceec0af76d5b97610f3d4e7a47a19d245Alkis Evlogimenos unsigned loopDepth = loopInfo.getLoopDepth(mbb->getBasicBlock()); 1117a40eaaceec0af76d5b97610f3d4e7a47a19d245Alkis Evlogimenos 112c0b9dc5be79f009d260edb5cd5e1d8346587aaa2Alkis Evlogimenos for (MachineBasicBlock::const_iterator mi = mbb->begin(), 113c0b9dc5be79f009d260edb5cd5e1d8346587aaa2Alkis Evlogimenos mie = mbb->end(); mi != mie; ++mi) { 114b606eaca1b149ef74c578a6a11d65339c125edabAlkis Evlogimenos for (int i = mi->getNumOperands() - 1; i >= 0; --i) { 115c0b9dc5be79f009d260edb5cd5e1d8346587aaa2Alkis Evlogimenos const MachineOperand& mop = mi->getOperand(i); 1161cbe4d0ad0888e50858cca83cf2a0d3083709513Chris Lattner if (mop.isRegister() && 1171cbe4d0ad0888e50858cca83cf2a0d3083709513Chris Lattner MRegisterInfo::isVirtualRegister(mop.getReg())) { 118be766c72464116a445a02b542a450c4274bab5d0Alkis Evlogimenos unsigned reg = mop.getReg(); 11908cec00588ec1a8fa85b208555f006d7396ae7a4Alkis Evlogimenos Reg2IntervalMap::iterator r2iit = r2iMap_.find(reg); 12008cec00588ec1a8fa85b208555f006d7396ae7a4Alkis Evlogimenos assert(r2iit != r2iMap_.end()); 12108cec00588ec1a8fa85b208555f006d7396ae7a4Alkis Evlogimenos r2iit->second->weight += pow(10.0F, loopDepth); 12208cec00588ec1a8fa85b208555f006d7396ae7a4Alkis Evlogimenos } 1237a40eaaceec0af76d5b97610f3d4e7a47a19d245Alkis Evlogimenos } 1247a40eaaceec0af76d5b97610f3d4e7a47a19d245Alkis Evlogimenos } 1257a40eaaceec0af76d5b97610f3d4e7a47a19d245Alkis Evlogimenos } 1267a40eaaceec0af76d5b97610f3d4e7a47a19d245Alkis Evlogimenos 127e88280a4224730dcf8076e0d9a20973c5761fd06Alkis Evlogimenos // join intervals if requested 128e88280a4224730dcf8076e0d9a20973c5761fd06Alkis Evlogimenos if (join) joinIntervals(); 129e88280a4224730dcf8076e0d9a20973c5761fd06Alkis Evlogimenos 130d6e40a6cbced8265334ee0375f5996098dfdccb2Alkis Evlogimenos numIntervals += intervals_.size(); 131d6e40a6cbced8265334ee0375f5996098dfdccb2Alkis Evlogimenos 13201e74a2aab64c5901a62d9ba9e1c263759929390Alkis Evlogimenos intervals_.sort(StartPointComp()); 13301e74a2aab64c5901a62d9ba9e1c263759929390Alkis Evlogimenos DEBUG(std::copy(intervals_.begin(), intervals_.end(), 13401e74a2aab64c5901a62d9ba9e1c263759929390Alkis Evlogimenos std::ostream_iterator<Interval>(std::cerr, "\n"))); 135ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos return true; 136ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos} 137ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos 138ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenosvoid LiveIntervals::printRegName(unsigned reg) const 139ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos{ 1404f67b8664889d9e93b452a9a5f099d41d1bd235aAlkis Evlogimenos if (MRegisterInfo::isPhysicalRegister(reg)) 141ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos std::cerr << mri_->getName(reg); 142ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos else 143ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos std::cerr << '%' << reg; 144ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos} 145ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos 146ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenosvoid LiveIntervals::handleVirtualRegisterDef(MachineBasicBlock* mbb, 147ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos MachineBasicBlock::iterator mi, 148ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos unsigned reg) 149ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos{ 150a3a6524965416647883bc0b78ff6f18fb3f7b5fcAlkis Evlogimenos DEBUG(std::cerr << "\t\tregister: ";printRegName(reg); std::cerr << '\n'); 151ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos 152ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos LiveVariables::VarInfo& vi = lv_->getVarInfo(reg); 153ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos 154dd2cc65f34f9b7bfda1cd0c42becedfc361d46f8Alkis Evlogimenos Interval* interval = 0; 15508cec00588ec1a8fa85b208555f006d7396ae7a4Alkis Evlogimenos Reg2IntervalMap::iterator r2iit = r2iMap_.lower_bound(reg); 15608cec00588ec1a8fa85b208555f006d7396ae7a4Alkis Evlogimenos if (r2iit == r2iMap_.end() || r2iit->first != reg) { 157ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos // add new interval 158ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos intervals_.push_back(Interval(reg)); 159ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos // update interval index for this register 16008cec00588ec1a8fa85b208555f006d7396ae7a4Alkis Evlogimenos r2iMap_.insert(r2iit, std::make_pair(reg, --intervals_.end())); 161dd2cc65f34f9b7bfda1cd0c42becedfc361d46f8Alkis Evlogimenos interval = &intervals_.back(); 162ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos 163ad48cd6327df13ad4b8530733bbf115224bf9562Alkis Evlogimenos // iterate over all of the blocks that the variable is 164ad48cd6327df13ad4b8530733bbf115224bf9562Alkis Evlogimenos // completely live in, adding them to the live 165ad48cd6327df13ad4b8530733bbf115224bf9562Alkis Evlogimenos // interval. obviously we only need to do this once. 166ad48cd6327df13ad4b8530733bbf115224bf9562Alkis Evlogimenos for (unsigned i = 0, e = vi.AliveBlocks.size(); i != e; ++i) { 167ad48cd6327df13ad4b8530733bbf115224bf9562Alkis Evlogimenos if (vi.AliveBlocks[i]) { 168ad48cd6327df13ad4b8530733bbf115224bf9562Alkis Evlogimenos MachineBasicBlock* mbb = lv_->getIndexMachineBasicBlock(i); 169ad48cd6327df13ad4b8530733bbf115224bf9562Alkis Evlogimenos if (!mbb->empty()) { 170c0b9dc5be79f009d260edb5cd5e1d8346587aaa2Alkis Evlogimenos interval->addRange(getInstructionIndex(&mbb->front()), 171c0b9dc5be79f009d260edb5cd5e1d8346587aaa2Alkis Evlogimenos getInstructionIndex(&mbb->back()) + 1); 172ad48cd6327df13ad4b8530733bbf115224bf9562Alkis Evlogimenos } 17352220f61bba91ab787d4cc0aee47df4e2ca55c04Alkis Evlogimenos } 174ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos } 175dd2cc65f34f9b7bfda1cd0c42becedfc361d46f8Alkis Evlogimenos } 176ad48cd6327df13ad4b8530733bbf115224bf9562Alkis Evlogimenos else { 177ad48cd6327df13ad4b8530733bbf115224bf9562Alkis Evlogimenos interval = &*r2iit->second; 178ad48cd6327df13ad4b8530733bbf115224bf9562Alkis Evlogimenos } 179ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos 1800b8cb2bc47a6bee59c8c3f46d4cc047badf7f8acAlkis Evlogimenos // we consider defs to happen at the second time slot of the 1810b8cb2bc47a6bee59c8c3f46d4cc047badf7f8acAlkis Evlogimenos // instruction 182c0b9dc5be79f009d260edb5cd5e1d8346587aaa2Alkis Evlogimenos unsigned instrIndex = getInstructionIndex(mi) + 1; 1830b8cb2bc47a6bee59c8c3f46d4cc047badf7f8acAlkis Evlogimenos 184dd2cc65f34f9b7bfda1cd0c42becedfc361d46f8Alkis Evlogimenos bool killedInDefiningBasicBlock = false; 185dd2cc65f34f9b7bfda1cd0c42becedfc361d46f8Alkis Evlogimenos for (int i = 0, e = vi.Kills.size(); i != e; ++i) { 186dd2cc65f34f9b7bfda1cd0c42becedfc361d46f8Alkis Evlogimenos MachineBasicBlock* killerBlock = vi.Kills[i].first; 187dd2cc65f34f9b7bfda1cd0c42becedfc361d46f8Alkis Evlogimenos MachineInstr* killerInstr = vi.Kills[i].second; 188dd2cc65f34f9b7bfda1cd0c42becedfc361d46f8Alkis Evlogimenos unsigned start = (mbb == killerBlock ? 189dd2cc65f34f9b7bfda1cd0c42becedfc361d46f8Alkis Evlogimenos instrIndex : 190c0b9dc5be79f009d260edb5cd5e1d8346587aaa2Alkis Evlogimenos getInstructionIndex(&killerBlock->front())); 191c0b9dc5be79f009d260edb5cd5e1d8346587aaa2Alkis Evlogimenos unsigned end = (killerInstr == mi ? 1920b8cb2bc47a6bee59c8c3f46d4cc047badf7f8acAlkis Evlogimenos instrIndex + 1 : // dead 1930b8cb2bc47a6bee59c8c3f46d4cc047badf7f8acAlkis Evlogimenos getInstructionIndex(killerInstr) + 1); // killed 19408cec00588ec1a8fa85b208555f006d7396ae7a4Alkis Evlogimenos // we do not want to add invalid ranges. these can happen when 19508cec00588ec1a8fa85b208555f006d7396ae7a4Alkis Evlogimenos // a variable has its latest use and is redefined later on in 19608cec00588ec1a8fa85b208555f006d7396ae7a4Alkis Evlogimenos // the same basic block (common with variables introduced by 19708cec00588ec1a8fa85b208555f006d7396ae7a4Alkis Evlogimenos // PHI elimination) 19843f692f90f6b27304570e1b1807542dff4b8e847Alkis Evlogimenos if (start < end) { 19943f692f90f6b27304570e1b1807542dff4b8e847Alkis Evlogimenos killedInDefiningBasicBlock |= mbb == killerBlock; 20043f692f90f6b27304570e1b1807542dff4b8e847Alkis Evlogimenos interval->addRange(start, end); 20143f692f90f6b27304570e1b1807542dff4b8e847Alkis Evlogimenos } 202dd2cc65f34f9b7bfda1cd0c42becedfc361d46f8Alkis Evlogimenos } 203ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos 204dd2cc65f34f9b7bfda1cd0c42becedfc361d46f8Alkis Evlogimenos if (!killedInDefiningBasicBlock) { 205c0b9dc5be79f009d260edb5cd5e1d8346587aaa2Alkis Evlogimenos unsigned end = getInstructionIndex(&mbb->back()) + 1; 206dd2cc65f34f9b7bfda1cd0c42becedfc361d46f8Alkis Evlogimenos interval->addRange(instrIndex, end); 207ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos } 208ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos} 209ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos 210ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenosvoid LiveIntervals::handlePhysicalRegisterDef(MachineBasicBlock* mbb, 211ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos MachineBasicBlock::iterator mi, 212ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos unsigned reg) 213ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos{ 21402ba13c9897ae2b19f9201e57460d7ee2b753a0bAlkis Evlogimenos typedef LiveVariables::killed_iterator KillIter; 21502ba13c9897ae2b19f9201e57460d7ee2b753a0bAlkis Evlogimenos 2161a119e24106810310825f44c7bfd232d3272e639Alkis Evlogimenos DEBUG(std::cerr << "\t\tregister: "; printRegName(reg)); 217ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos 21802ba13c9897ae2b19f9201e57460d7ee2b753a0bAlkis Evlogimenos MachineBasicBlock::iterator e = mbb->end(); 2190b8cb2bc47a6bee59c8c3f46d4cc047badf7f8acAlkis Evlogimenos // we consider defs to happen at the second time slot of the 2200b8cb2bc47a6bee59c8c3f46d4cc047badf7f8acAlkis Evlogimenos // instruction 2210b8cb2bc47a6bee59c8c3f46d4cc047badf7f8acAlkis Evlogimenos unsigned start, end; 222c0b9dc5be79f009d260edb5cd5e1d8346587aaa2Alkis Evlogimenos start = end = getInstructionIndex(mi) + 1; 2234d46e1e521c0df1990ea50f8146d22bd77ea71a6Alkis Evlogimenos 22402ba13c9897ae2b19f9201e57460d7ee2b753a0bAlkis Evlogimenos // a variable can be dead by the instruction defining it 225c0b9dc5be79f009d260edb5cd5e1d8346587aaa2Alkis Evlogimenos for (KillIter ki = lv_->dead_begin(mi), ke = lv_->dead_end(mi); 226af25473d5e99e0c0968746e12d8827e4b712bd31Alkis Evlogimenos ki != ke; ++ki) { 227af25473d5e99e0c0968746e12d8827e4b712bd31Alkis Evlogimenos if (reg == ki->second) { 228af25473d5e99e0c0968746e12d8827e4b712bd31Alkis Evlogimenos DEBUG(std::cerr << " dead\n"); 2290b8cb2bc47a6bee59c8c3f46d4cc047badf7f8acAlkis Evlogimenos ++end; 230af25473d5e99e0c0968746e12d8827e4b712bd31Alkis Evlogimenos goto exit; 231af25473d5e99e0c0968746e12d8827e4b712bd31Alkis Evlogimenos } 232af25473d5e99e0c0968746e12d8827e4b712bd31Alkis Evlogimenos } 233ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos 23402ba13c9897ae2b19f9201e57460d7ee2b753a0bAlkis Evlogimenos // a variable can only be killed by subsequent instructions 23502ba13c9897ae2b19f9201e57460d7ee2b753a0bAlkis Evlogimenos do { 23602ba13c9897ae2b19f9201e57460d7ee2b753a0bAlkis Evlogimenos ++mi; 2370b8cb2bc47a6bee59c8c3f46d4cc047badf7f8acAlkis Evlogimenos end += 2; 238c0b9dc5be79f009d260edb5cd5e1d8346587aaa2Alkis Evlogimenos for (KillIter ki = lv_->killed_begin(mi), ke = lv_->killed_end(mi); 2394d46e1e521c0df1990ea50f8146d22bd77ea71a6Alkis Evlogimenos ki != ke; ++ki) { 2404d46e1e521c0df1990ea50f8146d22bd77ea71a6Alkis Evlogimenos if (reg == ki->second) { 2414d46e1e521c0df1990ea50f8146d22bd77ea71a6Alkis Evlogimenos DEBUG(std::cerr << " killed\n"); 2424d46e1e521c0df1990ea50f8146d22bd77ea71a6Alkis Evlogimenos goto exit; 243ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos } 2444d46e1e521c0df1990ea50f8146d22bd77ea71a6Alkis Evlogimenos } 24502ba13c9897ae2b19f9201e57460d7ee2b753a0bAlkis Evlogimenos } while (mi != e); 24602ba13c9897ae2b19f9201e57460d7ee2b753a0bAlkis Evlogimenos 247ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenosexit: 248ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos assert(start < end && "did not find end of interval?"); 249ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos 25008cec00588ec1a8fa85b208555f006d7396ae7a4Alkis Evlogimenos Reg2IntervalMap::iterator r2iit = r2iMap_.lower_bound(reg); 25108cec00588ec1a8fa85b208555f006d7396ae7a4Alkis Evlogimenos if (r2iit != r2iMap_.end() && r2iit->first == reg) { 25208cec00588ec1a8fa85b208555f006d7396ae7a4Alkis Evlogimenos r2iit->second->addRange(start, end); 253ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos } 254ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos else { 255ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos intervals_.push_back(Interval(reg)); 256ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos // update interval index for this register 25708cec00588ec1a8fa85b208555f006d7396ae7a4Alkis Evlogimenos r2iMap_.insert(r2iit, std::make_pair(reg, --intervals_.end())); 25808cec00588ec1a8fa85b208555f006d7396ae7a4Alkis Evlogimenos intervals_.back().addRange(start, end); 259ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos } 260ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos} 261ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos 262ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenosvoid LiveIntervals::handleRegisterDef(MachineBasicBlock* mbb, 263ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos MachineBasicBlock::iterator mi, 264ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos unsigned reg) 265ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos{ 2664f67b8664889d9e93b452a9a5f099d41d1bd235aAlkis Evlogimenos if (MRegisterInfo::isPhysicalRegister(reg)) { 2671a119e24106810310825f44c7bfd232d3272e639Alkis Evlogimenos if (lv_->getAllocatablePhysicalRegisters()[reg]) { 268ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos handlePhysicalRegisterDef(mbb, mi, reg); 26919b6486d3891c8a02a301aa1b44348a420772fcfAlkis Evlogimenos for (const unsigned* as = mri_->getAliasSet(reg); *as; ++as) 27019b6486d3891c8a02a301aa1b44348a420772fcfAlkis Evlogimenos handlePhysicalRegisterDef(mbb, mi, *as); 271ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos } 272ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos } 273ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos else { 274ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos handleVirtualRegisterDef(mbb, mi, reg); 275ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos } 276ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos} 277ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos 2784d46e1e521c0df1990ea50f8146d22bd77ea71a6Alkis Evlogimenosunsigned LiveIntervals::getInstructionIndex(MachineInstr* instr) const 2794d46e1e521c0df1990ea50f8146d22bd77ea71a6Alkis Evlogimenos{ 2804d46e1e521c0df1990ea50f8146d22bd77ea71a6Alkis Evlogimenos assert(mi2iMap_.find(instr) != mi2iMap_.end() && 2814d46e1e521c0df1990ea50f8146d22bd77ea71a6Alkis Evlogimenos "instruction not assigned a number"); 2824d46e1e521c0df1990ea50f8146d22bd77ea71a6Alkis Evlogimenos return mi2iMap_.find(instr)->second; 2834d46e1e521c0df1990ea50f8146d22bd77ea71a6Alkis Evlogimenos} 2844d46e1e521c0df1990ea50f8146d22bd77ea71a6Alkis Evlogimenos 285ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos/// computeIntervals - computes the live intervals for virtual 2864d46e1e521c0df1990ea50f8146d22bd77ea71a6Alkis Evlogimenos/// registers. for some ordering of the machine instructions [1,N] a 28708cec00588ec1a8fa85b208555f006d7396ae7a4Alkis Evlogimenos/// live interval is an interval [i, j) where 1 <= i <= j < N for 288ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos/// which a variable is live 289ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenosvoid LiveIntervals::computeIntervals() 290ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos{ 291ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos DEBUG(std::cerr << "computing live intervals:\n"); 292ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos 293ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos for (MbbIndex2MbbMap::iterator 294ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos it = mbbi2mbbMap_.begin(), itEnd = mbbi2mbbMap_.end(); 295ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos it != itEnd; ++it) { 296ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos MachineBasicBlock* mbb = it->second; 297ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos DEBUG(std::cerr << "machine basic block: " 298ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos << mbb->getBasicBlock()->getName() << "\n"); 2996b4edbaaf9021e0434f0ce0c3724eb43ed41b770Alkis Evlogimenos 300ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos for (MachineBasicBlock::iterator mi = mbb->begin(), miEnd = mbb->end(); 301ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos mi != miEnd; ++mi) { 302ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos const TargetInstrDescriptor& tid = 303c0b9dc5be79f009d260edb5cd5e1d8346587aaa2Alkis Evlogimenos tm_->getInstrInfo().get(mi->getOpcode()); 304c0b9dc5be79f009d260edb5cd5e1d8346587aaa2Alkis Evlogimenos DEBUG(std::cerr << "\t[" << getInstructionIndex(mi) << "] "; 305c0b9dc5be79f009d260edb5cd5e1d8346587aaa2Alkis Evlogimenos mi->print(std::cerr, *tm_);); 306ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos 307ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos // handle implicit defs 30819b6486d3891c8a02a301aa1b44348a420772fcfAlkis Evlogimenos for (const unsigned* id = tid.ImplicitDefs; *id; ++id) 30919b6486d3891c8a02a301aa1b44348a420772fcfAlkis Evlogimenos handleRegisterDef(mbb, mi, *id); 310ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos 311ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos // handle explicit defs 312c0b9dc5be79f009d260edb5cd5e1d8346587aaa2Alkis Evlogimenos for (int i = mi->getNumOperands() - 1; i >= 0; --i) { 313c0b9dc5be79f009d260edb5cd5e1d8346587aaa2Alkis Evlogimenos MachineOperand& mop = mi->getOperand(i); 31408cec00588ec1a8fa85b208555f006d7396ae7a4Alkis Evlogimenos // handle register defs - build intervals 31508cec00588ec1a8fa85b208555f006d7396ae7a4Alkis Evlogimenos if (mop.isRegister() && mop.isDef()) 316be766c72464116a445a02b542a450c4274bab5d0Alkis Evlogimenos handleRegisterDef(mbb, mi, mop.getReg()); 317ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos } 318ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos } 319ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos } 320ff0cbe175df40e0d2b36e59c6fb72f211f1cba4cAlkis Evlogimenos} 321b27ef248f579b354aab434f63c417ab1103e47e2Alkis Evlogimenos 322e88280a4224730dcf8076e0d9a20973c5761fd06Alkis Evlogimenosunsigned LiveIntervals::rep(unsigned reg) 323169cfd01964fc03828a7f2cad5d710890fbb08d8Alkis Evlogimenos{ 324e88280a4224730dcf8076e0d9a20973c5761fd06Alkis Evlogimenos Reg2RegMap::iterator it = r2rMap_.find(reg); 325e88280a4224730dcf8076e0d9a20973c5761fd06Alkis Evlogimenos if (it != r2rMap_.end()) 326e88280a4224730dcf8076e0d9a20973c5761fd06Alkis Evlogimenos return it->second = rep(it->second); 327e88280a4224730dcf8076e0d9a20973c5761fd06Alkis Evlogimenos return reg; 328169cfd01964fc03828a7f2cad5d710890fbb08d8Alkis Evlogimenos} 329169cfd01964fc03828a7f2cad5d710890fbb08d8Alkis Evlogimenos 330e88280a4224730dcf8076e0d9a20973c5761fd06Alkis Evlogimenosvoid LiveIntervals::joinIntervals() 331dd2cc65f34f9b7bfda1cd0c42becedfc361d46f8Alkis Evlogimenos{ 332e88280a4224730dcf8076e0d9a20973c5761fd06Alkis Evlogimenos DEBUG(std::cerr << "joining compatible intervals:\n"); 333dd2cc65f34f9b7bfda1cd0c42becedfc361d46f8Alkis Evlogimenos 334e88280a4224730dcf8076e0d9a20973c5761fd06Alkis Evlogimenos const TargetInstrInfo& tii = tm_->getInstrInfo(); 335dd2cc65f34f9b7bfda1cd0c42becedfc361d46f8Alkis Evlogimenos 336c0b9dc5be79f009d260edb5cd5e1d8346587aaa2Alkis Evlogimenos for (MachineFunction::iterator mbbi = mf_->begin(), mbbe = mf_->end(); 337c0b9dc5be79f009d260edb5cd5e1d8346587aaa2Alkis Evlogimenos mbbi != mbbe; ++mbbi) { 338c0b9dc5be79f009d260edb5cd5e1d8346587aaa2Alkis Evlogimenos MachineBasicBlock* mbb = mbbi; 339e88280a4224730dcf8076e0d9a20973c5761fd06Alkis Evlogimenos DEBUG(std::cerr << "machine basic block: " 340e88280a4224730dcf8076e0d9a20973c5761fd06Alkis Evlogimenos << mbb->getBasicBlock()->getName() << "\n"); 341e88280a4224730dcf8076e0d9a20973c5761fd06Alkis Evlogimenos 342c0b9dc5be79f009d260edb5cd5e1d8346587aaa2Alkis Evlogimenos for (MachineBasicBlock::iterator mi = mbb->begin(), mie = mbb->end(); 343c0b9dc5be79f009d260edb5cd5e1d8346587aaa2Alkis Evlogimenos mi != mie; ++mi) { 344e88280a4224730dcf8076e0d9a20973c5761fd06Alkis Evlogimenos const TargetInstrDescriptor& tid = 345e88280a4224730dcf8076e0d9a20973c5761fd06Alkis Evlogimenos tm_->getInstrInfo().get(mi->getOpcode()); 346e88280a4224730dcf8076e0d9a20973c5761fd06Alkis Evlogimenos DEBUG(std::cerr << "\t\tinstruction[" 347e88280a4224730dcf8076e0d9a20973c5761fd06Alkis Evlogimenos << getInstructionIndex(mi) << "]: "; 348e88280a4224730dcf8076e0d9a20973c5761fd06Alkis Evlogimenos mi->print(std::cerr, *tm_);); 349e88280a4224730dcf8076e0d9a20973c5761fd06Alkis Evlogimenos 35001e74a2aab64c5901a62d9ba9e1c263759929390Alkis Evlogimenos // we only join virtual registers with allocatable 35101e74a2aab64c5901a62d9ba9e1c263759929390Alkis Evlogimenos // physical registers since we do not have liveness information 35201e74a2aab64c5901a62d9ba9e1c263759929390Alkis Evlogimenos // on not allocatable physical registers 35301e74a2aab64c5901a62d9ba9e1c263759929390Alkis Evlogimenos unsigned regA, regB; 35401e74a2aab64c5901a62d9ba9e1c263759929390Alkis Evlogimenos if (tii.isMoveInstr(*mi, regA, regB) && 35501e74a2aab64c5901a62d9ba9e1c263759929390Alkis Evlogimenos (MRegisterInfo::isVirtualRegister(regA) || 35601e74a2aab64c5901a62d9ba9e1c263759929390Alkis Evlogimenos lv_->getAllocatablePhysicalRegisters()[regA]) && 35701e74a2aab64c5901a62d9ba9e1c263759929390Alkis Evlogimenos (MRegisterInfo::isVirtualRegister(regB) || 35801e74a2aab64c5901a62d9ba9e1c263759929390Alkis Evlogimenos lv_->getAllocatablePhysicalRegisters()[regB])) { 359e88280a4224730dcf8076e0d9a20973c5761fd06Alkis Evlogimenos 360e88280a4224730dcf8076e0d9a20973c5761fd06Alkis Evlogimenos // get representative registers 36101e74a2aab64c5901a62d9ba9e1c263759929390Alkis Evlogimenos regA = rep(regA); 36201e74a2aab64c5901a62d9ba9e1c263759929390Alkis Evlogimenos regB = rep(regB); 363e88280a4224730dcf8076e0d9a20973c5761fd06Alkis Evlogimenos 364e88280a4224730dcf8076e0d9a20973c5761fd06Alkis Evlogimenos // if they are already joined we continue 36501e74a2aab64c5901a62d9ba9e1c263759929390Alkis Evlogimenos if (regA == regB) 366e88280a4224730dcf8076e0d9a20973c5761fd06Alkis Evlogimenos continue; 367e88280a4224730dcf8076e0d9a20973c5761fd06Alkis Evlogimenos 36801e74a2aab64c5901a62d9ba9e1c263759929390Alkis Evlogimenos Reg2IntervalMap::iterator r2iA = r2iMap_.find(regA); 36901e74a2aab64c5901a62d9ba9e1c263759929390Alkis Evlogimenos assert(r2iA != r2iMap_.end()); 37001e74a2aab64c5901a62d9ba9e1c263759929390Alkis Evlogimenos Reg2IntervalMap::iterator r2iB = r2iMap_.find(regB); 37101e74a2aab64c5901a62d9ba9e1c263759929390Alkis Evlogimenos assert(r2iB != r2iMap_.end()); 37201e74a2aab64c5901a62d9ba9e1c263759929390Alkis Evlogimenos 37301e74a2aab64c5901a62d9ba9e1c263759929390Alkis Evlogimenos Intervals::iterator intA = r2iA->second; 37401e74a2aab64c5901a62d9ba9e1c263759929390Alkis Evlogimenos Intervals::iterator intB = r2iB->second; 37501e74a2aab64c5901a62d9ba9e1c263759929390Alkis Evlogimenos 37601e74a2aab64c5901a62d9ba9e1c263759929390Alkis Evlogimenos // both A and B are virtual registers 37701e74a2aab64c5901a62d9ba9e1c263759929390Alkis Evlogimenos if (MRegisterInfo::isVirtualRegister(intA->reg) && 37801e74a2aab64c5901a62d9ba9e1c263759929390Alkis Evlogimenos MRegisterInfo::isVirtualRegister(intB->reg)) { 37901e74a2aab64c5901a62d9ba9e1c263759929390Alkis Evlogimenos 38001e74a2aab64c5901a62d9ba9e1c263759929390Alkis Evlogimenos const TargetRegisterClass *rcA, *rcB; 38101e74a2aab64c5901a62d9ba9e1c263759929390Alkis Evlogimenos rcA = mf_->getSSARegMap()->getRegClass(intA->reg); 38201e74a2aab64c5901a62d9ba9e1c263759929390Alkis Evlogimenos rcB = mf_->getSSARegMap()->getRegClass(intB->reg); 38301e74a2aab64c5901a62d9ba9e1c263759929390Alkis Evlogimenos assert(rcA == rcB && "registers must be of the same class"); 38401e74a2aab64c5901a62d9ba9e1c263759929390Alkis Evlogimenos 38501e74a2aab64c5901a62d9ba9e1c263759929390Alkis Evlogimenos // if their intervals do not overlap we join them 38601e74a2aab64c5901a62d9ba9e1c263759929390Alkis Evlogimenos if (!intB->overlaps(*intA)) { 38701e74a2aab64c5901a62d9ba9e1c263759929390Alkis Evlogimenos intA->join(*intB); 38801e74a2aab64c5901a62d9ba9e1c263759929390Alkis Evlogimenos r2iB->second = r2iA->second; 38901e74a2aab64c5901a62d9ba9e1c263759929390Alkis Evlogimenos r2rMap_.insert(std::make_pair(intB->reg, intA->reg)); 39001e74a2aab64c5901a62d9ba9e1c263759929390Alkis Evlogimenos intervals_.erase(intB); 39101e74a2aab64c5901a62d9ba9e1c263759929390Alkis Evlogimenos ++numJoined; 392e88280a4224730dcf8076e0d9a20973c5761fd06Alkis Evlogimenos } 393e88280a4224730dcf8076e0d9a20973c5761fd06Alkis Evlogimenos } 394b0b0ebaac09a930f7cbd302255fa23c5d8107e66Alkis Evlogimenos else if (MRegisterInfo::isPhysicalRegister(intA->reg) ^ 39501e74a2aab64c5901a62d9ba9e1c263759929390Alkis Evlogimenos MRegisterInfo::isPhysicalRegister(intB->reg)) { 39601e74a2aab64c5901a62d9ba9e1c263759929390Alkis Evlogimenos if (MRegisterInfo::isPhysicalRegister(intB->reg)) { 39701e74a2aab64c5901a62d9ba9e1c263759929390Alkis Evlogimenos std::swap(regA, regB); 39801e74a2aab64c5901a62d9ba9e1c263759929390Alkis Evlogimenos std::swap(intA, intB); 39901e74a2aab64c5901a62d9ba9e1c263759929390Alkis Evlogimenos std::swap(r2iA, r2iB); 400e88280a4224730dcf8076e0d9a20973c5761fd06Alkis Evlogimenos } 40101e74a2aab64c5901a62d9ba9e1c263759929390Alkis Evlogimenos 40201e74a2aab64c5901a62d9ba9e1c263759929390Alkis Evlogimenos assert(MRegisterInfo::isPhysicalRegister(intA->reg) && 40301e74a2aab64c5901a62d9ba9e1c263759929390Alkis Evlogimenos MRegisterInfo::isVirtualRegister(intB->reg) && 40401e74a2aab64c5901a62d9ba9e1c263759929390Alkis Evlogimenos "A must be physical and B must be virtual"); 405676cf8cb1d613d626f826a45b44658ae35f58c7cAlkis Evlogimenos 40601e74a2aab64c5901a62d9ba9e1c263759929390Alkis Evlogimenos if (!intA->overlaps(*intB) && 40701e74a2aab64c5901a62d9ba9e1c263759929390Alkis Evlogimenos !overlapsAliases(*intA, *intB)) { 40801e74a2aab64c5901a62d9ba9e1c263759929390Alkis Evlogimenos intA->join(*intB); 40901e74a2aab64c5901a62d9ba9e1c263759929390Alkis Evlogimenos r2iB->second = r2iA->second; 41001e74a2aab64c5901a62d9ba9e1c263759929390Alkis Evlogimenos r2rMap_.insert(std::make_pair(intB->reg, intA->reg)); 41101e74a2aab64c5901a62d9ba9e1c263759929390Alkis Evlogimenos intervals_.erase(intB); 41201e74a2aab64c5901a62d9ba9e1c263759929390Alkis Evlogimenos ++numJoined; 413e88280a4224730dcf8076e0d9a20973c5761fd06Alkis Evlogimenos } 414e88280a4224730dcf8076e0d9a20973c5761fd06Alkis Evlogimenos } 415e88280a4224730dcf8076e0d9a20973c5761fd06Alkis Evlogimenos } 416e88280a4224730dcf8076e0d9a20973c5761fd06Alkis Evlogimenos } 417dd2cc65f34f9b7bfda1cd0c42becedfc361d46f8Alkis Evlogimenos } 418dd2cc65f34f9b7bfda1cd0c42becedfc361d46f8Alkis Evlogimenos} 419dd2cc65f34f9b7bfda1cd0c42becedfc361d46f8Alkis Evlogimenos 42079b0c3f0b9d91bbda354a2c6f22b6578655a5143Alkis Evlogimenosbool LiveIntervals::overlapsAliases(const Interval& lhs, 42179b0c3f0b9d91bbda354a2c6f22b6578655a5143Alkis Evlogimenos const Interval& rhs) const 42279b0c3f0b9d91bbda354a2c6f22b6578655a5143Alkis Evlogimenos{ 4234f67b8664889d9e93b452a9a5f099d41d1bd235aAlkis Evlogimenos assert(MRegisterInfo::isPhysicalRegister(lhs.reg) && 42479b0c3f0b9d91bbda354a2c6f22b6578655a5143Alkis Evlogimenos "first interval must describe a physical register"); 42579b0c3f0b9d91bbda354a2c6f22b6578655a5143Alkis Evlogimenos 42679b0c3f0b9d91bbda354a2c6f22b6578655a5143Alkis Evlogimenos for (const unsigned* as = mri_->getAliasSet(lhs.reg); *as; ++as) { 42779b0c3f0b9d91bbda354a2c6f22b6578655a5143Alkis Evlogimenos Reg2IntervalMap::const_iterator r2i = r2iMap_.find(*as); 42879b0c3f0b9d91bbda354a2c6f22b6578655a5143Alkis Evlogimenos assert(r2i != r2iMap_.end() && "alias does not have interval?"); 42979b0c3f0b9d91bbda354a2c6f22b6578655a5143Alkis Evlogimenos if (rhs.overlaps(*r2i->second)) 43079b0c3f0b9d91bbda354a2c6f22b6578655a5143Alkis Evlogimenos return true; 43179b0c3f0b9d91bbda354a2c6f22b6578655a5143Alkis Evlogimenos } 43279b0c3f0b9d91bbda354a2c6f22b6578655a5143Alkis Evlogimenos 43379b0c3f0b9d91bbda354a2c6f22b6578655a5143Alkis Evlogimenos return false; 43479b0c3f0b9d91bbda354a2c6f22b6578655a5143Alkis Evlogimenos} 43579b0c3f0b9d91bbda354a2c6f22b6578655a5143Alkis Evlogimenos 436e88280a4224730dcf8076e0d9a20973c5761fd06Alkis EvlogimenosLiveIntervals::Interval::Interval(unsigned r) 437e88280a4224730dcf8076e0d9a20973c5761fd06Alkis Evlogimenos : reg(r), 4384f67b8664889d9e93b452a9a5f099d41d1bd235aAlkis Evlogimenos weight((MRegisterInfo::isPhysicalRegister(r) ? 439e88280a4224730dcf8076e0d9a20973c5761fd06Alkis Evlogimenos std::numeric_limits<float>::max() : 0.0F)) 440dd2cc65f34f9b7bfda1cd0c42becedfc361d46f8Alkis Evlogimenos{ 441e88280a4224730dcf8076e0d9a20973c5761fd06Alkis Evlogimenos 442dd2cc65f34f9b7bfda1cd0c42becedfc361d46f8Alkis Evlogimenos} 443dd2cc65f34f9b7bfda1cd0c42becedfc361d46f8Alkis Evlogimenos 4440b8cb2bc47a6bee59c8c3f46d4cc047badf7f8acAlkis Evlogimenos// An example for liveAt(): 44508cec00588ec1a8fa85b208555f006d7396ae7a4Alkis Evlogimenos// 4460b8cb2bc47a6bee59c8c3f46d4cc047badf7f8acAlkis Evlogimenos// this = [1,2), liveAt(0) will return false. The instruction defining 4470b8cb2bc47a6bee59c8c3f46d4cc047badf7f8acAlkis Evlogimenos// this spans slots [0,1]. Since it is a definition we say that it is 4480b8cb2bc47a6bee59c8c3f46d4cc047badf7f8acAlkis Evlogimenos// live in the second slot onwards. By ending the lifetime of this 4490b8cb2bc47a6bee59c8c3f46d4cc047badf7f8acAlkis Evlogimenos// interval at 2 it means that it is not used at all. liveAt(1) 4500b8cb2bc47a6bee59c8c3f46d4cc047badf7f8acAlkis Evlogimenos// returns true which means that this clobbers a register at 4510b8cb2bc47a6bee59c8c3f46d4cc047badf7f8acAlkis Evlogimenos// instruction at 0. 45208cec00588ec1a8fa85b208555f006d7396ae7a4Alkis Evlogimenos// 4530b8cb2bc47a6bee59c8c3f46d4cc047badf7f8acAlkis Evlogimenos// this = [1,4), liveAt(0) will return false and liveAt(2) will return 4540b8cb2bc47a6bee59c8c3f46d4cc047badf7f8acAlkis Evlogimenos// true. The variable is defined at instruction 0 and last used at 2. 455169cfd01964fc03828a7f2cad5d710890fbb08d8Alkis Evlogimenosbool LiveIntervals::Interval::liveAt(unsigned index) const 456169cfd01964fc03828a7f2cad5d710890fbb08d8Alkis Evlogimenos{ 45797017de1872e08ffcdde2fccdfd399647c1ccc4aAlkis Evlogimenos Range dummy(index, index+1); 45897017de1872e08ffcdde2fccdfd399647c1ccc4aAlkis Evlogimenos Ranges::const_iterator r = std::upper_bound(ranges.begin(), 45997017de1872e08ffcdde2fccdfd399647c1ccc4aAlkis Evlogimenos ranges.end(), 46097017de1872e08ffcdde2fccdfd399647c1ccc4aAlkis Evlogimenos dummy); 46197017de1872e08ffcdde2fccdfd399647c1ccc4aAlkis Evlogimenos if (r == ranges.begin()) 46297017de1872e08ffcdde2fccdfd399647c1ccc4aAlkis Evlogimenos return false; 46397017de1872e08ffcdde2fccdfd399647c1ccc4aAlkis Evlogimenos 46497017de1872e08ffcdde2fccdfd399647c1ccc4aAlkis Evlogimenos --r; 4650b8cb2bc47a6bee59c8c3f46d4cc047badf7f8acAlkis Evlogimenos return index >= r->first && index < r->second; 466169cfd01964fc03828a7f2cad5d710890fbb08d8Alkis Evlogimenos} 467169cfd01964fc03828a7f2cad5d710890fbb08d8Alkis Evlogimenos 4680b8cb2bc47a6bee59c8c3f46d4cc047badf7f8acAlkis Evlogimenos// An example for overlaps(): 46908cec00588ec1a8fa85b208555f006d7396ae7a4Alkis Evlogimenos// 47008cec00588ec1a8fa85b208555f006d7396ae7a4Alkis Evlogimenos// 0: A = ... 4710b8cb2bc47a6bee59c8c3f46d4cc047badf7f8acAlkis Evlogimenos// 2: B = ... 4720b8cb2bc47a6bee59c8c3f46d4cc047badf7f8acAlkis Evlogimenos// 4: C = A + B ;; last use of A 47308cec00588ec1a8fa85b208555f006d7396ae7a4Alkis Evlogimenos// 47408cec00588ec1a8fa85b208555f006d7396ae7a4Alkis Evlogimenos// The live intervals should look like: 47508cec00588ec1a8fa85b208555f006d7396ae7a4Alkis Evlogimenos// 4760b8cb2bc47a6bee59c8c3f46d4cc047badf7f8acAlkis Evlogimenos// A = [1, 5) 4770b8cb2bc47a6bee59c8c3f46d4cc047badf7f8acAlkis Evlogimenos// B = [3, x) 4780b8cb2bc47a6bee59c8c3f46d4cc047badf7f8acAlkis Evlogimenos// C = [5, y) 47908cec00588ec1a8fa85b208555f006d7396ae7a4Alkis Evlogimenos// 48008cec00588ec1a8fa85b208555f006d7396ae7a4Alkis Evlogimenos// A->overlaps(C) should return false since we want to be able to join 48108cec00588ec1a8fa85b208555f006d7396ae7a4Alkis Evlogimenos// A and C. 482169cfd01964fc03828a7f2cad5d710890fbb08d8Alkis Evlogimenosbool LiveIntervals::Interval::overlaps(const Interval& other) const 483169cfd01964fc03828a7f2cad5d710890fbb08d8Alkis Evlogimenos{ 48480b378cf7c3dce77029dc3118e1f63bc6d389da1Alkis Evlogimenos Ranges::const_iterator i = ranges.begin(); 48597017de1872e08ffcdde2fccdfd399647c1ccc4aAlkis Evlogimenos Ranges::const_iterator ie = ranges.end(); 48680b378cf7c3dce77029dc3118e1f63bc6d389da1Alkis Evlogimenos Ranges::const_iterator j = other.ranges.begin(); 48797017de1872e08ffcdde2fccdfd399647c1ccc4aAlkis Evlogimenos Ranges::const_iterator je = other.ranges.end(); 48897017de1872e08ffcdde2fccdfd399647c1ccc4aAlkis Evlogimenos if (i->first < j->first) { 48997017de1872e08ffcdde2fccdfd399647c1ccc4aAlkis Evlogimenos i = std::upper_bound(i, ie, *j); 49097017de1872e08ffcdde2fccdfd399647c1ccc4aAlkis Evlogimenos if (i != ranges.begin()) --i; 49197017de1872e08ffcdde2fccdfd399647c1ccc4aAlkis Evlogimenos } 49297017de1872e08ffcdde2fccdfd399647c1ccc4aAlkis Evlogimenos else if (j->first < i->first) { 49397017de1872e08ffcdde2fccdfd399647c1ccc4aAlkis Evlogimenos j = std::upper_bound(j, je, *i); 49497017de1872e08ffcdde2fccdfd399647c1ccc4aAlkis Evlogimenos if (j != other.ranges.begin()) --j; 49597017de1872e08ffcdde2fccdfd399647c1ccc4aAlkis Evlogimenos } 49697017de1872e08ffcdde2fccdfd399647c1ccc4aAlkis Evlogimenos 49797017de1872e08ffcdde2fccdfd399647c1ccc4aAlkis Evlogimenos while (i != ie && j != je) { 49897017de1872e08ffcdde2fccdfd399647c1ccc4aAlkis Evlogimenos if (i->first == j->first) { 49997017de1872e08ffcdde2fccdfd399647c1ccc4aAlkis Evlogimenos return true; 50097017de1872e08ffcdde2fccdfd399647c1ccc4aAlkis Evlogimenos } 50197017de1872e08ffcdde2fccdfd399647c1ccc4aAlkis Evlogimenos else { 50297017de1872e08ffcdde2fccdfd399647c1ccc4aAlkis Evlogimenos if (i->first > j->first) { 50397017de1872e08ffcdde2fccdfd399647c1ccc4aAlkis Evlogimenos swap(i, j); 50497017de1872e08ffcdde2fccdfd399647c1ccc4aAlkis Evlogimenos swap(ie, je); 50597017de1872e08ffcdde2fccdfd399647c1ccc4aAlkis Evlogimenos } 50697017de1872e08ffcdde2fccdfd399647c1ccc4aAlkis Evlogimenos assert(i->first < j->first); 50780b378cf7c3dce77029dc3118e1f63bc6d389da1Alkis Evlogimenos 5080b8cb2bc47a6bee59c8c3f46d4cc047badf7f8acAlkis Evlogimenos if (i->second > j->first) { 50980b378cf7c3dce77029dc3118e1f63bc6d389da1Alkis Evlogimenos return true; 51080b378cf7c3dce77029dc3118e1f63bc6d389da1Alkis Evlogimenos } 51180b378cf7c3dce77029dc3118e1f63bc6d389da1Alkis Evlogimenos else { 51280b378cf7c3dce77029dc3118e1f63bc6d389da1Alkis Evlogimenos ++i; 51380b378cf7c3dce77029dc3118e1f63bc6d389da1Alkis Evlogimenos } 51480b378cf7c3dce77029dc3118e1f63bc6d389da1Alkis Evlogimenos } 515169cfd01964fc03828a7f2cad5d710890fbb08d8Alkis Evlogimenos } 516169cfd01964fc03828a7f2cad5d710890fbb08d8Alkis Evlogimenos 517169cfd01964fc03828a7f2cad5d710890fbb08d8Alkis Evlogimenos return false; 518169cfd01964fc03828a7f2cad5d710890fbb08d8Alkis Evlogimenos} 519169cfd01964fc03828a7f2cad5d710890fbb08d8Alkis Evlogimenos 520e88280a4224730dcf8076e0d9a20973c5761fd06Alkis Evlogimenosvoid LiveIntervals::Interval::addRange(unsigned start, unsigned end) 521e88280a4224730dcf8076e0d9a20973c5761fd06Alkis Evlogimenos{ 52208cec00588ec1a8fa85b208555f006d7396ae7a4Alkis Evlogimenos assert(start < end && "Invalid range to add!"); 523e88280a4224730dcf8076e0d9a20973c5761fd06Alkis Evlogimenos DEBUG(std::cerr << "\t\t\tadding range: [" << start <<','<< end << ") -> "); 524e88280a4224730dcf8076e0d9a20973c5761fd06Alkis Evlogimenos //assert(start < end && "invalid range?"); 525e88280a4224730dcf8076e0d9a20973c5761fd06Alkis Evlogimenos Range range = std::make_pair(start, end); 526e88280a4224730dcf8076e0d9a20973c5761fd06Alkis Evlogimenos Ranges::iterator it = 527e88280a4224730dcf8076e0d9a20973c5761fd06Alkis Evlogimenos ranges.insert(std::upper_bound(ranges.begin(), ranges.end(), range), 528e88280a4224730dcf8076e0d9a20973c5761fd06Alkis Evlogimenos range); 529e88280a4224730dcf8076e0d9a20973c5761fd06Alkis Evlogimenos 530e88280a4224730dcf8076e0d9a20973c5761fd06Alkis Evlogimenos it = mergeRangesForward(it); 531e88280a4224730dcf8076e0d9a20973c5761fd06Alkis Evlogimenos it = mergeRangesBackward(it); 532e88280a4224730dcf8076e0d9a20973c5761fd06Alkis Evlogimenos DEBUG(std::cerr << "\t\t\t\tafter merging: " << *this << '\n'); 533e88280a4224730dcf8076e0d9a20973c5761fd06Alkis Evlogimenos} 534e88280a4224730dcf8076e0d9a20973c5761fd06Alkis Evlogimenos 535e88280a4224730dcf8076e0d9a20973c5761fd06Alkis Evlogimenosvoid LiveIntervals::Interval::join(const LiveIntervals::Interval& other) 536e88280a4224730dcf8076e0d9a20973c5761fd06Alkis Evlogimenos{ 537e88280a4224730dcf8076e0d9a20973c5761fd06Alkis Evlogimenos DEBUG(std::cerr << "\t\t\t\tjoining intervals: " 538e88280a4224730dcf8076e0d9a20973c5761fd06Alkis Evlogimenos << other << " and " << *this << '\n'); 539e88280a4224730dcf8076e0d9a20973c5761fd06Alkis Evlogimenos Ranges::iterator cur = ranges.begin(); 540e88280a4224730dcf8076e0d9a20973c5761fd06Alkis Evlogimenos 541e88280a4224730dcf8076e0d9a20973c5761fd06Alkis Evlogimenos for (Ranges::const_iterator i = other.ranges.begin(), 542e88280a4224730dcf8076e0d9a20973c5761fd06Alkis Evlogimenos e = other.ranges.end(); i != e; ++i) { 543e88280a4224730dcf8076e0d9a20973c5761fd06Alkis Evlogimenos cur = ranges.insert(std::upper_bound(cur, ranges.end(), *i), *i); 544e88280a4224730dcf8076e0d9a20973c5761fd06Alkis Evlogimenos cur = mergeRangesForward(cur); 545e88280a4224730dcf8076e0d9a20973c5761fd06Alkis Evlogimenos cur = mergeRangesBackward(cur); 546e88280a4224730dcf8076e0d9a20973c5761fd06Alkis Evlogimenos } 5474f67b8664889d9e93b452a9a5f099d41d1bd235aAlkis Evlogimenos if (MRegisterInfo::isVirtualRegister(reg)) 548e88280a4224730dcf8076e0d9a20973c5761fd06Alkis Evlogimenos weight += other.weight; 549e88280a4224730dcf8076e0d9a20973c5761fd06Alkis Evlogimenos 550e88280a4224730dcf8076e0d9a20973c5761fd06Alkis Evlogimenos DEBUG(std::cerr << "\t\t\t\tafter merging: " << *this << '\n'); 551e88280a4224730dcf8076e0d9a20973c5761fd06Alkis Evlogimenos} 552e88280a4224730dcf8076e0d9a20973c5761fd06Alkis Evlogimenos 553e88280a4224730dcf8076e0d9a20973c5761fd06Alkis EvlogimenosLiveIntervals::Interval::Ranges::iterator 554e88280a4224730dcf8076e0d9a20973c5761fd06Alkis EvlogimenosLiveIntervals::Interval::mergeRangesForward(Ranges::iterator it) 555e88280a4224730dcf8076e0d9a20973c5761fd06Alkis Evlogimenos{ 556e88280a4224730dcf8076e0d9a20973c5761fd06Alkis Evlogimenos for (Ranges::iterator next = it + 1; 557e88280a4224730dcf8076e0d9a20973c5761fd06Alkis Evlogimenos next != ranges.end() && it->second >= next->first; ) { 558e88280a4224730dcf8076e0d9a20973c5761fd06Alkis Evlogimenos it->second = std::max(it->second, next->second); 559e88280a4224730dcf8076e0d9a20973c5761fd06Alkis Evlogimenos next = ranges.erase(next); 560e88280a4224730dcf8076e0d9a20973c5761fd06Alkis Evlogimenos } 561e88280a4224730dcf8076e0d9a20973c5761fd06Alkis Evlogimenos return it; 562e88280a4224730dcf8076e0d9a20973c5761fd06Alkis Evlogimenos} 563e88280a4224730dcf8076e0d9a20973c5761fd06Alkis Evlogimenos 564e88280a4224730dcf8076e0d9a20973c5761fd06Alkis EvlogimenosLiveIntervals::Interval::Ranges::iterator 565e88280a4224730dcf8076e0d9a20973c5761fd06Alkis EvlogimenosLiveIntervals::Interval::mergeRangesBackward(Ranges::iterator it) 566e88280a4224730dcf8076e0d9a20973c5761fd06Alkis Evlogimenos{ 56708cec00588ec1a8fa85b208555f006d7396ae7a4Alkis Evlogimenos while (it != ranges.begin()) { 56808cec00588ec1a8fa85b208555f006d7396ae7a4Alkis Evlogimenos Ranges::iterator prev = it - 1; 56908cec00588ec1a8fa85b208555f006d7396ae7a4Alkis Evlogimenos if (it->first > prev->second) break; 57008cec00588ec1a8fa85b208555f006d7396ae7a4Alkis Evlogimenos 571e88280a4224730dcf8076e0d9a20973c5761fd06Alkis Evlogimenos it->first = std::min(it->first, prev->first); 572e88280a4224730dcf8076e0d9a20973c5761fd06Alkis Evlogimenos it->second = std::max(it->second, prev->second); 573e88280a4224730dcf8076e0d9a20973c5761fd06Alkis Evlogimenos it = ranges.erase(prev); 574e88280a4224730dcf8076e0d9a20973c5761fd06Alkis Evlogimenos } 575e88280a4224730dcf8076e0d9a20973c5761fd06Alkis Evlogimenos 576e88280a4224730dcf8076e0d9a20973c5761fd06Alkis Evlogimenos return it; 577e88280a4224730dcf8076e0d9a20973c5761fd06Alkis Evlogimenos} 578e88280a4224730dcf8076e0d9a20973c5761fd06Alkis Evlogimenos 579b27ef248f579b354aab434f63c417ab1103e47e2Alkis Evlogimenosstd::ostream& llvm::operator<<(std::ostream& os, 580b27ef248f579b354aab434f63c417ab1103e47e2Alkis Evlogimenos const LiveIntervals::Interval& li) 581b27ef248f579b354aab434f63c417ab1103e47e2Alkis Evlogimenos{ 582169cfd01964fc03828a7f2cad5d710890fbb08d8Alkis Evlogimenos os << "%reg" << li.reg << ',' << li.weight << " = "; 583b27ef248f579b354aab434f63c417ab1103e47e2Alkis Evlogimenos for (LiveIntervals::Interval::Ranges::const_iterator 584b27ef248f579b354aab434f63c417ab1103e47e2Alkis Evlogimenos i = li.ranges.begin(), e = li.ranges.end(); i != e; ++i) { 58563841bc85d15ca0ce1b3208084f4262f3d33ef21Alkis Evlogimenos os << "[" << i->first << "," << i->second << ")"; 586b27ef248f579b354aab434f63c417ab1103e47e2Alkis Evlogimenos } 587b27ef248f579b354aab434f63c417ab1103e47e2Alkis Evlogimenos return os; 588b27ef248f579b354aab434f63c417ab1103e47e2Alkis Evlogimenos} 589