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 "llvm/CodeGen/LiveInterval.h" 00026 00027 namespace llvm { 00028 00029 class LiveVariables; 00030 class MRegisterInfo; 00031 class TargetInstrInfo; 00032 class VirtRegMap; 00033 00034 class LiveIntervals : public MachineFunctionPass { 00035 MachineFunction* mf_; 00036 const TargetMachine* tm_; 00037 const MRegisterInfo* mri_; 00038 const TargetInstrInfo* tii_; 00039 LiveVariables* lv_; 00040 00041 typedef std::map<MachineInstr*, unsigned> Mi2IndexMap; 00042 Mi2IndexMap mi2iMap_; 00043 00044 typedef std::vector<MachineInstr*> Index2MiMap; 00045 Index2MiMap i2miMap_; 00046 00047 typedef std::map<unsigned, LiveInterval> Reg2IntervalMap; 00048 Reg2IntervalMap r2iMap_; 00049 00050 typedef DenseMap<unsigned> Reg2RegMap; 00051 Reg2RegMap r2rMap_; 00052 00053 std::vector<bool> allocatableRegs_; 00054 00055 public: 00056 struct InstrSlots 00057 { 00058 enum { 00059 LOAD = 0, 00060 USE = 1, 00061 DEF = 2, 00062 STORE = 3, 00063 NUM = 4 00064 }; 00065 }; 00066 00067 static unsigned getBaseIndex(unsigned index) { 00068 return index - (index % InstrSlots::NUM); 00069 } 00070 static unsigned getBoundaryIndex(unsigned index) { 00071 return getBaseIndex(index + InstrSlots::NUM - 1); 00072 } 00073 static unsigned getLoadIndex(unsigned index) { 00074 return getBaseIndex(index) + InstrSlots::LOAD; 00075 } 00076 static unsigned getUseIndex(unsigned index) { 00077 return getBaseIndex(index) + InstrSlots::USE; 00078 } 00079 static unsigned getDefIndex(unsigned index) { 00080 return getBaseIndex(index) + InstrSlots::DEF; 00081 } 00082 static unsigned getStoreIndex(unsigned index) { 00083 return getBaseIndex(index) + InstrSlots::STORE; 00084 } 00085 00086 typedef Reg2IntervalMap::iterator iterator; 00087 typedef Reg2IntervalMap::const_iterator const_iterator; 00088 const_iterator begin() const { return r2iMap_.begin(); } 00089 const_iterator end() const { return r2iMap_.end(); } 00090 iterator begin() { return r2iMap_.begin(); } 00091 iterator end() { return r2iMap_.end(); } 00092 unsigned getNumIntervals() const { return r2iMap_.size(); } 00093 00094 LiveInterval &getInterval(unsigned reg) { 00095 Reg2IntervalMap::iterator I = r2iMap_.find(reg); 00096 assert(I != r2iMap_.end() && "Interval does not exist for register"); 00097 return I->second; 00098 } 00099 00100 const LiveInterval &getInterval(unsigned reg) const { 00101 Reg2IntervalMap::const_iterator I = r2iMap_.find(reg); 00102 assert(I != r2iMap_.end() && "Interval does not exist for register"); 00103 return I->second; 00104 } 00105 00106 /// getInstructionIndex - returns the base index of instr 00107 unsigned getInstructionIndex(MachineInstr* instr) const { 00108 Mi2IndexMap::const_iterator it = mi2iMap_.find(instr); 00109 assert(it != mi2iMap_.end() && "Invalid instruction!"); 00110 return it->second; 00111 } 00112 00113 /// getInstructionFromIndex - given an index in any slot of an 00114 /// instruction return a pointer the instruction 00115 MachineInstr* getInstructionFromIndex(unsigned index) const { 00116 index /= InstrSlots::NUM; // convert index to vector index 00117 assert(index < i2miMap_.size() && 00118 "index does not correspond to an instruction"); 00119 return i2miMap_[index]; 00120 } 00121 00122 std::vector<LiveInterval*> addIntervalsForSpills(const LiveInterval& i, 00123 VirtRegMap& vrm, 00124 int slot); 00125 00126 virtual void getAnalysisUsage(AnalysisUsage &AU) const; 00127 virtual void releaseMemory(); 00128 00129 /// runOnMachineFunction - pass entry point 00130 virtual bool runOnMachineFunction(MachineFunction&); 00131 00132 /// print - Implement the dump method. 00133 virtual void print(std::ostream &O, const Module* = 0) const; 00134 00135 private: 00136 /// computeIntervals - compute live intervals 00137 void computeIntervals(); 00138 00139 /// joinIntervals - join compatible live intervals 00140 void joinIntervals(); 00141 00142 /// joinIntervalsInMachineBB - Join intervals based on move 00143 /// instructions in the specified basic block. 00144 void joinIntervalsInMachineBB(MachineBasicBlock *MBB); 00145 00146 /// handleRegisterDef - update intervals for a register def 00147 /// (calls handlePhysicalRegisterDef and 00148 /// handleVirtualRegisterDef) 00149 void handleRegisterDef(MachineBasicBlock* mbb, 00150 MachineBasicBlock::iterator mi, 00151 unsigned reg); 00152 00153 /// handleVirtualRegisterDef - update intervals for a virtual 00154 /// register def 00155 void handleVirtualRegisterDef(MachineBasicBlock* mbb, 00156 MachineBasicBlock::iterator mi, 00157 LiveInterval& interval); 00158 00159 /// handlePhysicalRegisterDef - update intervals for a physical register 00160 /// def. If the defining instruction is a move instruction, SrcReg will be 00161 /// the input register, and DestReg will be the result. Note that Interval 00162 /// may not match DestReg (it might be an alias instead). 00163 /// 00164 void handlePhysicalRegisterDef(MachineBasicBlock* mbb, 00165 MachineBasicBlock::iterator mi, 00166 LiveInterval& interval, 00167 unsigned SrcReg, unsigned DestReg, 00168 bool isLiveIn = false); 00169 00170 /// Return true if the two specified registers belong to different 00171 /// register classes. The registers may be either phys or virt regs. 00172 bool differingRegisterClasses(unsigned RegA, unsigned RegB) const; 00173 00174 00175 bool AdjustIfAllOverlappingRangesAreCopiesFrom(LiveInterval &IntA, 00176 LiveInterval &IntB, 00177 unsigned CopyIdx); 00178 00179 bool overlapsAliases(const LiveInterval *lhs, 00180 const LiveInterval *rhs) const; 00181 00182 static LiveInterval createInterval(unsigned Reg); 00183 00184 LiveInterval &getOrCreateInterval(unsigned reg) { 00185 Reg2IntervalMap::iterator I = r2iMap_.find(reg); 00186 if (I == r2iMap_.end()) 00187 I = r2iMap_.insert(I, std::make_pair(reg, createInterval(reg))); 00188 return I->second; 00189 } 00190 00191 /// rep - returns the representative of this register 00192 unsigned rep(unsigned Reg) { 00193 unsigned Rep = r2rMap_[Reg]; 00194 if (Rep) 00195 return r2rMap_[Reg] = rep(Rep); 00196 return Reg; 00197 } 00198 00199 void printRegName(unsigned reg) const; 00200 }; 00201 00202 } // End llvm namespace 00203 00204 #endif