LiveIntervalAnalysis.cpp revision 52220f61bba91ab787d4cc0aee47df4e2ca55c04
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 <cmath> 34#include <iostream> 35#include <limits> 36 37using namespace llvm; 38 39namespace { 40 RegisterAnalysis<LiveIntervals> X("liveintervals", 41 "Live Interval Analysis"); 42 43 Statistic<> numIntervals("liveintervals", "Number of intervals"); 44 Statistic<> numJoined ("liveintervals", "Number of intervals joined"); 45 46 cl::opt<bool> 47 join("join-liveintervals", 48 cl::desc("Join compatible live intervals"), 49 cl::init(true)); 50}; 51 52void LiveIntervals::getAnalysisUsage(AnalysisUsage &AU) const 53{ 54 AU.addPreserved<LiveVariables>(); 55 AU.addRequired<LiveVariables>(); 56 AU.addPreservedID(PHIEliminationID); 57 AU.addRequiredID(PHIEliminationID); 58 AU.addRequiredID(TwoAddressInstructionPassID); 59 AU.addRequired<LoopInfo>(); 60 MachineFunctionPass::getAnalysisUsage(AU); 61} 62 63void LiveIntervals::releaseMemory() 64{ 65 mbbi2mbbMap_.clear(); 66 mi2iMap_.clear(); 67 r2iMap_.clear(); 68 r2iMap_.clear(); 69 r2rMap_.clear(); 70 intervals_.clear(); 71} 72 73 74/// runOnMachineFunction - Register allocate the whole function 75/// 76bool LiveIntervals::runOnMachineFunction(MachineFunction &fn) { 77 DEBUG(std::cerr << "Machine Function\n"); 78 mf_ = &fn; 79 tm_ = &fn.getTarget(); 80 mri_ = tm_->getRegisterInfo(); 81 lv_ = &getAnalysis<LiveVariables>(); 82 83 // number MachineInstrs 84 unsigned miIndex = 0; 85 for (MachineFunction::iterator mbb = mf_->begin(), mbbEnd = mf_->end(); 86 mbb != mbbEnd; ++mbb) { 87 const std::pair<MachineBasicBlock*, unsigned>& entry = 88 lv_->getMachineBasicBlockInfo(mbb); 89 bool inserted = mbbi2mbbMap_.insert(std::make_pair(entry.second, 90 entry.first)).second; 91 assert(inserted && "multiple index -> MachineBasicBlock"); 92 93 for (MachineBasicBlock::iterator mi = mbb->begin(), miEnd = mbb->end(); 94 mi != miEnd; ++mi) { 95 inserted = mi2iMap_.insert(std::make_pair(*mi, miIndex)).second; 96 assert(inserted && "multiple MachineInstr -> index mappings"); 97 ++miIndex; 98 } 99 } 100 101 computeIntervals(); 102 103 // compute spill weights 104 const LoopInfo& loopInfo = getAnalysis<LoopInfo>(); 105 const TargetInstrInfo& tii = tm_->getInstrInfo(); 106 107 for (MachineFunction::const_iterator mbbi = mf_->begin(), 108 mbbe = mf_->end(); mbbi != mbbe; ++mbbi) { 109 const MachineBasicBlock* mbb = mbbi; 110 unsigned loopDepth = loopInfo.getLoopDepth(mbb->getBasicBlock()); 111 112 if (loopDepth) { 113 for (MachineBasicBlock::const_iterator mii = mbb->begin(), 114 mie = mbb->end(); mii != mie; ++mii) { 115 MachineInstr* mi = *mii; 116 117 for (int i = mi->getNumOperands() - 1; i >= 0; --i) { 118 MachineOperand& mop = mi->getOperand(i); 119 120 if (!mop.isVirtualRegister()) 121 continue; 122 123 unsigned reg = mop.getAllocatedRegNum(); 124 Reg2IntervalMap::iterator r2iit = r2iMap_.find(reg); 125 assert(r2iit != r2iMap_.end()); 126 r2iit->second->weight += pow(10.0F, loopDepth); 127 } 128 } 129 } 130 } 131 132 // join intervals if requested 133 if (join) joinIntervals(); 134 135 numIntervals += intervals_.size(); 136 137 return true; 138} 139 140void LiveIntervals::printRegName(unsigned reg) const 141{ 142 if (reg < MRegisterInfo::FirstVirtualRegister) 143 std::cerr << mri_->getName(reg); 144 else 145 std::cerr << '%' << reg; 146} 147 148void LiveIntervals::handleVirtualRegisterDef(MachineBasicBlock* mbb, 149 MachineBasicBlock::iterator mi, 150 unsigned reg) 151{ 152 DEBUG(std::cerr << "\t\tregister: ";printRegName(reg); std::cerr << '\n'); 153 154 unsigned instrIndex = getInstructionIndex(*mi); 155 156 LiveVariables::VarInfo& vi = lv_->getVarInfo(reg); 157 158 Interval* interval = 0; 159 Reg2IntervalMap::iterator r2iit = r2iMap_.lower_bound(reg); 160 if (r2iit == r2iMap_.end() || r2iit->first != reg) { 161 // add new interval 162 intervals_.push_back(Interval(reg)); 163 // update interval index for this register 164 r2iMap_.insert(r2iit, std::make_pair(reg, --intervals_.end())); 165 interval = &intervals_.back(); 166 } 167 else { 168 interval = &*r2iit->second; 169 } 170 171 // iterate over all of the blocks that the variable is completely 172 // live in, adding them to the live interval 173 for (unsigned i = 0, e = vi.AliveBlocks.size(); i != e; ++i) { 174 if (vi.AliveBlocks[i]) { 175 MachineBasicBlock* mbb = lv_->getIndexMachineBasicBlock(i); 176 if (!mbb->empty()) { 177 interval->addRange(getInstructionIndex(mbb->front()), 178 getInstructionIndex(mbb->back()) + 1); 179 } 180 } 181 } 182 183 bool killedInDefiningBasicBlock = false; 184 for (int i = 0, e = vi.Kills.size(); i != e; ++i) { 185 MachineBasicBlock* killerBlock = vi.Kills[i].first; 186 MachineInstr* killerInstr = vi.Kills[i].second; 187 unsigned start = (mbb == killerBlock ? 188 instrIndex : 189 getInstructionIndex(killerBlock->front())); 190 unsigned end = getInstructionIndex(killerInstr) + 1; 191 // we do not want to add invalid ranges. these can happen when 192 // a variable has its latest use and is redefined later on in 193 // the same basic block (common with variables introduced by 194 // PHI elimination) 195 if (start < end) { 196 killedInDefiningBasicBlock |= mbb == killerBlock; 197 interval->addRange(start, end); 198 } 199 } 200 201 if (!killedInDefiningBasicBlock) { 202 unsigned end = getInstructionIndex(mbb->back()) + 1; 203 interval->addRange(instrIndex, end); 204 } 205} 206 207void LiveIntervals::handlePhysicalRegisterDef(MachineBasicBlock* mbb, 208 MachineBasicBlock::iterator mi, 209 unsigned reg) 210{ 211 typedef LiveVariables::killed_iterator KillIter; 212 213 DEBUG(std::cerr << "\t\tregister: "; printRegName(reg)); 214 215 MachineBasicBlock::iterator e = mbb->end(); 216 unsigned start = getInstructionIndex(*mi); 217 unsigned end = start + 1; 218 219 // a variable can be dead by the instruction defining it 220 for (KillIter ki = lv_->dead_begin(*mi), ke = lv_->dead_end(*mi); 221 ki != ke; ++ki) { 222 if (reg == ki->second) { 223 DEBUG(std::cerr << " dead\n"); 224 goto exit; 225 } 226 } 227 228 // a variable can only be killed by subsequent instructions 229 do { 230 ++mi; 231 ++end; 232 for (KillIter ki = lv_->killed_begin(*mi), ke = lv_->killed_end(*mi); 233 ki != ke; ++ki) { 234 if (reg == ki->second) { 235 DEBUG(std::cerr << " killed\n"); 236 goto exit; 237 } 238 } 239 } while (mi != e); 240 241exit: 242 assert(start < end && "did not find end of interval?"); 243 244 Reg2IntervalMap::iterator r2iit = r2iMap_.lower_bound(reg); 245 if (r2iit != r2iMap_.end() && r2iit->first == reg) { 246 r2iit->second->addRange(start, end); 247 } 248 else { 249 intervals_.push_back(Interval(reg)); 250 // update interval index for this register 251 r2iMap_.insert(r2iit, std::make_pair(reg, --intervals_.end())); 252 intervals_.back().addRange(start, end); 253 } 254} 255 256void LiveIntervals::handleRegisterDef(MachineBasicBlock* mbb, 257 MachineBasicBlock::iterator mi, 258 unsigned reg) 259{ 260 if (reg < MRegisterInfo::FirstVirtualRegister) { 261 if (lv_->getAllocatablePhysicalRegisters()[reg]) { 262 handlePhysicalRegisterDef(mbb, mi, reg); 263 for (const unsigned* as = mri_->getAliasSet(reg); *as; ++as) 264 handlePhysicalRegisterDef(mbb, mi, *as); 265 } 266 } 267 else { 268 handleVirtualRegisterDef(mbb, mi, reg); 269 } 270} 271 272unsigned LiveIntervals::getInstructionIndex(MachineInstr* instr) const 273{ 274 assert(mi2iMap_.find(instr) != mi2iMap_.end() && 275 "instruction not assigned a number"); 276 return mi2iMap_.find(instr)->second; 277} 278 279/// computeIntervals - computes the live intervals for virtual 280/// registers. for some ordering of the machine instructions [1,N] a 281/// live interval is an interval [i, j) where 1 <= i <= j < N for 282/// which a variable is live 283void LiveIntervals::computeIntervals() 284{ 285 DEBUG(std::cerr << "computing live intervals:\n"); 286 287 for (MbbIndex2MbbMap::iterator 288 it = mbbi2mbbMap_.begin(), itEnd = mbbi2mbbMap_.end(); 289 it != itEnd; ++it) { 290 MachineBasicBlock* mbb = it->second; 291 DEBUG(std::cerr << "machine basic block: " 292 << mbb->getBasicBlock()->getName() << "\n"); 293 294 for (MachineBasicBlock::iterator mi = mbb->begin(), miEnd = mbb->end(); 295 mi != miEnd; ++mi) { 296 MachineInstr* instr = *mi; 297 const TargetInstrDescriptor& tid = 298 tm_->getInstrInfo().get(instr->getOpcode()); 299 DEBUG(std::cerr << "\t[" << getInstructionIndex(instr) << "] "; 300 instr->print(std::cerr, *tm_);); 301 302 // handle implicit defs 303 for (const unsigned* id = tid.ImplicitDefs; *id; ++id) 304 handleRegisterDef(mbb, mi, *id); 305 306 // handle explicit defs 307 for (int i = instr->getNumOperands() - 1; i >= 0; --i) { 308 MachineOperand& mop = instr->getOperand(i); 309 // handle register defs - build intervals 310 if (mop.isRegister() && mop.isDef()) 311 handleRegisterDef(mbb, mi, mop.getAllocatedRegNum()); 312 } 313 } 314 } 315 316 intervals_.sort(StartPointComp()); 317 DEBUG(std::copy(intervals_.begin(), intervals_.end(), 318 std::ostream_iterator<Interval>(std::cerr, "\n"))); 319} 320 321unsigned LiveIntervals::rep(unsigned reg) 322{ 323 Reg2RegMap::iterator it = r2rMap_.find(reg); 324 if (it != r2rMap_.end()) 325 return it->second = rep(it->second); 326 return reg; 327} 328 329void LiveIntervals::joinIntervals() 330{ 331 DEBUG(std::cerr << "joining compatible intervals:\n"); 332 333 const TargetInstrInfo& tii = tm_->getInstrInfo(); 334 335 for (MachineFunction::const_iterator mbbi = mf_->begin(), 336 mbbe = mf_->end(); mbbi != mbbe; ++mbbi) { 337 const MachineBasicBlock* mbb = mbbi; 338 DEBUG(std::cerr << "machine basic block: " 339 << mbb->getBasicBlock()->getName() << "\n"); 340 341 for (MachineBasicBlock::const_iterator mii = mbb->begin(), 342 mie = mbb->end(); mii != mie; ++mii) { 343 MachineInstr* mi = *mii; 344 const TargetInstrDescriptor& tid = 345 tm_->getInstrInfo().get(mi->getOpcode()); 346 DEBUG(std::cerr << "\t\tinstruction[" 347 << getInstructionIndex(mi) << "]: "; 348 mi->print(std::cerr, *tm_);); 349 350 unsigned srcReg, dstReg; 351 if (tii.isMoveInstr(*mi, srcReg, dstReg) && 352 (srcReg >= MRegisterInfo::FirstVirtualRegister || 353 lv_->getAllocatablePhysicalRegisters()[srcReg]) && 354 (dstReg >= MRegisterInfo::FirstVirtualRegister || 355 lv_->getAllocatablePhysicalRegisters()[dstReg])) { 356 357 // get representative registers 358 srcReg = rep(srcReg); 359 dstReg = rep(dstReg); 360 361 // if they are already joined we continue 362 if (srcReg == dstReg) 363 continue; 364 365 Reg2IntervalMap::iterator r2iSrc = r2iMap_.find(srcReg); 366 assert(r2iSrc != r2iMap_.end()); 367 Reg2IntervalMap::iterator r2iDst = r2iMap_.find(dstReg); 368 assert(r2iDst != r2iMap_.end()); 369 370 Intervals::iterator srcInt = r2iSrc->second; 371 Intervals::iterator dstInt = r2iDst->second; 372 373 // src is a physical register 374 if (srcInt->reg < MRegisterInfo::FirstVirtualRegister) { 375 if (dstInt->reg == srcInt->reg || 376 (dstInt->reg >= MRegisterInfo::FirstVirtualRegister && 377 !srcInt->overlaps(*dstInt) && 378 !overlapsAliases(*srcInt, *dstInt))) { 379 srcInt->join(*dstInt); 380 r2iDst->second = r2iSrc->second; 381 r2rMap_.insert(std::make_pair(dstInt->reg, srcInt->reg)); 382 intervals_.erase(dstInt); 383 } 384 } 385 // dst is a physical register 386 else if (dstInt->reg < MRegisterInfo::FirstVirtualRegister) { 387 if (srcInt->reg == dstInt->reg || 388 (srcInt->reg >= MRegisterInfo::FirstVirtualRegister && 389 !dstInt->overlaps(*srcInt) && 390 !overlapsAliases(*dstInt, *srcInt))) { 391 dstInt->join(*srcInt); 392 r2iSrc->second = r2iDst->second; 393 r2rMap_.insert(std::make_pair(srcInt->reg, dstInt->reg)); 394 intervals_.erase(srcInt); 395 } 396 } 397 // neither src nor dst are physical registers 398 else { 399 const TargetRegisterClass *srcRc, *dstRc; 400 srcRc = mf_->getSSARegMap()->getRegClass(srcInt->reg); 401 dstRc = mf_->getSSARegMap()->getRegClass(dstInt->reg); 402 403 if (srcRc == dstRc && !dstInt->overlaps(*srcInt)) { 404 srcInt->join(*dstInt); 405 r2iDst->second = r2iSrc->second; 406 r2rMap_.insert(std::make_pair(dstInt->reg, srcInt->reg)); 407 intervals_.erase(dstInt); 408 } 409 } 410 ++numJoined; 411 } 412 } 413 } 414 415 intervals_.sort(StartPointComp()); 416 DEBUG(std::copy(intervals_.begin(), intervals_.end(), 417 std::ostream_iterator<Interval>(std::cerr, "\n"))); 418 DEBUG(for (Reg2RegMap::const_iterator i = r2rMap_.begin(), 419 e = r2rMap_.end(); i != e; ++i) 420 std::cerr << i->first << " -> " << i->second << '\n';); 421 422} 423 424bool LiveIntervals::overlapsAliases(const Interval& lhs, 425 const Interval& rhs) const 426{ 427 assert(lhs.reg < MRegisterInfo::FirstVirtualRegister && 428 "first interval must describe a physical register"); 429 430 for (const unsigned* as = mri_->getAliasSet(lhs.reg); *as; ++as) { 431 Reg2IntervalMap::const_iterator r2i = r2iMap_.find(*as); 432 assert(r2i != r2iMap_.end() && "alias does not have interval?"); 433 if (rhs.overlaps(*r2i->second)) 434 return true; 435 } 436 437 return false; 438} 439 440LiveIntervals::Interval::Interval(unsigned r) 441 : reg(r), 442 weight((r < MRegisterInfo::FirstVirtualRegister ? 443 std::numeric_limits<float>::max() : 0.0F)) 444{ 445 446} 447 448// This example is provided becaues liveAt() is non-obvious: 449// 450// this = [1,2), liveAt(1) will return false. The idea is that the 451// variable is defined in 1 and not live after definition. So it was 452// dead to begin with (defined but never used). 453// 454// this = [1,3), liveAt(2) will return false. The variable is used at 455// 2 but 2 is the last use so the variable's allocated register is 456// available for reuse. 457bool LiveIntervals::Interval::liveAt(unsigned index) const 458{ 459 Range dummy(index, index+1); 460 Ranges::const_iterator r = std::upper_bound(ranges.begin(), 461 ranges.end(), 462 dummy); 463 if (r == ranges.begin()) 464 return false; 465 466 --r; 467 return index >= r->first && index < (r->second - 1); 468} 469 470// This example is provided because overlaps() is non-obvious: 471// 472// 0: A = ... 473// 1: B = ... 474// 2: C = A + B ;; last use of A 475// 476// The live intervals should look like: 477// 478// A = [0, 3) 479// B = [1, x) 480// C = [2, y) 481// 482// A->overlaps(C) should return false since we want to be able to join 483// A and C. 484bool LiveIntervals::Interval::overlaps(const Interval& other) const 485{ 486 Ranges::const_iterator i = ranges.begin(); 487 Ranges::const_iterator ie = ranges.end(); 488 Ranges::const_iterator j = other.ranges.begin(); 489 Ranges::const_iterator je = other.ranges.end(); 490 if (i->first < j->first) { 491 i = std::upper_bound(i, ie, *j); 492 if (i != ranges.begin()) --i; 493 } 494 else if (j->first < i->first) { 495 j = std::upper_bound(j, je, *i); 496 if (j != other.ranges.begin()) --j; 497 } 498 499 while (i != ie && j != je) { 500 if (i->first == j->first) { 501 return true; 502 } 503 else { 504 if (i->first > j->first) { 505 swap(i, j); 506 swap(ie, je); 507 } 508 assert(i->first < j->first); 509 510 if ((i->second - 1) > j->first) { 511 return true; 512 } 513 else { 514 ++i; 515 } 516 } 517 } 518 519 return false; 520} 521 522void LiveIntervals::Interval::addRange(unsigned start, unsigned end) 523{ 524 assert(start < end && "Invalid range to add!"); 525 DEBUG(std::cerr << "\t\t\tadding range: [" << start <<','<< end << ") -> "); 526 //assert(start < end && "invalid range?"); 527 Range range = std::make_pair(start, end); 528 Ranges::iterator it = 529 ranges.insert(std::upper_bound(ranges.begin(), ranges.end(), range), 530 range); 531 532 it = mergeRangesForward(it); 533 it = mergeRangesBackward(it); 534 DEBUG(std::cerr << "\t\t\t\tafter merging: " << *this << '\n'); 535} 536 537void LiveIntervals::Interval::join(const LiveIntervals::Interval& other) 538{ 539 DEBUG(std::cerr << "\t\t\t\tjoining intervals: " 540 << other << " and " << *this << '\n'); 541 Ranges::iterator cur = ranges.begin(); 542 543 for (Ranges::const_iterator i = other.ranges.begin(), 544 e = other.ranges.end(); i != e; ++i) { 545 cur = ranges.insert(std::upper_bound(cur, ranges.end(), *i), *i); 546 cur = mergeRangesForward(cur); 547 cur = mergeRangesBackward(cur); 548 } 549 if (reg >= MRegisterInfo::FirstVirtualRegister) 550 weight += other.weight; 551 552 DEBUG(std::cerr << "\t\t\t\tafter merging: " << *this << '\n'); 553} 554 555LiveIntervals::Interval::Ranges::iterator 556LiveIntervals::Interval::mergeRangesForward(Ranges::iterator it) 557{ 558 for (Ranges::iterator next = it + 1; 559 next != ranges.end() && it->second >= next->first; ) { 560 it->second = std::max(it->second, next->second); 561 next = ranges.erase(next); 562 } 563 return it; 564} 565 566LiveIntervals::Interval::Ranges::iterator 567LiveIntervals::Interval::mergeRangesBackward(Ranges::iterator it) 568{ 569 while (it != ranges.begin()) { 570 Ranges::iterator prev = it - 1; 571 if (it->first > prev->second) break; 572 573 it->first = std::min(it->first, prev->first); 574 it->second = std::max(it->second, prev->second); 575 it = ranges.erase(prev); 576 } 577 578 return it; 579} 580 581std::ostream& llvm::operator<<(std::ostream& os, 582 const LiveIntervals::Interval& li) 583{ 584 os << "%reg" << li.reg << ',' << li.weight << " = "; 585 for (LiveIntervals::Interval::Ranges::const_iterator 586 i = li.ranges.begin(), e = li.ranges.end(); i != e; ++i) { 587 os << "[" << i->first << "," << i->second << ")"; 588 } 589 return os; 590} 591