1239310Sdim//===-- RegisterPressure.h - Dynamic Register Pressure -*- C++ -*-------===// 2239310Sdim// 3239310Sdim// The LLVM Compiler Infrastructure 4239310Sdim// 5239310Sdim// This file is distributed under the University of Illinois Open Source 6239310Sdim// License. See LICENSE.TXT for details. 7239310Sdim// 8239310Sdim//===----------------------------------------------------------------------===// 9239310Sdim// 10239310Sdim// This file defines the RegisterPressure class which can be used to track 11239310Sdim// MachineInstr level register pressure. 12239310Sdim// 13239310Sdim//===----------------------------------------------------------------------===// 14239310Sdim 15239310Sdim#ifndef LLVM_CODEGEN_REGISTERPRESSURE_H 16239310Sdim#define LLVM_CODEGEN_REGISTERPRESSURE_H 17239310Sdim 18249423Sdim#include "llvm/ADT/SparseSet.h" 19239310Sdim#include "llvm/CodeGen/SlotIndexes.h" 20239310Sdim#include "llvm/Target/TargetRegisterInfo.h" 21239310Sdim 22239310Sdimnamespace llvm { 23239310Sdim 24239310Sdimclass LiveIntervals; 25263508Sdimclass LiveRange; 26239310Sdimclass RegisterClassInfo; 27239310Sdimclass MachineInstr; 28239310Sdim 29239310Sdim/// Base class for register pressure results. 30239310Sdimstruct RegisterPressure { 31239310Sdim /// Map of max reg pressure indexed by pressure set ID, not class ID. 32239310Sdim std::vector<unsigned> MaxSetPressure; 33239310Sdim 34249423Sdim /// List of live in virtual registers or physical register units. 35239310Sdim SmallVector<unsigned,8> LiveInRegs; 36239310Sdim SmallVector<unsigned,8> LiveOutRegs; 37239310Sdim 38239310Sdim /// Increase register pressure for each pressure set impacted by this register 39239310Sdim /// class. Normally called by RegPressureTracker, but may be called manually 40239310Sdim /// to account for live through (global liveness). 41249423Sdim /// 42249423Sdim /// \param Reg is either a virtual register number or register unit number. 43249423Sdim void increase(unsigned Reg, const TargetRegisterInfo *TRI, 44249423Sdim const MachineRegisterInfo *MRI); 45239310Sdim 46239310Sdim /// Decrease register pressure for each pressure set impacted by this register 47239310Sdim /// class. This is only useful to account for spilling or rematerialization. 48249423Sdim /// 49249423Sdim /// \param Reg is either a virtual register number or register unit number. 50249423Sdim void decrease(unsigned Reg, const TargetRegisterInfo *TRI, 51249423Sdim const MachineRegisterInfo *MRI); 52239310Sdim 53243830Sdim void dump(const TargetRegisterInfo *TRI) const; 54239310Sdim}; 55239310Sdim 56239310Sdim/// RegisterPressure computed within a region of instructions delimited by 57239310Sdim/// TopIdx and BottomIdx. During pressure computation, the maximum pressure per 58239310Sdim/// register pressure set is increased. Once pressure within a region is fully 59239310Sdim/// computed, the live-in and live-out sets are recorded. 60239310Sdim/// 61239310Sdim/// This is preferable to RegionPressure when LiveIntervals are available, 62239310Sdim/// because delimiting regions by SlotIndex is more robust and convenient than 63239310Sdim/// holding block iterators. The block contents can change without invalidating 64239310Sdim/// the pressure result. 65239310Sdimstruct IntervalPressure : RegisterPressure { 66239310Sdim /// Record the boundary of the region being tracked. 67239310Sdim SlotIndex TopIdx; 68239310Sdim SlotIndex BottomIdx; 69239310Sdim 70239310Sdim void reset(); 71239310Sdim 72239310Sdim void openTop(SlotIndex NextTop); 73239310Sdim 74239310Sdim void openBottom(SlotIndex PrevBottom); 75239310Sdim}; 76239310Sdim 77239310Sdim/// RegisterPressure computed within a region of instructions delimited by 78239310Sdim/// TopPos and BottomPos. This is a less precise version of IntervalPressure for 79239310Sdim/// use when LiveIntervals are unavailable. 80239310Sdimstruct RegionPressure : RegisterPressure { 81239310Sdim /// Record the boundary of the region being tracked. 82239310Sdim MachineBasicBlock::const_iterator TopPos; 83239310Sdim MachineBasicBlock::const_iterator BottomPos; 84239310Sdim 85239310Sdim void reset(); 86239310Sdim 87239310Sdim void openTop(MachineBasicBlock::const_iterator PrevTop); 88239310Sdim 89239310Sdim void openBottom(MachineBasicBlock::const_iterator PrevBottom); 90239310Sdim}; 91239310Sdim 92263508Sdim/// Capture a change in pressure for a single pressure set. UnitInc may be 93263508Sdim/// expressed in terms of upward or downward pressure depending on the client 94263508Sdim/// and will be dynamically adjusted for current liveness. 95263508Sdim/// 96263508Sdim/// Pressure increments are tiny, typically 1-2 units, and this is only for 97263508Sdim/// heuristics, so we don't check UnitInc overflow. Instead, we may have a 98263508Sdim/// higher level assert that pressure is consistent within a region. We also 99263508Sdim/// effectively ignore dead defs which don't affect heuristics much. 100263508Sdimclass PressureChange { 101263508Sdim uint16_t PSetID; // ID+1. 0=Invalid. 102263508Sdim int16_t UnitInc; 103263508Sdimpublic: 104263508Sdim PressureChange(): PSetID(0), UnitInc(0) {} 105263508Sdim PressureChange(unsigned id): PSetID(id+1), UnitInc(0) { 106263508Sdim assert(id < UINT16_MAX && "PSetID overflow."); 107263508Sdim } 108239310Sdim 109263508Sdim bool isValid() const { return PSetID > 0; } 110239310Sdim 111263508Sdim unsigned getPSet() const { 112263508Sdim assert(isValid() && "invalid PressureChange"); 113263508Sdim return PSetID - 1; 114263508Sdim } 115263508Sdim // If PSetID is invalid, return UINT16_MAX to give it lowest priority. 116263508Sdim unsigned getPSetOrMax() const { return (PSetID - 1) & UINT16_MAX; } 117263508Sdim 118263508Sdim int getUnitInc() const { return UnitInc; } 119263508Sdim 120263508Sdim void setUnitInc(int Inc) { UnitInc = Inc; } 121263508Sdim 122263508Sdim bool operator==(const PressureChange &RHS) const { 123263508Sdim return PSetID == RHS.PSetID && UnitInc == RHS.UnitInc; 124263508Sdim } 125239310Sdim}; 126239310Sdim 127263508Sdimtemplate <> struct isPodLike<PressureChange> { 128263508Sdim static const bool value = true; 129263508Sdim}; 130263508Sdim 131263508Sdim/// List of PressureChanges in order of increasing, unique PSetID. 132263508Sdim/// 133263508Sdim/// Use a small fixed number, because we can fit more PressureChanges in an 134263508Sdim/// empty SmallVector than ever need to be tracked per register class. If more 135263508Sdim/// PSets are affected, then we only track the most constrained. 136263508Sdimclass PressureDiff { 137263508Sdim // The initial design was for MaxPSets=4, but that requires PSet partitions, 138263508Sdim // which are not yet implemented. (PSet partitions are equivalent PSets given 139263508Sdim // the register classes actually in use within the scheduling region.) 140263508Sdim enum { MaxPSets = 16 }; 141263508Sdim 142263508Sdim PressureChange PressureChanges[MaxPSets]; 143263508Sdimpublic: 144263508Sdim typedef PressureChange* iterator; 145263508Sdim typedef const PressureChange* const_iterator; 146263508Sdim iterator begin() { return &PressureChanges[0]; } 147263508Sdim iterator end() { return &PressureChanges[MaxPSets]; } 148263508Sdim const_iterator begin() const { return &PressureChanges[0]; } 149263508Sdim const_iterator end() const { return &PressureChanges[MaxPSets]; } 150263508Sdim 151263508Sdim void addPressureChange(unsigned RegUnit, bool IsDec, 152263508Sdim const MachineRegisterInfo *MRI); 153263508Sdim}; 154263508Sdim 155263508Sdim/// Array of PressureDiffs. 156263508Sdimclass PressureDiffs { 157263508Sdim PressureDiff *PDiffArray; 158263508Sdim unsigned Size; 159263508Sdim unsigned Max; 160263508Sdimpublic: 161263508Sdim PressureDiffs(): PDiffArray(0), Size(0), Max(0) {} 162263508Sdim ~PressureDiffs() { free(PDiffArray); } 163263508Sdim 164263508Sdim void clear() { Size = 0; } 165263508Sdim 166263508Sdim void init(unsigned N); 167263508Sdim 168263508Sdim PressureDiff &operator[](unsigned Idx) { 169263508Sdim assert(Idx < Size && "PressureDiff index out of bounds"); 170263508Sdim return PDiffArray[Idx]; 171263508Sdim } 172263508Sdim const PressureDiff &operator[](unsigned Idx) const { 173263508Sdim return const_cast<PressureDiffs*>(this)->operator[](Idx); 174263508Sdim } 175263508Sdim}; 176263508Sdim 177239310Sdim/// Store the effects of a change in pressure on things that MI scheduler cares 178239310Sdim/// about. 179239310Sdim/// 180239310Sdim/// Excess records the value of the largest difference in register units beyond 181239310Sdim/// the target's pressure limits across the affected pressure sets, where 182239310Sdim/// largest is defined as the absolute value of the difference. Negative 183239310Sdim/// ExcessUnits indicates a reduction in pressure that had already exceeded the 184239310Sdim/// target's limits. 185239310Sdim/// 186239310Sdim/// CriticalMax records the largest increase in the tracker's max pressure that 187239310Sdim/// exceeds the critical limit for some pressure set determined by the client. 188239310Sdim/// 189239310Sdim/// CurrentMax records the largest increase in the tracker's max pressure that 190239310Sdim/// exceeds the current limit for some pressure set determined by the client. 191239310Sdimstruct RegPressureDelta { 192263508Sdim PressureChange Excess; 193263508Sdim PressureChange CriticalMax; 194263508Sdim PressureChange CurrentMax; 195239310Sdim 196239310Sdim RegPressureDelta() {} 197263508Sdim 198263508Sdim bool operator==(const RegPressureDelta &RHS) const { 199263508Sdim return Excess == RHS.Excess && CriticalMax == RHS.CriticalMax 200263508Sdim && CurrentMax == RHS.CurrentMax; 201263508Sdim } 202263508Sdim bool operator!=(const RegPressureDelta &RHS) const { 203263508Sdim return !operator==(RHS); 204263508Sdim } 205239310Sdim}; 206239310Sdim 207249423Sdim/// \brief A set of live virtual registers and physical register units. 208249423Sdim/// 209249423Sdim/// Virtual and physical register numbers require separate sparse sets, but most 210249423Sdim/// of the RegisterPressureTracker handles them uniformly. 211249423Sdimstruct LiveRegSet { 212249423Sdim SparseSet<unsigned> PhysRegs; 213249423Sdim SparseSet<unsigned, VirtReg2IndexFunctor> VirtRegs; 214249423Sdim 215263508Sdim bool contains(unsigned Reg) const { 216249423Sdim if (TargetRegisterInfo::isVirtualRegister(Reg)) 217249423Sdim return VirtRegs.count(Reg); 218249423Sdim return PhysRegs.count(Reg); 219249423Sdim } 220249423Sdim 221249423Sdim bool insert(unsigned Reg) { 222249423Sdim if (TargetRegisterInfo::isVirtualRegister(Reg)) 223249423Sdim return VirtRegs.insert(Reg).second; 224249423Sdim return PhysRegs.insert(Reg).second; 225249423Sdim } 226249423Sdim 227249423Sdim bool erase(unsigned Reg) { 228249423Sdim if (TargetRegisterInfo::isVirtualRegister(Reg)) 229249423Sdim return VirtRegs.erase(Reg); 230249423Sdim return PhysRegs.erase(Reg); 231249423Sdim } 232249423Sdim}; 233249423Sdim 234239310Sdim/// Track the current register pressure at some position in the instruction 235239310Sdim/// stream, and remember the high water mark within the region traversed. This 236239310Sdim/// does not automatically consider live-through ranges. The client may 237239310Sdim/// independently adjust for global liveness. 238239310Sdim/// 239239310Sdim/// Each RegPressureTracker only works within a MachineBasicBlock. Pressure can 240239310Sdim/// be tracked across a larger region by storing a RegisterPressure result at 241239310Sdim/// each block boundary and explicitly adjusting pressure to account for block 242239310Sdim/// live-in and live-out register sets. 243239310Sdim/// 244239310Sdim/// RegPressureTracker holds a reference to a RegisterPressure result that it 245239310Sdim/// computes incrementally. During downward tracking, P.BottomIdx or P.BottomPos 246239310Sdim/// is invalid until it reaches the end of the block or closeRegion() is 247239310Sdim/// explicitly called. Similarly, P.TopIdx is invalid during upward 248239310Sdim/// tracking. Changing direction has the side effect of closing region, and 249239310Sdim/// traversing past TopIdx or BottomIdx reopens it. 250239310Sdimclass RegPressureTracker { 251239310Sdim const MachineFunction *MF; 252239310Sdim const TargetRegisterInfo *TRI; 253239310Sdim const RegisterClassInfo *RCI; 254239310Sdim const MachineRegisterInfo *MRI; 255239310Sdim const LiveIntervals *LIS; 256239310Sdim 257239310Sdim /// We currently only allow pressure tracking within a block. 258239310Sdim const MachineBasicBlock *MBB; 259239310Sdim 260239310Sdim /// Track the max pressure within the region traversed so far. 261239310Sdim RegisterPressure &P; 262239310Sdim 263239310Sdim /// Run in two modes dependending on whether constructed with IntervalPressure 264239310Sdim /// or RegisterPressure. If requireIntervals is false, LIS are ignored. 265239310Sdim bool RequireIntervals; 266239310Sdim 267263508Sdim /// True if UntiedDefs will be populated. 268263508Sdim bool TrackUntiedDefs; 269263508Sdim 270239310Sdim /// Register pressure corresponds to liveness before this instruction 271249423Sdim /// iterator. It may point to the end of the block or a DebugValue rather than 272249423Sdim /// an instruction. 273239310Sdim MachineBasicBlock::const_iterator CurrPos; 274239310Sdim 275239310Sdim /// Pressure map indexed by pressure set ID, not class ID. 276239310Sdim std::vector<unsigned> CurrSetPressure; 277239310Sdim 278249423Sdim /// Set of live registers. 279249423Sdim LiveRegSet LiveRegs; 280239310Sdim 281263508Sdim /// Set of vreg defs that start a live range. 282263508Sdim SparseSet<unsigned, VirtReg2IndexFunctor> UntiedDefs; 283263508Sdim /// Live-through pressure. 284263508Sdim std::vector<unsigned> LiveThruPressure; 285263508Sdim 286239310Sdimpublic: 287239310Sdim RegPressureTracker(IntervalPressure &rp) : 288263508Sdim MF(0), TRI(0), RCI(0), LIS(0), MBB(0), P(rp), RequireIntervals(true), 289263508Sdim TrackUntiedDefs(false) {} 290239310Sdim 291239310Sdim RegPressureTracker(RegionPressure &rp) : 292263508Sdim MF(0), TRI(0), RCI(0), LIS(0), MBB(0), P(rp), RequireIntervals(false), 293263508Sdim TrackUntiedDefs(false) {} 294239310Sdim 295263508Sdim void reset(); 296263508Sdim 297239310Sdim void init(const MachineFunction *mf, const RegisterClassInfo *rci, 298239310Sdim const LiveIntervals *lis, const MachineBasicBlock *mbb, 299263508Sdim MachineBasicBlock::const_iterator pos, 300263508Sdim bool ShouldTrackUntiedDefs = false); 301239310Sdim 302249423Sdim /// Force liveness of virtual registers or physical register 303249423Sdim /// units. Particularly useful to initialize the livein/out state of the 304249423Sdim /// tracker before the first call to advance/recede. 305239310Sdim void addLiveRegs(ArrayRef<unsigned> Regs); 306239310Sdim 307239310Sdim /// Get the MI position corresponding to this register pressure. 308239310Sdim MachineBasicBlock::const_iterator getPos() const { return CurrPos; } 309239310Sdim 310239310Sdim // Reset the MI position corresponding to the register pressure. This allows 311239310Sdim // schedulers to move instructions above the RegPressureTracker's 312239310Sdim // CurrPos. Since the pressure is computed before CurrPos, the iterator 313239310Sdim // position changes while pressure does not. 314239310Sdim void setPos(MachineBasicBlock::const_iterator Pos) { CurrPos = Pos; } 315239310Sdim 316249423Sdim /// \brief Get the SlotIndex for the first nondebug instruction including or 317249423Sdim /// after the current position. 318249423Sdim SlotIndex getCurrSlot() const; 319249423Sdim 320239310Sdim /// Recede across the previous instruction. 321263508Sdim bool recede(SmallVectorImpl<unsigned> *LiveUses = 0, PressureDiff *PDiff = 0); 322239310Sdim 323239310Sdim /// Advance across the current instruction. 324239310Sdim bool advance(); 325239310Sdim 326239310Sdim /// Finalize the region boundaries and recored live ins and live outs. 327239310Sdim void closeRegion(); 328239310Sdim 329263508Sdim /// Initialize the LiveThru pressure set based on the untied defs found in 330263508Sdim /// RPTracker. 331263508Sdim void initLiveThru(const RegPressureTracker &RPTracker); 332263508Sdim 333263508Sdim /// Copy an existing live thru pressure result. 334263508Sdim void initLiveThru(ArrayRef<unsigned> PressureSet) { 335263508Sdim LiveThruPressure.assign(PressureSet.begin(), PressureSet.end()); 336263508Sdim } 337263508Sdim 338263508Sdim ArrayRef<unsigned> getLiveThru() const { return LiveThruPressure; } 339263508Sdim 340239310Sdim /// Get the resulting register pressure over the traversed region. 341239310Sdim /// This result is complete if either advance() or recede() has returned true, 342239310Sdim /// or if closeRegion() was explicitly invoked. 343239310Sdim RegisterPressure &getPressure() { return P; } 344243830Sdim const RegisterPressure &getPressure() const { return P; } 345239310Sdim 346239310Sdim /// Get the register set pressure at the current position, which may be less 347239310Sdim /// than the pressure across the traversed region. 348239310Sdim std::vector<unsigned> &getRegSetPressureAtPos() { return CurrSetPressure; } 349239310Sdim 350249423Sdim void discoverLiveOut(unsigned Reg); 351249423Sdim void discoverLiveIn(unsigned Reg); 352239310Sdim 353239310Sdim bool isTopClosed() const; 354239310Sdim bool isBottomClosed() const; 355239310Sdim 356239310Sdim void closeTop(); 357239310Sdim void closeBottom(); 358239310Sdim 359239310Sdim /// Consider the pressure increase caused by traversing this instruction 360239310Sdim /// bottom-up. Find the pressure set with the most change beyond its pressure 361239310Sdim /// limit based on the tracker's current pressure, and record the number of 362239310Sdim /// excess register units of that pressure set introduced by this instruction. 363239310Sdim void getMaxUpwardPressureDelta(const MachineInstr *MI, 364263508Sdim PressureDiff *PDiff, 365239310Sdim RegPressureDelta &Delta, 366263508Sdim ArrayRef<PressureChange> CriticalPSets, 367239310Sdim ArrayRef<unsigned> MaxPressureLimit); 368239310Sdim 369263508Sdim void getUpwardPressureDelta(const MachineInstr *MI, 370263508Sdim /*const*/ PressureDiff &PDiff, 371263508Sdim RegPressureDelta &Delta, 372263508Sdim ArrayRef<PressureChange> CriticalPSets, 373263508Sdim ArrayRef<unsigned> MaxPressureLimit) const; 374263508Sdim 375239310Sdim /// Consider the pressure increase caused by traversing this instruction 376239310Sdim /// top-down. Find the pressure set with the most change beyond its pressure 377239310Sdim /// limit based on the tracker's current pressure, and record the number of 378239310Sdim /// excess register units of that pressure set introduced by this instruction. 379239310Sdim void getMaxDownwardPressureDelta(const MachineInstr *MI, 380239310Sdim RegPressureDelta &Delta, 381263508Sdim ArrayRef<PressureChange> CriticalPSets, 382239310Sdim ArrayRef<unsigned> MaxPressureLimit); 383239310Sdim 384239310Sdim /// Find the pressure set with the most change beyond its pressure limit after 385239310Sdim /// traversing this instruction either upward or downward depending on the 386239310Sdim /// closed end of the current region. 387263508Sdim void getMaxPressureDelta(const MachineInstr *MI, 388263508Sdim RegPressureDelta &Delta, 389263508Sdim ArrayRef<PressureChange> CriticalPSets, 390239310Sdim ArrayRef<unsigned> MaxPressureLimit) { 391239310Sdim if (isTopClosed()) 392239310Sdim return getMaxDownwardPressureDelta(MI, Delta, CriticalPSets, 393239310Sdim MaxPressureLimit); 394239310Sdim 395239310Sdim assert(isBottomClosed() && "Uninitialized pressure tracker"); 396263508Sdim return getMaxUpwardPressureDelta(MI, 0, Delta, CriticalPSets, 397239310Sdim MaxPressureLimit); 398239310Sdim } 399239310Sdim 400239310Sdim /// Get the pressure of each PSet after traversing this instruction bottom-up. 401239310Sdim void getUpwardPressure(const MachineInstr *MI, 402239310Sdim std::vector<unsigned> &PressureResult, 403239310Sdim std::vector<unsigned> &MaxPressureResult); 404239310Sdim 405239310Sdim /// Get the pressure of each PSet after traversing this instruction top-down. 406239310Sdim void getDownwardPressure(const MachineInstr *MI, 407239310Sdim std::vector<unsigned> &PressureResult, 408239310Sdim std::vector<unsigned> &MaxPressureResult); 409239310Sdim 410239310Sdim void getPressureAfterInst(const MachineInstr *MI, 411239310Sdim std::vector<unsigned> &PressureResult, 412239310Sdim std::vector<unsigned> &MaxPressureResult) { 413239310Sdim if (isTopClosed()) 414239310Sdim return getUpwardPressure(MI, PressureResult, MaxPressureResult); 415239310Sdim 416239310Sdim assert(isBottomClosed() && "Uninitialized pressure tracker"); 417239310Sdim return getDownwardPressure(MI, PressureResult, MaxPressureResult); 418239310Sdim } 419239310Sdim 420263508Sdim bool hasUntiedDef(unsigned VirtReg) const { 421263508Sdim return UntiedDefs.count(VirtReg); 422263508Sdim } 423263508Sdim 424249423Sdim void dump() const; 425249423Sdim 426239310Sdimprotected: 427263508Sdim const LiveRange *getLiveRange(unsigned Reg) const; 428239310Sdim 429249423Sdim void increaseRegPressure(ArrayRef<unsigned> Regs); 430249423Sdim void decreaseRegPressure(ArrayRef<unsigned> Regs); 431239310Sdim 432239310Sdim void bumpUpwardPressure(const MachineInstr *MI); 433239310Sdim void bumpDownwardPressure(const MachineInstr *MI); 434239310Sdim}; 435263508Sdim 436263508Sdim#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP) 437263508Sdimvoid dumpRegSetPressure(ArrayRef<unsigned> SetPressure, 438263508Sdim const TargetRegisterInfo *TRI); 439263508Sdim#endif 440239310Sdim} // end namespace llvm 441239310Sdim 442239310Sdim#endif 443