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