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