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: 71 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; 82 MemAccessInfo() : V(nullptr), Base(nullptr), Offset(0) {} 83 bool isLargeStride(MemAccessInfo &Reference) const; 84 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP) 85 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 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 146 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 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 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 295 bool AMDGPUPerfHint::isMemBound(const AMDGPUPerfHintAnalysis::FuncInfo &FI) { 296 return FI.MemInstCount * 100 / FI.InstCount > MemBoundThresh; 297 } 298 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 305 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 314 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 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 332 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 346 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 354 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 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 383 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 391 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