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
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),
19 //===----------------------------------------------------------------------===//
21 #ifndef LLVM_CODEGEN_LIVEINTERVALS_H
22 #define LLVM_CODEGEN_LIVEINTERVALS_H
24 #include "llvm/CodeGen/MachineFunctionPass.h"
34 typedef std::pair<unsigned, unsigned> Range;
35 typedef std::vector<Range> Ranges;
36 unsigned reg; // the register of this interval
37 float weight; // weight of this interval:
38 // (number of uses *10^loopDepth)
39 Ranges ranges; // the ranges in which this register is live
41 explicit Interval(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 Interval& other) const;
65 void addRange(unsigned start, unsigned end);
67 void join(const Interval& other);
69 bool operator<(const Interval& other) const {
70 return start() < other.start();
73 bool operator==(const Interval& 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 Interval& li);
84 class LiveIntervals : public MachineFunctionPass
87 typedef std::list<Interval> Intervals;
91 const TargetMachine* tm_;
92 const MRegisterInfo* mri_;
93 MachineBasicBlock* currentMbb_;
94 MachineBasicBlock::iterator currentInstr_;
97 typedef std::map<unsigned, MachineBasicBlock*> MbbIndex2MbbMap;
98 MbbIndex2MbbMap mbbi2mbbMap_;
100 typedef std::map<MachineInstr*, unsigned> Mi2IndexMap;
101 Mi2IndexMap mi2iMap_;
103 typedef std::vector<MachineInstr*> Index2MiMap;
104 Index2MiMap i2miMap_;
106 typedef std::map<unsigned, Intervals::iterator> Reg2IntervalMap;
107 Reg2IntervalMap r2iMap_;
109 typedef std::map<unsigned, unsigned> Reg2RegMap;
112 Intervals intervals_;
126 static unsigned getBaseIndex(unsigned index) {
127 return index - (index % InstrSlots::NUM);
129 static unsigned getBoundaryIndex(unsigned index) {
130 return getBaseIndex(index + InstrSlots::NUM - 1);
132 static unsigned getLoadIndex(unsigned index) {
133 return getBaseIndex(index) + InstrSlots::LOAD;
135 static unsigned getUseIndex(unsigned index) {
136 return getBaseIndex(index) + InstrSlots::USE;
138 static unsigned getDefIndex(unsigned index) {
139 return getBaseIndex(index) + InstrSlots::DEF;
141 static unsigned getStoreIndex(unsigned index) {
142 return getBaseIndex(index) + InstrSlots::STORE;
145 virtual void getAnalysisUsage(AnalysisUsage &AU) const;
146 virtual void releaseMemory();
148 /// runOnMachineFunction - pass entry point
149 virtual bool runOnMachineFunction(MachineFunction&);
151 Interval& getInterval(unsigned reg) {
152 assert(r2iMap_.count(reg)&& "Interval does not exist for register");
153 return *r2iMap_.find(reg)->second;
156 /// getInstructionIndex - returns the base index of instr
157 unsigned getInstructionIndex(MachineInstr* instr) const;
159 /// getInstructionFromIndex - given an index in any slot of an
160 /// instruction return a pointer the instruction
161 MachineInstr* getInstructionFromIndex(unsigned index) const;
163 Intervals& getIntervals() { return intervals_; }
165 std::vector<Interval*> addIntervalsForSpills(const Interval& i,
170 /// computeIntervals - compute live intervals
171 void computeIntervals();
173 /// joinIntervals - join compatible live intervals
174 void joinIntervals();
176 /// handleRegisterDef - update intervals for a register def
177 /// (calls handlePhysicalRegisterDef and
178 /// handleVirtualRegisterDef)
179 void handleRegisterDef(MachineBasicBlock* mbb,
180 MachineBasicBlock::iterator mi,
183 /// handleVirtualRegisterDef - update intervals for a virtual
185 void handleVirtualRegisterDef(MachineBasicBlock* mbb,
186 MachineBasicBlock::iterator mi,
189 /// handlePhysicalRegisterDef - update intervals for a
190 /// physical register def
191 void handlePhysicalRegisterDef(MachineBasicBlock* mbb,
192 MachineBasicBlock::iterator mi,
195 bool overlapsAliases(const Interval& lhs, const Interval& rhs) const;
198 Interval& getOrCreateInterval(unsigned reg);
200 /// rep - returns the representative of this register
201 unsigned rep(unsigned reg);
203 void printRegName(unsigned reg) const;
206 } // End llvm namespace