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