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