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