LiveIntervalAnalysis.h revision 5f37502bfbadfa65de087627bd67fd58bb03725c 
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
44            Interval(unsigned r);
45
46            bool empty() const { return ranges.empty(); }
47
48            bool spilled() const;
49
50            unsigned start() const {
51                assert(!empty() && "empty interval for register");
52                return ranges.front().first;
53            }
54
55            unsigned end() const {
56                assert(!empty() && "empty interval for register");
57                return ranges.back().second;
58            }
59
60            bool expiredAt(unsigned index) const {
61                return end() <= (index + 1);
62            }
63
64            bool liveAt(unsigned index) const;
65
66            bool overlaps(const Interval& other) const;
67
68            void addRange(unsigned start, unsigned end);
69
70            void join(const Interval& other);
71
72        private:
73            Ranges::iterator mergeRangesForward(Ranges::iterator it);
74
75            Ranges::iterator mergeRangesBackward(Ranges::iterator it);
76        };
77
78        struct StartPointComp {
79            bool operator()(const Interval& lhs, const Interval& rhs) {
80                return lhs.ranges.front().first < rhs.ranges.front().first;
81            }
82        };
83
84        struct EndPointComp {
85            bool operator()(const Interval& lhs, const Interval& rhs) {
86                return lhs.ranges.back().second < rhs.ranges.back().second;
87            }
88        };
89
90        typedef std::list<Interval> Intervals;
91
92    private:
93        MachineFunction* mf_;
94        const TargetMachine* tm_;
95        const MRegisterInfo* mri_;
96        MachineBasicBlock* currentMbb_;
97        MachineBasicBlock::iterator currentInstr_;
98        LiveVariables* lv_;
99
100        typedef std::map<unsigned, MachineBasicBlock*> MbbIndex2MbbMap;
101        MbbIndex2MbbMap mbbi2mbbMap_;
102
103        typedef std::map<MachineInstr*, unsigned> Mi2IndexMap;
104        Mi2IndexMap mi2iMap_;
105
106        typedef std::vector<MachineInstr*> Index2MiMap;
107        Index2MiMap i2miMap_;
108
109        typedef std::map<unsigned, Intervals::iterator> Reg2IntervalMap;
110        Reg2IntervalMap r2iMap_;
111
112        typedef std::map<unsigned, unsigned> Reg2RegMap;
113        Reg2RegMap r2rMap_;
114
115        Intervals intervals_;
116
117    public:
118        struct InstrSlots
119        {
120            enum {
121                LOAD  = 0,
122                USE   = 1,
123                DEF   = 2,
124                STORE = 3,
125                NUM   = 4,
126            };
127        };
128
129        static unsigned getBaseIndex(unsigned index) {
130            return index - (index % InstrSlots::NUM);
131        }
132        static unsigned getBoundaryIndex(unsigned index) {
133            return getBaseIndex(index + InstrSlots::NUM - 1);
134        }
135        static unsigned getLoadIndex(unsigned index) {
136            return getBaseIndex(index) + InstrSlots::LOAD;
137        }
138        static unsigned getUseIndex(unsigned index) {
139            return getBaseIndex(index) + InstrSlots::USE;
140        }
141        static unsigned getDefIndex(unsigned index) {
142            return getBaseIndex(index) + InstrSlots::DEF;
143        }
144        static unsigned getStoreIndex(unsigned index) {
145            return getBaseIndex(index) + InstrSlots::STORE;
146        }
147
148        virtual void getAnalysisUsage(AnalysisUsage &AU) const;
149        virtual void releaseMemory();
150
151        /// runOnMachineFunction - pass entry point
152        virtual bool runOnMachineFunction(MachineFunction&);
153
154        Interval& getInterval(unsigned reg) {
155            assert(r2iMap_.count(reg)&& "Interval does not exist for register");
156            return *r2iMap_.find(reg)->second;
157        }
158
159        /// getInstructionIndex - returns the base index of instr
160        unsigned getInstructionIndex(MachineInstr* instr) const;
161
162        /// getInstructionFromIndex - given an index in any slot of an
163        /// instruction return a pointer the instruction
164        MachineInstr* getInstructionFromIndex(unsigned index) const;
165
166        Intervals& getIntervals() { return intervals_; }
167
168        void updateSpilledInterval(Interval& i, VirtRegMap& vrm, int slot);
169
170    private:
171        /// computeIntervals - compute live intervals
172        void computeIntervals();
173
174        /// joinIntervals - join compatible live intervals
175        void joinIntervals();
176
177        /// handleRegisterDef - update intervals for a register def
178        /// (calls handlePhysicalRegisterDef and
179        /// handleVirtualRegisterDef)
180        void handleRegisterDef(MachineBasicBlock* mbb,
181                               MachineBasicBlock::iterator mi,
182                               unsigned reg);
183
184        /// handleVirtualRegisterDef - update intervals for a virtual
185        /// register def
186        void handleVirtualRegisterDef(MachineBasicBlock* mbb,
187                                      MachineBasicBlock::iterator mi,
188                                      unsigned reg);
189
190        /// handlePhysicalRegisterDef - update intervals for a
191        /// physical register def
192        void handlePhysicalRegisterDef(MachineBasicBlock* mbb,
193                                       MachineBasicBlock::iterator mi,
194                                       unsigned reg);
195
196        bool overlapsAliases(const Interval& lhs, const Interval& rhs) const;
197
198        /// rep - returns the representative of this register
199        unsigned rep(unsigned reg);
200
201        void printRegName(unsigned reg) const;
202    };
203
204    inline bool operator==(const LiveIntervals::Interval& lhs,
205                           const LiveIntervals::Interval& rhs) {
206        return lhs.reg == rhs.reg;
207    }
208
209    std::ostream& operator<<(std::ostream& os,
210                             const LiveIntervals::Interval& li);
211
212} // End llvm namespace
213
214#endif
215