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/// \file This file implements the LiveInterval analysis pass. Given some 11/// numbering of each the machine instructions (in this implemention depth-first 12/// order) an interval [i, j) is said to be a live interval for register v if 13/// there is no instruction with number j' > j such that v is live at j' and 14/// there is no instruction with number i' < i such that v is live at i'. In 15/// this implementation intervals can have holes, i.e. an interval might look 16/// like [1,20), [50,65), [1000,1001). 17// 18//===----------------------------------------------------------------------===// 19 20#ifndef LLVM_CODEGEN_LIVEINTERVALANALYSIS_H 21#define LLVM_CODEGEN_LIVEINTERVALANALYSIS_H 22 23#include "llvm/ADT/ArrayRef.h" 24#include "llvm/ADT/IndexedMap.h" 25#include "llvm/ADT/SmallVector.h" 26#include "llvm/Analysis/AliasAnalysis.h" 27#include "llvm/CodeGen/LiveInterval.h" 28#include "llvm/CodeGen/MachineBasicBlock.h" 29#include "llvm/CodeGen/MachineFunctionPass.h" 30#include "llvm/CodeGen/SlotIndexes.h" 31#include "llvm/MC/LaneBitmask.h" 32#include "llvm/Support/CommandLine.h" 33#include "llvm/Support/Compiler.h" 34#include "llvm/Support/ErrorHandling.h" 35#include "llvm/Target/TargetRegisterInfo.h" 36#include <cassert> 37#include <cstdint> 38#include <utility> 39 40namespace llvm { 41 42extern cl::opt<bool> UseSegmentSetForPhysRegs; 43 44class BitVector; 45class LiveRangeCalc; 46class MachineBlockFrequencyInfo; 47class MachineDominatorTree; 48class MachineFunction; 49class MachineInstr; 50class MachineRegisterInfo; 51class raw_ostream; 52class TargetInstrInfo; 53class VirtRegMap; 54 55 class LiveIntervals : public MachineFunctionPass { 56 MachineFunction* MF; 57 MachineRegisterInfo* MRI; 58 const TargetRegisterInfo* TRI; 59 const TargetInstrInfo* TII; 60 AliasAnalysis *AA; 61 SlotIndexes* Indexes; 62 MachineDominatorTree *DomTree = nullptr; 63 LiveRangeCalc *LRCalc = nullptr; 64 65 /// Special pool allocator for VNInfo's (LiveInterval val#). 66 VNInfo::Allocator VNInfoAllocator; 67 68 /// Live interval pointers for all the virtual registers. 69 IndexedMap<LiveInterval*, VirtReg2IndexFunctor> VirtRegIntervals; 70 71 /// Sorted list of instructions with register mask operands. Always use the 72 /// 'r' slot, RegMasks are normal clobbers, not early clobbers. 73 SmallVector<SlotIndex, 8> RegMaskSlots; 74 75 /// This vector is parallel to RegMaskSlots, it holds a pointer to the 76 /// corresponding register mask. This pointer can be recomputed as: 77 /// 78 /// MI = Indexes->getInstructionFromIndex(RegMaskSlot[N]); 79 /// unsigned OpNum = findRegMaskOperand(MI); 80 /// RegMaskBits[N] = MI->getOperand(OpNum).getRegMask(); 81 /// 82 /// This is kept in a separate vector partly because some standard 83 /// libraries don't support lower_bound() with mixed objects, partly to 84 /// improve locality when searching in RegMaskSlots. 85 /// Also see the comment in LiveInterval::find(). 86 SmallVector<const uint32_t*, 8> RegMaskBits; 87 88 /// For each basic block number, keep (begin, size) pairs indexing into the 89 /// RegMaskSlots and RegMaskBits arrays. 90 /// Note that basic block numbers may not be layout contiguous, that's why 91 /// we can't just keep track of the first register mask in each basic 92 /// block. 93 SmallVector<std::pair<unsigned, unsigned>, 8> RegMaskBlocks; 94 95 /// Keeps a live range set for each register unit to track fixed physreg 96 /// interference. 97 SmallVector<LiveRange*, 0> RegUnitRanges; 98 99 public: 100 static char ID; 101 102 LiveIntervals(); 103 ~LiveIntervals() override; 104 105 /// Calculate the spill weight to assign to a single instruction. 106 static float getSpillWeight(bool isDef, bool isUse, 107 const MachineBlockFrequencyInfo *MBFI, 108 const MachineInstr &Instr); 109 110 LiveInterval &getInterval(unsigned Reg) { 111 if (hasInterval(Reg)) 112 return *VirtRegIntervals[Reg]; 113 else 114 return createAndComputeVirtRegInterval(Reg); 115 } 116 117 const LiveInterval &getInterval(unsigned Reg) const { 118 return const_cast<LiveIntervals*>(this)->getInterval(Reg); 119 } 120 121 bool hasInterval(unsigned Reg) const { 122 return VirtRegIntervals.inBounds(Reg) && VirtRegIntervals[Reg]; 123 } 124 125 /// Interval creation. 126 LiveInterval &createEmptyInterval(unsigned Reg) { 127 assert(!hasInterval(Reg) && "Interval already exists!"); 128 VirtRegIntervals.grow(Reg); 129 VirtRegIntervals[Reg] = createInterval(Reg); 130 return *VirtRegIntervals[Reg]; 131 } 132 133 LiveInterval &createAndComputeVirtRegInterval(unsigned Reg) { 134 LiveInterval &LI = createEmptyInterval(Reg); 135 computeVirtRegInterval(LI); 136 return LI; 137 } 138 139 /// Interval removal. 140 void removeInterval(unsigned Reg) { 141 delete VirtRegIntervals[Reg]; 142 VirtRegIntervals[Reg] = nullptr; 143 } 144 145 /// Given a register and an instruction, adds a live segment from that 146 /// instruction to the end of its MBB. 147 LiveInterval::Segment addSegmentToEndOfBlock(unsigned reg, 148 MachineInstr &startInst); 149 150 /// After removing some uses of a register, shrink its live range to just 151 /// the remaining uses. This method does not compute reaching defs for new 152 /// uses, and it doesn't remove dead defs. 153 /// Dead PHIDef values are marked as unused. New dead machine instructions 154 /// are added to the dead vector. Returns true if the interval may have been 155 /// separated into multiple connected components. 156 bool shrinkToUses(LiveInterval *li, 157 SmallVectorImpl<MachineInstr*> *dead = nullptr); 158 159 /// Specialized version of 160 /// shrinkToUses(LiveInterval *li, SmallVectorImpl<MachineInstr*> *dead) 161 /// that works on a subregister live range and only looks at uses matching 162 /// the lane mask of the subregister range. 163 /// This may leave the subrange empty which needs to be cleaned up with 164 /// LiveInterval::removeEmptySubranges() afterwards. 165 void shrinkToUses(LiveInterval::SubRange &SR, unsigned Reg); 166 167 /// Extend the live range \p LR to reach all points in \p Indices. The 168 /// points in the \p Indices array must be jointly dominated by the union 169 /// of the existing defs in \p LR and points in \p Undefs. 170 /// 171 /// PHI-defs are added as needed to maintain SSA form. 172 /// 173 /// If a SlotIndex in \p Indices is the end index of a basic block, \p LR 174 /// will be extended to be live out of the basic block. 175 /// If a SlotIndex in \p Indices is jointy dominated only by points in 176 /// \p Undefs, the live range will not be extended to that point. 177 /// 178 /// See also LiveRangeCalc::extend(). 179 void extendToIndices(LiveRange &LR, ArrayRef<SlotIndex> Indices, 180 ArrayRef<SlotIndex> Undefs); 181 182 void extendToIndices(LiveRange &LR, ArrayRef<SlotIndex> Indices) { 183 extendToIndices(LR, Indices, /*Undefs=*/{}); 184 } 185 186 /// If \p LR has a live value at \p Kill, prune its live range by removing 187 /// any liveness reachable from Kill. Add live range end points to 188 /// EndPoints such that extendToIndices(LI, EndPoints) will reconstruct the 189 /// value's live range. 190 /// 191 /// Calling pruneValue() and extendToIndices() can be used to reconstruct 192 /// SSA form after adding defs to a virtual register. 193 void pruneValue(LiveRange &LR, SlotIndex Kill, 194 SmallVectorImpl<SlotIndex> *EndPoints); 195 196 /// This function should not be used. Its intend is to tell you that 197 /// you are doing something wrong if you call pruveValue directly on a 198 /// LiveInterval. Indeed, you are supposed to call pruneValue on the main 199 /// LiveRange and all the LiveRange of the subranges if any. 200 LLVM_ATTRIBUTE_UNUSED void pruneValue(LiveInterval &, SlotIndex, 201 SmallVectorImpl<SlotIndex> *) { 202 llvm_unreachable( 203 "Use pruneValue on the main LiveRange and on each subrange"); 204 } 205 206 SlotIndexes *getSlotIndexes() const { 207 return Indexes; 208 } 209 210 AliasAnalysis *getAliasAnalysis() const { 211 return AA; 212 } 213 214 /// Returns true if the specified machine instr has been removed or was 215 /// never entered in the map. 216 bool isNotInMIMap(const MachineInstr &Instr) const { 217 return !Indexes->hasIndex(Instr); 218 } 219 220 /// Returns the base index of the given instruction. 221 SlotIndex getInstructionIndex(const MachineInstr &Instr) const { 222 return Indexes->getInstructionIndex(Instr); 223 } 224 225 /// Returns the instruction associated with the given index. 226 MachineInstr* getInstructionFromIndex(SlotIndex index) const { 227 return Indexes->getInstructionFromIndex(index); 228 } 229 230 /// Return the first index in the given basic block. 231 SlotIndex getMBBStartIdx(const MachineBasicBlock *mbb) const { 232 return Indexes->getMBBStartIdx(mbb); 233 } 234 235 /// Return the last index in the given basic block. 236 SlotIndex getMBBEndIdx(const MachineBasicBlock *mbb) const { 237 return Indexes->getMBBEndIdx(mbb); 238 } 239 240 bool isLiveInToMBB(const LiveRange &LR, 241 const MachineBasicBlock *mbb) const { 242 return LR.liveAt(getMBBStartIdx(mbb)); 243 } 244 245 bool isLiveOutOfMBB(const LiveRange &LR, 246 const MachineBasicBlock *mbb) const { 247 return LR.liveAt(getMBBEndIdx(mbb).getPrevSlot()); 248 } 249 250 MachineBasicBlock* getMBBFromIndex(SlotIndex index) const { 251 return Indexes->getMBBFromIndex(index); 252 } 253 254 void insertMBBInMaps(MachineBasicBlock *MBB) { 255 Indexes->insertMBBInMaps(MBB); 256 assert(unsigned(MBB->getNumber()) == RegMaskBlocks.size() && 257 "Blocks must be added in order."); 258 RegMaskBlocks.push_back(std::make_pair(RegMaskSlots.size(), 0)); 259 } 260 261 SlotIndex InsertMachineInstrInMaps(MachineInstr &MI) { 262 return Indexes->insertMachineInstrInMaps(MI); 263 } 264 265 void InsertMachineInstrRangeInMaps(MachineBasicBlock::iterator B, 266 MachineBasicBlock::iterator E) { 267 for (MachineBasicBlock::iterator I = B; I != E; ++I) 268 Indexes->insertMachineInstrInMaps(*I); 269 } 270 271 void RemoveMachineInstrFromMaps(MachineInstr &MI) { 272 Indexes->removeMachineInstrFromMaps(MI); 273 } 274 275 SlotIndex ReplaceMachineInstrInMaps(MachineInstr &MI, MachineInstr &NewMI) { 276 return Indexes->replaceMachineInstrInMaps(MI, NewMI); 277 } 278 279 VNInfo::Allocator& getVNInfoAllocator() { return VNInfoAllocator; } 280 281 void getAnalysisUsage(AnalysisUsage &AU) const override; 282 void releaseMemory() override; 283 284 /// Pass entry point; Calculates LiveIntervals. 285 bool runOnMachineFunction(MachineFunction&) override; 286 287 /// Implement the dump method. 288 void print(raw_ostream &O, const Module* = nullptr) const override; 289 290 /// If LI is confined to a single basic block, return a pointer to that 291 /// block. If LI is live in to or out of any block, return NULL. 292 MachineBasicBlock *intervalIsInOneMBB(const LiveInterval &LI) const; 293 294 /// Returns true if VNI is killed by any PHI-def values in LI. 295 /// This may conservatively return true to avoid expensive computations. 296 bool hasPHIKill(const LiveInterval &LI, const VNInfo *VNI) const; 297 298 /// Add kill flags to any instruction that kills a virtual register. 299 void addKillFlags(const VirtRegMap*); 300 301 /// Call this method to notify LiveIntervals that instruction \p MI has been 302 /// moved within a basic block. This will update the live intervals for all 303 /// operands of \p MI. Moves between basic blocks are not supported. 304 /// 305 /// \param UpdateFlags Update live intervals for nonallocatable physregs. 306 void handleMove(MachineInstr &MI, bool UpdateFlags = false); 307 308 /// Update intervals for operands of \p MI so that they begin/end on the 309 /// SlotIndex for \p BundleStart. 310 /// 311 /// \param UpdateFlags Update live intervals for nonallocatable physregs. 312 /// 313 /// Requires MI and BundleStart to have SlotIndexes, and assumes 314 /// existing liveness is accurate. BundleStart should be the first 315 /// instruction in the Bundle. 316 void handleMoveIntoBundle(MachineInstr &MI, MachineInstr &BundleStart, 317 bool UpdateFlags = false); 318 319 /// Update live intervals for instructions in a range of iterators. It is 320 /// intended for use after target hooks that may insert or remove 321 /// instructions, and is only efficient for a small number of instructions. 322 /// 323 /// OrigRegs is a vector of registers that were originally used by the 324 /// instructions in the range between the two iterators. 325 /// 326 /// Currently, the only only changes that are supported are simple removal 327 /// and addition of uses. 328 void repairIntervalsInRange(MachineBasicBlock *MBB, 329 MachineBasicBlock::iterator Begin, 330 MachineBasicBlock::iterator End, 331 ArrayRef<unsigned> OrigRegs); 332 333 // Register mask functions. 334 // 335 // Machine instructions may use a register mask operand to indicate that a 336 // large number of registers are clobbered by the instruction. This is 337 // typically used for calls. 338 // 339 // For compile time performance reasons, these clobbers are not recorded in 340 // the live intervals for individual physical registers. Instead, 341 // LiveIntervalAnalysis maintains a sorted list of instructions with 342 // register mask operands. 343 344 /// Returns a sorted array of slot indices of all instructions with 345 /// register mask operands. 346 ArrayRef<SlotIndex> getRegMaskSlots() const { return RegMaskSlots; } 347 348 /// Returns a sorted array of slot indices of all instructions with register 349 /// mask operands in the basic block numbered \p MBBNum. 350 ArrayRef<SlotIndex> getRegMaskSlotsInBlock(unsigned MBBNum) const { 351 std::pair<unsigned, unsigned> P = RegMaskBlocks[MBBNum]; 352 return getRegMaskSlots().slice(P.first, P.second); 353 } 354 355 /// Returns an array of register mask pointers corresponding to 356 /// getRegMaskSlots(). 357 ArrayRef<const uint32_t*> getRegMaskBits() const { return RegMaskBits; } 358 359 /// Returns an array of mask pointers corresponding to 360 /// getRegMaskSlotsInBlock(MBBNum). 361 ArrayRef<const uint32_t*> getRegMaskBitsInBlock(unsigned MBBNum) const { 362 std::pair<unsigned, unsigned> P = RegMaskBlocks[MBBNum]; 363 return getRegMaskBits().slice(P.first, P.second); 364 } 365 366 /// Test if \p LI is live across any register mask instructions, and 367 /// compute a bit mask of physical registers that are not clobbered by any 368 /// of them. 369 /// 370 /// Returns false if \p LI doesn't cross any register mask instructions. In 371 /// that case, the bit vector is not filled in. 372 bool checkRegMaskInterference(LiveInterval &LI, 373 BitVector &UsableRegs); 374 375 // Register unit functions. 376 // 377 // Fixed interference occurs when MachineInstrs use physregs directly 378 // instead of virtual registers. This typically happens when passing 379 // arguments to a function call, or when instructions require operands in 380 // fixed registers. 381 // 382 // Each physreg has one or more register units, see MCRegisterInfo. We 383 // track liveness per register unit to handle aliasing registers more 384 // efficiently. 385 386 /// Return the live range for register unit \p Unit. It will be computed if 387 /// it doesn't exist. 388 LiveRange &getRegUnit(unsigned Unit) { 389 LiveRange *LR = RegUnitRanges[Unit]; 390 if (!LR) { 391 // Compute missing ranges on demand. 392 // Use segment set to speed-up initial computation of the live range. 393 RegUnitRanges[Unit] = LR = new LiveRange(UseSegmentSetForPhysRegs); 394 computeRegUnitRange(*LR, Unit); 395 } 396 return *LR; 397 } 398 399 /// Return the live range for register unit \p Unit if it has already been 400 /// computed, or nullptr if it hasn't been computed yet. 401 LiveRange *getCachedRegUnit(unsigned Unit) { 402 return RegUnitRanges[Unit]; 403 } 404 405 const LiveRange *getCachedRegUnit(unsigned Unit) const { 406 return RegUnitRanges[Unit]; 407 } 408 409 /// Remove computed live range for register unit \p Unit. Subsequent uses 410 /// should rely on on-demand recomputation. 411 void removeRegUnit(unsigned Unit) { 412 delete RegUnitRanges[Unit]; 413 RegUnitRanges[Unit] = nullptr; 414 } 415 416 /// Remove value numbers and related live segments starting at position 417 /// \p Pos that are part of any liverange of physical register \p Reg or one 418 /// of its subregisters. 419 void removePhysRegDefAt(unsigned Reg, SlotIndex Pos); 420 421 /// Remove value number and related live segments of \p LI and its subranges 422 /// that start at position \p Pos. 423 void removeVRegDefAt(LiveInterval &LI, SlotIndex Pos); 424 425 /// Split separate components in LiveInterval \p LI into separate intervals. 426 void splitSeparateComponents(LiveInterval &LI, 427 SmallVectorImpl<LiveInterval*> &SplitLIs); 428 429 /// For live interval \p LI with correct SubRanges construct matching 430 /// information for the main live range. Expects the main live range to not 431 /// have any segments or value numbers. 432 void constructMainRangeFromSubranges(LiveInterval &LI); 433 434 private: 435 /// Compute live intervals for all virtual registers. 436 void computeVirtRegs(); 437 438 /// Compute RegMaskSlots and RegMaskBits. 439 void computeRegMasks(); 440 441 /// Walk the values in \p LI and check for dead values: 442 /// - Dead PHIDef values are marked as unused. 443 /// - Dead operands are marked as such. 444 /// - Completely dead machine instructions are added to the \p dead vector 445 /// if it is not nullptr. 446 /// Returns true if any PHI value numbers have been removed which may 447 /// have separated the interval into multiple connected components. 448 bool computeDeadValues(LiveInterval &LI, 449 SmallVectorImpl<MachineInstr*> *dead); 450 451 static LiveInterval* createInterval(unsigned Reg); 452 453 void printInstrs(raw_ostream &O) const; 454 void dumpInstrs() const; 455 456 void computeLiveInRegUnits(); 457 void computeRegUnitRange(LiveRange&, unsigned Unit); 458 void computeVirtRegInterval(LiveInterval&); 459 460 461 /// Helper function for repairIntervalsInRange(), walks backwards and 462 /// creates/modifies live segments in \p LR to match the operands found. 463 /// Only full operands or operands with subregisters matching \p LaneMask 464 /// are considered. 465 void repairOldRegInRange(MachineBasicBlock::iterator Begin, 466 MachineBasicBlock::iterator End, 467 const SlotIndex endIdx, LiveRange &LR, 468 unsigned Reg, 469 LaneBitmask LaneMask = LaneBitmask::getAll()); 470 471 class HMEditor; 472 }; 473 474} // end namespace llvm 475 476#endif // LLVM_CODEGEN_LIVEINTERVALANALYSIS_H 477