106f32e7eSjoerg //===-------- LoopDataPrefetch.cpp - Loop Data Prefetching Pass -----------===//
206f32e7eSjoerg //
306f32e7eSjoerg // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
406f32e7eSjoerg // See https://llvm.org/LICENSE.txt for license information.
506f32e7eSjoerg // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
606f32e7eSjoerg //
706f32e7eSjoerg //===----------------------------------------------------------------------===//
806f32e7eSjoerg //
906f32e7eSjoerg // This file implements a Loop Data Prefetching Pass.
1006f32e7eSjoerg //
1106f32e7eSjoerg //===----------------------------------------------------------------------===//
1206f32e7eSjoerg
1306f32e7eSjoerg #include "llvm/Transforms/Scalar/LoopDataPrefetch.h"
14*da58b97aSjoerg #include "llvm/InitializePasses.h"
1506f32e7eSjoerg
1606f32e7eSjoerg #define DEBUG_TYPE "loop-data-prefetch"
1706f32e7eSjoerg #include "llvm/ADT/DepthFirstIterator.h"
1806f32e7eSjoerg #include "llvm/ADT/Statistic.h"
1906f32e7eSjoerg #include "llvm/Analysis/AssumptionCache.h"
2006f32e7eSjoerg #include "llvm/Analysis/CodeMetrics.h"
2106f32e7eSjoerg #include "llvm/Analysis/LoopInfo.h"
2206f32e7eSjoerg #include "llvm/Analysis/OptimizationRemarkEmitter.h"
2306f32e7eSjoerg #include "llvm/Analysis/ScalarEvolution.h"
2406f32e7eSjoerg #include "llvm/Analysis/ScalarEvolutionExpressions.h"
2506f32e7eSjoerg #include "llvm/Analysis/TargetTransformInfo.h"
2606f32e7eSjoerg #include "llvm/IR/CFG.h"
2706f32e7eSjoerg #include "llvm/IR/Dominators.h"
2806f32e7eSjoerg #include "llvm/IR/Function.h"
2906f32e7eSjoerg #include "llvm/IR/Module.h"
3006f32e7eSjoerg #include "llvm/Support/CommandLine.h"
3106f32e7eSjoerg #include "llvm/Support/Debug.h"
3206f32e7eSjoerg #include "llvm/Transforms/Scalar.h"
3306f32e7eSjoerg #include "llvm/Transforms/Utils/BasicBlockUtils.h"
34*da58b97aSjoerg #include "llvm/Transforms/Utils/ScalarEvolutionExpander.h"
3506f32e7eSjoerg #include "llvm/Transforms/Utils/ValueMapper.h"
3606f32e7eSjoerg using namespace llvm;
3706f32e7eSjoerg
3806f32e7eSjoerg // By default, we limit this to creating 16 PHIs (which is a little over half
3906f32e7eSjoerg // of the allocatable register set).
4006f32e7eSjoerg static cl::opt<bool>
4106f32e7eSjoerg PrefetchWrites("loop-prefetch-writes", cl::Hidden, cl::init(false),
4206f32e7eSjoerg cl::desc("Prefetch write addresses"));
4306f32e7eSjoerg
4406f32e7eSjoerg static cl::opt<unsigned>
4506f32e7eSjoerg PrefetchDistance("prefetch-distance",
4606f32e7eSjoerg cl::desc("Number of instructions to prefetch ahead"),
4706f32e7eSjoerg cl::Hidden);
4806f32e7eSjoerg
4906f32e7eSjoerg static cl::opt<unsigned>
5006f32e7eSjoerg MinPrefetchStride("min-prefetch-stride",
5106f32e7eSjoerg cl::desc("Min stride to add prefetches"), cl::Hidden);
5206f32e7eSjoerg
5306f32e7eSjoerg static cl::opt<unsigned> MaxPrefetchIterationsAhead(
5406f32e7eSjoerg "max-prefetch-iters-ahead",
5506f32e7eSjoerg cl::desc("Max number of iterations to prefetch ahead"), cl::Hidden);
5606f32e7eSjoerg
5706f32e7eSjoerg STATISTIC(NumPrefetches, "Number of prefetches inserted");
5806f32e7eSjoerg
5906f32e7eSjoerg namespace {
6006f32e7eSjoerg
6106f32e7eSjoerg /// Loop prefetch implementation class.
6206f32e7eSjoerg class LoopDataPrefetch {
6306f32e7eSjoerg public:
LoopDataPrefetch(AssumptionCache * AC,DominatorTree * DT,LoopInfo * LI,ScalarEvolution * SE,const TargetTransformInfo * TTI,OptimizationRemarkEmitter * ORE)64*da58b97aSjoerg LoopDataPrefetch(AssumptionCache *AC, DominatorTree *DT, LoopInfo *LI,
65*da58b97aSjoerg ScalarEvolution *SE, const TargetTransformInfo *TTI,
6606f32e7eSjoerg OptimizationRemarkEmitter *ORE)
67*da58b97aSjoerg : AC(AC), DT(DT), LI(LI), SE(SE), TTI(TTI), ORE(ORE) {}
6806f32e7eSjoerg
6906f32e7eSjoerg bool run();
7006f32e7eSjoerg
7106f32e7eSjoerg private:
7206f32e7eSjoerg bool runOnLoop(Loop *L);
7306f32e7eSjoerg
7406f32e7eSjoerg /// Check if the stride of the accesses is large enough to
7506f32e7eSjoerg /// warrant a prefetch.
76*da58b97aSjoerg bool isStrideLargeEnough(const SCEVAddRecExpr *AR, unsigned TargetMinStride);
7706f32e7eSjoerg
getMinPrefetchStride(unsigned NumMemAccesses,unsigned NumStridedMemAccesses,unsigned NumPrefetches,bool HasCall)78*da58b97aSjoerg unsigned getMinPrefetchStride(unsigned NumMemAccesses,
79*da58b97aSjoerg unsigned NumStridedMemAccesses,
80*da58b97aSjoerg unsigned NumPrefetches,
81*da58b97aSjoerg bool HasCall) {
8206f32e7eSjoerg if (MinPrefetchStride.getNumOccurrences() > 0)
8306f32e7eSjoerg return MinPrefetchStride;
84*da58b97aSjoerg return TTI->getMinPrefetchStride(NumMemAccesses, NumStridedMemAccesses,
85*da58b97aSjoerg NumPrefetches, HasCall);
8606f32e7eSjoerg }
8706f32e7eSjoerg
getPrefetchDistance()8806f32e7eSjoerg unsigned getPrefetchDistance() {
8906f32e7eSjoerg if (PrefetchDistance.getNumOccurrences() > 0)
9006f32e7eSjoerg return PrefetchDistance;
9106f32e7eSjoerg return TTI->getPrefetchDistance();
9206f32e7eSjoerg }
9306f32e7eSjoerg
getMaxPrefetchIterationsAhead()9406f32e7eSjoerg unsigned getMaxPrefetchIterationsAhead() {
9506f32e7eSjoerg if (MaxPrefetchIterationsAhead.getNumOccurrences() > 0)
9606f32e7eSjoerg return MaxPrefetchIterationsAhead;
9706f32e7eSjoerg return TTI->getMaxPrefetchIterationsAhead();
9806f32e7eSjoerg }
9906f32e7eSjoerg
doPrefetchWrites()100*da58b97aSjoerg bool doPrefetchWrites() {
101*da58b97aSjoerg if (PrefetchWrites.getNumOccurrences() > 0)
102*da58b97aSjoerg return PrefetchWrites;
103*da58b97aSjoerg return TTI->enableWritePrefetching();
104*da58b97aSjoerg }
105*da58b97aSjoerg
10606f32e7eSjoerg AssumptionCache *AC;
107*da58b97aSjoerg DominatorTree *DT;
10806f32e7eSjoerg LoopInfo *LI;
10906f32e7eSjoerg ScalarEvolution *SE;
11006f32e7eSjoerg const TargetTransformInfo *TTI;
11106f32e7eSjoerg OptimizationRemarkEmitter *ORE;
11206f32e7eSjoerg };
11306f32e7eSjoerg
11406f32e7eSjoerg /// Legacy class for inserting loop data prefetches.
11506f32e7eSjoerg class LoopDataPrefetchLegacyPass : public FunctionPass {
11606f32e7eSjoerg public:
11706f32e7eSjoerg static char ID; // Pass ID, replacement for typeid
LoopDataPrefetchLegacyPass()11806f32e7eSjoerg LoopDataPrefetchLegacyPass() : FunctionPass(ID) {
11906f32e7eSjoerg initializeLoopDataPrefetchLegacyPassPass(*PassRegistry::getPassRegistry());
12006f32e7eSjoerg }
12106f32e7eSjoerg
getAnalysisUsage(AnalysisUsage & AU) const12206f32e7eSjoerg void getAnalysisUsage(AnalysisUsage &AU) const override {
12306f32e7eSjoerg AU.addRequired<AssumptionCacheTracker>();
124*da58b97aSjoerg AU.addRequired<DominatorTreeWrapperPass>();
12506f32e7eSjoerg AU.addPreserved<DominatorTreeWrapperPass>();
12606f32e7eSjoerg AU.addRequired<LoopInfoWrapperPass>();
12706f32e7eSjoerg AU.addPreserved<LoopInfoWrapperPass>();
12806f32e7eSjoerg AU.addRequired<OptimizationRemarkEmitterWrapperPass>();
12906f32e7eSjoerg AU.addRequired<ScalarEvolutionWrapperPass>();
13006f32e7eSjoerg AU.addPreserved<ScalarEvolutionWrapperPass>();
13106f32e7eSjoerg AU.addRequired<TargetTransformInfoWrapperPass>();
13206f32e7eSjoerg }
13306f32e7eSjoerg
13406f32e7eSjoerg bool runOnFunction(Function &F) override;
13506f32e7eSjoerg };
13606f32e7eSjoerg }
13706f32e7eSjoerg
13806f32e7eSjoerg char LoopDataPrefetchLegacyPass::ID = 0;
13906f32e7eSjoerg INITIALIZE_PASS_BEGIN(LoopDataPrefetchLegacyPass, "loop-data-prefetch",
14006f32e7eSjoerg "Loop Data Prefetch", false, false)
INITIALIZE_PASS_DEPENDENCY(AssumptionCacheTracker)14106f32e7eSjoerg INITIALIZE_PASS_DEPENDENCY(AssumptionCacheTracker)
14206f32e7eSjoerg INITIALIZE_PASS_DEPENDENCY(TargetTransformInfoWrapperPass)
14306f32e7eSjoerg INITIALIZE_PASS_DEPENDENCY(LoopInfoWrapperPass)
14406f32e7eSjoerg INITIALIZE_PASS_DEPENDENCY(OptimizationRemarkEmitterWrapperPass)
14506f32e7eSjoerg INITIALIZE_PASS_DEPENDENCY(ScalarEvolutionWrapperPass)
14606f32e7eSjoerg INITIALIZE_PASS_END(LoopDataPrefetchLegacyPass, "loop-data-prefetch",
14706f32e7eSjoerg "Loop Data Prefetch", false, false)
14806f32e7eSjoerg
14906f32e7eSjoerg FunctionPass *llvm::createLoopDataPrefetchPass() {
15006f32e7eSjoerg return new LoopDataPrefetchLegacyPass();
15106f32e7eSjoerg }
15206f32e7eSjoerg
isStrideLargeEnough(const SCEVAddRecExpr * AR,unsigned TargetMinStride)153*da58b97aSjoerg bool LoopDataPrefetch::isStrideLargeEnough(const SCEVAddRecExpr *AR,
154*da58b97aSjoerg unsigned TargetMinStride) {
15506f32e7eSjoerg // No need to check if any stride goes.
15606f32e7eSjoerg if (TargetMinStride <= 1)
15706f32e7eSjoerg return true;
15806f32e7eSjoerg
15906f32e7eSjoerg const auto *ConstStride = dyn_cast<SCEVConstant>(AR->getStepRecurrence(*SE));
16006f32e7eSjoerg // If MinStride is set, don't prefetch unless we can ensure that stride is
16106f32e7eSjoerg // larger.
16206f32e7eSjoerg if (!ConstStride)
16306f32e7eSjoerg return false;
16406f32e7eSjoerg
16506f32e7eSjoerg unsigned AbsStride = std::abs(ConstStride->getAPInt().getSExtValue());
16606f32e7eSjoerg return TargetMinStride <= AbsStride;
16706f32e7eSjoerg }
16806f32e7eSjoerg
run(Function & F,FunctionAnalysisManager & AM)16906f32e7eSjoerg PreservedAnalyses LoopDataPrefetchPass::run(Function &F,
17006f32e7eSjoerg FunctionAnalysisManager &AM) {
171*da58b97aSjoerg DominatorTree *DT = &AM.getResult<DominatorTreeAnalysis>(F);
17206f32e7eSjoerg LoopInfo *LI = &AM.getResult<LoopAnalysis>(F);
17306f32e7eSjoerg ScalarEvolution *SE = &AM.getResult<ScalarEvolutionAnalysis>(F);
17406f32e7eSjoerg AssumptionCache *AC = &AM.getResult<AssumptionAnalysis>(F);
17506f32e7eSjoerg OptimizationRemarkEmitter *ORE =
17606f32e7eSjoerg &AM.getResult<OptimizationRemarkEmitterAnalysis>(F);
17706f32e7eSjoerg const TargetTransformInfo *TTI = &AM.getResult<TargetIRAnalysis>(F);
17806f32e7eSjoerg
179*da58b97aSjoerg LoopDataPrefetch LDP(AC, DT, LI, SE, TTI, ORE);
18006f32e7eSjoerg bool Changed = LDP.run();
18106f32e7eSjoerg
18206f32e7eSjoerg if (Changed) {
18306f32e7eSjoerg PreservedAnalyses PA;
18406f32e7eSjoerg PA.preserve<DominatorTreeAnalysis>();
18506f32e7eSjoerg PA.preserve<LoopAnalysis>();
18606f32e7eSjoerg return PA;
18706f32e7eSjoerg }
18806f32e7eSjoerg
18906f32e7eSjoerg return PreservedAnalyses::all();
19006f32e7eSjoerg }
19106f32e7eSjoerg
runOnFunction(Function & F)19206f32e7eSjoerg bool LoopDataPrefetchLegacyPass::runOnFunction(Function &F) {
19306f32e7eSjoerg if (skipFunction(F))
19406f32e7eSjoerg return false;
19506f32e7eSjoerg
196*da58b97aSjoerg DominatorTree *DT = &getAnalysis<DominatorTreeWrapperPass>().getDomTree();
19706f32e7eSjoerg LoopInfo *LI = &getAnalysis<LoopInfoWrapperPass>().getLoopInfo();
19806f32e7eSjoerg ScalarEvolution *SE = &getAnalysis<ScalarEvolutionWrapperPass>().getSE();
19906f32e7eSjoerg AssumptionCache *AC =
20006f32e7eSjoerg &getAnalysis<AssumptionCacheTracker>().getAssumptionCache(F);
20106f32e7eSjoerg OptimizationRemarkEmitter *ORE =
20206f32e7eSjoerg &getAnalysis<OptimizationRemarkEmitterWrapperPass>().getORE();
20306f32e7eSjoerg const TargetTransformInfo *TTI =
20406f32e7eSjoerg &getAnalysis<TargetTransformInfoWrapperPass>().getTTI(F);
20506f32e7eSjoerg
206*da58b97aSjoerg LoopDataPrefetch LDP(AC, DT, LI, SE, TTI, ORE);
20706f32e7eSjoerg return LDP.run();
20806f32e7eSjoerg }
20906f32e7eSjoerg
run()21006f32e7eSjoerg bool LoopDataPrefetch::run() {
21106f32e7eSjoerg // If PrefetchDistance is not set, don't run the pass. This gives an
21206f32e7eSjoerg // opportunity for targets to run this pass for selected subtargets only
21306f32e7eSjoerg // (whose TTI sets PrefetchDistance).
21406f32e7eSjoerg if (getPrefetchDistance() == 0)
21506f32e7eSjoerg return false;
21606f32e7eSjoerg assert(TTI->getCacheLineSize() && "Cache line size is not set for target");
21706f32e7eSjoerg
21806f32e7eSjoerg bool MadeChange = false;
21906f32e7eSjoerg
22006f32e7eSjoerg for (Loop *I : *LI)
22106f32e7eSjoerg for (auto L = df_begin(I), LE = df_end(I); L != LE; ++L)
22206f32e7eSjoerg MadeChange |= runOnLoop(*L);
22306f32e7eSjoerg
22406f32e7eSjoerg return MadeChange;
22506f32e7eSjoerg }
22606f32e7eSjoerg
227*da58b97aSjoerg /// A record for a potential prefetch made during the initial scan of the
228*da58b97aSjoerg /// loop. This is used to let a single prefetch target multiple memory accesses.
229*da58b97aSjoerg struct Prefetch {
230*da58b97aSjoerg /// The address formula for this prefetch as returned by ScalarEvolution.
231*da58b97aSjoerg const SCEVAddRecExpr *LSCEVAddRec;
232*da58b97aSjoerg /// The point of insertion for the prefetch instruction.
233*da58b97aSjoerg Instruction *InsertPt;
234*da58b97aSjoerg /// True if targeting a write memory access.
235*da58b97aSjoerg bool Writes;
236*da58b97aSjoerg /// The (first seen) prefetched instruction.
237*da58b97aSjoerg Instruction *MemI;
238*da58b97aSjoerg
239*da58b97aSjoerg /// Constructor to create a new Prefetch for \p I.
PrefetchPrefetch240*da58b97aSjoerg Prefetch(const SCEVAddRecExpr *L, Instruction *I)
241*da58b97aSjoerg : LSCEVAddRec(L), InsertPt(nullptr), Writes(false), MemI(nullptr) {
242*da58b97aSjoerg addInstruction(I);
243*da58b97aSjoerg };
244*da58b97aSjoerg
245*da58b97aSjoerg /// Add the instruction \param I to this prefetch. If it's not the first
246*da58b97aSjoerg /// one, 'InsertPt' and 'Writes' will be updated as required.
247*da58b97aSjoerg /// \param PtrDiff the known constant address difference to the first added
248*da58b97aSjoerg /// instruction.
addInstructionPrefetch249*da58b97aSjoerg void addInstruction(Instruction *I, DominatorTree *DT = nullptr,
250*da58b97aSjoerg int64_t PtrDiff = 0) {
251*da58b97aSjoerg if (!InsertPt) {
252*da58b97aSjoerg MemI = I;
253*da58b97aSjoerg InsertPt = I;
254*da58b97aSjoerg Writes = isa<StoreInst>(I);
255*da58b97aSjoerg } else {
256*da58b97aSjoerg BasicBlock *PrefBB = InsertPt->getParent();
257*da58b97aSjoerg BasicBlock *InsBB = I->getParent();
258*da58b97aSjoerg if (PrefBB != InsBB) {
259*da58b97aSjoerg BasicBlock *DomBB = DT->findNearestCommonDominator(PrefBB, InsBB);
260*da58b97aSjoerg if (DomBB != PrefBB)
261*da58b97aSjoerg InsertPt = DomBB->getTerminator();
262*da58b97aSjoerg }
263*da58b97aSjoerg
264*da58b97aSjoerg if (isa<StoreInst>(I) && PtrDiff == 0)
265*da58b97aSjoerg Writes = true;
266*da58b97aSjoerg }
267*da58b97aSjoerg }
268*da58b97aSjoerg };
269*da58b97aSjoerg
runOnLoop(Loop * L)27006f32e7eSjoerg bool LoopDataPrefetch::runOnLoop(Loop *L) {
27106f32e7eSjoerg bool MadeChange = false;
27206f32e7eSjoerg
27306f32e7eSjoerg // Only prefetch in the inner-most loop
274*da58b97aSjoerg if (!L->isInnermost())
27506f32e7eSjoerg return MadeChange;
27606f32e7eSjoerg
27706f32e7eSjoerg SmallPtrSet<const Value *, 32> EphValues;
27806f32e7eSjoerg CodeMetrics::collectEphemeralValues(L, AC, EphValues);
27906f32e7eSjoerg
28006f32e7eSjoerg // Calculate the number of iterations ahead to prefetch
28106f32e7eSjoerg CodeMetrics Metrics;
282*da58b97aSjoerg bool HasCall = false;
28306f32e7eSjoerg for (const auto BB : L->blocks()) {
28406f32e7eSjoerg // If the loop already has prefetches, then assume that the user knows
28506f32e7eSjoerg // what they are doing and don't add any more.
286*da58b97aSjoerg for (auto &I : *BB) {
287*da58b97aSjoerg if (isa<CallInst>(&I) || isa<InvokeInst>(&I)) {
288*da58b97aSjoerg if (const Function *F = cast<CallBase>(I).getCalledFunction()) {
28906f32e7eSjoerg if (F->getIntrinsicID() == Intrinsic::prefetch)
29006f32e7eSjoerg return MadeChange;
291*da58b97aSjoerg if (TTI->isLoweredToCall(F))
292*da58b97aSjoerg HasCall = true;
293*da58b97aSjoerg } else { // indirect call.
294*da58b97aSjoerg HasCall = true;
295*da58b97aSjoerg }
296*da58b97aSjoerg }
297*da58b97aSjoerg }
29806f32e7eSjoerg Metrics.analyzeBasicBlock(BB, *TTI, EphValues);
29906f32e7eSjoerg }
30006f32e7eSjoerg unsigned LoopSize = Metrics.NumInsts;
30106f32e7eSjoerg if (!LoopSize)
30206f32e7eSjoerg LoopSize = 1;
30306f32e7eSjoerg
30406f32e7eSjoerg unsigned ItersAhead = getPrefetchDistance() / LoopSize;
30506f32e7eSjoerg if (!ItersAhead)
30606f32e7eSjoerg ItersAhead = 1;
30706f32e7eSjoerg
30806f32e7eSjoerg if (ItersAhead > getMaxPrefetchIterationsAhead())
30906f32e7eSjoerg return MadeChange;
31006f32e7eSjoerg
311*da58b97aSjoerg unsigned ConstantMaxTripCount = SE->getSmallConstantMaxTripCount(L);
312*da58b97aSjoerg if (ConstantMaxTripCount && ConstantMaxTripCount < ItersAhead + 1)
313*da58b97aSjoerg return MadeChange;
31406f32e7eSjoerg
315*da58b97aSjoerg unsigned NumMemAccesses = 0;
316*da58b97aSjoerg unsigned NumStridedMemAccesses = 0;
317*da58b97aSjoerg SmallVector<Prefetch, 16> Prefetches;
318*da58b97aSjoerg for (const auto BB : L->blocks())
31906f32e7eSjoerg for (auto &I : *BB) {
32006f32e7eSjoerg Value *PtrValue;
32106f32e7eSjoerg Instruction *MemI;
32206f32e7eSjoerg
32306f32e7eSjoerg if (LoadInst *LMemI = dyn_cast<LoadInst>(&I)) {
32406f32e7eSjoerg MemI = LMemI;
32506f32e7eSjoerg PtrValue = LMemI->getPointerOperand();
32606f32e7eSjoerg } else if (StoreInst *SMemI = dyn_cast<StoreInst>(&I)) {
327*da58b97aSjoerg if (!doPrefetchWrites()) continue;
32806f32e7eSjoerg MemI = SMemI;
32906f32e7eSjoerg PtrValue = SMemI->getPointerOperand();
33006f32e7eSjoerg } else continue;
33106f32e7eSjoerg
33206f32e7eSjoerg unsigned PtrAddrSpace = PtrValue->getType()->getPointerAddressSpace();
33306f32e7eSjoerg if (PtrAddrSpace)
33406f32e7eSjoerg continue;
335*da58b97aSjoerg NumMemAccesses++;
33606f32e7eSjoerg if (L->isLoopInvariant(PtrValue))
33706f32e7eSjoerg continue;
33806f32e7eSjoerg
33906f32e7eSjoerg const SCEV *LSCEV = SE->getSCEV(PtrValue);
34006f32e7eSjoerg const SCEVAddRecExpr *LSCEVAddRec = dyn_cast<SCEVAddRecExpr>(LSCEV);
34106f32e7eSjoerg if (!LSCEVAddRec)
34206f32e7eSjoerg continue;
343*da58b97aSjoerg NumStridedMemAccesses++;
34406f32e7eSjoerg
345*da58b97aSjoerg // We don't want to double prefetch individual cache lines. If this
346*da58b97aSjoerg // access is known to be within one cache line of some other one that
347*da58b97aSjoerg // has already been prefetched, then don't prefetch this one as well.
34806f32e7eSjoerg bool DupPref = false;
349*da58b97aSjoerg for (auto &Pref : Prefetches) {
350*da58b97aSjoerg const SCEV *PtrDiff = SE->getMinusSCEV(LSCEVAddRec, Pref.LSCEVAddRec);
35106f32e7eSjoerg if (const SCEVConstant *ConstPtrDiff =
35206f32e7eSjoerg dyn_cast<SCEVConstant>(PtrDiff)) {
35306f32e7eSjoerg int64_t PD = std::abs(ConstPtrDiff->getValue()->getSExtValue());
35406f32e7eSjoerg if (PD < (int64_t) TTI->getCacheLineSize()) {
355*da58b97aSjoerg Pref.addInstruction(MemI, DT, PD);
35606f32e7eSjoerg DupPref = true;
35706f32e7eSjoerg break;
35806f32e7eSjoerg }
35906f32e7eSjoerg }
36006f32e7eSjoerg }
361*da58b97aSjoerg if (!DupPref)
362*da58b97aSjoerg Prefetches.push_back(Prefetch(LSCEVAddRec, MemI));
363*da58b97aSjoerg }
364*da58b97aSjoerg
365*da58b97aSjoerg unsigned TargetMinStride =
366*da58b97aSjoerg getMinPrefetchStride(NumMemAccesses, NumStridedMemAccesses,
367*da58b97aSjoerg Prefetches.size(), HasCall);
368*da58b97aSjoerg
369*da58b97aSjoerg LLVM_DEBUG(dbgs() << "Prefetching " << ItersAhead
370*da58b97aSjoerg << " iterations ahead (loop size: " << LoopSize << ") in "
371*da58b97aSjoerg << L->getHeader()->getParent()->getName() << ": " << *L);
372*da58b97aSjoerg LLVM_DEBUG(dbgs() << "Loop has: "
373*da58b97aSjoerg << NumMemAccesses << " memory accesses, "
374*da58b97aSjoerg << NumStridedMemAccesses << " strided memory accesses, "
375*da58b97aSjoerg << Prefetches.size() << " potential prefetch(es), "
376*da58b97aSjoerg << "a minimum stride of " << TargetMinStride << ", "
377*da58b97aSjoerg << (HasCall ? "calls" : "no calls") << ".\n");
378*da58b97aSjoerg
379*da58b97aSjoerg for (auto &P : Prefetches) {
380*da58b97aSjoerg // Check if the stride of the accesses is large enough to warrant a
381*da58b97aSjoerg // prefetch.
382*da58b97aSjoerg if (!isStrideLargeEnough(P.LSCEVAddRec, TargetMinStride))
38306f32e7eSjoerg continue;
38406f32e7eSjoerg
385*da58b97aSjoerg const SCEV *NextLSCEV = SE->getAddExpr(P.LSCEVAddRec, SE->getMulExpr(
386*da58b97aSjoerg SE->getConstant(P.LSCEVAddRec->getType(), ItersAhead),
387*da58b97aSjoerg P.LSCEVAddRec->getStepRecurrence(*SE)));
38806f32e7eSjoerg if (!isSafeToExpand(NextLSCEV, *SE))
38906f32e7eSjoerg continue;
39006f32e7eSjoerg
391*da58b97aSjoerg BasicBlock *BB = P.InsertPt->getParent();
392*da58b97aSjoerg Type *I8Ptr = Type::getInt8PtrTy(BB->getContext(), 0/*PtrAddrSpace*/);
393*da58b97aSjoerg SCEVExpander SCEVE(*SE, BB->getModule()->getDataLayout(), "prefaddr");
394*da58b97aSjoerg Value *PrefPtrValue = SCEVE.expandCodeFor(NextLSCEV, I8Ptr, P.InsertPt);
39506f32e7eSjoerg
396*da58b97aSjoerg IRBuilder<> Builder(P.InsertPt);
39706f32e7eSjoerg Module *M = BB->getParent()->getParent();
39806f32e7eSjoerg Type *I32 = Type::getInt32Ty(BB->getContext());
39906f32e7eSjoerg Function *PrefetchFunc = Intrinsic::getDeclaration(
40006f32e7eSjoerg M, Intrinsic::prefetch, PrefPtrValue->getType());
40106f32e7eSjoerg Builder.CreateCall(
40206f32e7eSjoerg PrefetchFunc,
40306f32e7eSjoerg {PrefPtrValue,
404*da58b97aSjoerg ConstantInt::get(I32, P.Writes),
40506f32e7eSjoerg ConstantInt::get(I32, 3), ConstantInt::get(I32, 1)});
40606f32e7eSjoerg ++NumPrefetches;
407*da58b97aSjoerg LLVM_DEBUG(dbgs() << " Access: "
408*da58b97aSjoerg << *P.MemI->getOperand(isa<LoadInst>(P.MemI) ? 0 : 1)
409*da58b97aSjoerg << ", SCEV: " << *P.LSCEVAddRec << "\n");
41006f32e7eSjoerg ORE->emit([&]() {
411*da58b97aSjoerg return OptimizationRemark(DEBUG_TYPE, "Prefetched", P.MemI)
41206f32e7eSjoerg << "prefetched memory access";
41306f32e7eSjoerg });
41406f32e7eSjoerg
41506f32e7eSjoerg MadeChange = true;
41606f32e7eSjoerg }
41706f32e7eSjoerg
41806f32e7eSjoerg return MadeChange;
41906f32e7eSjoerg }
420