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