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 33 using namespace llvm; 34 35 #define DEBUG_TYPE "amdgpu-perf-hint" 36 37 static cl::opt<unsigned> 38 MemBoundThresh("amdgpu-membound-threshold", cl::init(50), cl::Hidden, 39 cl::desc("Function mem bound threshold in %")); 40 41 static cl::opt<unsigned> 42 LimitWaveThresh("amdgpu-limit-wave-threshold", cl::init(50), cl::Hidden, 43 cl::desc("Kernel limit wave threshold in %")); 44 45 static cl::opt<unsigned> 46 IAWeight("amdgpu-indirect-access-weight", cl::init(1000), cl::Hidden, 47 cl::desc("Indirect access memory instruction weight")); 48 49 static cl::opt<unsigned> 50 LSWeight("amdgpu-large-stride-weight", cl::init(1000), cl::Hidden, 51 cl::desc("Large stride memory access weight")); 52 53 static cl::opt<unsigned> 54 LargeStrideThresh("amdgpu-large-stride-threshold", cl::init(64), cl::Hidden, 55 cl::desc("Large stride memory access threshold")); 56 57 STATISTIC(NumMemBound, "Number of functions marked as memory bound"); 58 STATISTIC(NumLimitWave, "Number of functions marked as needing limit wave"); 59 60 char llvm::AMDGPUPerfHintAnalysis::ID = 0; 61 char &llvm::AMDGPUPerfHintAnalysisID = AMDGPUPerfHintAnalysis::ID; 62 63 INITIALIZE_PASS(AMDGPUPerfHintAnalysis, DEBUG_TYPE, 64 "Analysis if a function is memory bound", true, true) 65 66 namespace { 67 68 struct AMDGPUPerfHint { 69 friend AMDGPUPerfHintAnalysis; 70 71 public: 72 AMDGPUPerfHint(AMDGPUPerfHintAnalysis::FuncInfoMap &FIM_, 73 const TargetLowering *TLI_) 74 : FIM(FIM_), DL(nullptr), TLI(TLI_) {} 75 76 bool runOnFunction(Function &F); 77 78 private: 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 125 static 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 145 bool 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 207 AMDGPUPerfHintAnalysis::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 260 bool 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 291 bool AMDGPUPerfHint::isMemBound(const AMDGPUPerfHintAnalysis::FuncInfo &FI) { 292 return FI.MemInstCount * 100 / FI.InstCount > MemBoundThresh; 293 } 294 295 bool AMDGPUPerfHint::needLimitWave(const AMDGPUPerfHintAnalysis::FuncInfo &FI) { 296 return ((FI.MemInstCount + FI.IAMInstCount * IAWeight + 297 FI.LSMInstCount * LSWeight) * 298 100 / FI.InstCount) > LimitWaveThresh; 299 } 300 301 bool 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 310 bool 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 316 bool 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 327 AMDGPUPerfHint::MemAccessInfo 328 AMDGPUPerfHint::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 342 bool 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 351 bool 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 367 bool 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 390 bool 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 398 bool 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