LiveIntervalAnalysis.h revision 45f4f2cd0ce90bb83ac043aecb639dc19ffe14a1
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' and 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/MachineBasicBlock.h" 24#include "llvm/CodeGen/MachineFunctionPass.h" 25#include "llvm/CodeGen/LiveInterval.h" 26#include "llvm/CodeGen/SlotIndexes.h" 27#include "llvm/ADT/BitVector.h" 28#include "llvm/ADT/DenseMap.h" 29#include "llvm/ADT/SmallPtrSet.h" 30#include "llvm/ADT/SmallVector.h" 31#include "llvm/Support/Allocator.h" 32#include <cmath> 33#include <iterator> 34 35namespace llvm { 36 37 class AliasAnalysis; 38 class LiveVariables; 39 class MachineLoopInfo; 40 class TargetRegisterInfo; 41 class MachineRegisterInfo; 42 class TargetInstrInfo; 43 class TargetRegisterClass; 44 class VirtRegMap; 45 46 class LiveIntervals : public MachineFunctionPass { 47 MachineFunction* mf_; 48 MachineRegisterInfo* mri_; 49 const TargetMachine* tm_; 50 const TargetRegisterInfo* tri_; 51 const TargetInstrInfo* tii_; 52 AliasAnalysis *aa_; 53 LiveVariables* lv_; 54 SlotIndexes* indexes_; 55 56 /// Special pool allocator for VNInfo's (LiveInterval val#). 57 /// 58 VNInfo::Allocator VNInfoAllocator; 59 60 typedef DenseMap<unsigned, LiveInterval*> Reg2IntervalMap; 61 Reg2IntervalMap r2iMap_; 62 63 /// allocatableRegs_ - A bit vector of allocatable registers. 64 BitVector allocatableRegs_; 65 66 public: 67 static char ID; // Pass identification, replacement for typeid 68 LiveIntervals() : MachineFunctionPass(ID) { 69 initializeLiveIntervalsPass(*PassRegistry::getPassRegistry()); 70 } 71 72 // Calculate the spill weight to assign to a single instruction. 73 static float getSpillWeight(bool isDef, bool isUse, unsigned loopDepth); 74 75 typedef Reg2IntervalMap::iterator iterator; 76 typedef Reg2IntervalMap::const_iterator const_iterator; 77 const_iterator begin() const { return r2iMap_.begin(); } 78 const_iterator end() const { return r2iMap_.end(); } 79 iterator begin() { return r2iMap_.begin(); } 80 iterator end() { return r2iMap_.end(); } 81 unsigned getNumIntervals() const { return (unsigned)r2iMap_.size(); } 82 83 LiveInterval &getInterval(unsigned reg) { 84 Reg2IntervalMap::iterator I = r2iMap_.find(reg); 85 assert(I != r2iMap_.end() && "Interval does not exist for register"); 86 return *I->second; 87 } 88 89 const LiveInterval &getInterval(unsigned reg) const { 90 Reg2IntervalMap::const_iterator I = r2iMap_.find(reg); 91 assert(I != r2iMap_.end() && "Interval does not exist for register"); 92 return *I->second; 93 } 94 95 bool hasInterval(unsigned reg) const { 96 return r2iMap_.count(reg); 97 } 98 99 /// isAllocatable - is the physical register reg allocatable in the current 100 /// function? 101 bool isAllocatable(unsigned reg) const { 102 return allocatableRegs_.test(reg); 103 } 104 105 /// getScaledIntervalSize - get the size of an interval in "units," 106 /// where every function is composed of one thousand units. This 107 /// measure scales properly with empty index slots in the function. 108 double getScaledIntervalSize(LiveInterval& I) { 109 return (1000.0 * I.getSize()) / indexes_->getIndexesLength(); 110 } 111 112 /// getFuncInstructionCount - Return the number of instructions in the 113 /// current function. 114 unsigned getFuncInstructionCount() { 115 return indexes_->getFunctionSize(); 116 } 117 118 /// getApproximateInstructionCount - computes an estimate of the number 119 /// of instructions in a given LiveInterval. 120 unsigned getApproximateInstructionCount(LiveInterval& I) { 121 double IntervalPercentage = getScaledIntervalSize(I) / 1000.0; 122 return (unsigned)(IntervalPercentage * indexes_->getFunctionSize()); 123 } 124 125 // Interval creation 126 LiveInterval &getOrCreateInterval(unsigned reg) { 127 Reg2IntervalMap::iterator I = r2iMap_.find(reg); 128 if (I == r2iMap_.end()) 129 I = r2iMap_.insert(std::make_pair(reg, createInterval(reg))).first; 130 return *I->second; 131 } 132 133 /// dupInterval - Duplicate a live interval. The caller is responsible for 134 /// managing the allocated memory. 135 LiveInterval *dupInterval(LiveInterval *li); 136 137 /// addLiveRangeToEndOfBlock - Given a register and an instruction, 138 /// adds a live range from that instruction to the end of its MBB. 139 LiveRange addLiveRangeToEndOfBlock(unsigned reg, 140 MachineInstr* startInst); 141 142 /// shrinkToUses - After removing some uses of a register, shrink its live 143 /// range to just the remaining uses. This method does not compute reaching 144 /// defs for new uses, and it doesn't remove dead defs. 145 /// Dead PHIDef values are marked as unused. 146 /// New dead machine instructions are added to the dead vector. 147 /// Return true if the interval may have been separated into multiple 148 /// connected components. 149 bool shrinkToUses(LiveInterval *li, 150 SmallVectorImpl<MachineInstr*> *dead = 0); 151 152 // Interval removal 153 154 void removeInterval(unsigned Reg) { 155 DenseMap<unsigned, LiveInterval*>::iterator I = r2iMap_.find(Reg); 156 delete I->second; 157 r2iMap_.erase(I); 158 } 159 160 SlotIndexes *getSlotIndexes() const { 161 return indexes_; 162 } 163 164 /// isNotInMIMap - returns true if the specified machine instr has been 165 /// removed or was never entered in the map. 166 bool isNotInMIMap(const MachineInstr* Instr) const { 167 return !indexes_->hasIndex(Instr); 168 } 169 170 /// Returns the base index of the given instruction. 171 SlotIndex getInstructionIndex(const MachineInstr *instr) const { 172 return indexes_->getInstructionIndex(instr); 173 } 174 175 /// Returns the instruction associated with the given index. 176 MachineInstr* getInstructionFromIndex(SlotIndex index) const { 177 return indexes_->getInstructionFromIndex(index); 178 } 179 180 /// Return the first index in the given basic block. 181 SlotIndex getMBBStartIdx(const MachineBasicBlock *mbb) const { 182 return indexes_->getMBBStartIdx(mbb); 183 } 184 185 /// Return the last index in the given basic block. 186 SlotIndex getMBBEndIdx(const MachineBasicBlock *mbb) const { 187 return indexes_->getMBBEndIdx(mbb); 188 } 189 190 bool isLiveInToMBB(const LiveInterval &li, 191 const MachineBasicBlock *mbb) const { 192 return li.liveAt(getMBBStartIdx(mbb)); 193 } 194 195 bool isLiveOutOfMBB(const LiveInterval &li, 196 const MachineBasicBlock *mbb) const { 197 return li.liveAt(getMBBEndIdx(mbb).getPrevSlot()); 198 } 199 200 MachineBasicBlock* getMBBFromIndex(SlotIndex index) const { 201 return indexes_->getMBBFromIndex(index); 202 } 203 204 SlotIndex InsertMachineInstrInMaps(MachineInstr *MI) { 205 return indexes_->insertMachineInstrInMaps(MI); 206 } 207 208 void RemoveMachineInstrFromMaps(MachineInstr *MI) { 209 indexes_->removeMachineInstrFromMaps(MI); 210 } 211 212 void ReplaceMachineInstrInMaps(MachineInstr *MI, MachineInstr *NewMI) { 213 indexes_->replaceMachineInstrInMaps(MI, NewMI); 214 } 215 216 bool findLiveInMBBs(SlotIndex Start, SlotIndex End, 217 SmallVectorImpl<MachineBasicBlock*> &MBBs) const { 218 return indexes_->findLiveInMBBs(Start, End, MBBs); 219 } 220 221 VNInfo::Allocator& getVNInfoAllocator() { return VNInfoAllocator; } 222 223 virtual void getAnalysisUsage(AnalysisUsage &AU) const; 224 virtual void releaseMemory(); 225 226 /// runOnMachineFunction - pass entry point 227 virtual bool runOnMachineFunction(MachineFunction&); 228 229 /// print - Implement the dump method. 230 virtual void print(raw_ostream &O, const Module* = 0) const; 231 232 /// isReMaterializable - Returns true if every definition of MI of every 233 /// val# of the specified interval is re-materializable. Also returns true 234 /// by reference if all of the defs are load instructions. 235 bool isReMaterializable(const LiveInterval &li, 236 const SmallVectorImpl<LiveInterval*> *SpillIs, 237 bool &isLoad); 238 239 /// intervalIsInOneMBB - Returns true if the specified interval is entirely 240 /// within a single basic block. 241 bool intervalIsInOneMBB(const LiveInterval &li) const; 242 243 /// addKillFlags - Add kill flags to any instruction that kills a virtual 244 /// register. 245 void addKillFlags(); 246 247 /// moveInstr - Move MachineInstr mi to insertPt, updating the live 248 /// intervals of mi's operands to reflect the new position. The insertion 249 /// point can be above or below mi, but must be in the same basic block. 250 void moveInstr(MachineBasicBlock::iterator insertPt, MachineInstr* mi); 251 252 private: 253 /// computeIntervals - Compute live intervals. 254 void computeIntervals(); 255 256 /// handleRegisterDef - update intervals for a register def 257 /// (calls handlePhysicalRegisterDef and 258 /// handleVirtualRegisterDef) 259 void handleRegisterDef(MachineBasicBlock *MBB, 260 MachineBasicBlock::iterator MI, 261 SlotIndex MIIdx, 262 MachineOperand& MO, unsigned MOIdx); 263 264 /// isPartialRedef - Return true if the specified def at the specific index 265 /// is partially re-defining the specified live interval. A common case of 266 /// this is a definition of the sub-register. 267 bool isPartialRedef(SlotIndex MIIdx, MachineOperand &MO, 268 LiveInterval &interval); 269 270 /// handleVirtualRegisterDef - update intervals for a virtual 271 /// register def 272 void handleVirtualRegisterDef(MachineBasicBlock *MBB, 273 MachineBasicBlock::iterator MI, 274 SlotIndex MIIdx, MachineOperand& MO, 275 unsigned MOIdx, 276 LiveInterval& interval); 277 278 /// handlePhysicalRegisterDef - update intervals for a physical register 279 /// def. 280 void handlePhysicalRegisterDef(MachineBasicBlock* mbb, 281 MachineBasicBlock::iterator mi, 282 SlotIndex MIIdx, MachineOperand& MO, 283 LiveInterval &interval); 284 285 /// handleLiveInRegister - Create interval for a livein register. 286 void handleLiveInRegister(MachineBasicBlock* mbb, 287 SlotIndex MIIdx, 288 LiveInterval &interval, bool isAlias = false); 289 290 /// getReMatImplicitUse - If the remat definition MI has one (for now, we 291 /// only allow one) virtual register operand, then its uses are implicitly 292 /// using the register. Returns the virtual register. 293 unsigned getReMatImplicitUse(const LiveInterval &li, 294 MachineInstr *MI) const; 295 296 /// isValNoAvailableAt - Return true if the val# of the specified interval 297 /// which reaches the given instruction also reaches the specified use 298 /// index. 299 bool isValNoAvailableAt(const LiveInterval &li, MachineInstr *MI, 300 SlotIndex UseIdx) const; 301 302 /// isReMaterializable - Returns true if the definition MI of the specified 303 /// val# of the specified interval is re-materializable. Also returns true 304 /// by reference if the def is a load. 305 bool isReMaterializable(const LiveInterval &li, const VNInfo *ValNo, 306 MachineInstr *MI, 307 const SmallVectorImpl<LiveInterval*> *SpillIs, 308 bool &isLoad); 309 310 static LiveInterval* createInterval(unsigned Reg); 311 312 void printInstrs(raw_ostream &O) const; 313 void dumpInstrs() const; 314 }; 315} // End llvm namespace 316 317#endif 318