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 32namespace llvm { 33 34class LiveIntervals; 35class MachineFunction; 36class MachineInstr; 37class MachineRegisterInfo; 38class RegisterClassInfo; 39 40struct 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. 49struct 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. 69struct 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. 84struct 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. 104class PressureChange { 105 uint16_t PSetID = 0; // ID+1. 0=Invalid. 106 int16_t UnitInc = 0; 107 108public: 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 135template <> 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. 144class 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 157public: 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. 170class RegisterOperands { 171public: 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. 201class PressureDiffs { 202 PressureDiff *PDiffArray = nullptr; 203 unsigned Size = 0; 204 unsigned Max = 0; 205 206public: 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. 242struct 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. 262class LiveRegSet { 263private: 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 293public: 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. 360class 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 399public: 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 543protected: 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 571void dumpRegSetPressure(ArrayRef<unsigned> SetPressure, 572 const TargetRegisterInfo *TRI); 573 574} // end namespace llvm 575 576#endif // LLVM_CODEGEN_REGISTERPRESSURE_H 577