Coverage Report

Created: 2019-07-24 05:18

/Users/buildslave/jenkins/workspace/clang-stage2-coverage-R/llvm/lib/Transforms/Scalar/LoopLoadElimination.cpp
Line
Count
Source (jump to first uncovered line)
1
//===- LoopLoadElimination.cpp - Loop Load Elimination 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 implement a loop-aware load elimination pass.
10
//
11
// It uses LoopAccessAnalysis to identify loop-carried dependences with a
12
// distance of one between stores and loads.  These form the candidates for the
13
// transformation.  The source value of each store then propagated to the user
14
// of the corresponding load.  This makes the load dead.
15
//
16
// The pass can also version the loop and add memchecks in order to prove that
17
// may-aliasing stores can't change the value in memory before it's read by the
18
// load.
19
//
20
//===----------------------------------------------------------------------===//
21
22
#include "llvm/Transforms/Scalar/LoopLoadElimination.h"
23
#include "llvm/ADT/APInt.h"
24
#include "llvm/ADT/DenseMap.h"
25
#include "llvm/ADT/DepthFirstIterator.h"
26
#include "llvm/ADT/STLExtras.h"
27
#include "llvm/ADT/SmallPtrSet.h"
28
#include "llvm/ADT/SmallVector.h"
29
#include "llvm/ADT/Statistic.h"
30
#include "llvm/Analysis/AliasAnalysis.h"
31
#include "llvm/Analysis/AssumptionCache.h"
32
#include "llvm/Analysis/BlockFrequencyInfo.h"
33
#include "llvm/Analysis/GlobalsModRef.h"
34
#include "llvm/Analysis/LazyBlockFrequencyInfo.h"
35
#include "llvm/Analysis/LoopAccessAnalysis.h"
36
#include "llvm/Analysis/LoopAnalysisManager.h"
37
#include "llvm/Analysis/LoopInfo.h"
38
#include "llvm/Analysis/MemorySSA.h"
39
#include "llvm/Analysis/ProfileSummaryInfo.h"
40
#include "llvm/Analysis/ScalarEvolution.h"
41
#include "llvm/Analysis/ScalarEvolutionExpander.h"
42
#include "llvm/Analysis/ScalarEvolutionExpressions.h"
43
#include "llvm/Analysis/TargetLibraryInfo.h"
44
#include "llvm/Analysis/TargetTransformInfo.h"
45
#include "llvm/IR/DataLayout.h"
46
#include "llvm/IR/Dominators.h"
47
#include "llvm/IR/Instructions.h"
48
#include "llvm/IR/Module.h"
49
#include "llvm/IR/PassManager.h"
50
#include "llvm/IR/Type.h"
51
#include "llvm/IR/Value.h"
52
#include "llvm/Pass.h"
53
#include "llvm/Support/Casting.h"
54
#include "llvm/Support/CommandLine.h"
55
#include "llvm/Support/Debug.h"
56
#include "llvm/Support/raw_ostream.h"
57
#include "llvm/Transforms/Scalar.h"
58
#include "llvm/Transforms/Utils.h"
59
#include "llvm/Transforms/Utils/LoopVersioning.h"
60
#include "llvm/Transforms/Utils/SizeOpts.h"
61
#include <algorithm>
62
#include <cassert>
63
#include <forward_list>
64
#include <set>
65
#include <tuple>
66
#include <utility>
67
68
using namespace llvm;
69
70
#define LLE_OPTION "loop-load-elim"
71
#define DEBUG_TYPE LLE_OPTION
72
73
static cl::opt<unsigned> CheckPerElim(
74
    "runtime-check-per-loop-load-elim", cl::Hidden,
75
    cl::desc("Max number of memchecks allowed per eliminated load on average"),
76
    cl::init(1));
77
78
static cl::opt<unsigned> LoadElimSCEVCheckThreshold(
79
    "loop-load-elimination-scev-check-threshold", cl::init(8), cl::Hidden,
80
    cl::desc("The maximum number of SCEV checks allowed for Loop "
81
             "Load Elimination"));
