LLVM API Documentation
00001 //===-- LiveIntervalAnalysis.h - Live Interval Analysis ---------*- C++ -*-===// 00002 // 00003 // The LLVM Compiler Infrastructure 00004 // 00005 // This file was developed by the LLVM research group and is distributed under 00006 // the University of Illinois Open Source License. See LICENSE.TXT for details. 00007 // 00008 //===----------------------------------------------------------------------===// 00009 // 00010 // This file implements the LiveInterval analysis pass. Given some numbering of 00011 // each the machine instructions (in this implemention depth-first order) an 00012 // interval [i, j) is said to be a live interval for register v if there is no 00013 // instruction with number j' > j such that v is live at j' abd there is no 00014 // instruction with number i' < i such that v is live at i'. In this 00015 // implementation intervals can have holes, i.e. an interval might look like 00016 // [1,20), [50,65), [1000,1001). 00017 // 00018 //===----------------------------------------------------------------------===// 00019 00020 #ifndef LLVM_CODEGEN_LIVEINTERVAL_ANALYSIS_H 00021 #define LLVM_CODEGEN_LIVEINTERVAL_ANALYSIS_H 00022 00023 #include "llvm/ADT/DenseMap.h" 00024 #include "llvm/CodeGen/MachineFunctionPass.h" 00025 #include "LiveInterval.h" 00026 00027 namespace llvm { 00028 00029 class LiveVariables; 00030 class MRegisterInfo; 00031 class VirtRegMap; 00032 00033 class LiveIntervals : public MachineFunctionPass { 00034 MachineFunction* mf_; 00035 const TargetMachine* tm_; 00036 const MRegisterInfo* mri_; 00037 LiveVariables* lv_; 00038 00039 typedef std::map<MachineInstr*, unsigned> Mi2IndexMap; 00040 Mi2IndexMap mi2iMap_; 00041 00042 typedef std::vector<MachineInstr*> Index2MiMap; 00043 Index2MiMap i2miMap_; 00044 00045 typedef std::map<unsigned, LiveInterval> Reg2IntervalMap; 00046 Reg2IntervalMap r2iMap_; 00047 00048 typedef DenseMap<unsigned> Reg2RegMap; 00049 Reg2RegMap r2rMap_; 00050 00051 std::vector<bool> allocatableRegs_; 00052 00053 public: 00054 struct InstrSlots 00055 { 00056 enum { 00057 LOAD = 0, 00058 USE = 1, 00059 DEF = 2, 00060 STORE = 3, 00061 NUM = 4, 00062 }; 00063 }; 00064 00065 static unsigned getBaseIndex(unsigned index) { 00066 return index - (index % InstrSlots::NUM); 00067 } 00068 static unsigned getBoundaryIndex(unsigned index) { 00069 return getBaseIndex(index + InstrSlots::NUM - 1); 00070 } 00071 static unsigned getLoadIndex(unsigned index) { 00072 return getBaseIndex(index) + InstrSlots::LOAD; 00073 } 00074 static unsigned getUseIndex(unsigned index) { 00075 return getBaseIndex(index) + InstrSlots::USE; 00076 } 00077 static unsigned getDefIndex(unsigned index) { 00078 return getBaseIndex(index) + InstrSlots::DEF; 00079 } 00080 static unsigned getStoreIndex(unsigned index) { 00081 return getBaseIndex(index) + InstrSlots::STORE; 00082 } 00083 00084 typedef Reg2IntervalMap::iterator iterator; 00085 typedef Reg2IntervalMap::const_iterator const_iterator; 00086 const_iterator begin() const { return r2iMap_.begin(); } 00087 const_iterator end() const { return r2iMap_.end(); } 00088 iterator begin() { return r2iMap_.begin(); } 00089 iterator end() { return r2iMap_.end(); } 00090 unsigned getNumIntervals() const { return r2iMap_.size(); } 00091 00092 LiveInterval &getInterval(unsigned reg) { 00093 Reg2IntervalMap::iterator I = r2iMap_.find(reg); 00094 assert(I != r2iMap_.end() && "Interval does not exist for register"); 00095 return I->second; 00096 } 00097 00098 const LiveInterval &getInterval(unsigned reg) const { 00099 Reg2IntervalMap::const_iterator I = r2iMap_.find(reg); 00100 assert(I != r2iMap_.end() && "Interval does not exist for register"); 00101 return I->second; 00102 } 00103 00104 /// getInstructionIndex - returns the base index of instr 00105 unsigned getInstructionIndex(MachineInstr* instr) const { 00106 Mi2IndexMap::const_iterator it = mi2iMap_.find(instr); 00107 assert(it != mi2iMap_.end() && "Invalid instruction!"); 00108 return it->second; 00109 } 00110 00111 /// getInstructionFromIndex - given an index in any slot of an 00112 /// instruction return a pointer the instruction 00113 MachineInstr* getInstructionFromIndex(unsigned index) const { 00114 index /= InstrSlots::NUM; // convert index to vector index 00115 assert(index < i2miMap_.size() && 00116 "index does not correspond to an instruction"); 00117 return i2miMap_[index]; 00118 } 00119 00120 std::vector<LiveInterval*> addIntervalsForSpills(const LiveInterval& i, 00121 VirtRegMap& vrm, 00122 int slot); 00123 00124 virtual void getAnalysisUsage(AnalysisUsage &AU) const; 00125 virtual void releaseMemory(); 00126 00127 /// runOnMachineFunction - pass entry point 00128 virtual bool runOnMachineFunction(MachineFunction&); 00129 00130 /// print - Implement the dump method. 00131 virtual void print(std::ostream &O) const; 00132 00133 private: 00134 /// computeIntervals - compute live intervals 00135 void computeIntervals(); 00136 00137 /// joinIntervals - join compatible live intervals 00138 void joinIntervals(); 00139 00140 /// joinIntervalsInMachineBB - Join intervals based on move 00141 /// instructions in the specified basic block. 00142 void joinIntervalsInMachineBB(MachineBasicBlock *MBB); 00143 00144 /// handleRegisterDef - update intervals for a register def 00145 /// (calls handlePhysicalRegisterDef and 00146 /// handleVirtualRegisterDef) 00147 void handleRegisterDef(MachineBasicBlock* mbb, 00148 MachineBasicBlock::iterator mi, 00149 unsigned reg); 00150 00151 /// handleVirtualRegisterDef - update intervals for a virtual 00152 /// register def 00153 void handleVirtualRegisterDef(MachineBasicBlock* mbb, 00154 MachineBasicBlock::iterator mi, 00155 LiveInterval& interval); 00156 00157 /// handlePhysicalRegisterDef - update intervals for a 00158 /// physical register def 00159 void handlePhysicalRegisterDef(MachineBasicBlock* mbb, 00160 MachineBasicBlock::iterator mi, 00161 LiveInterval& interval); 00162 00163 /// Return true if the two specified registers belong to different 00164 /// register classes. The registers may be either phys or virt regs. 00165 bool differingRegisterClasses(unsigned RegA, unsigned RegB) const; 00166 00167 bool overlapsAliases(const LiveInterval *lhs, 00168 const LiveInterval *rhs) const; 00169 00170 static LiveInterval createInterval(unsigned Reg); 00171 00172 LiveInterval &getOrCreateInterval(unsigned reg) { 00173 Reg2IntervalMap::iterator I = r2iMap_.find(reg); 00174 if (I == r2iMap_.end()) 00175 I = r2iMap_.insert(I, std::make_pair(reg, createInterval(reg))); 00176 return I->second; 00177 } 00178 00179 /// rep - returns the representative of this register 00180 unsigned rep(unsigned Reg) { 00181 unsigned Rep = r2rMap_[Reg]; 00182 if (Rep) 00183 return r2rMap_[Reg] = rep(Rep); 00184 return Reg; 00185 } 00186 00187 void printRegName(unsigned reg) const; 00188 }; 00189 00190 } // End llvm namespace 00191 00192 #endif