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