]>
Commit | Line | Data |
---|---|---|
223e47cc LB |
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 | ||
970d7e83 | 18 | #include "llvm/ADT/SparseSet.h" |
223e47cc LB |
19 | #include "llvm/CodeGen/SlotIndexes.h" |
20 | #include "llvm/Target/TargetRegisterInfo.h" | |
223e47cc LB |
21 | |
22 | namespace llvm { | |
23 | ||
24 | class LiveIntervals; | |
1a4d82fc | 25 | class LiveRange; |
223e47cc LB |
26 | class RegisterClassInfo; |
27 | class MachineInstr; | |
28 | ||
29 | /// Base class for register pressure results. | |
30 | struct RegisterPressure { | |
31 | /// Map of max reg pressure indexed by pressure set ID, not class ID. | |
32 | std::vector<unsigned> MaxSetPressure; | |
33 | ||
970d7e83 | 34 | /// List of live in virtual registers or physical register units. |
223e47cc LB |
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). | |
970d7e83 LB |
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); | |
223e47cc LB |
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. | |
970d7e83 LB |
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); | |
223e47cc | 52 | |
970d7e83 | 53 | void dump(const TargetRegisterInfo *TRI) const; |
223e47cc LB |
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. | |
65 | struct 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. | |
80 | struct 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 | ||
1a4d82fc JJ |
92 | /// Capture a change in pressure for a single pressure set. UnitInc may be |
93 | /// expressed in terms of upward or downward pressure depending on the client | |
94 | /// and will be dynamically adjusted for current liveness. | |
95 | /// | |
96 | /// Pressure increments are tiny, typically 1-2 units, and this is only for | |
97 | /// heuristics, so we don't check UnitInc overflow. Instead, we may have a | |
98 | /// higher level assert that pressure is consistent within a region. We also | |
99 | /// effectively ignore dead defs which don't affect heuristics much. | |
100 | class PressureChange { | |
101 | uint16_t PSetID; // ID+1. 0=Invalid. | |
102 | int16_t UnitInc; | |
103 | public: | |
104 | PressureChange(): PSetID(0), UnitInc(0) {} | |
105 | PressureChange(unsigned id): PSetID(id+1), UnitInc(0) { | |
106 | assert(id < UINT16_MAX && "PSetID overflow."); | |
107 | } | |
108 | ||
109 | bool isValid() const { return PSetID > 0; } | |
110 | ||
111 | unsigned getPSet() const { | |
112 | assert(isValid() && "invalid PressureChange"); | |
113 | return PSetID - 1; | |
114 | } | |
115 | // If PSetID is invalid, return UINT16_MAX to give it lowest priority. | |
116 | unsigned getPSetOrMax() const { return (PSetID - 1) & UINT16_MAX; } | |
117 | ||
118 | int getUnitInc() const { return UnitInc; } | |
119 | ||
120 | void setUnitInc(int Inc) { UnitInc = Inc; } | |
223e47cc | 121 | |
1a4d82fc JJ |
122 | bool operator==(const PressureChange &RHS) const { |
123 | return PSetID == RHS.PSetID && UnitInc == RHS.UnitInc; | |
124 | } | |
125 | }; | |
223e47cc | 126 | |
1a4d82fc JJ |
127 | template <> struct isPodLike<PressureChange> { |
128 | static const bool value = true; | |
129 | }; | |
130 | ||
131 | /// List of PressureChanges in order of increasing, unique PSetID. | |
132 | /// | |
133 | /// Use a small fixed number, because we can fit more PressureChanges in an | |
134 | /// empty SmallVector than ever need to be tracked per register class. If more | |
135 | /// PSets are affected, then we only track the most constrained. | |
136 | class PressureDiff { | |
137 | // The initial design was for MaxPSets=4, but that requires PSet partitions, | |
138 | // which are not yet implemented. (PSet partitions are equivalent PSets given | |
139 | // the register classes actually in use within the scheduling region.) | |
140 | enum { MaxPSets = 16 }; | |
141 | ||
142 | PressureChange PressureChanges[MaxPSets]; | |
143 | public: | |
144 | typedef PressureChange* iterator; | |
145 | typedef const PressureChange* const_iterator; | |
146 | iterator begin() { return &PressureChanges[0]; } | |
147 | iterator end() { return &PressureChanges[MaxPSets]; } | |
148 | const_iterator begin() const { return &PressureChanges[0]; } | |
149 | const_iterator end() const { return &PressureChanges[MaxPSets]; } | |
150 | ||
151 | void addPressureChange(unsigned RegUnit, bool IsDec, | |
152 | const MachineRegisterInfo *MRI); | |
153 | }; | |
154 | ||
155 | /// Array of PressureDiffs. | |
156 | class PressureDiffs { | |
157 | PressureDiff *PDiffArray; | |
158 | unsigned Size; | |
159 | unsigned Max; | |
160 | public: | |
161 | PressureDiffs(): PDiffArray(nullptr), Size(0), Max(0) {} | |
162 | ~PressureDiffs() { free(PDiffArray); } | |
163 | ||
164 | void clear() { Size = 0; } | |
165 | ||
166 | void init(unsigned N); | |
167 | ||
168 | PressureDiff &operator[](unsigned Idx) { | |
169 | assert(Idx < Size && "PressureDiff index out of bounds"); | |
170 | return PDiffArray[Idx]; | |
171 | } | |
172 | const PressureDiff &operator[](unsigned Idx) const { | |
173 | return const_cast<PressureDiffs*>(this)->operator[](Idx); | |
174 | } | |
223e47cc LB |
175 | }; |
176 | ||
177 | /// Store the effects of a change in pressure on things that MI scheduler cares | |
178 | /// about. | |
179 | /// | |
180 | /// Excess records the value of the largest difference in register units beyond | |
181 | /// the target's pressure limits across the affected pressure sets, where | |
182 | /// largest is defined as the absolute value of the difference. Negative | |
183 | /// ExcessUnits indicates a reduction in pressure that had already exceeded the | |
184 | /// target's limits. | |
185 | /// | |
186 | /// CriticalMax records the largest increase in the tracker's max pressure that | |
187 | /// exceeds the critical limit for some pressure set determined by the client. | |
188 | /// | |
189 | /// CurrentMax records the largest increase in the tracker's max pressure that | |
190 | /// exceeds the current limit for some pressure set determined by the client. | |
191 | struct RegPressureDelta { | |
1a4d82fc JJ |
192 | PressureChange Excess; |
193 | PressureChange CriticalMax; | |
194 | PressureChange CurrentMax; | |
223e47cc LB |
195 | |
196 | RegPressureDelta() {} | |
1a4d82fc JJ |
197 | |
198 | bool operator==(const RegPressureDelta &RHS) const { | |
199 | return Excess == RHS.Excess && CriticalMax == RHS.CriticalMax | |
200 | && CurrentMax == RHS.CurrentMax; | |
201 | } | |
202 | bool operator!=(const RegPressureDelta &RHS) const { | |
203 | return !operator==(RHS); | |
204 | } | |
223e47cc LB |
205 | }; |
206 | ||
970d7e83 LB |
207 | /// \brief A set of live virtual registers and physical register units. |
208 | /// | |
209 | /// Virtual and physical register numbers require separate sparse sets, but most | |
210 | /// of the RegisterPressureTracker handles them uniformly. | |
211 | struct LiveRegSet { | |
212 | SparseSet<unsigned> PhysRegs; | |
213 | SparseSet<unsigned, VirtReg2IndexFunctor> VirtRegs; | |
214 | ||
1a4d82fc | 215 | bool contains(unsigned Reg) const { |
970d7e83 LB |
216 | if (TargetRegisterInfo::isVirtualRegister(Reg)) |
217 | return VirtRegs.count(Reg); | |
218 | return PhysRegs.count(Reg); | |
219 | } | |
220 | ||
221 | bool insert(unsigned Reg) { | |
222 | if (TargetRegisterInfo::isVirtualRegister(Reg)) | |
223 | return VirtRegs.insert(Reg).second; | |
224 | return PhysRegs.insert(Reg).second; | |
225 | } | |
226 | ||
227 | bool erase(unsigned Reg) { | |
228 | if (TargetRegisterInfo::isVirtualRegister(Reg)) | |
229 | return VirtRegs.erase(Reg); | |
230 | return PhysRegs.erase(Reg); | |
231 | } | |
232 | }; | |
233 | ||
223e47cc LB |
234 | /// Track the current register pressure at some position in the instruction |
235 | /// stream, and remember the high water mark within the region traversed. This | |
236 | /// does not automatically consider live-through ranges. The client may | |
237 | /// independently adjust for global liveness. | |
238 | /// | |
239 | /// Each RegPressureTracker only works within a MachineBasicBlock. Pressure can | |
240 | /// be tracked across a larger region by storing a RegisterPressure result at | |
241 | /// each block boundary and explicitly adjusting pressure to account for block | |
242 | /// live-in and live-out register sets. | |
243 | /// | |
244 | /// RegPressureTracker holds a reference to a RegisterPressure result that it | |
245 | /// computes incrementally. During downward tracking, P.BottomIdx or P.BottomPos | |
246 | /// is invalid until it reaches the end of the block or closeRegion() is | |
247 | /// explicitly called. Similarly, P.TopIdx is invalid during upward | |
248 | /// tracking. Changing direction has the side effect of closing region, and | |
249 | /// traversing past TopIdx or BottomIdx reopens it. | |
250 | class RegPressureTracker { | |
251 | const MachineFunction *MF; | |
252 | const TargetRegisterInfo *TRI; | |
253 | const RegisterClassInfo *RCI; | |
254 | const MachineRegisterInfo *MRI; | |
255 | const LiveIntervals *LIS; | |
256 | ||
257 | /// We currently only allow pressure tracking within a block. | |
258 | const MachineBasicBlock *MBB; | |
259 | ||
260 | /// Track the max pressure within the region traversed so far. | |
261 | RegisterPressure &P; | |
262 | ||
263 | /// Run in two modes dependending on whether constructed with IntervalPressure | |
264 | /// or RegisterPressure. If requireIntervals is false, LIS are ignored. | |
265 | bool RequireIntervals; | |
266 | ||
1a4d82fc JJ |
267 | /// True if UntiedDefs will be populated. |
268 | bool TrackUntiedDefs; | |
269 | ||
223e47cc | 270 | /// Register pressure corresponds to liveness before this instruction |
970d7e83 LB |
271 | /// iterator. It may point to the end of the block or a DebugValue rather than |
272 | /// an instruction. | |
223e47cc LB |
273 | MachineBasicBlock::const_iterator CurrPos; |
274 | ||
275 | /// Pressure map indexed by pressure set ID, not class ID. | |
276 | std::vector<unsigned> CurrSetPressure; | |
277 | ||
970d7e83 LB |
278 | /// Set of live registers. |
279 | LiveRegSet LiveRegs; | |
223e47cc | 280 | |
1a4d82fc JJ |
281 | /// Set of vreg defs that start a live range. |
282 | SparseSet<unsigned, VirtReg2IndexFunctor> UntiedDefs; | |
283 | /// Live-through pressure. | |
284 | std::vector<unsigned> LiveThruPressure; | |
285 | ||
223e47cc LB |
286 | public: |
287 | RegPressureTracker(IntervalPressure &rp) : | |
1a4d82fc JJ |
288 | MF(nullptr), TRI(nullptr), RCI(nullptr), LIS(nullptr), MBB(nullptr), P(rp), |
289 | RequireIntervals(true), TrackUntiedDefs(false) {} | |
223e47cc LB |
290 | |
291 | RegPressureTracker(RegionPressure &rp) : | |
1a4d82fc JJ |
292 | MF(nullptr), TRI(nullptr), RCI(nullptr), LIS(nullptr), MBB(nullptr), P(rp), |
293 | RequireIntervals(false), TrackUntiedDefs(false) {} | |
294 | ||
295 | void reset(); | |
223e47cc LB |
296 | |
297 | void init(const MachineFunction *mf, const RegisterClassInfo *rci, | |
298 | const LiveIntervals *lis, const MachineBasicBlock *mbb, | |
1a4d82fc JJ |
299 | MachineBasicBlock::const_iterator pos, |
300 | bool ShouldTrackUntiedDefs = false); | |
223e47cc | 301 | |
970d7e83 LB |
302 | /// Force liveness of virtual registers or physical register |
303 | /// units. Particularly useful to initialize the livein/out state of the | |
304 | /// tracker before the first call to advance/recede. | |
223e47cc LB |
305 | void addLiveRegs(ArrayRef<unsigned> Regs); |
306 | ||
307 | /// Get the MI position corresponding to this register pressure. | |
308 | MachineBasicBlock::const_iterator getPos() const { return CurrPos; } | |
309 | ||
310 | // Reset the MI position corresponding to the register pressure. This allows | |
311 | // schedulers to move instructions above the RegPressureTracker's | |
312 | // CurrPos. Since the pressure is computed before CurrPos, the iterator | |
313 | // position changes while pressure does not. | |
314 | void setPos(MachineBasicBlock::const_iterator Pos) { CurrPos = Pos; } | |
315 | ||
970d7e83 LB |
316 | /// \brief Get the SlotIndex for the first nondebug instruction including or |
317 | /// after the current position. | |
318 | SlotIndex getCurrSlot() const; | |
319 | ||
223e47cc | 320 | /// Recede across the previous instruction. |
1a4d82fc JJ |
321 | bool recede(SmallVectorImpl<unsigned> *LiveUses = nullptr, |
322 | PressureDiff *PDiff = nullptr); | |
223e47cc LB |
323 | |
324 | /// Advance across the current instruction. | |
325 | bool advance(); | |
326 | ||
327 | /// Finalize the region boundaries and recored live ins and live outs. | |
328 | void closeRegion(); | |
329 | ||
1a4d82fc JJ |
330 | /// Initialize the LiveThru pressure set based on the untied defs found in |
331 | /// RPTracker. | |
332 | void initLiveThru(const RegPressureTracker &RPTracker); | |
333 | ||
334 | /// Copy an existing live thru pressure result. | |
335 | void initLiveThru(ArrayRef<unsigned> PressureSet) { | |
336 | LiveThruPressure.assign(PressureSet.begin(), PressureSet.end()); | |
337 | } | |
338 | ||
339 | ArrayRef<unsigned> getLiveThru() const { return LiveThruPressure; } | |
340 | ||
223e47cc LB |
341 | /// Get the resulting register pressure over the traversed region. |
342 | /// This result is complete if either advance() or recede() has returned true, | |
343 | /// or if closeRegion() was explicitly invoked. | |
344 | RegisterPressure &getPressure() { return P; } | |
970d7e83 | 345 | const RegisterPressure &getPressure() const { return P; } |
223e47cc LB |
346 | |
347 | /// Get the register set pressure at the current position, which may be less | |
348 | /// than the pressure across the traversed region. | |
349 | std::vector<unsigned> &getRegSetPressureAtPos() { return CurrSetPressure; } | |
350 | ||
970d7e83 LB |
351 | void discoverLiveOut(unsigned Reg); |
352 | void discoverLiveIn(unsigned Reg); | |
223e47cc LB |
353 | |
354 | bool isTopClosed() const; | |
355 | bool isBottomClosed() const; | |
356 | ||
357 | void closeTop(); | |
358 | void closeBottom(); | |
359 | ||
360 | /// Consider the pressure increase caused by traversing this instruction | |
361 | /// bottom-up. Find the pressure set with the most change beyond its pressure | |
362 | /// limit based on the tracker's current pressure, and record the number of | |
363 | /// excess register units of that pressure set introduced by this instruction. | |
364 | void getMaxUpwardPressureDelta(const MachineInstr *MI, | |
1a4d82fc | 365 | PressureDiff *PDiff, |
223e47cc | 366 | RegPressureDelta &Delta, |
1a4d82fc | 367 | ArrayRef<PressureChange> CriticalPSets, |
223e47cc LB |
368 | ArrayRef<unsigned> MaxPressureLimit); |
369 | ||
1a4d82fc JJ |
370 | void getUpwardPressureDelta(const MachineInstr *MI, |
371 | /*const*/ PressureDiff &PDiff, | |
372 | RegPressureDelta &Delta, | |
373 | ArrayRef<PressureChange> CriticalPSets, | |
374 | ArrayRef<unsigned> MaxPressureLimit) const; | |
375 | ||
223e47cc LB |
376 | /// Consider the pressure increase caused by traversing this instruction |
377 | /// top-down. Find the pressure set with the most change beyond its pressure | |
378 | /// limit based on the tracker's current pressure, and record the number of | |
379 | /// excess register units of that pressure set introduced by this instruction. | |
380 | void getMaxDownwardPressureDelta(const MachineInstr *MI, | |
381 | RegPressureDelta &Delta, | |
1a4d82fc | 382 | ArrayRef<PressureChange> CriticalPSets, |
223e47cc LB |
383 | ArrayRef<unsigned> MaxPressureLimit); |
384 | ||
385 | /// Find the pressure set with the most change beyond its pressure limit after | |
386 | /// traversing this instruction either upward or downward depending on the | |
387 | /// closed end of the current region. | |
1a4d82fc JJ |
388 | void getMaxPressureDelta(const MachineInstr *MI, |
389 | RegPressureDelta &Delta, | |
390 | ArrayRef<PressureChange> CriticalPSets, | |
223e47cc LB |
391 | ArrayRef<unsigned> MaxPressureLimit) { |
392 | if (isTopClosed()) | |
393 | return getMaxDownwardPressureDelta(MI, Delta, CriticalPSets, | |
394 | MaxPressureLimit); | |
395 | ||
396 | assert(isBottomClosed() && "Uninitialized pressure tracker"); | |
1a4d82fc | 397 | return getMaxUpwardPressureDelta(MI, nullptr, Delta, CriticalPSets, |
223e47cc LB |
398 | MaxPressureLimit); |
399 | } | |
400 | ||
401 | /// Get the pressure of each PSet after traversing this instruction bottom-up. | |
402 | void getUpwardPressure(const MachineInstr *MI, | |
403 | std::vector<unsigned> &PressureResult, | |
404 | std::vector<unsigned> &MaxPressureResult); | |
405 | ||
406 | /// Get the pressure of each PSet after traversing this instruction top-down. | |
407 | void getDownwardPressure(const MachineInstr *MI, | |
408 | std::vector<unsigned> &PressureResult, | |
409 | std::vector<unsigned> &MaxPressureResult); | |
410 | ||
411 | void getPressureAfterInst(const MachineInstr *MI, | |
412 | std::vector<unsigned> &PressureResult, | |
413 | std::vector<unsigned> &MaxPressureResult) { | |
414 | if (isTopClosed()) | |
415 | return getUpwardPressure(MI, PressureResult, MaxPressureResult); | |
416 | ||
417 | assert(isBottomClosed() && "Uninitialized pressure tracker"); | |
418 | return getDownwardPressure(MI, PressureResult, MaxPressureResult); | |
419 | } | |
420 | ||
1a4d82fc JJ |
421 | bool hasUntiedDef(unsigned VirtReg) const { |
422 | return UntiedDefs.count(VirtReg); | |
423 | } | |
424 | ||
970d7e83 LB |
425 | void dump() const; |
426 | ||
223e47cc | 427 | protected: |
1a4d82fc | 428 | const LiveRange *getLiveRange(unsigned Reg) const; |
223e47cc | 429 | |
970d7e83 LB |
430 | void increaseRegPressure(ArrayRef<unsigned> Regs); |
431 | void decreaseRegPressure(ArrayRef<unsigned> Regs); | |
223e47cc LB |
432 | |
433 | void bumpUpwardPressure(const MachineInstr *MI); | |
434 | void bumpDownwardPressure(const MachineInstr *MI); | |
435 | }; | |
1a4d82fc JJ |
436 | |
437 | void dumpRegSetPressure(ArrayRef<unsigned> SetPressure, | |
438 | const TargetRegisterInfo *TRI); | |
223e47cc LB |
439 | } // end namespace llvm |
440 | ||
441 | #endif |