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