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 22 namespace llvm { 23 24 class LiveIntervals; 25 class RegisterClassInfo; 26 class MachineInstr; 27 28 /// Base class for register pressure results. 29 struct 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. 58 struct 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. 73 struct 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. 87 struct 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. 111 struct 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. 135 class 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 163 public: 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 270 protected: 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