LiveIntervalAnalysis.h revision 2f6cb2b14c5811b154b06163355b3c8bc8b73231
1//===-- LiveIntervalAnalysis.h - Live Interval Analysis ---------*- C++ -*-===// 2// 3// The LLVM Compiler Infrastructure 4// 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. 7// 8//===----------------------------------------------------------------------===// 9// 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). 17// 18//===----------------------------------------------------------------------===// 19 20#ifndef LLVM_CODEGEN_LIVEINTERVAL_ANALYSIS_H 21#define LLVM_CODEGEN_LIVEINTERVAL_ANALYSIS_H 22 23#include "llvm/CodeGen/MachineFunctionPass.h" 24#include "llvm/CodeGen/LiveInterval.h" 25#include "llvm/ADT/BitVector.h" 26#include "llvm/ADT/DenseMap.h" 27#include "llvm/ADT/IndexedMap.h" 28 29namespace llvm { 30 31 class LiveVariables; 32 class MRegisterInfo; 33 class TargetInstrInfo; 34 class TargetRegisterClass; 35 class VirtRegMap; 36 37 class LiveIntervals : public MachineFunctionPass { 38 MachineFunction* mf_; 39 const TargetMachine* tm_; 40 const MRegisterInfo* mri_; 41 const TargetInstrInfo* tii_; 42 LiveVariables* lv_; 43 44 /// MBB2IdxMap - The index of the first instruction in the specified basic 45 /// block. 46 std::vector<unsigned> MBB2IdxMap; 47 48 typedef std::map<MachineInstr*, unsigned> Mi2IndexMap; 49 Mi2IndexMap mi2iMap_; 50 51 typedef std::vector<MachineInstr*> Index2MiMap; 52 Index2MiMap i2miMap_; 53 54 typedef std::map<unsigned, LiveInterval> Reg2IntervalMap; 55 Reg2IntervalMap r2iMap_; 56 57 typedef IndexedMap<unsigned> Reg2RegMap; 58 Reg2RegMap r2rMap_; 59 60 BitVector allocatableRegs_; 61 DenseMap<const TargetRegisterClass*, BitVector> allocatableRCRegs_; 62 63 /// JoinedLIs - Keep track which register intervals have been coalesced 64 /// with other intervals. 65 BitVector JoinedLIs; 66 67 public: 68 static char ID; // Pass identification, replacement for typeid 69 LiveIntervals() : MachineFunctionPass((intptr_t)&ID) {} 70 71 struct CopyRec { 72 MachineInstr *MI; 73 unsigned SrcReg, DstReg; 74 }; 75 CopyRec getCopyRec(MachineInstr *MI, unsigned SrcReg, unsigned DstReg) { 76 CopyRec R; 77 R.MI = MI; 78 R.SrcReg = SrcReg; 79 R.DstReg = DstReg; 80 return R; 81 } 82 struct InstrSlots { 83 enum { 84 LOAD = 0, 85 USE = 1, 86 DEF = 2, 87 STORE = 3, 88 NUM = 4 89 }; 90 }; 91 92 static unsigned getBaseIndex(unsigned index) { 93 return index - (index % InstrSlots::NUM); 94 } 95 static unsigned getBoundaryIndex(unsigned index) { 96 return getBaseIndex(index + InstrSlots::NUM - 1); 97 } 98 static unsigned getLoadIndex(unsigned index) { 99 return getBaseIndex(index) + InstrSlots::LOAD; 100 } 101 static unsigned getUseIndex(unsigned index) { 102 return getBaseIndex(index) + InstrSlots::USE; 103 } 104 static unsigned getDefIndex(unsigned index) { 105 return getBaseIndex(index) + InstrSlots::DEF; 106 } 107 static unsigned getStoreIndex(unsigned index) { 108 return getBaseIndex(index) + InstrSlots::STORE; 109 } 110 111 typedef Reg2IntervalMap::iterator iterator; 112 typedef Reg2IntervalMap::const_iterator const_iterator; 113 const_iterator begin() const { return r2iMap_.begin(); } 114 const_iterator end() const { return r2iMap_.end(); } 115 iterator begin() { return r2iMap_.begin(); } 116 iterator end() { return r2iMap_.end(); } 117 unsigned getNumIntervals() const { return r2iMap_.size(); } 118 119 LiveInterval &getInterval(unsigned reg) { 120 Reg2IntervalMap::iterator I = r2iMap_.find(reg); 121 assert(I != r2iMap_.end() && "Interval does not exist for register"); 122 return I->second; 123 } 124 125 const LiveInterval &getInterval(unsigned reg) const { 126 Reg2IntervalMap::const_iterator I = r2iMap_.find(reg); 127 assert(I != r2iMap_.end() && "Interval does not exist for register"); 128 return I->second; 129 } 130 131 bool hasInterval(unsigned reg) const { 132 return r2iMap_.count(reg); 133 } 134 135 /// getMBBStartIdx - Return the base index of the first instruction in the 136 /// specified MachineBasicBlock. 137 unsigned getMBBStartIdx(MachineBasicBlock *MBB) const { 138 return getMBBStartIdx(MBB->getNumber()); 139 } 140 141 unsigned getMBBStartIdx(unsigned MBBNo) const { 142 assert(MBBNo < MBB2IdxMap.size() && "Invalid MBB number!"); 143 return MBB2IdxMap[MBBNo]; 144 } 145 146 /// getInstructionIndex - returns the base index of instr 147 unsigned getInstructionIndex(MachineInstr* instr) const { 148 Mi2IndexMap::const_iterator it = mi2iMap_.find(instr); 149 assert(it != mi2iMap_.end() && "Invalid instruction!"); 150 return it->second; 151 } 152 153 /// getInstructionFromIndex - given an index in any slot of an 154 /// instruction return a pointer the instruction 155 MachineInstr* getInstructionFromIndex(unsigned index) const { 156 index /= InstrSlots::NUM; // convert index to vector index 157 assert(index < i2miMap_.size() && 158 "index does not correspond to an instruction"); 159 return i2miMap_[index]; 160 } 161 162 std::vector<LiveInterval*> addIntervalsForSpills(const LiveInterval& i, 163 VirtRegMap& vrm, 164 int slot); 165 166 /// CreateNewLiveInterval - Create a new live interval with the given live 167 /// ranges. The new live interval will have an infinite spill weight. 168 LiveInterval &CreateNewLiveInterval(const LiveInterval *LI, 169 const std::vector<LiveRange> &LRs); 170 171 virtual void getAnalysisUsage(AnalysisUsage &AU) const; 172 virtual void releaseMemory(); 173 174 /// runOnMachineFunction - pass entry point 175 virtual bool runOnMachineFunction(MachineFunction&); 176 177 /// print - Implement the dump method. 178 virtual void print(std::ostream &O, const Module* = 0) const; 179 void print(std::ostream *O, const Module* M = 0) const { 180 if (O) print(*O, M); 181 } 182 183 private: 184 /// isRemoved - returns true if the specified machine instr has been 185 /// removed. 186 bool isRemoved(MachineInstr* instr) const { 187 return !mi2iMap_.count(instr); 188 } 189 190 /// RemoveMachineInstrFromMaps - This marks the specified machine instr as 191 /// deleted. 192 void RemoveMachineInstrFromMaps(MachineInstr *MI) { 193 // remove index -> MachineInstr and 194 // MachineInstr -> index mappings 195 Mi2IndexMap::iterator mi2i = mi2iMap_.find(MI); 196 if (mi2i != mi2iMap_.end()) { 197 i2miMap_[mi2i->second/InstrSlots::NUM] = 0; 198 mi2iMap_.erase(mi2i); 199 } 200 } 201 202 /// computeIntervals - Compute live intervals. 203 void computeIntervals(); 204 205 /// joinIntervals - join compatible live intervals 206 void joinIntervals(); 207 208 /// CopyCoallesceInMBB - Coallsece copies in the specified MBB, putting 209 /// copies that cannot yet be coallesced into the "TryAgain" list. 210 void CopyCoallesceInMBB(MachineBasicBlock *MBB, 211 std::vector<CopyRec> *TryAgain, bool PhysOnly = false); 212 213 /// JoinCopy - Attempt to join intervals corresponding to SrcReg/DstReg, 214 /// which are the src/dst of the copy instruction CopyMI. This returns true 215 /// if the copy was successfully coallesced away, or if it is never possible 216 /// to coallesce these this copy, due to register constraints. It returns 217 /// false if it is not currently possible to coallesce this interval, but 218 /// it may be possible if other things get coallesced. 219 bool JoinCopy(MachineInstr *CopyMI, unsigned SrcReg, unsigned DstReg, 220 bool PhysOnly = false); 221 222 /// JoinIntervals - Attempt to join these two intervals. On failure, this 223 /// returns false. Otherwise, if one of the intervals being joined is a 224 /// physreg, this method always canonicalizes DestInt to be it. The output 225 /// "SrcInt" will not have been modified, so we can use this information 226 /// below to update aliases. 227 bool JoinIntervals(LiveInterval &LHS, LiveInterval &RHS); 228 229 /// SimpleJoin - Attempt to join the specified interval into this one. The 230 /// caller of this method must guarantee that the RHS only contains a single 231 /// value number and that the RHS is not defined by a copy from this 232 /// interval. This returns false if the intervals are not joinable, or it 233 /// joins them and returns true. 234 bool SimpleJoin(LiveInterval &LHS, LiveInterval &RHS); 235 236 /// handleRegisterDef - update intervals for a register def 237 /// (calls handlePhysicalRegisterDef and 238 /// handleVirtualRegisterDef) 239 void handleRegisterDef(MachineBasicBlock *MBB, 240 MachineBasicBlock::iterator MI, unsigned MIIdx, 241 unsigned reg); 242 243 /// handleVirtualRegisterDef - update intervals for a virtual 244 /// register def 245 void handleVirtualRegisterDef(MachineBasicBlock *MBB, 246 MachineBasicBlock::iterator MI, 247 unsigned MIIdx, 248 LiveInterval& interval); 249 250 /// handlePhysicalRegisterDef - update intervals for a physical register 251 /// def. 252 void handlePhysicalRegisterDef(MachineBasicBlock* mbb, 253 MachineBasicBlock::iterator mi, 254 unsigned MIIdx, 255 LiveInterval &interval, 256 unsigned SrcReg); 257 258 /// handleLiveInRegister - Create interval for a livein register. 259 void handleLiveInRegister(MachineBasicBlock* mbb, 260 unsigned MIIdx, 261 LiveInterval &interval, bool isAlias = false); 262 263 /// Return true if the two specified registers belong to different 264 /// register classes. The registers may be either phys or virt regs. 265 bool differingRegisterClasses(unsigned RegA, unsigned RegB) const; 266 267 268 bool AdjustCopiesBackFrom(LiveInterval &IntA, LiveInterval &IntB, 269 MachineInstr *CopyMI); 270 271 /// lastRegisterUse - Returns the last use of the specific register between 272 /// cycles Start and End. It also returns the use operand by reference. It 273 /// returns NULL if there are no uses. 274 MachineInstr *lastRegisterUse(unsigned Start, unsigned End, unsigned Reg, 275 MachineOperand *&MOU); 276 277 /// findDefOperand - Returns the MachineOperand that is a def of the specific 278 /// register. It returns NULL if the def is not found. 279 MachineOperand *findDefOperand(MachineInstr *MI, unsigned Reg); 280 281 /// unsetRegisterKill - Unset IsKill property of all uses of the specific 282 /// register of the specific instruction. 283 void unsetRegisterKill(MachineInstr *MI, unsigned Reg); 284 285 /// unsetRegisterKills - Unset IsKill property of all uses of specific register 286 /// between cycles Start and End. 287 void unsetRegisterKills(unsigned Start, unsigned End, unsigned Reg); 288 289 /// hasRegisterDef - True if the instruction defines the specific register. 290 /// 291 bool hasRegisterDef(MachineInstr *MI, unsigned Reg); 292 293 static LiveInterval createInterval(unsigned Reg); 294 295 void removeInterval(unsigned Reg) { 296 r2iMap_.erase(Reg); 297 } 298 299 LiveInterval &getOrCreateInterval(unsigned reg) { 300 Reg2IntervalMap::iterator I = r2iMap_.find(reg); 301 if (I == r2iMap_.end()) 302 I = r2iMap_.insert(I, std::make_pair(reg, createInterval(reg))); 303 return I->second; 304 } 305 306 /// rep - returns the representative of this register 307 unsigned rep(unsigned Reg) { 308 unsigned Rep = r2rMap_[Reg]; 309 if (Rep) 310 return r2rMap_[Reg] = rep(Rep); 311 return Reg; 312 } 313 314 void printRegName(unsigned reg) const; 315 }; 316 317} // End llvm namespace 318 319#endif 320