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