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
40 explicit LiveInterval(unsigned r);
42 bool empty() const { return ranges.empty(); }
46 unsigned start() const {
47 assert(!empty() && "empty interval for register");
48 return ranges.front().first;
51 unsigned end() const {
52 assert(!empty() && "empty interval for register");
53 return ranges.back().second;
56 bool expiredAt(unsigned index) const {
57 return end() <= (index + 1);
60 bool liveAt(unsigned index) const;
62 bool overlaps(const LiveInterval& other) const;
64 void addRange(unsigned start, unsigned end);
66 void join(const LiveInterval& other);
68 bool operator<(const LiveInterval& other) const {
69 return start() < other.start();
72 bool operator==(const LiveInterval& other) const {
73 return reg == other.reg;
77 Ranges::iterator mergeRangesForward(Ranges::iterator it);
78 Ranges::iterator mergeRangesBackward(Ranges::iterator it);
81 std::ostream& operator<<(std::ostream& os, const LiveInterval& li);
83 class LiveIntervals : public MachineFunctionPass
86 typedef std::list<LiveInterval> Intervals;
90 const TargetMachine* tm_;
91 const MRegisterInfo* mri_;
92 MachineBasicBlock* currentMbb_;
93 MachineBasicBlock::iterator currentInstr_;
96 typedef std::map<MachineInstr*, unsigned> Mi2IndexMap;
99 typedef std::vector<MachineInstr*> Index2MiMap;
100 Index2MiMap i2miMap_;
102 typedef std::map<unsigned, Intervals::iterator> Reg2IntervalMap;
103 Reg2IntervalMap r2iMap_;
105 typedef std::map<unsigned, unsigned> Reg2RegMap;
108 Intervals intervals_;
122 static unsigned getBaseIndex(unsigned index) {
123 return index - (index % InstrSlots::NUM);
125 static unsigned getBoundaryIndex(unsigned index) {
126 return getBaseIndex(index + InstrSlots::NUM - 1);
128 static unsigned getLoadIndex(unsigned index) {
129 return getBaseIndex(index) + InstrSlots::LOAD;
131 static unsigned getUseIndex(unsigned index) {
132 return getBaseIndex(index) + InstrSlots::USE;
134 static unsigned getDefIndex(unsigned index) {
135 return getBaseIndex(index) + InstrSlots::DEF;
137 static unsigned getStoreIndex(unsigned index) {
138 return getBaseIndex(index) + InstrSlots::STORE;
141 virtual void getAnalysisUsage(AnalysisUsage &AU) const;
142 virtual void releaseMemory();
144 /// runOnMachineFunction - pass entry point
145 virtual bool runOnMachineFunction(MachineFunction&);
147 LiveInterval& getInterval(unsigned reg) {
148 assert(r2iMap_.count(reg)&& "Interval does not exist for register");
149 return *r2iMap_.find(reg)->second;
152 /// getInstructionIndex - returns the base index of instr
153 unsigned getInstructionIndex(MachineInstr* instr) const;
155 /// getInstructionFromIndex - given an index in any slot of an
156 /// instruction return a pointer the instruction
157 MachineInstr* getInstructionFromIndex(unsigned index) const;
159 Intervals& getIntervals() { return intervals_; }
161 std::vector<LiveInterval*> addIntervalsForSpills(const LiveInterval& i,
166 /// computeIntervals - compute live intervals
167 void computeIntervals();
169 /// joinIntervals - join compatible live intervals
170 void joinIntervals();
172 /// joinIntervalsInMachineBB - Join intervals based on move
173 /// instructions in the specified basic block.
174 void joinIntervalsInMachineBB(MachineBasicBlock *MBB);
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,
187 LiveInterval& interval);
189 /// handlePhysicalRegisterDef - update intervals for a
190 /// physical register def
191 void handlePhysicalRegisterDef(MachineBasicBlock* mbb,
192 MachineBasicBlock::iterator mi,
193 LiveInterval& interval);
195 bool overlapsAliases(const LiveInterval& lhs,
196 const LiveInterval& rhs) const;
199 LiveInterval& getOrCreateInterval(unsigned reg);
201 /// rep - returns the representative of this register
202 unsigned rep(unsigned reg);
204 void printRegName(unsigned reg) const;
207 } // End llvm namespace