LiveIntervalAnalysis.cpp revision af25473d5e99e0c0968746e12d8827e4b712bd31
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/Function.h" 21#include "llvm/Analysis/LoopInfo.h" 22#include "llvm/CodeGen/LiveVariables.h" 23#include "llvm/CodeGen/MachineFrameInfo.h" 24#include "llvm/CodeGen/MachineFunctionPass.h" 25#include "llvm/CodeGen/MachineInstr.h" 26#include "llvm/CodeGen/Passes.h" 27#include "llvm/CodeGen/SSARegMap.h" 28#include "llvm/Target/MRegisterInfo.h" 29#include "llvm/Target/TargetInstrInfo.h" 30#include "llvm/Target/TargetMachine.h" 31#include "llvm/Target/TargetRegInfo.h" 32#include "llvm/Support/CFG.h" 33#include "Support/Debug.h" 34#include "Support/DepthFirstIterator.h" 35#include "Support/Statistic.h" 36#include <cmath> 37#include <iostream> 38#include <limits> 39 40using namespace llvm; 41 42namespace { 43 RegisterAnalysis<LiveIntervals> X("liveintervals", 44 "Live Interval Analysis"); 45 46 Statistic<> numIntervals("liveintervals", "Number of intervals"); 47}; 48 49void LiveIntervals::getAnalysisUsage(AnalysisUsage &AU) const 50{ 51 AU.addPreserved<LiveVariables>(); 52 AU.addRequired<LiveVariables>(); 53 AU.addPreservedID(PHIEliminationID); 54 AU.addRequiredID(PHIEliminationID); 55 AU.addRequiredID(TwoAddressInstructionPassID); 56 AU.addRequired<LoopInfo>(); 57 MachineFunctionPass::getAnalysisUsage(AU); 58} 59 60/// runOnMachineFunction - Register allocate the whole function 61/// 62bool LiveIntervals::runOnMachineFunction(MachineFunction &fn) { 63 DEBUG(std::cerr << "Machine Function\n"); 64 mf_ = &fn; 65 tm_ = &fn.getTarget(); 66 mri_ = tm_->getRegisterInfo(); 67 lv_ = &getAnalysis<LiveVariables>(); 68 mbbi2mbbMap_.clear(); 69 mi2iMap_.clear(); 70 r2iMap_.clear(); 71 r2iMap_.clear(); 72 intervals_.clear(); 73 74 // number MachineInstrs 75 unsigned miIndex = 0; 76 for (MachineFunction::iterator mbb = mf_->begin(), mbbEnd = mf_->end(); 77 mbb != mbbEnd; ++mbb) { 78 const std::pair<MachineBasicBlock*, unsigned>& entry = 79 lv_->getMachineBasicBlockInfo(&*mbb); 80 bool inserted = mbbi2mbbMap_.insert(std::make_pair(entry.second, 81 entry.first)).second; 82 assert(inserted && "multiple index -> MachineBasicBlock"); 83 84 for (MachineBasicBlock::iterator mi = mbb->begin(), miEnd = mbb->end(); 85 mi != miEnd; ++mi) { 86 inserted = mi2iMap_.insert(std::make_pair(*mi, miIndex)).second; 87 assert(inserted && "multiple MachineInstr -> index mappings"); 88 ++miIndex; 89 } 90 } 91 92 computeIntervals(); 93 94 // compute spill weights 95 const LoopInfo& loopInfo = getAnalysis<LoopInfo>(); 96 const TargetInstrInfo& tii = tm_->getInstrInfo(); 97 98 for (MbbIndex2MbbMap::iterator 99 it = mbbi2mbbMap_.begin(), itEnd = mbbi2mbbMap_.end(); 100 it != itEnd; ++it) { 101 MachineBasicBlock* mbb = it->second; 102 103 unsigned loopDepth = loopInfo.getLoopDepth(mbb->getBasicBlock()); 104 105 for (MachineBasicBlock::iterator mi = mbb->begin(), miEnd = mbb->end(); 106 mi != miEnd; ++mi) { 107 MachineInstr* instr = *mi; 108 for (int i = instr->getNumOperands() - 1; i >= 0; --i) { 109 MachineOperand& mop = instr->getOperand(i); 110 111 if (!mop.isVirtualRegister()) 112 continue; 113 114 unsigned reg = mop.getAllocatedRegNum(); 115 Reg2IntervalMap::iterator r2iit = r2iMap_.find(reg); 116 assert(r2iit != r2iMap_.end()); 117 intervals_[r2iit->second].weight += pow(10.0F, loopDepth); 118 } 119 } 120 } 121 122 return true; 123} 124 125void LiveIntervals::printRegName(unsigned reg) const 126{ 127 if (reg < MRegisterInfo::FirstVirtualRegister) 128 std::cerr << mri_->getName(reg); 129 else 130 std::cerr << '%' << reg; 131} 132 133void LiveIntervals::handleVirtualRegisterDef(MachineBasicBlock* mbb, 134 MachineBasicBlock::iterator mi, 135 unsigned reg) 136{ 137 DEBUG(std::cerr << "\t\tregister: ";printRegName(reg); std::cerr << '\n'); 138 139 unsigned instrIndex = getInstructionIndex(*mi); 140 141 LiveVariables::VarInfo& vi = lv_->getVarInfo(reg); 142 143 Interval* interval = 0; 144 Reg2IntervalMap::iterator r2iit = r2iMap_.find(reg); 145 if (r2iit == r2iMap_.end()) { 146 // add new interval 147 intervals_.push_back(Interval(reg)); 148 // update interval index for this register 149 r2iMap_[reg] = intervals_.size() - 1; 150 interval = &intervals_.back(); 151 } 152 else { 153 interval = &intervals_[r2iit->second]; 154 } 155 156 for (MbbIndex2MbbMap::iterator 157 it = mbbi2mbbMap_.begin(), itEnd = mbbi2mbbMap_.end(); 158 it != itEnd; ++it) { 159 unsigned liveBlockIndex = it->first; 160 MachineBasicBlock* liveBlock = it->second; 161 if (liveBlockIndex < vi.AliveBlocks.size() && 162 vi.AliveBlocks[liveBlockIndex] && 163 !liveBlock->empty()) { 164 unsigned start = getInstructionIndex(liveBlock->front()); 165 unsigned end = getInstructionIndex(liveBlock->back()) + 1; 166 interval->addRange(start, end); 167 } 168 } 169 170 bool killedInDefiningBasicBlock = false; 171 for (int i = 0, e = vi.Kills.size(); i != e; ++i) { 172 MachineBasicBlock* killerBlock = vi.Kills[i].first; 173 MachineInstr* killerInstr = vi.Kills[i].second; 174 unsigned start = (mbb == killerBlock ? 175 instrIndex : 176 getInstructionIndex(killerBlock->front())); 177 unsigned end = getInstructionIndex(killerInstr) + 1; 178 if (start < end) { 179 killedInDefiningBasicBlock |= mbb == killerBlock; 180 interval->addRange(start, end); 181 } 182 } 183 184 if (!killedInDefiningBasicBlock) { 185 unsigned end = getInstructionIndex(mbb->back()) + 1; 186 interval->addRange(instrIndex, end); 187 } 188} 189 190void LiveIntervals::handlePhysicalRegisterDef(MachineBasicBlock* mbb, 191 MachineBasicBlock::iterator mi, 192 unsigned reg) 193{ 194 DEBUG(std::cerr << "\t\tregister: "; printRegName(reg)); 195 196 unsigned start = getInstructionIndex(*mi); 197 unsigned end = start; 198 199 // register can be dead by the instruction defining it but it can 200 // only be killed by subsequent instructions 201 202 for (LiveVariables::killed_iterator 203 ki = lv_->dead_begin(*mi), 204 ke = lv_->dead_end(*mi); 205 ki != ke; ++ki) { 206 if (reg == ki->second) { 207 end = getInstructionIndex(ki->first) + 1; 208 DEBUG(std::cerr << " dead\n"); 209 goto exit; 210 } 211 } 212 ++mi; 213 214 for (MachineBasicBlock::iterator e = mbb->end(); mi != e; ++mi) { 215 for (LiveVariables::killed_iterator 216 ki = lv_->dead_begin(*mi), 217 ke = lv_->dead_end(*mi); 218 ki != ke; ++ki) { 219 if (reg == ki->second) { 220 end = getInstructionIndex(ki->first) + 1; 221 DEBUG(std::cerr << " dead\n"); 222 goto exit; 223 } 224 } 225 226 for (LiveVariables::killed_iterator 227 ki = lv_->killed_begin(*mi), 228 ke = lv_->killed_end(*mi); 229 ki != ke; ++ki) { 230 if (reg == ki->second) { 231 end = getInstructionIndex(ki->first) + 1; 232 DEBUG(std::cerr << " killed\n"); 233 goto exit; 234 } 235 } 236 } 237exit: 238 assert(start < end && "did not find end of interval?"); 239 240 Reg2IntervalMap::iterator r2iit = r2iMap_.find(reg); 241 if (r2iit != r2iMap_.end()) { 242 unsigned ii = r2iit->second; 243 Interval& interval = intervals_[ii]; 244 interval.addRange(start, end); 245 } 246 else { 247 intervals_.push_back(Interval(reg)); 248 Interval& interval = intervals_.back(); 249 // update interval index for this register 250 r2iMap_[reg] = intervals_.size() - 1; 251 interval.addRange(start, end); 252 } 253} 254 255void LiveIntervals::handleRegisterDef(MachineBasicBlock* mbb, 256 MachineBasicBlock::iterator mi, 257 unsigned reg) 258{ 259 if (reg < MRegisterInfo::FirstVirtualRegister) { 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 309 if (!mop.isRegister()) 310 continue; 311 312 // handle defs - build intervals 313 if (mop.isDef()) 314 handleRegisterDef(mbb, mi, mop.getAllocatedRegNum()); 315 } 316 } 317 } 318 319 std::sort(intervals_.begin(), intervals_.end(), StartPointComp()); 320 DEBUG(std::copy(intervals_.begin(), intervals_.end(), 321 std::ostream_iterator<Interval>(std::cerr, "\n"))); 322} 323 324LiveIntervals::Interval::Interval(unsigned r) 325 : reg(r), hint(0), 326 weight((r < MRegisterInfo::FirstVirtualRegister ? 327 std::numeric_limits<float>::max() : 0.0F)) 328{ 329 330} 331 332void LiveIntervals::Interval::addRange(unsigned start, unsigned end) 333{ 334 DEBUG(std::cerr << "\t\t\tadding range: [" << start <<','<< end << ") -> "); 335 //assert(start < end && "invalid range?"); 336 Range range = std::make_pair(start, end); 337 Ranges::iterator it = 338 ranges.insert(std::upper_bound(ranges.begin(), ranges.end(), range), 339 range); 340 341 mergeRangesForward(it); 342 mergeRangesBackward(it); 343 DEBUG(std::cerr << *this << '\n'); 344} 345 346void LiveIntervals::Interval::mergeRangesForward(Ranges::iterator it) 347{ 348 for (Ranges::iterator next = it + 1; 349 next != ranges.end() && it->second >= next->first; ) { 350 it->second = std::max(it->second, next->second); 351 next = ranges.erase(next); 352 } 353} 354 355void LiveIntervals::Interval::mergeRangesBackward(Ranges::iterator it) 356{ 357 for (Ranges::iterator prev = it - 1; 358 it != ranges.begin() && it->first <= prev->second; ) { 359 it->first = std::min(it->first, prev->first); 360 it->second = std::max(it->second, prev->second); 361 it = ranges.erase(prev); 362 prev = it - 1; 363 } 364} 365 366bool LiveIntervals::Interval::liveAt(unsigned index) const 367{ 368 Ranges::const_iterator r = ranges.begin(); 369 while (r != ranges.end() && index < r->second) { 370 if (index >= r->first) 371 return true; 372 ++r; 373 } 374 return false; 375} 376 377bool LiveIntervals::Interval::overlaps(const Interval& other) const 378{ 379 Ranges::const_iterator i = ranges.begin(); 380 Ranges::const_iterator j = other.ranges.begin(); 381 382 while (i != ranges.end() && j != other.ranges.end()) { 383 if (i->first < j->first) { 384 if (i->second > j->first) { 385 return true; 386 } 387 else { 388 ++i; 389 } 390 } 391 else if (j->first < i->first) { 392 if (j->second > i->first) { 393 return true; 394 } 395 else { 396 ++j; 397 } 398 } 399 else { 400 return true; 401 } 402 } 403 404 return false; 405} 406 407std::ostream& llvm::operator<<(std::ostream& os, 408 const LiveIntervals::Interval& li) 409{ 410 os << "%reg" << li.reg << ',' << li.weight << " = "; 411 for (LiveIntervals::Interval::Ranges::const_iterator 412 i = li.ranges.begin(), e = li.ranges.end(); i != e; ++i) { 413 os << "[" << i->first << "," << i->second << ")"; 414 } 415 return os; 416} 417