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"
25 #include "llvm/CodeGen/MachineBasicBlock.h"
34 class LiveIntervals : public MachineFunctionPass
38 typedef std::pair<unsigned, unsigned> Range;
39 typedef std::vector<Range> Ranges;
40 unsigned reg; // the register of this interval
41 Ranges ranges; // the ranges this register is valid
48 unsigned start() const {
49 assert(!ranges.empty() && "empty interval for register");
50 return ranges.front().first;
53 unsigned end() const {
54 assert(!ranges.empty() && "empty interval for register");
55 return ranges.back().second;
58 bool expired(unsigned index) const {
59 return end() <= index;
62 bool overlaps(unsigned index) const {
63 for (Ranges::const_iterator
64 i = ranges.begin(), e = ranges.end(); i != e; ++i) {
65 if (index >= i->first && index < i->second) {
72 void addRange(unsigned start, unsigned end) {
73 Range range = std::make_pair(start, end);
75 std::lower_bound(ranges.begin(), ranges.end(), range);
77 if (it == ranges.end()) {
78 it = ranges.insert(it, range);
82 assert(range.first <= it->first && "got wrong iterator?");
83 // merge ranges if necesary
84 if (range.first < it->first) {
85 if (range.second >= it->first) {
86 it->first = range.first;
89 it = ranges.insert(it, range);
90 assert(it != ranges.end() && "wtf?");
96 mergeRangesIfNecessary(it);
100 void mergeRangesIfNecessary(Ranges::iterator it) {
101 while (it != ranges.begin()) {
102 Ranges::iterator prev = it - 1;
103 if (prev->second < it->first) {
106 prev->second = it->second;
113 struct StartPointComp {
114 bool operator()(const Interval& lhs, const Interval& rhs) {
115 return lhs.ranges.front().first < rhs.ranges.front().first;
119 struct EndPointComp {
120 bool operator()(const Interval& lhs, const Interval& rhs) {
121 return lhs.ranges.back().second < rhs.ranges.back().second;
125 typedef std::vector<Interval> Intervals;
126 typedef std::vector<MachineBasicBlock*> MachineBasicBlockPtrs;
129 MachineFunction* mf_;
130 const TargetMachine* tm_;
131 const MRegisterInfo* mri_;
132 MachineBasicBlock* currentMbb_;
133 MachineBasicBlock::iterator currentInstr_;
136 std::vector<bool> allocatableRegisters_;
138 typedef std::map<unsigned, MachineBasicBlock*> MbbIndex2MbbMap;
139 MbbIndex2MbbMap mbbi2mbbMap_;
141 typedef std::map<MachineInstr*, unsigned> Mi2IndexMap;
142 Mi2IndexMap mi2iMap_;
144 typedef std::map<unsigned, unsigned> Reg2IntervalMap;
145 Reg2IntervalMap r2iMap_;
147 Intervals intervals_;
150 virtual void getAnalysisUsage(AnalysisUsage &AU) const;
151 Intervals& getIntervals() { return intervals_; }
152 MachineBasicBlockPtrs getOrderedMachineBasicBlockPtrs() const {
153 MachineBasicBlockPtrs result;
154 for (MbbIndex2MbbMap::const_iterator
155 it = mbbi2mbbMap_.begin(), itEnd = mbbi2mbbMap_.end();
157 result.push_back(it->second);
163 /// runOnMachineFunction - pass entry point
164 bool runOnMachineFunction(MachineFunction&);
166 /// computeIntervals - compute live intervals
167 void computeIntervals();
170 /// handleRegisterDef - update intervals for a register def
171 /// (calls handlePhysicalRegisterDef and
172 /// handleVirtualRegisterDef)
173 void handleRegisterDef(MachineBasicBlock* mbb,
174 MachineBasicBlock::iterator mi,
177 /// handleVirtualRegisterDef - update intervals for a virtual
179 void handleVirtualRegisterDef(MachineBasicBlock* mbb,
180 MachineBasicBlock::iterator mi,
183 /// handlePhysicalRegisterDef - update intervals for a
184 /// physical register def
185 void handlePhysicalRegisterDef(MachineBasicBlock* mbb,
186 MachineBasicBlock::iterator mi,
189 unsigned getInstructionIndex(MachineInstr* instr) const;
191 void printRegName(unsigned reg) const;
194 inline bool operator==(const LiveIntervals::Interval& lhs,
195 const LiveIntervals::Interval& rhs) {
196 return lhs.reg == rhs.reg;
199 inline std::ostream& operator<<(std::ostream& os,
200 const LiveIntervals::Interval& li) {
201 os << "%reg" << li.reg << " = ";
202 for (LiveIntervals::Interval::Ranges::const_iterator
203 i = li.ranges.begin(), e = li.ranges.end(); i != e; ++i) {
204 os << "[" << i->first << ", " << i->second << "]";
209 } // End llvm namespace