LiveIntervalAnalysis.cpp revision dd2cc65f34f9b7bfda1cd0c42becedfc361d46f8
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/CodeGen/LiveVariables.h" 22#include "llvm/CodeGen/MachineFrameInfo.h" 23#include "llvm/CodeGen/MachineFunctionPass.h" 24#include "llvm/CodeGen/MachineInstr.h" 25#include "llvm/CodeGen/Passes.h" 26#include "llvm/CodeGen/SSARegMap.h" 27#include "llvm/Target/MRegisterInfo.h" 28#include "llvm/Target/TargetInstrInfo.h" 29#include "llvm/Target/TargetMachine.h" 30#include "llvm/Target/TargetRegInfo.h" 31#include "llvm/Support/CFG.h" 32#include "Support/Debug.h" 33#include "Support/DepthFirstIterator.h" 34#include "Support/Statistic.h" 35#include <iostream> 36 37using namespace llvm; 38 39namespace { 40 RegisterAnalysis<LiveIntervals> X("liveintervals", 41 "Live Interval Analysis"); 42 43 Statistic<> numIntervals("liveintervals", "Number of intervals"); 44}; 45 46void LiveIntervals::getAnalysisUsage(AnalysisUsage &AU) const 47{ 48 AU.addPreserved<LiveVariables>(); 49 AU.addRequired<LiveVariables>(); 50 AU.addPreservedID(PHIEliminationID); 51 AU.addRequiredID(PHIEliminationID); 52 MachineFunctionPass::getAnalysisUsage(AU); 53} 54 55/// runOnMachineFunction - Register allocate the whole function 56/// 57bool LiveIntervals::runOnMachineFunction(MachineFunction &fn) { 58 DEBUG(std::cerr << "Machine Function\n"); 59 mf_ = &fn; 60 tm_ = &fn.getTarget(); 61 mri_ = tm_->getRegisterInfo(); 62 lv_ = &getAnalysis<LiveVariables>(); 63 allocatableRegisters_.clear(); 64 mbbi2mbbMap_.clear(); 65 mi2iMap_.clear(); 66 r2iMap_.clear(); 67 r2iMap_.clear(); 68 intervals_.clear(); 69 70 // mark allocatable registers 71 allocatableRegisters_.resize(MRegisterInfo::FirstVirtualRegister); 72 // Loop over all of the register classes... 73 for (MRegisterInfo::regclass_iterator 74 rci = mri_->regclass_begin(), rce = mri_->regclass_end(); 75 rci != rce; ++rci) { 76 // Loop over all of the allocatable registers in the function... 77 for (TargetRegisterClass::iterator 78 i = (*rci)->allocation_order_begin(*mf_), 79 e = (*rci)->allocation_order_end(*mf_); i != e; ++i) { 80 allocatableRegisters_[*i] = true; // The reg is allocatable! 81 } 82 } 83 84 // number MachineInstrs 85 unsigned miIndex = 0; 86 for (MachineFunction::iterator mbb = mf_->begin(), mbbEnd = mf_->end(); 87 mbb != mbbEnd; ++mbb) { 88 const std::pair<MachineBasicBlock*, unsigned>& entry = 89 lv_->getMachineBasicBlockInfo(&*mbb); 90 bool inserted = mbbi2mbbMap_.insert(std::make_pair(entry.second, 91 entry.first)).second; 92 assert(inserted && "multiple index -> MachineBasicBlock"); 93 94 for (MachineBasicBlock::iterator mi = mbb->begin(), miEnd = mbb->end(); 95 mi != miEnd; ++mi) { 96 inserted = mi2iMap_.insert(std::make_pair(*mi, miIndex)).second; 97 assert(inserted && "multiple MachineInstr -> index mappings"); 98 ++miIndex; 99 } 100 } 101 102 computeIntervals(); 103 104 return true; 105} 106 107void LiveIntervals::printRegName(unsigned reg) const 108{ 109 if (reg < MRegisterInfo::FirstVirtualRegister) 110 std::cerr << mri_->getName(reg); 111 else 112 std::cerr << '%' << reg; 113} 114 115void LiveIntervals::handleVirtualRegisterDef(MachineBasicBlock* mbb, 116 MachineBasicBlock::iterator mi, 117 unsigned reg) 118{ 119 DEBUG(std::cerr << "\t\t\tregister: ";printRegName(reg); std::cerr << '\n'); 120 121 unsigned instrIndex = getInstructionIndex(*mi); 122 123 LiveVariables::VarInfo& vi = lv_->getVarInfo(reg); 124 125 Interval* interval = 0; 126 Reg2IntervalMap::iterator r2iit = r2iMap_.find(reg); 127 if (r2iit == r2iMap_.end()) { 128 // add new interval 129 intervals_.push_back(Interval(reg)); 130 // update interval index for this register 131 r2iMap_[reg] = intervals_.size() - 1; 132 interval = &intervals_.back(); 133 } 134 else { 135 interval = &intervals_[r2iit->second]; 136 } 137 138 for (MbbIndex2MbbMap::iterator 139 it = mbbi2mbbMap_.begin(), itEnd = mbbi2mbbMap_.end(); 140 it != itEnd; ++it) { 141 unsigned liveBlockIndex = it->first; 142 MachineBasicBlock* liveBlock = it->second; 143 if (liveBlockIndex < vi.AliveBlocks.size() && 144 vi.AliveBlocks[liveBlockIndex]) { 145 unsigned start = getInstructionIndex(liveBlock->front()); 146 unsigned end = getInstructionIndex(liveBlock->back()) + 1; 147 interval->addRange(start, end); 148 } 149 } 150 151 bool killedInDefiningBasicBlock = false; 152 for (int i = 0, e = vi.Kills.size(); i != e; ++i) { 153 MachineBasicBlock* killerBlock = vi.Kills[i].first; 154 MachineInstr* killerInstr = vi.Kills[i].second; 155 killedInDefiningBasicBlock |= mbb == killerBlock; 156 unsigned start = (mbb == killerBlock ? 157 instrIndex : 158 getInstructionIndex(killerBlock->front())); 159 unsigned end = getInstructionIndex(killerInstr) + 1; 160 } 161 162 if (!killedInDefiningBasicBlock) { 163 unsigned end = getInstructionIndex(mbb->back()) + 1; 164 interval->addRange(instrIndex, end); 165 } 166} 167 168void LiveIntervals::handlePhysicalRegisterDef(MachineBasicBlock* mbb, 169 MachineBasicBlock::iterator mi, 170 unsigned reg) 171{ 172 DEBUG(std::cerr << "\t\t\tregister: ";printRegName(reg); std::cerr << '\n'); 173 if (!lv_->getAllocatablePhysicalRegisters()[reg]) { 174 DEBUG(std::cerr << "\t\t\t\tnon allocatable register: ignoring\n"); 175 return; 176 } 177 178 unsigned start = getInstructionIndex(*mi); 179 unsigned end = start; 180 181 for (MachineBasicBlock::iterator e = mbb->end(); mi != e; ++mi) { 182 for (LiveVariables::killed_iterator 183 ki = lv_->dead_begin(*mi), 184 ke = lv_->dead_end(*mi); 185 ki != ke; ++ki) { 186 if (reg == ki->second) { 187 end = getInstructionIndex(ki->first) + 1; 188 goto exit; 189 } 190 } 191 192 for (LiveVariables::killed_iterator 193 ki = lv_->killed_begin(*mi), 194 ke = lv_->killed_end(*mi); 195 ki != ke; ++ki) { 196 if (reg == ki->second) { 197 end = getInstructionIndex(ki->first) + 1; 198 goto exit; 199 } 200 } 201 } 202exit: 203 assert(start < end && "did not find end of interval?"); 204 205 Reg2IntervalMap::iterator r2iit = r2iMap_.find(reg); 206 if (r2iit != r2iMap_.end()) { 207 unsigned ii = r2iit->second; 208 Interval& interval = intervals_[ii]; 209 interval.addRange(start, end); 210 } 211 else { 212 intervals_.push_back(Interval(reg)); 213 Interval& interval = intervals_.back(); 214 // update interval index for this register 215 r2iMap_[reg] = intervals_.size() - 1; 216 interval.addRange(start, end); 217 } 218} 219 220void LiveIntervals::handleRegisterDef(MachineBasicBlock* mbb, 221 MachineBasicBlock::iterator mi, 222 unsigned reg) 223{ 224 if (reg < MRegisterInfo::FirstVirtualRegister) { 225 if (allocatableRegisters_[reg]) { 226 handlePhysicalRegisterDef(mbb, mi, reg); 227 } 228 } 229 else { 230 handleVirtualRegisterDef(mbb, mi, reg); 231 } 232} 233 234unsigned LiveIntervals::getInstructionIndex(MachineInstr* instr) const 235{ 236 assert(mi2iMap_.find(instr) != mi2iMap_.end() && 237 "instruction not assigned a number"); 238 return mi2iMap_.find(instr)->second; 239} 240 241/// computeIntervals - computes the live intervals for virtual 242/// registers. for some ordering of the machine instructions [1,N] a 243/// live interval is an interval [i, j] where 1 <= i <= j <= N for 244/// which a variable is live 245void LiveIntervals::computeIntervals() 246{ 247 DEBUG(std::cerr << "computing live intervals:\n"); 248 249 for (MbbIndex2MbbMap::iterator 250 it = mbbi2mbbMap_.begin(), itEnd = mbbi2mbbMap_.end(); 251 it != itEnd; ++it) { 252 MachineBasicBlock* mbb = it->second; 253 DEBUG(std::cerr << "machine basic block: " 254 << mbb->getBasicBlock()->getName() << "\n"); 255 for (MachineBasicBlock::iterator mi = mbb->begin(), miEnd = mbb->end(); 256 mi != miEnd; ++mi) { 257 MachineInstr* instr = *mi; 258 const TargetInstrDescriptor& tid = 259 tm_->getInstrInfo().get(instr->getOpcode()); 260 DEBUG(std::cerr << "\t\tinstruction[" 261 << getInstructionIndex(instr) << "]: "; 262 instr->print(std::cerr, *tm_);); 263 264 // handle implicit defs 265 for (const unsigned* id = tid.ImplicitDefs; *id; ++id) { 266 unsigned physReg = *id; 267 handlePhysicalRegisterDef(mbb, mi, physReg); 268 } 269 270 // handle explicit defs 271 for (int i = instr->getNumOperands() - 1; i >= 0; --i) { 272 MachineOperand& mop = instr->getOperand(i); 273 274 if (!mop.isRegister()) 275 continue; 276 277 if (mop.isDef()) { 278 unsigned reg = mop.getAllocatedRegNum(); 279 if (reg < MRegisterInfo::FirstVirtualRegister) 280 handlePhysicalRegisterDef(mbb, mi, reg); 281 else 282 handleVirtualRegisterDef(mbb, mi, reg); 283 } 284 } 285 } 286 } 287 288 std::sort(intervals_.begin(), intervals_.end(), StartPointComp()); 289 DEBUG(std::copy(intervals_.begin(), intervals_.end(), 290 std::ostream_iterator<Interval>(std::cerr, "\n"))); 291} 292 293void LiveIntervals::Interval::addRange(unsigned start, unsigned end) 294{ 295 DEBUG(std::cerr << "\t\t\t\tadding range: [" << start <<','<< end << "]\n"); 296 //assert(start < end && "invalid range?"); 297 Range range = std::make_pair(start, end); 298 Ranges::iterator it = 299 ranges.insert(std::upper_bound(ranges.begin(), ranges.end(), range), 300 range); 301 302 DEBUG(std::cerr << "\t\t\t\tbefore merge forward: " << *this << '\n'); 303 mergeRangesForward(it); 304 DEBUG(std::cerr << "\t\t\t\tbefore merge backward: " << *this << '\n'); 305 mergeRangesBackward(it); 306 DEBUG(std::cerr << "\t\t\t\tafter merging: " << *this << '\n'); 307} 308 309void LiveIntervals::Interval::mergeRangesForward(Ranges::iterator it) 310{ 311 for (Ranges::iterator next = it + 1; 312 next != ranges.end() && it->second >= next->first; ) { 313 it->second = std::max(it->second, next->second); 314 next = ranges.erase(next); 315 } 316} 317 318void LiveIntervals::Interval::mergeRangesBackward(Ranges::iterator it) 319{ 320 for (Ranges::iterator prev = it - 1; 321 it != ranges.begin() && it->first <= prev->second; ) { 322 it->first = std::min(it->first, prev->first); 323 it->second = std::max(it->second, prev->second); 324 it = ranges.erase(prev); 325 prev = it - 1; 326 } 327} 328 329std::ostream& llvm::operator<<(std::ostream& os, 330 const LiveIntervals::Interval& li) 331{ 332 os << "%reg" << li.reg << " = "; 333 for (LiveIntervals::Interval::Ranges::const_iterator 334 i = li.ranges.begin(), e = li.ranges.end(); i != e; ++i) { 335 os << "[" << i->first << "," << i->second << "]"; 336 } 337 return os; 338} 339