1 //===------------------------- GCNRegPressure.cpp - -----------------------===//
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 /// \file
11 //
12 //===----------------------------------------------------------------------===//
13 
14 #include "GCNRegPressure.h"
15 
16 using namespace llvm;
17 
18 #define DEBUG_TYPE "misched"
19 
20 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
21 LLVM_DUMP_METHOD
22 void llvm::printLivesAt(SlotIndex SI,
23                         const LiveIntervals &LIS,
24                         const MachineRegisterInfo &MRI) {
25   dbgs() << "Live regs at " << SI << ": "
26          << *LIS.getInstructionFromIndex(SI);
27   unsigned Num = 0;
28   for (unsigned I = 0, E = MRI.getNumVirtRegs(); I != E; ++I) {
29     const unsigned Reg = TargetRegisterInfo::index2VirtReg(I);
30     if (MRI.reg_nodbg_empty(Reg))
31       continue;
32     const auto &LI = LIS.getInterval(Reg);
33     if (LI.hasSubRanges()) {
34       bool firstTime = true;
35       for (const auto &S : LI.subranges()) {
36         if (!S.liveAt(SI)) continue;
37         if (firstTime) {
38           dbgs() << "  " << PrintReg(Reg, MRI.getTargetRegisterInfo())
39                  << '\n';
40           firstTime = false;
41         }
42         dbgs() << "  " << S << '\n';
43         ++Num;
44       }
45     } else if (LI.liveAt(SI)) {
46       dbgs() << "  " << LI << '\n';
47       ++Num;
48     }
49   }
50   if (!Num) dbgs() << "  <none>\n";
51 }
52 
53 static bool isEqual(const GCNRPTracker::LiveRegSet &S1,
54                     const GCNRPTracker::LiveRegSet &S2) {
55   if (S1.size() != S2.size())
56     return false;
57 
58   for (const auto &P : S1) {
59     auto I = S2.find(P.first);
60     if (I == S2.end() || I->second != P.second)
61       return false;
62   }
63   return true;
64 }
65 
66 static GCNRPTracker::LiveRegSet
67 stripEmpty(const GCNRPTracker::LiveRegSet &LR) {
68   GCNRPTracker::LiveRegSet Res;
69   for (const auto &P : LR) {
70     if (P.second.any())
71       Res.insert(P);
72   }
73   return Res;
74 }
75 #endif
76 
77 ///////////////////////////////////////////////////////////////////////////////
78 // GCNRegPressure
79 
80 unsigned GCNRegPressure::getRegKind(unsigned Reg,
81                                     const MachineRegisterInfo &MRI) {
82   assert(TargetRegisterInfo::isVirtualRegister(Reg));
83   const auto RC = MRI.getRegClass(Reg);
84   auto STI = static_cast<const SIRegisterInfo*>(MRI.getTargetRegisterInfo());
85   return STI->isSGPRClass(RC) ?
86     (RC->getSize() == 4 ? SGPR32 : SGPR_TUPLE) :
87     (RC->getSize() == 4 ? VGPR32 : VGPR_TUPLE);
88 }
89 
90 void GCNRegPressure::inc(unsigned Reg,
91                          LaneBitmask PrevMask,
92                          LaneBitmask NewMask,
93                          const MachineRegisterInfo &MRI) {
94   if (NewMask == PrevMask)
95     return;
96 
97   int Sign = 1;
98   if (NewMask < PrevMask) {
99     std::swap(NewMask, PrevMask);
100     Sign = -1;
101   }
102 #ifndef NDEBUG
103   const auto MaxMask = MRI.getMaxLaneMaskForVReg(Reg);
104 #endif
105   switch (auto Kind = getRegKind(Reg, MRI)) {
106   case SGPR32:
107   case VGPR32:
108     assert(PrevMask.none() && NewMask == MaxMask);
109     Value[Kind] += Sign;
110     break;
111 
112   case SGPR_TUPLE:
113   case VGPR_TUPLE:
114     assert(NewMask < MaxMask || NewMask == MaxMask);
115     assert(PrevMask < NewMask);
116 
117     Value[Kind == SGPR_TUPLE ? SGPR32 : VGPR32] +=
118       Sign * countPopulation((~PrevMask & NewMask).getAsInteger());
119 
120     if (PrevMask.none()) {
121       assert(NewMask.any());
122       Value[Kind] += Sign * MRI.getPressureSets(Reg).getWeight();
123     }
124     break;
125 
126   default: llvm_unreachable("Unknown register kind");
127   }
128 }
129 
130 bool GCNRegPressure::less(const SISubtarget &ST,
131                           const GCNRegPressure& O,
132                           unsigned MaxOccupancy) const {
133   const auto SGPROcc = std::min(MaxOccupancy,
134                                 ST.getOccupancyWithNumSGPRs(getSGRPNum()));
135   const auto VGPROcc = std::min(MaxOccupancy,
136                                 ST.getOccupancyWithNumVGPRs(getVGRPNum()));
137   const auto OtherSGPROcc = std::min(MaxOccupancy,
138                                 ST.getOccupancyWithNumSGPRs(O.getSGRPNum()));
139   const auto OtherVGPROcc = std::min(MaxOccupancy,
140                                 ST.getOccupancyWithNumVGPRs(O.getVGRPNum()));
141 
142   const auto Occ = std::min(SGPROcc, VGPROcc);
143   const auto OtherOcc = std::min(OtherSGPROcc, OtherVGPROcc);
144   if (Occ != OtherOcc)
145     return Occ > OtherOcc;
146 
147   bool SGPRImportant = SGPROcc < VGPROcc;
148   const bool OtherSGPRImportant = OtherSGPROcc < OtherVGPROcc;
149 
150   // if both pressures disagree on what is more important compare vgprs
151   if (SGPRImportant != OtherSGPRImportant) {
152     SGPRImportant = false;
153   }
154 
155   // compare large regs pressure
156   bool SGPRFirst = SGPRImportant;
157   for (int I = 2; I > 0; --I, SGPRFirst = !SGPRFirst) {
158     if (SGPRFirst) {
159       auto SW = getSGPRTuplesWeight();
160       auto OtherSW = O.getSGPRTuplesWeight();
161       if (SW != OtherSW)
162         return SW < OtherSW;
163     } else {
164       auto VW = getVGPRTuplesWeight();
165       auto OtherVW = O.getVGPRTuplesWeight();
166       if (VW != OtherVW)
167         return VW < OtherVW;
168     }
169   }
170   return SGPRImportant ? (getSGRPNum() < O.getSGRPNum()):
171                          (getVGRPNum() < O.getVGRPNum());
172 }
173 
174 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
175 LLVM_DUMP_METHOD
176 void GCNRegPressure::print(raw_ostream &OS, const SISubtarget *ST) const {
177   OS << "VGPRs: " << getVGRPNum();
178   if (ST) OS << "(O" << ST->getOccupancyWithNumVGPRs(getVGRPNum()) << ')';
179   OS << ", SGPRs: " << getSGRPNum();
180   if (ST) OS << "(O" << ST->getOccupancyWithNumSGPRs(getSGRPNum()) << ')';
181   OS << ", LVGPR WT: " << getVGPRTuplesWeight()
182      << ", LSGPR WT: " << getSGPRTuplesWeight();
183   if (ST) OS << " -> Occ: " << getOccupancy(*ST);
184   OS << '\n';
185 }
186 #endif
187 
188 ///////////////////////////////////////////////////////////////////////////////
189 // GCNRPTracker
190 
191 LaneBitmask llvm::getLiveLaneMask(unsigned Reg,
192                                   SlotIndex SI,
193                                   const LiveIntervals &LIS,
194                                   const MachineRegisterInfo &MRI) {
195   assert(!MRI.reg_nodbg_empty(Reg));
196   LaneBitmask LiveMask;
197   const auto &LI = LIS.getInterval(Reg);
198   if (LI.hasSubRanges()) {
199     for (const auto &S : LI.subranges())
200       if (S.liveAt(SI)) {
201         LiveMask |= S.LaneMask;
202         assert(LiveMask < MRI.getMaxLaneMaskForVReg(Reg) ||
203                LiveMask == MRI.getMaxLaneMaskForVReg(Reg));
204       }
205   } else if (LI.liveAt(SI)) {
206     LiveMask = MRI.getMaxLaneMaskForVReg(Reg);
207   }
208   return LiveMask;
209 }
210 
211 GCNRPTracker::LiveRegSet llvm::getLiveRegs(SlotIndex SI,
212                                            const LiveIntervals &LIS,
213                                            const MachineRegisterInfo &MRI) {
214   GCNRPTracker::LiveRegSet LiveRegs;
215   for (unsigned I = 0, E = MRI.getNumVirtRegs(); I != E; ++I) {
216     auto Reg = TargetRegisterInfo::index2VirtReg(I);
217     if (MRI.reg_nodbg_empty(Reg))
218       continue;
219     auto LiveMask = getLiveLaneMask(Reg, SI, LIS, MRI);
220     if (LiveMask.any())
221       LiveRegs[Reg] = LiveMask;
222   }
223   return LiveRegs;
224 }
225 
226 void GCNUpwardRPTracker::reset(const MachineInstr &MI) {
227   MRI = &MI.getParent()->getParent()->getRegInfo();
228   LiveRegs = getLiveRegsAfter(MI, LIS);
229   MaxPressure = CurPressure = getRegPressure(*MRI, LiveRegs);
230 }
231 
232 LaneBitmask GCNUpwardRPTracker::getDefRegMask(const MachineOperand &MO) const {
233   assert(MO.isDef() && MO.isReg() &&
234     TargetRegisterInfo::isVirtualRegister(MO.getReg()));
235 
236   // We don't rely on read-undef flag because in case of tentative schedule
237   // tracking it isn't set correctly yet. This works correctly however since
238   // use mask has been tracked before using LIS.
239   return MO.getSubReg() == 0 ?
240     MRI->getMaxLaneMaskForVReg(MO.getReg()) :
241     MRI->getTargetRegisterInfo()->getSubRegIndexLaneMask(MO.getSubReg());
242 }
243 
244 LaneBitmask GCNUpwardRPTracker::getUsedRegMask(const MachineOperand &MO) const {
245   assert(MO.isUse() && MO.isReg() &&
246          TargetRegisterInfo::isVirtualRegister(MO.getReg()));
247 
248   if (auto SubReg = MO.getSubReg())
249     return MRI->getTargetRegisterInfo()->getSubRegIndexLaneMask(SubReg);
250 
251   auto MaxMask = MRI->getMaxLaneMaskForVReg(MO.getReg());
252   if (MaxMask.getAsInteger() == 1) // cannot have subregs
253     return MaxMask;
254 
255   // For a tentative schedule LIS isn't updated yet but livemask should remain
256   // the same on any schedule. Subreg defs can be reordered but they all must
257   // dominate uses anyway.
258   auto SI = LIS.getInstructionIndex(*MO.getParent()).getBaseIndex();
259   return getLiveLaneMask(MO.getReg(), SI, LIS, *MRI);
260 }
261 
262 void GCNUpwardRPTracker::recede(const MachineInstr &MI) {
263   assert(MRI && "call reset first");
264 
265   LastTrackedMI = &MI;
266 
267   if (MI.isDebugValue())
268     return;
269 
270   // process all defs first to ensure early clobbers are handled correctly
271   // iterating over operands() to catch implicit defs
272   for (const auto &MO : MI.operands()) {
273     if (!MO.isReg() || !MO.isDef() ||
274       !TargetRegisterInfo::isVirtualRegister(MO.getReg()))
275       continue;
276 
277     auto Reg = MO.getReg();
278     auto &LiveMask = LiveRegs[Reg];
279     auto PrevMask = LiveMask;
280     LiveMask &= ~getDefRegMask(MO);
281     CurPressure.inc(Reg, PrevMask, LiveMask, *MRI);
282   }
283 
284   // then all uses
285   for (const auto &MO : MI.uses()) {
286     if (!MO.isReg() || !MO.readsReg() ||
287       !TargetRegisterInfo::isVirtualRegister(MO.getReg()))
288       continue;
289 
290     auto Reg = MO.getReg();
291     auto &LiveMask = LiveRegs[Reg];
292     auto PrevMask = LiveMask;
293     LiveMask |= getUsedRegMask(MO);
294     CurPressure.inc(Reg, PrevMask, LiveMask, *MRI);
295   }
296 
297   MaxPressure = max(MaxPressure, CurPressure);
298 }
299 
300 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
301 LLVM_DUMP_METHOD
302 static void reportMismatch(const GCNRPTracker::LiveRegSet &LISLR,
303                            const GCNRPTracker::LiveRegSet &TrackedLR,
304                            const TargetRegisterInfo *TRI) {
305   for (auto const &P : TrackedLR) {
306     auto I = LISLR.find(P.first);
307     if (I == LISLR.end()) {
308       dbgs() << "  " << PrintReg(P.first, TRI)
309              << ":L" << PrintLaneMask(P.second)
310              << " isn't found in LIS reported set\n";
311     }
312     else if (I->second != P.second) {
313       dbgs() << "  " << PrintReg(P.first, TRI)
314         << " masks doesn't match: LIS reported "
315         << PrintLaneMask(I->second)
316         << ", tracked "
317         << PrintLaneMask(P.second)
318         << '\n';
319     }
320   }
321   for (auto const &P : LISLR) {
322     auto I = TrackedLR.find(P.first);
323     if (I == TrackedLR.end()) {
324       dbgs() << "  " << PrintReg(P.first, TRI)
325              << ":L" << PrintLaneMask(P.second)
326              << " isn't found in tracked set\n";
327     }
328   }
329 }
330 
331 bool GCNUpwardRPTracker::isValid() const {
332   const auto &SI = LIS.getInstructionIndex(*LastTrackedMI).getBaseIndex();
333   const auto LISLR = llvm::getLiveRegs(SI, LIS, *MRI);
334   const auto TrackedLR = stripEmpty(LiveRegs);
335 
336   if (!isEqual(LISLR, TrackedLR)) {
337     dbgs() << "\nGCNUpwardRPTracker error: Tracked and"
338               " LIS reported livesets mismatch:\n";
339     printLivesAt(SI, LIS, *MRI);
340     reportMismatch(LISLR, TrackedLR, MRI->getTargetRegisterInfo());
341     return false;
342   }
343 
344   auto LISPressure = getRegPressure(*MRI, LISLR);
345   if (LISPressure != CurPressure) {
346     dbgs() << "GCNUpwardRPTracker error: Pressure sets different\nTracked: ";
347     CurPressure.print(dbgs());
348     dbgs() << "LIS rpt: ";
349     LISPressure.print(dbgs());
350     return false;
351   }
352   return true;
353 }
354 
355 #endif
356