1 //===-- RegisterPressure.h - Dynamic Register Pressure -*- C++ -*-------===//
3 // The LLVM Compiler Infrastructure
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
8 //===----------------------------------------------------------------------===//
10 // This file defines the RegisterPressure class which can be used to track
11 // MachineInstr level register pressure.
13 //===----------------------------------------------------------------------===//
15 #ifndef LLVM_CODEGEN_REGISTERPRESSURE_H
16 #define LLVM_CODEGEN_REGISTERPRESSURE_H
18 #include "llvm/ADT/SparseSet.h"
19 #include "llvm/CodeGen/SlotIndexes.h"
20 #include "llvm/Target/TargetRegisterInfo.h"
26 class RegisterClassInfo;
29 struct RegisterMaskPair {
30 unsigned RegUnit; ///< Virtual register or register unit.
33 RegisterMaskPair(unsigned RegUnit, LaneBitmask LaneMask)
34 : RegUnit(RegUnit), LaneMask(LaneMask) {}
37 /// Base class for register pressure results.
38 struct RegisterPressure {
39 /// Map of max reg pressure indexed by pressure set ID, not class ID.
40 std::vector<unsigned> MaxSetPressure;
42 /// List of live in virtual registers or physical register units.
43 SmallVector<RegisterMaskPair,8> LiveInRegs;
44 SmallVector<RegisterMaskPair,8> LiveOutRegs;
46 void dump(const TargetRegisterInfo *TRI) const;
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.
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.
65 void openTop(SlotIndex NextTop);
67 void openBottom(SlotIndex PrevBottom);
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;
80 void openTop(MachineBasicBlock::const_iterator PrevTop);
82 void openBottom(MachineBasicBlock::const_iterator PrevBottom);
85 /// Capture a change in pressure for a single pressure set. UnitInc may be
86 /// expressed in terms of upward or downward pressure depending on the client
87 /// and will be dynamically adjusted for current liveness.
89 /// Pressure increments are tiny, typically 1-2 units, and this is only for
90 /// heuristics, so we don't check UnitInc overflow. Instead, we may have a
91 /// higher level assert that pressure is consistent within a region. We also
92 /// effectively ignore dead defs which don't affect heuristics much.
93 class PressureChange {
94 uint16_t PSetID; // ID+1. 0=Invalid.
97 PressureChange(): PSetID(0), UnitInc(0) {}
98 PressureChange(unsigned id): PSetID(id+1), UnitInc(0) {
99 assert(id < UINT16_MAX && "PSetID overflow.");
102 bool isValid() const { return PSetID > 0; }
104 unsigned getPSet() const {
105 assert(isValid() && "invalid PressureChange");
108 // If PSetID is invalid, return UINT16_MAX to give it lowest priority.
109 unsigned getPSetOrMax() const { return (PSetID - 1) & UINT16_MAX; }
111 int getUnitInc() const { return UnitInc; }
113 void setUnitInc(int Inc) { UnitInc = Inc; }
115 bool operator==(const PressureChange &RHS) const {
116 return PSetID == RHS.PSetID && UnitInc == RHS.UnitInc;
120 template <> struct isPodLike<PressureChange> {
121 static const bool value = true;
124 /// List of PressureChanges in order of increasing, unique PSetID.
126 /// Use a small fixed number, because we can fit more PressureChanges in an
127 /// empty SmallVector than ever need to be tracked per register class. If more
128 /// PSets are affected, then we only track the most constrained.
130 // The initial design was for MaxPSets=4, but that requires PSet partitions,
131 // which are not yet implemented. (PSet partitions are equivalent PSets given
132 // the register classes actually in use within the scheduling region.)
133 enum { MaxPSets = 16 };
135 PressureChange PressureChanges[MaxPSets];
137 typedef PressureChange* iterator;
138 iterator nonconst_begin() { return &PressureChanges[0]; }
139 iterator nonconst_end() { return &PressureChanges[MaxPSets]; }
142 typedef const PressureChange* const_iterator;
143 const_iterator begin() const { return &PressureChanges[0]; }
144 const_iterator end() const { return &PressureChanges[MaxPSets]; }
146 void addPressureChange(unsigned RegUnit, bool IsDec,
147 const MachineRegisterInfo *MRI);
149 LLVM_DUMP_METHOD void dump(const TargetRegisterInfo &TRI) const;
152 /// List of registers defined and used by a machine instruction.
153 class RegisterOperands {
155 /// List of virtual registers and register units read by the instruction.
156 SmallVector<RegisterMaskPair, 8> Uses;
157 /// \brief List of virtual registers and register units defined by the
158 /// instruction which are not dead.
159 SmallVector<RegisterMaskPair, 8> Defs;
160 /// \brief List of virtual registers and register units defined by the
161 /// instruction but dead.
162 SmallVector<RegisterMaskPair, 8> DeadDefs;
164 /// Analyze the given instruction \p MI and fill in the Uses, Defs and
165 /// DeadDefs list based on the MachineOperand flags.
166 void collect(const MachineInstr &MI, const TargetRegisterInfo &TRI,
167 const MachineRegisterInfo &MRI, bool TrackLaneMasks,
170 /// Use liveness information to find dead defs not marked with a dead flag
171 /// and move them to the DeadDefs vector.
172 void detectDeadDefs(const MachineInstr &MI, const LiveIntervals &LIS);
174 /// Use liveness information to find out which uses/defs are partially
175 /// undefined/dead and adjust the RegisterMaskPairs accordingly.
176 /// If \p AddFlagsMI is given then missing read-undef and dead flags will be
177 /// added to the instruction.
178 void adjustLaneLiveness(const LiveIntervals &LIS,
179 const MachineRegisterInfo &MRI, SlotIndex Pos,
180 MachineInstr *AddFlagsMI = nullptr);
183 /// Array of PressureDiffs.
184 class PressureDiffs {
185 PressureDiff *PDiffArray;
189 PressureDiffs(): PDiffArray(nullptr), Size(0), Max(0) {}
190 ~PressureDiffs() { free(PDiffArray); }
192 void clear() { Size = 0; }
194 void init(unsigned N);
196 PressureDiff &operator[](unsigned Idx) {
197 assert(Idx < Size && "PressureDiff index out of bounds");
198 return PDiffArray[Idx];
200 const PressureDiff &operator[](unsigned Idx) const {
201 return const_cast<PressureDiffs*>(this)->operator[](Idx);
203 /// \brief Record pressure difference induced by the given operand list to
204 /// node with index \p Idx.
205 void addInstruction(unsigned Idx, const RegisterOperands &RegOpers,
206 const MachineRegisterInfo &MRI);
209 /// Store the effects of a change in pressure on things that MI scheduler cares
212 /// Excess records the value of the largest difference in register units beyond
213 /// the target's pressure limits across the affected pressure sets, where
214 /// largest is defined as the absolute value of the difference. Negative
215 /// ExcessUnits indicates a reduction in pressure that had already exceeded the
218 /// CriticalMax records the largest increase in the tracker's max pressure that
219 /// exceeds the critical limit for some pressure set determined by the client.
221 /// CurrentMax records the largest increase in the tracker's max pressure that
222 /// exceeds the current limit for some pressure set determined by the client.
223 struct RegPressureDelta {
224 PressureChange Excess;
225 PressureChange CriticalMax;
226 PressureChange CurrentMax;
228 RegPressureDelta() {}
230 bool operator==(const RegPressureDelta &RHS) const {
231 return Excess == RHS.Excess && CriticalMax == RHS.CriticalMax
232 && CurrentMax == RHS.CurrentMax;
234 bool operator!=(const RegPressureDelta &RHS) const {
235 return !operator==(RHS);
239 /// A set of live virtual registers and physical register units.
241 /// This is a wrapper around a SparseSet which deals with mapping register unit
242 /// and virtual register indexes to an index usable by the sparse set.
245 struct IndexMaskPair {
247 LaneBitmask LaneMask;
249 IndexMaskPair(unsigned Index, LaneBitmask LaneMask)
250 : Index(Index), LaneMask(LaneMask) {}
252 unsigned getSparseSetIndex() const {
257 typedef SparseSet<IndexMaskPair> RegSet;
259 unsigned NumRegUnits;
261 unsigned getSparseIndexFromReg(unsigned Reg) const {
262 if (TargetRegisterInfo::isVirtualRegister(Reg))
263 return TargetRegisterInfo::virtReg2Index(Reg) + NumRegUnits;
264 assert(Reg < NumRegUnits);
267 unsigned getRegFromSparseIndex(unsigned SparseIndex) const {
268 if (SparseIndex >= NumRegUnits)
269 return TargetRegisterInfo::index2VirtReg(SparseIndex-NumRegUnits);
275 void init(const MachineRegisterInfo &MRI);
277 LaneBitmask contains(unsigned Reg) const {
278 unsigned SparseIndex = getSparseIndexFromReg(Reg);
279 RegSet::const_iterator I = Regs.find(SparseIndex);
281 return LaneBitmask::getNone();
285 /// Mark the \p Pair.LaneMask lanes of \p Pair.Reg as live.
286 /// Returns the previously live lanes of \p Pair.Reg.
287 LaneBitmask insert(RegisterMaskPair Pair) {
288 unsigned SparseIndex = getSparseIndexFromReg(Pair.RegUnit);
289 auto InsertRes = Regs.insert(IndexMaskPair(SparseIndex, Pair.LaneMask));
290 if (!InsertRes.second) {
291 LaneBitmask PrevMask = InsertRes.first->LaneMask;
292 InsertRes.first->LaneMask |= Pair.LaneMask;
295 return LaneBitmask::getNone();
298 /// Clears the \p Pair.LaneMask lanes of \p Pair.Reg (mark them as dead).
299 /// Returns the previously live lanes of \p Pair.Reg.
300 LaneBitmask erase(RegisterMaskPair Pair) {
301 unsigned SparseIndex = getSparseIndexFromReg(Pair.RegUnit);
302 RegSet::iterator I = Regs.find(SparseIndex);
304 return LaneBitmask::getNone();
305 LaneBitmask PrevMask = I->LaneMask;
306 I->LaneMask &= ~Pair.LaneMask;
310 size_t size() const {
314 template<typename ContainerT>
315 void appendTo(ContainerT &To) const {
316 for (const IndexMaskPair &P : Regs) {
317 unsigned Reg = getRegFromSparseIndex(P.Index);
318 if (P.LaneMask.any())
319 To.push_back(RegisterMaskPair(Reg, P.LaneMask));
324 /// Track the current register pressure at some position in the instruction
325 /// stream, and remember the high water mark within the region traversed. This
326 /// does not automatically consider live-through ranges. The client may
327 /// independently adjust for global liveness.
329 /// Each RegPressureTracker only works within a MachineBasicBlock. Pressure can
330 /// be tracked across a larger region by storing a RegisterPressure result at
331 /// each block boundary and explicitly adjusting pressure to account for block
332 /// live-in and live-out register sets.
334 /// RegPressureTracker holds a reference to a RegisterPressure result that it
335 /// computes incrementally. During downward tracking, P.BottomIdx or P.BottomPos
336 /// is invalid until it reaches the end of the block or closeRegion() is
337 /// explicitly called. Similarly, P.TopIdx is invalid during upward
338 /// tracking. Changing direction has the side effect of closing region, and
339 /// traversing past TopIdx or BottomIdx reopens it.
340 class RegPressureTracker {
341 const MachineFunction *MF;
342 const TargetRegisterInfo *TRI;
343 const RegisterClassInfo *RCI;
344 const MachineRegisterInfo *MRI;
345 const LiveIntervals *LIS;
347 /// We currently only allow pressure tracking within a block.
348 const MachineBasicBlock *MBB;
350 /// Track the max pressure within the region traversed so far.
353 /// Run in two modes dependending on whether constructed with IntervalPressure
354 /// or RegisterPressure. If requireIntervals is false, LIS are ignored.
355 bool RequireIntervals;
357 /// True if UntiedDefs will be populated.
358 bool TrackUntiedDefs;
360 /// True if lanemasks should be tracked.
363 /// Register pressure corresponds to liveness before this instruction
364 /// iterator. It may point to the end of the block or a DebugValue rather than
366 MachineBasicBlock::const_iterator CurrPos;
368 /// Pressure map indexed by pressure set ID, not class ID.
369 std::vector<unsigned> CurrSetPressure;
371 /// Set of live registers.
374 /// Set of vreg defs that start a live range.
375 SparseSet<unsigned, VirtReg2IndexFunctor> UntiedDefs;
376 /// Live-through pressure.
377 std::vector<unsigned> LiveThruPressure;
380 RegPressureTracker(IntervalPressure &rp) :
381 MF(nullptr), TRI(nullptr), RCI(nullptr), LIS(nullptr), MBB(nullptr), P(rp),
382 RequireIntervals(true), TrackUntiedDefs(false), TrackLaneMasks(false) {}
384 RegPressureTracker(RegionPressure &rp) :
385 MF(nullptr), TRI(nullptr), RCI(nullptr), LIS(nullptr), MBB(nullptr), P(rp),
386 RequireIntervals(false), TrackUntiedDefs(false), TrackLaneMasks(false) {}
390 void init(const MachineFunction *mf, const RegisterClassInfo *rci,
391 const LiveIntervals *lis, const MachineBasicBlock *mbb,
392 MachineBasicBlock::const_iterator pos,
393 bool TrackLaneMasks, bool TrackUntiedDefs);
395 /// Force liveness of virtual registers or physical register
396 /// units. Particularly useful to initialize the livein/out state of the
397 /// tracker before the first call to advance/recede.
398 void addLiveRegs(ArrayRef<RegisterMaskPair> Regs);
400 /// Get the MI position corresponding to this register pressure.
401 MachineBasicBlock::const_iterator getPos() const { return CurrPos; }
403 // Reset the MI position corresponding to the register pressure. This allows
404 // schedulers to move instructions above the RegPressureTracker's
405 // CurrPos. Since the pressure is computed before CurrPos, the iterator
406 // position changes while pressure does not.
407 void setPos(MachineBasicBlock::const_iterator Pos) { CurrPos = Pos; }
409 /// Recede across the previous instruction.
410 void recede(SmallVectorImpl<RegisterMaskPair> *LiveUses = nullptr);
412 /// Recede across the previous instruction.
413 /// This "low-level" variant assumes that recedeSkipDebugValues() was
414 /// called previously and takes precomputed RegisterOperands for the
416 void recede(const RegisterOperands &RegOpers,
417 SmallVectorImpl<RegisterMaskPair> *LiveUses = nullptr);
419 /// Recede until we find an instruction which is not a DebugValue.
420 void recedeSkipDebugValues();
422 /// Advance across the current instruction.
425 /// Advance across the current instruction.
426 /// This is a "low-level" variant of advance() which takes precomputed
427 /// RegisterOperands of the instruction.
428 void advance(const RegisterOperands &RegOpers);
430 /// Finalize the region boundaries and recored live ins and live outs.
433 /// Initialize the LiveThru pressure set based on the untied defs found in
435 void initLiveThru(const RegPressureTracker &RPTracker);
437 /// Copy an existing live thru pressure result.
438 void initLiveThru(ArrayRef<unsigned> PressureSet) {
439 LiveThruPressure.assign(PressureSet.begin(), PressureSet.end());
442 ArrayRef<unsigned> getLiveThru() const { return LiveThruPressure; }
444 /// Get the resulting register pressure over the traversed region.
445 /// This result is complete if closeRegion() was explicitly invoked.
446 RegisterPressure &getPressure() { return P; }
447 const RegisterPressure &getPressure() const { return P; }
449 /// Get the register set pressure at the current position, which may be less
450 /// than the pressure across the traversed region.
451 const std::vector<unsigned> &getRegSetPressureAtPos() const {
452 return CurrSetPressure;
455 bool isTopClosed() const;
456 bool isBottomClosed() const;
461 /// Consider the pressure increase caused by traversing this instruction
462 /// bottom-up. Find the pressure set with the most change beyond its pressure
463 /// limit based on the tracker's current pressure, and record the number of
464 /// excess register units of that pressure set introduced by this instruction.
465 void getMaxUpwardPressureDelta(const MachineInstr *MI,
467 RegPressureDelta &Delta,
468 ArrayRef<PressureChange> CriticalPSets,
469 ArrayRef<unsigned> MaxPressureLimit);
471 void getUpwardPressureDelta(const MachineInstr *MI,
472 /*const*/ PressureDiff &PDiff,
473 RegPressureDelta &Delta,
474 ArrayRef<PressureChange> CriticalPSets,
475 ArrayRef<unsigned> MaxPressureLimit) const;
477 /// Consider the pressure increase caused by traversing this instruction
478 /// top-down. Find the pressure set with the most change beyond its pressure
479 /// limit based on the tracker's current pressure, and record the number of
480 /// excess register units of that pressure set introduced by this instruction.
481 void getMaxDownwardPressureDelta(const MachineInstr *MI,
482 RegPressureDelta &Delta,
483 ArrayRef<PressureChange> CriticalPSets,
484 ArrayRef<unsigned> MaxPressureLimit);
486 /// Find the pressure set with the most change beyond its pressure limit after
487 /// traversing this instruction either upward or downward depending on the
488 /// closed end of the current region.
489 void getMaxPressureDelta(const MachineInstr *MI,
490 RegPressureDelta &Delta,
491 ArrayRef<PressureChange> CriticalPSets,
492 ArrayRef<unsigned> MaxPressureLimit) {
494 return getMaxDownwardPressureDelta(MI, Delta, CriticalPSets,
497 assert(isBottomClosed() && "Uninitialized pressure tracker");
498 return getMaxUpwardPressureDelta(MI, nullptr, Delta, CriticalPSets,
502 /// Get the pressure of each PSet after traversing this instruction bottom-up.
503 void getUpwardPressure(const MachineInstr *MI,
504 std::vector<unsigned> &PressureResult,
505 std::vector<unsigned> &MaxPressureResult);
507 /// Get the pressure of each PSet after traversing this instruction top-down.
508 void getDownwardPressure(const MachineInstr *MI,
509 std::vector<unsigned> &PressureResult,
510 std::vector<unsigned> &MaxPressureResult);
512 void getPressureAfterInst(const MachineInstr *MI,
513 std::vector<unsigned> &PressureResult,
514 std::vector<unsigned> &MaxPressureResult) {
516 return getUpwardPressure(MI, PressureResult, MaxPressureResult);
518 assert(isBottomClosed() && "Uninitialized pressure tracker");
519 return getDownwardPressure(MI, PressureResult, MaxPressureResult);
522 bool hasUntiedDef(unsigned VirtReg) const {
523 return UntiedDefs.count(VirtReg);
529 /// Add Reg to the live out set and increase max pressure.
530 void discoverLiveOut(RegisterMaskPair Pair);
531 /// Add Reg to the live in set and increase max pressure.
532 void discoverLiveIn(RegisterMaskPair Pair);
534 /// \brief Get the SlotIndex for the first nondebug instruction including or
535 /// after the current position.
536 SlotIndex getCurrSlot() const;
538 void increaseRegPressure(unsigned RegUnit, LaneBitmask PreviousMask,
539 LaneBitmask NewMask);
540 void decreaseRegPressure(unsigned RegUnit, LaneBitmask PreviousMask,
541 LaneBitmask NewMask);
543 void bumpDeadDefs(ArrayRef<RegisterMaskPair> DeadDefs);
545 void bumpUpwardPressure(const MachineInstr *MI);
546 void bumpDownwardPressure(const MachineInstr *MI);
548 void discoverLiveInOrOut(RegisterMaskPair Pair,
549 SmallVectorImpl<RegisterMaskPair> &LiveInOrOut);
551 LaneBitmask getLastUsedLanes(unsigned RegUnit, SlotIndex Pos) const;
552 LaneBitmask getLiveLanesAt(unsigned RegUnit, SlotIndex Pos) const;
553 LaneBitmask getLiveThroughAt(unsigned RegUnit, SlotIndex Pos) const;
556 void dumpRegSetPressure(ArrayRef<unsigned> SetPressure,
557 const TargetRegisterInfo *TRI);
558 } // end namespace llvm