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 =
163 F.getContext().getLibraryOptions().get<ScalarOptions>();
164 LoopDataPrefetch LDP(Opts, AC, DT, LI, SE, TTI, ORE);
165 bool Changed = LDP.run();
166
167 if (Changed) {
168 PreservedAnalyses PA;
169 PA.preserve<DominatorTreeAnalysis>();
170 PA.preserve<LoopAnalysis>();
171 return PA;
172 }
173
174 return PreservedAnalyses::all();
175}
176
177bool LoopDataPrefetchLegacyPass::runOnFunction(Function &F) {
178 if (skipFunction(F))
179 return false;
180
181 DominatorTree *DT = &getAnalysis<DominatorTreeWrapperPass>().getDomTree();
182 LoopInfo *LI = &getAnalysis<LoopInfoWrapperPass>().getLoopInfo();
183 ScalarEvolution *SE = &getAnalysis<ScalarEvolutionWrapperPass>().getSE();
184 AssumptionCache *AC =
185 &getAnalysis<AssumptionCacheTracker>().getAssumptionCache(F);
186 OptimizationRemarkEmitter *ORE =
187 &getAnalysis<OptimizationRemarkEmitterWrapperPass>().getORE();
188 const TargetTransformInfo *TTI =
189 &getAnalysis<TargetTransformInfoWrapperPass>().getTTI(F);
190
191 const ScalarOptions &Opts =
192 F.getContext().getLibraryOptions().get<ScalarOptions>();
193 LoopDataPrefetch LDP(Opts, AC, DT, LI, SE, TTI, ORE);
194 return LDP.run();
195}
196
197bool LoopDataPrefetch::run() {
198 // If PrefetchDistance is not set, don't run the pass. This gives an
199 // opportunity for targets to run this pass for selected subtargets only
200 // (whose TTI sets PrefetchDistance and CacheLineSize).
201 if (getPrefetchDistance() == 0 || TTI->getCacheLineSize() == 0) {
202 LLVM_DEBUG(dbgs() << "Please set both PrefetchDistance and CacheLineSize "
203 "for loop data prefetch.\n");
204 return false;
205 }
206
207 bool MadeChange = false;
208
209 for (Loop *I : *LI)
210 for (Loop *L : depth_first(G: I))
211 MadeChange |= runOnLoop(L);
212
213 return MadeChange;
214}
215
216/// A record for a potential prefetch made during the initial scan of the
217/// loop. This is used to let a single prefetch target multiple memory accesses.
218struct Prefetch {
219 /// The address formula for this prefetch as returned by ScalarEvolution.
220 const SCEVAddRecExpr *LSCEVAddRec;
221 /// The point of insertion for the prefetch instruction.
222 Instruction *InsertPt = nullptr;
223 /// True if targeting a write memory access.
224 bool Writes = false;
225 /// The (first seen) prefetched instruction.
226 Instruction *MemI = nullptr;
227
228 /// Constructor to create a new Prefetch for \p I.
229 Prefetch(const SCEVAddRecExpr *L, Instruction *I) : LSCEVAddRec(L) {
230 addInstruction(I);
231 };
232
233 /// Add the instruction \param I to this prefetch. If it's not the first
234 /// one, 'InsertPt' and 'Writes' will be updated as required.
235 /// \param PtrDiff the known constant address difference to the first added
236 /// instruction.
237 void addInstruction(Instruction *I, DominatorTree *DT = nullptr,
238 int64_t PtrDiff = 0) {
239 if (!InsertPt) {
240 MemI = I;
241 InsertPt = I;
242 Writes = isa<StoreInst>(Val: I);
243 } else {
244 BasicBlock *PrefBB = InsertPt->getParent();
245 BasicBlock *InsBB = I->getParent();
246 if (PrefBB != InsBB) {
247 BasicBlock *DomBB = DT->findNearestCommonDominator(A: PrefBB, B: InsBB);
248 if (DomBB != PrefBB)
249 InsertPt = DomBB->getTerminator();
250 }
251
252 if (isa<StoreInst>(Val: I) && PtrDiff == 0)
253 Writes = true;
254 }
255 }
256};
257
258bool LoopDataPrefetch::runOnLoop(Loop *L) {
259 bool MadeChange = false;
260
261 // Only prefetch in the inner-most loop
262 if (!L->isInnermost())
263 return MadeChange;
264
265 SmallPtrSet<const Value *, 32> EphValues;
266 CodeMetrics::collectEphemeralValues(L, AC, EphValues);
267
268 // Calculate the number of iterations ahead to prefetch
269 CodeMetrics Metrics;
270 bool HasCall = false;
271 for (const auto BB : L->blocks()) {
272 // If the loop already has prefetches, then assume that the user knows
273 // what they are doing and don't add any more.
274 for (auto &I : *BB) {
275 if (isa<CallInst>(Val: &I) || isa<InvokeInst>(Val: &I)) {
276 if (const Function *F = cast<CallBase>(Val&: I).getCalledFunction()) {
277 if (F->getIntrinsicID() == Intrinsic::prefetch)
278 return MadeChange;
279 if (TTI->isLoweredToCall(F))
280 HasCall = true;
281 } else { // indirect call.
282 HasCall = true;
283 }
284 }
285 }
286 Metrics.analyzeBasicBlock(BB, TTI: *TTI, EphValues);
287 }
288
289 if (!Metrics.NumInsts.isValid())
290 return MadeChange;
291
292 unsigned LoopSize = Metrics.NumInsts.getValue();
293 if (!LoopSize)
294 LoopSize = 1;
295
296 unsigned ItersAhead = getPrefetchDistance() / LoopSize;
297 if (!ItersAhead)
298 ItersAhead = 1;
299
300 if (ItersAhead > getMaxPrefetchIterationsAhead())
301 return MadeChange;
302
303 unsigned ConstantMaxTripCount = SE->getSmallConstantMaxTripCount(L);
304 if (ConstantMaxTripCount && ConstantMaxTripCount < ItersAhead + 1)
305 return MadeChange;
306
307 unsigned NumMemAccesses = 0;
308 unsigned NumStridedMemAccesses = 0;
309 SmallVector<Prefetch, 16> Prefetches;
310 for (const auto BB : L->blocks())
311 for (auto &I : *BB) {
312 Value *PtrValue;
313 Instruction *MemI;
314
315 if (LoadInst *LMemI = dyn_cast<LoadInst>(Val: &I)) {
316 MemI = LMemI;
317 PtrValue = LMemI->getPointerOperand();
318 } else if (StoreInst *SMemI = dyn_cast<StoreInst>(Val: &I)) {
319 if (!doPrefetchWrites()) continue;
320 MemI = SMemI;
321 PtrValue = SMemI->getPointerOperand();
322 } else continue;
323
324 unsigned PtrAddrSpace = PtrValue->getType()->getPointerAddressSpace();
325 if (!TTI->shouldPrefetchAddressSpace(AS: PtrAddrSpace))
326 continue;
327 NumMemAccesses++;
328 if (L->isLoopInvariant(V: PtrValue))
329 continue;
330
331 const SCEV *LSCEV = SE->getSCEV(V: PtrValue);
332 const SCEVAddRecExpr *LSCEVAddRec = dyn_cast<SCEVAddRecExpr>(Val: LSCEV);
333 if (!LSCEVAddRec)
334 continue;
335 NumStridedMemAccesses++;
336
337 // We don't want to double prefetch individual cache lines. If this
338 // access is known to be within one cache line of some other one that
339 // has already been prefetched, then don't prefetch this one as well.
340 bool DupPref = false;
341 for (auto &Pref : Prefetches) {
342 const SCEV *PtrDiff = SE->getMinusSCEV(LHS: LSCEVAddRec, RHS: Pref.LSCEVAddRec);
343 if (const SCEVConstant *ConstPtrDiff =
344 dyn_cast<SCEVConstant>(Val: PtrDiff)) {
345 int64_t PD = std::abs(i: ConstPtrDiff->getValue()->getSExtValue());
346 if (PD < (int64_t) TTI->getCacheLineSize()) {
347 Pref.addInstruction(I: MemI, DT, PtrDiff: PD);
348 DupPref = true;
349 break;
350 }
351 }
352 }
353 if (!DupPref)
354 Prefetches.push_back(Elt: Prefetch(LSCEVAddRec, MemI));
355 }
356
357 unsigned TargetMinStride =
358 getMinPrefetchStride(NumMemAccesses, NumStridedMemAccesses,
359 NumPrefetches: Prefetches.size(), HasCall);
360
361 LLVM_DEBUG(dbgs() << "Prefetching " << ItersAhead
362 << " iterations ahead (loop size: " << LoopSize << ") in "
363 << L->getHeader()->getParent()->getName() << ": " << *L);
364 LLVM_DEBUG(dbgs() << "Loop has: "
365 << NumMemAccesses << " memory accesses, "
366 << NumStridedMemAccesses << " strided memory accesses, "
367 << Prefetches.size() << " potential prefetch(es), "
368 << "a minimum stride of " << TargetMinStride << ", "
369 << (HasCall ? "calls" : "no calls") << ".\n");
370
371 for (auto &P : Prefetches) {
372 // Check if the stride of the accesses is large enough to warrant a
373 // prefetch.
374 if (!isStrideLargeEnough(AR: P.LSCEVAddRec, TargetMinStride))
375 continue;
376
377 BasicBlock *BB = P.InsertPt->getParent();
378 SCEVExpander SCEVE(*SE, "prefaddr");
379 const SCEV *NextLSCEV = SE->getAddExpr(
380 LHS: P.LSCEVAddRec,
381 RHS: SE->getMulExpr(LHS: SE->getConstant(Ty: P.LSCEVAddRec->getType(), V: ItersAhead),
382 RHS: P.LSCEVAddRec->getStepRecurrence(SE&: *SE)));
383 if (!SCEVE.isSafeToExpand(S: NextLSCEV))
384 continue;
385
386 unsigned PtrAddrSpace = NextLSCEV->getType()->getPointerAddressSpace();
387 Type *I8Ptr = PointerType::get(C&: BB->getContext(), AddressSpace: PtrAddrSpace);
388 Value *PrefPtrValue = SCEVE.expandCodeFor(SH: NextLSCEV, Ty: I8Ptr, I: P.InsertPt);
389
390 IRBuilder<> Builder(P.InsertPt);
391 Type *I32 = Type::getInt32Ty(C&: BB->getContext());
392 Builder.CreateIntrinsic(ID: Intrinsic::prefetch, OverloadTypes: PrefPtrValue->getType(),
393 Args: {PrefPtrValue, ConstantInt::get(Ty: I32, V: P.Writes),
394 ConstantInt::get(Ty: I32, V: 3),
395 ConstantInt::get(Ty: I32, V: 1)});
396 ++NumPrefetches;
397 LLVM_DEBUG(dbgs() << " Access: "
398 << *P.MemI->getOperand(isa<LoadInst>(P.MemI) ? 0 : 1)
399 << ", SCEV: " << *P.LSCEVAddRec << "\n");
400 ORE->emit(RemarkBuilder: [&]() {
401 return OptimizationRemark(DEBUG_TYPE, "Prefetched", P.MemI)
402 << "prefetched memory access";
403 });
404
405 MadeChange = true;
406 }
407
408 return MadeChange;
409}
410