LiveIntervalAnalysis.cpp revision 843b160a2040b3ec4d3452678450afa11704c473
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 li.addRange(index, index + 2); 195 } 196 } 197 } 198 } 199 } 200 // the new spill weight is now infinity as it cannot be spilled again 201 li.weight = std::numeric_limits<float>::infinity(); 202} 203 204void LiveIntervals::printRegName(unsigned reg) const 205{ 206 if (MRegisterInfo::isPhysicalRegister(reg)) 207 std::cerr << mri_->getName(reg); 208 else 209 std::cerr << '%' << reg; 210} 211 212void LiveIntervals::handleVirtualRegisterDef(MachineBasicBlock* mbb, 213 MachineBasicBlock::iterator mi, 214 unsigned reg) 215{ 216 DEBUG(std::cerr << "\t\tregister: ";printRegName(reg); std::cerr << '\n'); 217 218 LiveVariables::VarInfo& vi = lv_->getVarInfo(reg); 219 220 Interval* interval = 0; 221 Reg2IntervalMap::iterator r2iit = r2iMap_.lower_bound(reg); 222 if (r2iit == r2iMap_.end() || r2iit->first != reg) { 223 // add new interval 224 intervals_.push_back(Interval(reg)); 225 // update interval index for this register 226 r2iMap_.insert(r2iit, std::make_pair(reg, --intervals_.end())); 227 interval = &intervals_.back(); 228 229 // iterate over all of the blocks that the variable is 230 // completely live in, adding them to the live 231 // interval. obviously we only need to do this once. 232 for (unsigned i = 0, e = vi.AliveBlocks.size(); i != e; ++i) { 233 if (vi.AliveBlocks[i]) { 234 MachineBasicBlock* mbb = lv_->getIndexMachineBasicBlock(i); 235 if (!mbb->empty()) { 236 interval->addRange(getInstructionIndex(&mbb->front()), 237 getInstructionIndex(&mbb->back()) + 1); 238 } 239 } 240 } 241 } 242 else { 243 interval = &*r2iit->second; 244 } 245 246 // we consider defs to happen at the second time slot of the 247 // instruction 248 unsigned instrIndex = getInstructionIndex(mi) + 1; 249 250 bool killedInDefiningBasicBlock = false; 251 for (int i = 0, e = vi.Kills.size(); i != e; ++i) { 252 MachineBasicBlock* killerBlock = vi.Kills[i].first; 253 MachineInstr* killerInstr = vi.Kills[i].second; 254 unsigned start = (mbb == killerBlock ? 255 instrIndex : 256 getInstructionIndex(&killerBlock->front())); 257 unsigned end = (killerInstr == mi ? 258 instrIndex + 1 : // dead 259 getInstructionIndex(killerInstr) + 1); // killed 260 // we do not want to add invalid ranges. these can happen when 261 // a variable has its latest use and is redefined later on in 262 // the same basic block (common with variables introduced by 263 // PHI elimination) 264 if (start < end) { 265 killedInDefiningBasicBlock |= mbb == killerBlock; 266 interval->addRange(start, end); 267 } 268 } 269 270 if (!killedInDefiningBasicBlock) { 271 unsigned end = getInstructionIndex(&mbb->back()) + 1; 272 interval->addRange(instrIndex, end); 273 } 274} 275 276void LiveIntervals::handlePhysicalRegisterDef(MachineBasicBlock* mbb, 277 MachineBasicBlock::iterator mi, 278 unsigned reg) 279{ 280 typedef LiveVariables::killed_iterator KillIter; 281 282 DEBUG(std::cerr << "\t\tregister: "; printRegName(reg)); 283 284 MachineBasicBlock::iterator e = mbb->end(); 285 // we consider defs to happen at the second time slot of the 286 // instruction 287 unsigned start, end; 288 start = end = getInstructionIndex(mi) + 1; 289 290 // a variable can be dead by the instruction defining it 291 for (KillIter ki = lv_->dead_begin(mi), ke = lv_->dead_end(mi); 292 ki != ke; ++ki) { 293 if (reg == ki->second) { 294 DEBUG(std::cerr << " dead\n"); 295 ++end; 296 goto exit; 297 } 298 } 299 300 // a variable can only be killed by subsequent instructions 301 do { 302 ++mi; 303 end += 2; 304 for (KillIter ki = lv_->killed_begin(mi), ke = lv_->killed_end(mi); 305 ki != ke; ++ki) { 306 if (reg == ki->second) { 307 DEBUG(std::cerr << " killed\n"); 308 goto exit; 309 } 310 } 311 } while (mi != e); 312 313exit: 314 assert(start < end && "did not find end of interval?"); 315 316 Reg2IntervalMap::iterator r2iit = r2iMap_.lower_bound(reg); 317 if (r2iit != r2iMap_.end() && r2iit->first == reg) { 318 r2iit->second->addRange(start, end); 319 } 320 else { 321 intervals_.push_back(Interval(reg)); 322 // update interval index for this register 323 r2iMap_.insert(r2iit, std::make_pair(reg, --intervals_.end())); 324 intervals_.back().addRange(start, end); 325 } 326} 327 328void LiveIntervals::handleRegisterDef(MachineBasicBlock* mbb, 329 MachineBasicBlock::iterator mi, 330 unsigned reg) 331{ 332 if (MRegisterInfo::isPhysicalRegister(reg)) { 333 if (lv_->getAllocatablePhysicalRegisters()[reg]) { 334 handlePhysicalRegisterDef(mbb, mi, reg); 335 for (const unsigned* as = mri_->getAliasSet(reg); *as; ++as) 336 handlePhysicalRegisterDef(mbb, mi, *as); 337 } 338 } 339 else { 340 handleVirtualRegisterDef(mbb, mi, reg); 341 } 342} 343 344unsigned LiveIntervals::getInstructionIndex(MachineInstr* instr) const 345{ 346 Mi2IndexMap::const_iterator it = mi2iMap_.find(instr); 347 return it == mi2iMap_.end() ? std::numeric_limits<unsigned>::max() : it->second; 348} 349 350MachineInstr* LiveIntervals::getInstructionFromIndex(unsigned index) const 351{ 352 index /= 2; // convert index to vector index 353 assert(index < i2miMap_.size() && 354 "index does not correspond to an instruction"); 355 return i2miMap_[index]; 356} 357 358/// computeIntervals - computes the live intervals for virtual 359/// registers. for some ordering of the machine instructions [1,N] a 360/// live interval is an interval [i, j) where 1 <= i <= j < N for 361/// which a variable is live 362void LiveIntervals::computeIntervals() 363{ 364 DEBUG(std::cerr << "*** COMPUTING LIVE INTERVALS ***\n"); 365 366 for (MbbIndex2MbbMap::iterator 367 it = mbbi2mbbMap_.begin(), itEnd = mbbi2mbbMap_.end(); 368 it != itEnd; ++it) { 369 MachineBasicBlock* mbb = it->second; 370 DEBUG(std::cerr << mbb->getBasicBlock()->getName() << ":\n"); 371 372 for (MachineBasicBlock::iterator mi = mbb->begin(), miEnd = mbb->end(); 373 mi != miEnd; ++mi) { 374 const TargetInstrDescriptor& tid = 375 tm_->getInstrInfo().get(mi->getOpcode()); 376 DEBUG(std::cerr << "[" << getInstructionIndex(mi) << "]\t"; 377 mi->print(std::cerr, *tm_);); 378 379 // handle implicit defs 380 for (const unsigned* id = tid.ImplicitDefs; *id; ++id) 381 handleRegisterDef(mbb, mi, *id); 382 383 // handle explicit defs 384 for (int i = mi->getNumOperands() - 1; i >= 0; --i) { 385 MachineOperand& mop = mi->getOperand(i); 386 // handle register defs - build intervals 387 if (mop.isRegister() && mop.isDef()) 388 handleRegisterDef(mbb, mi, mop.getReg()); 389 } 390 } 391 } 392} 393 394unsigned LiveIntervals::rep(unsigned reg) 395{ 396 Reg2RegMap::iterator it = r2rMap_.find(reg); 397 if (it != r2rMap_.end()) 398 return it->second = rep(it->second); 399 return reg; 400} 401 402void LiveIntervals::joinIntervals() 403{ 404 DEBUG(std::cerr << "** JOINING INTERVALS ***\n"); 405 406 const TargetInstrInfo& tii = tm_->getInstrInfo(); 407 408 for (MachineFunction::iterator mbbi = mf_->begin(), mbbe = mf_->end(); 409 mbbi != mbbe; ++mbbi) { 410 MachineBasicBlock* mbb = mbbi; 411 DEBUG(std::cerr << mbb->getBasicBlock()->getName() << ":\n"); 412 413 for (MachineBasicBlock::iterator mi = mbb->begin(), mie = mbb->end(); 414 mi != mie; ++mi) { 415 const TargetInstrDescriptor& tid = 416 tm_->getInstrInfo().get(mi->getOpcode()); 417 DEBUG(std::cerr << "[" << getInstructionIndex(mi) << "]\t"; 418 mi->print(std::cerr, *tm_);); 419 420 // we only join virtual registers with allocatable 421 // physical registers since we do not have liveness information 422 // on not allocatable physical registers 423 unsigned regA, regB; 424 if (tii.isMoveInstr(*mi, regA, regB) && 425 (MRegisterInfo::isVirtualRegister(regA) || 426 lv_->getAllocatablePhysicalRegisters()[regA]) && 427 (MRegisterInfo::isVirtualRegister(regB) || 428 lv_->getAllocatablePhysicalRegisters()[regB])) { 429 430 // get representative registers 431 regA = rep(regA); 432 regB = rep(regB); 433 434 // if they are already joined we continue 435 if (regA == regB) 436 continue; 437 438 Reg2IntervalMap::iterator r2iA = r2iMap_.find(regA); 439 assert(r2iA != r2iMap_.end()); 440 Reg2IntervalMap::iterator r2iB = r2iMap_.find(regB); 441 assert(r2iB != r2iMap_.end()); 442 443 Intervals::iterator intA = r2iA->second; 444 Intervals::iterator intB = r2iB->second; 445 446 // both A and B are virtual registers 447 if (MRegisterInfo::isVirtualRegister(intA->reg) && 448 MRegisterInfo::isVirtualRegister(intB->reg)) { 449 450 const TargetRegisterClass *rcA, *rcB; 451 rcA = mf_->getSSARegMap()->getRegClass(intA->reg); 452 rcB = mf_->getSSARegMap()->getRegClass(intB->reg); 453 assert(rcA == rcB && "registers must be of the same class"); 454 455 // if their intervals do not overlap we join them 456 if (!intB->overlaps(*intA)) { 457 intA->join(*intB); 458 r2iB->second = r2iA->second; 459 r2rMap_.insert(std::make_pair(intB->reg, intA->reg)); 460 intervals_.erase(intB); 461 ++numJoined; 462 } 463 } 464 else if (MRegisterInfo::isPhysicalRegister(intA->reg) ^ 465 MRegisterInfo::isPhysicalRegister(intB->reg)) { 466 if (MRegisterInfo::isPhysicalRegister(intB->reg)) { 467 std::swap(regA, regB); 468 std::swap(intA, intB); 469 std::swap(r2iA, r2iB); 470 } 471 472 assert(MRegisterInfo::isPhysicalRegister(intA->reg) && 473 MRegisterInfo::isVirtualRegister(intB->reg) && 474 "A must be physical and B must be virtual"); 475 476 if (!intA->overlaps(*intB) && 477 !overlapsAliases(*intA, *intB)) { 478 intA->join(*intB); 479 r2iB->second = r2iA->second; 480 r2rMap_.insert(std::make_pair(intB->reg, intA->reg)); 481 intervals_.erase(intB); 482 ++numJoined; 483 } 484 } 485 } 486 } 487 } 488} 489 490bool LiveIntervals::overlapsAliases(const Interval& lhs, 491 const Interval& rhs) const 492{ 493 assert(MRegisterInfo::isPhysicalRegister(lhs.reg) && 494 "first interval must describe a physical register"); 495 496 for (const unsigned* as = mri_->getAliasSet(lhs.reg); *as; ++as) { 497 Reg2IntervalMap::const_iterator r2i = r2iMap_.find(*as); 498 assert(r2i != r2iMap_.end() && "alias does not have interval?"); 499 if (rhs.overlaps(*r2i->second)) 500 return true; 501 } 502 503 return false; 504} 505 506LiveIntervals::Interval::Interval(unsigned r) 507 : reg(r), 508 weight((MRegisterInfo::isPhysicalRegister(r) ? 509 std::numeric_limits<float>::infinity() : 0.0F)) 510{ 511 512} 513 514// An example for liveAt(): 515// 516// this = [1,2), liveAt(0) will return false. The instruction defining 517// this spans slots [0,1]. Since it is a definition we say that it is 518// live in the second slot onwards. By ending the lifetime of this 519// interval at 2 it means that it is not used at all. liveAt(1) 520// returns true which means that this clobbers a register at 521// instruction at 0. 522// 523// this = [1,4), liveAt(0) will return false and liveAt(2) will return 524// true. The variable is defined at instruction 0 and last used at 2. 525bool LiveIntervals::Interval::liveAt(unsigned index) const 526{ 527 Range dummy(index, index+1); 528 Ranges::const_iterator r = std::upper_bound(ranges.begin(), 529 ranges.end(), 530 dummy); 531 if (r == ranges.begin()) 532 return false; 533 534 --r; 535 return index >= r->first && index < r->second; 536} 537 538// An example for overlaps(): 539// 540// 0: A = ... 541// 2: B = ... 542// 4: C = A + B ;; last use of A 543// 544// The live intervals should look like: 545// 546// A = [1, 5) 547// B = [3, x) 548// C = [5, y) 549// 550// A->overlaps(C) should return false since we want to be able to join 551// A and C. 552bool LiveIntervals::Interval::overlaps(const Interval& other) const 553{ 554 Ranges::const_iterator i = ranges.begin(); 555 Ranges::const_iterator ie = ranges.end(); 556 Ranges::const_iterator j = other.ranges.begin(); 557 Ranges::const_iterator je = other.ranges.end(); 558 if (i->first < j->first) { 559 i = std::upper_bound(i, ie, *j); 560 if (i != ranges.begin()) --i; 561 } 562 else if (j->first < i->first) { 563 j = std::upper_bound(j, je, *i); 564 if (j != other.ranges.begin()) --j; 565 } 566 567 while (i != ie && j != je) { 568 if (i->first == j->first) { 569 return true; 570 } 571 else { 572 if (i->first > j->first) { 573 swap(i, j); 574 swap(ie, je); 575 } 576 assert(i->first < j->first); 577 578 if (i->second > j->first) { 579 return true; 580 } 581 else { 582 ++i; 583 } 584 } 585 } 586 587 return false; 588} 589 590void LiveIntervals::Interval::addRange(unsigned start, unsigned end) 591{ 592 assert(start < end && "Invalid range to add!"); 593 DEBUG(std::cerr << "\t\t\tadding range: [" << start <<','<< end << ") -> "); 594 //assert(start < end && "invalid range?"); 595 Range range = std::make_pair(start, end); 596 Ranges::iterator it = 597 ranges.insert(std::upper_bound(ranges.begin(), ranges.end(), range), 598 range); 599 600 it = mergeRangesForward(it); 601 it = mergeRangesBackward(it); 602 DEBUG(std::cerr << "\t\t\t\tafter merging: " << *this << '\n'); 603} 604 605void LiveIntervals::Interval::join(const LiveIntervals::Interval& other) 606{ 607 DEBUG(std::cerr << "\t\t\t\tjoining intervals: " 608 << other << " and " << *this << '\n'); 609 Ranges::iterator cur = ranges.begin(); 610 611 for (Ranges::const_iterator i = other.ranges.begin(), 612 e = other.ranges.end(); i != e; ++i) { 613 cur = ranges.insert(std::upper_bound(cur, ranges.end(), *i), *i); 614 cur = mergeRangesForward(cur); 615 cur = mergeRangesBackward(cur); 616 } 617 if (MRegisterInfo::isVirtualRegister(reg)) 618 weight += other.weight; 619 620 DEBUG(std::cerr << "\t\t\t\tafter merging: " << *this << '\n'); 621} 622 623LiveIntervals::Interval::Ranges::iterator 624LiveIntervals::Interval::mergeRangesForward(Ranges::iterator it) 625{ 626 for (Ranges::iterator next = it + 1; 627 next != ranges.end() && it->second >= next->first; ) { 628 it->second = std::max(it->second, next->second); 629 next = ranges.erase(next); 630 } 631 return it; 632} 633 634LiveIntervals::Interval::Ranges::iterator 635LiveIntervals::Interval::mergeRangesBackward(Ranges::iterator it) 636{ 637 while (it != ranges.begin()) { 638 Ranges::iterator prev = it - 1; 639 if (it->first > prev->second) break; 640 641 it->first = std::min(it->first, prev->first); 642 it->second = std::max(it->second, prev->second); 643 it = ranges.erase(prev); 644 } 645 646 return it; 647} 648 649std::ostream& llvm::operator<<(std::ostream& os, 650 const LiveIntervals::Interval& li) 651{ 652 os << "%reg" << li.reg << ',' << li.weight << " = "; 653 for (LiveIntervals::Interval::Ranges::const_iterator 654 i = li.ranges.begin(), e = li.ranges.end(); i != e; ++i) { 655 os << "[" << i->first << "," << i->second << ")"; 656 } 657 return os; 658} 659