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"
35 class LiveIntervals : public MachineFunctionPass
39 typedef std::pair<unsigned, unsigned> Range;
40 typedef std::vector<Range> Ranges;
41 unsigned reg; // the register of this interval
43 float weight; // weight of this interval (number of uses
45 Ranges ranges; // the ranges this register is valid
49 unsigned start() const {
50 assert(!ranges.empty() && "empty interval for register");
51 return ranges.front().first;
54 unsigned end() const {
55 assert(!ranges.empty() && "empty interval for register");
56 return ranges.back().second;
59 bool expiredAt(unsigned index) const {
60 return end() <= (index + 1);
63 bool liveAt(unsigned index) const;
65 bool overlaps(const Interval& other) const;
67 void addRange(unsigned start, unsigned end);
70 void mergeRangesForward(Ranges::iterator it);
72 void mergeRangesBackward(Ranges::iterator it);
75 struct StartPointComp {
76 bool operator()(const Interval& lhs, const Interval& rhs) {
77 return lhs.ranges.front().first < rhs.ranges.front().first;
82 bool operator()(const Interval& lhs, const Interval& rhs) {
83 return lhs.ranges.back().second < rhs.ranges.back().second;
87 typedef std::list<Interval> Intervals;
88 typedef std::vector<MachineBasicBlock*> MachineBasicBlockPtrs;
92 const TargetMachine* tm_;
93 const MRegisterInfo* mri_;
94 MachineBasicBlock* currentMbb_;
95 MachineBasicBlock::iterator currentInstr_;
98 typedef std::map<unsigned, MachineBasicBlock*> MbbIndex2MbbMap;
99 MbbIndex2MbbMap mbbi2mbbMap_;
101 typedef std::map<MachineInstr*, unsigned> Mi2IndexMap;
102 Mi2IndexMap mi2iMap_;
104 typedef std::map<unsigned, Intervals::iterator> Reg2IntervalMap;
105 Reg2IntervalMap r2iMap_;
107 Intervals intervals_;
110 virtual void getAnalysisUsage(AnalysisUsage &AU) const;
111 Intervals& getIntervals() { return intervals_; }
112 MachineBasicBlockPtrs getOrderedMachineBasicBlockPtrs() const {
113 MachineBasicBlockPtrs result;
114 for (MbbIndex2MbbMap::const_iterator
115 it = mbbi2mbbMap_.begin(), itEnd = mbbi2mbbMap_.end();
117 result.push_back(it->second);
123 /// runOnMachineFunction - pass entry point
124 bool runOnMachineFunction(MachineFunction&);
126 /// computeIntervals - compute live intervals
127 void computeIntervals();
130 /// handleRegisterDef - update intervals for a register def
131 /// (calls handlePhysicalRegisterDef and
132 /// handleVirtualRegisterDef)
133 void handleRegisterDef(MachineBasicBlock* mbb,
134 MachineBasicBlock::iterator mi,
137 /// handleVirtualRegisterDef - update intervals for a virtual
139 void handleVirtualRegisterDef(MachineBasicBlock* mbb,
140 MachineBasicBlock::iterator mi,
143 /// handlePhysicalRegisterDef - update intervals for a
144 /// physical register def
145 void handlePhysicalRegisterDef(MachineBasicBlock* mbb,
146 MachineBasicBlock::iterator mi,
149 unsigned getInstructionIndex(MachineInstr* instr) const;
151 void printRegName(unsigned reg) const;
154 inline bool operator==(const LiveIntervals::Interval& lhs,
155 const LiveIntervals::Interval& rhs) {
156 return lhs.reg == rhs.reg;
159 std::ostream& operator<<(std::ostream& os,
160 const LiveIntervals::Interval& li);
162 } // End llvm namespace