LiveIntervalAnalysis.h revision 4ca980e7f9ce7b78955307c2d07001a24d3b6bef
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#include "llvm/ADT/SmallPtrSet.h" 29#include "llvm/ADT/SmallVector.h" 30#include "llvm/Support/Allocator.h" 31 32namespace llvm { 33 34 class LiveVariables; 35 class MRegisterInfo; 36 class TargetInstrInfo; 37 class TargetRegisterClass; 38 class VirtRegMap; 39 typedef std::pair<unsigned, MachineBasicBlock*> IdxMBBPair; 40 41 class LiveIntervals : public MachineFunctionPass { 42 MachineFunction* mf_; 43 const TargetMachine* tm_; 44 const MRegisterInfo* mri_; 45 const TargetInstrInfo* tii_; 46 LiveVariables* lv_; 47 48 /// Special pool allocator for VNInfo's (LiveInterval val#). 49 /// 50 BumpPtrAllocator VNInfoAllocator; 51 52 /// MBB2IdxMap - The indexes of the first and last instructions in the 53 /// specified basic block. 54 std::vector<std::pair<unsigned, unsigned> > MBB2IdxMap; 55 56 /// Idx2MBBMap - Sorted list of pairs of index of first instruction 57 /// and MBB id. 58 std::vector<IdxMBBPair> Idx2MBBMap; 59 60 typedef std::map<MachineInstr*, unsigned> Mi2IndexMap; 61 Mi2IndexMap mi2iMap_; 62 63 typedef std::vector<MachineInstr*> Index2MiMap; 64 Index2MiMap i2miMap_; 65 66 typedef std::map<unsigned, LiveInterval> Reg2IntervalMap; 67 Reg2IntervalMap r2iMap_; 68 69 BitVector allocatableRegs_; 70 71 std::vector<MachineInstr*> ClonedMIs; 72 73 public: 74 static char ID; // Pass identification, replacement for typeid 75 LiveIntervals() : MachineFunctionPass((intptr_t)&ID) {} 76 77 struct InstrSlots { 78 enum { 79 LOAD = 0, 80 USE = 1, 81 DEF = 2, 82 STORE = 3, 83 NUM = 4 84 }; 85 }; 86 87 static unsigned getBaseIndex(unsigned index) { 88 return index - (index % InstrSlots::NUM); 89 } 90 static unsigned getBoundaryIndex(unsigned index) { 91 return getBaseIndex(index + InstrSlots::NUM - 1); 92 } 93 static unsigned getLoadIndex(unsigned index) { 94 return getBaseIndex(index) + InstrSlots::LOAD; 95 } 96 static unsigned getUseIndex(unsigned index) { 97 return getBaseIndex(index) + InstrSlots::USE; 98 } 99 static unsigned getDefIndex(unsigned index) { 100 return getBaseIndex(index) + InstrSlots::DEF; 101 } 102 static unsigned getStoreIndex(unsigned index) { 103 return getBaseIndex(index) + InstrSlots::STORE; 104 } 105 106 typedef Reg2IntervalMap::iterator iterator; 107 typedef Reg2IntervalMap::const_iterator const_iterator; 108 const_iterator begin() const { return r2iMap_.begin(); } 109 const_iterator end() const { return r2iMap_.end(); } 110 iterator begin() { return r2iMap_.begin(); } 111 iterator end() { return r2iMap_.end(); } 112 unsigned getNumIntervals() const { return r2iMap_.size(); } 113 114 LiveInterval &getInterval(unsigned reg) { 115 Reg2IntervalMap::iterator I = r2iMap_.find(reg); 116 assert(I != r2iMap_.end() && "Interval does not exist for register"); 117 return I->second; 118 } 119 120 const LiveInterval &getInterval(unsigned reg) const { 121 Reg2IntervalMap::const_iterator I = r2iMap_.find(reg); 122 assert(I != r2iMap_.end() && "Interval does not exist for register"); 123 return I->second; 124 } 125 126 bool hasInterval(unsigned reg) const { 127 return r2iMap_.count(reg); 128 } 129 130 /// getMBBStartIdx - Return the base index of the first instruction in the 131 /// specified MachineBasicBlock. 132 unsigned getMBBStartIdx(MachineBasicBlock *MBB) const { 133 return getMBBStartIdx(MBB->getNumber()); 134 } 135 unsigned getMBBStartIdx(unsigned MBBNo) const { 136 assert(MBBNo < MBB2IdxMap.size() && "Invalid MBB number!"); 137 return MBB2IdxMap[MBBNo].first; 138 } 139 140 /// getMBBEndIdx - Return the store index of the last instruction in the 141 /// specified MachineBasicBlock. 142 unsigned getMBBEndIdx(MachineBasicBlock *MBB) const { 143 return getMBBEndIdx(MBB->getNumber()); 144 } 145 unsigned getMBBEndIdx(unsigned MBBNo) const { 146 assert(MBBNo < MBB2IdxMap.size() && "Invalid MBB number!"); 147 return MBB2IdxMap[MBBNo].second; 148 } 149 150 /// getInstructionIndex - returns the base index of instr 151 unsigned getInstructionIndex(MachineInstr* instr) const { 152 Mi2IndexMap::const_iterator it = mi2iMap_.find(instr); 153 assert(it != mi2iMap_.end() && "Invalid instruction!"); 154 return it->second; 155 } 156 157 /// getInstructionFromIndex - given an index in any slot of an 158 /// instruction return a pointer the instruction 159 MachineInstr* getInstructionFromIndex(unsigned index) const { 160 index /= InstrSlots::NUM; // convert index to vector index 161 assert(index < i2miMap_.size() && 162 "index does not correspond to an instruction"); 163 return i2miMap_[index]; 164 } 165 166 /// findLiveInMBBs - Given a live range, if the value of the range 167 /// is live in any MBB returns true as well as the list of basic blocks 168 /// where the value is live in. 169 bool findLiveInMBBs(const LiveRange &LR, 170 SmallVector<MachineBasicBlock*, 4> &MBBs) const; 171 172 // Interval creation 173 174 LiveInterval &getOrCreateInterval(unsigned reg) { 175 Reg2IntervalMap::iterator I = r2iMap_.find(reg); 176 if (I == r2iMap_.end()) 177 I = r2iMap_.insert(I, std::make_pair(reg, createInterval(reg))); 178 return I->second; 179 } 180 181 std::vector<LiveInterval*> addIntervalsForSpills(const LiveInterval& i, 182 VirtRegMap& vrm, unsigned reg); 183 184 // Interval removal 185 186 void removeInterval(unsigned Reg) { 187 r2iMap_.erase(Reg); 188 } 189 190 /// isRemoved - returns true if the specified machine instr has been 191 /// removed. 192 bool isRemoved(MachineInstr* instr) const { 193 return !mi2iMap_.count(instr); 194 } 195 196 /// RemoveMachineInstrFromMaps - This marks the specified machine instr as 197 /// deleted. 198 void RemoveMachineInstrFromMaps(MachineInstr *MI) { 199 // remove index -> MachineInstr and 200 // MachineInstr -> index mappings 201 Mi2IndexMap::iterator mi2i = mi2iMap_.find(MI); 202 if (mi2i != mi2iMap_.end()) { 203 i2miMap_[mi2i->second/InstrSlots::NUM] = 0; 204 mi2iMap_.erase(mi2i); 205 } 206 } 207 208 BumpPtrAllocator& getVNInfoAllocator() { return VNInfoAllocator; } 209 210 virtual void getAnalysisUsage(AnalysisUsage &AU) const; 211 virtual void releaseMemory(); 212 213 /// runOnMachineFunction - pass entry point 214 virtual bool runOnMachineFunction(MachineFunction&); 215 216 /// print - Implement the dump method. 217 virtual void print(std::ostream &O, const Module* = 0) const; 218 void print(std::ostream *O, const Module* M = 0) const { 219 if (O) print(*O, M); 220 } 221 222 private: 223 /// computeIntervals - Compute live intervals. 224 void computeIntervals(); 225 226 /// handleRegisterDef - update intervals for a register def 227 /// (calls handlePhysicalRegisterDef and 228 /// handleVirtualRegisterDef) 229 void handleRegisterDef(MachineBasicBlock *MBB, 230 MachineBasicBlock::iterator MI, unsigned MIIdx, 231 unsigned reg); 232 233 /// handleVirtualRegisterDef - update intervals for a virtual 234 /// register def 235 void handleVirtualRegisterDef(MachineBasicBlock *MBB, 236 MachineBasicBlock::iterator MI, 237 unsigned MIIdx, 238 LiveInterval& interval); 239 240 /// handlePhysicalRegisterDef - update intervals for a physical register 241 /// def. 242 void handlePhysicalRegisterDef(MachineBasicBlock* mbb, 243 MachineBasicBlock::iterator mi, 244 unsigned MIIdx, 245 LiveInterval &interval, 246 unsigned SrcReg); 247 248 /// handleLiveInRegister - Create interval for a livein register. 249 void handleLiveInRegister(MachineBasicBlock* mbb, 250 unsigned MIIdx, 251 LiveInterval &interval, bool isAlias = false); 252 253 /// isReMaterializable - Returns true if the definition MI of the specified 254 /// val# of the specified interval is re-materializable. 255 bool isReMaterializable(const LiveInterval &li, const VNInfo *ValNo, 256 MachineInstr *MI); 257 258 /// tryFoldMemoryOperand - Attempts to fold either a spill / restore from 259 /// slot / to reg or any rematerialized load into ith operand of specified 260 /// MI. If it is successul, MI is updated with the newly created MI and 261 /// returns true. 262 bool tryFoldMemoryOperand(MachineInstr* &MI, VirtRegMap &vrm, 263 MachineInstr *DefMI, unsigned index, unsigned i, 264 bool isSS, int slot, unsigned reg); 265 266 static LiveInterval createInterval(unsigned Reg); 267 268 void printRegName(unsigned reg) const; 269 }; 270 271} // End llvm namespace 272 273#endif 274