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"
32 class LiveIntervals : public MachineFunctionPass
36 typedef std::pair<unsigned, unsigned> Range;
37 typedef std::vector<Range> Ranges;
38 unsigned reg; // the register of this interval
39 float weight; // weight of this interval (number of uses
41 Ranges ranges; // the ranges in which this register is live
45 unsigned start() const {
46 assert(!ranges.empty() && "empty interval for register");
47 return ranges.front().first;
50 unsigned end() const {
51 assert(!ranges.empty() && "empty interval for register");
52 return ranges.back().second;
55 bool expiredAt(unsigned index) const {
56 return end() <= (index + 1);
59 bool liveAt(unsigned index) const;
61 bool overlaps(const Interval& other) const;
63 void addRange(unsigned start, unsigned end);
65 void join(const Interval& other);
68 Ranges::iterator mergeRangesForward(Ranges::iterator it);
70 Ranges::iterator mergeRangesBackward(Ranges::iterator it);
73 struct StartPointComp {
74 bool operator()(const Interval& lhs, const Interval& rhs) {
75 return lhs.ranges.front().first < rhs.ranges.front().first;
80 bool operator()(const Interval& lhs, const Interval& rhs) {
81 return lhs.ranges.back().second < rhs.ranges.back().second;
85 typedef std::list<Interval> Intervals;
86 typedef std::map<unsigned, unsigned> Reg2RegMap;
87 typedef std::vector<MachineBasicBlock*> MachineBasicBlockPtrs;
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::map<unsigned, Intervals::iterator> Reg2IntervalMap;
104 Reg2IntervalMap r2iMap_;
108 Intervals intervals_;
111 virtual void getAnalysisUsage(AnalysisUsage &AU) const;
112 virtual void releaseMemory();
114 /// runOnMachineFunction - pass entry point
115 virtual bool runOnMachineFunction(MachineFunction&);
117 Intervals& getIntervals() { return intervals_; }
119 MachineBasicBlockPtrs getOrderedMachineBasicBlockPtrs() const {
120 MachineBasicBlockPtrs result;
121 for (MbbIndex2MbbMap::const_iterator
122 it = mbbi2mbbMap_.begin(), itEnd = mbbi2mbbMap_.end();
124 result.push_back(it->second);
129 const Reg2RegMap& getJoinedRegMap() const {
133 /// rep - returns the representative of this register
134 unsigned rep(unsigned reg);
137 /// computeIntervals - compute live intervals
138 void computeIntervals();
140 /// joinIntervals - join compatible live intervals
141 void joinIntervals();
143 /// handleRegisterDef - update intervals for a register def
144 /// (calls handlePhysicalRegisterDef and
145 /// handleVirtualRegisterDef)
146 void handleRegisterDef(MachineBasicBlock* mbb,
147 MachineBasicBlock::iterator mi,
150 /// handleVirtualRegisterDef - update intervals for a virtual
152 void handleVirtualRegisterDef(MachineBasicBlock* mbb,
153 MachineBasicBlock::iterator mi,
156 /// handlePhysicalRegisterDef - update intervals for a
157 /// physical register def
158 void handlePhysicalRegisterDef(MachineBasicBlock* mbb,
159 MachineBasicBlock::iterator mi,
162 bool overlapsAliases(const Interval& lhs, const Interval& rhs) const;
164 unsigned getInstructionIndex(MachineInstr* instr) const {
165 assert(mi2iMap_.count(instr) && "instruction not assigned a number");
166 return mi2iMap_.find(instr)->second;
169 void printRegName(unsigned reg) const;
172 inline bool operator==(const LiveIntervals::Interval& lhs,
173 const LiveIntervals::Interval& rhs) {
174 return lhs.reg == rhs.reg;
177 std::ostream& operator<<(std::ostream& os,
178 const LiveIntervals::Interval& li);
180 } // End llvm namespace