1 //===-------- LoopDataPrefetch.cpp - Loop Data Prefetching Pass -----------===// 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 // This file implements a Loop Data Prefetching Pass. 11 // 12 //===----------------------------------------------------------------------===// 13 14 #include "llvm/Transforms/Scalar/LoopDataPrefetch.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/InstructionSimplify.h" 22 #include "llvm/Analysis/LoopInfo.h" 23 #include "llvm/Analysis/OptimizationDiagnosticInfo.h" 24 #include "llvm/Analysis/ScalarEvolution.h" 25 #include "llvm/Analysis/ScalarEvolutionAliasAnalysis.h" 26 #include "llvm/Analysis/ScalarEvolutionExpander.h" 27 #include "llvm/Analysis/ScalarEvolutionExpressions.h" 28 #include "llvm/Analysis/TargetTransformInfo.h" 29 #include "llvm/Analysis/ValueTracking.h" 30 #include "llvm/IR/CFG.h" 31 #include "llvm/IR/Dominators.h" 32 #include "llvm/IR/Function.h" 33 #include "llvm/IR/IntrinsicInst.h" 34 #include "llvm/IR/Module.h" 35 #include "llvm/Support/CommandLine.h" 36 #include "llvm/Support/Debug.h" 37 #include "llvm/Transforms/Scalar.h" 38 #include "llvm/Transforms/Utils/BasicBlockUtils.h" 39 #include "llvm/Transforms/Utils/Local.h" 40 #include "llvm/Transforms/Utils/ValueMapper.h" 41 using namespace llvm; 42 43 // By default, we limit this to creating 16 PHIs (which is a little over half 44 // of the allocatable register set). 45 static cl::opt<bool> 46 PrefetchWrites("loop-prefetch-writes", cl::Hidden, cl::init(false), 47 cl::desc("Prefetch write addresses")); 48 49 static cl::opt<unsigned> 50 PrefetchDistance("prefetch-distance", 51 cl::desc("Number of instructions to prefetch ahead"), 52 cl::Hidden); 53 54 static cl::opt<unsigned> 55 MinPrefetchStride("min-prefetch-stride", 56 cl::desc("Min stride to add prefetches"), cl::Hidden); 57 58 static cl::opt<unsigned> MaxPrefetchIterationsAhead( 59 "max-prefetch-iters-ahead", 60 cl::desc("Max number of iterations to prefetch ahead"), cl::Hidden); 61 62 STATISTIC(NumPrefetches, "Number of prefetches inserted"); 63 64 namespace { 65 66 /// Loop prefetch implementation class. 67 class LoopDataPrefetch { 68 public: 69 LoopDataPrefetch(AssumptionCache *AC, LoopInfo *LI, ScalarEvolution *SE, 70 const TargetTransformInfo *TTI, 71 OptimizationRemarkEmitter *ORE) 72 : AC(AC), LI(LI), SE(SE), TTI(TTI), ORE(ORE) {} 73 74 bool run(); 75 76 private: 77 bool runOnLoop(Loop *L); 78 79 /// \brief Check if the the stride of the accesses is large enough to 80 /// warrant a prefetch. 81 bool isStrideLargeEnough(const SCEVAddRecExpr *AR); 82 83 unsigned getMinPrefetchStride() { 84 if (MinPrefetchStride.getNumOccurrences() > 0) 85 return MinPrefetchStride; 86 return TTI->getMinPrefetchStride(); 87 } 88 89 unsigned getPrefetchDistance() { 90 if (PrefetchDistance.getNumOccurrences() > 0) 91 return PrefetchDistance; 92 return TTI->getPrefetchDistance(); 93 } 94 95 unsigned getMaxPrefetchIterationsAhead() { 96 if (MaxPrefetchIterationsAhead.getNumOccurrences() > 0) 97 return MaxPrefetchIterationsAhead; 98 return TTI->getMaxPrefetchIterationsAhead(); 99 } 100 101 AssumptionCache *AC; 102 LoopInfo *LI; 103 ScalarEvolution *SE; 104 const TargetTransformInfo *TTI; 105 OptimizationRemarkEmitter *ORE; 106 }; 107 108 /// Legacy class for inserting loop data prefetches. 109 class LoopDataPrefetchLegacyPass : public FunctionPass { 110 public: 111 static char ID; // Pass ID, replacement for typeid 112 LoopDataPrefetchLegacyPass() : FunctionPass(ID) { 113 initializeLoopDataPrefetchLegacyPassPass(*PassRegistry::getPassRegistry()); 114 } 115 116 void getAnalysisUsage(AnalysisUsage &AU) const override { 117 AU.addRequired<AssumptionCacheTracker>(); 118 AU.addPreserved<DominatorTreeWrapperPass>(); 119 AU.addRequired<LoopInfoWrapperPass>(); 120 AU.addPreserved<LoopInfoWrapperPass>(); 121 AU.addRequired<OptimizationRemarkEmitterWrapperPass>(); 122 AU.addRequired<ScalarEvolutionWrapperPass>(); 123 // FIXME: For some reason, preserving SE here breaks LSR (even if 124 // this pass changes nothing). 125 // AU.addPreserved<ScalarEvolutionWrapperPass>(); 126 AU.addRequired<TargetTransformInfoWrapperPass>(); 127 } 128 129 bool runOnFunction(Function &F) override; 130 }; 131 } 132 133 char LoopDataPrefetchLegacyPass::ID = 0; 134 INITIALIZE_PASS_BEGIN(LoopDataPrefetchLegacyPass, "loop-data-prefetch", 135 "Loop Data Prefetch", false, false) 136 INITIALIZE_PASS_DEPENDENCY(AssumptionCacheTracker) 137 INITIALIZE_PASS_DEPENDENCY(TargetTransformInfoWrapperPass) 138 INITIALIZE_PASS_DEPENDENCY(LoopInfoWrapperPass) 139 INITIALIZE_PASS_DEPENDENCY(OptimizationRemarkEmitterWrapperPass) 140 INITIALIZE_PASS_DEPENDENCY(ScalarEvolutionWrapperPass) 141 INITIALIZE_PASS_END(LoopDataPrefetchLegacyPass, "loop-data-prefetch", 142 "Loop Data Prefetch", false, false) 143 144 FunctionPass *llvm::createLoopDataPrefetchPass() { 145 return new LoopDataPrefetchLegacyPass(); 146 } 147 148 bool LoopDataPrefetch::isStrideLargeEnough(const SCEVAddRecExpr *AR) { 149 unsigned TargetMinStride = getMinPrefetchStride(); 150 // No need to check if any stride goes. 151 if (TargetMinStride <= 1) 152 return true; 153 154 const auto *ConstStride = dyn_cast<SCEVConstant>(AR->getStepRecurrence(*SE)); 155 // If MinStride is set, don't prefetch unless we can ensure that stride is 156 // larger. 157 if (!ConstStride) 158 return false; 159 160 unsigned AbsStride = std::abs(ConstStride->getAPInt().getSExtValue()); 161 return TargetMinStride <= AbsStride; 162 } 163 164 PreservedAnalyses LoopDataPrefetchPass::run(Function &F, 165 FunctionAnalysisManager &AM) { 166 LoopInfo *LI = &AM.getResult<LoopAnalysis>(F); 167 ScalarEvolution *SE = &AM.getResult<ScalarEvolutionAnalysis>(F); 168 AssumptionCache *AC = &AM.getResult<AssumptionAnalysis>(F); 169 OptimizationRemarkEmitter *ORE = 170 &AM.getResult<OptimizationRemarkEmitterAnalysis>(F); 171 const TargetTransformInfo *TTI = &AM.getResult<TargetIRAnalysis>(F); 172 173 LoopDataPrefetch LDP(AC, LI, SE, TTI, ORE); 174 bool Changed = LDP.run(); 175 176 if (Changed) { 177 PreservedAnalyses PA; 178 PA.preserve<DominatorTreeAnalysis>(); 179 PA.preserve<LoopAnalysis>(); 180 return PA; 181 } 182 183 return PreservedAnalyses::all(); 184 } 185 186 bool LoopDataPrefetchLegacyPass::runOnFunction(Function &F) { 187 if (skipFunction(F)) 188 return false; 189 190 LoopInfo *LI = &getAnalysis<LoopInfoWrapperPass>().getLoopInfo(); 191 ScalarEvolution *SE = &getAnalysis<ScalarEvolutionWrapperPass>().getSE(); 192 AssumptionCache *AC = 193 &getAnalysis<AssumptionCacheTracker>().getAssumptionCache(F); 194 OptimizationRemarkEmitter *ORE = 195 &getAnalysis<OptimizationRemarkEmitterWrapperPass>().getORE(); 196 const TargetTransformInfo *TTI = 197 &getAnalysis<TargetTransformInfoWrapperPass>().getTTI(F); 198 199 LoopDataPrefetch LDP(AC, LI, SE, TTI, ORE); 200 return LDP.run(); 201 } 202 203 bool LoopDataPrefetch::run() { 204 // If PrefetchDistance is not set, don't run the pass. This gives an 205 // opportunity for targets to run this pass for selected subtargets only 206 // (whose TTI sets PrefetchDistance). 207 if (getPrefetchDistance() == 0) 208 return false; 209 assert(TTI->getCacheLineSize() && "Cache line size is not set for target"); 210 211 bool MadeChange = false; 212 213 for (Loop *I : *LI) 214 for (auto L = df_begin(I), LE = df_end(I); L != LE; ++L) 215 MadeChange |= runOnLoop(*L); 216 217 return MadeChange; 218 } 219 220 bool LoopDataPrefetch::runOnLoop(Loop *L) { 221 bool MadeChange = false; 222 223 // Only prefetch in the inner-most loop 224 if (!L->empty()) 225 return MadeChange; 226 227 SmallPtrSet<const Value *, 32> EphValues; 228 CodeMetrics::collectEphemeralValues(L, AC, EphValues); 229 230 // Calculate the number of iterations ahead to prefetch 231 CodeMetrics Metrics; 232 for (const auto BB : L->blocks()) { 233 // If the loop already has prefetches, then assume that the user knows 234 // what they are doing and don't add any more. 235 for (auto &I : *BB) 236 if (CallInst *CI = dyn_cast<CallInst>(&I)) 237 if (Function *F = CI->getCalledFunction()) 238 if (F->getIntrinsicID() == Intrinsic::prefetch) 239 return MadeChange; 240 241 Metrics.analyzeBasicBlock(BB, *TTI, EphValues); 242 } 243 unsigned LoopSize = Metrics.NumInsts; 244 if (!LoopSize) 245 LoopSize = 1; 246 247 unsigned ItersAhead = getPrefetchDistance() / LoopSize; 248 if (!ItersAhead) 249 ItersAhead = 1; 250 251 if (ItersAhead > getMaxPrefetchIterationsAhead()) 252 return MadeChange; 253 254 DEBUG(dbgs() << "Prefetching " << ItersAhead 255 << " iterations ahead (loop size: " << LoopSize << ") in " 256 << L->getHeader()->getParent()->getName() << ": " << *L); 257 258 SmallVector<std::pair<Instruction *, const SCEVAddRecExpr *>, 16> PrefLoads; 259 for (const auto BB : L->blocks()) { 260 for (auto &I : *BB) { 261 Value *PtrValue; 262 Instruction *MemI; 263 264 if (LoadInst *LMemI = dyn_cast<LoadInst>(&I)) { 265 MemI = LMemI; 266 PtrValue = LMemI->getPointerOperand(); 267 } else if (StoreInst *SMemI = dyn_cast<StoreInst>(&I)) { 268 if (!PrefetchWrites) continue; 269 MemI = SMemI; 270 PtrValue = SMemI->getPointerOperand(); 271 } else continue; 272 273 unsigned PtrAddrSpace = PtrValue->getType()->getPointerAddressSpace(); 274 if (PtrAddrSpace) 275 continue; 276 277 if (L->isLoopInvariant(PtrValue)) 278 continue; 279 280 const SCEV *LSCEV = SE->getSCEV(PtrValue); 281 const SCEVAddRecExpr *LSCEVAddRec = dyn_cast<SCEVAddRecExpr>(LSCEV); 282 if (!LSCEVAddRec) 283 continue; 284 285 // Check if the the stride of the accesses is large enough to warrant a 286 // prefetch. 287 if (!isStrideLargeEnough(LSCEVAddRec)) 288 continue; 289 290 // We don't want to double prefetch individual cache lines. If this load 291 // is known to be within one cache line of some other load that has 292 // already been prefetched, then don't prefetch this one as well. 293 bool DupPref = false; 294 for (const auto &PrefLoad : PrefLoads) { 295 const SCEV *PtrDiff = SE->getMinusSCEV(LSCEVAddRec, PrefLoad.second); 296 if (const SCEVConstant *ConstPtrDiff = 297 dyn_cast<SCEVConstant>(PtrDiff)) { 298 int64_t PD = std::abs(ConstPtrDiff->getValue()->getSExtValue()); 299 if (PD < (int64_t) TTI->getCacheLineSize()) { 300 DupPref = true; 301 break; 302 } 303 } 304 } 305 if (DupPref) 306 continue; 307 308 const SCEV *NextLSCEV = SE->getAddExpr(LSCEVAddRec, SE->getMulExpr( 309 SE->getConstant(LSCEVAddRec->getType(), ItersAhead), 310 LSCEVAddRec->getStepRecurrence(*SE))); 311 if (!isSafeToExpand(NextLSCEV, *SE)) 312 continue; 313 314 PrefLoads.push_back(std::make_pair(MemI, LSCEVAddRec)); 315 316 Type *I8Ptr = Type::getInt8PtrTy(BB->getContext(), PtrAddrSpace); 317 SCEVExpander SCEVE(*SE, I.getModule()->getDataLayout(), "prefaddr"); 318 Value *PrefPtrValue = SCEVE.expandCodeFor(NextLSCEV, I8Ptr, MemI); 319 320 IRBuilder<> Builder(MemI); 321 Module *M = BB->getParent()->getParent(); 322 Type *I32 = Type::getInt32Ty(BB->getContext()); 323 Value *PrefetchFunc = Intrinsic::getDeclaration(M, Intrinsic::prefetch); 324 Builder.CreateCall( 325 PrefetchFunc, 326 {PrefPtrValue, 327 ConstantInt::get(I32, MemI->mayReadFromMemory() ? 0 : 1), 328 ConstantInt::get(I32, 3), ConstantInt::get(I32, 1)}); 329 ++NumPrefetches; 330 DEBUG(dbgs() << " Access: " << *PtrValue << ", SCEV: " << *LSCEV 331 << "\n"); 332 ORE->emit(OptimizationRemark(DEBUG_TYPE, "Prefetched", MemI) 333 << "prefetched memory access"); 334 335 MadeChange = true; 336 } 337 } 338 339 return MadeChange; 340 } 341 342