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); 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 201 /// Get the register set pressure at the current position, which may be less 202 /// than the pressure across the traversed region. 203 std::vector<unsigned> &getRegSetPressureAtPos() { return CurrSetPressure; } 204 205 void discoverPhysLiveIn(unsigned Reg); 206 void discoverPhysLiveOut(unsigned Reg); 207 208 void discoverVirtLiveIn(unsigned Reg); 209 void discoverVirtLiveOut(unsigned Reg); 210 211 bool isTopClosed() const; 212 bool isBottomClosed() const; 213 214 void closeTop(); 215 void closeBottom(); 216 217 /// Consider the pressure increase caused by traversing this instruction 218 /// bottom-up. Find the pressure set with the most change beyond its pressure 219 /// limit based on the tracker's current pressure, and record the number of 220 /// excess register units of that pressure set introduced by this instruction. 221 void getMaxUpwardPressureDelta(const MachineInstr *MI, 222 RegPressureDelta &Delta, 223 ArrayRef<PressureElement> CriticalPSets, 224 ArrayRef<unsigned> MaxPressureLimit); 225 226 /// Consider the pressure increase caused by traversing this instruction 227 /// top-down. Find the pressure set with the most change beyond its pressure 228 /// limit based on the tracker's current pressure, and record the number of 229 /// excess register units of that pressure set introduced by this instruction. 230 void getMaxDownwardPressureDelta(const MachineInstr *MI, 231 RegPressureDelta &Delta, 232 ArrayRef<PressureElement> CriticalPSets, 233 ArrayRef<unsigned> MaxPressureLimit); 234 235 /// Find the pressure set with the most change beyond its pressure limit after 236 /// traversing this instruction either upward or downward depending on the 237 /// closed end of the current region. 238 void getMaxPressureDelta(const MachineInstr *MI, RegPressureDelta &Delta, 239 ArrayRef<PressureElement> CriticalPSets, 240 ArrayRef<unsigned> MaxPressureLimit) { 241 if (isTopClosed()) 242 return getMaxDownwardPressureDelta(MI, Delta, CriticalPSets, 243 MaxPressureLimit); 244 245 assert(isBottomClosed() && "Uninitialized pressure tracker"); 246 return getMaxUpwardPressureDelta(MI, Delta, CriticalPSets, 247 MaxPressureLimit); 248 } 249 250 /// Get the pressure of each PSet after traversing this instruction bottom-up. 251 void getUpwardPressure(const MachineInstr *MI, 252 std::vector<unsigned> &PressureResult, 253 std::vector<unsigned> &MaxPressureResult); 254 255 /// Get the pressure of each PSet after traversing this instruction top-down. 256 void getDownwardPressure(const MachineInstr *MI, 257 std::vector<unsigned> &PressureResult, 258 std::vector<unsigned> &MaxPressureResult); 259 260 void getPressureAfterInst(const MachineInstr *MI, 261 std::vector<unsigned> &PressureResult, 262 std::vector<unsigned> &MaxPressureResult) { 263 if (isTopClosed()) 264 return getUpwardPressure(MI, PressureResult, MaxPressureResult); 265 266 assert(isBottomClosed() && "Uninitialized pressure tracker"); 267 return getDownwardPressure(MI, PressureResult, MaxPressureResult); 268 } 269 270protected: 271 void increasePhysRegPressure(ArrayRef<unsigned> Regs); 272 void decreasePhysRegPressure(ArrayRef<unsigned> Regs); 273 274 void increaseVirtRegPressure(ArrayRef<unsigned> Regs); 275 void decreaseVirtRegPressure(ArrayRef<unsigned> Regs); 276 277 void bumpUpwardPressure(const MachineInstr *MI); 278 void bumpDownwardPressure(const MachineInstr *MI); 279}; 280} // end namespace llvm 281 282#endif 283