1 //===-- LiveIntervalAnalysis.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_LIVEINTERVAL_ANALYSIS_H
21 #define LLVM_CODEGEN_LIVEINTERVAL_ANALYSIS_H
23 #include "llvm/CodeGen/MachineFunctionPass.h"
24 #include "LiveInterval.h"
33 class LiveIntervals : public MachineFunctionPass
36 typedef std::list<LiveInterval> Intervals;
40 const TargetMachine* tm_;
41 const MRegisterInfo* mri_;
42 MachineBasicBlock* currentMbb_;
43 MachineBasicBlock::iterator currentInstr_;
46 typedef std::map<MachineInstr*, unsigned> Mi2IndexMap;
49 typedef std::vector<MachineInstr*> Index2MiMap;
52 typedef std::map<unsigned, Intervals::iterator> Reg2IntervalMap;
53 Reg2IntervalMap r2iMap_;
55 typedef std::map<unsigned, unsigned> Reg2RegMap;
72 static unsigned getBaseIndex(unsigned index) {
73 return index - (index % InstrSlots::NUM);
75 static unsigned getBoundaryIndex(unsigned index) {
76 return getBaseIndex(index + InstrSlots::NUM - 1);
78 static unsigned getLoadIndex(unsigned index) {
79 return getBaseIndex(index) + InstrSlots::LOAD;
81 static unsigned getUseIndex(unsigned index) {
82 return getBaseIndex(index) + InstrSlots::USE;
84 static unsigned getDefIndex(unsigned index) {
85 return getBaseIndex(index) + InstrSlots::DEF;
87 static unsigned getStoreIndex(unsigned index) {
88 return getBaseIndex(index) + InstrSlots::STORE;
91 virtual void getAnalysisUsage(AnalysisUsage &AU) const;
92 virtual void releaseMemory();
94 /// runOnMachineFunction - pass entry point
95 virtual bool runOnMachineFunction(MachineFunction&);
97 LiveInterval& getInterval(unsigned reg) {
98 assert(r2iMap_.count(reg)&& "Interval does not exist for register");
99 return *r2iMap_.find(reg)->second;
102 /// getInstructionIndex - returns the base index of instr
103 unsigned getInstructionIndex(MachineInstr* instr) const;
105 /// getInstructionFromIndex - given an index in any slot of an
106 /// instruction return a pointer the instruction
107 MachineInstr* getInstructionFromIndex(unsigned index) const;
109 Intervals& getIntervals() { return intervals_; }
111 std::vector<LiveInterval*> addIntervalsForSpills(const LiveInterval& i,
116 /// computeIntervals - compute live intervals
117 void computeIntervals();
119 /// joinIntervals - join compatible live intervals
120 void joinIntervals();
122 /// joinIntervalsInMachineBB - Join intervals based on move
123 /// instructions in the specified basic block.
124 void joinIntervalsInMachineBB(MachineBasicBlock *MBB);
126 /// handleRegisterDef - update intervals for a register def
127 /// (calls handlePhysicalRegisterDef and
128 /// handleVirtualRegisterDef)
129 void handleRegisterDef(MachineBasicBlock* mbb,
130 MachineBasicBlock::iterator mi,
133 /// handleVirtualRegisterDef - update intervals for a virtual
135 void handleVirtualRegisterDef(MachineBasicBlock* mbb,
136 MachineBasicBlock::iterator mi,
137 LiveInterval& interval);
139 /// handlePhysicalRegisterDef - update intervals for a
140 /// physical register def
141 void handlePhysicalRegisterDef(MachineBasicBlock* mbb,
142 MachineBasicBlock::iterator mi,
143 LiveInterval& interval);
145 bool overlapsAliases(const LiveInterval& lhs,
146 const LiveInterval& rhs) const;
149 LiveInterval& getOrCreateInterval(unsigned reg);
151 /// rep - returns the representative of this register
152 unsigned rep(unsigned reg);
154 void printRegName(unsigned reg) const;
157 } // End llvm namespace