LiveIntervalAnalysis.h revision 4dc54ae0d950764443ee6a475cc9212d37074747 
1//===-- LiveIntervalAnalysis.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 numbering of
11// each the machine instructions (in this implemention depth-first order) an
12// interval [i, j) is said to be a live interval for register v if there is no
13// instruction with number j' > j such that v is live at j' abd there is no
14// instruction with number i' < i such that v is live at i'. In this
15// implementation intervals can have holes, i.e. an interval might look like
16// [1,20), [50,65), [1000,1001).
17//
18//===----------------------------------------------------------------------===//
19
20#ifndef LLVM_CODEGEN_LIVEINTERVAL_ANALYSIS_H
21#define LLVM_CODEGEN_LIVEINTERVAL_ANALYSIS_H
22
23#include "llvm/CodeGen/MachineFunctionPass.h"
24#include "LiveInterval.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        typedef std::list<LiveInterval> Intervals;
37
38    private:
39        MachineFunction* mf_;
40        const TargetMachine* tm_;
41        const MRegisterInfo* mri_;
42        MachineBasicBlock* currentMbb_;
43        MachineBasicBlock::iterator currentInstr_;
44        LiveVariables* lv_;
45
46        typedef std::map<MachineInstr*, unsigned> Mi2IndexMap;
47        Mi2IndexMap mi2iMap_;
48
49        typedef std::vector<MachineInstr*> Index2MiMap;
50        Index2MiMap i2miMap_;
51
52        typedef std::map<unsigned, Intervals::iterator> Reg2IntervalMap;
53        Reg2IntervalMap r2iMap_;
54
55        typedef std::map<unsigned, unsigned> Reg2RegMap;
56        Reg2RegMap r2rMap_;
57
58        Intervals intervals_;
59
60    public:
61        struct InstrSlots
62        {
63            enum {
64                LOAD  = 0,
65                USE   = 1,
66                DEF   = 2,
67                STORE = 3,
68                NUM   = 4,
69            };
70        };
71
72        static unsigned getBaseIndex(unsigned index) {
73            return index - (index % InstrSlots::NUM);
74        }
75        static unsigned getBoundaryIndex(unsigned index) {
76            return getBaseIndex(index + InstrSlots::NUM - 1);
77        }
78        static unsigned getLoadIndex(unsigned index) {
79            return getBaseIndex(index) + InstrSlots::LOAD;
80        }
81        static unsigned getUseIndex(unsigned index) {
82            return getBaseIndex(index) + InstrSlots::USE;
83        }
84        static unsigned getDefIndex(unsigned index) {
85            return getBaseIndex(index) + InstrSlots::DEF;
86        }
87        static unsigned getStoreIndex(unsigned index) {
88            return getBaseIndex(index) + InstrSlots::STORE;
89        }
90
91        virtual void getAnalysisUsage(AnalysisUsage &AU) const;
92        virtual void releaseMemory();
93
94        /// runOnMachineFunction - pass entry point
95        virtual bool runOnMachineFunction(MachineFunction&);
96
97        LiveInterval& getInterval(unsigned reg) {
98          Reg2IntervalMap::iterator I = r2iMap_.find(reg);
99            assert(I != r2iMap_.end()&& "Interval does not exist for register");
100            return *I->second;
101        }
102
103        /// getInstructionIndex - returns the base index of instr
104        unsigned getInstructionIndex(MachineInstr* instr) const;
105
106        /// getInstructionFromIndex - given an index in any slot of an
107        /// instruction return a pointer the instruction
108        MachineInstr* getInstructionFromIndex(unsigned index) const;
109
110        Intervals& getIntervals() { return intervals_; }
111
112        std::vector<LiveInterval*> addIntervalsForSpills(const LiveInterval& i,
113                                                         VirtRegMap& vrm,
114                                                         int slot);
115
116    private:
117        /// computeIntervals - compute live intervals
118        void computeIntervals();
119
120        /// joinIntervals - join compatible live intervals
121        void joinIntervals();
122
123        /// joinIntervalsInMachineBB - Join intervals based on move
124        /// instructions in the specified basic block.
125        void joinIntervalsInMachineBB(MachineBasicBlock *MBB);
126
127        /// handleRegisterDef - update intervals for a register def
128        /// (calls handlePhysicalRegisterDef and
129        /// handleVirtualRegisterDef)
130        void handleRegisterDef(MachineBasicBlock* mbb,
131                               MachineBasicBlock::iterator mi,
132                               unsigned reg);
133
134        /// handleVirtualRegisterDef - update intervals for a virtual
135        /// register def
136        void handleVirtualRegisterDef(MachineBasicBlock* mbb,
137                                      MachineBasicBlock::iterator mi,
138                                      LiveInterval& interval);
139
140        /// handlePhysicalRegisterDef - update intervals for a
141        /// physical register def
142        void handlePhysicalRegisterDef(MachineBasicBlock* mbb,
143                                       MachineBasicBlock::iterator mi,
144                                       LiveInterval& interval);
145
146        bool overlapsAliases(const LiveInterval& lhs,
147                             const LiveInterval& rhs) const;
148
149
150        LiveInterval& getOrCreateInterval(unsigned reg);
151
152        /// rep - returns the representative of this register
153        unsigned rep(unsigned reg);
154
155        void printRegName(unsigned reg) const;
156    };
157
158} // End llvm namespace
159
160#endif
161