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 #include "llvm/CodeGen/RegisterPressure.h"
16 
17 using namespace llvm;
18 
19 #define DEBUG_TYPE "misched"
20 
21 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
22 LLVM_DUMP_METHOD
23 void llvm::printLivesAt(SlotIndex SI,
24                         const LiveIntervals &LIS,
25                         const MachineRegisterInfo &MRI) {
26   dbgs() << "Live regs at " << SI << ": "
27          << *LIS.getInstructionFromIndex(SI);
28   unsigned Num = 0;
29   for (unsigned I = 0, E = MRI.getNumVirtRegs(); I != E; ++I) {
30     const unsigned Reg = TargetRegisterInfo::index2VirtReg(I);
31     if (!LIS.hasInterval(Reg))
32       continue;
33     const auto &LI = LIS.getInterval(Reg);
34     if (LI.hasSubRanges()) {
35       bool firstTime = true;
36       for (const auto &S : LI.subranges()) {
37         if (!S.liveAt(SI)) continue;
38         if (firstTime) {
39           dbgs() << "  " << PrintReg(Reg, MRI.getTargetRegisterInfo())
40                  << '\n';
41           firstTime = false;
42         }
43         dbgs() << "  " << S << '\n';
44         ++Num;
45       }
46     } else if (LI.liveAt(SI)) {
47       dbgs() << "  " << LI << '\n';
48       ++Num;
49     }
50   }
51   if (!Num) dbgs() << "  <none>\n";
52 }
53 
54 static bool isEqual(const GCNRPTracker::LiveRegSet &S1,
55                     const GCNRPTracker::LiveRegSet &S2) {
56   if (S1.size() != S2.size())
57     return false;
58 
59   for (const auto &P : S1) {
60     auto I = S2.find(P.first);
61     if (I == S2.end() || I->second != P.second)
62       return false;
63   }
64   return true;
65 }
66 
67 #endif
68 
69 ///////////////////////////////////////////////////////////////////////////////
70 // GCNRegPressure
71 
72 unsigned GCNRegPressure::getRegKind(unsigned Reg,
73                                     const MachineRegisterInfo &MRI) {
74   assert(TargetRegisterInfo::isVirtualRegister(Reg));
75   const auto RC = MRI.getRegClass(Reg);
76   auto STI = static_cast<const SIRegisterInfo*>(MRI.getTargetRegisterInfo());
77   return STI->isSGPRClass(RC) ?
78     (STI->getRegSizeInBits(*RC) == 32 ? SGPR32 : SGPR_TUPLE) :
79     (STI->getRegSizeInBits(*RC) == 32 ? VGPR32 : VGPR_TUPLE);
80 }
81 
82 void GCNRegPressure::inc(unsigned Reg,
83                          LaneBitmask PrevMask,
84                          LaneBitmask NewMask,
85                          const MachineRegisterInfo &MRI) {
86   if (NewMask == PrevMask)
87     return;
88 
89   int Sign = 1;
90   if (NewMask < PrevMask) {
91     std::swap(NewMask, PrevMask);
92     Sign = -1;
93   }
94 #ifndef NDEBUG
95   const auto MaxMask = MRI.getMaxLaneMaskForVReg(Reg);
96 #endif
97   switch (auto Kind = getRegKind(Reg, MRI)) {
98   case SGPR32:
99   case VGPR32:
100     assert(PrevMask.none() && NewMask == MaxMask);
101     Value[Kind] += Sign;
102     break;
103 
104   case SGPR_TUPLE:
105   case VGPR_TUPLE:
106     assert(NewMask < MaxMask || NewMask == MaxMask);
107     assert(PrevMask < NewMask);
108 
109     Value[Kind == SGPR_TUPLE ? SGPR32 : VGPR32] +=
110       Sign * countPopulation((~PrevMask & NewMask).getAsInteger());
111 
112     if (PrevMask.none()) {
113       assert(NewMask.any());
114       Value[Kind] += Sign * MRI.getPressureSets(Reg).getWeight();
115     }
116     break;
117 
118   default: llvm_unreachable("Unknown register kind");
119   }
120 }
121 
122 bool GCNRegPressure::less(const SISubtarget &ST,
123                           const GCNRegPressure& O,
124                           unsigned MaxOccupancy) const {
125   const auto SGPROcc = std::min(MaxOccupancy,
126                                 ST.getOccupancyWithNumSGPRs(getSGPRNum()));
127   const auto VGPROcc = std::min(MaxOccupancy,
128                                 ST.getOccupancyWithNumVGPRs(getVGPRNum()));
129   const auto OtherSGPROcc = std::min(MaxOccupancy,
130                                 ST.getOccupancyWithNumSGPRs(O.getSGPRNum()));
131   const auto OtherVGPROcc = std::min(MaxOccupancy,
132                                 ST.getOccupancyWithNumVGPRs(O.getVGPRNum()));
133 
134   const auto Occ = std::min(SGPROcc, VGPROcc);
135   const auto OtherOcc = std::min(OtherSGPROcc, OtherVGPROcc);
136   if (Occ != OtherOcc)
137     return Occ > OtherOcc;
138 
139   bool SGPRImportant = SGPROcc < VGPROcc;
140   const bool OtherSGPRImportant = OtherSGPROcc < OtherVGPROcc;
141 
142   // if both pressures disagree on what is more important compare vgprs
143   if (SGPRImportant != OtherSGPRImportant) {
144     SGPRImportant = false;
145   }
146 
147   // compare large regs pressure
148   bool SGPRFirst = SGPRImportant;
149   for (int I = 2; I > 0; --I, SGPRFirst = !SGPRFirst) {
150     if (SGPRFirst) {
151       auto SW = getSGPRTuplesWeight();
152       auto OtherSW = O.getSGPRTuplesWeight();
153       if (SW != OtherSW)
154         return SW < OtherSW;
155     } else {
156       auto VW = getVGPRTuplesWeight();
157       auto OtherVW = O.getVGPRTuplesWeight();
158       if (VW != OtherVW)
159         return VW < OtherVW;
160     }
161   }
162   return SGPRImportant ? (getSGPRNum() < O.getSGPRNum()):
163                          (getVGPRNum() < O.getVGPRNum());
164 }
165 
166 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
167 LLVM_DUMP_METHOD
168 void GCNRegPressure::print(raw_ostream &OS, const SISubtarget *ST) const {
169   OS << "VGPRs: " << getVGPRNum();
170   if (ST) OS << "(O" << ST->getOccupancyWithNumVGPRs(getVGPRNum()) << ')';
171   OS << ", SGPRs: " << getSGPRNum();
172   if (ST) OS << "(O" << ST->getOccupancyWithNumSGPRs(getSGPRNum()) << ')';
173   OS << ", LVGPR WT: " << getVGPRTuplesWeight()
174      << ", LSGPR WT: " << getSGPRTuplesWeight();
175   if (ST) OS << " -> Occ: " << getOccupancy(*ST);
176   OS << '\n';
177 }
178 #endif
179 
180 
181 static LaneBitmask getDefRegMask(const MachineOperand &MO,
182                                  const MachineRegisterInfo &MRI) {
183   assert(MO.isDef() && MO.isReg() &&
184     TargetRegisterInfo::isVirtualRegister(MO.getReg()));
185 
186   // We don't rely on read-undef flag because in case of tentative schedule
187   // tracking it isn't set correctly yet. This works correctly however since
188   // use mask has been tracked before using LIS.
189   return MO.getSubReg() == 0 ?
190     MRI.getMaxLaneMaskForVReg(MO.getReg()) :
191     MRI.getTargetRegisterInfo()->getSubRegIndexLaneMask(MO.getSubReg());
192 }
193 
194 static LaneBitmask getUsedRegMask(const MachineOperand &MO,
195                                   const MachineRegisterInfo &MRI,
196                                   const LiveIntervals &LIS) {
197   assert(MO.isUse() && MO.isReg() &&
198          TargetRegisterInfo::isVirtualRegister(MO.getReg()));
199 
200   if (auto SubReg = MO.getSubReg())
201     return MRI.getTargetRegisterInfo()->getSubRegIndexLaneMask(SubReg);
202 
203   auto MaxMask = MRI.getMaxLaneMaskForVReg(MO.getReg());
204   if (MaxMask.getAsInteger() == 1) // cannot have subregs
205     return MaxMask;
206 
207   // For a tentative schedule LIS isn't updated yet but livemask should remain
208   // the same on any schedule. Subreg defs can be reordered but they all must
209   // dominate uses anyway.
210   auto SI = LIS.getInstructionIndex(*MO.getParent()).getBaseIndex();
211   return getLiveLaneMask(MO.getReg(), SI, LIS, MRI);
212 }
213 
214 static SmallVector<RegisterMaskPair, 8>
215 collectVirtualRegUses(const MachineInstr &MI, const LiveIntervals &LIS,
216                       const MachineRegisterInfo &MRI) {
217   SmallVector<RegisterMaskPair, 8> Res;
218   for (const auto &MO : MI.operands()) {
219     if (!MO.isReg() || !TargetRegisterInfo::isVirtualRegister(MO.getReg()))
220       continue;
221     if (!MO.isUse() || !MO.readsReg())
222       continue;
223 
224     auto const UsedMask = getUsedRegMask(MO, MRI, LIS);
225 
226     auto Reg = MO.getReg();
227     auto I = std::find_if(Res.begin(), Res.end(), [Reg](const RegisterMaskPair &RM) {
228       return RM.RegUnit == Reg;
229     });
230     if (I != Res.end())
231       I->LaneMask |= UsedMask;
232     else
233       Res.push_back(RegisterMaskPair(Reg, UsedMask));
234   }
235   return Res;
236 }
237 
238 ///////////////////////////////////////////////////////////////////////////////
239 // GCNRPTracker
240 
241 LaneBitmask llvm::getLiveLaneMask(unsigned Reg,
242                                   SlotIndex SI,
243                                   const LiveIntervals &LIS,
244                                   const MachineRegisterInfo &MRI) {
245   LaneBitmask LiveMask;
246   const auto &LI = LIS.getInterval(Reg);
247   if (LI.hasSubRanges()) {
248     for (const auto &S : LI.subranges())
249       if (S.liveAt(SI)) {
250         LiveMask |= S.LaneMask;
251         assert(LiveMask < MRI.getMaxLaneMaskForVReg(Reg) ||
252                LiveMask == MRI.getMaxLaneMaskForVReg(Reg));
253       }
254   } else if (LI.liveAt(SI)) {
255     LiveMask = MRI.getMaxLaneMaskForVReg(Reg);
256   }
257   return LiveMask;
258 }
259 
260 GCNRPTracker::LiveRegSet llvm::getLiveRegs(SlotIndex SI,
261                                            const LiveIntervals &LIS,
262                                            const MachineRegisterInfo &MRI) {
263   GCNRPTracker::LiveRegSet LiveRegs;
264   for (unsigned I = 0, E = MRI.getNumVirtRegs(); I != E; ++I) {
265     auto Reg = TargetRegisterInfo::index2VirtReg(I);
266     if (!LIS.hasInterval(Reg))
267       continue;
268     auto LiveMask = getLiveLaneMask(Reg, SI, LIS, MRI);
269     if (LiveMask.any())
270       LiveRegs[Reg] = LiveMask;
271   }
272   return LiveRegs;
273 }
274 
275 void GCNUpwardRPTracker::reset(const MachineInstr &MI,
276                                const LiveRegSet *LiveRegsCopy) {
277   MRI = &MI.getParent()->getParent()->getRegInfo();
278   if (LiveRegsCopy) {
279     if (&LiveRegs != LiveRegsCopy)
280       LiveRegs = *LiveRegsCopy;
281   } else {
282     LiveRegs = getLiveRegsAfter(MI, LIS);
283   }
284   MaxPressure = CurPressure = getRegPressure(*MRI, LiveRegs);
285 }
286 
287 void GCNUpwardRPTracker::recede(const MachineInstr &MI) {
288   assert(MRI && "call reset first");
289 
290   LastTrackedMI = &MI;
291 
292   if (MI.isDebugValue())
293     return;
294 
295   auto const RegUses = collectVirtualRegUses(MI, LIS, *MRI);
296 
297   // calc pressure at the MI (defs + uses)
298   auto AtMIPressure = CurPressure;
299   for (const auto &U : RegUses) {
300     auto LiveMask = LiveRegs[U.RegUnit];
301     AtMIPressure.inc(U.RegUnit, LiveMask, LiveMask | U.LaneMask, *MRI);
302   }
303   // update max pressure
304   MaxPressure = max(AtMIPressure, MaxPressure);
305 
306   for (const auto &MO : MI.defs()) {
307     if (!MO.isReg() || !TargetRegisterInfo::isVirtualRegister(MO.getReg()) ||
308          MO.isDead())
309       continue;
310 
311     auto Reg = MO.getReg();
312     auto I = LiveRegs.find(Reg);
313     if (I == LiveRegs.end())
314       continue;
315     auto &LiveMask = I->second;
316     auto PrevMask = LiveMask;
317     LiveMask &= ~getDefRegMask(MO, *MRI);
318     CurPressure.inc(Reg, PrevMask, LiveMask, *MRI);
319     if (LiveMask.none())
320       LiveRegs.erase(I);
321   }
322   for (const auto &U : RegUses) {
323     auto &LiveMask = LiveRegs[U.RegUnit];
324     auto PrevMask = LiveMask;
325     LiveMask |= U.LaneMask;
326     CurPressure.inc(U.RegUnit, PrevMask, LiveMask, *MRI);
327   }
328   assert(CurPressure == getRegPressure(*MRI, LiveRegs));
329 }
330 
331 bool GCNDownwardRPTracker::reset(const MachineInstr &MI,
332                                  const LiveRegSet *LiveRegsCopy) {
333   MRI = &MI.getParent()->getParent()->getRegInfo();
334   LastTrackedMI = nullptr;
335   MBBEnd = MI.getParent()->end();
336   NextMI = &MI;
337   NextMI = skipDebugInstructionsForward(NextMI, MBBEnd);
338   if (NextMI == MBBEnd)
339     return false;
340   if (LiveRegsCopy) {
341     if (&LiveRegs != LiveRegsCopy)
342       LiveRegs = *LiveRegsCopy;
343   } else {
344     LiveRegs = getLiveRegsBefore(*NextMI, LIS);
345   }
346   MaxPressure = CurPressure = getRegPressure(*MRI, LiveRegs);
347   return true;
348 }
349 
350 bool GCNDownwardRPTracker::advanceBeforeNext() {
351   assert(MRI && "call reset first");
352 
353   NextMI = skipDebugInstructionsForward(NextMI, MBBEnd);
354   if (NextMI == MBBEnd)
355     return false;
356 
357   SlotIndex SI = LIS.getInstructionIndex(*NextMI).getBaseIndex();
358   assert(SI.isValid());
359 
360   // Remove dead registers or mask bits.
361   for (auto &It : LiveRegs) {
362     const LiveInterval &LI = LIS.getInterval(It.first);
363     if (LI.hasSubRanges()) {
364       for (const auto &S : LI.subranges()) {
365         if (!S.liveAt(SI)) {
366           auto PrevMask = It.second;
367           It.second &= ~S.LaneMask;
368           CurPressure.inc(It.first, PrevMask, It.second, *MRI);
369         }
370       }
371     } else if (!LI.liveAt(SI)) {
372       auto PrevMask = It.second;
373       It.second = LaneBitmask::getNone();
374       CurPressure.inc(It.first, PrevMask, It.second, *MRI);
375     }
376     if (It.second.none())
377       LiveRegs.erase(It.first);
378   }
379 
380   MaxPressure = max(MaxPressure, CurPressure);
381 
382   return true;
383 }
384 
385 void GCNDownwardRPTracker::advanceToNext() {
386   LastTrackedMI = &*NextMI++;
387 
388   // Add new registers or mask bits.
389   for (const auto &MO : LastTrackedMI->defs()) {
390     if (!MO.isReg())
391       continue;
392     unsigned Reg = MO.getReg();
393     if (!TargetRegisterInfo::isVirtualRegister(Reg))
394       continue;
395     auto &LiveMask = LiveRegs[Reg];
396     auto PrevMask = LiveMask;
397     LiveMask |= getDefRegMask(MO, *MRI);
398     CurPressure.inc(Reg, PrevMask, LiveMask, *MRI);
399   }
400 
401   MaxPressure = max(MaxPressure, CurPressure);
402 }
403 
404 bool GCNDownwardRPTracker::advance() {
405   // If we have just called reset live set is actual.
406   if ((NextMI == MBBEnd) || (LastTrackedMI && !advanceBeforeNext()))
407     return false;
408   advanceToNext();
409   return true;
410 }
411 
412 bool GCNDownwardRPTracker::advance(MachineBasicBlock::const_iterator End) {
413   while (NextMI != End)
414     if (!advance()) return false;
415   return true;
416 }
417 
418 bool GCNDownwardRPTracker::advance(MachineBasicBlock::const_iterator Begin,
419                                    MachineBasicBlock::const_iterator End,
420                                    const LiveRegSet *LiveRegsCopy) {
421   reset(*Begin, LiveRegsCopy);
422   return advance(End);
423 }
424 
425 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
426 LLVM_DUMP_METHOD
427 static void reportMismatch(const GCNRPTracker::LiveRegSet &LISLR,
428                            const GCNRPTracker::LiveRegSet &TrackedLR,
429                            const TargetRegisterInfo *TRI) {
430   for (auto const &P : TrackedLR) {
431     auto I = LISLR.find(P.first);
432     if (I == LISLR.end()) {
433       dbgs() << "  " << PrintReg(P.first, TRI)
434              << ":L" << PrintLaneMask(P.second)
435              << " isn't found in LIS reported set\n";
436     }
437     else if (I->second != P.second) {
438       dbgs() << "  " << PrintReg(P.first, TRI)
439         << " masks doesn't match: LIS reported "
440         << PrintLaneMask(I->second)
441         << ", tracked "
442         << PrintLaneMask(P.second)
443         << '\n';
444     }
445   }
446   for (auto const &P : LISLR) {
447     auto I = TrackedLR.find(P.first);
448     if (I == TrackedLR.end()) {
449       dbgs() << "  " << PrintReg(P.first, TRI)
450              << ":L" << PrintLaneMask(P.second)
451              << " isn't found in tracked set\n";
452     }
453   }
454 }
455 
456 bool GCNUpwardRPTracker::isValid() const {
457   const auto &SI = LIS.getInstructionIndex(*LastTrackedMI).getBaseIndex();
458   const auto LISLR = llvm::getLiveRegs(SI, LIS, *MRI);
459   const auto &TrackedLR = LiveRegs;
460 
461   if (!isEqual(LISLR, TrackedLR)) {
462     dbgs() << "\nGCNUpwardRPTracker error: Tracked and"
463               " LIS reported livesets mismatch:\n";
464     printLivesAt(SI, LIS, *MRI);
465     reportMismatch(LISLR, TrackedLR, MRI->getTargetRegisterInfo());
466     return false;
467   }
468 
469   auto LISPressure = getRegPressure(*MRI, LISLR);
470   if (LISPressure != CurPressure) {
471     dbgs() << "GCNUpwardRPTracker error: Pressure sets different\nTracked: ";
472     CurPressure.print(dbgs());
473     dbgs() << "LIS rpt: ";
474     LISPressure.print(dbgs());
475     return false;
476   }
477   return true;
478 }
479 
480 void GCNRPTracker::printLiveRegs(raw_ostream &OS, const LiveRegSet& LiveRegs,
481                                  const MachineRegisterInfo &MRI) {
482   const TargetRegisterInfo *TRI = MRI.getTargetRegisterInfo();
483   for (unsigned I = 0, E = MRI.getNumVirtRegs(); I != E; ++I) {
484     unsigned Reg = TargetRegisterInfo::index2VirtReg(I);
485     auto It = LiveRegs.find(Reg);
486     if (It != LiveRegs.end() && It->second.any())
487       OS << ' ' << PrintVRegOrUnit(Reg, TRI) << ':'
488          << PrintLaneMask(It->second);
489   }
490   OS << '\n';
491 }
492 #endif
493