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:
AMDGPUPerfHint__anon2f55d1980111::AMDGPUPerfHint71 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;
MemAccessInfo__anon2f55d1980111::AMDGPUPerfHint::MemAccessInfo82 MemAccessInfo() : V(nullptr), Base(nullptr), Offset(0) {}
83 bool isLargeStride(MemAccessInfo &Reference) const;
84 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
print__anon2f55d1980111::AMDGPUPerfHint::MemAccessInfo85 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
getMemoryInstrPtr(const Instruction * Inst)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
isIndirectAccess(const Instruction * Inst) const146 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
visit(const Function & F)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
runOnFunction(Function & F)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
isMemBound(const AMDGPUPerfHintAnalysis::FuncInfo & FI)295 bool AMDGPUPerfHint::isMemBound(const AMDGPUPerfHintAnalysis::FuncInfo &FI) {
296 return FI.MemInstCount * 100 / FI.InstCount > MemBoundThresh;
297 }
298
needLimitWave(const AMDGPUPerfHintAnalysis::FuncInfo & FI)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
isGlobalAddr(const Value * V) const305 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
isLocalAddr(const Value * V) const314 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
isLargeStride(const Instruction * Inst)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
makeMemAccessInfo(Instruction * Inst) const332 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
isConstantAddr(const Value * V) const346 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
isLargeStride(MemAccessInfo & Reference) const354 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
runOnFunction(Function & F)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
isMemoryBound(const Function * F) const383 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
needsWaveLimiter(const Function * F) const391 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