RegisterPressure.h revision 243830
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/CodeGen/SlotIndexes.h" 19#include "llvm/Target/TargetRegisterInfo.h" 20#include "llvm/ADT/SparseSet.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 rather than an instruction. 154 MachineBasicBlock::const_iterator CurrPos; 155 156 /// Pressure map indexed by pressure set ID, not class ID. 157 std::vector<unsigned> CurrSetPressure; 158 159 /// List of live registers. 160 SparseSet<unsigned> LivePhysRegs; 161 SparseSet<unsigned, VirtReg2IndexFunctor> LiveVirtRegs; 162 163public: 164 RegPressureTracker(IntervalPressure &rp) : 165 MF(0), TRI(0), RCI(0), LIS(0), MBB(0), P(rp), RequireIntervals(true) {} 166 167 RegPressureTracker(RegionPressure &rp) : 168 MF(0), TRI(0), RCI(0), LIS(0), MBB(0), P(rp), RequireIntervals(false) {} 169 170 void init(const MachineFunction *mf, const RegisterClassInfo *rci, 171 const LiveIntervals *lis, const MachineBasicBlock *mbb, 172 MachineBasicBlock::const_iterator pos); 173 174 /// Force liveness of registers. Particularly useful to initialize the 175 /// livein/out state of the tracker before the first call to advance/recede. 176 void addLiveRegs(ArrayRef<unsigned> Regs); 177 178 /// Get the MI position corresponding to this register pressure. 179 MachineBasicBlock::const_iterator getPos() const { return CurrPos; } 180 181 // Reset the MI position corresponding to the register pressure. This allows 182 // schedulers to move instructions above the RegPressureTracker's 183 // CurrPos. Since the pressure is computed before CurrPos, the iterator 184 // position changes while pressure does not. 185 void setPos(MachineBasicBlock::const_iterator Pos) { CurrPos = Pos; } 186 187 /// Recede across the previous instruction. 188 bool recede(); 189 190 /// Advance across the current instruction. 191 bool advance(); 192 193 /// Finalize the region boundaries and recored live ins and live outs. 194 void closeRegion(); 195 196 /// Get the resulting register pressure over the traversed region. 197 /// This result is complete if either advance() or recede() has returned true, 198 /// or if closeRegion() was explicitly invoked. 199 RegisterPressure &getPressure() { return P; } 200 const RegisterPressure &getPressure() const { return P; } 201 202 /// Get the register set pressure at the current position, which may be less 203 /// than the pressure across the traversed region. 204 std::vector<unsigned> &getRegSetPressureAtPos() { return CurrSetPressure; } 205 206 void discoverPhysLiveIn(unsigned Reg); 207 void discoverPhysLiveOut(unsigned Reg); 208 209 void discoverVirtLiveIn(unsigned Reg); 210 void discoverVirtLiveOut(unsigned Reg); 211 212 bool isTopClosed() const; 213 bool isBottomClosed() const; 214 215 void closeTop(); 216 void closeBottom(); 217 218 /// Consider the pressure increase caused by traversing this instruction 219 /// bottom-up. Find the pressure set with the most change beyond its pressure 220 /// limit based on the tracker's current pressure, and record the number of 221 /// excess register units of that pressure set introduced by this instruction. 222 void getMaxUpwardPressureDelta(const MachineInstr *MI, 223 RegPressureDelta &Delta, 224 ArrayRef<PressureElement> CriticalPSets, 225 ArrayRef<unsigned> MaxPressureLimit); 226 227 /// Consider the pressure increase caused by traversing this instruction 228 /// top-down. Find the pressure set with the most change beyond its pressure 229 /// limit based on the tracker's current pressure, and record the number of 230 /// excess register units of that pressure set introduced by this instruction. 231 void getMaxDownwardPressureDelta(const MachineInstr *MI, 232 RegPressureDelta &Delta, 233 ArrayRef<PressureElement> CriticalPSets, 234 ArrayRef<unsigned> MaxPressureLimit); 235 236 /// Find the pressure set with the most change beyond its pressure limit after 237 /// traversing this instruction either upward or downward depending on the 238 /// closed end of the current region. 239 void getMaxPressureDelta(const MachineInstr *MI, RegPressureDelta &Delta, 240 ArrayRef<PressureElement> CriticalPSets, 241 ArrayRef<unsigned> MaxPressureLimit) { 242 if (isTopClosed()) 243 return getMaxDownwardPressureDelta(MI, Delta, CriticalPSets, 244 MaxPressureLimit); 245 246 assert(isBottomClosed() && "Uninitialized pressure tracker"); 247 return getMaxUpwardPressureDelta(MI, Delta, CriticalPSets, 248 MaxPressureLimit); 249 } 250 251 /// Get the pressure of each PSet after traversing this instruction bottom-up. 252 void getUpwardPressure(const MachineInstr *MI, 253 std::vector<unsigned> &PressureResult, 254 std::vector<unsigned> &MaxPressureResult); 255 256 /// Get the pressure of each PSet after traversing this instruction top-down. 257 void getDownwardPressure(const MachineInstr *MI, 258 std::vector<unsigned> &PressureResult, 259 std::vector<unsigned> &MaxPressureResult); 260 261 void getPressureAfterInst(const MachineInstr *MI, 262 std::vector<unsigned> &PressureResult, 263 std::vector<unsigned> &MaxPressureResult) { 264 if (isTopClosed()) 265 return getUpwardPressure(MI, PressureResult, MaxPressureResult); 266 267 assert(isBottomClosed() && "Uninitialized pressure tracker"); 268 return getDownwardPressure(MI, PressureResult, MaxPressureResult); 269 } 270 271protected: 272 void increasePhysRegPressure(ArrayRef<unsigned> Regs); 273 void decreasePhysRegPressure(ArrayRef<unsigned> Regs); 274 275 void increaseVirtRegPressure(ArrayRef<unsigned> Regs); 276 void decreaseVirtRegPressure(ArrayRef<unsigned> Regs); 277 278 void bumpUpwardPressure(const MachineInstr *MI); 279 void bumpDownwardPressure(const MachineInstr *MI); 280}; 281} // end namespace llvm 282 283#endif 284