82
83
STATISTIC(NumLoopLoadEliminted, "Number of loads eliminated by LLE");
84
85
namespace {
86
87
/// Represent a store-to-forwarding candidate.
88
struct StoreToLoadForwardingCandidate {
89
  LoadInst *Load;
90
  StoreInst *Store;
91
92
  StoreToLoadForwardingCandidate(LoadInst *Load, StoreInst *Store)
93
859
      : Load(Load), Store(Store) {}
94
95
  /// Return true if the dependence from the store to the load has a
96
  /// distance of one.  E.g. A[i+1] = A[i]
97
  bool isDependenceDistanceOfOne(PredicatedScalarEvolution &PSE,
98
392
                                 Loop *L) const {
99
392
    Value *LoadPtr = Load->getPointerOperand();
100
392
    Value *StorePtr = Store->getPointerOperand();
101
392
    Type *LoadPtrType = LoadPtr->getType();
102
392
    Type *LoadType = LoadPtrType->getPointerElementType();
103
392
104
392
    assert(LoadPtrType->getPointerAddressSpace() ==
105
392
               StorePtr->getType()->getPointerAddressSpace() &&
106
392
           LoadType == StorePtr->getType()->getPointerElementType() &&
107
392
           "Should be a known dependence");
108
392
109
392
    // Currently we only support accesses with unit stride.  FIXME: we should be
110
392
    // able to handle non unit stirde as well as long as the stride is equal to
111
392
    // the dependence distance.
112
392
    if (getPtrStride(PSE, LoadPtr, L) != 1 ||
113
392
        
getPtrStride(PSE, StorePtr, L) != 1332
)
114
60
      return false;
115
332
116
332
    auto &DL = Load->getParent()->getModule()->getDataLayout();
117
332
    unsigned TypeByteSize = DL.getTypeAllocSize(const_cast<Type *>(LoadType));
118
332
119
332
    auto *LoadPtrSCEV = cast<SCEVAddRecExpr>(PSE.getSCEV(LoadPtr));
120
332
    auto *StorePtrSCEV = cast<SCEVAddRecExpr>(PSE.getSCEV(StorePtr));
121
332
122
332
    // We don't need to check non-wrapping here because forward/backward
123
332
    // dependence wouldn't be valid if these weren't monotonic accesses.
124
332
    auto *Dist = cast<SCEVConstant>(
125
332
        PSE.getSE()->getMinusSCEV(StorePtrSCEV, LoadPtrSCEV));
126
332
    const APInt &Val = Dist->getAPInt();
127
332
    return Val == TypeByteSize;
128
332
  }
129
130
40
  Value *getLoadPtr() const { return Load->getPointerOperand(); }
131
132
#ifndef NDEBUG
133
  friend raw_ostream &operator<<(raw_ostream &OS,
134
                                 const StoreToLoadForwardingCandidate &Cand) {
135
    OS << *Cand.Store << " -->\n";
136
    OS.indent(2) << *Cand.Load << "\n";
137
    return OS;
138
  }
139
#endif
140
};
141
142
} // end anonymous namespace
143
144
/// Check if the store dominates all latches, so as long as there is no
145
/// intervening store this value will be loaded in the next iteration.
146
static bool doesStoreDominatesAllLatches(BasicBlock *StoreBlock, Loop *L,
147
333
                                         DominatorTree *DT) {
148
333
  SmallVector<BasicBlock *, 8> Latches;
149
333
  L->getLoopLatches(Latches);
150
333
  return llvm::all_of(Latches, [&](const BasicBlock *Latch) {
151
333
    return DT->dominates(StoreBlock, Latch);
152
333
  });
153
333
}
154
155
/// Return true if the load is not executed on all paths in the loop.
156
289
static bool isLoadConditional(LoadInst *Load, Loop *L) {
157
289
  return Load->getParent() != L->getHeader();
158
289
}
159
160
namespace {
161
162
/// The per-loop class that does most of the work.
163
class LoadEliminationForLoop {
164
public:
165
  LoadEliminationForLoop(Loop *L, LoopInfo *LI, const LoopAccessInfo &LAI,
166
                         DominatorTree *DT, BlockFrequencyInfo *BFI,
167
                         ProfileSummaryInfo* PSI)
168
162k
      : L(L), LI(LI), LAI(LAI), DT(DT), BFI(BFI), PSI(PSI), PSE(LAI.getPSE()) {}
169
170
  /// Look through the loop-carried and loop-independent dependences in
171
  /// this loop and find store->load dependences.
172
  ///
173
  /// Note that no candidate is returned if LAA has failed to analyze the loop
174
  /// (e.g. if it's not bottom-tested, contains volatile memops, etc.)
175
  std::forward_list<StoreToLoadForwardingCandidate>
176
162k
  findStoreToLoadDependences(const LoopAccessInfo &LAI) {
177
162k
    std::forward_list<StoreToLoadForwardingCandidate> Candidates;
178
162k
179
162k
    const auto *Deps = LAI.getDepChecker().getDependences();
180
162k
    if (!Deps)
181
110
      return Candidates;
182
161k
183
161k
    // Find store->load dependences (consequently true dep).  Both lexically
184
161k
    // forward and backward dependences qualify.  Disqualify loads that have
185
161k
    // other unknown dependences.
186
161k
187
161k
    SmallPtrSet<Instruction *, 4> LoadsWithUnknownDepedence;
188
161k
189
161k
    for (const auto &Dep : *Deps) {
190
7.97k
      Instruction *Source = Dep.getSource(LAI);
191
7.97k
      Instruction *Destination = Dep.getDestination(LAI);
192
7.97k
193
7.97k
      if (Dep.Type == MemoryDepChecker::Dependence::Unknown) {
194
2.30k
        if (isa<LoadInst>(Source))
195
1.03k
          LoadsWithUnknownDepedence.insert(Source);
196
2.30k
        if (isa<LoadInst>(Destination))
197
268
          LoadsWithUnknownDepedence.insert(Destination);
198
2.30k
        continue;
199
2.30k
      }
200
5.67k
201
5.67k
      if (Dep.isBackward())
202
2.07k
        // Note that the designations source and destination follow the program
203
2.07k
        // order, i.e. source is always first.  (The direction is given by the
204
2.07k
        // DepType.)
205
2.07k
        std::swap(Source, Destination);
206
5.67k
      else
207
5.67k
        assert(Dep.isForward() && "Needs to be a forward dependence");
208
5.67k
209
5.67k
      auto *Store = dyn_cast<StoreInst>(Source);
210
5.67k
      if (!Store)
211
3.02k
        continue;
212
2.64k
      auto *Load = dyn_cast<LoadInst>(Destination);
213
2.64k
      if (!Load)
214
1.77k
        continue;
215
872
216
872
      // Only progagate the value if they are of the same type.
217
872
      if (Store->getPointerOperandType() != Load->getPointerOperandType())
218
13
        continue;
219
859
220
859
      Candidates.emplace_front(Load, Store);
221
859
    }
222
161k
223
161k
    if (!LoadsWithUnknownDepedence.empty())
224
287
      Candidates.remove_if([&](const StoreToLoadForwardingCandidate &C) {
225
61
        return LoadsWithUnknownDepedence.count(C.Load);
226
61
      });
227
161k
228
161k
    return Candidates;
229
161k
  }
230
231
  /// Return the index of the instruction according to program order.
232
86
  unsigned getInstrIndex(Instruction *Inst) {
233
86
    auto I = InstOrder.find(Inst);
234
86
    assert(I != InstOrder.end() && "No index for instruction");
235
86
    return I->second;
236
86
  }
237
238
  /// If a load has multiple candidates associated (i.e. different
239
  /// stores), it means that it could be forwarding from multiple stores
240
  /// depending on control flow.  Remove these candidates.
241
  ///
242
  /// Here, we rely on LAA to include the relevant loop-independent dependences.
243
  /// LAA is known to omit these in the very simple case when the read and the
244
  /// write within an alias set always takes place using the *same* pointer.
245
  ///
246
  /// However, we know that this is not the case here, i.e. we can rely on LAA
247
  /// to provide us with loop-independent dependences for the cases we're
248
  /// interested.  Consider the case for example where a loop-independent
249
  /// dependece S1->S2 invalidates the forwarding S3->S2.
250
  ///
251
  ///         A[i]   = ...   (S1)
252
  ///         ...    = A[i]  (S2)
253
  ///         A[i+1] = ...   (S3)
254
  ///
255
  /// LAA will perform dependence analysis here because there are two
256
  /// *different* pointers involved in the same alias set (&A[i] and &A[i+1]).
257
  void removeDependencesFromMultipleStores(
258
253
      std::forward_list<StoreToLoadForwardingCandidate> &Candidates) {
259
253
    // If Store is nullptr it means that we have multiple stores forwarding to
260
253
    // this store.
261
253
    using LoadToSingleCandT =
262
253
        DenseMap<LoadInst *, const StoreToLoadForwardingCandidate *>;
263
253
    LoadToSingleCandT LoadToSingleCand;
264
253
265
857
    for (const auto &Cand : Candidates) {
266
857
      bool NewElt;
267
857
      LoadToSingleCandT::iterator Iter;
268
857
269
857
      std::tie(Iter, NewElt) =
270
857
          LoadToSingleCand.insert(std::make_pair(Cand.Load, &Cand));
271
857
      if (!NewElt) {
272
380
        const StoreToLoadForwardingCandidate *&OtherCand = Iter->second;
273
380
        // Already multiple stores forward to this load.
274
380
        if (OtherCand == nullptr)
275
235
          continue;
276
145
277
145
        // Handle the very basic case when the two stores are in the same block
278
145
        // so deciding which one forwards is easy.  The later one forwards as
279
145
        // long as they both have a dependence distance of one to the load.
280
145
        if (Cand.Store->getParent() == OtherCand->Store->getParent() &&
281
145
            
Cand.isDependenceDistanceOfOne(PSE, L)108
&&
282
145
            
OtherCand->isDependenceDistanceOfOne(PSE, L)2
) {
283
1
          // They are in the same block, the later one will forward to the load.
284
1
          if (getInstrIndex(OtherCand->Store) < getInstrIndex(Cand.Store))
285
0
            OtherCand = &Cand;
286
1
        } else
287
144
          OtherCand = nullptr;
288
145
      }
289
857
    }
290
253
291
857
    Candidates.remove_if([&](const StoreToLoadForwardingCandidate &Cand) {
292
857
      if (LoadToSingleCand[Cand.Load] != &Cand) {
293
524
        LLVM_DEBUG(
294
524
            dbgs() << "Removing from candidates: \n"
295
524
                   << Cand
296
524
                   << "  The load may have multiple stores forwarding to "
297
524
                   << "it\n");
298
524
        return true;
299
524
      }
300
333
      return false;
301
333
    });
302
253
  }
303
304
  /// Given two pointers operations by their RuntimePointerChecking
305
  /// indices, return true if they require an alias check.
306
  ///
307
  /// We need a check if one is a pointer for a candidate load and the other is
308
  /// a pointer for a possibly intervening store.
309
  bool needsChecking(unsigned PtrIdx1, unsigned PtrIdx2,
310
                     const SmallPtrSet<Value *, 4> &PtrsWrittenOnFwdingPath,
311
132
                     const std::set<Value *> &CandLoadPtrs) {
312
132
    Value *Ptr1 =
313
132
        LAI.getRuntimePointerChecking()->getPointerInfo(PtrIdx1).PointerValue;
314
132
    Value *Ptr2 =
315
132
        LAI.getRuntimePointerChecking()->getPointerInfo(PtrIdx2).PointerValue;
316
132
    return ((PtrsWrittenOnFwdingPath.count(Ptr1) && 
CandLoadPtrs.count(Ptr2)32
) ||
317
132
            (PtrsWrittenOnFwdingPath.count(Ptr2) && 
CandLoadPtrs.count(Ptr1)18
));
318
132
  }
319
320
  /// Return pointers that are possibly written to on the path from a
321
  /// forwarding store to a load.
322
  ///
323
  /// These pointers need to be alias-checked against the forwarding candidates.
324
  SmallPtrSet<Value *, 4> findPointersWrittenOnForwardingPath(
325
38
      const SmallVectorImpl<StoreToLoadForwardingCandidate> &Candidates) {
326
38
    // From FirstStore to LastLoad neither of the elimination candidate loads
327
38
    // should overlap with any of the stores.
328
38
    //
329
38
    // E.g.:
330
38
    //
331
38
    // st1 C[i]
332
38
    // ld1 B[i] <-------,
333
38
    // ld0 A[i] <----,  |              * LastLoad
334
38
    // ...           |  |
335
38
    // st2 E[i]      |  |
336
38
    // st3 B[i+1] -- | -'              * FirstStore
337
38
    // st0 A[i+1] ---'
338
38
    // st4 D[i]
339
38
    //
340
38
    // st0 forwards to ld0 if the accesses in st4 and st1 don't overlap with
341
38
    // ld0.
342
38
343
38
    LoadInst *LastLoad =
344
38
        std::max_element(Candidates.begin(), Candidates.end(),
345
38
                         [&](const StoreToLoadForwardingCandidate &A,
346
38
                             const StoreToLoadForwardingCandidate &B) {
347
2
                           return getInstrIndex(A.Load) < getInstrIndex(B.Load);
348
2
                         })
349
38
            ->Load;
350
38
    StoreInst *FirstStore =
351
38
        std::min_element(Candidates.begin(), Candidates.end(),
352
38
                         [&](const StoreToLoadForwardingCandidate &A,
353
38
                             const StoreToLoadForwardingCandidate &B) {
354
2
                           return getInstrIndex(A.Store) <
355
2
                                  getInstrIndex(B.Store);
356
2
                         })
357
38
            ->Store;
358
38
359
38
    // We're looking for stores after the first forwarding store until the end
360
38
    // of the loop, then from the beginning of the loop until the last
361
38
    // forwarded-to load.  Collect the pointer for the stores.
362
38
    SmallPtrSet<Value *, 4> PtrsWrittenOnFwdingPath;
363
38
364
80
    auto InsertStorePtr = [&](Instruction *I) {
365
80
      if (auto *S = dyn_cast<StoreInst>(I))
366
36
        PtrsWrittenOnFwdingPath.insert(S->getPointerOperand());
367
80
    };
368
38
    const auto &MemInstrs = LAI.getDepChecker().getMemoryInstructions();
369
38
    std::for_each(MemInstrs.begin() + getInstrIndex(FirstStore) + 1,
370
38
                  MemInstrs.end(), InsertStorePtr);
371
38
    std::for_each(MemInstrs.begin(), &MemInstrs[getInstrIndex(LastLoad)],
372
38
                  InsertStorePtr);
373
38
374
38
    return PtrsWrittenOnFwdingPath;
375
38
  }
376
377
  /// Determine the pointer alias checks to prove that there are no
378
  /// intervening stores.
379
  SmallVector<RuntimePointerChecking::PointerCheck, 4> collectMemchecks(
380
38
      const SmallVectorImpl<StoreToLoadForwardingCandidate> &Candidates) {
381
38
382
38
    SmallPtrSet<Value *, 4> PtrsWrittenOnFwdingPath =
383
38
        findPointersWrittenOnForwardingPath(Candidates);
384
38
385
38
    // Collect the pointers of the candidate loads.
386
38
    // FIXME: SmallPtrSet does not work with std::inserter.
387
38
    std::set<Value *> CandLoadPtrs;
388
38
    transform(Candidates,
389
38
                   std::inserter(CandLoadPtrs, CandLoadPtrs.begin()),
390
38
                   std::mem_fn(&StoreToLoadForwardingCandidate::getLoadPtr));
391
38
392
38
    const auto &AllChecks = LAI.getRuntimePointerChecking()->getChecks();
393
38
    SmallVector<RuntimePointerChecking::PointerCheck, 4> Checks;
394
38
395
38
    copy_if(AllChecks, std::back_inserter(Checks),
396
61
            [&](const RuntimePointerChecking::PointerCheck &Check) {
397
61
              for (auto PtrIdx1 : Check.first->Members)
398
130
                for (auto PtrIdx2 : Check.second->Members)
399
132
                  if (needsChecking(PtrIdx1, PtrIdx2, PtrsWrittenOnFwdingPath,
400
132
                                    CandLoadPtrs))
401
16
                    return true;
402
61
              
return false45
;
403
61
            });
404
38
405
38
    LLVM_DEBUG(dbgs() << "\nPointer Checks (count: " << Checks.size()
406
38
                      << "):\n");
407
38
    LLVM_DEBUG(LAI.getRuntimePointerChecking()->printChecks(dbgs(), Checks));
408
38
409
38
    return Checks;
410
38
  }
411
412
  /// Perform the transformation for a candidate.
413
  void
414
  propagateStoredValueToLoadUsers(const StoreToLoadForwardingCandidate &Cand,
415
31
                                  SCEVExpander &SEE) {
416
31
    // loop:
417
31
    //      %x = load %gep_i
418
31
    //         = ... %x
419
31
    //      store %y, %gep_i_plus_1
420
31
    //
421
31
    // =>
422
31
    //
423
31
    // ph:
424
31
    //      %x.initial = load %gep_0
425
31
    // loop:
426
31
    //      %x.storeforward = phi [%x.initial, %ph] [%y, %loop]
427
31
    //      %x = load %gep_i            <---- now dead
428
31
    //         = ... %x.storeforward
429
31
    //      store %y, %gep_i_plus_1
430
31
431
31
    Value *Ptr = Cand.Load->getPointerOperand();
432
31
    auto *PtrSCEV = cast<SCEVAddRecExpr>(PSE.getSCEV(Ptr));
433
31
    auto *PH = L->getLoopPreheader();
434
31
    Value *InitialPtr = SEE.expandCodeFor(PtrSCEV->getStart(), Ptr->getType(),
435
31
                                          PH->getTerminator());
436
31
    Value *Initial = new LoadInst(
437
31
        Cand.Load->getType(), InitialPtr, "load_initial",
438
31
        /* isVolatile */ false, Cand.Load->getAlignment(), PH->getTerminator());
439
31
440
31
    PHINode *PHI = PHINode::Create(Initial->getType(), 2, "store_forwarded",
441
31
                                   &L->getHeader()->front());
442
31
    PHI->addIncoming(Initial, PH);
443
31
    PHI->addIncoming(Cand.Store->getOperand(0), L->getLoopLatch());
444
31
445
31
    Cand.Load->replaceAllUsesWith(PHI);
446
31
  }
447
448
  /// Top-level driver for each loop: find store->load forwarding
449
  /// candidates, add run-time checks and perform transformation.
450
162k
  bool processLoop() {
451
162k
    LLVM_DEBUG(dbgs() << "\nIn \"" << L->getHeader()->getParent()->getName()
452
162k
                      << "\" checking " << *L << "\n");
453
162k
454
162k
    // Look for store-to-load forwarding cases across the
455
162k
    // backedge. E.g.:
456
162k
    //
457
162k
    // loop:
458
162k
    //      %x = load %gep_i
459
162k
    //         = ... %x
460
162k
    //      store %y, %gep_i_plus_1
461
162k
    //
462
162k
    // =>
463
162k
    //
464
162k
    // ph:
465
162k
    //      %x.initial = load %gep_0
466
162k
    // loop:
467
162k
    //      %x.storeforward = phi [%x.initial, %ph] [%y, %loop]
468
162k
    //      %x = load %gep_i            <---- now dead
469
162k
    //         = ... %x.storeforward
470
162k
    //      store %y, %gep_i_plus_1
471
162k
472
162k
    // First start with store->load dependences.
473
162k
    auto StoreToLoadDependences = findStoreToLoadDependences(LAI);
474
162k
    if (StoreToLoadDependences.empty())
475
161k
      return false;
476
253
477
253
    // Generate an index for each load and store according to the original
478
253
    // program order.  This will be used later.
479
253
    InstOrder = LAI.getDepChecker().generateInstructionOrderMap();
480
253
481
253
    // To keep things simple for now, remove those where the load is potentially
482
253
    // fed by multiple stores.
483
253
    removeDependencesFromMultipleStores(StoreToLoadDependences);
484
253
    if (StoreToLoadDependences.empty())
485
8
      return false;
486
245
487
245
    // Filter the candidates further.
488
245
    SmallVector<StoreToLoadForwardingCandidate, 4> Candidates;
489
245
    unsigned NumForwarding = 0;
490
333
    for (const StoreToLoadForwardingCandidate Cand : StoreToLoadDependences) {
491
333
      LLVM_DEBUG(dbgs() << "Candidate " << Cand);
492
333
493
333
      // Make sure that the stored values is available everywhere in the loop in
494
333
      // the next iteration.
495
333
      if (!doesStoreDominatesAllLatches(Cand.Store->getParent(), L, DT))
496
44
        continue;
497
289
498
289
      // If the load is conditional we can't hoist its 0-iteration instance to
499
289
      // the preheader because that would make it unconditional.  Thus we would
500
289
      // access a memory location that the original loop did not access.
501
289
      if (isLoadConditional(Cand.Load, L))
502
7
        continue;
503
282
504
282
      // Check whether the SCEV difference is the same as the induction step,
505
282
      // thus we load the value in the next iteration.
506
282
      if (!Cand.isDependenceDistanceOfOne(PSE, L))
507
242
        continue;
508
40
509
40
      ++NumForwarding;
510
40
      LLVM_DEBUG(
511
40
          dbgs()
512
40
          << NumForwarding
513
40
          << ". Valid store-to-load forwarding across the loop backedge\n");
514
40
      Candidates.push_back(Cand);
515
40
    }
516
245
    if (Candidates.empty())
517
207
      return false;
518
38
519
38
    // Check intervening may-alias stores.  These need runtime checks for alias
520
38
    // disambiguation.
521
38
    SmallVector<RuntimePointerChecking::PointerCheck, 4> Checks =
522
38
        collectMemchecks(Candidates);
523
38
524
38
    // Too many checks are likely to outweigh the benefits of forwarding.
525
38
    if (Checks.size() > Candidates.size() * CheckPerElim) {
526
1
      LLVM_DEBUG(dbgs() << "Too many run-time checks needed.\n");
527
1
      return false;
528
1
    }
529
37
530
37
    if (LAI.getPSE().getUnionPredicate().getComplexity() >
531
37
        LoadElimSCEVCheckThreshold) {
532
1
      LLVM_DEBUG(dbgs() << "Too many SCEV run-time checks needed.\n");
533
1
      return false;
534
1
    }
535
36
536
36
    if (!Checks.empty() || 
!LAI.getPSE().getUnionPredicate().isAlwaysTrue()23
) {
537
20
      if (LAI.hasConvergentOp()) {
538
2
        LLVM_DEBUG(dbgs() << "Versioning is needed but not allowed with "
539
2
                             "convergent calls\n");
540
2
        return false;
541
2
      }
542
18
543
18
      auto *HeaderBB = L->getHeader();
544
18
      auto *F = HeaderBB->getParent();
545
18
      bool OptForSize = F->hasOptSize() ||
546
18
                        
llvm::shouldOptimizeForSize(HeaderBB, PSI, BFI)15
;
547
18
      if (OptForSize) {
548
5
        LLVM_DEBUG(
549
5
            dbgs() << "Versioning is needed but not allowed when optimizing "
550
5
                      "for size.\n");
551
5
        return false;
552
5
      }
553
13
554
13
      if (!L->isLoopSimplifyForm()) {
555
0
        LLVM_DEBUG(dbgs() << "Loop is not is loop-simplify form");
556
0
        return false;
557
0
      }
558
13
559
13
      // Point of no-return, start the transformation.  First, version the loop
560
13
      // if necessary.
561
13
562
13
      LoopVersioning LV(LAI, L, LI, DT, PSE.getSE(), false);
563
13
      LV.setAliasChecks(std::move(Checks));
564
13
      LV.setSCEVChecks(LAI.getPSE().getUnionPredicate());
565
13
      LV.versionLoop();
566
13
    }
567
36
568
36
    // Next, propagate the value stored by the store to the users of the load.
569
36
    // Also for the first iteration, generate the initial value of the load.
570
36
    SCEVExpander SEE(*PSE.getSE(), L->getHeader()->getModule()->getDataLayout(),
571
29
                     "storeforward");
572
29
    for (const auto &Cand : Candidates)
573
31
      propagateStoredValueToLoadUsers(Cand, SEE);
574
29
    NumLoopLoadEliminted += NumForwarding;
575
29
576
29
    return true;
577
36
  }
578
579
private:
580
  Loop *L;
581
582
  /// Maps the load/store instructions to their index according to
583
  /// program order.
584
  DenseMap<Instruction *, unsigned> InstOrder;
585
586
  // Analyses used.
587
  LoopInfo *LI;
588
  const LoopAccessInfo &LAI;
589
  DominatorTree *DT;
590
  BlockFrequencyInfo *BFI;
591
  ProfileSummaryInfo *PSI;
592
  PredicatedScalarEvolution PSE;
593
};
594
595
} // end anonymous namespace
596
597
static bool
598
eliminateLoadsAcrossLoops(Function &F, LoopInfo &LI, DominatorTree &DT,
599
                          BlockFrequencyInfo *BFI, ProfileSummaryInfo *PSI,
600
279k
                          function_ref<const LoopAccessInfo &(Loop &)> GetLAI) {
601
279k
  // Build up a worklist of inner-loops to transform to avoid iterator
602
279k
  // invalidation.
603
279k
  // FIXME: This logic comes from other passes that actually change the loop
604
279k
  // nest structure. It isn't clear this is necessary (or useful) for a pass
605
279k
  // which merely optimizes the use of loads in a loop.
606
279k
  SmallVector<Loop *, 8> Worklist;
607
279k
608
279k
  for (Loop *TopLevelLoop : LI)
609
140k
    for (Loop *L : depth_first(TopLevelLoop))
610
194k
      // We only handle inner-most loops.
611
194k
      if (L->empty())
612
162k
        Worklist.push_back(L);
613
279k
614
279k
  // Now walk the identified inner loops.
615
279k
  bool Changed = false;
616
279k
  for (Loop *L : Worklist) {
617
162k
    // The actual work is performed by LoadEliminationForLoop.
618
162k
    LoadEliminationForLoop LEL(L, &LI, GetLAI(*L), &DT, BFI, PSI);
619
162k
    Changed |= LEL.processLoop();
620
162k
  }
621
279k
  return Changed;
622
279k
}
623
624
namespace {
625
626
/// The pass.  Most of the work is delegated to the per-loop
627
/// LoadEliminationForLoop class.
628
class LoopLoadElimination : public FunctionPass {
629
public:
630
  static char ID;
631
632
12.9k
  LoopLoadElimination() : FunctionPass(ID) {
633
12.9k
    initializeLoopLoadEliminationPass(*PassRegistry::getPassRegistry());
634
12.9k
  }
635
636
278k
  bool runOnFunction(Function &F) override {
637
278k
    if (skipFunction(F))
638
44
      return false;
639
278k
640
278k
    auto &LI = getAnalysis<LoopInfoWrapperPass>().getLoopInfo();
641
278k
    auto &LAA = getAnalysis<LoopAccessLegacyAnalysis>();
642
278k
    auto &DT = getAnalysis<DominatorTreeWrapperPass>().getDomTree();
643
278k
    auto *PSI = &getAnalysis<ProfileSummaryInfoWrapperPass>().getPSI();
644
278k
    auto *BFI = (PSI && PSI->hasProfileSummary()) ?
645
46
                &getAnalysis<LazyBlockFrequencyInfoPass>().getBFI() :
646
278k
                
nullptr278k
;
647
278k
648
278k
    // Process each loop nest in the function.
649
278k
    return eliminateLoadsAcrossLoops(
650
278k
        F, LI, DT, BFI, PSI,
651
278k
        [&LAA](Loop &L) -> const LoopAccessInfo & 
{ return LAA.getInfo(&L); }162k
);
652
278k
  }
653
654
12.9k
  void getAnalysisUsage(AnalysisUsage &AU) const override {
655
12.9k
    AU.addRequiredID(LoopSimplifyID);
656
12.9k
    AU.addRequired<LoopInfoWrapperPass>();
657
12.9k
    AU.addPreserved<LoopInfoWrapperPass>();
658
12.9k
    AU.addRequired<LoopAccessLegacyAnalysis>();
659
12.9k
    AU.addRequired<ScalarEvolutionWrapperPass>();
660
12.9k
    AU.addRequired<DominatorTreeWrapperPass>();
661
12.9k
    AU.addPreserved<DominatorTreeWrapperPass>();
662
12.9k
    AU.addPreserved<GlobalsAAWrapperPass>();
663
12.9k
    AU.addRequired<ProfileSummaryInfoWrapperPass>();
664
12.9k
    LazyBlockFrequencyInfoPass::getLazyBFIAnalysisUsage(AU);
665
12.9k
  }
666
};
667
668
} // end anonymous namespace
669
670
char LoopLoadElimination::ID;
671
672
static const char LLE_name[] = "Loop Load Elimination";
673
674
48.6k
INITIALIZE_PASS_BEGIN(LoopLoadElimination, LLE_OPTION, LLE_name, false, false)
675
48.6k
INITIALIZE_PASS_DEPENDENCY(LoopInfoWrapperPass)
676
48.6k
INITIALIZE_PASS_DEPENDENCY(LoopAccessLegacyAnalysis)
677
48.6k
INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass)
678
48.6k
INITIALIZE_PASS_DEPENDENCY(ScalarEvolutionWrapperPass)
679
48.6k
INITIALIZE_PASS_DEPENDENCY(LoopSimplify)
680
48.6k
INITIALIZE_PASS_DEPENDENCY(ProfileSummaryInfoWrapperPass)
681
48.6k
INITIALIZE_PASS_DEPENDENCY(LazyBlockFrequencyInfoPass)
682
48.6k
INITIALIZE_PASS_END(LoopLoadElimination, LLE_OPTION, LLE_name, false, false)
683
684
12.9k
FunctionPass *llvm::createLoopLoadEliminationPass() {
685
12.9k
  return new LoopLoadElimination();
686
12.9k
}
687
688
PreservedAnalyses LoopLoadEliminationPass::run(Function &F,
689
863
                                               FunctionAnalysisManager &AM) {
690
863
  auto &SE = AM.getResult<ScalarEvolutionAnalysis>(F);
691
863
  auto &LI = AM.getResult<LoopAnalysis>(F);
692
863
  auto &TTI = AM.getResult<TargetIRAnalysis>(F);
693
863
  auto &DT = AM.getResult<DominatorTreeAnalysis>(F);
694
863
  auto &TLI = AM.getResult<TargetLibraryAnalysis>(F);
695
863
  auto &AA = AM.getResult<AAManager>(F);
696
863
  auto &AC = AM.getResult<AssumptionAnalysis>(F);
697
863
  auto &MAM = AM.getResult<ModuleAnalysisManagerFunctionProxy>(F).getManager();
698
863
  auto *PSI = MAM.getCachedResult<ProfileSummaryAnalysis>(*F.getParent());
699
863
  auto *BFI = (PSI && 
PSI->hasProfileSummary()860
) ?
700
825
      
&AM.getResult<BlockFrequencyAnalysis>(F)38
: nullptr;
701
863
  MemorySSA *MSSA = EnableMSSALoopDependency
702
863
                        ? 
&AM.getResult<MemorySSAAnalysis>(F).getMSSA()0
703
863
                        : nullptr;
704
863
705
863
  auto &LAM = AM.getResult<LoopAnalysisManagerFunctionProxy>(F).getManager();
706
863
  bool Changed = eliminateLoadsAcrossLoops(
707
863
      F, LI, DT, BFI, PSI, [&](Loop &L) -> const LoopAccessInfo & {
708
48
        LoopStandardAnalysisResults AR = {AA, AC, DT, LI, SE, TLI, TTI, MSSA};
709
48
        return LAM.getResult<LoopAccessAnalysis>(L, AR);
710
48
      });
711
863
712
863
  if (!Changed)
713
861
    return PreservedAnalyses::all();
714
2
715
2
  PreservedAnalyses PA;
716
2
  return PA;
717
2
}