1 //===-- llvm/CodeGen/LiveInterval.h - Live Interval Analysis ----*- C++ -*-===//
3 // The LLVM Compiler Infrastructure
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.
8 //===----------------------------------------------------------------------===//
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).
18 //===----------------------------------------------------------------------===//
20 #ifndef LLVM_CODEGEN_LIVEINTERVALS_H
21 #define LLVM_CODEGEN_LIVEINTERVALS_H
23 #include "llvm/CodeGen/MachineFunctionPass.h"
33 typedef std::pair<unsigned, unsigned> Range;
34 typedef std::vector<Range> Ranges;
35 unsigned reg; // the register of this interval
36 float weight; // weight of this interval:
37 // (number of uses *10^loopDepth)
38 Ranges ranges; // the ranges in which this register is live
39 bool isDefinedOnce; // True if there is one def of this register
41 explicit LiveInterval(unsigned r);
43 bool empty() const { return ranges.empty(); }
47 unsigned start() const {
48 assert(!empty() && "empty interval for register");
49 return ranges.front().first;
52 unsigned end() const {
53 assert(!empty() && "empty interval for register");
54 return ranges.back().second;
57 bool expiredAt(unsigned index) const {
58 return end() <= (index + 1);
61 bool liveAt(unsigned index) const;
63 bool overlaps(const LiveInterval& other) const;
65 void addRange(unsigned start, unsigned end);
67 void join(const LiveInterval& other);
69 bool operator<(const LiveInterval& other) const {
70 return start() < other.start();
73 bool operator==(const LiveInterval& other) const {
74 return reg == other.reg;
78 Ranges::iterator mergeRangesForward(Ranges::iterator it);
79 Ranges::iterator mergeRangesBackward(Ranges::iterator it);
82 std::ostream& operator<<(std::ostream& os, const LiveInterval& li);
84 class LiveIntervals : public MachineFunctionPass
87 typedef std::list<LiveInterval> Intervals;
91 const TargetMachine* tm_;
92 const MRegisterInfo* mri_;
93 MachineBasicBlock* currentMbb_;
94 MachineBasicBlock::iterator currentInstr_;
97 typedef std::map<MachineInstr*, unsigned> Mi2IndexMap;
100 typedef std::vector<MachineInstr*> Index2MiMap;
101 Index2MiMap i2miMap_;
103 typedef std::map<unsigned, Intervals::iterator> Reg2IntervalMap;
104 Reg2IntervalMap r2iMap_;
106 typedef std::map<unsigned, unsigned> Reg2RegMap;
109 Intervals intervals_;
123 static unsigned getBaseIndex(unsigned index) {
124 return index - (index % InstrSlots::NUM);
126 static unsigned getBoundaryIndex(unsigned index) {
127 return getBaseIndex(index + InstrSlots::NUM - 1);
129 static unsigned getLoadIndex(unsigned index) {
130 return getBaseIndex(index) + InstrSlots::LOAD;
132 static unsigned getUseIndex(unsigned index) {
133 return getBaseIndex(index) + InstrSlots::USE;
135 static unsigned getDefIndex(unsigned index) {
136 return getBaseIndex(index) + InstrSlots::DEF;
138 static unsigned getStoreIndex(unsigned index) {
139 return getBaseIndex(index) + InstrSlots::STORE;
142 virtual void getAnalysisUsage(AnalysisUsage &AU) const;
143 virtual void releaseMemory();
145 /// runOnMachineFunction - pass entry point
146 virtual bool runOnMachineFunction(MachineFunction&);
148 LiveInterval& getInterval(unsigned reg) {
149 assert(r2iMap_.count(reg)&& "Interval does not exist for register");
150 return *r2iMap_.find(reg)->second;
153 /// getInstructionIndex - returns the base index of instr
154 unsigned getInstructionIndex(MachineInstr* instr) const;
156 /// getInstructionFromIndex - given an index in any slot of an
157 /// instruction return a pointer the instruction
158 MachineInstr* getInstructionFromIndex(unsigned index) const;
160 Intervals& getIntervals() { return intervals_; }
162 std::vector<LiveInterval*> addIntervalsForSpills(const LiveInterval& i,
167 /// computeIntervals - compute live intervals
168 void computeIntervals();
170 /// joinIntervals - join compatible live intervals
171 void joinIntervals();
173 /// joinIntervalsInMachineBB - Join intervals based on move
174 /// instructions in the specified basic block.
175 void joinIntervalsInMachineBB(MachineBasicBlock *MBB);
177 /// handleRegisterDef - update intervals for a register def
178 /// (calls handlePhysicalRegisterDef and
179 /// handleVirtualRegisterDef)
180 void handleRegisterDef(MachineBasicBlock* mbb,
181 MachineBasicBlock::iterator mi,
184 /// handleVirtualRegisterDef - update intervals for a virtual
186 void handleVirtualRegisterDef(MachineBasicBlock* mbb,
187 MachineBasicBlock::iterator mi,
188 LiveInterval& interval);
190 /// handlePhysicalRegisterDef - update intervals for a
191 /// physical register def
192 void handlePhysicalRegisterDef(MachineBasicBlock* mbb,
193 MachineBasicBlock::iterator mi,
194 LiveInterval& interval);
196 bool overlapsAliases(const LiveInterval& lhs,
197 const LiveInterval& rhs) const;
200 LiveInterval& getOrCreateInterval(unsigned reg);
202 /// rep - returns the representative of this register
203 unsigned rep(unsigned reg);
205 void printRegName(unsigned reg) const;
208 } // End llvm namespace