1 //===- GCNRegPressure.h -----------------------------------------*- C++ -*-===//
2 //
3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4 // See https://llvm.org/LICENSE.txt for license information.
5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6 //
7 //===----------------------------------------------------------------------===//
8 ///
9 /// \file
10 /// This file defines the GCNRegPressure class, which tracks registry pressure
11 /// by bookkeeping number of SGPR/VGPRs used, weights for large SGPR/VGPRs. It
12 /// also implements a compare function, which compares different register
13 /// pressures, and declares one with max occupance as winner.
14 ///
15 //===----------------------------------------------------------------------===//
16 
17 #ifndef LLVM_LIB_TARGET_AMDGPU_GCNREGPRESSURE_H
18 #define LLVM_LIB_TARGET_AMDGPU_GCNREGPRESSURE_H
19 
20 #include "GCNSubtarget.h"
21 #include "llvm/CodeGen/LiveIntervals.h"
22 #include <algorithm>
23 
24 namespace llvm {
25 
26 class MachineRegisterInfo;
27 class raw_ostream;
28 class SlotIndex;
29 
30 struct GCNRegPressure {
31   enum RegKind {
32     SGPR32,
33     SGPR_TUPLE,
34     VGPR32,
35     VGPR_TUPLE,
36     AGPR32,
37     AGPR_TUPLE,
38     TOTAL_KINDS
39   };
40 
41   GCNRegPressure() {
42     clear();
43   }
44 
45   bool empty() const { return getSGPRNum() == 0 && getVGPRNum() == 0; }
46 
47   void clear() { std::fill(&Value[0], &Value[TOTAL_KINDS], 0); }
48 
49   unsigned getSGPRNum() const { return Value[SGPR32]; }
50   unsigned getVGPRNum() const { return std::max(Value[VGPR32], Value[AGPR32]); }
51 
52   unsigned getVGPRTuplesWeight() const { return std::max(Value[VGPR_TUPLE],
53                                                          Value[AGPR_TUPLE]); }
54   unsigned getSGPRTuplesWeight() const { return Value[SGPR_TUPLE]; }
55 
56   unsigned getOccupancy(const GCNSubtarget &ST) const {
57     return std::min(ST.getOccupancyWithNumSGPRs(getSGPRNum()),
58                     ST.getOccupancyWithNumVGPRs(getVGPRNum()));
59   }
60 
61   void inc(unsigned Reg,
62            LaneBitmask PrevMask,
63            LaneBitmask NewMask,
64            const MachineRegisterInfo &MRI);
65 
66   bool higherOccupancy(const GCNSubtarget &ST, const GCNRegPressure& O) const {
67     return getOccupancy(ST) > O.getOccupancy(ST);
68   }
69 
70   bool less(const GCNSubtarget &ST, const GCNRegPressure& O,
71     unsigned MaxOccupancy = std::numeric_limits<unsigned>::max()) const;
72 
73   bool operator==(const GCNRegPressure &O) const {
74     return std::equal(&Value[0], &Value[TOTAL_KINDS], O.Value);
75   }
76 
77   bool operator!=(const GCNRegPressure &O) const {
78     return !(*this == O);
79   }
80 
81   void print(raw_ostream &OS, const GCNSubtarget *ST = nullptr) const;
82   void dump() const { print(dbgs()); }
83 
84 private:
85   unsigned Value[TOTAL_KINDS];
86 
87   static unsigned getRegKind(Register Reg, const MachineRegisterInfo &MRI);
88 
89   friend GCNRegPressure max(const GCNRegPressure &P1,
90                             const GCNRegPressure &P2);
91 };
92 
93 inline GCNRegPressure max(const GCNRegPressure &P1, const GCNRegPressure &P2) {
94   GCNRegPressure Res;
95   for (unsigned I = 0; I < GCNRegPressure::TOTAL_KINDS; ++I)
96     Res.Value[I] = std::max(P1.Value[I], P2.Value[I]);
97   return Res;
98 }
99 
100 class GCNRPTracker {
101 public:
102   using LiveRegSet = DenseMap<unsigned, LaneBitmask>;
103 
104 protected:
105   const LiveIntervals &LIS;
106   LiveRegSet LiveRegs;
107   GCNRegPressure CurPressure, MaxPressure;
108   const MachineInstr *LastTrackedMI = nullptr;
109   mutable const MachineRegisterInfo *MRI = nullptr;
110 
111   GCNRPTracker(const LiveIntervals &LIS_) : LIS(LIS_) {}
112 
113   void reset(const MachineInstr &MI, const LiveRegSet *LiveRegsCopy,
114              bool After);
115 
116 public:
117   // live regs for the current state
118   const decltype(LiveRegs) &getLiveRegs() const { return LiveRegs; }
119   const MachineInstr *getLastTrackedMI() const { return LastTrackedMI; }
120 
121   void clearMaxPressure() { MaxPressure.clear(); }
122 
123   // returns MaxPressure, resetting it
124   decltype(MaxPressure) moveMaxPressure() {
125     auto Res = MaxPressure;
126     MaxPressure.clear();
127     return Res;
128   }
129 
130   decltype(LiveRegs) moveLiveRegs() {
131     return std::move(LiveRegs);
132   }
133 
134   static void printLiveRegs(raw_ostream &OS, const LiveRegSet& LiveRegs,
135                             const MachineRegisterInfo &MRI);
136 };
137 
138 class GCNUpwardRPTracker : public GCNRPTracker {
139 public:
140   GCNUpwardRPTracker(const LiveIntervals &LIS_) : GCNRPTracker(LIS_) {}
141 
142   // reset tracker to the point just below MI
143   // filling live regs upon this point using LIS
144   void reset(const MachineInstr &MI, const LiveRegSet *LiveRegs = nullptr);
145 
146   // move to the state just above the MI
147   void recede(const MachineInstr &MI);
148 
149   // checks whether the tracker's state after receding MI corresponds
150   // to reported by LIS
151   bool isValid() const;
152 };
153 
154 class GCNDownwardRPTracker : public GCNRPTracker {
155   // Last position of reset or advanceBeforeNext
156   MachineBasicBlock::const_iterator NextMI;
157 
158   MachineBasicBlock::const_iterator MBBEnd;
159 
160 public:
161   GCNDownwardRPTracker(const LiveIntervals &LIS_) : GCNRPTracker(LIS_) {}
162 
163   const MachineBasicBlock::const_iterator getNext() const { return NextMI; }
164 
165   // Reset tracker to the point before the MI
166   // filling live regs upon this point using LIS.
167   // Returns false if block is empty except debug values.
168   bool reset(const MachineInstr &MI, const LiveRegSet *LiveRegs = nullptr);
169 
170   // Move to the state right before the next MI. Returns false if reached
171   // end of the block.
172   bool advanceBeforeNext();
173 
174   // Move to the state at the MI, advanceBeforeNext has to be called first.
175   void advanceToNext();
176 
177   // Move to the state at the next MI. Returns false if reached end of block.
178   bool advance();
179 
180   // Advance instructions until before End.
181   bool advance(MachineBasicBlock::const_iterator End);
182 
183   // Reset to Begin and advance to End.
184   bool advance(MachineBasicBlock::const_iterator Begin,
185                MachineBasicBlock::const_iterator End,
186                const LiveRegSet *LiveRegsCopy = nullptr);
187 };
188 
189 LaneBitmask getLiveLaneMask(unsigned Reg,
190                             SlotIndex SI,
191                             const LiveIntervals &LIS,
192                             const MachineRegisterInfo &MRI);
193 
194 GCNRPTracker::LiveRegSet getLiveRegs(SlotIndex SI,
195                                      const LiveIntervals &LIS,
196                                      const MachineRegisterInfo &MRI);
197 
198 /// creates a map MachineInstr -> LiveRegSet
199 /// R - range of iterators on instructions
200 /// After - upon entry or exit of every instruction
201 /// Note: there is no entry in the map for instructions with empty live reg set
202 /// Complexity = O(NumVirtRegs * averageLiveRangeSegmentsPerReg * lg(R))
203 template <typename Range>
204 DenseMap<MachineInstr*, GCNRPTracker::LiveRegSet>
205 getLiveRegMap(Range &&R, bool After, LiveIntervals &LIS) {
206   std::vector<SlotIndex> Indexes;
207   Indexes.reserve(std::distance(R.begin(), R.end()));
208   auto &SII = *LIS.getSlotIndexes();
209   for (MachineInstr *I : R) {
210     auto SI = SII.getInstructionIndex(*I);
211     Indexes.push_back(After ? SI.getDeadSlot() : SI.getBaseIndex());
212   }
213   llvm::sort(Indexes);
214 
215   auto &MRI = (*R.begin())->getParent()->getParent()->getRegInfo();
216   DenseMap<MachineInstr *, GCNRPTracker::LiveRegSet> LiveRegMap;
217   SmallVector<SlotIndex, 32> LiveIdxs, SRLiveIdxs;
218   for (unsigned I = 0, E = MRI.getNumVirtRegs(); I != E; ++I) {
219     auto Reg = Register::index2VirtReg(I);
220     if (!LIS.hasInterval(Reg))
221       continue;
222     auto &LI = LIS.getInterval(Reg);
223     LiveIdxs.clear();
224     if (!LI.findIndexesLiveAt(Indexes, std::back_inserter(LiveIdxs)))
225       continue;
226     if (!LI.hasSubRanges()) {
227       for (auto SI : LiveIdxs)
228         LiveRegMap[SII.getInstructionFromIndex(SI)][Reg] =
229           MRI.getMaxLaneMaskForVReg(Reg);
230     } else
231       for (const auto &S : LI.subranges()) {
232         // constrain search for subranges by indexes live at main range
233         SRLiveIdxs.clear();
234         S.findIndexesLiveAt(LiveIdxs, std::back_inserter(SRLiveIdxs));
235         for (auto SI : SRLiveIdxs)
236           LiveRegMap[SII.getInstructionFromIndex(SI)][Reg] |= S.LaneMask;
237       }
238   }
239   return LiveRegMap;
240 }
241 
242 inline GCNRPTracker::LiveRegSet getLiveRegsAfter(const MachineInstr &MI,
243                                                  const LiveIntervals &LIS) {
244   return getLiveRegs(LIS.getInstructionIndex(MI).getDeadSlot(), LIS,
245                      MI.getParent()->getParent()->getRegInfo());
246 }
247 
248 inline GCNRPTracker::LiveRegSet getLiveRegsBefore(const MachineInstr &MI,
249                                                   const LiveIntervals &LIS) {
250   return getLiveRegs(LIS.getInstructionIndex(MI).getBaseIndex(), LIS,
251                      MI.getParent()->getParent()->getRegInfo());
252 }
253 
254 template <typename Range>
255 GCNRegPressure getRegPressure(const MachineRegisterInfo &MRI,
256                               Range &&LiveRegs) {
257   GCNRegPressure Res;
258   for (const auto &RM : LiveRegs)
259     Res.inc(RM.first, LaneBitmask::getNone(), RM.second, MRI);
260   return Res;
261 }
262 
263 bool isEqual(const GCNRPTracker::LiveRegSet &S1,
264              const GCNRPTracker::LiveRegSet &S2);
265 
266 void printLivesAt(SlotIndex SI,
267                   const LiveIntervals &LIS,
268                   const MachineRegisterInfo &MRI);
269 
270 } // end namespace llvm
271 
272 #endif // LLVM_LIB_TARGET_AMDGPU_GCNREGPRESSURE_H
273