LiveIntervalAnalysis.cpp revision 7a40eaaceec0af76d5b97610f3d4e7a47a19d245
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 allocatableRegisters_.clear(); 69 mbbi2mbbMap_.clear(); 70 mi2iMap_.clear(); 71 r2iMap_.clear(); 72 r2iMap_.clear(); 73 intervals_.clear(); 74 75 // mark allocatable registers 76 allocatableRegisters_.resize(MRegisterInfo::FirstVirtualRegister); 77 // Loop over all of the register classes... 78 for (MRegisterInfo::regclass_iterator 79 rci = mri_->regclass_begin(), rce = mri_->regclass_end(); 80 rci != rce; ++rci) { 81 // Loop over all of the allocatable registers in the function... 82 for (TargetRegisterClass::iterator 83 i = (*rci)->allocation_order_begin(*mf_), 84 e = (*rci)->allocation_order_end(*mf_); i != e; ++i) { 85 allocatableRegisters_[*i] = true; // The reg is allocatable! 86 } 87 } 88 89 // number MachineInstrs 90 unsigned miIndex = 0; 91 for (MachineFunction::iterator mbb = mf_->begin(), mbbEnd = mf_->end(); 92 mbb != mbbEnd; ++mbb) { 93 const std::pair<MachineBasicBlock*, unsigned>& entry = 94 lv_->getMachineBasicBlockInfo(&*mbb); 95 bool inserted = mbbi2mbbMap_.insert(std::make_pair(entry.second, 96 entry.first)).second; 97 assert(inserted && "multiple index -> MachineBasicBlock"); 98 99 for (MachineBasicBlock::iterator mi = mbb->begin(), miEnd = mbb->end(); 100 mi != miEnd; ++mi) { 101 inserted = mi2iMap_.insert(std::make_pair(*mi, miIndex)).second; 102 assert(inserted && "multiple MachineInstr -> index mappings"); 103 ++miIndex; 104 } 105 } 106 107 computeIntervals(); 108 109 // compute spill weights 110 const LoopInfo& loopInfo = getAnalysis<LoopInfo>(); 111 112 for (MbbIndex2MbbMap::iterator 113 it = mbbi2mbbMap_.begin(), itEnd = mbbi2mbbMap_.end(); 114 it != itEnd; ++it) { 115 MachineBasicBlock* mbb = it->second; 116 117 unsigned loopDepth = loopInfo.getLoopDepth(mbb->getBasicBlock()); 118 119 for (MachineBasicBlock::iterator mi = mbb->begin(), miEnd = mbb->end(); 120 mi != miEnd; ++mi) { 121 MachineInstr* instr = *mi; 122 for (int i = instr->getNumOperands() - 1; i >= 0; --i) { 123 MachineOperand& mop = instr->getOperand(i); 124 125 if (!mop.isVirtualRegister()) 126 continue; 127 128 unsigned reg = mop.getAllocatedRegNum(); 129 Reg2IntervalMap::iterator r2iit = r2iMap_.find(reg); 130 assert(r2iit != r2iMap_.end()); 131 intervals_[r2iit->second].weight += pow(10.0F, loopDepth); 132 } 133 } 134 } 135 136 return true; 137} 138 139void LiveIntervals::printRegName(unsigned reg) const 140{ 141 if (reg < MRegisterInfo::FirstVirtualRegister) 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\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_.find(reg); 159 if (r2iit == r2iMap_.end()) { 160 // add new interval 161 intervals_.push_back(Interval(reg)); 162 // update interval index for this register 163 r2iMap_[reg] = intervals_.size() - 1; 164 interval = &intervals_.back(); 165 } 166 else { 167 interval = &intervals_[r2iit->second]; 168 } 169 170 for (MbbIndex2MbbMap::iterator 171 it = mbbi2mbbMap_.begin(), itEnd = mbbi2mbbMap_.end(); 172 it != itEnd; ++it) { 173 unsigned liveBlockIndex = it->first; 174 MachineBasicBlock* liveBlock = it->second; 175 if (liveBlockIndex < vi.AliveBlocks.size() && 176 vi.AliveBlocks[liveBlockIndex] && 177 !liveBlock->empty()) { 178 unsigned start = getInstructionIndex(liveBlock->front()); 179 unsigned end = getInstructionIndex(liveBlock->back()) + 1; 180 interval->addRange(start, end); 181 } 182 } 183 184 bool killedInDefiningBasicBlock = false; 185 for (int i = 0, e = vi.Kills.size(); i != e; ++i) { 186 MachineBasicBlock* killerBlock = vi.Kills[i].first; 187 MachineInstr* killerInstr = vi.Kills[i].second; 188 unsigned start = (mbb == killerBlock ? 189 instrIndex : 190 getInstructionIndex(killerBlock->front())); 191 unsigned end = getInstructionIndex(killerInstr) + 1; 192 if (start < end) { 193 killedInDefiningBasicBlock |= mbb == killerBlock; 194 interval->addRange(start, end); 195 } 196 } 197 198 if (!killedInDefiningBasicBlock) { 199 unsigned end = getInstructionIndex(mbb->back()) + 1; 200 interval->addRange(instrIndex, end); 201 } 202} 203 204void LiveIntervals::handlePhysicalRegisterDef(MachineBasicBlock* mbb, 205 MachineBasicBlock::iterator mi, 206 unsigned reg) 207{ 208 DEBUG(std::cerr << "\t\t\tregister: ";printRegName(reg); std::cerr << '\n'); 209 if (!lv_->getAllocatablePhysicalRegisters()[reg]) { 210 DEBUG(std::cerr << "\t\t\t\tnon allocatable register: ignoring\n"); 211 return; 212 } 213 214 unsigned start = getInstructionIndex(*mi); 215 unsigned end = start; 216 217 for (MachineBasicBlock::iterator e = mbb->end(); mi != e; ++mi) { 218 for (LiveVariables::killed_iterator 219 ki = lv_->dead_begin(*mi), 220 ke = lv_->dead_end(*mi); 221 ki != ke; ++ki) { 222 if (reg == ki->second) { 223 end = getInstructionIndex(ki->first) + 1; 224 goto exit; 225 } 226 } 227 228 for (LiveVariables::killed_iterator 229 ki = lv_->killed_begin(*mi), 230 ke = lv_->killed_end(*mi); 231 ki != ke; ++ki) { 232 if (reg == ki->second) { 233 end = getInstructionIndex(ki->first) + 1; 234 goto exit; 235 } 236 } 237 } 238exit: 239 assert(start < end && "did not find end of interval?"); 240 241 Reg2IntervalMap::iterator r2iit = r2iMap_.find(reg); 242 if (r2iit != r2iMap_.end()) { 243 unsigned ii = r2iit->second; 244 Interval& interval = intervals_[ii]; 245 interval.addRange(start, end); 246 } 247 else { 248 intervals_.push_back(Interval(reg)); 249 Interval& interval = intervals_.back(); 250 // update interval index for this register 251 r2iMap_[reg] = intervals_.size() - 1; 252 interval.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 (allocatableRegisters_[reg]) { 262 handlePhysicalRegisterDef(mbb, mi, reg); 263 } 264 } 265 else { 266 handleVirtualRegisterDef(mbb, mi, reg); 267 } 268} 269 270unsigned LiveIntervals::getInstructionIndex(MachineInstr* instr) const 271{ 272 assert(mi2iMap_.find(instr) != mi2iMap_.end() && 273 "instruction not assigned a number"); 274 return mi2iMap_.find(instr)->second; 275} 276 277/// computeIntervals - computes the live intervals for virtual 278/// registers. for some ordering of the machine instructions [1,N] a 279/// live interval is an interval [i, j] where 1 <= i <= j <= N for 280/// which a variable is live 281void LiveIntervals::computeIntervals() 282{ 283 DEBUG(std::cerr << "computing live intervals:\n"); 284 285 for (MbbIndex2MbbMap::iterator 286 it = mbbi2mbbMap_.begin(), itEnd = mbbi2mbbMap_.end(); 287 it != itEnd; ++it) { 288 MachineBasicBlock* mbb = it->second; 289 DEBUG(std::cerr << "machine basic block: " 290 << mbb->getBasicBlock()->getName() << "\n"); 291 292 for (MachineBasicBlock::iterator mi = mbb->begin(), miEnd = mbb->end(); 293 mi != miEnd; ++mi) { 294 MachineInstr* instr = *mi; 295 const TargetInstrDescriptor& tid = 296 tm_->getInstrInfo().get(instr->getOpcode()); 297 DEBUG(std::cerr << "\t\tinstruction[" 298 << getInstructionIndex(instr) << "]: "; 299 instr->print(std::cerr, *tm_);); 300 301 // handle implicit defs 302 for (const unsigned* id = tid.ImplicitDefs; *id; ++id) { 303 unsigned physReg = *id; 304 handlePhysicalRegisterDef(mbb, mi, physReg); 305 } 306 307 // handle explicit defs 308 for (int i = instr->getNumOperands() - 1; i >= 0; --i) { 309 MachineOperand& mop = instr->getOperand(i); 310 311 if (!mop.isRegister()) 312 continue; 313 314 unsigned reg = mop.getAllocatedRegNum(); 315 // handle defs - build intervals 316 if (mop.isDef()) { 317 if (reg < MRegisterInfo::FirstVirtualRegister) 318 handlePhysicalRegisterDef(mbb, mi, reg); 319 else 320 handleVirtualRegisterDef(mbb, mi, reg); 321 } 322 } 323 } 324 } 325 326 std::sort(intervals_.begin(), intervals_.end(), StartPointComp()); 327 DEBUG(std::copy(intervals_.begin(), intervals_.end(), 328 std::ostream_iterator<Interval>(std::cerr, "\n"))); 329} 330 331LiveIntervals::Interval::Interval(unsigned r) 332 : reg(r), 333 weight((r < MRegisterInfo::FirstVirtualRegister ? 334 std::numeric_limits<float>::max() : 0.0F)) 335{ 336 337} 338 339void LiveIntervals::Interval::addRange(unsigned start, unsigned end) 340{ 341 DEBUG(std::cerr << "\t\t\t\tadding range: [" << start <<','<< end << "]\n"); 342 //assert(start < end && "invalid range?"); 343 Range range = std::make_pair(start, end); 344 Ranges::iterator it = 345 ranges.insert(std::upper_bound(ranges.begin(), ranges.end(), range), 346 range); 347 348 DEBUG(std::cerr << "\t\t\t\tbefore merge forward: " << *this << '\n'); 349 mergeRangesForward(it); 350 DEBUG(std::cerr << "\t\t\t\tbefore merge backward: " << *this << '\n'); 351 mergeRangesBackward(it); 352 DEBUG(std::cerr << "\t\t\t\tafter merging: " << *this << '\n'); 353} 354 355void LiveIntervals::Interval::mergeRangesForward(Ranges::iterator it) 356{ 357 for (Ranges::iterator next = it + 1; 358 next != ranges.end() && it->second >= next->first; ) { 359 it->second = std::max(it->second, next->second); 360 next = ranges.erase(next); 361 } 362} 363 364void LiveIntervals::Interval::mergeRangesBackward(Ranges::iterator it) 365{ 366 for (Ranges::iterator prev = it - 1; 367 it != ranges.begin() && it->first <= prev->second; ) { 368 it->first = std::min(it->first, prev->first); 369 it->second = std::max(it->second, prev->second); 370 it = ranges.erase(prev); 371 prev = it - 1; 372 } 373} 374 375bool LiveIntervals::Interval::liveAt(unsigned index) const 376{ 377 Ranges::const_iterator r = ranges.begin(); 378 while (r != ranges.end() && index < r->second) { 379 if (index >= r->first) 380 return true; 381 ++r; 382 } 383 return false; 384} 385 386bool LiveIntervals::Interval::overlaps(const Interval& other) const 387{ 388 std::vector<bool> bitMap(end(), false); 389 for (Ranges::const_iterator r = ranges.begin(); r != ranges.end(); ++r) { 390 for (unsigned i = r->first; i < r->second; ++i) 391 bitMap[i] = true; 392 } 393 for (Ranges::const_iterator r = other.ranges.begin(); 394 r != other.ranges.end(); ++r) { 395 for (unsigned i = r->first; 396 i < r->second && i < bitMap.size(); ++i) 397 if (bitMap[i]) 398 return true; 399 } 400 401 return false; 402} 403 404std::ostream& llvm::operator<<(std::ostream& os, 405 const LiveIntervals::Interval& li) 406{ 407 os << "%reg" << li.reg << ',' << li.weight << " = "; 408 for (LiveIntervals::Interval::Ranges::const_iterator 409 i = li.ranges.begin(), e = li.ranges.end(); i != e; ++i) { 410 os << "[" << i->first << "," << i->second << "]"; 411 } 412 return os; 413} 414