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