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