contrib/llvm-project/llvm/lib/Target/AMDGPU/GCNRegBankReassign.cpp

   1 //===-- GCNRegBankReassign.cpp - Reassign registers after regalloc --------===//
   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 /// \brief Try to reassign registers on GFX10+ to reduce register bank
  11 /// conflicts.
  12 ///
  13 /// On GFX10 registers are organized in banks. VGPRs have 4 banks assigned in
  14 /// a round-robin fashion: v0, v4, v8... belong to bank 0. v1, v5, v9... to
  15 /// bank 1, etc. SGPRs have 8 banks and allocated in pairs, so that s0:s1,
  16 /// s16:s17, s32:s33 are at bank 0. s2:s3, s18:s19, s34:s35 are at bank 1 etc.
  17 ///
  18 /// The shader can read one dword from each of these banks once per cycle.
  19 /// If an instruction has to read more register operands from the same bank
  20 /// an additional cycle is needed. HW attempts to pre-load registers through
  21 /// input operand gathering, but a stall cycle may occur if that fails. For
  22 /// example V_FMA_F32 V111 = V0 + V4 * V8 will need 3 cycles to read operands,
  23 /// potentially incuring 2 stall cycles.
  24 ///
  25 /// The pass tries to reassign registers to reduce bank conflicts.
  26 ///
  27 /// In this pass bank numbers 0-3 are VGPR banks and 4-11 are SGPR banks, so
  28 /// that 4 has to be subtracted from an SGPR bank number to get the real value.
  29 /// This also corresponds to bit numbers in bank masks used in the pass.
  30 ///
  31 //===----------------------------------------------------------------------===//
  32
  33 #include "AMDGPU.h"
  34 #include "AMDGPUSubtarget.h"
  35 #include "MCTargetDesc/AMDGPUMCTargetDesc.h"
  36 #include "SIInstrInfo.h"
  37 #include "SIMachineFunctionInfo.h"
  38 #include "llvm/ADT/SmallSet.h"
  39 #include "llvm/ADT/Statistic.h"
  40 #include "llvm/CodeGen/LiveInterval.h"
  41 #include "llvm/CodeGen/LiveIntervals.h"
  42 #include "llvm/CodeGen/LiveRegMatrix.h"
  43 #include "llvm/CodeGen/MachineFunctionPass.h"
  44 #include "llvm/CodeGen/MachineLoopInfo.h"
  45 #include "llvm/CodeGen/VirtRegMap.h"
  46 #include "llvm/InitializePasses.h"
  47 #include "llvm/Support/MathExtras.h"
  48
  49 using namespace llvm;
  50
  51 static cl::opt<unsigned> VerifyStallCycles("amdgpu-verify-regbanks-reassign",
  52   cl::desc("Verify stall cycles in the regbanks reassign pass"),
  53   cl::value_desc("0|1|2"),
  54   cl::init(0), cl::Hidden);
  55
  56 #define DEBUG_TYPE "amdgpu-regbanks-reassign"
  57
  58 #define NUM_VGPR_BANKS 4
  59 #define NUM_SGPR_BANKS 8
  60 #define NUM_BANKS (NUM_VGPR_BANKS + NUM_SGPR_BANKS)
  61 #define SGPR_BANK_OFFSET NUM_VGPR_BANKS
  62 #define VGPR_BANK_MASK 0xf
  63 #define SGPR_BANK_MASK 0xff0
  64 #define SGPR_BANK_SHIFTED_MASK (SGPR_BANK_MASK >> SGPR_BANK_OFFSET)
  65
  66 STATISTIC(NumStallsDetected,
  67           "Number of operand read stalls detected");
  68 STATISTIC(NumStallsRecovered,
  69           "Number of operand read stalls recovered");
  70
  71 namespace {
  72
  73 class GCNRegBankReassign : public MachineFunctionPass {
  74
  75   class OperandMask {
  76   public:
  77     OperandMask(unsigned r, unsigned s, unsigned m)
  78       : Reg(r), SubReg(s), Mask(m) {}
  79     unsigned Reg;
  80     unsigned SubReg;
  81     unsigned Mask;
  82   };
  83
  84   class Candidate {
  85   public:
  86     Candidate(MachineInstr *mi, unsigned reg, unsigned freebanks,
  87               unsigned weight)
  88       : MI(mi), Reg(reg), FreeBanks(freebanks), Weight(weight) {}
  89
  90     bool operator< (const Candidate& RHS) const { return Weight < RHS.Weight; }
  91
  92 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
  93     void dump(const GCNRegBankReassign *P) const {
  94       MI->dump();
  95       dbgs() << P->printReg(Reg) << " to banks ";
  96       dumpFreeBanks(FreeBanks);
  97       dbgs() << " weight " << Weight << '\n';
  98     }
  99 #endif
 100
 101     MachineInstr *MI;
 102     unsigned Reg;
 103     unsigned FreeBanks;
 104     unsigned Weight;
 105   };
 106
 107   class CandidateList : public std::list<Candidate> {
 108   public:
 109     // Speedup subsequent sort.
 110     void push(const Candidate&& C) {
 111       if (C.Weight) push_back(C);
 112       else push_front(C);
 113     }
 114   };
 115
 116 public:
 117   static char ID;
 118
 119 public:
 120   GCNRegBankReassign() : MachineFunctionPass(ID) {
 121     initializeGCNRegBankReassignPass(*PassRegistry::getPassRegistry());
 122   }
 123
 124   bool runOnMachineFunction(MachineFunction &MF) override;
 125
 126   StringRef getPassName() const override { return "GCN RegBank Reassign"; }
 127
 128   void getAnalysisUsage(AnalysisUsage &AU) const override {
 129     AU.addRequired<MachineLoopInfo>();
 130     AU.addRequired<LiveIntervals>();
 131     AU.addRequired<VirtRegMap>();
 132     AU.addRequired<LiveRegMatrix>();
 133     AU.setPreservesAll();
 134     MachineFunctionPass::getAnalysisUsage(AU);
 135   }
 136
 137 private:
 138   const GCNSubtarget *ST;
 139
 140   const MachineRegisterInfo *MRI;
 141
 142   const SIRegisterInfo *TRI;
 143
 144   MachineLoopInfo *MLI;
 145
 146   VirtRegMap *VRM;
 147
 148   LiveRegMatrix *LRM;
 149
 150   LiveIntervals *LIS;
 151
 152   unsigned MaxNumVGPRs;
 153
 154   unsigned MaxNumSGPRs;
 155
 156   BitVector RegsUsed;
 157
 158   SmallVector<OperandMask, 8> OperandMasks;
 159
 160   CandidateList Candidates;
 161
 162   const MCPhysReg *CSRegs;
 163
 164   // Returns bank for a phys reg.
 165   unsigned getPhysRegBank(unsigned Reg) const;
 166
 167   // Return a bit set for each register bank used. 4 banks for VGPRs and
 168   // 8 banks for SGPRs.
 169   // Registers already processed and recorded in RegsUsed are excluded.
 170   // If Bank is not -1 assume Reg:SubReg to belong to that Bank.
 171   unsigned getRegBankMask(unsigned Reg, unsigned SubReg, int Bank);
 172
 173   // Return number of stalls in the instructions.
 174   // UsedBanks has bits set for the banks used by all operands.
 175   // If Reg and Bank provided substitute the Reg with the Bank.
 176   unsigned analyzeInst(const MachineInstr& MI, unsigned& UsedBanks,
 177                        unsigned Reg = AMDGPU::NoRegister, int Bank = -1);
 178
 179   // Return true if register is regular VGPR or SGPR or their tuples.
 180   // Returns false for special registers like m0, vcc etc.
 181   bool isReassignable(unsigned Reg) const;
 182
 183   // Check if registers' defs are old and may be pre-loaded.
 184   // Returns 0 if both registers are old enough, 1 or 2 if one or both
 185   // registers will not likely be pre-loaded.
 186   unsigned getOperandGatherWeight(const MachineInstr& MI,
 187                                   unsigned Reg1,
 188                                   unsigned Reg2,
 189                                   unsigned StallCycles) const;
 190
 191
 192   // Find all bank bits in UsedBanks where Mask can be relocated to.
 193   unsigned getFreeBanks(unsigned Mask, unsigned UsedBanks) const;
 194
 195   // Find all bank bits in UsedBanks where Mask can be relocated to.
 196   // Bank is relative to the register and not its subregister component.
 197   // Returns 0 is a register is not reassignable.
 198   unsigned getFreeBanks(unsigned Reg, unsigned SubReg, unsigned Mask,
 199                         unsigned UsedBanks) const;
 200
 201   // Add cadidate instruction to the work list.
 202   void collectCandidates(MachineInstr& MI, unsigned UsedBanks,
 203                          unsigned StallCycles);
 204
 205   // Collect cadidate instructions across function. Returns a number stall
 206   // cycles detected. Only counts stalls if Collect is false.
 207   unsigned collectCandidates(MachineFunction &MF, bool Collect = true);
 208
 209   // Remove all candidates that read specified register.
 210   void removeCandidates(unsigned Reg);
 211
 212   // Compute stalls within the uses of SrcReg replaced by a register from
 213   // Bank. If Bank is -1 does not perform substitution. If Collect is set
 214   // candidates are collected and added to work list.
 215   unsigned computeStallCycles(unsigned SrcReg,
 216                               unsigned Reg = AMDGPU::NoRegister,
 217                               int Bank = -1, bool Collect = false);
 218
 219   // Search for a register in Bank unused within LI.
 220   // Returns phys reg or NoRegister.
 221   unsigned scavengeReg(LiveInterval& LI, unsigned Bank) const;
 222
 223   // Try to reassign candidate. Returns number or stall cycles saved.
 224   unsigned tryReassign(Candidate &C);
 225
 226   bool verifyCycles(MachineFunction &MF,
 227                     unsigned OriginalCycles, unsigned CyclesSaved);
 228
 229
 230 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
 231 public:
 232   Printable printReg(unsigned Reg, unsigned SubReg = 0) const {
 233     return Printable([Reg, SubReg, this](raw_ostream &OS) {
 234       if (Register::isPhysicalRegister(Reg)) {
 235         OS << llvm::printReg(Reg, TRI);
 236         return;
 237       }
 238       if (!VRM->isAssignedReg(Reg))
 239         OS << "<unassigned> " << llvm::printReg(Reg, TRI);
 240       else
 241         OS << llvm::printReg(Reg, TRI) << '('
 242            << llvm::printReg(VRM->getPhys(Reg), TRI) << ')';
 243       if (SubReg)
 244         OS << ':' << TRI->getSubRegIndexName(SubReg);
 245     });
 246   }
 247
 248   static Printable printBank(unsigned Bank) {
 249     return Printable([Bank](raw_ostream &OS) {
 250       OS << ((Bank >= SGPR_BANK_OFFSET) ? Bank - SGPR_BANK_OFFSET : Bank);
 251     });
 252   }
 253
 254   static void dumpFreeBanks(unsigned FreeBanks) {
 255     for (unsigned L = 0; L < NUM_BANKS; ++L)
 256       if (FreeBanks & (1 << L))
 257         dbgs() << printBank(L) << ' ';
 258   }
 259 #endif
 260 };
 261
 262 } // End anonymous namespace.
 263
 264 INITIALIZE_PASS_BEGIN(GCNRegBankReassign, DEBUG_TYPE, "GCN RegBank Reassign",
 265                       false, false)
 266 INITIALIZE_PASS_DEPENDENCY(LiveIntervals)
 267 INITIALIZE_PASS_DEPENDENCY(MachineLoopInfo)
 268 INITIALIZE_PASS_DEPENDENCY(VirtRegMap)
 269 INITIALIZE_PASS_DEPENDENCY(LiveRegMatrix)
 270 INITIALIZE_PASS_END(GCNRegBankReassign, DEBUG_TYPE, "GCN RegBank Reassign",
 271                     false, false)
 272
 273
 274 char GCNRegBankReassign::ID = 0;
 275
 276 char &llvm::GCNRegBankReassignID = GCNRegBankReassign::ID;
 277
 278 unsigned GCNRegBankReassign::getPhysRegBank(unsigned Reg) const {
 279   assert(Register::isPhysicalRegister(Reg));
 280
 281   const TargetRegisterClass *RC = TRI->getMinimalPhysRegClass(Reg);
 282   unsigned Size = TRI->getRegSizeInBits(*RC);
 283   if (Size > 32)
 284     Reg = TRI->getSubReg(Reg, AMDGPU::sub0);
 285
 286   if (TRI->hasVGPRs(RC)) {
 287     Reg -= AMDGPU::VGPR0;
 288     return Reg % NUM_VGPR_BANKS;
 289   }
 290
 291   Reg = TRI->getEncodingValue(Reg) / 2;
 292   return Reg % NUM_SGPR_BANKS + SGPR_BANK_OFFSET;
 293 }
 294
 295 unsigned GCNRegBankReassign::getRegBankMask(unsigned Reg, unsigned SubReg,
 296                                             int Bank) {
 297   if (Register::isVirtualRegister(Reg)) {
 298     if (!VRM->isAssignedReg(Reg))
 299       return 0;
 300
 301     Reg = VRM->getPhys(Reg);
 302     if (!Reg)
 303       return 0;
 304     if (SubReg)
 305       Reg = TRI->getSubReg(Reg, SubReg);
 306   }
 307
 308   const TargetRegisterClass *RC = TRI->getMinimalPhysRegClass(Reg);
 309   unsigned Size = TRI->getRegSizeInBits(*RC) / 32;
 310   if (Size > 1)
 311     Reg = TRI->getSubReg(Reg, AMDGPU::sub0);
 312
 313   if (TRI->hasVGPRs(RC)) {
 314     // VGPRs have 4 banks assigned in a round-robin fashion.
 315     Reg -= AMDGPU::VGPR0;
 316     unsigned Mask = (1 << Size) - 1;
 317     unsigned Used = 0;
 318     // Bitmask lacks an extract method
 319     for (unsigned I = 0; I < Size; ++I)
 320       if (RegsUsed.test(Reg + I))
 321         Used |= 1 << I;
 322     RegsUsed.set(Reg, Reg + Size);
 323     Mask &= ~Used;
 324     Mask <<= (Bank == -1) ? Reg % NUM_VGPR_BANKS : unsigned(Bank);
 325     return (Mask | (Mask >> NUM_VGPR_BANKS)) & VGPR_BANK_MASK;
 326   }
 327
 328   // SGPRs have 8 banks holding 2 consequitive registers each.
 329   Reg = TRI->getEncodingValue(Reg) / 2;
 330   unsigned StartBit = AMDGPU::VGPR_32RegClass.getNumRegs();
 331   if (Reg + StartBit >= RegsUsed.size())
 332     return 0;
 333
 334   if (Size > 1)
 335     Size /= 2;
 336   unsigned Mask = (1 << Size) - 1;
 337   unsigned Used = 0;
 338   for (unsigned I = 0; I < Size; ++I)
 339     if (RegsUsed.test(StartBit + Reg + I))
 340       Used |= 1 << I;
 341   RegsUsed.set(StartBit + Reg, StartBit + Reg + Size);
 342   Mask &= ~Used;
 343   Mask <<= (Bank == -1) ? Reg % NUM_SGPR_BANKS
 344                         : unsigned(Bank - SGPR_BANK_OFFSET);
 345   Mask = (Mask | (Mask >> NUM_SGPR_BANKS)) & SGPR_BANK_SHIFTED_MASK;
 346   // Reserve 4 bank ids for VGPRs.
 347   return Mask << SGPR_BANK_OFFSET;
 348 }
 349
 350 unsigned GCNRegBankReassign::analyzeInst(const MachineInstr& MI,
 351                                          unsigned& UsedBanks,
 352                                          unsigned Reg,
 353                                          int Bank) {
 354   unsigned StallCycles = 0;
 355   UsedBanks = 0;
 356
 357   if (MI.isDebugValue())
 358     return 0;
 359
 360   RegsUsed.reset();
 361   OperandMasks.clear();
 362   for (const auto& Op : MI.explicit_uses()) {
 363     // Undef can be assigned to any register, so two vregs can be assigned
 364     // the same phys reg within the same instruction.
 365     if (!Op.isReg() || Op.isUndef())
 366       continue;
 367
 368     Register R = Op.getReg();
 369     if (TRI->hasAGPRs(TRI->getRegClassForReg(*MRI, R)))
 370       continue;
 371
 372     unsigned ShiftedBank = Bank;
 373
 374     if (Bank != -1 && R == Reg && Op.getSubReg()) {
 375       unsigned LM = TRI->getSubRegIndexLaneMask(Op.getSubReg()).getAsInteger();
 376       if (!(LM & 1) && (Bank < NUM_VGPR_BANKS)) {
 377         // If a register spans all banks we cannot shift it to avoid conflict.
 378         if (countPopulation(LM) >= NUM_VGPR_BANKS)
 379           continue;
 380         ShiftedBank = (Bank + countTrailingZeros(LM)) % NUM_VGPR_BANKS;
 381       } else if (!(LM & 3) && (Bank >= SGPR_BANK_OFFSET)) {
 382         // If a register spans all banks we cannot shift it to avoid conflict.
 383         if (countPopulation(LM) / 2 >= NUM_SGPR_BANKS)
 384           continue;
 385         ShiftedBank = SGPR_BANK_OFFSET + (Bank - SGPR_BANK_OFFSET +
 386                                           (countTrailingZeros(LM) >> 1)) %
 387                                              NUM_SGPR_BANKS;
 388       }
 389     }
 390
 391     unsigned Mask = getRegBankMask(R, Op.getSubReg(),
 392                                    (Reg == R) ? ShiftedBank : -1);
 393     StallCycles += countPopulation(UsedBanks & Mask);
 394     UsedBanks |= Mask;
 395     OperandMasks.push_back(OperandMask(Op.getReg(), Op.getSubReg(), Mask));
 396   }
 397
 398   return StallCycles;
 399 }
 400
 401 unsigned GCNRegBankReassign::getOperandGatherWeight(const MachineInstr& MI,
 402                                                     unsigned Reg1,
 403                                                     unsigned Reg2,
 404                                                     unsigned StallCycles) const
 405 {
 406   unsigned Defs = 0;
 407   MachineBasicBlock::const_instr_iterator Def(MI.getIterator());
 408   MachineBasicBlock::const_instr_iterator B(MI.getParent()->instr_begin());
 409   for (unsigned S = StallCycles; S && Def != B && Defs != 3; --S) {
 410     if (MI.isDebugInstr())
 411       continue;
 412     --Def;
 413     if (Def->getOpcode() == TargetOpcode::IMPLICIT_DEF)
 414       continue;
 415     if (Def->modifiesRegister(Reg1, TRI))
 416       Defs |= 1;
 417     if (Def->modifiesRegister(Reg2, TRI))
 418       Defs |= 2;
 419   }
 420   return countPopulation(Defs);
 421 }
 422
 423 bool GCNRegBankReassign::isReassignable(unsigned Reg) const {
 424   if (Register::isPhysicalRegister(Reg) || !VRM->isAssignedReg(Reg))
 425     return false;
 426
 427   const MachineInstr *Def = MRI->getUniqueVRegDef(Reg);
 428
 429   Register PhysReg = VRM->getPhys(Reg);
 430
 431   if (Def && Def->isCopy() && Def->getOperand(1).getReg() == PhysReg)
 432     return false;
 433
 434   for (auto U : MRI->use_nodbg_operands(Reg)) {
 435     if (U.isImplicit())
 436       return false;
 437     const MachineInstr *UseInst = U.getParent();
 438     if (UseInst->isCopy() && UseInst->getOperand(0).getReg() == PhysReg)
 439       return false;
 440   }
 441
 442   const TargetRegisterClass *RC = TRI->getMinimalPhysRegClass(PhysReg);
 443   if (TRI->hasVGPRs(RC))
 444     return true;
 445
 446   unsigned Size = TRI->getRegSizeInBits(*RC);
 447   if (Size > 32)
 448     PhysReg = TRI->getSubReg(PhysReg, AMDGPU::sub0);
 449
 450   return AMDGPU::SGPR_32RegClass.contains(PhysReg);
 451 }
 452
 453 unsigned GCNRegBankReassign::getFreeBanks(unsigned Mask,
 454                                           unsigned UsedBanks) const {
 455   unsigned Size = countPopulation(Mask);
 456   unsigned FreeBanks = 0;
 457   unsigned Bank = findFirstSet(Mask);
 458
 459   UsedBanks &= ~Mask;
 460
 461   // Find free VGPR banks
 462   if ((Mask & VGPR_BANK_MASK) && (Size < NUM_VGPR_BANKS)) {
 463     for (unsigned I = 0; I < NUM_VGPR_BANKS; ++I) {
 464       if (Bank == I)
 465         continue;
 466       unsigned NewMask = ((1 << Size) - 1) << I;
 467       NewMask = (NewMask | (NewMask >> NUM_VGPR_BANKS)) & VGPR_BANK_MASK;
 468       if (!(UsedBanks & NewMask))
 469         FreeBanks |= 1 << I;
 470     }
 471     return FreeBanks;
 472   }
 473
 474   // Find free SGPR banks
 475   // SGPR tuples must be aligned, so step is size in banks it
 476   // crosses.
 477   Bank -= SGPR_BANK_OFFSET;
 478   for (unsigned I = 0; I < NUM_SGPR_BANKS; I += Size) {
 479     if (Bank == I)
 480       continue;
 481     unsigned NewMask = ((1 << Size) - 1) << I;
 482     NewMask = (NewMask | (NewMask >> NUM_SGPR_BANKS)) & SGPR_BANK_SHIFTED_MASK;
 483     if (!(UsedBanks & (NewMask << SGPR_BANK_OFFSET)))
 484       FreeBanks |= (1 << SGPR_BANK_OFFSET) << I;
 485   }
 486
 487   return FreeBanks;
 488 }
 489
 490 unsigned GCNRegBankReassign::getFreeBanks(unsigned Reg,
 491                                           unsigned SubReg,
 492                                           unsigned Mask,
 493                                           unsigned UsedBanks) const {
 494   if (!isReassignable(Reg))
 495     return 0;
 496
 497   unsigned FreeBanks = getFreeBanks(Mask, UsedBanks);
 498
 499   unsigned LM = TRI->getSubRegIndexLaneMask(SubReg).getAsInteger();
 500   if (!(LM & 1) && (Mask & VGPR_BANK_MASK)) {
 501     unsigned Shift = countTrailingZeros(LM);
 502     if (Shift >= NUM_VGPR_BANKS)
 503       return 0;
 504     unsigned VB = FreeBanks & VGPR_BANK_MASK;
 505     FreeBanks = ((VB >> Shift) | (VB << (NUM_VGPR_BANKS - Shift))) &
 506                 VGPR_BANK_MASK;
 507   } else if (!(LM & 3) && (Mask & SGPR_BANK_MASK)) {
 508     unsigned Shift = countTrailingZeros(LM) >> 1;
 509     if (Shift >= NUM_SGPR_BANKS)
 510       return 0;
 511     unsigned SB = FreeBanks >> SGPR_BANK_OFFSET;
 512     FreeBanks = ((SB >> Shift) | (SB << (NUM_SGPR_BANKS - Shift))) &
 513                 SGPR_BANK_SHIFTED_MASK;
 514     FreeBanks <<= SGPR_BANK_OFFSET;
 515   }
 516
 517   LLVM_DEBUG(if (FreeBanks) {
 518           dbgs() << "Potential reassignments of " << printReg(Reg, SubReg)
 519                  << " to banks: "; dumpFreeBanks(FreeBanks);
 520           dbgs() << '\n'; });
 521
 522   return FreeBanks;
 523 }
 524
 525 void GCNRegBankReassign::collectCandidates(MachineInstr& MI,
 526                                            unsigned UsedBanks,
 527                                            unsigned StallCycles) {
 528   LLVM_DEBUG(MI.dump());
 529
 530   if (!StallCycles)
 531     return;
 532
 533   LLVM_DEBUG(dbgs() << "Stall cycles = " << StallCycles << '\n');
 534
 535   for (unsigned I = 0, E = OperandMasks.size(); I + 1 < E; ++I) {
 536     for (unsigned J = I + 1; J != E; ++J) {
 537       if (!(OperandMasks[I].Mask & OperandMasks[J].Mask))
 538         continue;
 539
 540       unsigned Reg1 = OperandMasks[I].Reg;
 541       unsigned Reg2 = OperandMasks[J].Reg;
 542       unsigned SubReg1 = OperandMasks[I].SubReg;
 543       unsigned SubReg2 = OperandMasks[J].SubReg;
 544       unsigned Mask1 = OperandMasks[I].Mask;
 545       unsigned Mask2 = OperandMasks[J].Mask;
 546       unsigned Size1 = countPopulation(Mask1);
 547       unsigned Size2 = countPopulation(Mask2);
 548
 549       LLVM_DEBUG(dbgs() << "Conflicting operands: " << printReg(Reg1, SubReg1) <<
 550                       " and " << printReg(Reg2, SubReg2) << '\n');
 551
 552       unsigned Weight = getOperandGatherWeight(MI, Reg1, Reg2, StallCycles);
 553       Weight += MLI->getLoopDepth(MI.getParent()) * 10;
 554
 555       LLVM_DEBUG(dbgs() << "Stall weight = " << Weight << '\n');
 556
 557       unsigned FreeBanks1 = getFreeBanks(Reg1, SubReg1, Mask1, UsedBanks);
 558       unsigned FreeBanks2 = getFreeBanks(Reg2, SubReg2, Mask2, UsedBanks);
 559       if (FreeBanks1)
 560         Candidates.push(Candidate(&MI, Reg1, FreeBanks1, Weight
 561                                     + ((Size2 > Size1) ? 1 : 0)));
 562       if (FreeBanks2)
 563         Candidates.push(Candidate(&MI, Reg2, FreeBanks2, Weight
 564                                     + ((Size1 > Size2) ? 1 : 0)));
 565     }
 566   }
 567 }
 568
 569 unsigned GCNRegBankReassign::computeStallCycles(unsigned SrcReg,
 570                                                 unsigned Reg, int Bank,
 571                                                 bool Collect) {
 572   unsigned TotalStallCycles = 0;
 573   unsigned UsedBanks = 0;
 574   SmallSet<const MachineInstr *, 16> Visited;
 575
 576   for (auto &MI : MRI->use_nodbg_instructions(SrcReg)) {
 577     if (MI.isBundle())
 578       continue;
 579     if (!Visited.insert(&MI).second)
 580       continue;
 581     unsigned StallCycles = analyzeInst(MI, UsedBanks, Reg, Bank);
 582     TotalStallCycles += StallCycles;
 583     if (Collect)
 584       collectCandidates(MI, UsedBanks, StallCycles);
 585   }
 586
 587   return TotalStallCycles;
 588 }
 589
 590 unsigned GCNRegBankReassign::scavengeReg(LiveInterval& LI,
 591                                          unsigned Bank) const {
 592   const TargetRegisterClass *RC = MRI->getRegClass(LI.reg);
 593   unsigned MaxNumRegs = (Bank < NUM_VGPR_BANKS) ? MaxNumVGPRs
 594                                                 : MaxNumSGPRs;
 595   unsigned MaxReg = MaxNumRegs + (Bank < NUM_VGPR_BANKS ? AMDGPU::VGPR0
 596                                                         : AMDGPU::SGPR0);
 597
 598   for (unsigned Reg : RC->getRegisters()) {
 599     // Check occupancy limit.
 600     if (TRI->isSubRegisterEq(Reg, MaxReg))
 601       break;
 602
 603     if (!MRI->isAllocatable(Reg) || getPhysRegBank(Reg) != Bank)
 604       continue;
 605
 606     for (unsigned I = 0; CSRegs[I]; ++I)
 607       if (TRI->isSubRegisterEq(Reg, CSRegs[I]) &&
 608           !LRM->isPhysRegUsed(CSRegs[I]))
 609         return AMDGPU::NoRegister;
 610
 611     LLVM_DEBUG(dbgs() << "Trying register " << printReg(Reg) << '\n');
 612
 613     if (!LRM->checkInterference(LI, Reg))
 614       return Reg;
 615   }
 616
 617   return AMDGPU::NoRegister;
 618 }
 619
 620 unsigned GCNRegBankReassign::tryReassign(Candidate &C) {
 621   if (!LIS->hasInterval(C.Reg))
 622     return 0;
 623
 624   LiveInterval &LI = LIS->getInterval(C.Reg);
 625   LLVM_DEBUG(dbgs() << "Try reassign " << printReg(C.Reg) << " in "; C.MI->dump();
 626              LI.dump());
 627
 628   // For each candidate bank walk all instructions in the range of live
 629   // interval and check if replacing the register with one belonging to
 630   // the candidate bank reduces conflicts.
 631
 632   unsigned OrigStalls = computeStallCycles(C.Reg);
 633   LLVM_DEBUG(dbgs() << "--- Stall cycles in range = " << OrigStalls << '\n');
 634   if (!OrigStalls)
 635     return 0;
 636
 637   struct BankStall {
 638     BankStall(unsigned b, unsigned s) : Bank(b), Stalls(s) {};
 639     bool operator< (const BankStall &RHS) const { return Stalls > RHS.Stalls; }
 640     unsigned Bank;
 641     unsigned Stalls;
 642   };
 643   SmallVector<BankStall, 8> BankStalls;
 644
 645   for (int Bank = 0; Bank < NUM_BANKS; ++Bank) {
 646     if (C.FreeBanks & (1 << Bank)) {
 647       LLVM_DEBUG(dbgs() << "Trying bank " << printBank(Bank) << '\n');
 648       unsigned Stalls = computeStallCycles(C.Reg, C.Reg, Bank);
 649       if (Stalls < OrigStalls) {
 650         LLVM_DEBUG(dbgs() << "With bank " << printBank(Bank) << " -> "
 651                      << Stalls << '\n');
 652         BankStalls.push_back(BankStall((unsigned)Bank, Stalls));
 653       }
 654     }
 655   }
 656   std::sort(BankStalls.begin(), BankStalls.end());
 657
 658   Register OrigReg = VRM->getPhys(C.Reg);
 659   LRM->unassign(LI);
 660   while (!BankStalls.empty()) {
 661     BankStall BS = BankStalls.pop_back_val();
 662     unsigned Reg = scavengeReg(LI, BS.Bank);
 663     if (Reg == AMDGPU::NoRegister) {
 664       LLVM_DEBUG(dbgs() << "No free registers in bank " << printBank(BS.Bank)
 665                    << '\n');
 666       continue;
 667     }
 668     LLVM_DEBUG(dbgs() << "Found free register " << printReg(Reg)
 669                  << (LRM->isPhysRegUsed(Reg) ? "" : " (new)")
 670                  << " in bank " << printBank(BS.Bank) << '\n');
 671
 672     LRM->assign(LI, Reg);
 673
 674     LLVM_DEBUG(dbgs() << "--- Cycles saved: " << OrigStalls - BS.Stalls << '\n');
 675
 676     return OrigStalls - BS.Stalls;
 677   }
 678   LRM->assign(LI, OrigReg);
 679
 680   return 0;
 681 }
 682
 683 unsigned GCNRegBankReassign::collectCandidates(MachineFunction &MF,
 684                                                bool Collect) {
 685   unsigned TotalStallCycles = 0;
 686
 687   for (MachineBasicBlock &MBB : MF) {
 688
 689     LLVM_DEBUG(if (Collect) {
 690             if (MBB.getName().empty()) dbgs() << "bb." << MBB.getNumber();
 691             else dbgs() << MBB.getName(); dbgs() << ":\n";
 692           });
 693
 694     for (MachineInstr &MI : MBB.instrs()) {
 695       if (MI.isBundle())
 696           continue; // we analyze the instructions inside the bundle individually
 697
 698       unsigned UsedBanks = 0;
 699       unsigned StallCycles = analyzeInst(MI, UsedBanks);
 700
 701       if (Collect)
 702         collectCandidates(MI, UsedBanks, StallCycles);
 703
 704       TotalStallCycles += StallCycles;
 705     }
 706
 707     LLVM_DEBUG(if (Collect) { dbgs() << '\n'; });
 708   }
 709
 710   return TotalStallCycles;
 711 }
 712
 713 void GCNRegBankReassign::removeCandidates(unsigned Reg) {
 714   Candidates.remove_if([Reg, this](const Candidate& C) {
 715     return C.MI->readsRegister(Reg, TRI);
 716   });
 717 }
 718
 719 bool GCNRegBankReassign::verifyCycles(MachineFunction &MF,
 720                                       unsigned OriginalCycles,
 721                                       unsigned CyclesSaved) {
 722   unsigned StallCycles = collectCandidates(MF, false);
 723   LLVM_DEBUG(dbgs() << "=== After the pass " << StallCycles
 724                << " stall cycles left\n");
 725   return StallCycles + CyclesSaved == OriginalCycles;
 726 }
 727
 728 bool GCNRegBankReassign::runOnMachineFunction(MachineFunction &MF) {
 729   ST = &MF.getSubtarget<GCNSubtarget>();
 730   if (!ST->hasRegisterBanking() || skipFunction(MF.getFunction()))
 731     return false;
 732
 733   MRI = &MF.getRegInfo();
 734   TRI = ST->getRegisterInfo();
 735   MLI = &getAnalysis<MachineLoopInfo>();
 736   VRM = &getAnalysis<VirtRegMap>();
 737   LRM = &getAnalysis<LiveRegMatrix>();
 738   LIS = &getAnalysis<LiveIntervals>();
 739
 740   const SIMachineFunctionInfo *MFI = MF.getInfo<SIMachineFunctionInfo>();
 741   unsigned Occupancy = MFI->getOccupancy();
 742   MaxNumVGPRs = ST->getMaxNumVGPRs(MF);
 743   MaxNumSGPRs = ST->getMaxNumSGPRs(MF);
 744   MaxNumVGPRs = std::min(ST->getMaxNumVGPRs(Occupancy), MaxNumVGPRs);
 745   MaxNumSGPRs = std::min(ST->getMaxNumSGPRs(Occupancy, true), MaxNumSGPRs);
 746
 747   CSRegs = MRI->getCalleeSavedRegs();
 748
 749   RegsUsed.resize(AMDGPU::VGPR_32RegClass.getNumRegs() +
 750                   TRI->getEncodingValue(AMDGPU::SGPR_NULL) / 2 + 1);
 751
 752   LLVM_DEBUG(dbgs() << "=== RegBanks reassign analysis on function " << MF.getName()
 753                << '\n');
 754
 755   unsigned StallCycles = collectCandidates(MF);
 756   NumStallsDetected += StallCycles;
 757
 758   LLVM_DEBUG(dbgs() << "=== " << StallCycles << " stall cycles detected in "
 759                   "function " << MF.getName() << '\n');
 760
 761   Candidates.sort();
 762
 763   LLVM_DEBUG(dbgs() << "\nCandidates:\n\n";
 764         for (auto C : Candidates) C.dump(this);
 765         dbgs() << "\n\n");
 766
 767   unsigned CyclesSaved = 0;
 768   while (!Candidates.empty()) {
 769     Candidate C = Candidates.back();
 770     unsigned LocalCyclesSaved = tryReassign(C);
 771     CyclesSaved += LocalCyclesSaved;
 772
 773     if (VerifyStallCycles > 1 && !verifyCycles(MF, StallCycles, CyclesSaved))
 774       report_fatal_error("RegBank reassign stall cycles verification failed.");
 775
 776     Candidates.pop_back();
 777     if (LocalCyclesSaved) {
 778       removeCandidates(C.Reg);
 779       computeStallCycles(C.Reg, AMDGPU::NoRegister, -1, true);
 780       Candidates.sort();
 781
 782       LLVM_DEBUG(dbgs() << "\nCandidates:\n\n";
 783             for (auto C : Candidates)
 784               C.dump(this);
 785             dbgs() << "\n\n");
 786     }
 787   }
 788   NumStallsRecovered += CyclesSaved;
 789
 790   LLVM_DEBUG(dbgs() << "=== After the pass " << CyclesSaved
 791                << " cycles saved in function " << MF.getName() << '\n');
 792
 793   Candidates.clear();
 794
 795   if (VerifyStallCycles == 1 && !verifyCycles(MF, StallCycles, CyclesSaved))
 796     report_fatal_error("RegBank reassign stall cycles verification failed.");
 797
 798   RegsUsed.clear();
 799
 800   return CyclesSaved > 0;
 801 }