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