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