LiveIntervalAnalysis.h revision 26bfc08b80c904c71487ac1ab49a8b3a15a8d3e9 
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 "llvm/CodeGen/MachineBasicBlock.h"
26#include <iostream>
27#include <map>
28
29namespace llvm {
30
31    class LiveVariables;
32    class MRegisterInfo;
33
34    class LiveIntervals : public MachineFunctionPass
35    {
36    public:
37        struct Interval {
38            typedef std::pair<unsigned, unsigned> Range;
39            typedef std::vector<Range> Ranges;
40            unsigned reg;   // the register of this interval
41            unsigned hint;
42            float weight;   // weight of this interval (number of uses
43                            // * 10^loopDepth)
44            Ranges ranges;  // the ranges this register is valid
45
46            Interval(unsigned r);
47
48            unsigned start() const {
49                assert(!ranges.empty() && "empty interval for register");
50                return ranges.front().first;
51            }
52
53            unsigned end() const {
54                assert(!ranges.empty() && "empty interval for register");
55                return ranges.back().second;
56            }
57
58            bool expiredAt(unsigned index) const {
59                return end() <= index;
60            }
61
62            bool liveAt(unsigned index) const;
63
64            bool overlaps(const Interval& other) const;
65
66            void addRange(unsigned start, unsigned end);
67
68        private:
69            void mergeRangesForward(Ranges::iterator it);
70
71            void mergeRangesBackward(Ranges::iterator it);
72        };
73
74        struct StartPointComp {
75            bool operator()(const Interval& lhs, const Interval& rhs) {
76                return lhs.ranges.front().first < rhs.ranges.front().first;
77            }
78        };
79
80        struct EndPointComp {
81            bool operator()(const Interval& lhs, const Interval& rhs) {
82                return lhs.ranges.back().second < rhs.ranges.back().second;
83            }
84        };
85
86        typedef std::vector<Interval> Intervals;
87        typedef std::vector<MachineBasicBlock*> MachineBasicBlockPtrs;
88
89    private:
90        MachineFunction* mf_;
91        const TargetMachine* tm_;
92        const MRegisterInfo* mri_;
93        MachineBasicBlock* currentMbb_;
94        MachineBasicBlock::iterator currentInstr_;
95        LiveVariables* lv_;
96
97        std::vector<bool> allocatableRegisters_;
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::map<unsigned, unsigned> Reg2IntervalMap;
106        Reg2IntervalMap r2iMap_;
107
108        Intervals intervals_;
109
110    public:
111        virtual void getAnalysisUsage(AnalysisUsage &AU) const;
112        Intervals& getIntervals() { return intervals_; }
113        MachineBasicBlockPtrs getOrderedMachineBasicBlockPtrs() const {
114            MachineBasicBlockPtrs result;
115            for (MbbIndex2MbbMap::const_iterator
116                     it = mbbi2mbbMap_.begin(), itEnd = mbbi2mbbMap_.end();
117                 it != itEnd; ++it) {
118                result.push_back(it->second);
119            }
120            return result;
121        }
122
123    private:
124        /// runOnMachineFunction - pass entry point
125        bool runOnMachineFunction(MachineFunction&);
126
127        /// computeIntervals - compute live intervals
128        void computeIntervals();
129
130
131        /// handleRegisterDef - update intervals for a register def
132        /// (calls handlePhysicalRegisterDef and
133        /// handleVirtualRegisterDef)
134        void handleRegisterDef(MachineBasicBlock* mbb,
135                               MachineBasicBlock::iterator mi,
136                               unsigned reg);
137
138        /// handleVirtualRegisterDef - update intervals for a virtual
139        /// register def
140        void handleVirtualRegisterDef(MachineBasicBlock* mbb,
141                                      MachineBasicBlock::iterator mi,
142                                      unsigned reg);
143
144        /// handlePhysicalRegisterDef - update intervals for a
145        /// physical register def
146        void handlePhysicalRegisterDef(MachineBasicBlock* mbb,
147                                       MachineBasicBlock::iterator mi,
148                                       unsigned reg);
149
150        unsigned getInstructionIndex(MachineInstr* instr) const;
151
152        void printRegName(unsigned reg) const;
153    };
154
155    inline bool operator==(const LiveIntervals::Interval& lhs,
156                           const LiveIntervals::Interval& rhs) {
157        return lhs.reg == rhs.reg;
158    }
159
160    std::ostream& operator<<(std::ostream& os,
161                             const LiveIntervals::Interval& li);
162
163} // End llvm namespace
164
165#endif
166