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