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