LLVM API Documentation

RegisterPressure.h
Go to the documentation of this file.
00001 //===-- RegisterPressure.h - Dynamic Register Pressure -*- C++ -*-------===//
00002 //
00003 //                     The LLVM Compiler Infrastructure
00004 //
00005 // This file is distributed under the University of Illinois Open Source
00006 // License. See LICENSE.TXT for details.
00007 //
00008 //===----------------------------------------------------------------------===//
00009 //
00010 // This file defines the RegisterPressure class which can be used to track
00011 // MachineInstr level register pressure.
00012 //
00013 //===----------------------------------------------------------------------===//
00014 
00015 #ifndef LLVM_CODEGEN_REGISTERPRESSURE_H
00016 #define LLVM_CODEGEN_REGISTERPRESSURE_H
00017 
00018 #include "llvm/ADT/SparseSet.h"
00019 #include "llvm/CodeGen/SlotIndexes.h"
00020 #include "llvm/Target/TargetRegisterInfo.h"
00021 
00022 namespace llvm {
00023 
00024 class LiveIntervals;
00025 class LiveRange;
00026 class RegisterClassInfo;
00027 class MachineInstr;
00028 
00029 /// Base class for register pressure results.
00030 struct RegisterPressure {
00031   /// Map of max reg pressure indexed by pressure set ID, not class ID.
00032   std::vector<unsigned> MaxSetPressure;
00033 
00034   /// List of live in virtual registers or physical register units.
00035   SmallVector<unsigned,8> LiveInRegs;
00036   SmallVector<unsigned,8> LiveOutRegs;
00037 
00038   /// Increase register pressure for each pressure set impacted by this register
00039   /// class. Normally called by RegPressureTracker, but may be called manually
00040   /// to account for live through (global liveness).
00041   ///
00042   /// \param Reg is either a virtual register number or register unit number.
00043   void increase(unsigned Reg, const TargetRegisterInfo *TRI,
00044                 const MachineRegisterInfo *MRI);
00045 
00046   /// Decrease register pressure for each pressure set impacted by this register
00047   /// class. This is only useful to account for spilling or rematerialization.
00048   ///
00049   /// \param Reg is either a virtual register number or register unit number.
00050   void decrease(unsigned Reg, const TargetRegisterInfo *TRI,
00051                 const MachineRegisterInfo *MRI);
00052 
00053   void dump(const TargetRegisterInfo *TRI) const;
00054 };
00055 
00056 /// RegisterPressure computed within a region of instructions delimited by
00057 /// TopIdx and BottomIdx.  During pressure computation, the maximum pressure per
00058 /// register pressure set is increased. Once pressure within a region is fully
00059 /// computed, the live-in and live-out sets are recorded.
00060 ///
00061 /// This is preferable to RegionPressure when LiveIntervals are available,
00062 /// because delimiting regions by SlotIndex is more robust and convenient than
00063 /// holding block iterators. The block contents can change without invalidating
00064 /// the pressure result.
00065 struct IntervalPressure : RegisterPressure {
00066   /// Record the boundary of the region being tracked.
00067   SlotIndex TopIdx;
00068   SlotIndex BottomIdx;
00069 
00070   void reset();
00071 
00072   void openTop(SlotIndex NextTop);
00073 
00074   void openBottom(SlotIndex PrevBottom);
00075 };
00076 
00077 /// RegisterPressure computed within a region of instructions delimited by
00078 /// TopPos and BottomPos. This is a less precise version of IntervalPressure for
00079 /// use when LiveIntervals are unavailable.
00080 struct RegionPressure : RegisterPressure {
00081   /// Record the boundary of the region being tracked.
00082   MachineBasicBlock::const_iterator TopPos;
00083   MachineBasicBlock::const_iterator BottomPos;
00084 
00085   void reset();
00086 
00087   void openTop(MachineBasicBlock::const_iterator PrevTop);
00088 
00089   void openBottom(MachineBasicBlock::const_iterator PrevBottom);
00090 };
00091 
00092 /// Capture a change in pressure for a single pressure set. UnitInc may be
00093 /// expressed in terms of upward or downward pressure depending on the client
00094 /// and will be dynamically adjusted for current liveness.
00095 ///
00096 /// Pressure increments are tiny, typically 1-2 units, and this is only for
00097 /// heuristics, so we don't check UnitInc overflow. Instead, we may have a
00098 /// higher level assert that pressure is consistent within a region. We also
00099 /// effectively ignore dead defs which don't affect heuristics much.
00100 class PressureChange {
00101   uint16_t PSetID; // ID+1. 0=Invalid.
00102   int16_t  UnitInc;
00103 public:
00104   PressureChange(): PSetID(0), UnitInc(0) {}
00105   PressureChange(unsigned id): PSetID(id+1), UnitInc(0) {
00106     assert(id < UINT16_MAX && "PSetID overflow.");
00107   }
00108 
00109   bool isValid() const { return PSetID > 0; }
00110 
00111   unsigned getPSet() const {
00112     assert(isValid() && "invalid PressureChange");
00113     return PSetID - 1;
00114   }
00115   // If PSetID is invalid, return UINT16_MAX to give it lowest priority.
00116   unsigned getPSetOrMax() const { return (PSetID - 1) & UINT16_MAX; }
00117 
00118   int getUnitInc() const { return UnitInc; }
00119 
00120   void setUnitInc(int Inc) { UnitInc = Inc; }
00121 
00122   bool operator==(const PressureChange &RHS) const {
00123     return PSetID == RHS.PSetID && UnitInc == RHS.UnitInc;
00124   }
00125 };
00126 
00127 template <> struct isPodLike<PressureChange> {
00128    static const bool value = true;
00129 };
00130 
00131 /// List of PressureChanges in order of increasing, unique PSetID.
00132 ///
00133 /// Use a small fixed number, because we can fit more PressureChanges in an
00134 /// empty SmallVector than ever need to be tracked per register class. If more
00135 /// PSets are affected, then we only track the most constrained.
00136 class PressureDiff {
00137   // The initial design was for MaxPSets=4, but that requires PSet partitions,
00138   // which are not yet implemented. (PSet partitions are equivalent PSets given
00139   // the register classes actually in use within the scheduling region.)
00140   enum { MaxPSets = 16 };
00141 
00142   PressureChange PressureChanges[MaxPSets];
00143 public:
00144   typedef PressureChange* iterator;
00145   typedef const PressureChange* const_iterator;
00146   iterator begin() { return &PressureChanges[0]; }
00147   iterator end() { return &PressureChanges[MaxPSets]; }
00148   const_iterator begin() const { return &PressureChanges[0]; }
00149   const_iterator end() const { return &PressureChanges[MaxPSets]; }
00150 
00151   void addPressureChange(unsigned RegUnit, bool IsDec,
00152                          const MachineRegisterInfo *MRI);
00153 };
00154 
00155 /// Array of PressureDiffs.
00156 class PressureDiffs {
00157   PressureDiff *PDiffArray;
00158   unsigned Size;
00159   unsigned Max;
00160 public:
00161   PressureDiffs(): PDiffArray(nullptr), Size(0), Max(0) {}
00162   ~PressureDiffs() { free(PDiffArray); }
00163 
00164   void clear() { Size = 0; }
00165 
00166   void init(unsigned N);
00167 
00168   PressureDiff &operator[](unsigned Idx) {
00169     assert(Idx < Size && "PressureDiff index out of bounds");
00170     return PDiffArray[Idx];
00171   }
00172   const PressureDiff &operator[](unsigned Idx) const {
00173     return const_cast<PressureDiffs*>(this)->operator[](Idx);
00174   }
00175 };
00176 
00177 /// Store the effects of a change in pressure on things that MI scheduler cares
00178 /// about.
00179 ///
00180 /// Excess records the value of the largest difference in register units beyond
00181 /// the target's pressure limits across the affected pressure sets, where
00182 /// largest is defined as the absolute value of the difference. Negative
00183 /// ExcessUnits indicates a reduction in pressure that had already exceeded the
00184 /// target's limits.
00185 ///
00186 /// CriticalMax records the largest increase in the tracker's max pressure that
00187 /// exceeds the critical limit for some pressure set determined by the client.
00188 ///
00189 /// CurrentMax records the largest increase in the tracker's max pressure that
00190 /// exceeds the current limit for some pressure set determined by the client.
00191 struct RegPressureDelta {
00192   PressureChange Excess;
00193   PressureChange CriticalMax;
00194   PressureChange CurrentMax;
00195 
00196   RegPressureDelta() {}
00197 
00198   bool operator==(const RegPressureDelta &RHS) const {
00199     return Excess == RHS.Excess && CriticalMax == RHS.CriticalMax
00200       && CurrentMax == RHS.CurrentMax;
00201   }
00202   bool operator!=(const RegPressureDelta &RHS) const {
00203     return !operator==(RHS);
00204   }
00205 };
00206 
00207 /// \brief A set of live virtual registers and physical register units.
00208 ///
00209 /// Virtual and physical register numbers require separate sparse sets, but most
00210 /// of the RegisterPressureTracker handles them uniformly.
00211 struct LiveRegSet {
00212   SparseSet<unsigned> PhysRegs;
00213   SparseSet<unsigned, VirtReg2IndexFunctor> VirtRegs;
00214 
00215   bool contains(unsigned Reg) const {
00216     if (TargetRegisterInfo::isVirtualRegister(Reg))
00217       return VirtRegs.count(Reg);
00218     return PhysRegs.count(Reg);
00219   }
00220 
00221   bool insert(unsigned Reg) {
00222     if (TargetRegisterInfo::isVirtualRegister(Reg))
00223       return VirtRegs.insert(Reg).second;
00224     return PhysRegs.insert(Reg).second;
00225   }
00226 
00227   bool erase(unsigned Reg) {
00228     if (TargetRegisterInfo::isVirtualRegister(Reg))
00229       return VirtRegs.erase(Reg);
00230     return PhysRegs.erase(Reg);
00231   }
00232 };
00233 
00234 /// Track the current register pressure at some position in the instruction
00235 /// stream, and remember the high water mark within the region traversed. This
00236 /// does not automatically consider live-through ranges. The client may
00237 /// independently adjust for global liveness.
00238 ///
00239 /// Each RegPressureTracker only works within a MachineBasicBlock. Pressure can
00240 /// be tracked across a larger region by storing a RegisterPressure result at
00241 /// each block boundary and explicitly adjusting pressure to account for block
00242 /// live-in and live-out register sets.
00243 ///
00244 /// RegPressureTracker holds a reference to a RegisterPressure result that it
00245 /// computes incrementally. During downward tracking, P.BottomIdx or P.BottomPos
00246 /// is invalid until it reaches the end of the block or closeRegion() is
00247 /// explicitly called. Similarly, P.TopIdx is invalid during upward
00248 /// tracking. Changing direction has the side effect of closing region, and
00249 /// traversing past TopIdx or BottomIdx reopens it.
00250 class RegPressureTracker {
00251   const MachineFunction     *MF;
00252   const TargetRegisterInfo  *TRI;
00253   const RegisterClassInfo   *RCI;
00254   const MachineRegisterInfo *MRI;
00255   const LiveIntervals       *LIS;
00256 
00257   /// We currently only allow pressure tracking within a block.
00258   const MachineBasicBlock *MBB;
00259 
00260   /// Track the max pressure within the region traversed so far.
00261   RegisterPressure &P;
00262 
00263   /// Run in two modes dependending on whether constructed with IntervalPressure
00264   /// or RegisterPressure. If requireIntervals is false, LIS are ignored.
00265   bool RequireIntervals;
00266 
00267   /// True if UntiedDefs will be populated.
00268   bool TrackUntiedDefs;
00269 
00270   /// Register pressure corresponds to liveness before this instruction
00271   /// iterator. It may point to the end of the block or a DebugValue rather than
00272   /// an instruction.
00273   MachineBasicBlock::const_iterator CurrPos;
00274 
00275   /// Pressure map indexed by pressure set ID, not class ID.
00276   std::vector<unsigned> CurrSetPressure;
00277 
00278   /// Set of live registers.
00279   LiveRegSet LiveRegs;
00280 
00281   /// Set of vreg defs that start a live range.
00282   SparseSet<unsigned, VirtReg2IndexFunctor> UntiedDefs;
00283   /// Live-through pressure.
00284   std::vector<unsigned> LiveThruPressure;
00285 
00286 public:
00287   RegPressureTracker(IntervalPressure &rp) :
00288     MF(nullptr), TRI(nullptr), RCI(nullptr), LIS(nullptr), MBB(nullptr), P(rp),
00289     RequireIntervals(true), TrackUntiedDefs(false) {}
00290 
00291   RegPressureTracker(RegionPressure &rp) :
00292     MF(nullptr), TRI(nullptr), RCI(nullptr), LIS(nullptr), MBB(nullptr), P(rp),
00293     RequireIntervals(false), TrackUntiedDefs(false) {}
00294 
00295   void reset();
00296 
00297   void init(const MachineFunction *mf, const RegisterClassInfo *rci,
00298             const LiveIntervals *lis, const MachineBasicBlock *mbb,
00299             MachineBasicBlock::const_iterator pos,
00300             bool ShouldTrackUntiedDefs = false);
00301 
00302   /// Force liveness of virtual registers or physical register
00303   /// units. Particularly useful to initialize the livein/out state of the
00304   /// tracker before the first call to advance/recede.
00305   void addLiveRegs(ArrayRef<unsigned> Regs);
00306 
00307   /// Get the MI position corresponding to this register pressure.
00308   MachineBasicBlock::const_iterator getPos() const { return CurrPos; }
00309 
00310   // Reset the MI position corresponding to the register pressure. This allows
00311   // schedulers to move instructions above the RegPressureTracker's
00312   // CurrPos. Since the pressure is computed before CurrPos, the iterator
00313   // position changes while pressure does not.
00314   void setPos(MachineBasicBlock::const_iterator Pos) { CurrPos = Pos; }
00315 
00316   /// \brief Get the SlotIndex for the first nondebug instruction including or
00317   /// after the current position.
00318   SlotIndex getCurrSlot() const;
00319 
00320   /// Recede across the previous instruction.
00321   bool recede(SmallVectorImpl<unsigned> *LiveUses = nullptr,
00322               PressureDiff *PDiff = nullptr);
00323 
00324   /// Advance across the current instruction.
00325   bool advance();
00326 
00327   /// Finalize the region boundaries and recored live ins and live outs.
00328   void closeRegion();
00329 
00330   /// Initialize the LiveThru pressure set based on the untied defs found in
00331   /// RPTracker.
00332   void initLiveThru(const RegPressureTracker &RPTracker);
00333 
00334   /// Copy an existing live thru pressure result.
00335   void initLiveThru(ArrayRef<unsigned> PressureSet) {
00336     LiveThruPressure.assign(PressureSet.begin(), PressureSet.end());
00337   }
00338 
00339   ArrayRef<unsigned> getLiveThru() const { return LiveThruPressure; }
00340 
00341   /// Get the resulting register pressure over the traversed region.
00342   /// This result is complete if either advance() or recede() has returned true,
00343   /// or if closeRegion() was explicitly invoked.
00344   RegisterPressure &getPressure() { return P; }
00345   const RegisterPressure &getPressure() const { return P; }
00346 
00347   /// Get the register set pressure at the current position, which may be less
00348   /// than the pressure across the traversed region.
00349   std::vector<unsigned> &getRegSetPressureAtPos() { return CurrSetPressure; }
00350 
00351   void discoverLiveOut(unsigned Reg);
00352   void discoverLiveIn(unsigned Reg);
00353 
00354   bool isTopClosed() const;
00355   bool isBottomClosed() const;
00356 
00357   void closeTop();
00358   void closeBottom();
00359 
00360   /// Consider the pressure increase caused by traversing this instruction
00361   /// bottom-up. Find the pressure set with the most change beyond its pressure
00362   /// limit based on the tracker's current pressure, and record the number of
00363   /// excess register units of that pressure set introduced by this instruction.
00364   void getMaxUpwardPressureDelta(const MachineInstr *MI,
00365                                  PressureDiff *PDiff,
00366                                  RegPressureDelta &Delta,
00367                                  ArrayRef<PressureChange> CriticalPSets,
00368                                  ArrayRef<unsigned> MaxPressureLimit);
00369 
00370   void getUpwardPressureDelta(const MachineInstr *MI,
00371                               /*const*/ PressureDiff &PDiff,
00372                               RegPressureDelta &Delta,
00373                               ArrayRef<PressureChange> CriticalPSets,
00374                               ArrayRef<unsigned> MaxPressureLimit) const;
00375 
00376   /// Consider the pressure increase caused by traversing this instruction
00377   /// top-down. Find the pressure set with the most change beyond its pressure
00378   /// limit based on the tracker's current pressure, and record the number of
00379   /// excess register units of that pressure set introduced by this instruction.
00380   void getMaxDownwardPressureDelta(const MachineInstr *MI,
00381                                    RegPressureDelta &Delta,
00382                                    ArrayRef<PressureChange> CriticalPSets,
00383                                    ArrayRef<unsigned> MaxPressureLimit);
00384 
00385   /// Find the pressure set with the most change beyond its pressure limit after
00386   /// traversing this instruction either upward or downward depending on the
00387   /// closed end of the current region.
00388   void getMaxPressureDelta(const MachineInstr *MI,
00389                            RegPressureDelta &Delta,
00390                            ArrayRef<PressureChange> CriticalPSets,
00391                            ArrayRef<unsigned> MaxPressureLimit) {
00392     if (isTopClosed())
00393       return getMaxDownwardPressureDelta(MI, Delta, CriticalPSets,
00394                                          MaxPressureLimit);
00395 
00396     assert(isBottomClosed() && "Uninitialized pressure tracker");
00397     return getMaxUpwardPressureDelta(MI, nullptr, Delta, CriticalPSets,
00398                                      MaxPressureLimit);
00399   }
00400 
00401   /// Get the pressure of each PSet after traversing this instruction bottom-up.
00402   void getUpwardPressure(const MachineInstr *MI,
00403                          std::vector<unsigned> &PressureResult,
00404                          std::vector<unsigned> &MaxPressureResult);
00405 
00406   /// Get the pressure of each PSet after traversing this instruction top-down.
00407   void getDownwardPressure(const MachineInstr *MI,
00408                            std::vector<unsigned> &PressureResult,
00409                            std::vector<unsigned> &MaxPressureResult);
00410 
00411   void getPressureAfterInst(const MachineInstr *MI,
00412                             std::vector<unsigned> &PressureResult,
00413                             std::vector<unsigned> &MaxPressureResult) {
00414     if (isTopClosed())
00415       return getUpwardPressure(MI, PressureResult, MaxPressureResult);
00416 
00417     assert(isBottomClosed() && "Uninitialized pressure tracker");
00418     return getDownwardPressure(MI, PressureResult, MaxPressureResult);
00419   }
00420 
00421   bool hasUntiedDef(unsigned VirtReg) const {
00422     return UntiedDefs.count(VirtReg);
00423   }
00424 
00425   void dump() const;
00426 
00427 protected:
00428   const LiveRange *getLiveRange(unsigned Reg) const;
00429 
00430   void increaseRegPressure(ArrayRef<unsigned> Regs);
00431   void decreaseRegPressure(ArrayRef<unsigned> Regs);
00432 
00433   void bumpUpwardPressure(const MachineInstr *MI);
00434   void bumpDownwardPressure(const MachineInstr *MI);
00435 };
00436 
00437 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
00438 void dumpRegSetPressure(ArrayRef<unsigned> SetPressure,
00439                         const TargetRegisterInfo *TRI);
00440 #endif
00441 } // end namespace llvm
00442 
00443 #endif