LiveIntervalAnalysis.cpp revision 99d9923608bfd0feff288d667c3e4f94c4132c26
1//===-- LiveIntervals.cpp - Live Interval Analysis ------------------------===// 2// 3// The LLVM Compiler Infrastructure 4// 5// This file was developed by the LLVM research group and is distributed under 6// the University of Illinois Open Source License. See LICENSE.TXT for details. 7// 8//===----------------------------------------------------------------------===// 9// 10// This file implements the LiveInterval analysis pass which is used 11// by the Linear Scan Register allocator. This pass linearizes the 12// basic blocks of the function in DFS order and uses the 13// LiveVariables pass to conservatively compute live intervals for 14// each virtual and physical register. 15// 16//===----------------------------------------------------------------------===// 17 18#define DEBUG_TYPE "liveintervals" 19#include "llvm/CodeGen/LiveIntervals.h" 20#include "llvm/Analysis/LoopInfo.h" 21#include "llvm/CodeGen/LiveVariables.h" 22#include "llvm/CodeGen/MachineFrameInfo.h" 23#include "llvm/CodeGen/MachineInstr.h" 24#include "llvm/CodeGen/Passes.h" 25#include "llvm/CodeGen/SSARegMap.h" 26#include "llvm/Target/MRegisterInfo.h" 27#include "llvm/Target/TargetInstrInfo.h" 28#include "llvm/Target/TargetMachine.h" 29#include "llvm/Support/CFG.h" 30#include "Support/CommandLine.h" 31#include "Support/Debug.h" 32#include "Support/Statistic.h" 33#include "Support/STLExtras.h" 34#include <cmath> 35#include <iostream> 36#include <limits> 37 38using namespace llvm; 39 40namespace { 41 RegisterAnalysis<LiveIntervals> X("liveintervals", 42 "Live Interval Analysis"); 43 44 Statistic<> numIntervals("liveintervals", "Number of intervals"); 45 Statistic<> numJoined ("liveintervals", "Number of joined intervals"); 46 Statistic<> numPeep ("liveintervals", "Number of identity moves " 47 "eliminated after coalescing"); 48 49 cl::opt<bool> 50 join("join-liveintervals", 51 cl::desc("Join compatible live intervals"), 52 cl::init(true)); 53}; 54 55void LiveIntervals::getAnalysisUsage(AnalysisUsage &AU) const 56{ 57 AU.addPreserved<LiveVariables>(); 58 AU.addRequired<LiveVariables>(); 59 AU.addPreservedID(PHIEliminationID); 60 AU.addRequiredID(PHIEliminationID); 61 AU.addRequiredID(TwoAddressInstructionPassID); 62 AU.addRequired<LoopInfo>(); 63 MachineFunctionPass::getAnalysisUsage(AU); 64} 65 66void LiveIntervals::releaseMemory() 67{ 68 mbbi2mbbMap_.clear(); 69 mi2iMap_.clear(); 70 i2miMap_.clear(); 71 r2iMap_.clear(); 72 r2rMap_.clear(); 73 intervals_.clear(); 74} 75 76 77/// runOnMachineFunction - Register allocate the whole function 78/// 79bool LiveIntervals::runOnMachineFunction(MachineFunction &fn) { 80 DEBUG(std::cerr << "MACHINE FUNCTION: "; fn.print(std::cerr)); 81 mf_ = &fn; 82 tm_ = &fn.getTarget(); 83 mri_ = tm_->getRegisterInfo(); 84 lv_ = &getAnalysis<LiveVariables>(); 85 86 // number MachineInstrs 87 unsigned miIndex = 0; 88 for (MachineFunction::iterator mbb = mf_->begin(), mbbEnd = mf_->end(); 89 mbb != mbbEnd; ++mbb) { 90 const std::pair<MachineBasicBlock*, unsigned>& entry = 91 lv_->getMachineBasicBlockInfo(mbb); 92 bool inserted = mbbi2mbbMap_.insert(std::make_pair(entry.second, 93 entry.first)).second; 94 assert(inserted && "multiple index -> MachineBasicBlock"); 95 96 for (MachineBasicBlock::iterator mi = mbb->begin(), miEnd = mbb->end(); 97 mi != miEnd; ++mi) { 98 inserted = mi2iMap_.insert(std::make_pair(mi, miIndex)).second; 99 assert(inserted && "multiple MachineInstr -> index mappings"); 100 i2miMap_.push_back(mi); 101 miIndex += 2; 102 } 103 } 104 105 computeIntervals(); 106 107 numIntervals += intervals_.size(); 108 109 // join intervals if requested 110 if (join) joinIntervals(); 111 112 // perform a final pass over the instructions and compute spill 113 // weights, coalesce virtual registers and remove identity moves 114 const LoopInfo& loopInfo = getAnalysis<LoopInfo>(); 115 const TargetInstrInfo& tii = tm_->getInstrInfo(); 116 117 for (MachineFunction::iterator mbbi = mf_->begin(), mbbe = mf_->end(); 118 mbbi != mbbe; ++mbbi) { 119 MachineBasicBlock* mbb = mbbi; 120 unsigned loopDepth = loopInfo.getLoopDepth(mbb->getBasicBlock()); 121 122 for (MachineBasicBlock::iterator mii = mbb->begin(), mie = mbb->end(); 123 mii != mie; ) { 124 for (unsigned i = 0; i < mii->getNumOperands(); ++i) { 125 const MachineOperand& mop = mii->getOperand(i); 126 if (mop.isRegister()) { 127 // replace register with representative register 128 unsigned reg = rep(mop.getReg()); 129 mii->SetMachineOperandReg(i, reg); 130 131 if (MRegisterInfo::isVirtualRegister(reg)) { 132 Reg2IntervalMap::iterator r2iit = r2iMap_.find(reg); 133 assert(r2iit != r2iMap_.end()); 134 r2iit->second->weight += pow(10.0F, loopDepth); 135 } 136 } 137 } 138 139 // if the move is now an identity move delete it 140 unsigned srcReg, dstReg; 141 if (tii.isMoveInstr(*mii, srcReg, dstReg) && srcReg == dstReg) { 142 // remove index -> MachineInstr and 143 // MachineInstr -> index mappings 144 Mi2IndexMap::iterator mi2i = mi2iMap_.find(mii); 145 if (mi2i != mi2iMap_.end()) { 146 i2miMap_[mi2i->second/2] = 0; 147 mi2iMap_.erase(mi2i); 148 } 149 mii = mbbi->erase(mii); 150 ++numPeep; 151 } 152 else 153 ++mii; 154 } 155 } 156 157 intervals_.sort(StartPointComp()); 158 DEBUG(std::cerr << "*** INTERVALS ***\n"); 159 DEBUG(std::copy(intervals_.begin(), intervals_.end(), 160 std::ostream_iterator<Interval>(std::cerr, "\n"))); 161 DEBUG(std::cerr << "*** MACHINEINSTRS ***\n"); 162 DEBUG( 163 for (unsigned i = 0; i != i2miMap_.size(); ++i) { 164 if (const MachineInstr* mi = i2miMap_[i]) { 165 std:: cerr << i*2 << '\t'; 166 mi->print(std::cerr, *tm_); 167 } 168 }); 169 170 return true; 171} 172 173void LiveIntervals::updateSpilledInterval(Interval& li) 174{ 175 assert(li.weight != std::numeric_limits<float>::infinity() && 176 "attempt to spill already spilled interval!"); 177 Interval::Ranges oldRanges; 178 swap(oldRanges, li.ranges); 179 180 for (Interval::Ranges::iterator i = oldRanges.begin(), e = oldRanges.end(); 181 i != e; ++i) { 182 unsigned index = i->first & ~1; 183 unsigned end = i->second; 184 185 for (; index < end; index += 2) { 186 // skip deleted instructions 187 while (!getInstructionFromIndex(index)) index += 2; 188 MachineInstr* mi = getInstructionFromIndex(index); 189 for (unsigned i = 0; i < mi->getNumOperands(); ++i) { 190 MachineOperand& mop = mi->getOperand(i); 191 if (mop.isRegister()) { 192 unsigned reg = mop.getReg(); 193 if (rep(reg) == li.reg) { 194 unsigned start = mop.isUse() ? index : index+1; 195 unsigned end = mop.isDef() ? index+2 : index+1; 196 li.addRange(start, end); 197 } 198 } 199 } 200 } 201 } 202 // the new spill weight is now infinity as it cannot be spilled again 203 li.weight = std::numeric_limits<float>::infinity(); 204} 205 206void LiveIntervals::printRegName(unsigned reg) const 207{ 208 if (MRegisterInfo::isPhysicalRegister(reg)) 209 std::cerr << mri_->getName(reg); 210 else 211 std::cerr << '%' << reg; 212} 213 214void LiveIntervals::handleVirtualRegisterDef(MachineBasicBlock* mbb, 215 MachineBasicBlock::iterator mi, 216 unsigned reg) 217{ 218 DEBUG(std::cerr << "\t\tregister: ";printRegName(reg); std::cerr << '\n'); 219 220 LiveVariables::VarInfo& vi = lv_->getVarInfo(reg); 221 222 Interval* interval = 0; 223 Reg2IntervalMap::iterator r2iit = r2iMap_.lower_bound(reg); 224 if (r2iit == r2iMap_.end() || r2iit->first != reg) { 225 // add new interval 226 intervals_.push_back(Interval(reg)); 227 // update interval index for this register 228 r2iMap_.insert(r2iit, std::make_pair(reg, --intervals_.end())); 229 interval = &intervals_.back(); 230 231 // iterate over all of the blocks that the variable is 232 // completely live in, adding them to the live 233 // interval. obviously we only need to do this once. 234 for (unsigned i = 0, e = vi.AliveBlocks.size(); i != e; ++i) { 235 if (vi.AliveBlocks[i]) { 236 MachineBasicBlock* mbb = lv_->getIndexMachineBasicBlock(i); 237 if (!mbb->empty()) { 238 interval->addRange(getInstructionIndex(&mbb->front()), 239 getInstructionIndex(&mbb->back()) + 1); 240 } 241 } 242 } 243 } 244 else { 245 interval = &*r2iit->second; 246 } 247 248 // we consider defs to happen at the second time slot of the 249 // instruction 250 unsigned instrIndex = getInstructionIndex(mi) + 1; 251 252 bool killedInDefiningBasicBlock = false; 253 for (int i = 0, e = vi.Kills.size(); i != e; ++i) { 254 MachineBasicBlock* killerBlock = vi.Kills[i].first; 255 MachineInstr* killerInstr = vi.Kills[i].second; 256 unsigned start = (mbb == killerBlock ? 257 instrIndex : 258 getInstructionIndex(&killerBlock->front())); 259 unsigned end = (killerInstr == mi ? 260 instrIndex + 1 : // dead 261 getInstructionIndex(killerInstr) + 1); // killed 262 // we do not want to add invalid ranges. these can happen when 263 // a variable has its latest use and is redefined later on in 264 // the same basic block (common with variables introduced by 265 // PHI elimination) 266 if (start < end) { 267 killedInDefiningBasicBlock |= mbb == killerBlock; 268 interval->addRange(start, end); 269 } 270 } 271 272 if (!killedInDefiningBasicBlock) { 273 unsigned end = getInstructionIndex(&mbb->back()) + 1; 274 interval->addRange(instrIndex, end); 275 } 276} 277 278void LiveIntervals::handlePhysicalRegisterDef(MachineBasicBlock* mbb, 279 MachineBasicBlock::iterator mi, 280 unsigned reg) 281{ 282 typedef LiveVariables::killed_iterator KillIter; 283 284 DEBUG(std::cerr << "\t\tregister: "; printRegName(reg)); 285 286 MachineBasicBlock::iterator e = mbb->end(); 287 // we consider defs to happen at the second time slot of the 288 // instruction 289 unsigned start, end; 290 start = end = getInstructionIndex(mi) + 1; 291 292 // a variable can be dead by the instruction defining it 293 for (KillIter ki = lv_->dead_begin(mi), ke = lv_->dead_end(mi); 294 ki != ke; ++ki) { 295 if (reg == ki->second) { 296 DEBUG(std::cerr << " dead\n"); 297 ++end; 298 goto exit; 299 } 300 } 301 302 // a variable can only be killed by subsequent instructions 303 do { 304 ++mi; 305 end += 2; 306 for (KillIter ki = lv_->killed_begin(mi), ke = lv_->killed_end(mi); 307 ki != ke; ++ki) { 308 if (reg == ki->second) { 309 DEBUG(std::cerr << " killed\n"); 310 goto exit; 311 } 312 } 313 } while (mi != e); 314 315exit: 316 assert(start < end && "did not find end of interval?"); 317 318 Reg2IntervalMap::iterator r2iit = r2iMap_.lower_bound(reg); 319 if (r2iit != r2iMap_.end() && r2iit->first == reg) { 320 r2iit->second->addRange(start, end); 321 } 322 else { 323 intervals_.push_back(Interval(reg)); 324 // update interval index for this register 325 r2iMap_.insert(r2iit, std::make_pair(reg, --intervals_.end())); 326 intervals_.back().addRange(start, end); 327 } 328} 329 330void LiveIntervals::handleRegisterDef(MachineBasicBlock* mbb, 331 MachineBasicBlock::iterator mi, 332 unsigned reg) 333{ 334 if (MRegisterInfo::isPhysicalRegister(reg)) { 335 if (lv_->getAllocatablePhysicalRegisters()[reg]) { 336 handlePhysicalRegisterDef(mbb, mi, reg); 337 for (const unsigned* as = mri_->getAliasSet(reg); *as; ++as) 338 handlePhysicalRegisterDef(mbb, mi, *as); 339 } 340 } 341 else { 342 handleVirtualRegisterDef(mbb, mi, reg); 343 } 344} 345 346unsigned LiveIntervals::getInstructionIndex(MachineInstr* instr) const 347{ 348 Mi2IndexMap::const_iterator it = mi2iMap_.find(instr); 349 return it == mi2iMap_.end() ? std::numeric_limits<unsigned>::max() : it->second; 350} 351 352MachineInstr* LiveIntervals::getInstructionFromIndex(unsigned index) const 353{ 354 index /= 2; // convert index to vector index 355 assert(index < i2miMap_.size() && 356 "index does not correspond to an instruction"); 357 return i2miMap_[index]; 358} 359 360/// computeIntervals - computes the live intervals for virtual 361/// registers. for some ordering of the machine instructions [1,N] a 362/// live interval is an interval [i, j) where 1 <= i <= j < N for 363/// which a variable is live 364void LiveIntervals::computeIntervals() 365{ 366 DEBUG(std::cerr << "*** COMPUTING LIVE INTERVALS ***\n"); 367 368 for (MbbIndex2MbbMap::iterator 369 it = mbbi2mbbMap_.begin(), itEnd = mbbi2mbbMap_.end(); 370 it != itEnd; ++it) { 371 MachineBasicBlock* mbb = it->second; 372 DEBUG(std::cerr << mbb->getBasicBlock()->getName() << ":\n"); 373 374 for (MachineBasicBlock::iterator mi = mbb->begin(), miEnd = mbb->end(); 375 mi != miEnd; ++mi) { 376 const TargetInstrDescriptor& tid = 377 tm_->getInstrInfo().get(mi->getOpcode()); 378 DEBUG(std::cerr << "[" << getInstructionIndex(mi) << "]\t"; 379 mi->print(std::cerr, *tm_);); 380 381 // handle implicit defs 382 for (const unsigned* id = tid.ImplicitDefs; *id; ++id) 383 handleRegisterDef(mbb, mi, *id); 384 385 // handle explicit defs 386 for (int i = mi->getNumOperands() - 1; i >= 0; --i) { 387 MachineOperand& mop = mi->getOperand(i); 388 // handle register defs - build intervals 389 if (mop.isRegister() && mop.isDef()) 390 handleRegisterDef(mbb, mi, mop.getReg()); 391 } 392 } 393 } 394} 395 396unsigned LiveIntervals::rep(unsigned reg) 397{ 398 Reg2RegMap::iterator it = r2rMap_.find(reg); 399 if (it != r2rMap_.end()) 400 return it->second = rep(it->second); 401 return reg; 402} 403 404void LiveIntervals::joinIntervals() 405{ 406 DEBUG(std::cerr << "** JOINING INTERVALS ***\n"); 407 408 const TargetInstrInfo& tii = tm_->getInstrInfo(); 409 410 for (MachineFunction::iterator mbbi = mf_->begin(), mbbe = mf_->end(); 411 mbbi != mbbe; ++mbbi) { 412 MachineBasicBlock* mbb = mbbi; 413 DEBUG(std::cerr << mbb->getBasicBlock()->getName() << ":\n"); 414 415 for (MachineBasicBlock::iterator mi = mbb->begin(), mie = mbb->end(); 416 mi != mie; ++mi) { 417 const TargetInstrDescriptor& tid = 418 tm_->getInstrInfo().get(mi->getOpcode()); 419 DEBUG(std::cerr << "[" << getInstructionIndex(mi) << "]\t"; 420 mi->print(std::cerr, *tm_);); 421 422 // we only join virtual registers with allocatable 423 // physical registers since we do not have liveness information 424 // on not allocatable physical registers 425 unsigned regA, regB; 426 if (tii.isMoveInstr(*mi, regA, regB) && 427 (MRegisterInfo::isVirtualRegister(regA) || 428 lv_->getAllocatablePhysicalRegisters()[regA]) && 429 (MRegisterInfo::isVirtualRegister(regB) || 430 lv_->getAllocatablePhysicalRegisters()[regB])) { 431 432 // get representative registers 433 regA = rep(regA); 434 regB = rep(regB); 435 436 // if they are already joined we continue 437 if (regA == regB) 438 continue; 439 440 Reg2IntervalMap::iterator r2iA = r2iMap_.find(regA); 441 assert(r2iA != r2iMap_.end()); 442 Reg2IntervalMap::iterator r2iB = r2iMap_.find(regB); 443 assert(r2iB != r2iMap_.end()); 444 445 Intervals::iterator intA = r2iA->second; 446 Intervals::iterator intB = r2iB->second; 447 448 // both A and B are virtual registers 449 if (MRegisterInfo::isVirtualRegister(intA->reg) && 450 MRegisterInfo::isVirtualRegister(intB->reg)) { 451 452 const TargetRegisterClass *rcA, *rcB; 453 rcA = mf_->getSSARegMap()->getRegClass(intA->reg); 454 rcB = mf_->getSSARegMap()->getRegClass(intB->reg); 455 assert(rcA == rcB && "registers must be of the same class"); 456 457 // if their intervals do not overlap we join them 458 if (!intB->overlaps(*intA)) { 459 intA->join(*intB); 460 r2iB->second = r2iA->second; 461 r2rMap_.insert(std::make_pair(intB->reg, intA->reg)); 462 intervals_.erase(intB); 463 ++numJoined; 464 } 465 } 466 else if (MRegisterInfo::isPhysicalRegister(intA->reg) ^ 467 MRegisterInfo::isPhysicalRegister(intB->reg)) { 468 if (MRegisterInfo::isPhysicalRegister(intB->reg)) { 469 std::swap(regA, regB); 470 std::swap(intA, intB); 471 std::swap(r2iA, r2iB); 472 } 473 474 assert(MRegisterInfo::isPhysicalRegister(intA->reg) && 475 MRegisterInfo::isVirtualRegister(intB->reg) && 476 "A must be physical and B must be virtual"); 477 478 if (!intA->overlaps(*intB) && 479 !overlapsAliases(*intA, *intB)) { 480 intA->join(*intB); 481 r2iB->second = r2iA->second; 482 r2rMap_.insert(std::make_pair(intB->reg, intA->reg)); 483 intervals_.erase(intB); 484 ++numJoined; 485 } 486 } 487 } 488 } 489 } 490} 491 492bool LiveIntervals::overlapsAliases(const Interval& lhs, 493 const Interval& rhs) const 494{ 495 assert(MRegisterInfo::isPhysicalRegister(lhs.reg) && 496 "first interval must describe a physical register"); 497 498 for (const unsigned* as = mri_->getAliasSet(lhs.reg); *as; ++as) { 499 Reg2IntervalMap::const_iterator r2i = r2iMap_.find(*as); 500 assert(r2i != r2iMap_.end() && "alias does not have interval?"); 501 if (rhs.overlaps(*r2i->second)) 502 return true; 503 } 504 505 return false; 506} 507 508LiveIntervals::Interval::Interval(unsigned r) 509 : reg(r), 510 weight((MRegisterInfo::isPhysicalRegister(r) ? 511 std::numeric_limits<float>::infinity() : 0.0F)) 512{ 513 514} 515 516// An example for liveAt(): 517// 518// this = [1,2), liveAt(0) will return false. The instruction defining 519// this spans slots [0,1]. Since it is a definition we say that it is 520// live in the second slot onwards. By ending the lifetime of this 521// interval at 2 it means that it is not used at all. liveAt(1) 522// returns true which means that this clobbers a register at 523// instruction at 0. 524// 525// this = [1,4), liveAt(0) will return false and liveAt(2) will return 526// true. The variable is defined at instruction 0 and last used at 2. 527bool LiveIntervals::Interval::liveAt(unsigned index) const 528{ 529 Range dummy(index, index+1); 530 Ranges::const_iterator r = std::upper_bound(ranges.begin(), 531 ranges.end(), 532 dummy); 533 if (r == ranges.begin()) 534 return false; 535 536 --r; 537 return index >= r->first && index < r->second; 538} 539 540// An example for overlaps(): 541// 542// 0: A = ... 543// 2: B = ... 544// 4: C = A + B ;; last use of A 545// 546// The live intervals should look like: 547// 548// A = [1, 5) 549// B = [3, x) 550// C = [5, y) 551// 552// A->overlaps(C) should return false since we want to be able to join 553// A and C. 554bool LiveIntervals::Interval::overlaps(const Interval& other) const 555{ 556 Ranges::const_iterator i = ranges.begin(); 557 Ranges::const_iterator ie = ranges.end(); 558 Ranges::const_iterator j = other.ranges.begin(); 559 Ranges::const_iterator je = other.ranges.end(); 560 if (i->first < j->first) { 561 i = std::upper_bound(i, ie, *j); 562 if (i != ranges.begin()) --i; 563 } 564 else if (j->first < i->first) { 565 j = std::upper_bound(j, je, *i); 566 if (j != other.ranges.begin()) --j; 567 } 568 569 while (i != ie && j != je) { 570 if (i->first == j->first) { 571 return true; 572 } 573 else { 574 if (i->first > j->first) { 575 swap(i, j); 576 swap(ie, je); 577 } 578 assert(i->first < j->first); 579 580 if (i->second > j->first) { 581 return true; 582 } 583 else { 584 ++i; 585 } 586 } 587 } 588 589 return false; 590} 591 592void LiveIntervals::Interval::addRange(unsigned start, unsigned end) 593{ 594 assert(start < end && "Invalid range to add!"); 595 DEBUG(std::cerr << "\t\t\tadding range: [" << start <<','<< end << ") -> "); 596 //assert(start < end && "invalid range?"); 597 Range range = std::make_pair(start, end); 598 Ranges::iterator it = 599 ranges.insert(std::upper_bound(ranges.begin(), ranges.end(), range), 600 range); 601 602 it = mergeRangesForward(it); 603 it = mergeRangesBackward(it); 604 DEBUG(std::cerr << "\t\t\t\tafter merging: " << *this << '\n'); 605} 606 607void LiveIntervals::Interval::join(const LiveIntervals::Interval& other) 608{ 609 DEBUG(std::cerr << "\t\t\t\tjoining intervals: " 610 << other << " and " << *this << '\n'); 611 Ranges::iterator cur = ranges.begin(); 612 613 for (Ranges::const_iterator i = other.ranges.begin(), 614 e = other.ranges.end(); i != e; ++i) { 615 cur = ranges.insert(std::upper_bound(cur, ranges.end(), *i), *i); 616 cur = mergeRangesForward(cur); 617 cur = mergeRangesBackward(cur); 618 } 619 if (MRegisterInfo::isVirtualRegister(reg)) 620 weight += other.weight; 621 622 DEBUG(std::cerr << "\t\t\t\tafter merging: " << *this << '\n'); 623} 624 625LiveIntervals::Interval::Ranges::iterator 626LiveIntervals::Interval::mergeRangesForward(Ranges::iterator it) 627{ 628 for (Ranges::iterator next = it + 1; 629 next != ranges.end() && it->second >= next->first; ) { 630 it->second = std::max(it->second, next->second); 631 next = ranges.erase(next); 632 } 633 return it; 634} 635 636LiveIntervals::Interval::Ranges::iterator 637LiveIntervals::Interval::mergeRangesBackward(Ranges::iterator it) 638{ 639 while (it != ranges.begin()) { 640 Ranges::iterator prev = it - 1; 641 if (it->first > prev->second) break; 642 643 it->first = std::min(it->first, prev->first); 644 it->second = std::max(it->second, prev->second); 645 it = ranges.erase(prev); 646 } 647 648 return it; 649} 650 651std::ostream& llvm::operator<<(std::ostream& os, 652 const LiveIntervals::Interval& li) 653{ 654 os << "%reg" << li.reg << ',' << li.weight << " = "; 655 for (LiveIntervals::Interval::Ranges::const_iterator 656 i = li.ranges.begin(), e = li.ranges.end(); i != e; ++i) { 657 os << "[" << i->first << "," << i->second << ")"; 658 } 659 return os; 660} 661