LiveIntervalAnalysis.h revision 84bc5427d6883f73cfeae3da640acd011d35c006
1//===-- LiveIntervalAnalysis.h - Live Interval Analysis ---------*- C++ -*-===// 2// 3// The LLVM Compiler Infrastructure 4// 5// This file is distributed under the University of Illinois Open Source 6// 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 MachineLoopInfo; 36 class MRegisterInfo; 37 class MachineRegisterInfo; 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 MachineLoopInfo *loopInfo, VirtRegMap& vrm); 235 236 /// isReMaterializable - Returns true if every definition of MI of every 237 /// val# of the specified interval is re-materializable. Also returns true 238 /// by reference if all of the defs are load instructions. 239 bool isReMaterializable(const LiveInterval &li, bool &isLoad); 240 241 private: 242 /// computeIntervals - Compute live intervals. 243 void computeIntervals(); 244 245 /// handleRegisterDef - update intervals for a register def 246 /// (calls handlePhysicalRegisterDef and 247 /// handleVirtualRegisterDef) 248 void handleRegisterDef(MachineBasicBlock *MBB, 249 MachineBasicBlock::iterator MI, unsigned MIIdx, 250 unsigned reg); 251 252 /// handleVirtualRegisterDef - update intervals for a virtual 253 /// register def 254 void handleVirtualRegisterDef(MachineBasicBlock *MBB, 255 MachineBasicBlock::iterator MI, 256 unsigned MIIdx, 257 LiveInterval& interval); 258 259 /// handlePhysicalRegisterDef - update intervals for a physical register 260 /// def. 261 void handlePhysicalRegisterDef(MachineBasicBlock* mbb, 262 MachineBasicBlock::iterator mi, 263 unsigned MIIdx, 264 LiveInterval &interval, 265 unsigned SrcReg); 266 267 /// handleLiveInRegister - Create interval for a livein register. 268 void handleLiveInRegister(MachineBasicBlock* mbb, 269 unsigned MIIdx, 270 LiveInterval &interval, bool isAlias = false); 271 272 /// isReMaterializable - Returns true if the definition MI of the specified 273 /// val# of the specified interval is re-materializable. Also returns true 274 /// by reference if the def is a load. 275 bool isReMaterializable(const LiveInterval &li, const VNInfo *ValNo, 276 MachineInstr *MI, bool &isLoad); 277 278 /// tryFoldMemoryOperand - Attempts to fold either a spill / restore from 279 /// slot / to reg or any rematerialized load into ith operand of specified 280 /// MI. If it is successul, MI is updated with the newly created MI and 281 /// returns true. 282 bool tryFoldMemoryOperand(MachineInstr* &MI, VirtRegMap &vrm, 283 MachineInstr *DefMI, unsigned InstrIdx, 284 SmallVector<unsigned, 2> &Ops, 285 bool isSS, int Slot, unsigned Reg); 286 287 /// canFoldMemoryOperand - Returns true if the specified load / store 288 /// folding is possible. 289 bool canFoldMemoryOperand(MachineInstr *MI, 290 SmallVector<unsigned, 2> &Ops) const; 291 292 /// anyKillInMBBAfterIdx - Returns true if there is a kill of the specified 293 /// VNInfo that's after the specified index but is within the basic block. 294 bool anyKillInMBBAfterIdx(const LiveInterval &li, const VNInfo *VNI, 295 MachineBasicBlock *MBB, unsigned Idx) const; 296 297 /// intervalIsInOneMBB - Returns true if the specified interval is entirely 298 /// within a single basic block. 299 bool intervalIsInOneMBB(const LiveInterval &li) const; 300 301 /// SRInfo - Spill / restore info. 302 struct SRInfo { 303 int index; 304 unsigned vreg; 305 bool canFold; 306 SRInfo(int i, unsigned vr, bool f) : index(i), vreg(vr), canFold(f) {}; 307 }; 308 309 bool alsoFoldARestore(int Id, int index, unsigned vr, 310 BitVector &RestoreMBBs, 311 std::map<unsigned,std::vector<SRInfo> >&RestoreIdxes); 312 void eraseRestoreInfo(int Id, int index, unsigned vr, 313 BitVector &RestoreMBBs, 314 std::map<unsigned,std::vector<SRInfo> >&RestoreIdxes); 315 316 /// rewriteInstructionForSpills, rewriteInstructionsForSpills - Helper 317 /// functions for addIntervalsForSpills to rewrite uses / defs for the given 318 /// live range. 319 bool rewriteInstructionForSpills(const LiveInterval &li, bool TrySplit, 320 unsigned id, unsigned index, unsigned end, MachineInstr *MI, 321 MachineInstr *OrigDefMI, MachineInstr *DefMI, unsigned Slot, int LdSlot, 322 bool isLoad, bool isLoadSS, bool DefIsReMat, bool CanDelete, 323 VirtRegMap &vrm, MachineRegisterInfo &RegMap, 324 const TargetRegisterClass* rc, 325 SmallVector<int, 4> &ReMatIds, 326 unsigned &NewVReg, bool &HasDef, bool &HasUse, 327 const MachineLoopInfo *loopInfo, 328 std::map<unsigned,unsigned> &MBBVRegsMap, 329 std::vector<LiveInterval*> &NewLIs); 330 void rewriteInstructionsForSpills(const LiveInterval &li, bool TrySplit, 331 LiveInterval::Ranges::const_iterator &I, 332 MachineInstr *OrigDefMI, MachineInstr *DefMI, unsigned Slot, int LdSlot, 333 bool isLoad, bool isLoadSS, bool DefIsReMat, bool CanDelete, 334 VirtRegMap &vrm, MachineRegisterInfo &RegMap, 335 const TargetRegisterClass* rc, 336 SmallVector<int, 4> &ReMatIds, const MachineLoopInfo *loopInfo, 337 BitVector &SpillMBBs, 338 std::map<unsigned,std::vector<SRInfo> > &SpillIdxes, 339 BitVector &RestoreMBBs, 340 std::map<unsigned,std::vector<SRInfo> > &RestoreIdxes, 341 std::map<unsigned,unsigned> &MBBVRegsMap, 342 std::vector<LiveInterval*> &NewLIs); 343 344 static LiveInterval createInterval(unsigned Reg); 345 346 void printRegName(unsigned reg) const; 347 }; 348 349} // End llvm namespace 350 351#endif 352