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