contrib/llvm/lib/Target/AMDGPU/GCNRegPressure.cpp

   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 SmallVector<RegisterMaskPair, 8> collectVirtualRegUses(const MachineInstr &MI,
 215                                               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