LiveIntervalAnalysis.cpp revision 8640f4e666086cc6e7447dc164105e428e6cb81a
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/Value.h" 21#include "llvm/Analysis/LoopInfo.h" 22#include "llvm/CodeGen/LiveVariables.h" 23#include "llvm/CodeGen/MachineFrameInfo.h" 24#include "llvm/CodeGen/MachineInstr.h" 25#include "llvm/CodeGen/Passes.h" 26#include "llvm/CodeGen/SSARegMap.h" 27#include "llvm/Target/MRegisterInfo.h" 28#include "llvm/Target/TargetInstrInfo.h" 29#include "llvm/Target/TargetMachine.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 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 EnableJoining("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 mi2iMap_.clear(); 79 i2miMap_.clear(); 80 r2iMap_.clear(); 81 r2rMap_.clear(); 82 intervals_.clear(); 83} 84 85 86/// runOnMachineFunction - Register allocate the whole function 87/// 88bool LiveIntervals::runOnMachineFunction(MachineFunction &fn) { 89 mf_ = &fn; 90 tm_ = &fn.getTarget(); 91 mri_ = tm_->getRegisterInfo(); 92 lv_ = &getAnalysis<LiveVariables>(); 93 94 // number MachineInstrs 95 unsigned miIndex = 0; 96 for (MachineFunction::iterator mbb = mf_->begin(), mbbEnd = mf_->end(); 97 mbb != mbbEnd; ++mbb) 98 for (MachineBasicBlock::iterator mi = mbb->begin(), miEnd = mbb->end(); 99 mi != miEnd; ++mi) { 100 bool inserted = mi2iMap_.insert(std::make_pair(mi, miIndex)).second; 101 assert(inserted && "multiple MachineInstr -> index mappings"); 102 i2miMap_.push_back(mi); 103 miIndex += InstrSlots::NUM; 104 } 105 106 computeIntervals(); 107 108 numIntervals += intervals_.size(); 109 110 // join intervals if requested 111 if (EnableJoining) joinIntervals(); 112 113 numIntervalsAfter += intervals_.size(); 114 115 // perform a final pass over the instructions and compute spill 116 // weights, coalesce virtual registers and remove identity moves 117 const LoopInfo& loopInfo = getAnalysis<LoopInfo>(); 118 const TargetInstrInfo& tii = *tm_->getInstrInfo(); 119 120 for (MachineFunction::iterator mbbi = mf_->begin(), mbbe = mf_->end(); 121 mbbi != mbbe; ++mbbi) { 122 MachineBasicBlock* mbb = mbbi; 123 unsigned loopDepth = loopInfo.getLoopDepth(mbb->getBasicBlock()); 124 125 for (MachineBasicBlock::iterator mii = mbb->begin(), mie = mbb->end(); 126 mii != mie; ) { 127 // if the move will be an identity move delete it 128 unsigned srcReg, dstReg; 129 if (tii.isMoveInstr(*mii, srcReg, dstReg) && 130 rep(srcReg) == rep(dstReg)) { 131 // remove from def list 132 LiveInterval& interval = getOrCreateInterval(rep(dstReg)); 133 // remove index -> MachineInstr and 134 // MachineInstr -> index mappings 135 Mi2IndexMap::iterator mi2i = mi2iMap_.find(mii); 136 if (mi2i != mi2iMap_.end()) { 137 i2miMap_[mi2i->second/InstrSlots::NUM] = 0; 138 mi2iMap_.erase(mi2i); 139 } 140 mii = mbbi->erase(mii); 141 ++numPeep; 142 } 143 else { 144 for (unsigned i = 0; i < mii->getNumOperands(); ++i) { 145 const MachineOperand& mop = mii->getOperand(i); 146 if (mop.isRegister() && mop.getReg() && 147 MRegisterInfo::isVirtualRegister(mop.getReg())) { 148 // replace register with representative register 149 unsigned reg = rep(mop.getReg()); 150 mii->SetMachineOperandReg(i, reg); 151 152 Reg2IntervalMap::iterator r2iit = r2iMap_.find(reg); 153 assert(r2iit != r2iMap_.end()); 154 r2iit->second->weight += 155 (mop.isUse() + mop.isDef()) * pow(10.0F, loopDepth); 156 } 157 } 158 ++mii; 159 } 160 } 161 } 162 163 intervals_.sort(); 164 DEBUG(std::cerr << "********** INTERVALS **********\n"); 165 DEBUG(std::copy(intervals_.begin(), intervals_.end(), 166 std::ostream_iterator<LiveInterval>(std::cerr, "\n"))); 167 DEBUG(std::cerr << "********** MACHINEINSTRS **********\n"); 168 DEBUG( 169 for (MachineFunction::iterator mbbi = mf_->begin(), mbbe = mf_->end(); 170 mbbi != mbbe; ++mbbi) { 171 std::cerr << ((Value*)mbbi->getBasicBlock())->getName() << ":\n"; 172 for (MachineBasicBlock::iterator mii = mbbi->begin(), 173 mie = mbbi->end(); mii != mie; ++mii) { 174 std::cerr << getInstructionIndex(mii) << '\t'; 175 mii->print(std::cerr, tm_); 176 } 177 }); 178 179 return true; 180} 181 182namespace { 183 /// CompareIntervalStar - This is a simple comparison function for interval 184 /// pointers. It compares based on their starting point. 185 struct CompareIntervalStar { 186 bool operator()(LiveInterval *LHS, LiveInterval* RHS) const { 187 return LHS->start() < RHS->start(); 188 } 189 }; 190} 191 192std::vector<LiveInterval*> LiveIntervals::addIntervalsForSpills( 193 const LiveInterval& li, 194 VirtRegMap& vrm, 195 int slot) 196{ 197 std::vector<LiveInterval*> added; 198 199 assert(li.weight != HUGE_VAL && 200 "attempt to spill already spilled interval!"); 201 202 DEBUG(std::cerr << "\t\t\t\tadding intervals for spills for interval: " 203 << li << '\n'); 204 205 const TargetRegisterClass* rc = mf_->getSSARegMap()->getRegClass(li.reg); 206 207 for (LiveInterval::Ranges::const_iterator 208 i = li.ranges.begin(), e = li.ranges.end(); i != e; ++i) { 209 unsigned index = getBaseIndex(i->first); 210 unsigned end = getBaseIndex(i->second-1) + InstrSlots::NUM; 211 for (; index != end; index += InstrSlots::NUM) { 212 // skip deleted instructions 213 while (index != end && !getInstructionFromIndex(index)) 214 index += InstrSlots::NUM; 215 if (index == end) break; 216 217 MachineBasicBlock::iterator mi = getInstructionFromIndex(index); 218 219 for_operand: 220 for (unsigned i = 0; i != mi->getNumOperands(); ++i) { 221 MachineOperand& mop = mi->getOperand(i); 222 if (mop.isRegister() && mop.getReg() == li.reg) { 223 if (MachineInstr* fmi = 224 mri_->foldMemoryOperand(mi, i, slot)) { 225 lv_->instructionChanged(mi, fmi); 226 vrm.virtFolded(li.reg, mi, fmi); 227 mi2iMap_.erase(mi); 228 i2miMap_[index/InstrSlots::NUM] = fmi; 229 mi2iMap_[fmi] = index; 230 MachineBasicBlock& mbb = *mi->getParent(); 231 mi = mbb.insert(mbb.erase(mi), fmi); 232 ++numFolded; 233 goto for_operand; 234 } 235 else { 236 // This is tricky. We need to add information in 237 // the interval about the spill code so we have to 238 // use our extra load/store slots. 239 // 240 // If we have a use we are going to have a load so 241 // we start the interval from the load slot 242 // onwards. Otherwise we start from the def slot. 243 unsigned start = (mop.isUse() ? 244 getLoadIndex(index) : 245 getDefIndex(index)); 246 // If we have a def we are going to have a store 247 // right after it so we end the interval after the 248 // use of the next instruction. Otherwise we end 249 // after the use of this instruction. 250 unsigned end = 1 + (mop.isDef() ? 251 getStoreIndex(index) : 252 getUseIndex(index)); 253 254 // create a new register for this spill 255 unsigned nReg = 256 mf_->getSSARegMap()->createVirtualRegister(rc); 257 mi->SetMachineOperandReg(i, nReg); 258 vrm.grow(); 259 vrm.assignVirt2StackSlot(nReg, slot); 260 LiveInterval& nI = getOrCreateInterval(nReg); 261 assert(nI.empty()); 262 // the spill weight is now infinity as it 263 // cannot be spilled again 264 nI.weight = HUGE_VAL; 265 nI.addRange(start, end); 266 added.push_back(&nI); 267 // update live variables 268 lv_->addVirtualRegisterKilled(nReg, mi); 269 DEBUG(std::cerr << "\t\t\t\tadded new interval: " 270 << nI << '\n'); 271 } 272 } 273 } 274 } 275 } 276 277 // FIXME: This method MUST return intervals in sorted order. If a 278 // particular machine instruction both uses and defines the vreg being 279 // spilled (e.g., vr = vr + 1) and if the def is processed before the 280 // use, the list ends up not sorted. 281 // 282 // The proper way to fix this is to process all uses of the vreg before we 283 // process any defs. However, this would require refactoring the above 284 // blob of code, which I'm not feeling up to right now. 285 std::sort(added.begin(), added.end(), CompareIntervalStar()); 286 return added; 287} 288 289void LiveIntervals::printRegName(unsigned reg) const 290{ 291 if (MRegisterInfo::isPhysicalRegister(reg)) 292 std::cerr << mri_->getName(reg); 293 else 294 std::cerr << "%reg" << reg; 295} 296 297void LiveIntervals::handleVirtualRegisterDef(MachineBasicBlock* mbb, 298 MachineBasicBlock::iterator mi, 299 LiveInterval& interval) 300{ 301 DEBUG(std::cerr << "\t\tregister: "; printRegName(interval.reg)); 302 LiveVariables::VarInfo& vi = lv_->getVarInfo(interval.reg); 303 304 // Virtual registers may be defined multiple times (due to phi 305 // elimination). Much of what we do only has to be done once for the vreg. 306 // We use an empty interval to detect the first time we see a vreg. 307 if (interval.empty()) { 308 309 // Get the Idx of the defining instructions. 310 unsigned defIndex = getDefIndex(getInstructionIndex(mi)); 311 312 // Loop over all of the blocks that the vreg is defined in. There are 313 // two cases we have to handle here. The most common case is a vreg 314 // whose lifetime is contained within a basic block. In this case there 315 // will be a single kill, in MBB, which comes after the definition. 316 if (vi.Kills.size() == 1 && vi.Kills[0]->getParent() == mbb) { 317 // FIXME: what about dead vars? 318 unsigned killIdx; 319 if (vi.Kills[0] != mi) 320 killIdx = getUseIndex(getInstructionIndex(vi.Kills[0]))+1; 321 else 322 killIdx = defIndex+1; 323 324 // If the kill happens after the definition, we have an intra-block 325 // live range. 326 if (killIdx > defIndex) { 327 assert(vi.AliveBlocks.empty() && 328 "Shouldn't be alive across any blocks!"); 329 interval.addRange(defIndex, killIdx); 330 return; 331 } 332 } 333 334 // The other case we handle is when a virtual register lives to the end 335 // of the defining block, potentially live across some blocks, then is 336 // live into some number of blocks, but gets killed. Start by adding a 337 // range that goes from this definition to the end of the defining block. 338 interval.addRange(defIndex, 339 getInstructionIndex(&mbb->back()) + InstrSlots::NUM); 340 341 // Iterate over all of the blocks that the variable is completely 342 // live in, adding [insrtIndex(begin), instrIndex(end)+4) to the 343 // live interval. 344 for (unsigned i = 0, e = vi.AliveBlocks.size(); i != e; ++i) { 345 if (vi.AliveBlocks[i]) { 346 MachineBasicBlock* mbb = mf_->getBlockNumbered(i); 347 if (!mbb->empty()) { 348 interval.addRange( 349 getInstructionIndex(&mbb->front()), 350 getInstructionIndex(&mbb->back()) + InstrSlots::NUM); 351 } 352 } 353 } 354 355 // Finally, this virtual register is live from the start of any killing 356 // block to the 'use' slot of the killing instruction. 357 for (unsigned i = 0, e = vi.Kills.size(); i != e; ++i) { 358 MachineInstr *Kill = vi.Kills[i]; 359 interval.addRange(getInstructionIndex(Kill->getParent()->begin()), 360 getUseIndex(getInstructionIndex(Kill))+1); 361 } 362 363 } else { 364 // If this is the second time we see a virtual register definition, it 365 // must be due to phi elimination. In this case, the defined value will 366 // be live until the end of the basic block it is defined in. 367 unsigned defIndex = getDefIndex(getInstructionIndex(mi)); 368 interval.addRange(defIndex, 369 getInstructionIndex(&mbb->back()) + InstrSlots::NUM); 370 } 371 372 DEBUG(std::cerr << '\n'); 373} 374 375void LiveIntervals::handlePhysicalRegisterDef(MachineBasicBlock* mbb, 376 MachineBasicBlock::iterator mi, 377 LiveInterval& interval) 378{ 379 // A physical register cannot be live across basic block, so its 380 // lifetime must end somewhere in its defining basic block. 381 DEBUG(std::cerr << "\t\tregister: "; printRegName(interval.reg)); 382 typedef LiveVariables::killed_iterator KillIter; 383 384 MachineBasicBlock::iterator e = mbb->end(); 385 unsigned baseIndex = getInstructionIndex(mi); 386 unsigned start = getDefIndex(baseIndex); 387 unsigned end = start; 388 389 // If it is not used after definition, it is considered dead at 390 // the instruction defining it. Hence its interval is: 391 // [defSlot(def), defSlot(def)+1) 392 for (KillIter ki = lv_->dead_begin(mi), ke = lv_->dead_end(mi); 393 ki != ke; ++ki) { 394 if (interval.reg == ki->second) { 395 DEBUG(std::cerr << " dead"); 396 end = getDefIndex(start) + 1; 397 goto exit; 398 } 399 } 400 401 // If it is not dead on definition, it must be killed by a 402 // subsequent instruction. Hence its interval is: 403 // [defSlot(def), useSlot(kill)+1) 404 do { 405 ++mi; 406 baseIndex += InstrSlots::NUM; 407 for (KillIter ki = lv_->killed_begin(mi), ke = lv_->killed_end(mi); 408 ki != ke; ++ki) { 409 if (interval.reg == ki->second) { 410 DEBUG(std::cerr << " killed"); 411 end = getUseIndex(baseIndex) + 1; 412 goto exit; 413 } 414 } 415 } while (mi != e); 416 417exit: 418 assert(start < end && "did not find end of interval?"); 419 interval.addRange(start, end); 420 DEBUG(std::cerr << '\n'); 421} 422 423void LiveIntervals::handleRegisterDef(MachineBasicBlock* mbb, 424 MachineBasicBlock::iterator mi, 425 unsigned reg) 426{ 427 if (MRegisterInfo::isPhysicalRegister(reg)) { 428 if (lv_->getAllocatablePhysicalRegisters()[reg]) { 429 handlePhysicalRegisterDef(mbb, mi, getOrCreateInterval(reg)); 430 for (const unsigned* as = mri_->getAliasSet(reg); *as; ++as) 431 handlePhysicalRegisterDef(mbb, mi, getOrCreateInterval(*as)); 432 } 433 } 434 else 435 handleVirtualRegisterDef(mbb, mi, getOrCreateInterval(reg)); 436} 437 438unsigned LiveIntervals::getInstructionIndex(MachineInstr* instr) const 439{ 440 Mi2IndexMap::const_iterator it = mi2iMap_.find(instr); 441 return (it == mi2iMap_.end() ? 442 std::numeric_limits<unsigned>::max() : 443 it->second); 444} 445 446MachineInstr* LiveIntervals::getInstructionFromIndex(unsigned index) const 447{ 448 index /= InstrSlots::NUM; // convert index to vector index 449 assert(index < i2miMap_.size() && 450 "index does not correspond to an instruction"); 451 return i2miMap_[index]; 452} 453 454/// computeIntervals - computes the live intervals for virtual 455/// registers. for some ordering of the machine instructions [1,N] a 456/// live interval is an interval [i, j) where 1 <= i <= j < N for 457/// which a variable is live 458void LiveIntervals::computeIntervals() 459{ 460 DEBUG(std::cerr << "********** COMPUTING LIVE INTERVALS **********\n"); 461 DEBUG(std::cerr << "********** Function: " 462 << ((Value*)mf_->getFunction())->getName() << '\n'); 463 464 for (MachineFunction::iterator I = mf_->begin(), E = mf_->end(); 465 I != E; ++I) { 466 MachineBasicBlock* mbb = I; 467 DEBUG(std::cerr << ((Value*)mbb->getBasicBlock())->getName() << ":\n"); 468 469 for (MachineBasicBlock::iterator mi = mbb->begin(), miEnd = mbb->end(); 470 mi != miEnd; ++mi) { 471 const TargetInstrDescriptor& tid = 472 tm_->getInstrInfo()->get(mi->getOpcode()); 473 DEBUG(std::cerr << getInstructionIndex(mi) << "\t"; 474 mi->print(std::cerr, tm_)); 475 476 // handle implicit defs 477 for (const unsigned* id = tid.ImplicitDefs; *id; ++id) 478 handleRegisterDef(mbb, mi, *id); 479 480 // handle explicit defs 481 for (int i = mi->getNumOperands() - 1; i >= 0; --i) { 482 MachineOperand& mop = mi->getOperand(i); 483 // handle register defs - build intervals 484 if (mop.isRegister() && mop.getReg() && mop.isDef()) 485 handleRegisterDef(mbb, mi, mop.getReg()); 486 } 487 } 488 } 489} 490 491unsigned LiveIntervals::rep(unsigned reg) 492{ 493 Reg2RegMap::iterator it = r2rMap_.find(reg); 494 if (it != r2rMap_.end()) 495 return it->second = rep(it->second); 496 return reg; 497} 498 499void LiveIntervals::joinIntervalsInMachineBB(MachineBasicBlock *MBB) { 500 DEBUG(std::cerr << ((Value*)MBB->getBasicBlock())->getName() << ":\n"); 501 const TargetInstrInfo& tii = *tm_->getInstrInfo(); 502 503 for (MachineBasicBlock::iterator mi = MBB->begin(), mie = MBB->end(); 504 mi != mie; ++mi) { 505 const TargetInstrDescriptor& tid = tii.get(mi->getOpcode()); 506 DEBUG(std::cerr << getInstructionIndex(mi) << '\t'; 507 mi->print(std::cerr, tm_);); 508 509 // we only join virtual registers with allocatable 510 // physical registers since we do not have liveness information 511 // on not allocatable physical registers 512 unsigned regA, regB; 513 if (tii.isMoveInstr(*mi, regA, regB) && 514 (MRegisterInfo::isVirtualRegister(regA) || 515 lv_->getAllocatablePhysicalRegisters()[regA]) && 516 (MRegisterInfo::isVirtualRegister(regB) || 517 lv_->getAllocatablePhysicalRegisters()[regB])) { 518 519 // get representative registers 520 regA = rep(regA); 521 regB = rep(regB); 522 523 // if they are already joined we continue 524 if (regA == regB) 525 continue; 526 527 Reg2IntervalMap::iterator r2iA = r2iMap_.find(regA); 528 assert(r2iA != r2iMap_.end() && 529 "Found unknown vreg in 'isMoveInstr' instruction"); 530 Reg2IntervalMap::iterator r2iB = r2iMap_.find(regB); 531 assert(r2iB != r2iMap_.end() && 532 "Found unknown vreg in 'isMoveInstr' instruction"); 533 534 Intervals::iterator intA = r2iA->second; 535 Intervals::iterator intB = r2iB->second; 536 537 // both A and B are virtual registers 538 if (MRegisterInfo::isVirtualRegister(intA->reg) && 539 MRegisterInfo::isVirtualRegister(intB->reg)) { 540 541 const TargetRegisterClass *rcA, *rcB; 542 rcA = mf_->getSSARegMap()->getRegClass(intA->reg); 543 rcB = mf_->getSSARegMap()->getRegClass(intB->reg); 544 // if they are not of the same register class we continue 545 if (rcA != rcB) 546 continue; 547 548 // if their intervals do not overlap we join them 549 if (!intB->overlaps(*intA)) { 550 intA->join(*intB); 551 r2iB->second = r2iA->second; 552 r2rMap_.insert(std::make_pair(intB->reg, intA->reg)); 553 intervals_.erase(intB); 554 } 555 } else if (MRegisterInfo::isPhysicalRegister(intA->reg) ^ 556 MRegisterInfo::isPhysicalRegister(intB->reg)) { 557 if (MRegisterInfo::isPhysicalRegister(intB->reg)) { 558 std::swap(regA, regB); 559 std::swap(intA, intB); 560 std::swap(r2iA, r2iB); 561 } 562 563 assert(MRegisterInfo::isPhysicalRegister(intA->reg) && 564 MRegisterInfo::isVirtualRegister(intB->reg) && 565 "A must be physical and B must be virtual"); 566 567 const TargetRegisterClass *rcA, *rcB; 568 rcA = mri_->getRegClass(intA->reg); 569 rcB = mf_->getSSARegMap()->getRegClass(intB->reg); 570 // if they are not of the same register class we continue 571 if (rcA != rcB) 572 continue; 573 574 if (!intA->overlaps(*intB) && 575 !overlapsAliases(*intA, *intB)) { 576 intA->join(*intB); 577 r2iB->second = r2iA->second; 578 r2rMap_.insert(std::make_pair(intB->reg, intA->reg)); 579 intervals_.erase(intB); 580 } 581 } 582 } 583 } 584} 585 586namespace { 587 // DepthMBBCompare - Comparison predicate that sort first based on the loop 588 // depth of the basic block (the unsigned), and then on the MBB number. 589 struct DepthMBBCompare { 590 typedef std::pair<unsigned, MachineBasicBlock*> DepthMBBPair; 591 bool operator()(const DepthMBBPair &LHS, const DepthMBBPair &RHS) const { 592 if (LHS.first > RHS.first) return true; // Deeper loops first 593 return LHS.first == RHS.first && 594 LHS.second->getNumber() < RHS.second->getNumber(); 595 } 596 }; 597} 598 599void LiveIntervals::joinIntervals() { 600 DEBUG(std::cerr << "********** JOINING INTERVALS ***********\n"); 601 602 const LoopInfo &LI = getAnalysis<LoopInfo>(); 603 if (LI.begin() == LI.end()) { 604 // If there are no loops in the function, join intervals in function order. 605 for (MachineFunction::iterator I = mf_->begin(), E = mf_->end(); 606 I != E; ++I) 607 joinIntervalsInMachineBB(I); 608 } else { 609 // Otherwise, join intervals in inner loops before other intervals. 610 // Unfortunately we can't just iterate over loop hierarchy here because 611 // there may be more MBB's than BB's. Collect MBB's for sorting. 612 std::vector<std::pair<unsigned, MachineBasicBlock*> > MBBs; 613 for (MachineFunction::iterator I = mf_->begin(), E = mf_->end(); 614 I != E; ++I) 615 MBBs.push_back(std::make_pair(LI.getLoopDepth(I->getBasicBlock()), I)); 616 617 // Sort by loop depth. 618 std::sort(MBBs.begin(), MBBs.end(), DepthMBBCompare()); 619 620 // Finally, join intervals in loop nest order. 621 for (unsigned i = 0, e = MBBs.size(); i != e; ++i) 622 joinIntervalsInMachineBB(MBBs[i].second); 623 } 624} 625 626bool LiveIntervals::overlapsAliases(const LiveInterval& lhs, 627 const LiveInterval& rhs) const 628{ 629 assert(MRegisterInfo::isPhysicalRegister(lhs.reg) && 630 "first interval must describe a physical register"); 631 632 for (const unsigned* as = mri_->getAliasSet(lhs.reg); *as; ++as) { 633 Reg2IntervalMap::const_iterator r2i = r2iMap_.find(*as); 634 assert(r2i != r2iMap_.end() && "alias does not have interval?"); 635 if (rhs.overlaps(*r2i->second)) 636 return true; 637 } 638 639 return false; 640} 641 642LiveInterval& LiveIntervals::getOrCreateInterval(unsigned reg) 643{ 644 Reg2IntervalMap::iterator r2iit = r2iMap_.lower_bound(reg); 645 if (r2iit == r2iMap_.end() || r2iit->first != reg) { 646 intervals_.push_back(LiveInterval(reg)); 647 r2iit = r2iMap_.insert(r2iit, std::make_pair(reg, --intervals_.end())); 648 } 649 650 return *r2iit->second; 651} 652 653LiveInterval::LiveInterval(unsigned r) 654 : reg(r), 655 weight((MRegisterInfo::isPhysicalRegister(r) ? HUGE_VAL : 0.0F)) 656{ 657} 658 659bool LiveInterval::spilled() const 660{ 661 return (weight == HUGE_VAL && 662 MRegisterInfo::isVirtualRegister(reg)); 663} 664 665// An example for liveAt(): 666// 667// this = [1,4), liveAt(0) will return false. The instruction defining 668// this spans slots [0,3]. The interval belongs to an spilled 669// definition of the variable it represents. This is because slot 1 is 670// used (def slot) and spans up to slot 3 (store slot). 671// 672bool LiveInterval::liveAt(unsigned index) const 673{ 674 Range dummy(index, index+1); 675 Ranges::const_iterator r = std::upper_bound(ranges.begin(), 676 ranges.end(), 677 dummy); 678 if (r == ranges.begin()) 679 return false; 680 681 --r; 682 return index >= r->first && index < r->second; 683} 684 685// An example for overlaps(): 686// 687// 0: A = ... 688// 4: B = ... 689// 8: C = A + B ;; last use of A 690// 691// The live intervals should look like: 692// 693// A = [3, 11) 694// B = [7, x) 695// C = [11, y) 696// 697// A->overlaps(C) should return false since we want to be able to join 698// A and C. 699bool LiveInterval::overlaps(const LiveInterval& other) const 700{ 701 Ranges::const_iterator i = ranges.begin(); 702 Ranges::const_iterator ie = ranges.end(); 703 Ranges::const_iterator j = other.ranges.begin(); 704 Ranges::const_iterator je = other.ranges.end(); 705 if (i->first < j->first) { 706 i = std::upper_bound(i, ie, *j); 707 if (i != ranges.begin()) --i; 708 } 709 else if (j->first < i->first) { 710 j = std::upper_bound(j, je, *i); 711 if (j != other.ranges.begin()) --j; 712 } 713 714 while (i != ie && j != je) { 715 if (i->first == j->first) { 716 return true; 717 } 718 else { 719 if (i->first > j->first) { 720 swap(i, j); 721 swap(ie, je); 722 } 723 assert(i->first < j->first); 724 725 if (i->second > j->first) { 726 return true; 727 } 728 else { 729 ++i; 730 } 731 } 732 } 733 734 return false; 735} 736 737void LiveInterval::addRange(unsigned start, unsigned end) 738{ 739 assert(start < end && "Invalid range to add!"); 740 DEBUG(std::cerr << " +[" << start << ',' << end << ")"); 741 //assert(start < end && "invalid range?"); 742 Range range = std::make_pair(start, end); 743 Ranges::iterator it = 744 ranges.insert(std::upper_bound(ranges.begin(), ranges.end(), range), 745 range); 746 747 it = mergeRangesForward(it); 748 it = mergeRangesBackward(it); 749} 750 751void LiveInterval::join(const LiveInterval& other) 752{ 753 DEBUG(std::cerr << "\t\tjoining " << *this << " with " << other); 754 Ranges::iterator cur = ranges.begin(); 755 756 for (Ranges::const_iterator i = other.ranges.begin(), 757 e = other.ranges.end(); i != e; ++i) { 758 cur = ranges.insert(std::upper_bound(cur, ranges.end(), *i), *i); 759 cur = mergeRangesForward(cur); 760 cur = mergeRangesBackward(cur); 761 } 762 weight += other.weight; 763 ++numJoins; 764 DEBUG(std::cerr << ". Result = " << *this << "\n"); 765} 766 767LiveInterval::Ranges::iterator LiveInterval:: 768mergeRangesForward(Ranges::iterator it) 769{ 770 Ranges::iterator n; 771 while ((n = next(it)) != ranges.end()) { 772 if (n->first > it->second) 773 break; 774 it->second = std::max(it->second, n->second); 775 n = ranges.erase(n); 776 } 777 return it; 778} 779 780LiveInterval::Ranges::iterator LiveInterval:: 781mergeRangesBackward(Ranges::iterator it) 782{ 783 while (it != ranges.begin()) { 784 Ranges::iterator p = prior(it); 785 if (it->first > p->second) 786 break; 787 788 it->first = std::min(it->first, p->first); 789 it->second = std::max(it->second, p->second); 790 it = ranges.erase(p); 791 } 792 793 return it; 794} 795 796std::ostream& llvm::operator<<(std::ostream& os, const LiveInterval& li) 797{ 798 os << "%reg" << li.reg << ',' << li.weight; 799 if (li.empty()) 800 return os << "EMPTY"; 801 802 os << " = "; 803 for (LiveInterval::Ranges::const_iterator 804 i = li.ranges.begin(), e = li.ranges.end(); i != e; ++i) { 805 os << "[" << i->first << "," << i->second << ")"; 806 } 807 return os; 808} 809