include/llvm/CodeGen/RegisterPressure.h

   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/SparseSet.h"
  19 #include "llvm/CodeGen/SlotIndexes.h"
  20 #include "llvm/Target/TargetRegisterInfo.h"
  21
  22 namespace llvm {
  23
  24 class LiveIntervals;
  25 class LiveRange;
  26 class RegisterClassInfo;
  27 class MachineInstr;
  28
  29 /// Base class for register pressure results.
  30 struct RegisterPressure {
  31   /// Map of max reg pressure indexed by pressure set ID, not class ID.
  32   std::vector<unsigned> MaxSetPressure;
  33
  34   void dump(const TargetRegisterInfo *TRI) const;
  35 };
  36
  37 /// RegisterPressure computed within a region of instructions delimited by
  38 /// TopIdx and BottomIdx.  During pressure computation, the maximum pressure per
  39 /// register pressure set is increased. Once pressure within a region is fully
  40 /// computed, the live-in and live-out sets are recorded.
  41 ///
  42 /// This is preferable to RegionPressure when LiveIntervals are available,
  43 /// because delimiting regions by SlotIndex is more robust and convenient than
  44 /// holding block iterators. The block contents can change without invalidating
  45 /// the pressure result.
  46 struct IntervalPressure : RegisterPressure {
  47   /// Record the boundary of the region being tracked.
  48   SlotIndex TopIdx;
  49   SlotIndex BottomIdx;
  50
  51   void reset();
  52
  53   void openTop(SlotIndex NextTop);
  54
  55   void openBottom(SlotIndex PrevBottom);
  56 };
  57
  58 /// RegisterPressure computed within a region of instructions delimited by
  59 /// TopPos and BottomPos. This is a less precise version of IntervalPressure for
  60 /// use when LiveIntervals are unavailable.
  61 struct RegionPressure : RegisterPressure {
  62   /// Record the boundary of the region being tracked.
  63   MachineBasicBlock::const_iterator TopPos;
  64   MachineBasicBlock::const_iterator BottomPos;
  65
  66   void reset();
  67
  68   void openTop(MachineBasicBlock::const_iterator PrevTop);
  69
  70   void openBottom(MachineBasicBlock::const_iterator PrevBottom);
  71 };
  72
  73 /// Capture a change in pressure for a single pressure set. UnitInc may be
  74 /// expressed in terms of upward or downward pressure depending on the client
  75 /// and will be dynamically adjusted for current liveness.
  76 ///
  77 /// Pressure increments are tiny, typically 1-2 units, and this is only for
  78 /// heuristics, so we don't check UnitInc overflow. Instead, we may have a
  79 /// higher level assert that pressure is consistent within a region. We also
  80 /// effectively ignore dead defs which don't affect heuristics much.
  81 class PressureChange {
  82   uint16_t PSetID; // ID+1. 0=Invalid.
  83   int16_t  UnitInc;
  84 public:
  85   PressureChange(): PSetID(0), UnitInc(0) {}
  86   PressureChange(unsigned id): PSetID(id+1), UnitInc(0) {
  87     assert(id < UINT16_MAX && "PSetID overflow.");
  88   }
  89
  90   bool isValid() const { return PSetID > 0; }
  91
  92   unsigned getPSet() const {
  93     assert(isValid() && "invalid PressureChange");
  94     return PSetID - 1;
  95   }
  96   // If PSetID is invalid, return UINT16_MAX to give it lowest priority.
  97   unsigned getPSetOrMax() const { return (PSetID - 1) & UINT16_MAX; }
  98
  99   int getUnitInc() const { return UnitInc; }
 100
 101   void setUnitInc(int Inc) { UnitInc = Inc; }
 102
 103   bool operator==(const PressureChange &RHS) const {
 104     return PSetID == RHS.PSetID && UnitInc == RHS.UnitInc;
 105   }
 106 };
 107
 108 template <> struct isPodLike<PressureChange> {
 109    static const bool value = true;
 110 };
 111
 112 /// List of PressureChanges in order of increasing, unique PSetID.
 113 ///
 114 /// Use a small fixed number, because we can fit more PressureChanges in an
 115 /// empty SmallVector than ever need to be tracked per register class. If more
 116 /// PSets are affected, then we only track the most constrained.
 117 class PressureDiff {
 118   // The initial design was for MaxPSets=4, but that requires PSet partitions,
 119   // which are not yet implemented. (PSet partitions are equivalent PSets given
 120   // the register classes actually in use within the scheduling region.)
 121   enum { MaxPSets = 16 };
 122
 123   PressureChange PressureChanges[MaxPSets];
 124 public:
 125   typedef PressureChange* iterator;
 126   typedef const PressureChange* const_iterator;
 127   iterator begin() { return &PressureChanges[0]; }
 128   iterator end() { return &PressureChanges[MaxPSets]; }
 129   const_iterator begin() const { return &PressureChanges[0]; }
 130   const_iterator end() const { return &PressureChanges[MaxPSets]; }
 131
 132   void addPressureChange(unsigned RegUnit, bool IsDec,
 133                          const MachineRegisterInfo *MRI);
 134
 135   LLVM_DUMP_METHOD void dump(const TargetRegisterInfo &TRI) const;
 136 };
 137
 138 /// Array of PressureDiffs.
 139 class PressureDiffs {
 140   PressureDiff *PDiffArray;
 141   unsigned Size;
 142   unsigned Max;
 143 public:
 144   PressureDiffs(): PDiffArray(nullptr), Size(0), Max(0) {}
 145   ~PressureDiffs() { free(PDiffArray); }
 146
 147   void clear() { Size = 0; }
 148
 149   void init(unsigned N);
 150
 151   PressureDiff &operator[](unsigned Idx) {
 152     assert(Idx < Size && "PressureDiff index out of bounds");
 153     return PDiffArray[Idx];
 154   }
 155   const PressureDiff &operator[](unsigned Idx) const {
 156     return const_cast<PressureDiffs*>(this)->operator[](Idx);
 157   }
 158 };
 159
 160 /// Store the effects of a change in pressure on things that MI scheduler cares
 161 /// about.
 162 ///
 163 /// Excess records the value of the largest difference in register units beyond
 164 /// the target's pressure limits across the affected pressure sets, where
 165 /// largest is defined as the absolute value of the difference. Negative
 166 /// ExcessUnits indicates a reduction in pressure that had already exceeded the
 167 /// target's limits.
 168 ///
 169 /// CriticalMax records the largest increase in the tracker's max pressure that
 170 /// exceeds the critical limit for some pressure set determined by the client.
 171 ///
 172 /// CurrentMax records the largest increase in the tracker's max pressure that
 173 /// exceeds the current limit for some pressure set determined by the client.
 174 struct RegPressureDelta {
 175   PressureChange Excess;
 176   PressureChange CriticalMax;
 177   PressureChange CurrentMax;
 178
 179   RegPressureDelta() {}
 180
 181   bool operator==(const RegPressureDelta &RHS) const {
 182     return Excess == RHS.Excess && CriticalMax == RHS.CriticalMax
 183       && CurrentMax == RHS.CurrentMax;
 184   }
 185   bool operator!=(const RegPressureDelta &RHS) const {
 186     return !operator==(RHS);
 187   }
 188 };
 189
 190 /// \brief A set of live virtual registers and physical register units.
 191 ///
 192 /// Virtual and physical register numbers require separate sparse sets, but most
 193 /// of the RegisterPressureTracker handles them uniformly.
 194 struct LiveRegSet {
 195   SparseSet<unsigned> PhysRegs;
 196   SparseSet<unsigned, VirtReg2IndexFunctor> VirtRegs;
 197
 198   bool contains(unsigned Reg) const {
 199     if (TargetRegisterInfo::isVirtualRegister(Reg))
 200       return VirtRegs.count(Reg);
 201     return PhysRegs.count(Reg);
 202   }
 203
 204   bool insert(unsigned Reg) {
 205     if (TargetRegisterInfo::isVirtualRegister(Reg))
 206       return VirtRegs.insert(Reg).second;
 207     return PhysRegs.insert(Reg).second;
 208   }
 209
 210   bool erase(unsigned Reg) {
 211     if (TargetRegisterInfo::isVirtualRegister(Reg))
 212       return VirtRegs.erase(Reg);
 213     return PhysRegs.erase(Reg);
 214   }
 215 };
 216
 217 /// Track the current register pressure at some position in the instruction
 218 /// stream, and remember the high water mark within the region traversed. This
 219 /// does not automatically consider live-through ranges. The client may
 220 /// independently adjust for global liveness.
 221 ///
 222 /// Each RegPressureTracker only works within a MachineBasicBlock. Pressure can
 223 /// be tracked across a larger region by storing a RegisterPressure result at
 224 /// each block boundary and explicitly adjusting pressure to account for block
 225 /// live-in and live-out register sets.
 226 ///
 227 /// RegPressureTracker holds a reference to a RegisterPressure result that it
 228 /// computes incrementally. During downward tracking, P.BottomIdx or P.BottomPos
 229 /// is invalid until it reaches the end of the block or closeRegion() is
 230 /// explicitly called. Similarly, P.TopIdx is invalid during upward
 231 /// tracking. Changing direction has the side effect of closing region, and
 232 /// traversing past TopIdx or BottomIdx reopens it.
 233 class RegPressureTracker {
 234   const MachineFunction     *MF;
 235   const TargetRegisterInfo  *TRI;
 236   const RegisterClassInfo   *RCI;
 237   const MachineRegisterInfo *MRI;
 238   const LiveIntervals       *LIS;
 239
 240   /// We currently only allow pressure tracking within a block.
 241   const MachineBasicBlock *MBB;
 242
 243   /// Track the max pressure within the region traversed so far.
 244   RegisterPressure &P;
 245
 246   /// Run in two modes dependending on whether constructed with IntervalPressure
 247   /// or RegisterPressure. If requireIntervals is false, LIS are ignored.
 248   bool RequireIntervals;
 249
 250   /// True if UntiedDefs will be populated.
 251   bool TrackUntiedDefs;
 252
 253   /// Register pressure corresponds to liveness before this instruction
 254   /// iterator. It may point to the end of the block or a DebugValue rather than
 255   /// an instruction.
 256   MachineBasicBlock::const_iterator CurrPos;
 257
 258   /// Pressure map indexed by pressure set ID, not class ID.
 259   std::vector<unsigned> CurrSetPressure;
 260
 261   /// Set of live registers.
 262   LiveRegSet LiveRegs;
 263
 264   /// Set of vreg defs that start a live range.
 265   SparseSet<unsigned, VirtReg2IndexFunctor> UntiedDefs;
 266   /// List of live in virtual registers or physical register units.
 267   SmallVector<unsigned,8> LiveInRegs;
 268   /// List of live out virtual registers or physical register units.
 269   SmallVector<unsigned,8> LiveOutRegs;
 270   /// Live-through pressure.
 271   std::vector<unsigned> LiveThruPressure;
 272
 273 public:
 274   RegPressureTracker(IntervalPressure &rp) :
 275     MF(nullptr), TRI(nullptr), RCI(nullptr), LIS(nullptr), MBB(nullptr), P(rp),
 276     RequireIntervals(true), TrackUntiedDefs(false) {}
 277
 278   RegPressureTracker(RegionPressure &rp) :
 279     MF(nullptr), TRI(nullptr), RCI(nullptr), LIS(nullptr), MBB(nullptr), P(rp),
 280     RequireIntervals(false), TrackUntiedDefs(false) {}
 281
 282   void reset();
 283
 284   void init(const MachineFunction *mf, const RegisterClassInfo *rci,
 285             const LiveIntervals *lis, const MachineBasicBlock *mbb,
 286             MachineBasicBlock::const_iterator pos,
 287             bool ShouldTrackUntiedDefs = false);
 288
 289   /// Force liveness of virtual registers or physical register
 290   /// units. Particularly useful to initialize the livein/out state of the
 291   /// tracker before the first call to advance/recede.
 292   void addLiveRegs(ArrayRef<unsigned> Regs);
 293
 294   /// Get the MI position corresponding to this register pressure.
 295   MachineBasicBlock::const_iterator getPos() const { return CurrPos; }
 296
 297   // Reset the MI position corresponding to the register pressure. This allows
 298   // schedulers to move instructions above the RegPressureTracker's
 299   // CurrPos. Since the pressure is computed before CurrPos, the iterator
 300   // position changes while pressure does not.
 301   void setPos(MachineBasicBlock::const_iterator Pos) { CurrPos = Pos; }
 302
 303   /// \brief Get the SlotIndex for the first nondebug instruction including or
 304   /// after the current position.
 305   SlotIndex getCurrSlot() const;
 306
 307   /// Recede across the previous instruction.
 308   bool recede(SmallVectorImpl<unsigned> *LiveUses = nullptr,
 309               PressureDiff *PDiff = nullptr);
 310
 311   /// Advance across the current instruction.
 312   bool advance();
 313
 314   /// Finalize the region boundaries and recored live ins and live outs.
 315   void closeRegion();
 316
 317   /// Initialize the LiveThru pressure set based on the untied defs found in
 318   /// RPTracker.
 319   void initLiveThru(const RegPressureTracker &RPTracker);
 320
 321   /// Copy an existing live thru pressure result.
 322   void initLiveThru(ArrayRef<unsigned> PressureSet) {
 323     LiveThruPressure.assign(PressureSet.begin(), PressureSet.end());
 324   }
 325
 326   ArrayRef<unsigned> getLiveIn() const { return LiveInRegs; }
 327   ArrayRef<unsigned> getLiveOut() const { return LiveOutRegs; }
 328   ArrayRef<unsigned> getLiveThru() const { return LiveThruPressure; }
 329
 330   /// Get the resulting register pressure over the traversed region.
 331   /// This result is complete if either advance() or recede() has returned true,
 332   /// or if closeRegion() was explicitly invoked.
 333   RegisterPressure &getPressure() { return P; }
 334   const RegisterPressure &getPressure() const { return P; }
 335
 336   /// Get the register set pressure at the current position, which may be less
 337   /// than the pressure across the traversed region.
 338   const std::vector<unsigned> &getRegSetPressureAtPos() const {
 339     return CurrSetPressure;
 340   }
 341
 342   void discoverLiveOut(unsigned Reg);
 343   void discoverLiveIn(unsigned Reg);
 344
 345   bool isTopClosed() const;
 346   bool isBottomClosed() const;
 347
 348   void closeTop();
 349   void closeBottom();
 350
 351   /// Consider the pressure increase caused by traversing this instruction
 352   /// bottom-up. Find the pressure set with the most change beyond its pressure
 353   /// limit based on the tracker's current pressure, and record the number of
 354   /// excess register units of that pressure set introduced by this instruction.
 355   void getMaxUpwardPressureDelta(const MachineInstr *MI,
 356                                  PressureDiff *PDiff,
 357                                  RegPressureDelta &Delta,
 358                                  ArrayRef<PressureChange> CriticalPSets,
 359                                  ArrayRef<unsigned> MaxPressureLimit);
 360
 361   void getUpwardPressureDelta(const MachineInstr *MI,
 362                               /*const*/ PressureDiff &PDiff,
 363                               RegPressureDelta &Delta,
 364                               ArrayRef<PressureChange> CriticalPSets,
 365                               ArrayRef<unsigned> MaxPressureLimit) const;
 366
 367   /// Consider the pressure increase caused by traversing this instruction
 368   /// top-down. Find the pressure set with the most change beyond its pressure
 369   /// limit based on the tracker's current pressure, and record the number of
 370   /// excess register units of that pressure set introduced by this instruction.
 371   void getMaxDownwardPressureDelta(const MachineInstr *MI,
 372                                    RegPressureDelta &Delta,
 373                                    ArrayRef<PressureChange> CriticalPSets,
 374                                    ArrayRef<unsigned> MaxPressureLimit);
 375
 376   /// Find the pressure set with the most change beyond its pressure limit after
 377   /// traversing this instruction either upward or downward depending on the
 378   /// closed end of the current region.
 379   void getMaxPressureDelta(const MachineInstr *MI,
 380                            RegPressureDelta &Delta,
 381                            ArrayRef<PressureChange> CriticalPSets,
 382                            ArrayRef<unsigned> MaxPressureLimit) {
 383     if (isTopClosed())
 384       return getMaxDownwardPressureDelta(MI, Delta, CriticalPSets,
 385                                          MaxPressureLimit);
 386
 387     assert(isBottomClosed() && "Uninitialized pressure tracker");
 388     return getMaxUpwardPressureDelta(MI, nullptr, Delta, CriticalPSets,
 389                                      MaxPressureLimit);
 390   }
 391
 392   /// Get the pressure of each PSet after traversing this instruction bottom-up.
 393   void getUpwardPressure(const MachineInstr *MI,
 394                          std::vector<unsigned> &PressureResult,
 395                          std::vector<unsigned> &MaxPressureResult);
 396
 397   /// Get the pressure of each PSet after traversing this instruction top-down.
 398   void getDownwardPressure(const MachineInstr *MI,
 399                            std::vector<unsigned> &PressureResult,
 400                            std::vector<unsigned> &MaxPressureResult);
 401
 402   void getPressureAfterInst(const MachineInstr *MI,
 403                             std::vector<unsigned> &PressureResult,
 404                             std::vector<unsigned> &MaxPressureResult) {
 405     if (isTopClosed())
 406       return getUpwardPressure(MI, PressureResult, MaxPressureResult);
 407
 408     assert(isBottomClosed() && "Uninitialized pressure tracker");
 409     return getDownwardPressure(MI, PressureResult, MaxPressureResult);
 410   }
 411
 412   bool hasUntiedDef(unsigned VirtReg) const {
 413     return UntiedDefs.count(VirtReg);
 414   }
 415
 416   void dump() const;
 417
 418 protected:
 419   const LiveRange *getLiveRange(unsigned Reg) const;
 420
 421   void increaseRegPressure(ArrayRef<unsigned> Regs);
 422   void decreaseRegPressure(ArrayRef<unsigned> Regs);
 423
 424   void bumpUpwardPressure(const MachineInstr *MI);
 425   void bumpDownwardPressure(const MachineInstr *MI);
 426 };
 427
 428 void dumpRegSetPressure(ArrayRef<unsigned> SetPressure,
 429                         const TargetRegisterInfo *TRI);
 430 } // end namespace llvm
 431
 432 #endif