1 //===- RegisterPressure.h - Dynamic Register Pressure -----------*- 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 // This file defines the RegisterPressure class which can be used to track 10 // MachineInstr level register pressure. 11 // 12 //===----------------------------------------------------------------------===// 13 14 #ifndef LLVM_CODEGEN_REGISTERPRESSURE_H 15 #define LLVM_CODEGEN_REGISTERPRESSURE_H 16 17 #include "llvm/ADT/ArrayRef.h" 18 #include "llvm/ADT/SmallVector.h" 19 #include "llvm/ADT/SparseSet.h" 20 #include "llvm/CodeGen/MachineBasicBlock.h" 21 #include "llvm/CodeGen/SlotIndexes.h" 22 #include "llvm/CodeGen/TargetRegisterInfo.h" 23 #include "llvm/MC/LaneBitmask.h" 24 #include <cassert> 25 #include <cstddef> 26 #include <cstdint> 27 #include <cstdlib> 28 #include <limits> 29 #include <vector> 30 31 namespace llvm { 32 33 class LiveIntervals; 34 class MachineFunction; 35 class MachineInstr; 36 class MachineRegisterInfo; 37 class RegisterClassInfo; 38 39 struct RegisterMaskPair { 40 unsigned RegUnit; ///< Virtual register or register unit. 41 LaneBitmask LaneMask; 42 RegisterMaskPairRegisterMaskPair43 RegisterMaskPair(unsigned RegUnit, LaneBitmask LaneMask) 44 : RegUnit(RegUnit), LaneMask(LaneMask) {} 45 }; 46 47 /// Base class for register pressure results. 48 struct RegisterPressure { 49 /// Map of max reg pressure indexed by pressure set ID, not class ID. 50 std::vector<unsigned> MaxSetPressure; 51 52 /// List of live in virtual registers or physical register units. 53 SmallVector<RegisterMaskPair,8> LiveInRegs; 54 SmallVector<RegisterMaskPair,8> LiveOutRegs; 55 56 void dump(const TargetRegisterInfo *TRI) const; 57 }; 58 59 /// RegisterPressure computed within a region of instructions delimited by 60 /// TopIdx and BottomIdx. During pressure computation, the maximum pressure per 61 /// register pressure set is increased. Once pressure within a region is fully 62 /// computed, the live-in and live-out sets are recorded. 63 /// 64 /// This is preferable to RegionPressure when LiveIntervals are available, 65 /// because delimiting regions by SlotIndex is more robust and convenient than 66 /// holding block iterators. The block contents can change without invalidating 67 /// the pressure result. 68 struct IntervalPressure : RegisterPressure { 69 /// Record the boundary of the region being tracked. 70 SlotIndex TopIdx; 71 SlotIndex BottomIdx; 72 73 void reset(); 74 75 void openTop(SlotIndex NextTop); 76 77 void openBottom(SlotIndex PrevBottom); 78 }; 79 80 /// RegisterPressure computed within a region of instructions delimited by 81 /// TopPos and BottomPos. This is a less precise version of IntervalPressure for 82 /// use when LiveIntervals are unavailable. 83 struct RegionPressure : RegisterPressure { 84 /// Record the boundary of the region being tracked. 85 MachineBasicBlock::const_iterator TopPos; 86 MachineBasicBlock::const_iterator BottomPos; 87 88 void reset(); 89 90 void openTop(MachineBasicBlock::const_iterator PrevTop); 91 92 void openBottom(MachineBasicBlock::const_iterator PrevBottom); 93 }; 94 95 /// Capture a change in pressure for a single pressure set. UnitInc may be 96 /// expressed in terms of upward or downward pressure depending on the client 97 /// and will be dynamically adjusted for current liveness. 98 /// 99 /// Pressure increments are tiny, typically 1-2 units, and this is only for 100 /// heuristics, so we don't check UnitInc overflow. Instead, we may have a 101 /// higher level assert that pressure is consistent within a region. We also 102 /// effectively ignore dead defs which don't affect heuristics much. 103 class PressureChange { 104 uint16_t PSetID = 0; // ID+1. 0=Invalid. 105 int16_t UnitInc = 0; 106 107 public: 108 PressureChange() = default; PressureChange(unsigned id)109 PressureChange(unsigned id): PSetID(id + 1) { 110 assert(id < std::numeric_limits<uint16_t>::max() && "PSetID overflow."); 111 } 112 isValid()113 bool isValid() const { return PSetID > 0; } 114 getPSet()115 unsigned getPSet() const { 116 assert(isValid() && "invalid PressureChange"); 117 return PSetID - 1; 118 } 119 120 // If PSetID is invalid, return UINT16_MAX to give it lowest priority. getPSetOrMax()121 unsigned getPSetOrMax() const { 122 return (PSetID - 1) & std::numeric_limits<uint16_t>::max(); 123 } 124 getUnitInc()125 int getUnitInc() const { return UnitInc; } 126 setUnitInc(int Inc)127 void setUnitInc(int Inc) { UnitInc = Inc; } 128 129 bool operator==(const PressureChange &RHS) const { 130 return PSetID == RHS.PSetID && UnitInc == RHS.UnitInc; 131 } 132 }; 133 134 /// List of PressureChanges in order of increasing, unique PSetID. 135 /// 136 /// Use a small fixed number, because we can fit more PressureChanges in an 137 /// empty SmallVector than ever need to be tracked per register class. If more 138 /// PSets are affected, then we only track the most constrained. 139 class PressureDiff { 140 // The initial design was for MaxPSets=4, but that requires PSet partitions, 141 // which are not yet implemented. (PSet partitions are equivalent PSets given 142 // the register classes actually in use within the scheduling region.) 143 enum { MaxPSets = 16 }; 144 145 PressureChange PressureChanges[MaxPSets]; 146 147 using iterator = PressureChange *; 148 nonconst_begin()149 iterator nonconst_begin() { return &PressureChanges[0]; } nonconst_end()150 iterator nonconst_end() { return &PressureChanges[MaxPSets]; } 151 152 public: 153 using const_iterator = const PressureChange *; 154 begin()155 const_iterator begin() const { return &PressureChanges[0]; } end()156 const_iterator end() const { return &PressureChanges[MaxPSets]; } 157 158 void addPressureChange(unsigned RegUnit, bool IsDec, 159 const MachineRegisterInfo *MRI); 160 161 void dump(const TargetRegisterInfo &TRI) const; 162 }; 163 164 /// List of registers defined and used by a machine instruction. 165 class RegisterOperands { 166 public: 167 /// List of virtual registers and register units read by the instruction. 168 SmallVector<RegisterMaskPair, 8> Uses; 169 /// List of virtual registers and register units defined by the 170 /// instruction which are not dead. 171 SmallVector<RegisterMaskPair, 8> Defs; 172 /// List of virtual registers and register units defined by the 173 /// instruction but dead. 174 SmallVector<RegisterMaskPair, 8> DeadDefs; 175 176 /// Analyze the given instruction \p MI and fill in the Uses, Defs and 177 /// DeadDefs list based on the MachineOperand flags. 178 void collect(const MachineInstr &MI, const TargetRegisterInfo &TRI, 179 const MachineRegisterInfo &MRI, bool TrackLaneMasks, 180 bool IgnoreDead); 181 182 /// Use liveness information to find dead defs not marked with a dead flag 183 /// and move them to the DeadDefs vector. 184 void detectDeadDefs(const MachineInstr &MI, const LiveIntervals &LIS); 185 186 /// Use liveness information to find out which uses/defs are partially 187 /// undefined/dead and adjust the RegisterMaskPairs accordingly. 188 /// If \p AddFlagsMI is given then missing read-undef and dead flags will be 189 /// added to the instruction. 190 void adjustLaneLiveness(const LiveIntervals &LIS, 191 const MachineRegisterInfo &MRI, SlotIndex Pos, 192 MachineInstr *AddFlagsMI = nullptr); 193 }; 194 195 /// Array of PressureDiffs. 196 class PressureDiffs { 197 PressureDiff *PDiffArray = nullptr; 198 unsigned Size = 0; 199 unsigned Max = 0; 200 201 public: 202 PressureDiffs() = default; ~PressureDiffs()203 ~PressureDiffs() { free(PDiffArray); } 204 clear()205 void clear() { Size = 0; } 206 207 void init(unsigned N); 208 209 PressureDiff &operator[](unsigned Idx) { 210 assert(Idx < Size && "PressureDiff index out of bounds"); 211 return PDiffArray[Idx]; 212 } 213 const PressureDiff &operator[](unsigned Idx) const { 214 return const_cast<PressureDiffs*>(this)->operator[](Idx); 215 } 216 217 /// Record pressure difference induced by the given operand list to 218 /// node with index \p Idx. 219 void addInstruction(unsigned Idx, const RegisterOperands &RegOpers, 220 const MachineRegisterInfo &MRI); 221 }; 222 223 /// Store the effects of a change in pressure on things that MI scheduler cares 224 /// about. 225 /// 226 /// Excess records the value of the largest difference in register units beyond 227 /// the target's pressure limits across the affected pressure sets, where 228 /// largest is defined as the absolute value of the difference. Negative 229 /// ExcessUnits indicates a reduction in pressure that had already exceeded the 230 /// target's limits. 231 /// 232 /// CriticalMax records the largest increase in the tracker's max pressure that 233 /// exceeds the critical limit for some pressure set determined by the client. 234 /// 235 /// CurrentMax records the largest increase in the tracker's max pressure that 236 /// exceeds the current limit for some pressure set determined by the client. 237 struct RegPressureDelta { 238 PressureChange Excess; 239 PressureChange CriticalMax; 240 PressureChange CurrentMax; 241 242 RegPressureDelta() = default; 243 244 bool operator==(const RegPressureDelta &RHS) const { 245 return Excess == RHS.Excess && CriticalMax == RHS.CriticalMax 246 && CurrentMax == RHS.CurrentMax; 247 } 248 bool operator!=(const RegPressureDelta &RHS) const { 249 return !operator==(RHS); 250 } 251 }; 252 253 /// A set of live virtual registers and physical register units. 254 /// 255 /// This is a wrapper around a SparseSet which deals with mapping register unit 256 /// and virtual register indexes to an index usable by the sparse set. 257 class LiveRegSet { 258 private: 259 struct IndexMaskPair { 260 unsigned Index; 261 LaneBitmask LaneMask; 262 IndexMaskPairIndexMaskPair263 IndexMaskPair(unsigned Index, LaneBitmask LaneMask) 264 : Index(Index), LaneMask(LaneMask) {} 265 getSparseSetIndexIndexMaskPair266 unsigned getSparseSetIndex() const { 267 return Index; 268 } 269 }; 270 271 using RegSet = SparseSet<IndexMaskPair>; 272 RegSet Regs; 273 unsigned NumRegUnits; 274 getSparseIndexFromReg(unsigned Reg)275 unsigned getSparseIndexFromReg(unsigned Reg) const { 276 if (TargetRegisterInfo::isVirtualRegister(Reg)) 277 return TargetRegisterInfo::virtReg2Index(Reg) + NumRegUnits; 278 assert(Reg < NumRegUnits); 279 return Reg; 280 } 281 getRegFromSparseIndex(unsigned SparseIndex)282 unsigned getRegFromSparseIndex(unsigned SparseIndex) const { 283 if (SparseIndex >= NumRegUnits) 284 return TargetRegisterInfo::index2VirtReg(SparseIndex-NumRegUnits); 285 return SparseIndex; 286 } 287 288 public: 289 void clear(); 290 void init(const MachineRegisterInfo &MRI); 291 contains(unsigned Reg)292 LaneBitmask contains(unsigned Reg) const { 293 unsigned SparseIndex = getSparseIndexFromReg(Reg); 294 RegSet::const_iterator I = Regs.find(SparseIndex); 295 if (I == Regs.end()) 296 return LaneBitmask::getNone(); 297 return I->LaneMask; 298 } 299 300 /// Mark the \p Pair.LaneMask lanes of \p Pair.Reg as live. 301 /// Returns the previously live lanes of \p Pair.Reg. insert(RegisterMaskPair Pair)302 LaneBitmask insert(RegisterMaskPair Pair) { 303 unsigned SparseIndex = getSparseIndexFromReg(Pair.RegUnit); 304 auto InsertRes = Regs.insert(IndexMaskPair(SparseIndex, Pair.LaneMask)); 305 if (!InsertRes.second) { 306 LaneBitmask PrevMask = InsertRes.first->LaneMask; 307 InsertRes.first->LaneMask |= Pair.LaneMask; 308 return PrevMask; 309 } 310 return LaneBitmask::getNone(); 311 } 312 313 /// Clears the \p Pair.LaneMask lanes of \p Pair.Reg (mark them as dead). 314 /// Returns the previously live lanes of \p Pair.Reg. erase(RegisterMaskPair Pair)315 LaneBitmask erase(RegisterMaskPair Pair) { 316 unsigned SparseIndex = getSparseIndexFromReg(Pair.RegUnit); 317 RegSet::iterator I = Regs.find(SparseIndex); 318 if (I == Regs.end()) 319 return LaneBitmask::getNone(); 320 LaneBitmask PrevMask = I->LaneMask; 321 I->LaneMask &= ~Pair.LaneMask; 322 return PrevMask; 323 } 324 size()325 size_t size() const { 326 return Regs.size(); 327 } 328 329 template<typename ContainerT> appendTo(ContainerT & To)330 void appendTo(ContainerT &To) const { 331 for (const IndexMaskPair &P : Regs) { 332 unsigned Reg = getRegFromSparseIndex(P.Index); 333 if (P.LaneMask.any()) 334 To.push_back(RegisterMaskPair(Reg, P.LaneMask)); 335 } 336 } 337 }; 338 339 /// Track the current register pressure at some position in the instruction 340 /// stream, and remember the high water mark within the region traversed. This 341 /// does not automatically consider live-through ranges. The client may 342 /// independently adjust for global liveness. 343 /// 344 /// Each RegPressureTracker only works within a MachineBasicBlock. Pressure can 345 /// be tracked across a larger region by storing a RegisterPressure result at 346 /// each block boundary and explicitly adjusting pressure to account for block 347 /// live-in and live-out register sets. 348 /// 349 /// RegPressureTracker holds a reference to a RegisterPressure result that it 350 /// computes incrementally. During downward tracking, P.BottomIdx or P.BottomPos 351 /// is invalid until it reaches the end of the block or closeRegion() is 352 /// explicitly called. Similarly, P.TopIdx is invalid during upward 353 /// tracking. Changing direction has the side effect of closing region, and 354 /// traversing past TopIdx or BottomIdx reopens it. 355 class RegPressureTracker { 356 const MachineFunction *MF = nullptr; 357 const TargetRegisterInfo *TRI = nullptr; 358 const RegisterClassInfo *RCI = nullptr; 359 const MachineRegisterInfo *MRI; 360 const LiveIntervals *LIS = nullptr; 361 362 /// We currently only allow pressure tracking within a block. 363 const MachineBasicBlock *MBB = nullptr; 364 365 /// Track the max pressure within the region traversed so far. 366 RegisterPressure &P; 367 368 /// Run in two modes dependending on whether constructed with IntervalPressure 369 /// or RegisterPressure. If requireIntervals is false, LIS are ignored. 370 bool RequireIntervals; 371 372 /// True if UntiedDefs will be populated. 373 bool TrackUntiedDefs = false; 374 375 /// True if lanemasks should be tracked. 376 bool TrackLaneMasks = false; 377 378 /// Register pressure corresponds to liveness before this instruction 379 /// iterator. It may point to the end of the block or a DebugValue rather than 380 /// an instruction. 381 MachineBasicBlock::const_iterator CurrPos; 382 383 /// Pressure map indexed by pressure set ID, not class ID. 384 std::vector<unsigned> CurrSetPressure; 385 386 /// Set of live registers. 387 LiveRegSet LiveRegs; 388 389 /// Set of vreg defs that start a live range. 390 SparseSet<unsigned, VirtReg2IndexFunctor> UntiedDefs; 391 /// Live-through pressure. 392 std::vector<unsigned> LiveThruPressure; 393 394 public: RegPressureTracker(IntervalPressure & rp)395 RegPressureTracker(IntervalPressure &rp) : P(rp), RequireIntervals(true) {} RegPressureTracker(RegionPressure & rp)396 RegPressureTracker(RegionPressure &rp) : P(rp), RequireIntervals(false) {} 397 398 void reset(); 399 400 void init(const MachineFunction *mf, const RegisterClassInfo *rci, 401 const LiveIntervals *lis, const MachineBasicBlock *mbb, 402 MachineBasicBlock::const_iterator pos, 403 bool TrackLaneMasks, bool TrackUntiedDefs); 404 405 /// Force liveness of virtual registers or physical register 406 /// units. Particularly useful to initialize the livein/out state of the 407 /// tracker before the first call to advance/recede. 408 void addLiveRegs(ArrayRef<RegisterMaskPair> Regs); 409 410 /// Get the MI position corresponding to this register pressure. getPos()411 MachineBasicBlock::const_iterator getPos() const { return CurrPos; } 412 413 // Reset the MI position corresponding to the register pressure. This allows 414 // schedulers to move instructions above the RegPressureTracker's 415 // CurrPos. Since the pressure is computed before CurrPos, the iterator 416 // position changes while pressure does not. setPos(MachineBasicBlock::const_iterator Pos)417 void setPos(MachineBasicBlock::const_iterator Pos) { CurrPos = Pos; } 418 419 /// Recede across the previous instruction. 420 void recede(SmallVectorImpl<RegisterMaskPair> *LiveUses = nullptr); 421 422 /// Recede across the previous instruction. 423 /// This "low-level" variant assumes that recedeSkipDebugValues() was 424 /// called previously and takes precomputed RegisterOperands for the 425 /// instruction. 426 void recede(const RegisterOperands &RegOpers, 427 SmallVectorImpl<RegisterMaskPair> *LiveUses = nullptr); 428 429 /// Recede until we find an instruction which is not a DebugValue. 430 void recedeSkipDebugValues(); 431 432 /// Advance across the current instruction. 433 void advance(); 434 435 /// Advance across the current instruction. 436 /// This is a "low-level" variant of advance() which takes precomputed 437 /// RegisterOperands of the instruction. 438 void advance(const RegisterOperands &RegOpers); 439 440 /// Finalize the region boundaries and recored live ins and live outs. 441 void closeRegion(); 442 443 /// Initialize the LiveThru pressure set based on the untied defs found in 444 /// RPTracker. 445 void initLiveThru(const RegPressureTracker &RPTracker); 446 447 /// Copy an existing live thru pressure result. initLiveThru(ArrayRef<unsigned> PressureSet)448 void initLiveThru(ArrayRef<unsigned> PressureSet) { 449 LiveThruPressure.assign(PressureSet.begin(), PressureSet.end()); 450 } 451 getLiveThru()452 ArrayRef<unsigned> getLiveThru() const { return LiveThruPressure; } 453 454 /// Get the resulting register pressure over the traversed region. 455 /// This result is complete if closeRegion() was explicitly invoked. getPressure()456 RegisterPressure &getPressure() { return P; } getPressure()457 const RegisterPressure &getPressure() const { return P; } 458 459 /// Get the register set pressure at the current position, which may be less 460 /// than the pressure across the traversed region. getRegSetPressureAtPos()461 const std::vector<unsigned> &getRegSetPressureAtPos() const { 462 return CurrSetPressure; 463 } 464 465 bool isTopClosed() const; 466 bool isBottomClosed() const; 467 468 void closeTop(); 469 void closeBottom(); 470 471 /// Consider the pressure increase caused by traversing this instruction 472 /// bottom-up. Find the pressure set with the most change beyond its pressure 473 /// limit based on the tracker's current pressure, and record the number of 474 /// excess register units of that pressure set introduced by this instruction. 475 void getMaxUpwardPressureDelta(const MachineInstr *MI, 476 PressureDiff *PDiff, 477 RegPressureDelta &Delta, 478 ArrayRef<PressureChange> CriticalPSets, 479 ArrayRef<unsigned> MaxPressureLimit); 480 481 void getUpwardPressureDelta(const MachineInstr *MI, 482 /*const*/ PressureDiff &PDiff, 483 RegPressureDelta &Delta, 484 ArrayRef<PressureChange> CriticalPSets, 485 ArrayRef<unsigned> MaxPressureLimit) const; 486 487 /// Consider the pressure increase caused by traversing this instruction 488 /// top-down. Find the pressure set with the most change beyond its pressure 489 /// limit based on the tracker's current pressure, and record the number of 490 /// excess register units of that pressure set introduced by this instruction. 491 void getMaxDownwardPressureDelta(const MachineInstr *MI, 492 RegPressureDelta &Delta, 493 ArrayRef<PressureChange> CriticalPSets, 494 ArrayRef<unsigned> MaxPressureLimit); 495 496 /// Find the pressure set with the most change beyond its pressure limit after 497 /// traversing this instruction either upward or downward depending on the 498 /// closed end of the current region. getMaxPressureDelta(const MachineInstr * MI,RegPressureDelta & Delta,ArrayRef<PressureChange> CriticalPSets,ArrayRef<unsigned> MaxPressureLimit)499 void getMaxPressureDelta(const MachineInstr *MI, 500 RegPressureDelta &Delta, 501 ArrayRef<PressureChange> CriticalPSets, 502 ArrayRef<unsigned> MaxPressureLimit) { 503 if (isTopClosed()) 504 return getMaxDownwardPressureDelta(MI, Delta, CriticalPSets, 505 MaxPressureLimit); 506 507 assert(isBottomClosed() && "Uninitialized pressure tracker"); 508 return getMaxUpwardPressureDelta(MI, nullptr, Delta, CriticalPSets, 509 MaxPressureLimit); 510 } 511 512 /// Get the pressure of each PSet after traversing this instruction bottom-up. 513 void getUpwardPressure(const MachineInstr *MI, 514 std::vector<unsigned> &PressureResult, 515 std::vector<unsigned> &MaxPressureResult); 516 517 /// Get the pressure of each PSet after traversing this instruction top-down. 518 void getDownwardPressure(const MachineInstr *MI, 519 std::vector<unsigned> &PressureResult, 520 std::vector<unsigned> &MaxPressureResult); 521 getPressureAfterInst(const MachineInstr * MI,std::vector<unsigned> & PressureResult,std::vector<unsigned> & MaxPressureResult)522 void getPressureAfterInst(const MachineInstr *MI, 523 std::vector<unsigned> &PressureResult, 524 std::vector<unsigned> &MaxPressureResult) { 525 if (isTopClosed()) 526 return getUpwardPressure(MI, PressureResult, MaxPressureResult); 527 528 assert(isBottomClosed() && "Uninitialized pressure tracker"); 529 return getDownwardPressure(MI, PressureResult, MaxPressureResult); 530 } 531 hasUntiedDef(unsigned VirtReg)532 bool hasUntiedDef(unsigned VirtReg) const { 533 return UntiedDefs.count(VirtReg); 534 } 535 536 void dump() const; 537 538 protected: 539 /// Add Reg to the live out set and increase max pressure. 540 void discoverLiveOut(RegisterMaskPair Pair); 541 /// Add Reg to the live in set and increase max pressure. 542 void discoverLiveIn(RegisterMaskPair Pair); 543 544 /// Get the SlotIndex for the first nondebug instruction including or 545 /// after the current position. 546 SlotIndex getCurrSlot() const; 547 548 void increaseRegPressure(unsigned RegUnit, LaneBitmask PreviousMask, 549 LaneBitmask NewMask); 550 void decreaseRegPressure(unsigned RegUnit, LaneBitmask PreviousMask, 551 LaneBitmask NewMask); 552 553 void bumpDeadDefs(ArrayRef<RegisterMaskPair> DeadDefs); 554 555 void bumpUpwardPressure(const MachineInstr *MI); 556 void bumpDownwardPressure(const MachineInstr *MI); 557 558 void discoverLiveInOrOut(RegisterMaskPair Pair, 559 SmallVectorImpl<RegisterMaskPair> &LiveInOrOut); 560 561 LaneBitmask getLastUsedLanes(unsigned RegUnit, SlotIndex Pos) const; 562 LaneBitmask getLiveLanesAt(unsigned RegUnit, SlotIndex Pos) const; 563 LaneBitmask getLiveThroughAt(unsigned RegUnit, SlotIndex Pos) const; 564 }; 565 566 void dumpRegSetPressure(ArrayRef<unsigned> SetPressure, 567 const TargetRegisterInfo *TRI); 568 569 } // end namespace llvm 570 571 #endif // LLVM_CODEGEN_REGISTERPRESSURE_H 572