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