LiveIntervalAnalysis.h revision 26f5a69e52b64e035d26c135979a39b39fd6ba3e 
1//===-- llvm/CodeGen/LiveInterval.h - Live Interval Analysis ----*- C++ -*-===//
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.  Given some
11// numbering of each the machine instructions (in this implemention
12// depth-first order) an interval [i, j) is said to be a live interval
13// for register v if there is no instruction with number j' > j such
14// that v is live at j' abd there is no instruction with number i' < i
15// such that v is live at i'. In this implementation intervals can
16// have holes, i.e. an interval might look like [1,20), [50,65),
17// [1000,1001)
18//
19//===----------------------------------------------------------------------===//
20
21#ifndef LLVM_CODEGEN_LIVEINTERVALS_H
22#define LLVM_CODEGEN_LIVEINTERVALS_H
23
24#include "llvm/CodeGen/MachineFunctionPass.h"
25#include <list>
26
27namespace llvm {
28
29    class LiveVariables;
30    class MRegisterInfo;
31    class VirtRegMap;
32
33    class LiveIntervals : public MachineFunctionPass
34    {
35    public:
36        struct Interval {
37            typedef std::pair<unsigned, unsigned> Range;
38            typedef std::vector<Range> Ranges;
39            unsigned reg;   // the register of this interval
40            float weight;   // weight of this interval (number of uses
41                            // * 10^loopDepth)
42            Ranges ranges;  // the ranges in which this register is live
43            Interval(unsigned r);
44
45            bool empty() const { return ranges.empty(); }
46
47            bool spilled() const;
48
49            unsigned start() const {
50                assert(!empty() && "empty interval for register");
51                return ranges.front().first;
52            }
53
54            unsigned end() const {
55                assert(!empty() && "empty interval for register");
56                return ranges.back().second;
57            }
58
59            bool expiredAt(unsigned index) const {
60                return end() <= (index + 1);
61            }
62
63            bool liveAt(unsigned index) const;
64
65            bool overlaps(const Interval& other) const;
66
67            void addRange(unsigned start, unsigned end);
68
69            void join(const Interval& other);
70
71        private:
72            Ranges::iterator mergeRangesForward(Ranges::iterator it);
73
74            Ranges::iterator mergeRangesBackward(Ranges::iterator it);
75        };
76
77        struct StartPointComp {
78            bool operator()(const Interval& lhs, const Interval& rhs) {
79                return lhs.ranges.front().first < rhs.ranges.front().first;
80            }
81        };
82
83        struct StartPointPtrComp {
84            bool operator()(const Interval* lhs, const Interval* rhs) {
85                return lhs->ranges.front().first < rhs->ranges.front().first;
86            }
87        };
88
89        typedef std::list<Interval> Intervals;
90
91    private:
92        MachineFunction* mf_;
93        const TargetMachine* tm_;
94        const MRegisterInfo* mri_;
95        MachineBasicBlock* currentMbb_;
96        MachineBasicBlock::iterator currentInstr_;
97        LiveVariables* lv_;
98
99        typedef std::map<unsigned, MachineBasicBlock*> MbbIndex2MbbMap;
100        MbbIndex2MbbMap mbbi2mbbMap_;
101
102        typedef std::map<MachineInstr*, unsigned> Mi2IndexMap;
103        Mi2IndexMap mi2iMap_;
104
105        typedef std::vector<MachineInstr*> Index2MiMap;
106        Index2MiMap i2miMap_;
107
108        typedef std::map<unsigned, Intervals::iterator> Reg2IntervalMap;
109        Reg2IntervalMap r2iMap_;
110
111        typedef std::map<unsigned, unsigned> Reg2RegMap;
112        Reg2RegMap r2rMap_;
113
114        Intervals intervals_;
115
116    public:
117        struct InstrSlots
118        {
119            enum {
120                LOAD  = 0,
121                USE   = 1,
122                DEF   = 2,
123                STORE = 3,
124                NUM   = 4,
125            };
126        };
127
128        static unsigned getBaseIndex(unsigned index) {
129            return index - (index % InstrSlots::NUM);
130        }
131        static unsigned getBoundaryIndex(unsigned index) {
132            return getBaseIndex(index + InstrSlots::NUM - 1);
133        }
134        static unsigned getLoadIndex(unsigned index) {
135            return getBaseIndex(index) + InstrSlots::LOAD;
136        }
137        static unsigned getUseIndex(unsigned index) {
138            return getBaseIndex(index) + InstrSlots::USE;
139        }
140        static unsigned getDefIndex(unsigned index) {
141            return getBaseIndex(index) + InstrSlots::DEF;
142        }
143        static unsigned getStoreIndex(unsigned index) {
144            return getBaseIndex(index) + InstrSlots::STORE;
145        }
146
147        virtual void getAnalysisUsage(AnalysisUsage &AU) const;
148        virtual void releaseMemory();
149
150        /// runOnMachineFunction - pass entry point
151        virtual bool runOnMachineFunction(MachineFunction&);
152
153        Interval& getInterval(unsigned reg) {
154            assert(r2iMap_.count(reg)&& "Interval does not exist for register");
155            return *r2iMap_.find(reg)->second;
156        }
157
158        /// getInstructionIndex - returns the base index of instr
159        unsigned getInstructionIndex(MachineInstr* instr) const;
160
161        /// getInstructionFromIndex - given an index in any slot of an
162        /// instruction return a pointer the instruction
163        MachineInstr* getInstructionFromIndex(unsigned index) const;
164
165        Intervals& getIntervals() { return intervals_; }
166
167        std::vector<Interval*> addIntervalsForSpills(const Interval& i,
168                                                     VirtRegMap& vrm,
169                                                     int slot);
170
171    private:
172        /// computeIntervals - compute live intervals
173        void computeIntervals();
174
175        /// joinIntervals - join compatible live intervals
176        void joinIntervals();
177
178        /// handleRegisterDef - update intervals for a register def
179        /// (calls handlePhysicalRegisterDef and
180        /// handleVirtualRegisterDef)
181        void handleRegisterDef(MachineBasicBlock* mbb,
182                               MachineBasicBlock::iterator mi,
183                               unsigned reg);
184
185        /// handleVirtualRegisterDef - update intervals for a virtual
186        /// register def
187        void handleVirtualRegisterDef(MachineBasicBlock* mbb,
188                                      MachineBasicBlock::iterator mi,
189                                      Interval& interval);
190
191        /// handlePhysicalRegisterDef - update intervals for a
192        /// physical register def
193        void handlePhysicalRegisterDef(MachineBasicBlock* mbb,
194                                       MachineBasicBlock::iterator mi,
195                                       Interval& interval);
196
197        bool overlapsAliases(const Interval& lhs, const Interval& rhs) const;
198
199
200        Interval& getOrCreateInterval(unsigned reg);
201
202        /// rep - returns the representative of this register
203        unsigned rep(unsigned reg);
204
205        void printRegName(unsigned reg) const;
206    };
207
208    inline bool operator==(const LiveIntervals::Interval& lhs,
209                           const LiveIntervals::Interval& rhs) {
210        return lhs.reg == rhs.reg;
211    }
212
213    std::ostream& operator<<(std::ostream& os,
214                             const LiveIntervals::Interval& li);
215
216} // End llvm namespace
217
218#endif
219