1 //===-------- LoopDataPrefetch.cpp - Loop Data Prefetching Pass -----------===// 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 // This file implements a Loop Data Prefetching Pass. 10 // 11 //===----------------------------------------------------------------------===// 12 13 #include "llvm/Transforms/Scalar/LoopDataPrefetch.h" 14 #include "llvm/InitializePasses.h" 15 16 #define DEBUG_TYPE "loop-data-prefetch" 17 #include "llvm/ADT/DepthFirstIterator.h" 18 #include "llvm/ADT/Statistic.h" 19 #include "llvm/Analysis/AssumptionCache.h" 20 #include "llvm/Analysis/CodeMetrics.h" 21 #include "llvm/Analysis/LoopInfo.h" 22 #include "llvm/Analysis/OptimizationRemarkEmitter.h" 23 #include "llvm/Analysis/ScalarEvolution.h" 24 #include "llvm/Analysis/ScalarEvolutionExpressions.h" 25 #include "llvm/Analysis/TargetTransformInfo.h" 26 #include "llvm/IR/CFG.h" 27 #include "llvm/IR/Dominators.h" 28 #include "llvm/IR/Function.h" 29 #include "llvm/IR/Module.h" 30 #include "llvm/Support/CommandLine.h" 31 #include "llvm/Support/Debug.h" 32 #include "llvm/Transforms/Scalar.h" 33 #include "llvm/Transforms/Utils/BasicBlockUtils.h" 34 #include "llvm/Transforms/Utils/ScalarEvolutionExpander.h" 35 #include "llvm/Transforms/Utils/ValueMapper.h" 36 using namespace llvm; 37 38 // By default, we limit this to creating 16 PHIs (which is a little over half 39 // of the allocatable register set). 40 static cl::opt<bool> 41 PrefetchWrites("loop-prefetch-writes", cl::Hidden, cl::init(false), 42 cl::desc("Prefetch write addresses")); 43 44 static cl::opt<unsigned> 45 PrefetchDistance("prefetch-distance", 46 cl::desc("Number of instructions to prefetch ahead"), 47 cl::Hidden); 48 49 static cl::opt<unsigned> 50 MinPrefetchStride("min-prefetch-stride", 51 cl::desc("Min stride to add prefetches"), cl::Hidden); 52 53 static cl::opt<unsigned> MaxPrefetchIterationsAhead( 54 "max-prefetch-iters-ahead", 55 cl::desc("Max number of iterations to prefetch ahead"), cl::Hidden); 56 57 STATISTIC(NumPrefetches, "Number of prefetches inserted"); 58 59 namespace { 60 61 /// Loop prefetch implementation class. 62 class LoopDataPrefetch { 63 public: 64 LoopDataPrefetch(AssumptionCache *AC, DominatorTree *DT, LoopInfo *LI, 65 ScalarEvolution *SE, const TargetTransformInfo *TTI, 66 OptimizationRemarkEmitter *ORE) 67 : AC(AC), DT(DT), LI(LI), SE(SE), TTI(TTI), ORE(ORE) {} 68 69 bool run(); 70 71 private: 72 bool runOnLoop(Loop *L); 73 74 /// Check if the stride of the accesses is large enough to 75 /// warrant a prefetch. 76 bool isStrideLargeEnough(const SCEVAddRecExpr *AR, unsigned TargetMinStride); 77 78 unsigned getMinPrefetchStride(unsigned NumMemAccesses, 79 unsigned NumStridedMemAccesses, 80 unsigned NumPrefetches, 81 bool HasCall) { 82 if (MinPrefetchStride.getNumOccurrences() > 0) 83 return MinPrefetchStride; 84 return TTI->getMinPrefetchStride(NumMemAccesses, NumStridedMemAccesses, 85 NumPrefetches, HasCall); 86 } 87 88 unsigned getPrefetchDistance() { 89 if (PrefetchDistance.getNumOccurrences() > 0) 90 return PrefetchDistance; 91 return TTI->getPrefetchDistance(); 92 } 93 94 unsigned getMaxPrefetchIterationsAhead() { 95 if (MaxPrefetchIterationsAhead.getNumOccurrences() > 0) 96 return MaxPrefetchIterationsAhead; 97 return TTI->getMaxPrefetchIterationsAhead(); 98 } 99 100 bool doPrefetchWrites() { 101 if (PrefetchWrites.getNumOccurrences() > 0) 102 return PrefetchWrites; 103 return TTI->enableWritePrefetching(); 104 } 105 106 AssumptionCache *AC; 107 DominatorTree *DT; 108 LoopInfo *LI; 109 ScalarEvolution *SE; 110 const TargetTransformInfo *TTI; 111 OptimizationRemarkEmitter *ORE; 112 }; 113 114 /// Legacy class for inserting loop data prefetches. 115 class LoopDataPrefetchLegacyPass : public FunctionPass { 116 public: 117 static char ID; // Pass ID, replacement for typeid 118 LoopDataPrefetchLegacyPass() : FunctionPass(ID) { 119 initializeLoopDataPrefetchLegacyPassPass(*PassRegistry::getPassRegistry()); 120 } 121 122 void getAnalysisUsage(AnalysisUsage &AU) const override { 123 AU.addRequired<AssumptionCacheTracker>(); 124 AU.addRequired<DominatorTreeWrapperPass>(); 125 AU.addPreserved<DominatorTreeWrapperPass>(); 126 AU.addRequired<LoopInfoWrapperPass>(); 127 AU.addPreserved<LoopInfoWrapperPass>(); 128 AU.addRequired<OptimizationRemarkEmitterWrapperPass>(); 129 AU.addRequired<ScalarEvolutionWrapperPass>(); 130 AU.addPreserved<ScalarEvolutionWrapperPass>(); 131 AU.addRequired<TargetTransformInfoWrapperPass>(); 132 } 133 134 bool runOnFunction(Function &F) override; 135 }; 136 } 137 138 char LoopDataPrefetchLegacyPass::ID = 0; 139 INITIALIZE_PASS_BEGIN(LoopDataPrefetchLegacyPass, "loop-data-prefetch", 140 "Loop Data Prefetch", false, false) 141 INITIALIZE_PASS_DEPENDENCY(AssumptionCacheTracker) 142 INITIALIZE_PASS_DEPENDENCY(TargetTransformInfoWrapperPass) 143 INITIALIZE_PASS_DEPENDENCY(LoopInfoWrapperPass) 144 INITIALIZE_PASS_DEPENDENCY(OptimizationRemarkEmitterWrapperPass) 145 INITIALIZE_PASS_DEPENDENCY(ScalarEvolutionWrapperPass) 146 INITIALIZE_PASS_END(LoopDataPrefetchLegacyPass, "loop-data-prefetch", 147 "Loop Data Prefetch", false, false) 148 149 FunctionPass *llvm::createLoopDataPrefetchPass() { 150 return new LoopDataPrefetchLegacyPass(); 151 } 152 153 bool LoopDataPrefetch::isStrideLargeEnough(const SCEVAddRecExpr *AR, 154 unsigned TargetMinStride) { 155 // No need to check if any stride goes. 156 if (TargetMinStride <= 1) 157 return true; 158 159 const auto *ConstStride = dyn_cast<SCEVConstant>(AR->getStepRecurrence(*SE)); 160 // If MinStride is set, don't prefetch unless we can ensure that stride is 161 // larger. 162 if (!ConstStride) 163 return false; 164 165 unsigned AbsStride = std::abs(ConstStride->getAPInt().getSExtValue()); 166 return TargetMinStride <= AbsStride; 167 } 168 169 PreservedAnalyses LoopDataPrefetchPass::run(Function &F, 170 FunctionAnalysisManager &AM) { 171 DominatorTree *DT = &AM.getResult<DominatorTreeAnalysis>(F); 172 LoopInfo *LI = &AM.getResult<LoopAnalysis>(F); 173 ScalarEvolution *SE = &AM.getResult<ScalarEvolutionAnalysis>(F); 174 AssumptionCache *AC = &AM.getResult<AssumptionAnalysis>(F); 175 OptimizationRemarkEmitter *ORE = 176 &AM.getResult<OptimizationRemarkEmitterAnalysis>(F); 177 const TargetTransformInfo *TTI = &AM.getResult<TargetIRAnalysis>(F); 178 179 LoopDataPrefetch LDP(AC, DT, LI, SE, TTI, ORE); 180 bool Changed = LDP.run(); 181 182 if (Changed) { 183 PreservedAnalyses PA; 184 PA.preserve<DominatorTreeAnalysis>(); 185 PA.preserve<LoopAnalysis>(); 186 return PA; 187 } 188 189 return PreservedAnalyses::all(); 190 } 191 192 bool LoopDataPrefetchLegacyPass::runOnFunction(Function &F) { 193 if (skipFunction(F)) 194 return false; 195 196 DominatorTree *DT = &getAnalysis<DominatorTreeWrapperPass>().getDomTree(); 197 LoopInfo *LI = &getAnalysis<LoopInfoWrapperPass>().getLoopInfo(); 198 ScalarEvolution *SE = &getAnalysis<ScalarEvolutionWrapperPass>().getSE(); 199 AssumptionCache *AC = 200 &getAnalysis<AssumptionCacheTracker>().getAssumptionCache(F); 201 OptimizationRemarkEmitter *ORE = 202 &getAnalysis<OptimizationRemarkEmitterWrapperPass>().getORE(); 203 const TargetTransformInfo *TTI = 204 &getAnalysis<TargetTransformInfoWrapperPass>().getTTI(F); 205 206 LoopDataPrefetch LDP(AC, DT, LI, SE, TTI, ORE); 207 return LDP.run(); 208 } 209 210 bool LoopDataPrefetch::run() { 211 // If PrefetchDistance is not set, don't run the pass. This gives an 212 // opportunity for targets to run this pass for selected subtargets only 213 // (whose TTI sets PrefetchDistance). 214 if (getPrefetchDistance() == 0) 215 return false; 216 assert(TTI->getCacheLineSize() && "Cache line size is not set for target"); 217 218 bool MadeChange = false; 219 220 for (Loop *I : *LI) 221 for (auto L = df_begin(I), LE = df_end(I); L != LE; ++L) 222 MadeChange |= runOnLoop(*L); 223 224 return MadeChange; 225 } 226 227 /// A record for a potential prefetch made during the initial scan of the 228 /// loop. This is used to let a single prefetch target multiple memory accesses. 229 struct Prefetch { 230 /// The address formula for this prefetch as returned by ScalarEvolution. 231 const SCEVAddRecExpr *LSCEVAddRec; 232 /// The point of insertion for the prefetch instruction. 233 Instruction *InsertPt; 234 /// True if targeting a write memory access. 235 bool Writes; 236 /// The (first seen) prefetched instruction. 237 Instruction *MemI; 238 239 /// Constructor to create a new Prefetch for \p I. 240 Prefetch(const SCEVAddRecExpr *L, Instruction *I) 241 : LSCEVAddRec(L), InsertPt(nullptr), Writes(false), MemI(nullptr) { 242 addInstruction(I); 243 }; 244 245 /// Add the instruction \param I to this prefetch. If it's not the first 246 /// one, 'InsertPt' and 'Writes' will be updated as required. 247 /// \param PtrDiff the known constant address difference to the first added 248 /// instruction. 249 void addInstruction(Instruction *I, DominatorTree *DT = nullptr, 250 int64_t PtrDiff = 0) { 251 if (!InsertPt) { 252 MemI = I; 253 InsertPt = I; 254 Writes = isa<StoreInst>(I); 255 } else { 256 BasicBlock *PrefBB = InsertPt->getParent(); 257 BasicBlock *InsBB = I->getParent(); 258 if (PrefBB != InsBB) { 259 BasicBlock *DomBB = DT->findNearestCommonDominator(PrefBB, InsBB); 260 if (DomBB != PrefBB) 261 InsertPt = DomBB->getTerminator(); 262 } 263 264 if (isa<StoreInst>(I) && PtrDiff == 0) 265 Writes = true; 266 } 267 } 268 }; 269 270 bool LoopDataPrefetch::runOnLoop(Loop *L) { 271 bool MadeChange = false; 272 273 // Only prefetch in the inner-most loop 274 if (!L->isInnermost()) 275 return MadeChange; 276 277 SmallPtrSet<const Value *, 32> EphValues; 278 CodeMetrics::collectEphemeralValues(L, AC, EphValues); 279 280 // Calculate the number of iterations ahead to prefetch 281 CodeMetrics Metrics; 282 bool HasCall = false; 283 for (const auto BB : L->blocks()) { 284 // If the loop already has prefetches, then assume that the user knows 285 // what they are doing and don't add any more. 286 for (auto &I : *BB) { 287 if (isa<CallInst>(&I) || isa<InvokeInst>(&I)) { 288 if (const Function *F = cast<CallBase>(I).getCalledFunction()) { 289 if (F->getIntrinsicID() == Intrinsic::prefetch) 290 return MadeChange; 291 if (TTI->isLoweredToCall(F)) 292 HasCall = true; 293 } else { // indirect call. 294 HasCall = true; 295 } 296 } 297 } 298 Metrics.analyzeBasicBlock(BB, *TTI, EphValues); 299 } 300 unsigned LoopSize = Metrics.NumInsts; 301 if (!LoopSize) 302 LoopSize = 1; 303 304 unsigned ItersAhead = getPrefetchDistance() / LoopSize; 305 if (!ItersAhead) 306 ItersAhead = 1; 307 308 if (ItersAhead > getMaxPrefetchIterationsAhead()) 309 return MadeChange; 310 311 unsigned ConstantMaxTripCount = SE->getSmallConstantMaxTripCount(L); 312 if (ConstantMaxTripCount && ConstantMaxTripCount < ItersAhead + 1) 313 return MadeChange; 314 315 unsigned NumMemAccesses = 0; 316 unsigned NumStridedMemAccesses = 0; 317 SmallVector<Prefetch, 16> Prefetches; 318 for (const auto BB : L->blocks()) 319 for (auto &I : *BB) { 320 Value *PtrValue; 321 Instruction *MemI; 322 323 if (LoadInst *LMemI = dyn_cast<LoadInst>(&I)) { 324 MemI = LMemI; 325 PtrValue = LMemI->getPointerOperand(); 326 } else if (StoreInst *SMemI = dyn_cast<StoreInst>(&I)) { 327 if (!doPrefetchWrites()) continue; 328 MemI = SMemI; 329 PtrValue = SMemI->getPointerOperand(); 330 } else continue; 331 332 unsigned PtrAddrSpace = PtrValue->getType()->getPointerAddressSpace(); 333 if (PtrAddrSpace) 334 continue; 335 NumMemAccesses++; 336 if (L->isLoopInvariant(PtrValue)) 337 continue; 338 339 const SCEV *LSCEV = SE->getSCEV(PtrValue); 340 const SCEVAddRecExpr *LSCEVAddRec = dyn_cast<SCEVAddRecExpr>(LSCEV); 341 if (!LSCEVAddRec) 342 continue; 343 NumStridedMemAccesses++; 344 345 // We don't want to double prefetch individual cache lines. If this 346 // access is known to be within one cache line of some other one that 347 // has already been prefetched, then don't prefetch this one as well. 348 bool DupPref = false; 349 for (auto &Pref : Prefetches) { 350 const SCEV *PtrDiff = SE->getMinusSCEV(LSCEVAddRec, Pref.LSCEVAddRec); 351 if (const SCEVConstant *ConstPtrDiff = 352 dyn_cast<SCEVConstant>(PtrDiff)) { 353 int64_t PD = std::abs(ConstPtrDiff->getValue()->getSExtValue()); 354 if (PD < (int64_t) TTI->getCacheLineSize()) { 355 Pref.addInstruction(MemI, DT, PD); 356 DupPref = true; 357 break; 358 } 359 } 360 } 361 if (!DupPref) 362 Prefetches.push_back(Prefetch(LSCEVAddRec, MemI)); 363 } 364 365 unsigned TargetMinStride = 366 getMinPrefetchStride(NumMemAccesses, NumStridedMemAccesses, 367 Prefetches.size(), HasCall); 368 369 LLVM_DEBUG(dbgs() << "Prefetching " << ItersAhead 370 << " iterations ahead (loop size: " << LoopSize << ") in " 371 << L->getHeader()->getParent()->getName() << ": " << *L); 372 LLVM_DEBUG(dbgs() << "Loop has: " 373 << NumMemAccesses << " memory accesses, " 374 << NumStridedMemAccesses << " strided memory accesses, " 375 << Prefetches.size() << " potential prefetch(es), " 376 << "a minimum stride of " << TargetMinStride << ", " 377 << (HasCall ? "calls" : "no calls") << ".\n"); 378 379 for (auto &P : Prefetches) { 380 // Check if the stride of the accesses is large enough to warrant a 381 // prefetch. 382 if (!isStrideLargeEnough(P.LSCEVAddRec, TargetMinStride)) 383 continue; 384 385 const SCEV *NextLSCEV = SE->getAddExpr(P.LSCEVAddRec, SE->getMulExpr( 386 SE->getConstant(P.LSCEVAddRec->getType(), ItersAhead), 387 P.LSCEVAddRec->getStepRecurrence(*SE))); 388 if (!isSafeToExpand(NextLSCEV, *SE)) 389 continue; 390 391 BasicBlock *BB = P.InsertPt->getParent(); 392 Type *I8Ptr = Type::getInt8PtrTy(BB->getContext(), 0/*PtrAddrSpace*/); 393 SCEVExpander SCEVE(*SE, BB->getModule()->getDataLayout(), "prefaddr"); 394 Value *PrefPtrValue = SCEVE.expandCodeFor(NextLSCEV, I8Ptr, P.InsertPt); 395 396 IRBuilder<> Builder(P.InsertPt); 397 Module *M = BB->getParent()->getParent(); 398 Type *I32 = Type::getInt32Ty(BB->getContext()); 399 Function *PrefetchFunc = Intrinsic::getDeclaration( 400 M, Intrinsic::prefetch, PrefPtrValue->getType()); 401 Builder.CreateCall( 402 PrefetchFunc, 403 {PrefPtrValue, 404 ConstantInt::get(I32, P.Writes), 405 ConstantInt::get(I32, 3), ConstantInt::get(I32, 1)}); 406 ++NumPrefetches; 407 LLVM_DEBUG(dbgs() << " Access: " 408 << *P.MemI->getOperand(isa<LoadInst>(P.MemI) ? 0 : 1) 409 << ", SCEV: " << *P.LSCEVAddRec << "\n"); 410 ORE->emit([&]() { 411 return OptimizationRemark(DEBUG_TYPE, "Prefetched", P.MemI) 412 << "prefetched memory access"; 413 }); 414 415 MadeChange = true; 416 } 417 418 return MadeChange; 419 } 420