llvm/lib/Target/AMDGPU/AMDGPUPerfHintAnalysis.cpp

   1 //===- AMDGPUPerfHintAnalysis.cpp - analysis of functions memory traffic --===//
   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 Analyzes if a function potentially memory bound and if a kernel
  11 /// kernel may benefit from limiting number of waves to reduce cache thrashing.
  12 ///
  13 //===----------------------------------------------------------------------===//
  14
  15 #include "AMDGPU.h"
  16 #include "AMDGPUPerfHintAnalysis.h"
  17 #include "Utils/AMDGPUBaseInfo.h"
  18 #include "llvm/ADT/SmallSet.h"
  19 #include "llvm/ADT/Statistic.h"
  20 #include "llvm/Analysis/CallGraph.h"
  21 #include "llvm/Analysis/ValueTracking.h"
  22 #include "llvm/CodeGen/TargetLowering.h"
  23 #include "llvm/CodeGen/TargetPassConfig.h"
  24 #include "llvm/CodeGen/TargetSubtargetInfo.h"
  25 #include "llvm/IR/Instructions.h"
  26 #include "llvm/IR/IntrinsicInst.h"
  27 #include "llvm/Support/CommandLine.h"
  28 #include "llvm/Target/TargetMachine.h"
  29
  30 using namespace llvm;
  31
  32 #define DEBUG_TYPE "amdgpu-perf-hint"
  33
  34 static cl::opt<unsigned>
  35     MemBoundThresh("amdgpu-membound-threshold", cl::init(50), cl::Hidden,
  36                    cl::desc("Function mem bound threshold in %"));
  37
  38 static cl::opt<unsigned>
  39     LimitWaveThresh("amdgpu-limit-wave-threshold", cl::init(50), cl::Hidden,
  40                     cl::desc("Kernel limit wave threshold in %"));
  41
  42 static cl::opt<unsigned>
  43     IAWeight("amdgpu-indirect-access-weight", cl::init(1000), cl::Hidden,
  44              cl::desc("Indirect access memory instruction weight"));
  45
  46 static cl::opt<unsigned>
  47     LSWeight("amdgpu-large-stride-weight", cl::init(1000), cl::Hidden,
  48              cl::desc("Large stride memory access weight"));
  49
  50 static cl::opt<unsigned>
  51     LargeStrideThresh("amdgpu-large-stride-threshold", cl::init(64), cl::Hidden,
  52                       cl::desc("Large stride memory access threshold"));
  53
  54 STATISTIC(NumMemBound, "Number of functions marked as memory bound");
  55 STATISTIC(NumLimitWave, "Number of functions marked as needing limit wave");
  56
  57 char llvm::AMDGPUPerfHintAnalysis::ID = 0;
  58 char &llvm::AMDGPUPerfHintAnalysisID = AMDGPUPerfHintAnalysis::ID;
  59
  60 INITIALIZE_PASS(AMDGPUPerfHintAnalysis, DEBUG_TYPE,
  61                 "Analysis if a function is memory bound", true, true)
  62
  63 namespace {
  64
  65 struct AMDGPUPerfHint {
  66   friend AMDGPUPerfHintAnalysis;
  67
  68 public:
  69   AMDGPUPerfHint(AMDGPUPerfHintAnalysis::FuncInfoMap &FIM_,
  70                  const TargetLowering *TLI_)
  71       : FIM(FIM_), TLI(TLI_) {}
  72
  73   bool runOnFunction(Function &F);
  74
  75 private:
  76   struct MemAccessInfo {
  77     const Value *V = nullptr;
  78     const Value *Base = nullptr;
  79     int64_t Offset = 0;
  80     MemAccessInfo() = default;
  81     bool isLargeStride(MemAccessInfo &Reference) const;
  82 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
  83     Printable print() const {
  84       return Printable([this](raw_ostream &OS) {
  85         OS << "Value: " << *V << '\n'
  86            << "Base: " << *Base << " Offset: " << Offset << '\n';
  87       });
  88     }
  89 #endif
  90   };
  91
  92   MemAccessInfo makeMemAccessInfo(Instruction *) const;
  93
  94   MemAccessInfo LastAccess; // Last memory access info
  95
  96   AMDGPUPerfHintAnalysis::FuncInfoMap &FIM;
  97
  98   const DataLayout *DL = nullptr;
  99
 100   const TargetLowering *TLI;
 101
 102   AMDGPUPerfHintAnalysis::FuncInfo *visit(const Function &F);
 103   static bool isMemBound(const AMDGPUPerfHintAnalysis::FuncInfo &F);
 104   static bool needLimitWave(const AMDGPUPerfHintAnalysis::FuncInfo &F);
 105
 106   bool isIndirectAccess(const Instruction *Inst) const;
 107
 108   /// Check if the instruction is large stride.
 109   /// The purpose is to identify memory access pattern like:
 110   /// x = a[i];
 111   /// y = a[i+1000];
 112   /// z = a[i+2000];
 113   /// In the above example, the second and third memory access will be marked
 114   /// large stride memory access.
 115   bool isLargeStride(const Instruction *Inst);
 116
 117   bool isGlobalAddr(const Value *V) const;
 118   bool isLocalAddr(const Value *V) const;
 119   bool isGlobalLoadUsedInBB(const Instruction &) const;
 120 };
 121
 122 static std::pair<const Value *, const Type *> getMemoryInstrPtrAndType(
 123     const Instruction *Inst) {
 124   if (auto LI = dyn_cast<LoadInst>(Inst))
 125     return {LI->getPointerOperand(), LI->getType()};
 126   if (auto SI = dyn_cast<StoreInst>(Inst))
 127     return {SI->getPointerOperand(), SI->getValueOperand()->getType()};
 128   if (auto AI = dyn_cast<AtomicCmpXchgInst>(Inst))
 129     return {AI->getPointerOperand(), AI->getCompareOperand()->getType()};
 130   if (auto AI = dyn_cast<AtomicRMWInst>(Inst))
 131     return {AI->getPointerOperand(), AI->getValOperand()->getType()};
 132   if (auto MI = dyn_cast<AnyMemIntrinsic>(Inst))
 133     return {MI->getRawDest(), Type::getInt8Ty(MI->getContext())};
 134
 135   return {nullptr, nullptr};
 136 }
 137
 138 bool AMDGPUPerfHint::isIndirectAccess(const Instruction *Inst) const {
 139   LLVM_DEBUG(dbgs() << "[isIndirectAccess] " << *Inst << '\n');
 140   SmallSet<const Value *, 32> WorkSet;
 141   SmallSet<const Value *, 32> Visited;
 142   if (const Value *MO = getMemoryInstrPtrAndType(Inst).first) {
 143     if (isGlobalAddr(MO))
 144       WorkSet.insert(MO);
 145   }
 146
 147   while (!WorkSet.empty()) {
 148     const Value *V = *WorkSet.begin();
 149     WorkSet.erase(*WorkSet.begin());
 150     if (!Visited.insert(V).second)
 151       continue;
 152     LLVM_DEBUG(dbgs() << "  check: " << *V << '\n');
 153
 154     if (auto LD = dyn_cast<LoadInst>(V)) {
 155       auto M = LD->getPointerOperand();
 156       if (isGlobalAddr(M)) {
 157         LLVM_DEBUG(dbgs() << "    is IA\n");
 158         return true;
 159       }
 160       continue;
 161     }
 162
 163     if (auto GEP = dyn_cast<GetElementPtrInst>(V)) {
 164       auto P = GEP->getPointerOperand();
 165       WorkSet.insert(P);
 166       for (unsigned I = 1, E = GEP->getNumIndices() + 1; I != E; ++I)
 167         WorkSet.insert(GEP->getOperand(I));
 168       continue;
 169     }
 170
 171     if (auto U = dyn_cast<UnaryInstruction>(V)) {
 172       WorkSet.insert(U->getOperand(0));
 173       continue;
 174     }
 175
 176     if (auto BO = dyn_cast<BinaryOperator>(V)) {
 177       WorkSet.insert(BO->getOperand(0));
 178       WorkSet.insert(BO->getOperand(1));
 179       continue;
 180     }
 181
 182     if (auto S = dyn_cast<SelectInst>(V)) {
 183       WorkSet.insert(S->getFalseValue());
 184       WorkSet.insert(S->getTrueValue());
 185       continue;
 186     }
 187
 188     if (auto E = dyn_cast<ExtractElementInst>(V)) {
 189       WorkSet.insert(E->getVectorOperand());
 190       continue;
 191     }
 192
 193     LLVM_DEBUG(dbgs() << "    dropped\n");
 194   }
 195
 196   LLVM_DEBUG(dbgs() << "  is not IA\n");
 197   return false;
 198 }
 199
 200 // Returns true if the global load `I` is used in its own basic block.
 201 bool AMDGPUPerfHint::isGlobalLoadUsedInBB(const Instruction &I) const {
 202   const auto *Ld = dyn_cast<LoadInst>(&I);
 203   if (!Ld)
 204     return false;
 205   if (!isGlobalAddr(Ld->getPointerOperand()))
 206     return false;
 207
 208   for (const User *Usr : Ld->users()) {
 209     if (const Instruction *UsrInst = dyn_cast<Instruction>(Usr)) {
 210       if (UsrInst->getParent() == I.getParent())
 211         return true;
 212     }
 213   }
 214
 215   return false;
 216 }
 217
 218 AMDGPUPerfHintAnalysis::FuncInfo *AMDGPUPerfHint::visit(const Function &F) {
 219   AMDGPUPerfHintAnalysis::FuncInfo &FI = FIM[&F];
 220
 221   LLVM_DEBUG(dbgs() << "[AMDGPUPerfHint] process " << F.getName() << '\n');
 222
 223   for (auto &B : F) {
 224     LastAccess = MemAccessInfo();
 225     unsigned UsedGlobalLoadsInBB = 0;
 226     for (auto &I : B) {
 227       if (const Type *Ty = getMemoryInstrPtrAndType(&I).second) {
 228         unsigned Size = divideCeil(Ty->getPrimitiveSizeInBits(), 32);
 229         // TODO: Check if the global load and its user are close to each other
 230         // instead (Or do this analysis in GCNSchedStrategy?).
 231         if (isGlobalLoadUsedInBB(I))
 232           UsedGlobalLoadsInBB += Size;
 233         if (isIndirectAccess(&I))
 234           FI.IAMInstCost += Size;
 235         if (isLargeStride(&I))
 236           FI.LSMInstCost += Size;
 237         FI.MemInstCost += Size;
 238         FI.InstCost += Size;
 239         continue;
 240       }
 241       if (auto *CB = dyn_cast<CallBase>(&I)) {
 242         Function *Callee = CB->getCalledFunction();
 243         if (!Callee || Callee->isDeclaration()) {
 244           ++FI.InstCost;
 245           continue;
 246         }
 247         if (&F == Callee) // Handle immediate recursion
 248           continue;
 249
 250         auto Loc = FIM.find(Callee);
 251         if (Loc == FIM.end())
 252           continue;
 253
 254         FI.MemInstCost += Loc->second.MemInstCost;
 255         FI.InstCost += Loc->second.InstCost;
 256         FI.IAMInstCost += Loc->second.IAMInstCost;
 257         FI.LSMInstCost += Loc->second.LSMInstCost;
 258       } else if (auto *GEP = dyn_cast<GetElementPtrInst>(&I)) {
 259         TargetLoweringBase::AddrMode AM;
 260         auto *Ptr = GetPointerBaseWithConstantOffset(GEP, AM.BaseOffs, *DL);
 261         AM.BaseGV = dyn_cast_or_null<GlobalValue>(const_cast<Value *>(Ptr));
 262         AM.HasBaseReg = !AM.BaseGV;
 263         if (TLI->isLegalAddressingMode(*DL, AM, GEP->getResultElementType(),
 264                                        GEP->getPointerAddressSpace()))
 265           // Offset will likely be folded into load or store
 266           continue;
 267         ++FI.InstCost;
 268       } else {
 269         ++FI.InstCost;
 270       }
 271     }
 272
 273     if (!FI.HasDenseGlobalMemAcc) {
 274       unsigned GlobalMemAccPercentage = UsedGlobalLoadsInBB * 100 / B.size();
 275       if (GlobalMemAccPercentage > 50) {
 276         LLVM_DEBUG(dbgs() << "[HasDenseGlobalMemAcc] Set to true since "
 277                           << B.getName() << " has " << GlobalMemAccPercentage
 278                           << "% global memory access\n");
 279         FI.HasDenseGlobalMemAcc = true;
 280       }
 281     }
 282   }
 283
 284   return &FI;
 285 }
 286
 287 bool AMDGPUPerfHint::runOnFunction(Function &F) {
 288   const Module &M = *F.getParent();
 289   DL = &M.getDataLayout();
 290
 291   if (F.hasFnAttribute("amdgpu-wave-limiter") &&
 292       F.hasFnAttribute("amdgpu-memory-bound"))
 293     return false;
 294
 295   const AMDGPUPerfHintAnalysis::FuncInfo *Info = visit(F);
 296
 297   LLVM_DEBUG(dbgs() << F.getName() << " MemInst cost: " << Info->MemInstCost
 298                     << '\n'
 299                     << " IAMInst cost: " << Info->IAMInstCost << '\n'
 300                     << " LSMInst cost: " << Info->LSMInstCost << '\n'
 301                     << " TotalInst cost: " << Info->InstCost << '\n');
 302
 303   bool Changed = false;
 304
 305   if (isMemBound(*Info)) {
 306     LLVM_DEBUG(dbgs() << F.getName() << " is memory bound\n");
 307     NumMemBound++;
 308     F.addFnAttr("amdgpu-memory-bound", "true");
 309     Changed = true;
 310   }
 311
 312   if (AMDGPU::isEntryFunctionCC(F.getCallingConv()) && needLimitWave(*Info)) {
 313     LLVM_DEBUG(dbgs() << F.getName() << " needs limit wave\n");
 314     NumLimitWave++;
 315     F.addFnAttr("amdgpu-wave-limiter", "true");
 316     Changed = true;
 317   }
 318
 319   return Changed;
 320 }
 321
 322 bool AMDGPUPerfHint::isMemBound(const AMDGPUPerfHintAnalysis::FuncInfo &FI) {
 323   // Reverting optimal scheduling in favour of occupancy with basic block(s)
 324   // having dense global memory access can potentially hurt performance.
 325   if (FI.HasDenseGlobalMemAcc)
 326     return true;
 327
 328   return FI.MemInstCost * 100 / FI.InstCost > MemBoundThresh;
 329 }
 330
 331 bool AMDGPUPerfHint::needLimitWave(const AMDGPUPerfHintAnalysis::FuncInfo &FI) {
 332   return ((FI.MemInstCost + FI.IAMInstCost * IAWeight +
 333            FI.LSMInstCost * LSWeight) * 100 / FI.InstCost) > LimitWaveThresh;
 334 }
 335
 336 bool AMDGPUPerfHint::isGlobalAddr(const Value *V) const {
 337   if (auto PT = dyn_cast<PointerType>(V->getType())) {
 338     unsigned As = PT->getAddressSpace();
 339     // Flat likely points to global too.
 340     return As == AMDGPUAS::GLOBAL_ADDRESS || As == AMDGPUAS::FLAT_ADDRESS;
 341   }
 342   return false;
 343 }
 344
 345 bool AMDGPUPerfHint::isLocalAddr(const Value *V) const {
 346   if (auto PT = dyn_cast<PointerType>(V->getType()))
 347     return PT->getAddressSpace() == AMDGPUAS::LOCAL_ADDRESS;
 348   return false;
 349 }
 350
 351 bool AMDGPUPerfHint::isLargeStride(const Instruction *Inst) {
 352   LLVM_DEBUG(dbgs() << "[isLargeStride] " << *Inst << '\n');
 353
 354   MemAccessInfo MAI = makeMemAccessInfo(const_cast<Instruction *>(Inst));
 355   bool IsLargeStride = MAI.isLargeStride(LastAccess);
 356   if (MAI.Base)
 357     LastAccess = std::move(MAI);
 358
 359   return IsLargeStride;
 360 }
 361
 362 AMDGPUPerfHint::MemAccessInfo
 363 AMDGPUPerfHint::makeMemAccessInfo(Instruction *Inst) const {
 364   MemAccessInfo MAI;
 365   const Value *MO = getMemoryInstrPtrAndType(Inst).first;
 366
 367   LLVM_DEBUG(dbgs() << "[isLargeStride] MO: " << *MO << '\n');
 368   // Do not treat local-addr memory access as large stride.
 369   if (isLocalAddr(MO))
 370     return MAI;
 371
 372   MAI.V = MO;
 373   MAI.Base = GetPointerBaseWithConstantOffset(MO, MAI.Offset, *DL);
 374   return MAI;
 375 }
 376
 377 bool AMDGPUPerfHint::MemAccessInfo::isLargeStride(
 378     MemAccessInfo &Reference) const {
 379
 380   if (!Base || !Reference.Base || Base != Reference.Base)
 381     return false;
 382
 383   uint64_t Diff = Offset > Reference.Offset ? Offset - Reference.Offset
 384                                             : Reference.Offset - Offset;
 385   bool Result = Diff > LargeStrideThresh;
 386   LLVM_DEBUG(dbgs() << "[isLargeStride compare]\n"
 387                << print() << "<=>\n"
 388                << Reference.print() << "Result:" << Result << '\n');
 389   return Result;
 390 }
 391 } // namespace
 392
 393 bool AMDGPUPerfHintAnalysis::runOnSCC(CallGraphSCC &SCC) {
 394   auto *TPC = getAnalysisIfAvailable<TargetPassConfig>();
 395   if (!TPC)
 396     return false;
 397
 398   const TargetMachine &TM = TPC->getTM<TargetMachine>();
 399
 400   bool Changed = false;
 401   for (CallGraphNode *I : SCC) {
 402     Function *F = I->getFunction();
 403     if (!F || F->isDeclaration())
 404       continue;
 405
 406     const TargetSubtargetInfo *ST = TM.getSubtargetImpl(*F);
 407     AMDGPUPerfHint Analyzer(FIM, ST->getTargetLowering());
 408
 409     if (Analyzer.runOnFunction(*F))
 410       Changed = true;
 411   }
 412
 413   return Changed;
 414 }
 415
 416 bool AMDGPUPerfHintAnalysis::isMemoryBound(const Function *F) const {
 417   auto FI = FIM.find(F);
 418   if (FI == FIM.end())
 419     return false;
 420
 421   return AMDGPUPerfHint::isMemBound(FI->second);
 422 }
 423
 424 bool AMDGPUPerfHintAnalysis::needsWaveLimiter(const Function *F) const {
 425   auto FI = FIM.find(F);
 426   if (FI == FIM.end())
 427     return false;
 428
 429   return AMDGPUPerfHint::needLimitWave(FI->second);
 430 }