Coverage Report

Created: 2019-07-24 05:18

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