LLVM  13.0.0git
LoopLoadElimination.cpp
Go to the documentation of this file.
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 
23 #include "llvm/ADT/APInt.h"
24 #include "llvm/ADT/DenseMap.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"
36 #include "llvm/Analysis/LoopInfo.h"
43 #include "llvm/IR/DataLayout.h"
44 #include "llvm/IR/Dominators.h"
45 #include "llvm/IR/Instructions.h"
46 #include "llvm/IR/Module.h"
47 #include "llvm/IR/PassManager.h"
48 #include "llvm/IR/Type.h"
49 #include "llvm/IR/Value.h"
50 #include "llvm/InitializePasses.h"
51 #include "llvm/Pass.h"
52 #include "llvm/Support/Casting.h"
54 #include "llvm/Support/Debug.h"
56 #include "llvm/Transforms/Scalar.h"
57 #include "llvm/Transforms/Utils.h"
62 #include <algorithm>
63 #include <cassert>
64 #include <forward_list>
65 #include <set>
66 #include <tuple>
67 #include <utility>
68 
69 using namespace llvm;
70 
71 #define LLE_OPTION "loop-load-elim"
72 #define DEBUG_TYPE LLE_OPTION
73 
75  "runtime-check-per-loop-load-elim", cl::Hidden,
76  cl::desc("Max number of memchecks allowed per eliminated load on average"),
77  cl::init(1));
78 
80  "loop-load-elimination-scev-check-threshold", cl::init(8), cl::Hidden,
81  cl::desc("The maximum number of SCEV checks allowed for Loop "
82  "Load Elimination"));
83 
84 STATISTIC(NumLoopLoadEliminted, "Number of loads eliminated by LLE");
85 
86 namespace {
87 
88 /// Represent a store-to-forwarding candidate.
89 struct StoreToLoadForwardingCandidate {
90  LoadInst *Load;
92 
93  StoreToLoadForwardingCandidate(LoadInst *Load, StoreInst *Store)
94  : Load(Load), Store(Store) {}
95 
96  /// Return true if the dependence from the store to the load has a
97  /// distance of one. E.g. A[i+1] = A[i]
98  bool isDependenceDistanceOfOne(PredicatedScalarEvolution &PSE,
99  Loop *L) const {
100  Value *LoadPtr = Load->getPointerOperand();
101  Value *StorePtr = Store->getPointerOperand();
102  Type *LoadPtrType = LoadPtr->getType();
103  Type *LoadType = LoadPtrType->getPointerElementType();
104 
105  assert(LoadPtrType->getPointerAddressSpace() ==
106  StorePtr->getType()->getPointerAddressSpace() &&
107  LoadType == StorePtr->getType()->getPointerElementType() &&
108  "Should be a known dependence");
109 
110  // Currently we only support accesses with unit stride. FIXME: we should be
111  // able to handle non unit stirde as well as long as the stride is equal to
112  // the dependence distance.
113  if (getPtrStride(PSE, LoadPtr, L) != 1 ||
114  getPtrStride(PSE, StorePtr, L) != 1)
115  return false;
116 
117  auto &DL = Load->getParent()->getModule()->getDataLayout();
118  unsigned TypeByteSize = DL.getTypeAllocSize(const_cast<Type *>(LoadType));
119 
120  auto *LoadPtrSCEV = cast<SCEVAddRecExpr>(PSE.getSCEV(LoadPtr));
121  auto *StorePtrSCEV = cast<SCEVAddRecExpr>(PSE.getSCEV(StorePtr));
122 
123  // We don't need to check non-wrapping here because forward/backward
124  // dependence wouldn't be valid if these weren't monotonic accesses.
125  auto *Dist = cast<SCEVConstant>(
126  PSE.getSE()->getMinusSCEV(StorePtrSCEV, LoadPtrSCEV));
127  const APInt &Val = Dist->getAPInt();
128  return Val == TypeByteSize;
129  }
130 
131  Value *getLoadPtr() const { return Load->getPointerOperand(); }
132 
133 #ifndef NDEBUG
134  friend raw_ostream &operator<<(raw_ostream &OS,
135  const StoreToLoadForwardingCandidate &Cand) {
136  OS << *Cand.Store << " -->\n";
137  OS.indent(2) << *Cand.Load << "\n";
138  return OS;
139  }
140 #endif
141 };
142 
143 } // end anonymous namespace
144 
145 /// Check if the store dominates all latches, so as long as there is no
146 /// intervening store this value will be loaded in the next iteration.
147 static bool doesStoreDominatesAllLatches(BasicBlock *StoreBlock, Loop *L,
148  DominatorTree *DT) {
150  L->getLoopLatches(Latches);
151  return llvm::all_of(Latches, [&](const BasicBlock *Latch) {
152  return DT->dominates(StoreBlock, Latch);
153  });
154 }
155 
156 /// Return true if the load is not executed on all paths in the loop.
157 static bool isLoadConditional(LoadInst *Load, Loop *L) {
158  return Load->getParent() != L->getHeader();
159 }
160 
161 namespace {
162 
163 /// The per-loop class that does most of the work.
164 class LoadEliminationForLoop {
165 public:
166  LoadEliminationForLoop(Loop *L, LoopInfo *LI, const LoopAccessInfo &LAI,
168  ProfileSummaryInfo* PSI)
169  : L(L), LI(LI), LAI(LAI), DT(DT), BFI(BFI), PSI(PSI), PSE(LAI.getPSE()) {}
170 
171  /// Look through the loop-carried and loop-independent dependences in
172  /// this loop and find store->load dependences.
173  ///
174  /// Note that no candidate is returned if LAA has failed to analyze the loop
175  /// (e.g. if it's not bottom-tested, contains volatile memops, etc.)
176  std::forward_list<StoreToLoadForwardingCandidate>
177  findStoreToLoadDependences(const LoopAccessInfo &LAI) {
178  std::forward_list<StoreToLoadForwardingCandidate> Candidates;
179 
180  const auto *Deps = LAI.getDepChecker().getDependences();
181  if (!Deps)
182  return Candidates;
183 
184  // Find store->load dependences (consequently true dep). Both lexically
185  // forward and backward dependences qualify. Disqualify loads that have
186  // other unknown dependences.
187 
188  SmallPtrSet<Instruction *, 4> LoadsWithUnknownDepedence;
189 
190  for (const auto &Dep : *Deps) {
191  Instruction *Source = Dep.getSource(LAI);
192  Instruction *Destination = Dep.getDestination(LAI);
193 
194  if (Dep.Type == MemoryDepChecker::Dependence::Unknown) {
195  if (isa<LoadInst>(Source))
196  LoadsWithUnknownDepedence.insert(Source);
197  if (isa<LoadInst>(Destination))
198  LoadsWithUnknownDepedence.insert(Destination);
199  continue;
200  }
201 
202  if (Dep.isBackward())
203  // Note that the designations source and destination follow the program
204  // order, i.e. source is always first. (The direction is given by the
205  // DepType.)
206  std::swap(Source, Destination);
207  else
208  assert(Dep.isForward() && "Needs to be a forward dependence");
209 
210  auto *Store = dyn_cast<StoreInst>(Source);
211  if (!Store)
212  continue;
213  auto *Load = dyn_cast<LoadInst>(Destination);
214  if (!Load)
215  continue;
216 
217  // Only progagate the value if they are of the same type.
218  if (Store->getPointerOperandType() != Load->getPointerOperandType())
219  continue;
220 
221  Candidates.emplace_front(Load, Store);
222  }
223 
224  if (!LoadsWithUnknownDepedence.empty())
225  Candidates.remove_if([&](const StoreToLoadForwardingCandidate &C) {
226  return LoadsWithUnknownDepedence.count(C.Load);
227  });
228 
229  return Candidates;
230  }
231 
232  /// Return the index of the instruction according to program order.
233  unsigned getInstrIndex(Instruction *Inst) {
234  auto I = InstOrder.find(Inst);
235  assert(I != InstOrder.end() && "No index for instruction");
236  return I->second;
237  }
238 
239  /// If a load has multiple candidates associated (i.e. different
240  /// stores), it means that it could be forwarding from multiple stores
241  /// depending on control flow. Remove these candidates.
242  ///
243  /// Here, we rely on LAA to include the relevant loop-independent dependences.
244  /// LAA is known to omit these in the very simple case when the read and the
245  /// write within an alias set always takes place using the *same* pointer.
246  ///
247  /// However, we know that this is not the case here, i.e. we can rely on LAA
248  /// to provide us with loop-independent dependences for the cases we're
249  /// interested. Consider the case for example where a loop-independent
250  /// dependece S1->S2 invalidates the forwarding S3->S2.
251  ///
252  /// A[i] = ... (S1)
253  /// ... = A[i] (S2)
254  /// A[i+1] = ... (S3)
255  ///
256  /// LAA will perform dependence analysis here because there are two
257  /// *different* pointers involved in the same alias set (&A[i] and &A[i+1]).
258  void removeDependencesFromMultipleStores(
259  std::forward_list<StoreToLoadForwardingCandidate> &Candidates) {
260  // If Store is nullptr it means that we have multiple stores forwarding to
261  // this store.
262  using LoadToSingleCandT =
264  LoadToSingleCandT LoadToSingleCand;
265 
266  for (const auto &Cand : Candidates) {
267  bool NewElt;
268  LoadToSingleCandT::iterator Iter;
269 
270  std::tie(Iter, NewElt) =
271  LoadToSingleCand.insert(std::make_pair(Cand.Load, &Cand));
272  if (!NewElt) {
273  const StoreToLoadForwardingCandidate *&OtherCand = Iter->second;
274  // Already multiple stores forward to this load.
275  if (OtherCand == nullptr)
276  continue;
277 
278  // Handle the very basic case when the two stores are in the same block
279  // so deciding which one forwards is easy. The later one forwards as
280  // long as they both have a dependence distance of one to the load.
281  if (Cand.Store->getParent() == OtherCand->Store->getParent() &&
282  Cand.isDependenceDistanceOfOne(PSE, L) &&
283  OtherCand->isDependenceDistanceOfOne(PSE, L)) {
284  // They are in the same block, the later one will forward to the load.
285  if (getInstrIndex(OtherCand->Store) < getInstrIndex(Cand.Store))
286  OtherCand = &Cand;
287  } else
288  OtherCand = nullptr;
289  }
290  }
291 
292  Candidates.remove_if([&](const StoreToLoadForwardingCandidate &Cand) {
293  if (LoadToSingleCand[Cand.Load] != &Cand) {
294  LLVM_DEBUG(
295  dbgs() << "Removing from candidates: \n"
296  << Cand
297  << " The load may have multiple stores forwarding to "
298  << "it\n");
299  return true;
300  }
301  return false;
302  });
303  }
304 
305  /// Given two pointers operations by their RuntimePointerChecking
306  /// indices, return true if they require an alias check.
307  ///
308  /// We need a check if one is a pointer for a candidate load and the other is
309  /// a pointer for a possibly intervening store.
310  bool needsChecking(unsigned PtrIdx1, unsigned PtrIdx2,
311  const SmallPtrSetImpl<Value *> &PtrsWrittenOnFwdingPath,
312  const SmallPtrSetImpl<Value *> &CandLoadPtrs) {
313  Value *Ptr1 =
315  Value *Ptr2 =
317  return ((PtrsWrittenOnFwdingPath.count(Ptr1) && CandLoadPtrs.count(Ptr2)) ||
318  (PtrsWrittenOnFwdingPath.count(Ptr2) && CandLoadPtrs.count(Ptr1)));
319  }
320 
321  /// Return pointers that are possibly written to on the path from a
322  /// forwarding store to a load.
323  ///
324  /// These pointers need to be alias-checked against the forwarding candidates.
325  SmallPtrSet<Value *, 4> findPointersWrittenOnForwardingPath(
327  // From FirstStore to LastLoad neither of the elimination candidate loads
328  // should overlap with any of the stores.
329  //
330  // E.g.:
331  //
332  // st1 C[i]
333  // ld1 B[i] <-------,
334  // ld0 A[i] <----, | * LastLoad
335  // ... | |
336  // st2 E[i] | |
337  // st3 B[i+1] -- | -' * FirstStore
338  // st0 A[i+1] ---'
339  // st4 D[i]
340  //
341  // st0 forwards to ld0 if the accesses in st4 and st1 don't overlap with
342  // ld0.
343 
344  LoadInst *LastLoad =
345  std::max_element(Candidates.begin(), Candidates.end(),
346  [&](const StoreToLoadForwardingCandidate &A,
347  const StoreToLoadForwardingCandidate &B) {
348  return getInstrIndex(A.Load) < getInstrIndex(B.Load);
349  })
350  ->Load;
351  StoreInst *FirstStore =
352  std::min_element(Candidates.begin(), Candidates.end(),
353  [&](const StoreToLoadForwardingCandidate &A,
354  const StoreToLoadForwardingCandidate &B) {
355  return getInstrIndex(A.Store) <
356  getInstrIndex(B.Store);
357  })
358  ->Store;
359 
360  // We're looking for stores after the first forwarding store until the end
361  // of the loop, then from the beginning of the loop until the last
362  // forwarded-to load. Collect the pointer for the stores.
363  SmallPtrSet<Value *, 4> PtrsWrittenOnFwdingPath;
364 
365  auto InsertStorePtr = [&](Instruction *I) {
366  if (auto *S = dyn_cast<StoreInst>(I))
367  PtrsWrittenOnFwdingPath.insert(S->getPointerOperand());
368  };
369  const auto &MemInstrs = LAI.getDepChecker().getMemoryInstructions();
370  std::for_each(MemInstrs.begin() + getInstrIndex(FirstStore) + 1,
371  MemInstrs.end(), InsertStorePtr);
372  std::for_each(MemInstrs.begin(), &MemInstrs[getInstrIndex(LastLoad)],
373  InsertStorePtr);
374 
375  return PtrsWrittenOnFwdingPath;
376  }
377 
378  /// Determine the pointer alias checks to prove that there are no
379  /// intervening stores.
380  SmallVector<RuntimePointerCheck, 4> collectMemchecks(
382 
383  SmallPtrSet<Value *, 4> PtrsWrittenOnFwdingPath =
384  findPointersWrittenOnForwardingPath(Candidates);
385 
386  // Collect the pointers of the candidate loads.
387  SmallPtrSet<Value *, 4> CandLoadPtrs;
388  for (const auto &Candidate : Candidates)
389  CandLoadPtrs.insert(Candidate.getLoadPtr());
390 
391  const auto &AllChecks = LAI.getRuntimePointerChecking()->getChecks();
393 
394  copy_if(AllChecks, std::back_inserter(Checks),
395  [&](const RuntimePointerCheck &Check) {
396  for (auto PtrIdx1 : Check.first->Members)
397  for (auto PtrIdx2 : Check.second->Members)
398  if (needsChecking(PtrIdx1, PtrIdx2, PtrsWrittenOnFwdingPath,
399  CandLoadPtrs))
400  return true;
401  return false;
402  });
403 
404  LLVM_DEBUG(dbgs() << "\nPointer Checks (count: " << Checks.size()
405  << "):\n");
407 
408  return Checks;
409  }
410 
411  /// Perform the transformation for a candidate.
412  void
413  propagateStoredValueToLoadUsers(const StoreToLoadForwardingCandidate &Cand,
414  SCEVExpander &SEE) {
415  // loop:
416  // %x = load %gep_i
417  // = ... %x
418  // store %y, %gep_i_plus_1
419  //
420  // =>
421  //
422  // ph:
423  // %x.initial = load %gep_0
424  // loop:
425  // %x.storeforward = phi [%x.initial, %ph] [%y, %loop]
426  // %x = load %gep_i <---- now dead
427  // = ... %x.storeforward
428  // store %y, %gep_i_plus_1
429 
430  Value *Ptr = Cand.Load->getPointerOperand();
431  auto *PtrSCEV = cast<SCEVAddRecExpr>(PSE.getSCEV(Ptr));
432  auto *PH = L->getLoopPreheader();
433  assert(PH && "Preheader should exist!");
434  Value *InitialPtr = SEE.expandCodeFor(PtrSCEV->getStart(), Ptr->getType(),
435  PH->getTerminator());
436  Value *Initial = new LoadInst(
437  Cand.Load->getType(), InitialPtr, "load_initial",
438  /* isVolatile */ false, Cand.Load->getAlign(), PH->getTerminator());
439 
440  PHINode *PHI = PHINode::Create(Initial->getType(), 2, "store_forwarded",
441  &L->getHeader()->front());
442  PHI->addIncoming(Initial, PH);
443  PHI->addIncoming(Cand.Store->getOperand(0), L->getLoopLatch());
444 
445  Cand.Load->replaceAllUsesWith(PHI);
446  }
447 
448  /// Top-level driver for each loop: find store->load forwarding
449  /// candidates, add run-time checks and perform transformation.
450  bool processLoop() {
451  LLVM_DEBUG(dbgs() << "\nIn \"" << L->getHeader()->getParent()->getName()
452  << "\" checking " << *L << "\n");
453 
454  // Look for store-to-load forwarding cases across the
455  // backedge. E.g.:
456  //
457  // loop:
458  // %x = load %gep_i
459  // = ... %x
460  // store %y, %gep_i_plus_1
461  //
462  // =>
463  //
464  // ph:
465  // %x.initial = load %gep_0
466  // loop:
467  // %x.storeforward = phi [%x.initial, %ph] [%y, %loop]
468  // %x = load %gep_i <---- now dead
469  // = ... %x.storeforward
470  // store %y, %gep_i_plus_1
471 
472  // First start with store->load dependences.
473  auto StoreToLoadDependences = findStoreToLoadDependences(LAI);
474  if (StoreToLoadDependences.empty())
475  return false;
476 
477  // Generate an index for each load and store according to the original
478  // program order. This will be used later.
479  InstOrder = LAI.getDepChecker().generateInstructionOrderMap();
480 
481  // To keep things simple for now, remove those where the load is potentially
482  // fed by multiple stores.
483  removeDependencesFromMultipleStores(StoreToLoadDependences);
484  if (StoreToLoadDependences.empty())
485  return false;
486 
487  // Filter the candidates further.
489  for (const StoreToLoadForwardingCandidate &Cand : StoreToLoadDependences) {
490  LLVM_DEBUG(dbgs() << "Candidate " << Cand);
491 
492  // Make sure that the stored values is available everywhere in the loop in
493  // the next iteration.
494  if (!doesStoreDominatesAllLatches(Cand.Store->getParent(), L, DT))
495  continue;
496 
497  // If the load is conditional we can't hoist its 0-iteration instance to
498  // the preheader because that would make it unconditional. Thus we would
499  // access a memory location that the original loop did not access.
500  if (isLoadConditional(Cand.Load, L))
501  continue;
502 
503  // Check whether the SCEV difference is the same as the induction step,
504  // thus we load the value in the next iteration.
505  if (!Cand.isDependenceDistanceOfOne(PSE, L))
506  continue;
507 
508  assert(isa<SCEVAddRecExpr>(PSE.getSCEV(Cand.Load->getPointerOperand())) &&
509  "Loading from something other than indvar?");
510  assert(
511  isa<SCEVAddRecExpr>(PSE.getSCEV(Cand.Store->getPointerOperand())) &&
512  "Storing to something other than indvar?");
513 
514  Candidates.push_back(Cand);
515  LLVM_DEBUG(
516  dbgs()
517  << Candidates.size()
518  << ". Valid store-to-load forwarding across the loop backedge\n");
519  }
520  if (Candidates.empty())
521  return false;
522 
523  // Check intervening may-alias stores. These need runtime checks for alias
524  // disambiguation.
525  SmallVector<RuntimePointerCheck, 4> Checks = collectMemchecks(Candidates);
526 
527  // Too many checks are likely to outweigh the benefits of forwarding.
528  if (Checks.size() > Candidates.size() * CheckPerElim) {
529  LLVM_DEBUG(dbgs() << "Too many run-time checks needed.\n");
530  return false;
531  }
532 
533  if (LAI.getPSE().getUnionPredicate().getComplexity() >
535  LLVM_DEBUG(dbgs() << "Too many SCEV run-time checks needed.\n");
536  return false;
537  }
538 
539  if (!L->isLoopSimplifyForm()) {
540  LLVM_DEBUG(dbgs() << "Loop is not is loop-simplify form");
541  return false;
542  }
543 
544  if (!Checks.empty() || !LAI.getPSE().getUnionPredicate().isAlwaysTrue()) {
545  if (LAI.hasConvergentOp()) {
546  LLVM_DEBUG(dbgs() << "Versioning is needed but not allowed with "
547  "convergent calls\n");
548  return false;
549  }
550 
551  auto *HeaderBB = L->getHeader();
552  auto *F = HeaderBB->getParent();
553  bool OptForSize = F->hasOptSize() ||
554  llvm::shouldOptimizeForSize(HeaderBB, PSI, BFI,
556  if (OptForSize) {
557  LLVM_DEBUG(
558  dbgs() << "Versioning is needed but not allowed when optimizing "
559  "for size.\n");
560  return false;
561  }
562 
563  // Point of no-return, start the transformation. First, version the loop
564  // if necessary.
565 
566  LoopVersioning LV(LAI, Checks, L, LI, DT, PSE.getSE());
567  LV.versionLoop();
568 
569  // After versioning, some of the candidates' pointers could stop being
570  // SCEVAddRecs. We need to filter them out.
571  auto NoLongerGoodCandidate = [this](
572  const StoreToLoadForwardingCandidate &Cand) {
573  return !isa<SCEVAddRecExpr>(
574  PSE.getSCEV(Cand.Load->getPointerOperand())) ||
575  !isa<SCEVAddRecExpr>(
576  PSE.getSCEV(Cand.Store->getPointerOperand()));
577  };
578  llvm::erase_if(Candidates, NoLongerGoodCandidate);
579  }
580 
581  // Next, propagate the value stored by the store to the users of the load.
582  // Also for the first iteration, generate the initial value of the load.
584  "storeforward");
585  for (const auto &Cand : Candidates)
586  propagateStoredValueToLoadUsers(Cand, SEE);
587  NumLoopLoadEliminted += Candidates.size();
588 
589  return true;
590  }
591 
592 private:
593  Loop *L;
594 
595  /// Maps the load/store instructions to their index according to
596  /// program order.
598 
599  // Analyses used.
600  LoopInfo *LI;
601  const LoopAccessInfo &LAI;
602  DominatorTree *DT;
604  ProfileSummaryInfo *PSI;
606 };
607 
608 } // end anonymous namespace
609 
610 static bool
614  function_ref<const LoopAccessInfo &(Loop &)> GetLAI) {
615  // Build up a worklist of inner-loops to transform to avoid iterator
616  // invalidation.
617  // FIXME: This logic comes from other passes that actually change the loop
618  // nest structure. It isn't clear this is necessary (or useful) for a pass
619  // which merely optimizes the use of loads in a loop.
620  SmallVector<Loop *, 8> Worklist;
621 
622  bool Changed = false;
623 
624  for (Loop *TopLevelLoop : LI)
625  for (Loop *L : depth_first(TopLevelLoop)) {
626  Changed |= simplifyLoop(L, &DT, &LI, SE, AC, /*MSSAU*/ nullptr, false);
627  // We only handle inner-most loops.
628  if (L->isInnermost())
629  Worklist.push_back(L);
630  }
631 
632  // Now walk the identified inner loops.
633  for (Loop *L : Worklist) {
634  // Match historical behavior
635  if (!L->isRotatedForm() || !L->getExitingBlock())
636  continue;
637  // The actual work is performed by LoadEliminationForLoop.
638  LoadEliminationForLoop LEL(L, &LI, GetLAI(*L), &DT, BFI, PSI);
639  Changed |= LEL.processLoop();
640  }
641  return Changed;
642 }
643 
644 namespace {
645 
646 /// The pass. Most of the work is delegated to the per-loop
647 /// LoadEliminationForLoop class.
648 class LoopLoadElimination : public FunctionPass {
649 public:
650  static char ID;
651 
652  LoopLoadElimination() : FunctionPass(ID) {
654  }
655 
656  bool runOnFunction(Function &F) override {
657  if (skipFunction(F))
658  return false;
659 
660  auto &LI = getAnalysis<LoopInfoWrapperPass>().getLoopInfo();
661  auto &LAA = getAnalysis<LoopAccessLegacyAnalysis>();
662  auto &DT = getAnalysis<DominatorTreeWrapperPass>().getDomTree();
663  auto *PSI = &getAnalysis<ProfileSummaryInfoWrapperPass>().getPSI();
664  auto *BFI = (PSI && PSI->hasProfileSummary()) ?
665  &getAnalysis<LazyBlockFrequencyInfoPass>().getBFI() :
666  nullptr;
667  auto *SE = &getAnalysis<ScalarEvolutionWrapperPass>().getSE();
668 
669  // Process each loop nest in the function.
671  F, LI, DT, BFI, PSI, SE, /*AC*/ nullptr,
672  [&LAA](Loop &L) -> const LoopAccessInfo & { return LAA.getInfo(&L); });
673  }
674 
675  void getAnalysisUsage(AnalysisUsage &AU) const override {
686  }
687 };
688 
689 } // end anonymous namespace
690 
692 
693 static const char LLE_name[] = "Loop Load Elimination";
694 
695 INITIALIZE_PASS_BEGIN(LoopLoadElimination, LLE_OPTION, LLE_name, false, false)
700 INITIALIZE_PASS_DEPENDENCY(LoopSimplify)
703 INITIALIZE_PASS_END(LoopLoadElimination, LLE_OPTION, LLE_name, false, false)
704 
706  return new LoopLoadElimination();
707 }
708 
711  auto &SE = AM.getResult<ScalarEvolutionAnalysis>(F);
712  auto &LI = AM.getResult<LoopAnalysis>(F);
713  auto &TTI = AM.getResult<TargetIRAnalysis>(F);
714  auto &DT = AM.getResult<DominatorTreeAnalysis>(F);
715  auto &TLI = AM.getResult<TargetLibraryAnalysis>(F);
716  auto &AA = AM.getResult<AAManager>(F);
717  auto &AC = AM.getResult<AssumptionAnalysis>(F);
718  auto &MAMProxy = AM.getResult<ModuleAnalysisManagerFunctionProxy>(F);
719  auto *PSI = MAMProxy.getCachedResult<ProfileSummaryAnalysis>(*F.getParent());
720  auto *BFI = (PSI && PSI->hasProfileSummary()) ?
721  &AM.getResult<BlockFrequencyAnalysis>(F) : nullptr;
723  ? &AM.getResult<MemorySSAAnalysis>(F).getMSSA()
724  : nullptr;
725 
726  auto &LAM = AM.getResult<LoopAnalysisManagerFunctionProxy>(F).getManager();
727  bool Changed = eliminateLoadsAcrossLoops(
728  F, LI, DT, BFI, PSI, &SE, &AC, [&](Loop &L) -> const LoopAccessInfo & {
729  LoopStandardAnalysisResults AR = {AA, AC, DT, LI, SE,
730  TLI, TTI, nullptr, MSSA};
731  return LAM.getResult<LoopAccessAnalysis>(L, AR);
732  });
733 
734  if (!Changed)
735  return PreservedAnalyses::all();
736 
738  return PA;
739 }
llvm::createLoopLoadEliminationPass
FunctionPass * createLoopLoadEliminationPass()
Definition: LoopLoadElimination.cpp:705
llvm::PreservedAnalyses
A set of analyses that are preserved following a run of a transformation pass.
Definition: PassManager.h:155
llvm::OuterAnalysisManagerProxy
An analysis over an "inner" IR unit that provides access to an analysis manager over a "outer" IR uni...
Definition: PassManager.h:1051
AssumptionCache.h
llvm::AAManager
A manager for alias analyses.
Definition: AliasAnalysis.h:1233
llvm::TargetIRAnalysis
Analysis pass providing the TargetTransformInfo.
Definition: TargetTransformInfo.h:2320
llvm::ScalarEvolutionAnalysis
Analysis pass that exposes the ScalarEvolution for a function.
Definition: ScalarEvolution.h:2105
llvm::LoopAccessLegacyAnalysis
This analysis provides dependence information for the memory accesses of a loop.
Definition: LoopAccessAnalysis.h:717
llvm::LoopLoadEliminationPass::run
PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM)
Definition: LoopLoadElimination.cpp:709
llvm
Definition: AllocatorList.h:23
LoopSimplify.h
llvm::RuntimePointerCheck
std::pair< const RuntimeCheckingPtrGroup *, const RuntimeCheckingPtrGroup * > RuntimePointerCheck
A memcheck which made up of a pair of grouped pointers.
Definition: LoopAccessAnalysis.h:368
llvm::BasicBlock::getParent
const Function * getParent() const
Return the enclosing method, or null if none.
Definition: BasicBlock.h:107
ScalarEvolutionExpander.h
llvm::AnalysisManager::getResult
PassT::Result & getResult(IRUnitT &IR, ExtraArgTs... ExtraArgs)
Get the result of an analysis pass for a given IR unit.
Definition: PassManager.h:769
Scalar.h
llvm::Function
Definition: Function.h:61
llvm::Loop
Represents a single loop in the control flow graph.
Definition: LoopInfo.h:530
Pass.h
llvm::SCEVExpander
This class uses information about analyze scalars to rewrite expressions in canonical form.
Definition: ScalarEvolutionExpander.h:63
llvm::ProfileSummaryInfo::hasProfileSummary
bool hasProfileSummary() const
Returns true if profile summary is available.
Definition: ProfileSummaryInfo.h:68
llvm::PredicatedScalarEvolution
An interface layer with SCEV used to manage how we see SCEV expressions for values in the context of ...
Definition: ScalarEvolution.h:2166
llvm::SmallVector
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
Definition: SmallVector.h:1167
Statistic.h
SizeOpts.h
llvm::TargetTransformInfo
This pass provides access to the codegen interfaces that are needed for IR-level transformations.
Definition: TargetTransformInfo.h:167
LoopAccessAnalysis.h
LazyBlockFrequencyInfo.h
llvm::Type::getPointerAddressSpace
unsigned getPointerAddressSpace() const
Get the address space of this pointer or pointer vector type.
Definition: DerivedTypes.h:728
llvm::erase_if
void erase_if(Container &C, UnaryPredicate P)
Provide a container algorithm similar to C++ Library Fundamentals v2's erase_if which is equivalent t...
Definition: STLExtras.h:1656
llvm::PredicatedScalarEvolution::getUnionPredicate
const SCEVUnionPredicate & getUnionPredicate() const
Definition: ScalarEvolution.cpp:13348
llvm::ScalarEvolution
The main scalar evolution driver.
Definition: ScalarEvolution.h:443
llvm::MemoryDepChecker::generateInstructionOrderMap
DenseMap< Instruction *, unsigned > generateInstructionOrderMap() const
Generate a mapping between the memory instructions and their indices according to program order.
Definition: LoopAccessAnalysis.h:248
llvm::DominatorTree
Concrete subclass of DominatorTreeBase that is used to compute a normal dominator tree.
Definition: Dominators.h:151
GlobalsModRef.h
LLE_name
static const char LLE_name[]
Definition: LoopLoadElimination.cpp:693
llvm::cl::Hidden
@ Hidden
Definition: CommandLine.h:143
llvm::LoopAccessAnalysis
This analysis provides dependence information for the memory accesses of a loop.
Definition: LoopAccessAnalysis.h:759
APInt.h
llvm::LazyBlockFrequencyInfoPass::getLazyBFIAnalysisUsage
static void getLazyBFIAnalysisUsage(AnalysisUsage &AU)
Helper for client passes to set up the analysis usage on behalf of this pass.
Definition: LazyBlockFrequencyInfo.cpp:62
ScalarEvolution.h
llvm::SPII::Load
@ Load
Definition: SparcInstrInfo.h:32
llvm::Type
The instances of the Type class are immutable: once they are created, they are never changed.
Definition: Type.h:46
DenseMap.h
Module.h
llvm::LoopInfoWrapperPass
The legacy pass manager's analysis pass to compute loop information.
Definition: LoopInfo.h:1258
llvm::LoopStandardAnalysisResults
The adaptor from a function pass to a loop pass computes these analyses and makes them available to t...
Definition: LoopAnalysisManager.h:52
llvm::SmallPtrSet< Instruction *, 4 >
STLExtras.h
llvm::EnableMSSALoopDependency
cl::opt< bool > EnableMSSALoopDependency
Enables memory ssa as a dependency for loop passes.
LLVM_DEBUG
#define LLVM_DEBUG(X)
Definition: Debug.h:122
DepthFirstIterator.h
F
#define F(x, y, z)
Definition: MD5.cpp:56
LLE_OPTION
#define LLE_OPTION
Definition: LoopLoadElimination.cpp:71
llvm::LazyBlockFrequencyInfoPass
This is an alternative analysis pass to BlockFrequencyInfoWrapperPass.
Definition: LazyBlockFrequencyInfo.h:100
llvm::BasicBlock
LLVM Basic Block Representation.
Definition: BasicBlock.h:58
LoopAnalysisManager.h
llvm::dbgs
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
Definition: Debug.cpp:132
llvm::DominatorTree::dominates
bool dominates(const BasicBlock *BB, const Use &U) const
Return true if the (end of the) basic block BB dominates the use U.
Definition: Dominators.cpp:115
CommandLine.h
llvm::all_of
bool all_of(R &&range, UnaryPredicate P)
Provide wrappers to std::all_of which take ranges instead of having to pass begin/end explicitly.
Definition: STLExtras.h:1482
llvm::BlockFrequencyInfo
BlockFrequencyInfo pass uses BlockFrequencyInfoImpl implementation to estimate IR basic block frequen...
Definition: BlockFrequencyInfo.h:37
llvm::LoopBase::getLoopLatches
void getLoopLatches(SmallVectorImpl< BlockT * > &LoopLatches) const
Return all loop latch blocks of this loop.
Definition: LoopInfo.h:334
llvm::shouldOptimizeForSize
bool shouldOptimizeForSize(const MachineFunction *MF, ProfileSummaryInfo *PSI, const MachineBlockFrequencyInfo *BFI, PGSOQueryType QueryType=PGSOQueryType::Other)
Returns true if machine function MF is suggested to be size-optimized based on the profile.
Definition: MachineSizeOpts.cpp:183
llvm::PassRegistry::getPassRegistry
static PassRegistry * getPassRegistry()
getPassRegistry - Access the global registry object, which is automatically initialized at applicatio...
Definition: PassRegistry.cpp:31
C
(vector float) vec_cmpeq(*A, *B) C
Definition: README_ALTIVEC.txt:86
llvm::AnalysisUsage
Represent the analysis usage information of a pass.
Definition: PassAnalysisSupport.h:47
llvm::getPtrStride
int64_t getPtrStride(PredicatedScalarEvolution &PSE, Value *Ptr, const Loop *Lp, const ValueToValueMap &StridesMap=ValueToValueMap(), bool Assume=false, bool ShouldCheckWrap=true)
If the pointer has a constant stride return it in units of its element size.
Definition: LoopAccessAnalysis.cpp:1017
TargetLibraryInfo.h
false
Definition: StackSlotColoring.cpp:142
B
static GCRegistry::Add< OcamlGC > B("ocaml", "ocaml 3.10-compatible GC")
llvm::Instruction
Definition: Instruction.h:45
llvm::PGSOQueryType::IRPass
@ IRPass
llvm::DominatorTreeWrapperPass
Legacy analysis pass which computes a DominatorTree.
Definition: Dominators.h:281
llvm::STATISTIC
STATISTIC(NumFunctions, "Total number of functions")
llvm::raw_ostream
This class implements an extremely fast bulk output stream that can only output to a stream.
Definition: raw_ostream.h:50
llvm::operator<<
raw_ostream & operator<<(raw_ostream &OS, const APFixedPoint &FX)
Definition: APFixedPoint.h:230
llvm::ScalarEvolutionWrapperPass
Definition: ScalarEvolution.h:2135
SmallPtrSet.h
llvm::BasicBlock::getModule
const Module * getModule() const
Return the module owning the function this basic block belongs to, or nullptr if the function does no...
Definition: BasicBlock.cpp:144
llvm::MemoryDepChecker::getDependences
const SmallVectorImpl< Dependence > * getDependences() const
Returns the memory dependences.
Definition: LoopAccessAnalysis.h:234
llvm::LoopBase::getExitingBlock
BlockT * getExitingBlock() const
If getExitingBlocks would return exactly one block, return that block.
Definition: LoopInfoImpl.h:49
Utils.h
llvm::BlockFrequencyAnalysis
Analysis pass which computes BlockFrequencyInfo.
Definition: BlockFrequencyInfo.h:112
Type.h
llvm::LoopAccessInfo::hasConvergentOp
bool hasConvergentOp() const
Return true if there is a convergent operation in the loop.
Definition: LoopAccessAnalysis.h:531
INITIALIZE_PASS_END
#define INITIALIZE_PASS_END(passName, arg, name, cfg, analysis)
Definition: PassSupport.h:58
LoopInfo.h
llvm::ProfileSummaryInfo
Analysis providing profile information.
Definition: ProfileSummaryInfo.h:39
llvm::function_ref
An efficient, type-erasing, non-owning reference to a callable.
Definition: STLExtras.h:168
Check
static bool Check(DecodeStatus &Out, DecodeStatus In)
Definition: AArch64Disassembler.cpp:230
llvm::Loop::isLoopSimplifyForm
bool isLoopSimplifyForm() const
Return true if the Loop is in the form that the LoopSimplify form transforms loops to,...
Definition: LoopInfo.cpp:478
llvm::cl::opt
Definition: CommandLine.h:1422
llvm::StoreInst
An instruction for storing to memory.
Definition: Instructions.h:303
llvm::SCEVUnionPredicate::getComplexity
unsigned getComplexity() const override
We estimate the complexity of a union predicate as the size number of predicates in the union.
Definition: ScalarEvolution.h:432
ProfileSummaryInfo.h
llvm::for_each
UnaryFunction for_each(R &&Range, UnaryFunction F)
Provide wrappers to std::for_each which take ranges instead of having to pass begin/end explicitly.
Definition: STLExtras.h:1475
llvm::AssumptionAnalysis
A function analysis which provides an AssumptionCache.
Definition: AssumptionCache.h:169
INITIALIZE_PASS_DEPENDENCY
INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass)
llvm::LoopVersioning
This class emits a version of the loop where run-time checks ensure that may-alias pointers can't ove...
Definition: LoopVersioning.h:40
llvm::PHINode::addIncoming
void addIncoming(Value *V, BasicBlock *BB)
Add an incoming value to the end of the PHI list.
Definition: Instructions.h:2750
llvm::RuntimePointerChecking::getChecks
const SmallVectorImpl< RuntimePointerCheck > & getChecks() const
Returns the checks that generateChecks created.
Definition: LoopAccessAnalysis.h:430
llvm::DenseMap
Definition: DenseMap.h:714
llvm::MemorySSA
Encapsulates MemorySSA, including all data associated with memory accesses.
Definition: MemorySSA.h:704
llvm::LoopAccessInfo::getRuntimePointerChecking
const RuntimePointerChecking * getRuntimePointerChecking() const
Definition: LoopAccessAnalysis.h:533
I
#define I(x, y, z)
Definition: MD5.cpp:59
llvm::cl::init
initializer< Ty > init(const Ty &Val)
Definition: CommandLine.h:443
llvm::LoopAccessInfo
Drive the analysis of memory accesses in the loop.
Definition: LoopAccessAnalysis.h:519
llvm::ProfileSummaryInfoWrapperPass
An analysis pass based on legacy pass manager to deliver ProfileSummaryInfo.
Definition: ProfileSummaryInfo.h:185
llvm::LoopBase::getLoopPreheader
BlockT * getLoopPreheader() const
If there is a preheader for this loop, return it.
Definition: LoopInfoImpl.h:167
llvm::LoopBase::getLoopLatch
BlockT * getLoopLatch() const
If there is a single latch block for this loop, return it.
Definition: LoopInfoImpl.h:216
assert
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
llvm::PredicatedScalarEvolution::getSCEV
const SCEV * getSCEV(Value *V)
Returns the SCEV expression of V, in the context of the current SCEV predicate.
Definition: ScalarEvolution.cpp:13313
llvm::MemoryDepChecker::getMemoryInstructions
const SmallVectorImpl< Instruction * > & getMemoryInstructions() const
The vector of memory access instructions.
Definition: LoopAccessAnalysis.h:242
std::swap
void swap(llvm::BitVector &LHS, llvm::BitVector &RHS)
Implement std::swap in terms of BitVector swap.
Definition: BitVector.h:840
llvm::TTI
TargetTransformInfo TTI
Definition: TargetTransformInfo.h:162
llvm::MemorySSAAnalysis
An analysis that produces MemorySSA for a function.
Definition: MemorySSA.h:922
doesStoreDominatesAllLatches
static bool doesStoreDominatesAllLatches(BasicBlock *StoreBlock, Loop *L, DominatorTree *DT)
Check if the store dominates all latches, so as long as there is no intervening store this value will...
Definition: LoopLoadElimination.cpp:147
llvm::SmallPtrSetImpl::count
size_type count(ConstPtrType Ptr) const
count - Return 1 if the specified pointer is in the set, 0 otherwise.
Definition: SmallPtrSet.h:382
llvm::APInt
Class for arbitrary precision integers.
Definition: APInt.h:70
llvm::SCEVUnionPredicate::isAlwaysTrue
bool isAlwaysTrue() const override
Implementation of the SCEVPredicate interface.
Definition: ScalarEvolution.cpp:13257
llvm::ProfileSummaryAnalysis
An analysis pass based on the new PM to deliver ProfileSummaryInfo.
Definition: ProfileSummaryInfo.h:203
llvm::LoopAccessInfo::getDepChecker
const MemoryDepChecker & getDepChecker() const
the Memory Dependence Checker which can determine the loop-independent and loop-carried dependences b...
Definition: LoopAccessAnalysis.h:561
llvm::Sched::Source
@ Source
Definition: TargetLowering.h:99
llvm::LoopInfo
Definition: LoopInfo.h:1080
DataLayout.h
llvm::AssumptionCache
A cache of @llvm.assume calls within a function.
Definition: AssumptionCache.h:41
llvm::Value::getType
Type * getType() const
All values are typed, get the type of this value.
Definition: Value.h:256
if
if(llvm_vc STREQUAL "") set(fake_version_inc "$
Definition: CMakeLists.txt:14
llvm::AnalysisUsage::addPreserved
AnalysisUsage & addPreserved()
Add the specified Pass class to the set of analyses preserved by this pass.
Definition: PassAnalysisSupport.h:98
DL
MachineBasicBlock MachineBasicBlock::iterator DebugLoc DL
Definition: AArch64SLSHardening.cpp:76
SEE
#define SEE(c)
Definition: regcomp.c:254
isLoadConditional
static bool isLoadConditional(LoadInst *Load, Loop *L)
Return true if the load is not executed on all paths in the loop.
Definition: LoopLoadElimination.cpp:157
S
add sub stmia L5 ldr r0 bl L_printf $stub Instead of a and a wouldn t it be better to do three moves *Return an aggregate type is even return S
Definition: README.txt:210
BlockFrequencyInfo.h
llvm::AMDGPUISD::BFI
@ BFI
Definition: AMDGPUISelLowering.h:418
LoadElimSCEVCheckThreshold
static cl::opt< unsigned > LoadElimSCEVCheckThreshold("loop-load-elimination-scev-check-threshold", cl::init(8), cl::Hidden, cl::desc("The maximum number of SCEV checks allowed for Loop " "Load Elimination"))
llvm::Value::getName
StringRef getName() const
Return a constant reference to the value's name.
Definition: Value.cpp:294
for
this could be done in SelectionDAGISel along with other special for
Definition: README.txt:104
llvm::LoadInst
An instruction for reading from memory.
Definition: Instructions.h:174
llvm::DenseMapBase::insert
std::pair< iterator, bool > insert(const std::pair< KeyT, ValueT > &KV)
Definition: DenseMap.h:207
LAM
LoopAnalysisManager LAM
Definition: PassBuilderBindings.cpp:58
llvm::BasicBlock::front
const Instruction & front() const
Definition: BasicBlock.h:308
llvm::depth_first
iterator_range< df_iterator< T > > depth_first(const T &G)
Definition: DepthFirstIterator.h:229
llvm::MemoryDepChecker::Dependence::Unknown
@ Unknown
Definition: LoopAccessAnalysis.h:114
runOnFunction
static bool runOnFunction(Function &F, bool PostInlining)
Definition: EntryExitInstrumenter.cpp:69
llvm::LoopBase::isInnermost
bool isInnermost() const
Return true if the loop does not contain any (natural) loops.
Definition: LoopInfo.h:165
LoopLoadElimination.h
llvm::LoopSimplifyID
char & LoopSimplifyID
Definition: LoopSimplify.cpp:801
CheckPerElim
static cl::opt< unsigned > CheckPerElim("runtime-check-per-loop-load-elim", cl::Hidden, cl::desc("Max number of memchecks allowed per eliminated load on average"), cl::init(1))
llvm::copy_if
OutputIt copy_if(R &&Range, OutputIt Out, UnaryPredicate P)
Provide wrappers to std::copy_if which take ranges instead of having to pass begin/end explicitly.
Definition: STLExtras.h:1528
llvm::ScalarEvolution::getMinusSCEV
const SCEV * getMinusSCEV(const SCEV *LHS, const SCEV *RHS, SCEV::NoWrapFlags Flags=SCEV::FlagAnyWrap, unsigned Depth=0)
Return LHS-RHS. Minus is represented in SCEV as A+B*-1.
Definition: ScalarEvolution.cpp:4076
llvm::RuntimePointerChecking::PointerInfo::PointerValue
TrackingVH< Value > PointerValue
Holds the pointer value that we need to check.
Definition: LoopAccessAnalysis.h:378
llvm::PreservedAnalyses::all
static PreservedAnalyses all()
Construct a special preserved set that preserves all passes.
Definition: PassManager.h:161
llvm::PHINode::Create
static PHINode * Create(Type *Ty, unsigned NumReservedValues, const Twine &NameStr="", Instruction *InsertBefore=nullptr)
Constructors - NumReservedValues is a hint for the number of incoming edges that this phi node will h...
Definition: Instructions.h:2642
llvm::RuntimePointerChecking::printChecks
void printChecks(raw_ostream &OS, const SmallVectorImpl< RuntimePointerCheck > &Checks, unsigned Depth=0) const
Print Checks.
Definition: LoopAccessAnalysis.cpp:458
Casting.h
llvm::LoopBase::getHeader
BlockT * getHeader() const
Definition: LoopInfo.h:104
PassManager.h
llvm::simplifyLoop
bool simplifyLoop(Loop *L, DominatorTree *DT, LoopInfo *LI, ScalarEvolution *SE, AssumptionCache *AC, MemorySSAUpdater *MSSAU, bool PreserveLCSSA)
Simplify each loop in a loop nest recursively.
Definition: LoopSimplify.cpp:719
LoopVersioning.h
llvm::SPII::Store
@ Store
Definition: SparcInstrInfo.h:33
ScalarEvolutionExpressions.h
llvm::DominatorTreeAnalysis
Analysis pass which computes a DominatorTree.
Definition: Dominators.h:252
MemorySSA.h
Instructions.h
INITIALIZE_PASS_BEGIN
#define INITIALIZE_PASS_BEGIN(passName, arg, name, cfg, analysis)
Definition: PassSupport.h:51
SmallVector.h
llvm::raw_ostream::indent
raw_ostream & indent(unsigned NumSpaces)
indent - Insert 'NumSpaces' spaces.
Definition: raw_ostream.cpp:497
Dominators.h
llvm::Type::getPointerElementType
Type * getPointerElementType() const
Definition: Type.h:378
llvm::SmallPtrSetImplBase::empty
LLVM_NODISCARD bool empty() const
Definition: SmallPtrSet.h:91
llvm::GlobalsAAWrapperPass
Legacy wrapper pass to provide the GlobalsAAResult object.
Definition: GlobalsModRef.h:143
TargetTransformInfo.h
llvm::PHINode
Definition: Instructions.h:2600
llvm::RuntimePointerChecking::getPointerInfo
const PointerInfo & getPointerInfo(unsigned PtrIdx) const
Return PointerInfo for pointer at index PtrIdx.
Definition: LoopAccessAnalysis.h:473
llvm::SmallVectorImpl
This class consists of common code factored out of the SmallVector class to reduce code duplication b...
Definition: APFloat.h:43
llvm::Module::getDataLayout
const DataLayout & getDataLayout() const
Get the data layout for the module's target platform.
Definition: Module.cpp:397
llvm::SmallPtrSetImpl< Value * >
llvm::AnalysisManager
A container for analyses that lazily runs them and caches their results.
Definition: InstructionSimplify.h:44
llvm::InnerAnalysisManagerProxy
An analysis over an "outer" IR unit that provides access to an analysis manager over an "inner" IR un...
Definition: PassManager.h:926
llvm::FunctionPass
FunctionPass class - This class is used to implement most global optimizations.
Definition: Pass.h:298
llvm::AnalysisUsage::addRequiredID
AnalysisUsage & addRequiredID(const void *ID)
Definition: Pass.cpp:267
llvm::AnalysisUsage::addRequired
AnalysisUsage & addRequired()
Definition: PassAnalysisSupport.h:75
llvm::Loop::isRotatedForm
bool isRotatedForm() const
Return true if the loop is in rotated form.
Definition: LoopInfo.h:785
eliminateLoadsAcrossLoops
static bool eliminateLoadsAcrossLoops(Function &F, LoopInfo &LI, DominatorTree &DT, BlockFrequencyInfo *BFI, ProfileSummaryInfo *PSI, ScalarEvolution *SE, AssumptionCache *AC, function_ref< const LoopAccessInfo &(Loop &)> GetLAI)
Definition: LoopLoadElimination.cpp:611
llvm::cl::desc
Definition: CommandLine.h:414
llvm::LoopAccessInfo::getPSE
const PredicatedScalarEvolution & getPSE() const
Used to add runtime SCEV checks.
Definition: LoopAccessAnalysis.h:591
raw_ostream.h
llvm::PredicatedScalarEvolution::getSE
ScalarEvolution * getSE() const
Returns the ScalarEvolution analysis used.
Definition: ScalarEvolution.h:2198
llvm::initializeLoopLoadEliminationPass
void initializeLoopLoadEliminationPass(PassRegistry &)
Value.h
InitializePasses.h
llvm::Value
LLVM Value Representation.
Definition: Value.h:75
Debug.h
llvm::TargetLibraryAnalysis
Analysis pass providing the TargetLibraryInfo.
Definition: TargetLibraryInfo.h:438
llvm::LoopAnalysis
Analysis pass that exposes the LoopInfo for a function.
Definition: LoopInfo.h:1233
llvm::SmallPtrSetImpl::insert
std::pair< iterator, bool > insert(PtrType Ptr)
Inserts Ptr if and only if there is no element in the container equal to Ptr.
Definition: SmallPtrSet.h:364
llvm::Intrinsic::ID
unsigned ID
Definition: TargetTransformInfo.h:38