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 35 namespace 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 /// conflictsWithPhysReg - Returns true if the specified register is used or 129 /// defined during the duration of the specified interval. Copies to and 130 /// from li.reg are allowed. This method is only able to analyze simple 131 /// ranges that stay within a single basic block. Anything else is 132 /// considered a conflict. 133 bool conflictsWithPhysReg(const LiveInterval &li, VirtRegMap &vrm, 134 unsigned reg); 135 136 /// conflictsWithAliasRef - Similar to conflictsWithPhysRegRef except 137 /// it checks for alias uses and defs. 138 bool conflictsWithAliasRef(LiveInterval &li, unsigned Reg, 139 SmallPtrSet<MachineInstr*,32> &JoinedCopies); 140 141 // Interval creation 142 LiveInterval &getOrCreateInterval(unsigned reg) { 143 Reg2IntervalMap::iterator I = r2iMap_.find(reg); 144 if (I == r2iMap_.end()) 145 I = r2iMap_.insert(std::make_pair(reg, createInterval(reg))).first; 146 return *I->second; 147 } 148 149 /// dupInterval - Duplicate a live interval. The caller is responsible for 150 /// managing the allocated memory. 151 LiveInterval *dupInterval(LiveInterval *li); 152 153 /// addLiveRangeToEndOfBlock - Given a register and an instruction, 154 /// adds a live range from that instruction to the end of its MBB. 155 LiveRange addLiveRangeToEndOfBlock(unsigned reg, 156 MachineInstr* startInst); 157 158 /// shrinkToUses - After removing some uses of a register, shrink its live 159 /// range to just the remaining uses. This method does not compute reaching 160 /// defs for new uses, and it doesn't remove dead defs. 161 /// Dead PHIDef values are marked as unused. 162 /// New dead machine instructions are added to the dead vector. 163 /// Return true if the interval may have been separated into multiple 164 /// connected components. 165 bool shrinkToUses(LiveInterval *li, 166 SmallVectorImpl<MachineInstr*> *dead = 0); 167 168 // Interval removal 169 170 void removeInterval(unsigned Reg) { 171 DenseMap<unsigned, LiveInterval*>::iterator I = r2iMap_.find(Reg); 172 delete I->second; 173 r2iMap_.erase(I); 174 } 175 176 SlotIndexes *getSlotIndexes() const { 177 return indexes_; 178 } 179 180 SlotIndex getZeroIndex() const { 181 return indexes_->getZeroIndex(); 182 } 183 184 SlotIndex getInvalidIndex() const { 185 return indexes_->getInvalidIndex(); 186 } 187 188 /// isNotInMIMap - returns true if the specified machine instr has been 189 /// removed or was never entered in the map. 190 bool isNotInMIMap(const MachineInstr* Instr) const { 191 return !indexes_->hasIndex(Instr); 192 } 193 194 /// Returns the base index of the given instruction. 195 SlotIndex getInstructionIndex(const MachineInstr *instr) const { 196 return indexes_->getInstructionIndex(instr); 197 } 198 199 /// Returns the instruction associated with the given index. 200 MachineInstr* getInstructionFromIndex(SlotIndex index) const { 201 return indexes_->getInstructionFromIndex(index); 202 } 203 204 /// Return the first index in the given basic block. 205 SlotIndex getMBBStartIdx(const MachineBasicBlock *mbb) const { 206 return indexes_->getMBBStartIdx(mbb); 207 } 208 209 /// Return the last index in the given basic block. 210 SlotIndex getMBBEndIdx(const MachineBasicBlock *mbb) const { 211 return indexes_->getMBBEndIdx(mbb); 212 } 213 214 bool isLiveInToMBB(const LiveInterval &li, 215 const MachineBasicBlock *mbb) const { 216 return li.liveAt(getMBBStartIdx(mbb)); 217 } 218 219 LiveRange* findEnteringRange(LiveInterval &li, 220 const MachineBasicBlock *mbb) { 221 return li.getLiveRangeContaining(getMBBStartIdx(mbb)); 222 } 223 224 bool isLiveOutOfMBB(const LiveInterval &li, 225 const MachineBasicBlock *mbb) const { 226 return li.liveAt(getMBBEndIdx(mbb).getPrevSlot()); 227 } 228 229 LiveRange* findExitingRange(LiveInterval &li, 230 const MachineBasicBlock *mbb) { 231 return li.getLiveRangeContaining(getMBBEndIdx(mbb).getPrevSlot()); 232 } 233 234 MachineBasicBlock* getMBBFromIndex(SlotIndex index) const { 235 return indexes_->getMBBFromIndex(index); 236 } 237 238 SlotIndex InsertMachineInstrInMaps(MachineInstr *MI) { 239 return indexes_->insertMachineInstrInMaps(MI); 240 } 241 242 void RemoveMachineInstrFromMaps(MachineInstr *MI) { 243 indexes_->removeMachineInstrFromMaps(MI); 244 } 245 246 void ReplaceMachineInstrInMaps(MachineInstr *MI, MachineInstr *NewMI) { 247 indexes_->replaceMachineInstrInMaps(MI, NewMI); 248 } 249 250 void InsertMBBInMaps(MachineBasicBlock *MBB) { 251 indexes_->insertMBBInMaps(MBB); 252 } 253 254 bool findLiveInMBBs(SlotIndex Start, SlotIndex End, 255 SmallVectorImpl<MachineBasicBlock*> &MBBs) const { 256 return indexes_->findLiveInMBBs(Start, End, MBBs); 257 } 258 259 void renumber() { 260 indexes_->renumberIndexes(); 261 } 262 263 VNInfo::Allocator& getVNInfoAllocator() { return VNInfoAllocator; } 264 265 virtual void getAnalysisUsage(AnalysisUsage &AU) const; 266 virtual void releaseMemory(); 267 268 /// runOnMachineFunction - pass entry point 269 virtual bool runOnMachineFunction(MachineFunction&); 270 271 /// print - Implement the dump method. 272 virtual void print(raw_ostream &O, const Module* = 0) const; 273 274 /// addIntervalsForSpills - Create new intervals for spilled defs / uses of 275 /// the given interval. FIXME: It also returns the weight of the spill slot 276 /// (if any is created) by reference. This is temporary. 277 std::vector<LiveInterval*> 278 addIntervalsForSpills(const LiveInterval& i, 279 const SmallVectorImpl<LiveInterval*> *SpillIs, 280 const MachineLoopInfo *loopInfo, VirtRegMap& vrm); 281 282 /// spillPhysRegAroundRegDefsUses - Spill the specified physical register 283 /// around all defs and uses of the specified interval. Return true if it 284 /// was able to cut its interval. 285 bool spillPhysRegAroundRegDefsUses(const LiveInterval &li, 286 unsigned PhysReg, VirtRegMap &vrm); 287 288 /// isReMaterializable - Returns true if every definition of MI of every 289 /// val# of the specified interval is re-materializable. Also returns true 290 /// by reference if all of the defs are load instructions. 291 bool isReMaterializable(const LiveInterval &li, 292 const SmallVectorImpl<LiveInterval*> *SpillIs, 293 bool &isLoad); 294 295 /// isReMaterializable - Returns true if the definition MI of the specified 296 /// val# of the specified interval is re-materializable. 297 bool isReMaterializable(const LiveInterval &li, const VNInfo *ValNo, 298 MachineInstr *MI); 299 300 /// getRepresentativeReg - Find the largest super register of the specified 301 /// physical register. 302 unsigned getRepresentativeReg(unsigned Reg) const; 303 304 /// getNumConflictsWithPhysReg - Return the number of uses and defs of the 305 /// specified interval that conflicts with the specified physical register. 306 unsigned getNumConflictsWithPhysReg(const LiveInterval &li, 307 unsigned PhysReg) const; 308 309 /// intervalIsInOneMBB - Returns true if the specified interval is entirely 310 /// within a single basic block. 311 bool intervalIsInOneMBB(const LiveInterval &li) const; 312 313 /// getLastSplitPoint - Return the last possible insertion point in mbb for 314 /// spilling and splitting code. This is the first terminator, or the call 315 /// instruction if li is live into a landing pad successor. 316 MachineBasicBlock::iterator getLastSplitPoint(const LiveInterval &li, 317 MachineBasicBlock *mbb) const; 318 319 /// addKillFlags - Add kill flags to any instruction that kills a virtual 320 /// register. 321 void addKillFlags(); 322 323 private: 324 /// computeIntervals - Compute live intervals. 325 void computeIntervals(); 326 327 /// handleRegisterDef - update intervals for a register def 328 /// (calls handlePhysicalRegisterDef and 329 /// handleVirtualRegisterDef) 330 void handleRegisterDef(MachineBasicBlock *MBB, 331 MachineBasicBlock::iterator MI, 332 SlotIndex MIIdx, 333 MachineOperand& MO, unsigned MOIdx); 334 335 /// isPartialRedef - Return true if the specified def at the specific index 336 /// is partially re-defining the specified live interval. A common case of 337 /// this is a definition of the sub-register. 338 bool isPartialRedef(SlotIndex MIIdx, MachineOperand &MO, 339 LiveInterval &interval); 340 341 /// handleVirtualRegisterDef - update intervals for a virtual 342 /// register def 343 void handleVirtualRegisterDef(MachineBasicBlock *MBB, 344 MachineBasicBlock::iterator MI, 345 SlotIndex MIIdx, MachineOperand& MO, 346 unsigned MOIdx, 347 LiveInterval& interval); 348 349 /// handlePhysicalRegisterDef - update intervals for a physical register 350 /// def. 351 void handlePhysicalRegisterDef(MachineBasicBlock* mbb, 352 MachineBasicBlock::iterator mi, 353 SlotIndex MIIdx, MachineOperand& MO, 354 LiveInterval &interval, 355 MachineInstr *CopyMI); 356 357 /// handleLiveInRegister - Create interval for a livein register. 358 void handleLiveInRegister(MachineBasicBlock* mbb, 359 SlotIndex MIIdx, 360 LiveInterval &interval, bool isAlias = false); 361 362 /// getReMatImplicitUse - If the remat definition MI has one (for now, we 363 /// only allow one) virtual register operand, then its uses are implicitly 364 /// using the register. Returns the virtual register. 365 unsigned getReMatImplicitUse(const LiveInterval &li, 366 MachineInstr *MI) const; 367 368 /// isValNoAvailableAt - Return true if the val# of the specified interval 369 /// which reaches the given instruction also reaches the specified use 370 /// index. 371 bool isValNoAvailableAt(const LiveInterval &li, MachineInstr *MI, 372 SlotIndex UseIdx) const; 373 374 /// isReMaterializable - Returns true if the definition MI of the specified 375 /// val# of the specified interval is re-materializable. Also returns true 376 /// by reference if the def is a load. 377 bool isReMaterializable(const LiveInterval &li, const VNInfo *ValNo, 378 MachineInstr *MI, 379 const SmallVectorImpl<LiveInterval*> *SpillIs, 380 bool &isLoad); 381 382 /// tryFoldMemoryOperand - Attempts to fold either a spill / restore from 383 /// slot / to reg or any rematerialized load into ith operand of specified 384 /// MI. If it is successul, MI is updated with the newly created MI and 385 /// returns true. 386 bool tryFoldMemoryOperand(MachineInstr* &MI, VirtRegMap &vrm, 387 MachineInstr *DefMI, SlotIndex InstrIdx, 388 SmallVector<unsigned, 2> &Ops, 389 bool isSS, int FrameIndex, unsigned Reg); 390 391 /// canFoldMemoryOperand - Return true if the specified load / store 392 /// folding is possible. 393 bool canFoldMemoryOperand(MachineInstr *MI, 394 SmallVector<unsigned, 2> &Ops, 395 bool ReMatLoadSS) const; 396 397 /// anyKillInMBBAfterIdx - Returns true if there is a kill of the specified 398 /// VNInfo that's after the specified index but is within the basic block. 399 bool anyKillInMBBAfterIdx(const LiveInterval &li, const VNInfo *VNI, 400 MachineBasicBlock *MBB, 401 SlotIndex Idx) const; 402 403 /// hasAllocatableSuperReg - Return true if the specified physical register 404 /// has any super register that's allocatable. 405 bool hasAllocatableSuperReg(unsigned Reg) const; 406 407 /// SRInfo - Spill / restore info. 408 struct SRInfo { 409 SlotIndex index; 410 unsigned vreg; 411 bool canFold; 412 SRInfo(SlotIndex i, unsigned vr, bool f) 413 : index(i), vreg(vr), canFold(f) {} 414 }; 415 416 bool alsoFoldARestore(int Id, SlotIndex index, unsigned vr, 417 BitVector &RestoreMBBs, 418 DenseMap<unsigned,std::vector<SRInfo> >&RestoreIdxes); 419 void eraseRestoreInfo(int Id, SlotIndex index, unsigned vr, 420 BitVector &RestoreMBBs, 421 DenseMap<unsigned,std::vector<SRInfo> >&RestoreIdxes); 422 423 /// handleSpilledImpDefs - Remove IMPLICIT_DEF instructions which are being 424 /// spilled and create empty intervals for their uses. 425 void handleSpilledImpDefs(const LiveInterval &li, VirtRegMap &vrm, 426 const TargetRegisterClass* rc, 427 std::vector<LiveInterval*> &NewLIs); 428 429 /// rewriteImplicitOps - Rewrite implicit use operands of MI (i.e. uses of 430 /// interval on to-be re-materialized operands of MI) with new register. 431 void rewriteImplicitOps(const LiveInterval &li, 432 MachineInstr *MI, unsigned NewVReg, VirtRegMap &vrm); 433 434 /// rewriteInstructionForSpills, rewriteInstructionsForSpills - Helper 435 /// functions for addIntervalsForSpills to rewrite uses / defs for the given 436 /// live range. 437 bool rewriteInstructionForSpills(const LiveInterval &li, const VNInfo *VNI, 438 bool TrySplit, SlotIndex index, SlotIndex end, 439 MachineInstr *MI, MachineInstr *OrigDefMI, MachineInstr *DefMI, 440 unsigned Slot, int LdSlot, 441 bool isLoad, bool isLoadSS, bool DefIsReMat, bool CanDelete, 442 VirtRegMap &vrm, const TargetRegisterClass* rc, 443 SmallVector<int, 4> &ReMatIds, const MachineLoopInfo *loopInfo, 444 unsigned &NewVReg, unsigned ImpUse, bool &HasDef, bool &HasUse, 445 DenseMap<unsigned,unsigned> &MBBVRegsMap, 446 std::vector<LiveInterval*> &NewLIs); 447 void rewriteInstructionsForSpills(const LiveInterval &li, bool TrySplit, 448 LiveInterval::Ranges::const_iterator &I, 449 MachineInstr *OrigDefMI, MachineInstr *DefMI, unsigned Slot, int LdSlot, 450 bool isLoad, bool isLoadSS, bool DefIsReMat, bool CanDelete, 451 VirtRegMap &vrm, const TargetRegisterClass* rc, 452 SmallVector<int, 4> &ReMatIds, const MachineLoopInfo *loopInfo, 453 BitVector &SpillMBBs, 454 DenseMap<unsigned,std::vector<SRInfo> > &SpillIdxes, 455 BitVector &RestoreMBBs, 456 DenseMap<unsigned,std::vector<SRInfo> > &RestoreIdxes, 457 DenseMap<unsigned,unsigned> &MBBVRegsMap, 458 std::vector<LiveInterval*> &NewLIs); 459 460 static LiveInterval* createInterval(unsigned Reg); 461 462 void printInstrs(raw_ostream &O) const; 463 void dumpInstrs() const; 464 }; 465 } // End llvm namespace 466 467 #endif 468
