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