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/Target/TargetRegisterInfo.h" 24 #include "llvm/CodeGen/MachineBasicBlock.h" 25 #include "llvm/CodeGen/MachineFunctionPass.h" 26 #include "llvm/CodeGen/LiveInterval.h" 27 #include "llvm/CodeGen/SlotIndexes.h" 28 #include "llvm/ADT/BitVector.h" 29 #include "llvm/ADT/IndexedMap.h" 30 #include "llvm/ADT/SmallPtrSet.h" 31 #include "llvm/ADT/SmallVector.h" 32 #include "llvm/Support/Allocator.h" 33 #include <cmath> 34 #include <iterator> 35 36 namespace llvm { 37 38 class AliasAnalysis; 39 class LiveRangeCalc; 40 class LiveVariables; 41 class MachineDominatorTree; 42 class MachineLoopInfo; 43 class TargetRegisterInfo; 44 class MachineRegisterInfo; 45 class TargetInstrInfo; 46 class TargetRegisterClass; 47 class VirtRegMap; 48 49 class LiveIntervals : public MachineFunctionPass { 50 MachineFunction* MF; 51 MachineRegisterInfo* MRI; 52 const TargetMachine* TM; 53 const TargetRegisterInfo* TRI; 54 const TargetInstrInfo* TII; 55 AliasAnalysis *AA; 56 LiveVariables* LV; 57 SlotIndexes* Indexes; 58 MachineDominatorTree *DomTree; 59 LiveRangeCalc *LRCalc; 60 61 /// Special pool allocator for VNInfo's (LiveInterval val#). 62 /// 63 VNInfo::Allocator VNInfoAllocator; 64 65 /// Live interval pointers for all the virtual registers. 66 IndexedMap<LiveInterval*, VirtReg2IndexFunctor> VirtRegIntervals; 67 68 /// AllocatableRegs - A bit vector of allocatable registers. 69 BitVector AllocatableRegs; 70 71 /// ReservedRegs - A bit vector of reserved registers. 72 BitVector ReservedRegs; 73 74 /// RegMaskSlots - Sorted list of instructions with register mask operands. 75 /// Always use the 'r' slot, RegMasks are normal clobbers, not early 76 /// clobbers. 77 SmallVector<SlotIndex, 8> RegMaskSlots; 78 79 /// RegMaskBits - This vector is parallel to RegMaskSlots, it holds a 80 /// pointer to the corresponding register mask. This pointer can be 81 /// recomputed as: 82 /// 83 /// MI = Indexes->getInstructionFromIndex(RegMaskSlot[N]); 84 /// unsigned OpNum = findRegMaskOperand(MI); 85 /// RegMaskBits[N] = MI->getOperand(OpNum).getRegMask(); 86 /// 87 /// This is kept in a separate vector partly because some standard 88 /// libraries don't support lower_bound() with mixed objects, partly to 89 /// improve locality when searching in RegMaskSlots. 90 /// Also see the comment in LiveInterval::find(). 91 SmallVector<const uint32_t*, 8> RegMaskBits; 92 93 /// For each basic block number, keep (begin, size) pairs indexing into the 94 /// RegMaskSlots and RegMaskBits arrays. 95 /// Note that basic block numbers may not be layout contiguous, that's why 96 /// we can't just keep track of the first register mask in each basic 97 /// block. 98 SmallVector<std::pair<unsigned, unsigned>, 8> RegMaskBlocks; 99 100 /// RegUnitIntervals - Keep a live interval for each register unit as a way 101 /// of tracking fixed physreg interference. 102 SmallVector<LiveInterval*, 0> RegUnitIntervals; 103 104 public: 105 static char ID; // Pass identification, replacement for typeid 106 LiveIntervals(); 107 virtual ~LiveIntervals(); 108 109 // Calculate the spill weight to assign to a single instruction. 110 static float getSpillWeight(bool isDef, bool isUse, unsigned loopDepth); 111 112 LiveInterval &getInterval(unsigned Reg) { 113 LiveInterval *LI = VirtRegIntervals[Reg]; 114 assert(LI && "Interval does not exist for virtual register"); 115 return *LI; 116 } 117 118 const LiveInterval &getInterval(unsigned Reg) const { 119 return const_cast<LiveIntervals*>(this)->getInterval(Reg); 120 } 121 122 bool hasInterval(unsigned Reg) const { 123 return VirtRegIntervals.inBounds(Reg) && VirtRegIntervals[Reg]; 124 } 125 126 /// isAllocatable - is the physical register reg allocatable in the current 127 /// function? 128 bool isAllocatable(unsigned reg) const { 129 return AllocatableRegs.test(reg); 130 } 131 132 /// isReserved - is the physical register reg reserved in the current 133 /// function 134 bool isReserved(unsigned reg) const { 135 return ReservedRegs.test(reg); 136 } 137 138 // Interval creation. 139 LiveInterval &getOrCreateInterval(unsigned Reg) { 140 if (!hasInterval(Reg)) { 141 VirtRegIntervals.grow(Reg); 142 VirtRegIntervals[Reg] = createInterval(Reg); 143 } 144 return getInterval(Reg); 145 } 146 147 // Interval removal. 148 void removeInterval(unsigned Reg) { 149 delete VirtRegIntervals[Reg]; 150 VirtRegIntervals[Reg] = 0; 151 } 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 SlotIndexes *getSlotIndexes() const { 169 return Indexes; 170 } 171 172 AliasAnalysis *getAliasAnalysis() const { 173 return AA; 174 } 175 176 /// isNotInMIMap - returns true if the specified machine instr has been 177 /// removed or was never entered in the map. 178 bool isNotInMIMap(const MachineInstr* Instr) const { 179 return !Indexes->hasIndex(Instr); 180 } 181 182 /// Returns the base index of the given instruction. 183 SlotIndex getInstructionIndex(const MachineInstr *instr) const { 184 return Indexes->getInstructionIndex(instr); 185 } 186 187 /// Returns the instruction associated with the given index. 188 MachineInstr* getInstructionFromIndex(SlotIndex index) const { 189 return Indexes->getInstructionFromIndex(index); 190 } 191 192 /// Return the first index in the given basic block. 193 SlotIndex getMBBStartIdx(const MachineBasicBlock *mbb) const { 194 return Indexes->getMBBStartIdx(mbb); 195 } 196 197 /// Return the last index in the given basic block. 198 SlotIndex getMBBEndIdx(const MachineBasicBlock *mbb) const { 199 return Indexes->getMBBEndIdx(mbb); 200 } 201 202 bool isLiveInToMBB(const LiveInterval &li, 203 const MachineBasicBlock *mbb) const { 204 return li.liveAt(getMBBStartIdx(mbb)); 205 } 206 207 bool isLiveOutOfMBB(const LiveInterval &li, 208 const MachineBasicBlock *mbb) const { 209 return li.liveAt(getMBBEndIdx(mbb).getPrevSlot()); 210 } 211 212 MachineBasicBlock* getMBBFromIndex(SlotIndex index) const { 213 return Indexes->getMBBFromIndex(index); 214 } 215 216 SlotIndex InsertMachineInstrInMaps(MachineInstr *MI) { 217 return Indexes->insertMachineInstrInMaps(MI); 218 } 219 220 void RemoveMachineInstrFromMaps(MachineInstr *MI) { 221 Indexes->removeMachineInstrFromMaps(MI); 222 } 223 224 void ReplaceMachineInstrInMaps(MachineInstr *MI, MachineInstr *NewMI) { 225 Indexes->replaceMachineInstrInMaps(MI, NewMI); 226 } 227 228 bool findLiveInMBBs(SlotIndex Start, SlotIndex End, 229 SmallVectorImpl<MachineBasicBlock*> &MBBs) const { 230 return Indexes->findLiveInMBBs(Start, End, MBBs); 231 } 232 233 VNInfo::Allocator& getVNInfoAllocator() { return VNInfoAllocator; } 234 235 virtual void getAnalysisUsage(AnalysisUsage &AU) const; 236 virtual void releaseMemory(); 237 238 /// runOnMachineFunction - pass entry point 239 virtual bool runOnMachineFunction(MachineFunction&); 240 241 /// print - Implement the dump method. 242 virtual void print(raw_ostream &O, const Module* = 0) const; 243 244 /// intervalIsInOneMBB - If LI is confined to a single basic block, return 245 /// a pointer to that block. If LI is live in to or out of any block, 246 /// return NULL. 247 MachineBasicBlock *intervalIsInOneMBB(const LiveInterval &LI) const; 248 249 /// Returns true if VNI is killed by any PHI-def values in LI. 250 /// This may conservatively return true to avoid expensive computations. 251 bool hasPHIKill(const LiveInterval &LI, const VNInfo *VNI) const; 252 253 /// addKillFlags - Add kill flags to any instruction that kills a virtual 254 /// register. 255 void addKillFlags(const VirtRegMap*); 256 257 /// handleMove - call this method to notify LiveIntervals that 258 /// instruction 'mi' has been moved within a basic block. This will update 259 /// the live intervals for all operands of mi. Moves between basic blocks 260 /// are not supported. 261 void handleMove(MachineInstr* MI); 262 263 /// moveIntoBundle - Update intervals for operands of MI so that they 264 /// begin/end on the SlotIndex for BundleStart. 265 /// 266 /// Requires MI and BundleStart to have SlotIndexes, and assumes 267 /// existing liveness is accurate. BundleStart should be the first 268 /// instruction in the Bundle. 269 void handleMoveIntoBundle(MachineInstr* MI, MachineInstr* BundleStart); 270 271 // Register mask functions. 272 // 273 // Machine instructions may use a register mask operand to indicate that a 274 // large number of registers are clobbered by the instruction. This is 275 // typically used for calls. 276 // 277 // For compile time performance reasons, these clobbers are not recorded in 278 // the live intervals for individual physical registers. Instead, 279 // LiveIntervalAnalysis maintains a sorted list of instructions with 280 // register mask operands. 281 282 /// getRegMaskSlots - Returns a sorted array of slot indices of all 283 /// instructions with register mask operands. 284 ArrayRef<SlotIndex> getRegMaskSlots() const { return RegMaskSlots; } 285 286 /// getRegMaskSlotsInBlock - Returns a sorted array of slot indices of all 287 /// instructions with register mask operands in the basic block numbered 288 /// MBBNum. 289 ArrayRef<SlotIndex> getRegMaskSlotsInBlock(unsigned MBBNum) const { 290 std::pair<unsigned, unsigned> P = RegMaskBlocks[MBBNum]; 291 return getRegMaskSlots().slice(P.first, P.second); 292 } 293 294 /// getRegMaskBits() - Returns an array of register mask pointers 295 /// corresponding to getRegMaskSlots(). 296 ArrayRef<const uint32_t*> getRegMaskBits() const { return RegMaskBits; } 297 298 /// getRegMaskBitsInBlock - Returns an array of mask pointers corresponding 299 /// to getRegMaskSlotsInBlock(MBBNum). 300 ArrayRef<const uint32_t*> getRegMaskBitsInBlock(unsigned MBBNum) const { 301 std::pair<unsigned, unsigned> P = RegMaskBlocks[MBBNum]; 302 return getRegMaskBits().slice(P.first, P.second); 303 } 304 305 /// checkRegMaskInterference - Test if LI is live across any register mask 306 /// instructions, and compute a bit mask of physical registers that are not 307 /// clobbered by any of them. 308 /// 309 /// Returns false if LI doesn't cross any register mask instructions. In 310 /// that case, the bit vector is not filled in. 311 bool checkRegMaskInterference(LiveInterval &LI, 312 BitVector &UsableRegs); 313 314 // Register unit functions. 315 // 316 // Fixed interference occurs when MachineInstrs use physregs directly 317 // instead of virtual registers. This typically happens when passing 318 // arguments to a function call, or when instructions require operands in 319 // fixed registers. 320 // 321 // Each physreg has one or more register units, see MCRegisterInfo. We 322 // track liveness per register unit to handle aliasing registers more 323 // efficiently. 324 325 /// getRegUnit - Return the live range for Unit. 326 /// It will be computed if it doesn't exist. 327 LiveInterval &getRegUnit(unsigned Unit) { 328 LiveInterval *LI = RegUnitIntervals[Unit]; 329 if (!LI) { 330 // Compute missing ranges on demand. 331 RegUnitIntervals[Unit] = LI = new LiveInterval(Unit, HUGE_VALF); 332 computeRegUnitInterval(LI); 333 } 334 return *LI; 335 } 336 337 /// getCachedRegUnit - Return the live range for Unit if it has already 338 /// been computed, or NULL if it hasn't been computed yet. 339 LiveInterval *getCachedRegUnit(unsigned Unit) { 340 return RegUnitIntervals[Unit]; 341 } 342 343 private: 344 /// computeIntervals - Compute live intervals. 345 void computeIntervals(); 346 347 /// Compute live intervals for all virtual registers. 348 void computeVirtRegs(); 349 350 /// Compute RegMaskSlots and RegMaskBits. 351 void computeRegMasks(); 352 353 /// handleRegisterDef - update intervals for a register def 354 /// (calls handleVirtualRegisterDef) 355 void handleRegisterDef(MachineBasicBlock *MBB, 356 MachineBasicBlock::iterator MI, 357 SlotIndex MIIdx, 358 MachineOperand& MO, unsigned MOIdx); 359 360 /// isPartialRedef - Return true if the specified def at the specific index 361 /// is partially re-defining the specified live interval. A common case of 362 /// this is a definition of the sub-register. 363 bool isPartialRedef(SlotIndex MIIdx, MachineOperand &MO, 364 LiveInterval &interval); 365 366 /// handleVirtualRegisterDef - update intervals for a virtual 367 /// register def 368 void handleVirtualRegisterDef(MachineBasicBlock *MBB, 369 MachineBasicBlock::iterator MI, 370 SlotIndex MIIdx, MachineOperand& MO, 371 unsigned MOIdx, 372 LiveInterval& interval); 373 374 static LiveInterval* createInterval(unsigned Reg); 375 376 void printInstrs(raw_ostream &O) const; 377 void dumpInstrs() const; 378 379 void computeLiveInRegUnits(); 380 void computeRegUnitInterval(LiveInterval*); 381 void computeVirtRegInterval(LiveInterval*); 382 383 class HMEditor; 384 }; 385 } // End llvm namespace 386 387 #endif 388
