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