LiveIntervalAnalysis.h revision a3b8b5c0e0a1d0942288568b2012592184ca67c5 
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            assert(r2iMap_.count(reg)&& "Interval does not exist for register");
99            return *r2iMap_.find(reg)->second;
100        }
101
102        /// getInstructionIndex - returns the base index of instr
103        unsigned getInstructionIndex(MachineInstr* instr) const;
104
105        /// getInstructionFromIndex - given an index in any slot of an
106        /// instruction return a pointer the instruction
107        MachineInstr* getInstructionFromIndex(unsigned index) const;
108
109        Intervals& getIntervals() { return intervals_; }
110
111        std::vector<LiveInterval*> addIntervalsForSpills(const LiveInterval& i,
112                                                         VirtRegMap& vrm,
113                                                         int slot);
114
115    private:
116        /// computeIntervals - compute live intervals
117        void computeIntervals();
118
119        /// joinIntervals - join compatible live intervals
120        void joinIntervals();
121
122        /// joinIntervalsInMachineBB - Join intervals based on move
123        /// instructions in the specified basic block.
124        void joinIntervalsInMachineBB(MachineBasicBlock *MBB);
125
126        /// handleRegisterDef - update intervals for a register def
127        /// (calls handlePhysicalRegisterDef and
128        /// handleVirtualRegisterDef)
129        void handleRegisterDef(MachineBasicBlock* mbb,
130                               MachineBasicBlock::iterator mi,
131                               unsigned reg);
132
133        /// handleVirtualRegisterDef - update intervals for a virtual
134        /// register def
135        void handleVirtualRegisterDef(MachineBasicBlock* mbb,
136                                      MachineBasicBlock::iterator mi,
137                                      LiveInterval& interval);
138
139        /// handlePhysicalRegisterDef - update intervals for a
140        /// physical register def
141        void handlePhysicalRegisterDef(MachineBasicBlock* mbb,
142                                       MachineBasicBlock::iterator mi,
143                                       LiveInterval& interval);
144
145        bool overlapsAliases(const LiveInterval& lhs,
146                             const LiveInterval& rhs) const;
147
148
149        LiveInterval& getOrCreateInterval(unsigned reg);
150
151        /// rep - returns the representative of this register
152        unsigned rep(unsigned reg);
153
154        void printRegName(unsigned reg) const;
155    };
156
157} // End llvm namespace
158
159#endif
160