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