RegisterPressure.h revision 17cf53519905acb69c567173bedd2df1c8e45523
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 22namespace llvm { 23 24class LiveIntervals; 25class RegisterClassInfo; 26class MachineInstr; 27 28/// Base class for register pressure results. 29struct RegisterPressure { 30 /// Map of max reg pressure indexed by pressure set ID, not class ID. 31 std::vector<unsigned> MaxSetPressure; 32 33 /// List of live in registers. 34 SmallVector<unsigned,8> LiveInRegs; 35 SmallVector<unsigned,8> LiveOutRegs; 36 37 /// Increase register pressure for each pressure set impacted by this register 38 /// class. Normally called by RegPressureTracker, but may be called manually 39 /// to account for live through (global liveness). 40 void increase(const TargetRegisterClass *RC, const TargetRegisterInfo *TRI); 41 42 /// Decrease register pressure for each pressure set impacted by this register 43 /// class. This is only useful to account for spilling or rematerialization. 44 void decrease(const TargetRegisterClass *RC, const TargetRegisterInfo *TRI); 45 46 void dump(const TargetRegisterInfo *TRI) const; 47}; 48 49/// RegisterPressure computed within a region of instructions delimited by 50/// TopIdx and BottomIdx. During pressure computation, the maximum pressure per 51/// register pressure set is increased. Once pressure within a region is fully 52/// computed, the live-in and live-out sets are recorded. 53/// 54/// This is preferable to RegionPressure when LiveIntervals are available, 55/// because delimiting regions by SlotIndex is more robust and convenient than 56/// holding block iterators. The block contents can change without invalidating 57/// the pressure result. 58struct IntervalPressure : RegisterPressure { 59 /// Record the boundary of the region being tracked. 60 SlotIndex TopIdx; 61 SlotIndex BottomIdx; 62 63 void reset(); 64 65 void openTop(SlotIndex NextTop); 66 67 void openBottom(SlotIndex PrevBottom); 68}; 69 70/// RegisterPressure computed within a region of instructions delimited by 71/// TopPos and BottomPos. This is a less precise version of IntervalPressure for 72/// use when LiveIntervals are unavailable. 73struct RegionPressure : RegisterPressure { 74 /// Record the boundary of the region being tracked. 75 MachineBasicBlock::const_iterator TopPos; 76 MachineBasicBlock::const_iterator BottomPos; 77 78 void reset(); 79 80 void openTop(MachineBasicBlock::const_iterator PrevTop); 81 82 void openBottom(MachineBasicBlock::const_iterator PrevBottom); 83}; 84 85/// An element of pressure difference that identifies the pressure set and 86/// amount of increase or decrease in units of pressure. 87struct PressureElement { 88 unsigned PSetID; 89 int UnitIncrease; 90 91 PressureElement(): PSetID(~0U), UnitIncrease(0) {} 92 PressureElement(unsigned id, int inc): PSetID(id), UnitIncrease(inc) {} 93 94 bool isValid() const { return PSetID != ~0U; } 95}; 96 97/// Store the effects of a change in pressure on things that MI scheduler cares 98/// about. 99/// 100/// Excess records the value of the largest difference in register units beyond 101/// the target's pressure limits across the affected pressure sets, where 102/// largest is defined as the absolute value of the difference. Negative 103/// ExcessUnits indicates a reduction in pressure that had already exceeded the 104/// target's limits. 105/// 106/// CriticalMax records the largest increase in the tracker's max pressure that 107/// exceeds the critical limit for some pressure set determined by the client. 108/// 109/// CurrentMax records the largest increase in the tracker's max pressure that 110/// exceeds the current limit for some pressure set determined by the client. 111struct RegPressureDelta { 112 PressureElement Excess; 113 PressureElement CriticalMax; 114 PressureElement CurrentMax; 115 116 RegPressureDelta() {} 117}; 118 119/// Track the current register pressure at some position in the instruction 120/// stream, and remember the high water mark within the region traversed. This 121/// does not automatically consider live-through ranges. The client may 122/// independently adjust for global liveness. 123/// 124/// Each RegPressureTracker only works within a MachineBasicBlock. Pressure can 125/// be tracked across a larger region by storing a RegisterPressure result at 126/// each block boundary and explicitly adjusting pressure to account for block 127/// live-in and live-out register sets. 128/// 129/// RegPressureTracker holds a reference to a RegisterPressure result that it 130/// computes incrementally. During downward tracking, P.BottomIdx or P.BottomPos 131/// is invalid until it reaches the end of the block or closeRegion() is 132/// explicitly called. Similarly, P.TopIdx is invalid during upward 133/// tracking. Changing direction has the side effect of closing region, and 134/// traversing past TopIdx or BottomIdx reopens it. 135class RegPressureTracker { 136 const MachineFunction *MF; 137 const TargetRegisterInfo *TRI; 138 const RegisterClassInfo *RCI; 139 const MachineRegisterInfo *MRI; 140 const LiveIntervals *LIS; 141 142 /// We currently only allow pressure tracking within a block. 143 const MachineBasicBlock *MBB; 144 145 /// Track the max pressure within the region traversed so far. 146 RegisterPressure &P; 147 148 /// Run in two modes dependending on whether constructed with IntervalPressure 149 /// or RegisterPressure. If requireIntervals is false, LIS are ignored. 150 bool RequireIntervals; 151 152 /// Register pressure corresponds to liveness before this instruction 153 /// iterator. It may point to the end of the block or a DebugValue rather than 154 /// an instruction. 155 MachineBasicBlock::const_iterator CurrPos; 156 157 /// Pressure map indexed by pressure set ID, not class ID. 158 std::vector<unsigned> CurrSetPressure; 159 160 /// List of live registers. 161 SparseSet<unsigned> LivePhysRegs; 162 SparseSet<unsigned, VirtReg2IndexFunctor> LiveVirtRegs; 163 164public: 165 RegPressureTracker(IntervalPressure &rp) : 166 MF(0), TRI(0), RCI(0), LIS(0), MBB(0), P(rp), RequireIntervals(true) {} 167 168 RegPressureTracker(RegionPressure &rp) : 169 MF(0), TRI(0), RCI(0), LIS(0), MBB(0), P(rp), RequireIntervals(false) {} 170 171 void init(const MachineFunction *mf, const RegisterClassInfo *rci, 172 const LiveIntervals *lis, const MachineBasicBlock *mbb, 173 MachineBasicBlock::const_iterator pos); 174 175 /// Force liveness of registers. Particularly useful to initialize the 176 /// livein/out state of the tracker before the first call to advance/recede. 177 void addLiveRegs(ArrayRef<unsigned> Regs); 178 179 /// Get the MI position corresponding to this register pressure. 180 MachineBasicBlock::const_iterator getPos() const { return CurrPos; } 181 182 // Reset the MI position corresponding to the register pressure. This allows 183 // schedulers to move instructions above the RegPressureTracker's 184 // CurrPos. Since the pressure is computed before CurrPos, the iterator 185 // position changes while pressure does not. 186 void setPos(MachineBasicBlock::const_iterator Pos) { CurrPos = Pos; } 187 188 /// \brief Get the SlotIndex for the first nondebug instruction including or 189 /// after the current position. 190 SlotIndex getCurrSlot() const; 191 192 /// Recede across the previous instruction. 193 bool recede(); 194 195 /// Advance across the current instruction. 196 bool advance(); 197 198 /// Finalize the region boundaries and recored live ins and live outs. 199 void closeRegion(); 200 201 /// Get the resulting register pressure over the traversed region. 202 /// This result is complete if either advance() or recede() has returned true, 203 /// or if closeRegion() was explicitly invoked. 204 RegisterPressure &getPressure() { return P; } 205 const RegisterPressure &getPressure() const { return P; } 206 207 /// Get the register set pressure at the current position, which may be less 208 /// than the pressure across the traversed region. 209 std::vector<unsigned> &getRegSetPressureAtPos() { return CurrSetPressure; } 210 211 void discoverPhysLiveIn(unsigned Reg); 212 void discoverPhysLiveOut(unsigned Reg); 213 214 void discoverVirtLiveIn(unsigned Reg); 215 void discoverVirtLiveOut(unsigned Reg); 216 217 bool isTopClosed() const; 218 bool isBottomClosed() const; 219 220 void closeTop(); 221 void closeBottom(); 222 223 /// Consider the pressure increase caused by traversing this instruction 224 /// bottom-up. Find the pressure set with the most change beyond its pressure 225 /// limit based on the tracker's current pressure, and record the number of 226 /// excess register units of that pressure set introduced by this instruction. 227 void getMaxUpwardPressureDelta(const MachineInstr *MI, 228 RegPressureDelta &Delta, 229 ArrayRef<PressureElement> CriticalPSets, 230 ArrayRef<unsigned> MaxPressureLimit); 231 232 /// Consider the pressure increase caused by traversing this instruction 233 /// top-down. Find the pressure set with the most change beyond its pressure 234 /// limit based on the tracker's current pressure, and record the number of 235 /// excess register units of that pressure set introduced by this instruction. 236 void getMaxDownwardPressureDelta(const MachineInstr *MI, 237 RegPressureDelta &Delta, 238 ArrayRef<PressureElement> CriticalPSets, 239 ArrayRef<unsigned> MaxPressureLimit); 240 241 /// Find the pressure set with the most change beyond its pressure limit after 242 /// traversing this instruction either upward or downward depending on the 243 /// closed end of the current region. 244 void getMaxPressureDelta(const MachineInstr *MI, RegPressureDelta &Delta, 245 ArrayRef<PressureElement> CriticalPSets, 246 ArrayRef<unsigned> MaxPressureLimit) { 247 if (isTopClosed()) 248 return getMaxDownwardPressureDelta(MI, Delta, CriticalPSets, 249 MaxPressureLimit); 250 251 assert(isBottomClosed() && "Uninitialized pressure tracker"); 252 return getMaxUpwardPressureDelta(MI, Delta, CriticalPSets, 253 MaxPressureLimit); 254 } 255 256 /// Get the pressure of each PSet after traversing this instruction bottom-up. 257 void getUpwardPressure(const MachineInstr *MI, 258 std::vector<unsigned> &PressureResult, 259 std::vector<unsigned> &MaxPressureResult); 260 261 /// Get the pressure of each PSet after traversing this instruction top-down. 262 void getDownwardPressure(const MachineInstr *MI, 263 std::vector<unsigned> &PressureResult, 264 std::vector<unsigned> &MaxPressureResult); 265 266 void getPressureAfterInst(const MachineInstr *MI, 267 std::vector<unsigned> &PressureResult, 268 std::vector<unsigned> &MaxPressureResult) { 269 if (isTopClosed()) 270 return getUpwardPressure(MI, PressureResult, MaxPressureResult); 271 272 assert(isBottomClosed() && "Uninitialized pressure tracker"); 273 return getDownwardPressure(MI, PressureResult, MaxPressureResult); 274 } 275 276 void dump(const TargetRegisterInfo *TRI) const; 277 278protected: 279 void increasePhysRegPressure(ArrayRef<unsigned> Regs); 280 void decreasePhysRegPressure(ArrayRef<unsigned> Regs); 281 282 void increaseVirtRegPressure(ArrayRef<unsigned> Regs); 283 void decreaseVirtRegPressure(ArrayRef<unsigned> Regs); 284 285 void bumpUpwardPressure(const MachineInstr *MI); 286 void bumpDownwardPressure(const MachineInstr *MI); 287}; 288} // end namespace llvm 289 290#endif 291