1 //===- LoopLoadElimination.cpp - Loop Load Elimination Pass ---------------===//
3 // The LLVM Compiler Infrastructure
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
8 //===----------------------------------------------------------------------===//
10 // This file implement a loop-aware load elimination pass.
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.
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
21 //===----------------------------------------------------------------------===//
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>
34 #define LLE_OPTION "loop-load-elim"
35 #define DEBUG_TYPE LLE_OPTION
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"),
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 "
50 STATISTIC(NumLoopLoadEliminted, "Number of loads eliminated by LLE");
54 /// \brief Represent a store-to-forwarding candidate.
55 struct StoreToLoadForwardingCandidate {
59 StoreToLoadForwardingCandidate(LoadInst *Load, StoreInst *Store)
60 : Load(Load), Store(Store) {}
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();
70 assert(LoadPtrType->getPointerAddressSpace() ==
71 StorePtr->getType()->getPointerAddressSpace() &&
72 LoadType == StorePtr->getType()->getPointerElementType() &&
73 "Should be a known dependence");
75 auto &DL = Load->getParent()->getModule()->getDataLayout();
76 unsigned TypeByteSize = DL.getTypeAllocSize(const_cast<Type *>(LoadType));
78 auto *LoadPtrSCEV = cast<SCEVAddRecExpr>(PSE.getSCEV(LoadPtr));
79 auto *StorePtrSCEV = cast<SCEVAddRecExpr>(PSE.getSCEV(StorePtr));
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->getValue()->getValue();
86 return Val.abs() == TypeByteSize;
89 Value *getLoadPtr() const { return Load->getPointerOperand(); }
92 friend raw_ostream &operator<<(raw_ostream &OS,
93 const StoreToLoadForwardingCandidate &Cand) {
94 OS << *Cand.Store << " -->\n";
95 OS.indent(2) << *Cand.Load << "\n";
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,
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);
113 /// \brief The per-loop class that does most of the work.
114 class LoadEliminationForLoop {
116 LoadEliminationForLoop(Loop *L, LoopInfo *LI, const LoopAccessInfo &LAI,
118 : L(L), LI(LI), LAI(LAI), DT(DT), PSE(LAI.PSE) {}
120 /// \brief Look through the loop-carried and loop-independent dependences in
121 /// this loop and find store->load dependences.
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;
129 const auto *Deps = LAI.getDepChecker().getDependences();
133 // Find store->load dependences (consequently true dep). Both lexically
134 // forward and backward dependences qualify. Disqualify loads that have
135 // other unknown dependences.
137 SmallSet<Instruction *, 4> LoadsWithUnknownDepedence;
139 for (const auto &Dep : *Deps) {
140 Instruction *Source = Dep.getSource(LAI);
141 Instruction *Destination = Dep.getDestination(LAI);
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);
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
155 std::swap(Source, Destination);
157 assert(Dep.isForward() && "Needs to be a forward dependence");
159 auto *Store = dyn_cast<StoreInst>(Source);
162 auto *Load = dyn_cast<LoadInst>(Destination);
165 Candidates.emplace_front(Load, Store);
168 if (!LoadsWithUnknownDepedence.empty())
169 Candidates.remove_if([&](const StoreToLoadForwardingCandidate &C) {
170 return LoadsWithUnknownDepedence.count(C.Load);
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");
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.
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.
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.
198 /// A[i+1] = ... (S3)
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
206 typedef DenseMap<LoadInst *, const StoreToLoadForwardingCandidate *>
208 LoadToSingleCandT LoadToSingleCand;
210 for (const auto &Cand : Candidates) {
212 LoadToSingleCandT::iterator Iter;
214 std::tie(Iter, NewElt) =
215 LoadToSingleCand.insert(std::make_pair(Cand.Load, &Cand));
217 const StoreToLoadForwardingCandidate *&OtherCand = Iter->second;
218 // Already multiple stores forward to this load.
219 if (OtherCand == nullptr)
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))
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 "
247 /// \brief Given two pointers operations by their RuntimePointerChecking
248 /// indices, return true if they require an alias check.
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) {
256 LAI.getRuntimePointerChecking()->getPointerInfo(PtrIdx1).PointerValue;
258 LAI.getRuntimePointerChecking()->getPointerInfo(PtrIdx2).PointerValue;
259 return ((PtrsWrittenOnFwdingPath.count(Ptr1) && CandLoadPtrs.count(Ptr2)) ||
260 (PtrsWrittenOnFwdingPath.count(Ptr2) && CandLoadPtrs.count(Ptr1)));
263 /// \brief Return pointers that are possibly written to on the path from a
264 /// forwarding store to a load.
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.
275 // ld1 B[i] <-------,
276 // ld0 A[i] <----, | * LastLoad
279 // st3 B[i+1] -- | -' * FirstStore
283 // st0 forwards to ld0 if the accesses in st4 and st1 don't overlap with
287 std::max_element(Candidates.begin(), Candidates.end(),
288 [&](const StoreToLoadForwardingCandidate &A,
289 const StoreToLoadForwardingCandidate &B) {
290 return getInstrIndex(A.Load) < getInstrIndex(B.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);
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;
307 auto InsertStorePtr = [&](Instruction *I) {
308 if (auto *S = dyn_cast<StoreInst>(I))
309 PtrsWrittenOnFwdingPath.insert(S->getPointerOperand());
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)],
317 return PtrsWrittenOnFwdingPath;
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) {
325 SmallSet<Value *, 4> PtrsWrittenOnFwdingPath =
326 findPointersWrittenOnForwardingPath(Candidates);
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));
335 const auto &AllChecks = LAI.getRuntimePointerChecking()->getChecks();
336 SmallVector<RuntimePointerChecking::PointerCheck, 4> Checks;
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))
348 DEBUG(dbgs() << "\nPointer Checks (count: " << Checks.size() << "):\n");
349 DEBUG(LAI.getRuntimePointerChecking()->printChecks(dbgs(), Checks));
354 /// \brief Perform the transformation for a candidate.
356 propagateStoredValueToLoadUsers(const StoreToLoadForwardingCandidate &Cand,
362 // store %y, %gep_i_plus_1
367 // %x.initial = load %gep_0
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
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());
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());
386 Cand.Load->replaceAllUsesWith(PHI);
389 /// \brief Top-level driver for each loop: find store->load forwarding
390 /// candidates, add run-time checks and perform transformation.
392 DEBUG(dbgs() << "\nIn \"" << L->getHeader()->getParent()->getName()
393 << "\" checking " << *L << "\n");
394 // Look for store-to-load forwarding cases across the
400 // store %y, %gep_i_plus_1
405 // %x.initial = load %gep_0
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
412 // First start with store->load dependences.
413 auto StoreToLoadDependences = findStoreToLoadDependences(LAI);
414 if (StoreToLoadDependences.empty())
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();
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())
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))
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))
445 << ". Valid store-to-load forwarding across the loop backedge\n");
446 Candidates.push_back(Cand);
448 if (Candidates.empty())
451 // Check intervening may-alias stores. These need runtime checks for alias
453 SmallVector<RuntimePointerChecking::PointerCheck, 4> Checks =
454 collectMemchecks(Candidates);
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");
462 if (LAI.PSE.getUnionPredicate().getComplexity() >
463 LoadElimSCEVCheckThreshold) {
464 DEBUG(dbgs() << "Too many SCEV run-time checks needed.\n");
468 // Point of no-return, start the transformation. First, version the loop if
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());
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(),
481 for (const auto &Cand : Candidates)
482 propagateStoredValueToLoadUsers(Cand, SEE);
483 NumLoopLoadEliminted += NumForwarding;
491 /// \brief Maps the load/store instructions to their index according to
493 DenseMap<Instruction *, unsigned> InstOrder;
497 const LoopAccessInfo &LAI;
499 PredicatedScalarEvolution PSE;
502 /// \brief The pass. Most of the work is delegated to the per-loop
503 /// LoadEliminationForLoop class.
504 class LoopLoadElimination : public FunctionPass {
506 LoopLoadElimination() : FunctionPass(ID) {
507 initializeLoopLoadEliminationPass(*PassRegistry::getPassRegistry());
510 bool runOnFunction(Function &F) override {
511 auto *LI = &getAnalysis<LoopInfoWrapperPass>().getLoopInfo();
512 auto *LAA = &getAnalysis<LoopAccessAnalysis>();
513 auto *DT = &getAnalysis<DominatorTreeWrapperPass>().getDomTree();
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
518 SmallVector<Loop *, 8> Worklist;
520 for (Loop *TopLevelLoop : *LI)
521 for (Loop *L : depth_first(TopLevelLoop))
522 // We only handle inner-most loops.
524 Worklist.push_back(L);
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();
535 // Process each loop nest in the function.
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>();
552 char LoopLoadElimination::ID;
553 static const char LLE_name[] = "Loop Load Elimination";
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)
563 FunctionPass *createLoopLoadEliminationPass() {
564 return new LoopLoadElimination();