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