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