LiveIntervalAnalysis.cpp revision 97017de1872e08ffcdde2fccdfd399647c1ccc4a 
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/CommandLine.h"
34#include "Support/Debug.h"
35#include "Support/DepthFirstIterator.h"
36#include "Support/Statistic.h"
37#include <cmath>
38#include <iostream>
39#include <limits>
40
41using namespace llvm;
42
43namespace {
44    RegisterAnalysis<LiveIntervals> X("liveintervals",
45                                      "Live Interval Analysis");
46
47    Statistic<> numIntervals("liveintervals", "Number of intervals");
48
49    cl::opt<bool>
50    join("join-liveintervals",
51         cl::desc("Join compatible live intervals"),
52         cl::init(true));
53};
54
55void LiveIntervals::getAnalysisUsage(AnalysisUsage &AU) const
56{
57    AU.addPreserved<LiveVariables>();
58    AU.addRequired<LiveVariables>();
59    AU.addPreservedID(PHIEliminationID);
60    AU.addRequiredID(PHIEliminationID);
61    AU.addRequiredID(TwoAddressInstructionPassID);
62    AU.addRequired<LoopInfo>();
63    MachineFunctionPass::getAnalysisUsage(AU);
64}
65
66/// runOnMachineFunction - Register allocate the whole function
67///
68bool LiveIntervals::runOnMachineFunction(MachineFunction &fn) {
69    DEBUG(std::cerr << "Machine Function\n");
70    mf_ = &fn;
71    tm_ = &fn.getTarget();
72    mri_ = tm_->getRegisterInfo();
73    lv_ = &getAnalysis<LiveVariables>();
74    mbbi2mbbMap_.clear();
75    mi2iMap_.clear();
76    r2iMap_.clear();
77    r2iMap_.clear();
78    r2rMap_.clear();
79    intervals_.clear();
80
81    // number MachineInstrs
82    unsigned miIndex = 0;
83    for (MachineFunction::iterator mbb = mf_->begin(), mbbEnd = mf_->end();
84         mbb != mbbEnd; ++mbb) {
85        const std::pair<MachineBasicBlock*, unsigned>& entry =
86            lv_->getMachineBasicBlockInfo(&*mbb);
87        bool inserted = mbbi2mbbMap_.insert(std::make_pair(entry.second,
88                                                           entry.first)).second;
89        assert(inserted && "multiple index -> MachineBasicBlock");
90
91        for (MachineBasicBlock::iterator mi = mbb->begin(), miEnd = mbb->end();
92             mi != miEnd; ++mi) {
93            inserted = mi2iMap_.insert(std::make_pair(*mi, miIndex)).second;
94            assert(inserted && "multiple MachineInstr -> index mappings");
95            ++miIndex;
96        }
97    }
98
99    computeIntervals();
100
101    // compute spill weights
102    const LoopInfo& loopInfo = getAnalysis<LoopInfo>();
103    const TargetInstrInfo& tii = tm_->getInstrInfo();
104
105    for (MachineFunction::const_iterator mbbi = mf_->begin(),
106             mbbe = mf_->end(); mbbi != mbbe; ++mbbi) {
107        const MachineBasicBlock* mbb = mbbi;
108        unsigned loopDepth = loopInfo.getLoopDepth(mbb->getBasicBlock());
109
110        for (MachineBasicBlock::const_iterator mii = mbb->begin(),
111                 mie = mbb->end(); mii != mie; ++mii) {
112            MachineInstr* mi = *mii;
113
114            for (int i = mi->getNumOperands() - 1; i >= 0; --i) {
115                MachineOperand& mop = mi->getOperand(i);
116
117                if (!mop.isVirtualRegister())
118                    continue;
119
120                unsigned reg = mop.getAllocatedRegNum();
121                Reg2IntervalMap::iterator r2iit = r2iMap_.find(reg);
122                assert(r2iit != r2iMap_.end());
123                r2iit->second->weight += pow(10.0F, loopDepth);
124            }
125        }
126    }
127
128    // join intervals if requested
129    if (join) joinIntervals();
130
131    numIntervals += intervals_.size();
132
133    return true;
134}
135
136void LiveIntervals::printRegName(unsigned reg) const
137{
138    if (reg < MRegisterInfo::FirstVirtualRegister)
139        std::cerr << mri_->getName(reg);
140    else
141        std::cerr << '%' << reg;
142}
143
144void LiveIntervals::handleVirtualRegisterDef(MachineBasicBlock* mbb,
145                                             MachineBasicBlock::iterator mi,
146                                             unsigned reg)
147{
148    DEBUG(std::cerr << "\t\tregister: ";printRegName(reg); std::cerr << '\n');
149
150    unsigned instrIndex = getInstructionIndex(*mi);
151
152    LiveVariables::VarInfo& vi = lv_->getVarInfo(reg);
153
154    Interval* interval = 0;
155    Reg2IntervalMap::iterator r2iit = r2iMap_.find(reg);
156    if (r2iit == r2iMap_.end()) {
157        // add new interval
158        intervals_.push_back(Interval(reg));
159        // update interval index for this register
160        bool inserted =
161            r2iMap_.insert(std::make_pair(reg, --intervals_.end())).second;
162        assert(inserted);
163        interval = &intervals_.back();
164    }
165    else {
166        interval = &*r2iit->second;
167    }
168
169    for (MbbIndex2MbbMap::iterator
170             it = mbbi2mbbMap_.begin(), itEnd = mbbi2mbbMap_.end();
171         it != itEnd; ++it) {
172        unsigned liveBlockIndex = it->first;
173        MachineBasicBlock* liveBlock = it->second;
174        if (liveBlockIndex < vi.AliveBlocks.size() &&
175            vi.AliveBlocks[liveBlockIndex] &&
176            !liveBlock->empty()) {
177            unsigned start =  getInstructionIndex(liveBlock->front());
178            unsigned end = getInstructionIndex(liveBlock->back()) + 1;
179            interval->addRange(start, end);
180        }
181    }
182
183    bool killedInDefiningBasicBlock = false;
184    for (int i = 0, e = vi.Kills.size(); i != e; ++i) {
185        MachineBasicBlock* killerBlock = vi.Kills[i].first;
186        MachineInstr* killerInstr = vi.Kills[i].second;
187        unsigned start = (mbb == killerBlock ?
188                          instrIndex :
189                          getInstructionIndex(killerBlock->front()));
190        unsigned end = getInstructionIndex(killerInstr) + 1;
191        if (start < end) {
192            killedInDefiningBasicBlock |= mbb == killerBlock;
193            interval->addRange(start, end);
194        }
195    }
196
197    if (!killedInDefiningBasicBlock) {
198        unsigned end = getInstructionIndex(mbb->back()) + 1;
199        interval->addRange(instrIndex, end);
200    }
201}
202
203void LiveIntervals::handlePhysicalRegisterDef(MachineBasicBlock* mbb,
204                                              MachineBasicBlock::iterator mi,
205                                              unsigned reg)
206{
207    DEBUG(std::cerr << "\t\tregister: "; printRegName(reg));
208
209    unsigned start = getInstructionIndex(*mi);
210    unsigned end = start;
211
212    // register can be dead by the instruction defining it but it can
213    // only be killed by subsequent instructions
214
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    ++mi;
226
227    for (MachineBasicBlock::iterator e = mbb->end(); mi != e; ++mi) {
228        for (LiveVariables::killed_iterator
229                 ki = lv_->dead_begin(*mi),
230                 ke = lv_->dead_end(*mi);
231             ki != ke; ++ki) {
232            if (reg == ki->second) {
233                end = getInstructionIndex(ki->first) + 1;
234                DEBUG(std::cerr << " dead\n");
235                goto exit;
236            }
237        }
238
239        for (LiveVariables::killed_iterator
240                 ki = lv_->killed_begin(*mi),
241                 ke = lv_->killed_end(*mi);
242             ki != ke; ++ki) {
243            if (reg == ki->second) {
244                end = getInstructionIndex(ki->first) + 1;
245                DEBUG(std::cerr << " killed\n");
246                goto exit;
247            }
248        }
249    }
250exit:
251    assert(start < end && "did not find end of interval?");
252
253    Reg2IntervalMap::iterator r2iit = r2iMap_.find(reg);
254    if (r2iit != r2iMap_.end()) {
255        Interval& interval = *r2iit->second;
256        interval.addRange(start, end);
257    }
258    else {
259        intervals_.push_back(Interval(reg));
260        Interval& interval = intervals_.back();
261        // update interval index for this register
262        bool inserted =
263            r2iMap_.insert(std::make_pair(reg, --intervals_.end())).second;
264        assert(inserted);
265        interval.addRange(start, end);
266    }
267}
268
269void LiveIntervals::handleRegisterDef(MachineBasicBlock* mbb,
270                                      MachineBasicBlock::iterator mi,
271                                      unsigned reg)
272{
273    if (reg < MRegisterInfo::FirstVirtualRegister) {
274        if (lv_->getAllocatablePhysicalRegisters()[reg]) {
275            handlePhysicalRegisterDef(mbb, mi, reg);
276            for (const unsigned* as = mri_->getAliasSet(reg); *as; ++as)
277                handlePhysicalRegisterDef(mbb, mi, *as);
278        }
279    }
280    else {
281        handleVirtualRegisterDef(mbb, mi, reg);
282    }
283}
284
285unsigned LiveIntervals::getInstructionIndex(MachineInstr* instr) const
286{
287    assert(mi2iMap_.find(instr) != mi2iMap_.end() &&
288           "instruction not assigned a number");
289    return mi2iMap_.find(instr)->second;
290}
291
292/// computeIntervals - computes the live intervals for virtual
293/// registers. for some ordering of the machine instructions [1,N] a
294/// live interval is an interval [i, j] where 1 <= i <= j <= N for
295/// which a variable is live
296void LiveIntervals::computeIntervals()
297{
298    DEBUG(std::cerr << "computing live intervals:\n");
299
300    for (MbbIndex2MbbMap::iterator
301             it = mbbi2mbbMap_.begin(), itEnd = mbbi2mbbMap_.end();
302         it != itEnd; ++it) {
303        MachineBasicBlock* mbb = it->second;
304        DEBUG(std::cerr << "machine basic block: "
305              << mbb->getBasicBlock()->getName() << "\n");
306
307        for (MachineBasicBlock::iterator mi = mbb->begin(), miEnd = mbb->end();
308             mi != miEnd; ++mi) {
309            MachineInstr* instr = *mi;
310            const TargetInstrDescriptor& tid =
311                tm_->getInstrInfo().get(instr->getOpcode());
312            DEBUG(std::cerr << "\t[" << getInstructionIndex(instr) << "] ";
313                  instr->print(std::cerr, *tm_););
314
315            // handle implicit defs
316            for (const unsigned* id = tid.ImplicitDefs; *id; ++id)
317                handleRegisterDef(mbb, mi, *id);
318
319            // handle explicit defs
320            for (int i = instr->getNumOperands() - 1; i >= 0; --i) {
321                MachineOperand& mop = instr->getOperand(i);
322
323                if (!mop.isRegister())
324                    continue;
325
326                // handle defs - build intervals
327                if (mop.isDef())
328                    handleRegisterDef(mbb, mi, mop.getAllocatedRegNum());
329            }
330        }
331    }
332
333    intervals_.sort(StartPointComp());
334    DEBUG(std::copy(intervals_.begin(), intervals_.end(),
335                    std::ostream_iterator<Interval>(std::cerr, "\n")));
336}
337
338unsigned LiveIntervals::rep(unsigned reg)
339{
340    Reg2RegMap::iterator it = r2rMap_.find(reg);
341    if (it != r2rMap_.end())
342        return it->second = rep(it->second);
343    return reg;
344}
345
346void LiveIntervals::joinIntervals()
347{
348    DEBUG(std::cerr << "joining compatible intervals:\n");
349
350    const TargetInstrInfo& tii = tm_->getInstrInfo();
351
352    for (MachineFunction::const_iterator mbbi = mf_->begin(),
353             mbbe = mf_->end(); mbbi != mbbe; ++mbbi) {
354        const MachineBasicBlock* mbb = mbbi;
355        DEBUG(std::cerr << "machine basic block: "
356              << mbb->getBasicBlock()->getName() << "\n");
357
358        for (MachineBasicBlock::const_iterator mii = mbb->begin(),
359                 mie = mbb->end(); mii != mie; ++mii) {
360            MachineInstr* mi = *mii;
361            const TargetInstrDescriptor& tid =
362                tm_->getInstrInfo().get(mi->getOpcode());
363            DEBUG(std::cerr << "\t\tinstruction["
364                  << getInstructionIndex(mi) << "]: ";
365                  mi->print(std::cerr, *tm_););
366
367            unsigned srcReg, dstReg;
368            if (tii.isMoveInstr(*mi, srcReg, dstReg) &&
369                (srcReg >= MRegisterInfo::FirstVirtualRegister ||
370                 lv_->getAllocatablePhysicalRegisters()[srcReg]) &&
371                (dstReg >= MRegisterInfo::FirstVirtualRegister ||
372                 lv_->getAllocatablePhysicalRegisters()[dstReg])) {
373
374                // get representative registers
375                srcReg = rep(srcReg);
376                dstReg = rep(dstReg);
377
378                // if they are already joined we continue
379                if (srcReg == dstReg)
380                    continue;
381
382                Reg2IntervalMap::iterator r2iSrc = r2iMap_.find(srcReg);
383                assert(r2iSrc != r2iMap_.end());
384                Reg2IntervalMap::iterator r2iDst = r2iMap_.find(dstReg);
385                assert(r2iDst != r2iMap_.end());
386
387                Intervals::iterator srcInt = r2iSrc->second;
388                Intervals::iterator dstInt = r2iDst->second;
389
390                // src is a physical register
391                if (srcInt->reg < MRegisterInfo::FirstVirtualRegister) {
392                    if (dstInt->reg == srcInt->reg ||
393                        (dstInt->reg >= MRegisterInfo::FirstVirtualRegister &&
394                         !srcInt->overlaps(*dstInt) &&
395                         !overlapsAliases(*srcInt, *dstInt))) {
396                        srcInt->join(*dstInt);
397                        r2iDst->second = r2iSrc->second;
398                        r2rMap_.insert(std::make_pair(dstInt->reg, srcInt->reg));
399                        intervals_.erase(dstInt);
400                    }
401                }
402                // dst is a physical register
403                else if (dstInt->reg < MRegisterInfo::FirstVirtualRegister) {
404                    if (srcInt->reg == dstInt->reg ||
405                        (srcInt->reg >= MRegisterInfo::FirstVirtualRegister &&
406                         !dstInt->overlaps(*srcInt) &&
407                         !overlapsAliases(*dstInt, *srcInt))) {
408                        dstInt->join(*srcInt);
409                        r2iSrc->second = r2iDst->second;
410                        r2rMap_.insert(std::make_pair(srcInt->reg, dstInt->reg));
411                        intervals_.erase(srcInt);
412                    }
413                }
414                // neither src nor dst are physical registers
415                else {
416                    const TargetRegisterClass *srcRc, *dstRc;
417                    srcRc = mf_->getSSARegMap()->getRegClass(srcInt->reg);
418                    dstRc = mf_->getSSARegMap()->getRegClass(dstInt->reg);
419
420                    if (srcRc == dstRc && !dstInt->overlaps(*srcInt)) {
421                        srcInt->join(*dstInt);
422                        r2iDst->second = r2iSrc->second;
423                        r2rMap_.insert(std::make_pair(dstInt->reg, srcInt->reg));
424                        intervals_.erase(dstInt);
425                    }
426                }
427            }
428        }
429    }
430
431    intervals_.sort(StartPointComp());
432    DEBUG(std::copy(intervals_.begin(), intervals_.end(),
433                    std::ostream_iterator<Interval>(std::cerr, "\n")));
434    DEBUG(for (Reg2RegMap::const_iterator i = r2rMap_.begin(),
435                   e = r2rMap_.end(); i != e; ++i)
436          std::cerr << i->first << " -> " << i->second << '\n';);
437
438}
439
440bool LiveIntervals::overlapsAliases(const Interval& lhs,
441                                    const Interval& rhs) const
442{
443    assert(lhs.reg < MRegisterInfo::FirstVirtualRegister &&
444           "first interval must describe a physical register");
445
446    for (const unsigned* as = mri_->getAliasSet(lhs.reg); *as; ++as) {
447        Reg2IntervalMap::const_iterator r2i = r2iMap_.find(*as);
448        assert(r2i != r2iMap_.end() && "alias does not have interval?");
449        if (rhs.overlaps(*r2i->second))
450            return true;
451    }
452
453    return false;
454}
455
456LiveIntervals::Interval::Interval(unsigned r)
457    : reg(r),
458      weight((r < MRegisterInfo::FirstVirtualRegister ?
459              std::numeric_limits<float>::max() : 0.0F))
460{
461
462}
463
464bool LiveIntervals::Interval::liveAt(unsigned index) const
465{
466    Range dummy(index, index+1);
467    Ranges::const_iterator r = std::upper_bound(ranges.begin(),
468                                                ranges.end(),
469                                                dummy);
470    if (r == ranges.begin())
471        return false;
472
473    --r;
474    return index >= r->first && index < (r->second - 1);
475}
476
477bool LiveIntervals::Interval::overlaps(const Interval& other) const
478{
479    Ranges::const_iterator i = ranges.begin();
480    Ranges::const_iterator ie = ranges.end();
481    Ranges::const_iterator j = other.ranges.begin();
482    Ranges::const_iterator je = other.ranges.end();
483    if (i->first < j->first) {
484        i = std::upper_bound(i, ie, *j);
485        if (i != ranges.begin()) --i;
486    }
487    else if (j->first < i->first) {
488        j = std::upper_bound(j, je, *i);
489        if (j != other.ranges.begin()) --j;
490    }
491
492    while (i != ie && j != je) {
493        if (i->first == j->first) {
494            return true;
495        }
496        else {
497            if (i->first > j->first) {
498                swap(i, j);
499                swap(ie, je);
500            }
501            assert(i->first < j->first);
502
503            if ((i->second - 1) > j->first) {
504                return true;
505            }
506            else {
507                ++i;
508            }
509        }
510    }
511
512    return false;
513}
514
515void LiveIntervals::Interval::addRange(unsigned start, unsigned end)
516{
517    DEBUG(std::cerr << "\t\t\tadding range: [" << start <<','<< end << ") -> ");
518    //assert(start < end && "invalid range?");
519    Range range = std::make_pair(start, end);
520    Ranges::iterator it =
521        ranges.insert(std::upper_bound(ranges.begin(), ranges.end(), range),
522                      range);
523
524    it = mergeRangesForward(it);
525    it = mergeRangesBackward(it);
526    DEBUG(std::cerr << "\t\t\t\tafter merging: " << *this << '\n');
527}
528
529void LiveIntervals::Interval::join(const LiveIntervals::Interval& other)
530{
531    DEBUG(std::cerr << "\t\t\t\tjoining intervals: "
532          << other << " and " << *this << '\n');
533    Ranges::iterator cur = ranges.begin();
534
535    for (Ranges::const_iterator i = other.ranges.begin(),
536             e = other.ranges.end(); i != e; ++i) {
537        cur = ranges.insert(std::upper_bound(cur, ranges.end(), *i), *i);
538        cur = mergeRangesForward(cur);
539        cur = mergeRangesBackward(cur);
540    }
541    if (reg >= MRegisterInfo::FirstVirtualRegister)
542        weight += other.weight;
543
544    DEBUG(std::cerr << "\t\t\t\tafter merging: " << *this << '\n');
545}
546
547LiveIntervals::Interval::Ranges::iterator
548LiveIntervals::Interval::mergeRangesForward(Ranges::iterator it)
549{
550    for (Ranges::iterator next = it + 1;
551         next != ranges.end() && it->second >= next->first; ) {
552        it->second = std::max(it->second, next->second);
553        next = ranges.erase(next);
554    }
555    return it;
556}
557
558LiveIntervals::Interval::Ranges::iterator
559LiveIntervals::Interval::mergeRangesBackward(Ranges::iterator it)
560{
561    for (Ranges::iterator prev = it - 1;
562         it != ranges.begin() && it->first <= prev->second; ) {
563        it->first = std::min(it->first, prev->first);
564        it->second = std::max(it->second, prev->second);
565        it = ranges.erase(prev);
566        prev = it - 1;
567    }
568
569    return it;
570}
571
572std::ostream& llvm::operator<<(std::ostream& os,
573                               const LiveIntervals::Interval& li)
574{
575    os << "%reg" << li.reg << ',' << li.weight << " = ";
576    for (LiveIntervals::Interval::Ranges::const_iterator
577             i = li.ranges.begin(), e = li.ranges.end(); i != e; ++i) {
578        os << "[" << i->first << "," << i->second << ")";
579    }
580    return os;
581}
582