1 //===-- LiveIntervals.cpp - Live Interval Analysis ------------------------===//
3 // The LLVM Compiler Infrastructure
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.
8 //===----------------------------------------------------------------------===//
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.
16 //===----------------------------------------------------------------------===//
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 "Support/STLExtras.h"
41 RegisterAnalysis<LiveIntervals> X("liveintervals",
42 "Live Interval Analysis");
44 Statistic<> numIntervals("liveintervals", "Number of intervals");
45 Statistic<> numJoined ("liveintervals", "Number of intervals after "
47 Statistic<> numJoins ("liveintervals", "Number of interval joins "
49 Statistic<> numPeep ("liveintervals", "Number of identity moves "
50 "eliminated after coalescing");
51 Statistic<> numFolded ("liveintervals", "Number of register operands "
54 join("join-liveintervals",
55 cl::desc("Join compatible live intervals"),
59 void LiveIntervals::getAnalysisUsage(AnalysisUsage &AU) const
61 AU.addPreserved<LiveVariables>();
62 AU.addRequired<LiveVariables>();
63 AU.addPreservedID(PHIEliminationID);
64 AU.addRequiredID(PHIEliminationID);
65 AU.addRequiredID(TwoAddressInstructionPassID);
66 AU.addRequired<LoopInfo>();
67 MachineFunctionPass::getAnalysisUsage(AU);
70 void LiveIntervals::releaseMemory()
81 /// runOnMachineFunction - Register allocate the whole function
83 bool LiveIntervals::runOnMachineFunction(MachineFunction &fn) {
85 tm_ = &fn.getTarget();
86 mri_ = tm_->getRegisterInfo();
87 lv_ = &getAnalysis<LiveVariables>();
89 // number MachineInstrs
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,
97 assert(inserted && "multiple index -> MachineBasicBlock");
99 for (MachineBasicBlock::iterator mi = mbb->begin(), miEnd = mbb->end();
101 inserted = mi2iMap_.insert(std::make_pair(mi, miIndex)).second;
102 assert(inserted && "multiple MachineInstr -> index mappings");
103 i2miMap_.push_back(mi);
104 miIndex += InstrSlots::NUM;
110 numIntervals += intervals_.size();
112 // join intervals if requested
113 if (join) joinIntervals();
115 // perform a final pass over the instructions and compute spill
116 // weights, coalesce virtual registers and remove identity moves
117 const LoopInfo& loopInfo = getAnalysis<LoopInfo>();
118 const TargetInstrInfo& tii = tm_->getInstrInfo();
120 for (MachineFunction::iterator mbbi = mf_->begin(), mbbe = mf_->end();
121 mbbi != mbbe; ++mbbi) {
122 MachineBasicBlock* mbb = mbbi;
123 unsigned loopDepth = loopInfo.getLoopDepth(mbb->getBasicBlock());
125 for (MachineBasicBlock::iterator mii = mbb->begin(), mie = mbb->end();
127 for (unsigned i = 0; i < mii->getNumOperands(); ++i) {
128 const MachineOperand& mop = mii->getOperand(i);
129 if (mop.isRegister()) {
130 // replace register with representative register
131 unsigned reg = rep(mop.getReg());
132 mii->SetMachineOperandReg(i, reg);
134 if (MRegisterInfo::isVirtualRegister(reg)) {
135 Reg2IntervalMap::iterator r2iit = r2iMap_.find(reg);
136 assert(r2iit != r2iMap_.end());
137 r2iit->second->weight += pow(10.0F, loopDepth);
142 // if the move is now an identity move delete it
143 unsigned srcReg, dstReg;
144 if (tii.isMoveInstr(*mii, srcReg, dstReg) && srcReg == dstReg) {
145 // remove index -> MachineInstr and
146 // MachineInstr -> index mappings
147 Mi2IndexMap::iterator mi2i = mi2iMap_.find(mii);
148 if (mi2i != mi2iMap_.end()) {
149 i2miMap_[mi2i->second/InstrSlots::NUM] = 0;
150 mi2iMap_.erase(mi2i);
152 mii = mbbi->erase(mii);
160 intervals_.sort(StartPointComp());
161 DEBUG(std::cerr << "********** INTERVALS **********\n");
162 DEBUG(std::copy(intervals_.begin(), intervals_.end(),
163 std::ostream_iterator<Interval>(std::cerr, "\n")));
164 DEBUG(std::cerr << "********** MACHINEINSTRS **********\n");
166 for (unsigned i = 0; i != i2miMap_.size(); ++i) {
167 if (const MachineInstr* mi = i2miMap_[i]) {
168 std:: cerr << i * InstrSlots::NUM << '\t';
169 mi->print(std::cerr, *tm_);
176 void LiveIntervals::updateSpilledInterval(Interval& li, int slot)
178 assert(li.weight != std::numeric_limits<float>::infinity() &&
179 "attempt to spill already spilled interval!");
180 Interval::Ranges oldRanges;
181 swap(oldRanges, li.ranges);
183 DEBUG(std::cerr << "\t\t\t\tupdating interval: " << li);
185 for (Interval::Ranges::iterator i = oldRanges.begin(), e = oldRanges.end();
187 unsigned index = getBaseIndex(i->first);
188 unsigned end = getBaseIndex(i->second-1) + InstrSlots::NUM;
189 for (; index < end; index += InstrSlots::NUM) {
190 // skip deleted instructions
191 while (!getInstructionFromIndex(index)) index += InstrSlots::NUM;
192 MachineBasicBlock::iterator mi = getInstructionFromIndex(index);
194 for (unsigned i = 0; i < mi->getNumOperands(); ++i) {
195 MachineOperand& mop = mi->getOperand(i);
196 if (mop.isRegister() && mop.getReg() == li.reg) {
197 // This is tricky. We need to add information in
198 // the interval about the spill code so we have to
199 // use our extra load/store slots.
201 // If we have a use we are going to have a load so
202 // we start the interval from the load slot
203 // onwards. Otherwise we start from the def slot.
204 unsigned start = (mop.isUse() ?
205 getLoadIndex(index) :
207 // If we have a def we are going to have a store
208 // right after it so we end the interval after the
209 // use of the next instruction. Otherwise we end
210 // after the use of this instruction.
211 unsigned end = 1 + (mop.isDef() ?
212 getUseIndex(index+InstrSlots::NUM) :
214 li.addRange(start, end);
219 // the new spill weight is now infinity as it cannot be spilled again
220 li.weight = std::numeric_limits<float>::infinity();
221 DEBUG(std::cerr << '\n');
224 void LiveIntervals::printRegName(unsigned reg) const
226 if (MRegisterInfo::isPhysicalRegister(reg))
227 std::cerr << mri_->getName(reg);
229 std::cerr << "%reg" << reg;
232 void LiveIntervals::handleVirtualRegisterDef(MachineBasicBlock* mbb,
233 MachineBasicBlock::iterator mi,
236 DEBUG(std::cerr << "\t\tregister: "; printRegName(reg));
237 LiveVariables::VarInfo& vi = lv_->getVarInfo(reg);
239 Interval* interval = 0;
240 Reg2IntervalMap::iterator r2iit = r2iMap_.lower_bound(reg);
241 if (r2iit == r2iMap_.end() || r2iit->first != reg) {
243 intervals_.push_back(Interval(reg));
244 // update interval index for this register
245 r2iMap_.insert(r2iit, std::make_pair(reg, --intervals_.end()));
246 interval = &intervals_.back();
248 // iterate over all of the blocks that the variable is
249 // completely live in, adding them to the live
250 // interval. obviously we only need to do this once.
251 for (unsigned i = 0, e = vi.AliveBlocks.size(); i != e; ++i) {
252 if (vi.AliveBlocks[i]) {
253 MachineBasicBlock* mbb = lv_->getIndexMachineBasicBlock(i);
256 getInstructionIndex(&mbb->front()),
257 getInstructionIndex(&mbb->back()) + InstrSlots::NUM);
263 interval = &*r2iit->second;
266 unsigned baseIndex = getInstructionIndex(mi);
268 bool killedInDefiningBasicBlock = false;
269 for (int i = 0, e = vi.Kills.size(); i != e; ++i) {
270 MachineBasicBlock* killerBlock = vi.Kills[i].first;
271 MachineInstr* killerInstr = vi.Kills[i].second;
272 unsigned start = (mbb == killerBlock ?
273 getDefIndex(baseIndex) :
274 getInstructionIndex(&killerBlock->front()));
275 unsigned end = (killerInstr == mi ?
279 getUseIndex(getInstructionIndex(killerInstr))+1);
280 // we do not want to add invalid ranges. these can happen when
281 // a variable has its latest use and is redefined later on in
282 // the same basic block (common with variables introduced by
285 killedInDefiningBasicBlock |= mbb == killerBlock;
286 interval->addRange(start, end);
290 if (!killedInDefiningBasicBlock) {
291 unsigned end = getInstructionIndex(&mbb->back()) + InstrSlots::NUM;
292 interval->addRange(getDefIndex(baseIndex), end);
294 DEBUG(std::cerr << '\n');
297 void LiveIntervals::handlePhysicalRegisterDef(MachineBasicBlock* mbb,
298 MachineBasicBlock::iterator mi,
301 DEBUG(std::cerr << "\t\tregister: "; printRegName(reg));
302 typedef LiveVariables::killed_iterator KillIter;
304 MachineBasicBlock::iterator e = mbb->end();
305 unsigned baseIndex = getInstructionIndex(mi);
306 unsigned start = getDefIndex(baseIndex);
307 unsigned end = start;
309 // a variable can be dead by the instruction defining it
310 for (KillIter ki = lv_->dead_begin(mi), ke = lv_->dead_end(mi);
312 if (reg == ki->second) {
313 DEBUG(std::cerr << " dead");
314 end = getDefIndex(start) + 1;
319 // a variable can only be killed by subsequent instructions
322 baseIndex += InstrSlots::NUM;
323 for (KillIter ki = lv_->killed_begin(mi), ke = lv_->killed_end(mi);
325 if (reg == ki->second) {
326 DEBUG(std::cerr << " killed");
327 end = getUseIndex(baseIndex) + 1;
334 assert(start < end && "did not find end of interval?");
336 Reg2IntervalMap::iterator r2iit = r2iMap_.lower_bound(reg);
337 if (r2iit != r2iMap_.end() && r2iit->first == reg) {
338 r2iit->second->addRange(start, end);
341 intervals_.push_back(Interval(reg));
342 // update interval index for this register
343 r2iMap_.insert(r2iit, std::make_pair(reg, --intervals_.end()));
344 intervals_.back().addRange(start, end);
346 DEBUG(std::cerr << '\n');
349 void LiveIntervals::handleRegisterDef(MachineBasicBlock* mbb,
350 MachineBasicBlock::iterator mi,
353 if (MRegisterInfo::isPhysicalRegister(reg)) {
354 if (lv_->getAllocatablePhysicalRegisters()[reg]) {
355 handlePhysicalRegisterDef(mbb, mi, reg);
356 for (const unsigned* as = mri_->getAliasSet(reg); *as; ++as)
357 handlePhysicalRegisterDef(mbb, mi, *as);
361 handleVirtualRegisterDef(mbb, mi, reg);
365 unsigned LiveIntervals::getInstructionIndex(MachineInstr* instr) const
367 Mi2IndexMap::const_iterator it = mi2iMap_.find(instr);
368 return (it == mi2iMap_.end() ?
369 std::numeric_limits<unsigned>::max() :
373 MachineInstr* LiveIntervals::getInstructionFromIndex(unsigned index) const
375 index /= InstrSlots::NUM; // convert index to vector index
376 assert(index < i2miMap_.size() &&
377 "index does not correspond to an instruction");
378 return i2miMap_[index];
381 /// computeIntervals - computes the live intervals for virtual
382 /// registers. for some ordering of the machine instructions [1,N] a
383 /// live interval is an interval [i, j) where 1 <= i <= j < N for
384 /// which a variable is live
385 void LiveIntervals::computeIntervals()
387 DEBUG(std::cerr << "********** COMPUTING LIVE INTERVALS **********\n");
388 DEBUG(std::cerr << "********** Function: "
389 << mf_->getFunction()->getName() << '\n');
391 for (MbbIndex2MbbMap::iterator
392 it = mbbi2mbbMap_.begin(), itEnd = mbbi2mbbMap_.end();
394 MachineBasicBlock* mbb = it->second;
395 DEBUG(std::cerr << mbb->getBasicBlock()->getName() << ":\n");
397 for (MachineBasicBlock::iterator mi = mbb->begin(), miEnd = mbb->end();
399 const TargetInstrDescriptor& tid =
400 tm_->getInstrInfo().get(mi->getOpcode());
401 DEBUG(std::cerr << getInstructionIndex(mi) << "\t";
402 mi->print(std::cerr, *tm_));
404 // handle implicit defs
405 for (const unsigned* id = tid.ImplicitDefs; *id; ++id)
406 handleRegisterDef(mbb, mi, *id);
408 // handle explicit defs
409 for (int i = mi->getNumOperands() - 1; i >= 0; --i) {
410 MachineOperand& mop = mi->getOperand(i);
411 // handle register defs - build intervals
412 if (mop.isRegister() && mop.isDef())
413 handleRegisterDef(mbb, mi, mop.getReg());
419 unsigned LiveIntervals::rep(unsigned reg)
421 Reg2RegMap::iterator it = r2rMap_.find(reg);
422 if (it != r2rMap_.end())
423 return it->second = rep(it->second);
427 void LiveIntervals::joinIntervals()
429 DEBUG(std::cerr << "********** JOINING INTERVALS ***********\n");
431 const TargetInstrInfo& tii = tm_->getInstrInfo();
433 for (MachineFunction::iterator mbbi = mf_->begin(), mbbe = mf_->end();
434 mbbi != mbbe; ++mbbi) {
435 MachineBasicBlock* mbb = mbbi;
436 DEBUG(std::cerr << mbb->getBasicBlock()->getName() << ":\n");
438 for (MachineBasicBlock::iterator mi = mbb->begin(), mie = mbb->end();
440 const TargetInstrDescriptor& tid =
441 tm_->getInstrInfo().get(mi->getOpcode());
442 DEBUG(std::cerr << getInstructionIndex(mi) << '\t';
443 mi->print(std::cerr, *tm_););
445 // we only join virtual registers with allocatable
446 // physical registers since we do not have liveness information
447 // on not allocatable physical registers
449 if (tii.isMoveInstr(*mi, regA, regB) &&
450 (MRegisterInfo::isVirtualRegister(regA) ||
451 lv_->getAllocatablePhysicalRegisters()[regA]) &&
452 (MRegisterInfo::isVirtualRegister(regB) ||
453 lv_->getAllocatablePhysicalRegisters()[regB])) {
455 // get representative registers
459 // if they are already joined we continue
463 Reg2IntervalMap::iterator r2iA = r2iMap_.find(regA);
464 assert(r2iA != r2iMap_.end());
465 Reg2IntervalMap::iterator r2iB = r2iMap_.find(regB);
466 assert(r2iB != r2iMap_.end());
468 Intervals::iterator intA = r2iA->second;
469 Intervals::iterator intB = r2iB->second;
471 // both A and B are virtual registers
472 if (MRegisterInfo::isVirtualRegister(intA->reg) &&
473 MRegisterInfo::isVirtualRegister(intB->reg)) {
475 const TargetRegisterClass *rcA, *rcB;
476 rcA = mf_->getSSARegMap()->getRegClass(intA->reg);
477 rcB = mf_->getSSARegMap()->getRegClass(intB->reg);
478 assert(rcA == rcB && "registers must be of the same class");
480 // if their intervals do not overlap we join them
481 if (!intB->overlaps(*intA)) {
483 r2iB->second = r2iA->second;
484 r2rMap_.insert(std::make_pair(intB->reg, intA->reg));
485 intervals_.erase(intB);
489 else if (MRegisterInfo::isPhysicalRegister(intA->reg) ^
490 MRegisterInfo::isPhysicalRegister(intB->reg)) {
491 if (MRegisterInfo::isPhysicalRegister(intB->reg)) {
492 std::swap(regA, regB);
493 std::swap(intA, intB);
494 std::swap(r2iA, r2iB);
497 assert(MRegisterInfo::isPhysicalRegister(intA->reg) &&
498 MRegisterInfo::isVirtualRegister(intB->reg) &&
499 "A must be physical and B must be virtual");
501 if (!intA->overlaps(*intB) &&
502 !overlapsAliases(*intA, *intB)) {
504 r2iB->second = r2iA->second;
505 r2rMap_.insert(std::make_pair(intB->reg, intA->reg));
506 intervals_.erase(intB);
515 bool LiveIntervals::overlapsAliases(const Interval& lhs,
516 const Interval& rhs) const
518 assert(MRegisterInfo::isPhysicalRegister(lhs.reg) &&
519 "first interval must describe a physical register");
521 for (const unsigned* as = mri_->getAliasSet(lhs.reg); *as; ++as) {
522 Reg2IntervalMap::const_iterator r2i = r2iMap_.find(*as);
523 assert(r2i != r2iMap_.end() && "alias does not have interval?");
524 if (rhs.overlaps(*r2i->second))
531 LiveIntervals::Interval::Interval(unsigned r)
533 weight((MRegisterInfo::isPhysicalRegister(r) ?
534 std::numeric_limits<float>::infinity() : 0.0F))
539 bool LiveIntervals::Interval::spilled() const
541 return (weight == std::numeric_limits<float>::infinity() &&
542 MRegisterInfo::isVirtualRegister(reg));
545 // An example for liveAt():
547 // this = [1,4), liveAt(0) will return false. The instruction defining
548 // this spans slots [0,3]. The interval belongs to an spilled
549 // definition of the variable it represents. This is because slot 1 is
550 // used (def slot) and spans up to slot 3 (store slot).
552 bool LiveIntervals::Interval::liveAt(unsigned index) const
554 Range dummy(index, index+1);
555 Ranges::const_iterator r = std::upper_bound(ranges.begin(),
558 if (r == ranges.begin())
562 return index >= r->first && index < r->second;
565 // An example for overlaps():
569 // 8: C = A + B ;; last use of A
571 // The live intervals should look like:
577 // A->overlaps(C) should return false since we want to be able to join
579 bool LiveIntervals::Interval::overlaps(const Interval& other) const
581 Ranges::const_iterator i = ranges.begin();
582 Ranges::const_iterator ie = ranges.end();
583 Ranges::const_iterator j = other.ranges.begin();
584 Ranges::const_iterator je = other.ranges.end();
585 if (i->first < j->first) {
586 i = std::upper_bound(i, ie, *j);
587 if (i != ranges.begin()) --i;
589 else if (j->first < i->first) {
590 j = std::upper_bound(j, je, *i);
591 if (j != other.ranges.begin()) --j;
594 while (i != ie && j != je) {
595 if (i->first == j->first) {
599 if (i->first > j->first) {
603 assert(i->first < j->first);
605 if (i->second > j->first) {
617 void LiveIntervals::Interval::addRange(unsigned start, unsigned end)
619 assert(start < end && "Invalid range to add!");
620 DEBUG(std::cerr << " +[" << start << ',' << end << ")");
621 //assert(start < end && "invalid range?");
622 Range range = std::make_pair(start, end);
623 Ranges::iterator it =
624 ranges.insert(std::upper_bound(ranges.begin(), ranges.end(), range),
627 it = mergeRangesForward(it);
628 it = mergeRangesBackward(it);
631 void LiveIntervals::Interval::join(const LiveIntervals::Interval& other)
633 DEBUG(std::cerr << "\t\tjoining " << *this << " with " << other << '\n');
634 Ranges::iterator cur = ranges.begin();
636 for (Ranges::const_iterator i = other.ranges.begin(),
637 e = other.ranges.end(); i != e; ++i) {
638 cur = ranges.insert(std::upper_bound(cur, ranges.end(), *i), *i);
639 cur = mergeRangesForward(cur);
640 cur = mergeRangesBackward(cur);
642 weight += other.weight;
646 LiveIntervals::Interval::Ranges::iterator
647 LiveIntervals::Interval::mergeRangesForward(Ranges::iterator it)
649 for (Ranges::iterator n = next(it);
650 n != ranges.end() && ((it->second & 1) + it->second) >= n->first; ) {
651 it->second = std::max(it->second, n->second);
657 LiveIntervals::Interval::Ranges::iterator
658 LiveIntervals::Interval::mergeRangesBackward(Ranges::iterator it)
660 while (it != ranges.begin()) {
661 Ranges::iterator p = prior(it);
662 if (it->first > ((p->second & 1) + p->second)) break;
664 it->first = std::min(it->first, p->first);
665 it->second = std::max(it->second, p->second);
666 it = ranges.erase(p);
672 std::ostream& llvm::operator<<(std::ostream& os,
673 const LiveIntervals::Interval& li)
675 os << "%reg" << li.reg << ',' << li.weight << " = ";
677 return os << "EMPTY";
678 for (LiveIntervals::Interval::Ranges::const_iterator
679 i = li.ranges.begin(), e = li.ranges.end(); i != e; ++i) {
680 os << "[" << i->first << "," << i->second << ")";