contrib/llvm/lib/Transforms/Scalar/LoopLoadElimination.cpp

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