1//===- LoopLoadElimination.cpp - Loop Load Elimination Pass ---------------===//
2//
3// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4// See https://llvm.org/LICENSE.txt for license information.
5// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6//
7//===----------------------------------------------------------------------===//
8//
9// This file implement a loop-aware load elimination pass.
10//
11// It uses LoopAccessAnalysis to identify loop-carried dependences with a
12// distance of one between stores and loads. These form the candidates for the
13// transformation. The source value of each store then propagated to the user
14// of the corresponding load. This makes the load dead.
15//
16// The pass can also version the loop and add memchecks in order to prove that
17// may-aliasing stores can't change the value in memory before it's read by the
18// load.
19//
20//===----------------------------------------------------------------------===//
21
22#include "llvm/Transforms/Scalar/LoopLoadElimination.h"
23#include "llvm/ADT/APInt.h"
24#include "llvm/ADT/DenseMap.h"
25#include "llvm/ADT/DepthFirstIterator.h"
26#include "llvm/ADT/STLExtras.h"
27#include "llvm/ADT/SmallPtrSet.h"
28#include "llvm/ADT/SmallVector.h"
29#include "llvm/ADT/Statistic.h"
30#include "llvm/Analysis/AssumptionCache.h"
31#include "llvm/Analysis/BlockFrequencyInfo.h"
32#include "llvm/Analysis/GlobalsModRef.h"
33#include "llvm/Analysis/LazyBlockFrequencyInfo.h"
34#include "llvm/Analysis/LoopAccessAnalysis.h"
35#include "llvm/Analysis/LoopAnalysisManager.h"
36#include "llvm/Analysis/LoopInfo.h"
37#include "llvm/Analysis/ProfileSummaryInfo.h"
38#include "llvm/Analysis/ScalarEvolution.h"
39#include "llvm/Analysis/ScalarEvolutionExpressions.h"
40#include "llvm/Analysis/TargetLibraryInfo.h"
41#include "llvm/Analysis/TargetTransformInfo.h"
42#include "llvm/IR/DataLayout.h"
43#include "llvm/IR/Dominators.h"
44#include "llvm/IR/Instructions.h"
45#include "llvm/IR/Module.h"
46#include "llvm/IR/PassManager.h"
47#include "llvm/IR/Type.h"
48#include "llvm/IR/Value.h"
49#include "llvm/Support/Casting.h"
50#include "llvm/Support/CommandLine.h"
51#include "llvm/Support/Debug.h"
52#include "llvm/Support/raw_ostream.h"
53#include "llvm/Transforms/Utils.h"
54#include "llvm/Transforms/Utils/LoopSimplify.h"
55#include "llvm/Transforms/Utils/LoopVersioning.h"
56#include "llvm/Transforms/Utils/ScalarEvolutionExpander.h"
57#include "llvm/Transforms/Utils/SizeOpts.h"
58#include <algorithm>
59#include <cassert>
60#include <forward_list>
61#include <tuple>
62#include <utility>
63
64using namespace llvm;
65
66#define LLE_OPTION "loop-load-elim"
67#define DEBUG_TYPE LLE_OPTION
68
69static cl::opt<unsigned> CheckPerElim(
70 "runtime-check-per-loop-load-elim", cl::Hidden,
71 cl::desc("Max number of memchecks allowed per eliminated load on average"),
72 cl::init(Val: 1));
73
74static cl::opt<unsigned> LoadElimSCEVCheckThreshold(
75 "loop-load-elimination-scev-check-threshold", cl::init(Val: 8), cl::Hidden,
76 cl::desc("The maximum number of SCEV checks allowed for Loop "
77 "Load Elimination"));
78
79STATISTIC(NumLoopLoadEliminted, "Number of loads eliminated by LLE");
80
81namespace {
82
83/// Represent a store-to-forwarding candidate.
84struct StoreToLoadForwardingCandidate {
85 LoadInst *Load;
86 StoreInst *Store;
87
88 StoreToLoadForwardingCandidate(LoadInst *Load, StoreInst *Store)
89 : Load(Load), Store(Store) {}
90
91 /// Return true if the dependence from the store to the load has an
92 /// absolute distance of one.
93 /// E.g. A[i+1] = A[i] (or A[i-1] = A[i] for descending loop)
94 bool isDependenceDistanceOfOne(PredicatedScalarEvolution &PSE,
95 Loop *L) const {
96 Value *LoadPtr = Load->getPointerOperand();
97 Value *StorePtr = Store->getPointerOperand();
98 Type *LoadType = getLoadStoreType(I: Load);
99 auto &DL = Load->getParent()->getModule()->getDataLayout();
100
101 assert(LoadPtr->getType()->getPointerAddressSpace() ==
102 StorePtr->getType()->getPointerAddressSpace() &&
103 DL.getTypeSizeInBits(LoadType) ==
104 DL.getTypeSizeInBits(getLoadStoreType(Store)) &&
105 "Should be a known dependence");
106
107 int64_t StrideLoad = getPtrStride(PSE, AccessTy: LoadType, Ptr: LoadPtr, Lp: L).value_or(u: 0);
108 int64_t StrideStore = getPtrStride(PSE, AccessTy: LoadType, Ptr: StorePtr, Lp: L).value_or(u: 0);
109 if (!StrideLoad || !StrideStore || StrideLoad != StrideStore)
110 return false;
111
112 // TODO: This check for stride values other than 1 and -1 can be eliminated.
113 // However, doing so may cause the LoopAccessAnalysis to overcompensate,
114 // generating numerous non-wrap runtime checks that may undermine the
115 // benefits of load elimination. To safely implement support for non-unit
116 // strides, we would need to ensure either that the processed case does not
117 // require these additional checks, or improve the LAA to handle them more
118 // efficiently, or potentially both.
119 if (std::abs(i: StrideLoad) != 1)
120 return false;
121
122 unsigned TypeByteSize = DL.getTypeAllocSize(Ty: const_cast<Type *>(LoadType));
123
124 auto *LoadPtrSCEV = cast<SCEVAddRecExpr>(Val: PSE.getSCEV(V: LoadPtr));
125 auto *StorePtrSCEV = cast<SCEVAddRecExpr>(Val: PSE.getSCEV(V: StorePtr));
126
127 // We don't need to check non-wrapping here because forward/backward
128 // dependence wouldn't be valid if these weren't monotonic accesses.
129 auto *Dist = cast<SCEVConstant>(
130 Val: PSE.getSE()->getMinusSCEV(LHS: StorePtrSCEV, RHS: LoadPtrSCEV));
131 const APInt &Val = Dist->getAPInt();
132 return Val == TypeByteSize * StrideLoad;
133 }
134
135 Value *getLoadPtr() const { return Load->getPointerOperand(); }
136
137#ifndef NDEBUG
138 friend raw_ostream &operator<<(raw_ostream &OS,
139 const StoreToLoadForwardingCandidate &Cand) {
140 OS << *Cand.Store << " -->\n";
141 OS.indent(NumSpaces: 2) << *Cand.Load << "\n";
142 return OS;
143 }
144#endif
145};
146
147} // end anonymous namespace
148
149/// Check if the store dominates all latches, so as long as there is no
150/// intervening store this value will be loaded in the next iteration.
151static bool doesStoreDominatesAllLatches(BasicBlock *StoreBlock, Loop *L,
152 DominatorTree *DT) {
153 SmallVector<BasicBlock *, 8> Latches;
154 L->getLoopLatches(LoopLatches&: Latches);
155 return llvm::all_of(Range&: Latches, P: [&](const BasicBlock *Latch) {
156 return DT->dominates(A: StoreBlock, B: Latch);
157 });
158}
159
160/// Return true if the load is not executed on all paths in the loop.
161static bool isLoadConditional(LoadInst *Load, Loop *L) {
162 return Load->getParent() != L->getHeader();
163}
164
165namespace {
166
167/// The per-loop class that does most of the work.
168class LoadEliminationForLoop {
169public:
170 LoadEliminationForLoop(Loop *L, LoopInfo *LI, const LoopAccessInfo &LAI,
171 DominatorTree *DT, BlockFrequencyInfo *BFI,
172 ProfileSummaryInfo* PSI)
173 : L(L), LI(LI), LAI(LAI), DT(DT), BFI(BFI), PSI(PSI), PSE(LAI.getPSE()) {}
174
175 /// Look through the loop-carried and loop-independent dependences in
176 /// this loop and find store->load dependences.
177 ///
178 /// Note that no candidate is returned if LAA has failed to analyze the loop
179 /// (e.g. if it's not bottom-tested, contains volatile memops, etc.)
180 std::forward_list<StoreToLoadForwardingCandidate>
181 findStoreToLoadDependences(const LoopAccessInfo &LAI) {
182 std::forward_list<StoreToLoadForwardingCandidate> Candidates;
183
184 const auto *Deps = LAI.getDepChecker().getDependences();
185 if (!Deps)
186 return Candidates;
187
188 // Find store->load dependences (consequently true dep). Both lexically
189 // forward and backward dependences qualify. Disqualify loads that have
190 // other unknown dependences.
191
192 SmallPtrSet<Instruction *, 4> LoadsWithUnknownDepedence;
193
194 for (const auto &Dep : *Deps) {
195 Instruction *Source = Dep.getSource(LAI);
196 Instruction *Destination = Dep.getDestination(LAI);
197
198 if (Dep.Type == MemoryDepChecker::Dependence::Unknown ||
199 Dep.Type == MemoryDepChecker::Dependence::IndirectUnsafe) {
200 if (isa<LoadInst>(Val: Source))
201 LoadsWithUnknownDepedence.insert(Ptr: Source);
202 if (isa<LoadInst>(Val: Destination))
203 LoadsWithUnknownDepedence.insert(Ptr: Destination);
204 continue;
205 }
206
207 if (Dep.isBackward())
208 // Note that the designations source and destination follow the program
209 // order, i.e. source is always first. (The direction is given by the
210 // DepType.)
211 std::swap(a&: Source, b&: Destination);
212 else
213 assert(Dep.isForward() && "Needs to be a forward dependence");
214
215 auto *Store = dyn_cast<StoreInst>(Val: Source);
216 if (!Store)
217 continue;
218 auto *Load = dyn_cast<LoadInst>(Val: Destination);
219 if (!Load)
220 continue;
221
222 // Only propagate if the stored values are bit/pointer castable.
223 if (!CastInst::isBitOrNoopPointerCastable(
224 SrcTy: getLoadStoreType(I: Store), DestTy: getLoadStoreType(I: Load),
225 DL: Store->getParent()->getModule()->getDataLayout()))
226 continue;
227
228 Candidates.emplace_front(args&: Load, args&: Store);
229 }
230
231 if (!LoadsWithUnknownDepedence.empty())
232 Candidates.remove_if(pred: [&](const StoreToLoadForwardingCandidate &C) {
233 return LoadsWithUnknownDepedence.count(Ptr: C.Load);
234 });
235
236 return Candidates;
237 }
238
239 /// Return the index of the instruction according to program order.
240 unsigned getInstrIndex(Instruction *Inst) {
241 auto I = InstOrder.find(Val: Inst);
242 assert(I != InstOrder.end() && "No index for instruction");
243 return I->second;
244 }
245
246 /// If a load has multiple candidates associated (i.e. different
247 /// stores), it means that it could be forwarding from multiple stores
248 /// depending on control flow. Remove these candidates.
249 ///
250 /// Here, we rely on LAA to include the relevant loop-independent dependences.
251 /// LAA is known to omit these in the very simple case when the read and the
252 /// write within an alias set always takes place using the *same* pointer.
253 ///
254 /// However, we know that this is not the case here, i.e. we can rely on LAA
255 /// to provide us with loop-independent dependences for the cases we're
256 /// interested. Consider the case for example where a loop-independent
257 /// dependece S1->S2 invalidates the forwarding S3->S2.
258 ///
259 /// A[i] = ... (S1)
260 /// ... = A[i] (S2)
261 /// A[i+1] = ... (S3)
262 ///
263 /// LAA will perform dependence analysis here because there are two
264 /// *different* pointers involved in the same alias set (&A[i] and &A[i+1]).
265 void removeDependencesFromMultipleStores(
266 std::forward_list<StoreToLoadForwardingCandidate> &Candidates) {
267 // If Store is nullptr it means that we have multiple stores forwarding to
268 // this store.
269 using LoadToSingleCandT =
270 DenseMap<LoadInst *, const StoreToLoadForwardingCandidate *>;
271 LoadToSingleCandT LoadToSingleCand;
272
273 for (const auto &Cand : Candidates) {
274 bool NewElt;
275 LoadToSingleCandT::iterator Iter;
276
277 std::tie(args&: Iter, args&: NewElt) =
278 LoadToSingleCand.insert(KV: std::make_pair(x: Cand.Load, y: &Cand));
279 if (!NewElt) {
280 const StoreToLoadForwardingCandidate *&OtherCand = Iter->second;
281 // Already multiple stores forward to this load.
282 if (OtherCand == nullptr)
283 continue;
284
285 // Handle the very basic case when the two stores are in the same block
286 // so deciding which one forwards is easy. The later one forwards as
287 // long as they both have a dependence distance of one to the load.
288 if (Cand.Store->getParent() == OtherCand->Store->getParent() &&
289 Cand.isDependenceDistanceOfOne(PSE, L) &&
290 OtherCand->isDependenceDistanceOfOne(PSE, L)) {
291 // They are in the same block, the later one will forward to the load.
292 if (getInstrIndex(Inst: OtherCand->Store) < getInstrIndex(Inst: Cand.Store))
293 OtherCand = &Cand;
294 } else
295 OtherCand = nullptr;
296 }
297 }
298
299 Candidates.remove_if(pred: [&](const StoreToLoadForwardingCandidate &Cand) {
300 if (LoadToSingleCand[Cand.Load] != &Cand) {
301 LLVM_DEBUG(
302 dbgs() << "Removing from candidates: \n"
303 << Cand
304 << " The load may have multiple stores forwarding to "
305 << "it\n");
306 return true;
307 }
308 return false;
309 });
310 }
311
312 /// Given two pointers operations by their RuntimePointerChecking
313 /// indices, return true if they require an alias check.
314 ///
315 /// We need a check if one is a pointer for a candidate load and the other is
316 /// a pointer for a possibly intervening store.
317 bool needsChecking(unsigned PtrIdx1, unsigned PtrIdx2,
318 const SmallPtrSetImpl<Value *> &PtrsWrittenOnFwdingPath,
319 const SmallPtrSetImpl<Value *> &CandLoadPtrs) {
320 Value *Ptr1 =
321 LAI.getRuntimePointerChecking()->getPointerInfo(PtrIdx: PtrIdx1).PointerValue;
322 Value *Ptr2 =
323 LAI.getRuntimePointerChecking()->getPointerInfo(PtrIdx: PtrIdx2).PointerValue;
324 return ((PtrsWrittenOnFwdingPath.count(Ptr: Ptr1) && CandLoadPtrs.count(Ptr: Ptr2)) ||
325 (PtrsWrittenOnFwdingPath.count(Ptr: Ptr2) && CandLoadPtrs.count(Ptr: Ptr1)));
326 }
327
328 /// Return pointers that are possibly written to on the path from a
329 /// forwarding store to a load.
330 ///
331 /// These pointers need to be alias-checked against the forwarding candidates.
332 SmallPtrSet<Value *, 4> findPointersWrittenOnForwardingPath(
333 const SmallVectorImpl<StoreToLoadForwardingCandidate> &Candidates) {
334 // From FirstStore to LastLoad neither of the elimination candidate loads
335 // should overlap with any of the stores.
336 //
337 // E.g.:
338 //
339 // st1 C[i]
340 // ld1 B[i] <-------,
341 // ld0 A[i] <----, | * LastLoad
342 // ... | |
343 // st2 E[i] | |
344 // st3 B[i+1] -- | -' * FirstStore
345 // st0 A[i+1] ---'
346 // st4 D[i]
347 //
348 // st0 forwards to ld0 if the accesses in st4 and st1 don't overlap with
349 // ld0.
350
351 LoadInst *LastLoad =
352 llvm::max_element(Range: Candidates,
353 C: [&](const StoreToLoadForwardingCandidate &A,
354 const StoreToLoadForwardingCandidate &B) {
355 return getInstrIndex(Inst: A.Load) <
356 getInstrIndex(Inst: B.Load);
357 })
358 ->Load;
359 StoreInst *FirstStore =
360 llvm::min_element(Range: Candidates,
361 C: [&](const StoreToLoadForwardingCandidate &A,
362 const StoreToLoadForwardingCandidate &B) {
363 return getInstrIndex(Inst: A.Store) <
364 getInstrIndex(Inst: B.Store);
365 })
366 ->Store;
367
368 // We're looking for stores after the first forwarding store until the end
369 // of the loop, then from the beginning of the loop until the last
370 // forwarded-to load. Collect the pointer for the stores.
371 SmallPtrSet<Value *, 4> PtrsWrittenOnFwdingPath;
372
373 auto InsertStorePtr = [&](Instruction *I) {
374 if (auto *S = dyn_cast<StoreInst>(Val: I))
375 PtrsWrittenOnFwdingPath.insert(Ptr: S->getPointerOperand());
376 };
377 const auto &MemInstrs = LAI.getDepChecker().getMemoryInstructions();
378 std::for_each(first: MemInstrs.begin() + getInstrIndex(Inst: FirstStore) + 1,
379 last: MemInstrs.end(), f: InsertStorePtr);
380 std::for_each(first: MemInstrs.begin(), last: &MemInstrs[getInstrIndex(Inst: LastLoad)],
381 f: InsertStorePtr);
382
383 return PtrsWrittenOnFwdingPath;
384 }
385
386 /// Determine the pointer alias checks to prove that there are no
387 /// intervening stores.
388 SmallVector<RuntimePointerCheck, 4> collectMemchecks(
389 const SmallVectorImpl<StoreToLoadForwardingCandidate> &Candidates) {
390
391 SmallPtrSet<Value *, 4> PtrsWrittenOnFwdingPath =
392 findPointersWrittenOnForwardingPath(Candidates);
393
394 // Collect the pointers of the candidate loads.
395 SmallPtrSet<Value *, 4> CandLoadPtrs;
396 for (const auto &Candidate : Candidates)
397 CandLoadPtrs.insert(Ptr: Candidate.getLoadPtr());
398
399 const auto &AllChecks = LAI.getRuntimePointerChecking()->getChecks();
400 SmallVector<RuntimePointerCheck, 4> Checks;
401
402 copy_if(Range: AllChecks, Out: std::back_inserter(x&: Checks),
403 P: [&](const RuntimePointerCheck &Check) {
404 for (auto PtrIdx1 : Check.first->Members)
405 for (auto PtrIdx2 : Check.second->Members)
406 if (needsChecking(PtrIdx1, PtrIdx2, PtrsWrittenOnFwdingPath,
407 CandLoadPtrs))
408 return true;
409 return false;
410 });
411
412 LLVM_DEBUG(dbgs() << "\nPointer Checks (count: " << Checks.size()
413 << "):\n");
414 LLVM_DEBUG(LAI.getRuntimePointerChecking()->printChecks(dbgs(), Checks));
415
416 return Checks;
417 }
418
419 /// Perform the transformation for a candidate.
420 void
421 propagateStoredValueToLoadUsers(const StoreToLoadForwardingCandidate &Cand,
422 SCEVExpander &SEE) {
423 // loop:
424 // %x = load %gep_i
425 // = ... %x
426 // store %y, %gep_i_plus_1
427 //
428 // =>
429 //
430 // ph:
431 // %x.initial = load %gep_0
432 // loop:
433 // %x.storeforward = phi [%x.initial, %ph] [%y, %loop]
434 // %x = load %gep_i <---- now dead
435 // = ... %x.storeforward
436 // store %y, %gep_i_plus_1
437
438 Value *Ptr = Cand.Load->getPointerOperand();
439 auto *PtrSCEV = cast<SCEVAddRecExpr>(Val: PSE.getSCEV(V: Ptr));
440 auto *PH = L->getLoopPreheader();
441 assert(PH && "Preheader should exist!");
442 Value *InitialPtr = SEE.expandCodeFor(SH: PtrSCEV->getStart(), Ty: Ptr->getType(),
443 I: PH->getTerminator());
444 Value *Initial =
445 new LoadInst(Cand.Load->getType(), InitialPtr, "load_initial",
446 /* isVolatile */ false, Cand.Load->getAlign(),
447 PH->getTerminator()->getIterator());
448
449 PHINode *PHI = PHINode::Create(Ty: Initial->getType(), NumReservedValues: 2, NameStr: "store_forwarded");
450 PHI->insertBefore(InsertPos: L->getHeader()->begin());
451 PHI->addIncoming(V: Initial, BB: PH);
452
453 Type *LoadType = Initial->getType();
454 Type *StoreType = Cand.Store->getValueOperand()->getType();
455 auto &DL = Cand.Load->getParent()->getModule()->getDataLayout();
456 (void)DL;
457
458 assert(DL.getTypeSizeInBits(LoadType) == DL.getTypeSizeInBits(StoreType) &&
459 "The type sizes should match!");
460
461 Value *StoreValue = Cand.Store->getValueOperand();
462 if (LoadType != StoreType)
463 StoreValue = CastInst::CreateBitOrPointerCast(S: StoreValue, Ty: LoadType,
464 Name: "store_forward_cast",
465 InsertBefore: Cand.Store->getIterator());
466
467 PHI->addIncoming(V: StoreValue, BB: L->getLoopLatch());
468
469 Cand.Load->replaceAllUsesWith(V: PHI);
470 }
471
472 /// Top-level driver for each loop: find store->load forwarding
473 /// candidates, add run-time checks and perform transformation.
474 bool processLoop() {
475 LLVM_DEBUG(dbgs() << "\nIn \"" << L->getHeader()->getParent()->getName()
476 << "\" checking " << *L << "\n");
477
478 // Look for store-to-load forwarding cases across the
479 // backedge. E.g.:
480 //
481 // loop:
482 // %x = load %gep_i
483 // = ... %x
484 // store %y, %gep_i_plus_1
485 //
486 // =>
487 //
488 // ph:
489 // %x.initial = load %gep_0
490 // loop:
491 // %x.storeforward = phi [%x.initial, %ph] [%y, %loop]
492 // %x = load %gep_i <---- now dead
493 // = ... %x.storeforward
494 // store %y, %gep_i_plus_1
495
496 // First start with store->load dependences.
497 auto StoreToLoadDependences = findStoreToLoadDependences(LAI);
498 if (StoreToLoadDependences.empty())
499 return false;
500
501 // Generate an index for each load and store according to the original
502 // program order. This will be used later.
503 InstOrder = LAI.getDepChecker().generateInstructionOrderMap();
504
505 // To keep things simple for now, remove those where the load is potentially
506 // fed by multiple stores.
507 removeDependencesFromMultipleStores(Candidates&: StoreToLoadDependences);
508 if (StoreToLoadDependences.empty())
509 return false;
510
511 // Filter the candidates further.
512 SmallVector<StoreToLoadForwardingCandidate, 4> Candidates;
513 for (const StoreToLoadForwardingCandidate &Cand : StoreToLoadDependences) {
514 LLVM_DEBUG(dbgs() << "Candidate " << Cand);
515
516 // Make sure that the stored values is available everywhere in the loop in
517 // the next iteration.
518 if (!doesStoreDominatesAllLatches(StoreBlock: Cand.Store->getParent(), L, DT))
519 continue;
520
521 // If the load is conditional we can't hoist its 0-iteration instance to
522 // the preheader because that would make it unconditional. Thus we would
523 // access a memory location that the original loop did not access.
524 if (isLoadConditional(Load: Cand.Load, L))
525 continue;
526
527 // Check whether the SCEV difference is the same as the induction step,
528 // thus we load the value in the next iteration.
529 if (!Cand.isDependenceDistanceOfOne(PSE, L))
530 continue;
531
532 assert(isa<SCEVAddRecExpr>(PSE.getSCEV(Cand.Load->getPointerOperand())) &&
533 "Loading from something other than indvar?");
534 assert(
535 isa<SCEVAddRecExpr>(PSE.getSCEV(Cand.Store->getPointerOperand())) &&
536 "Storing to something other than indvar?");
537
538 Candidates.push_back(Elt: Cand);
539 LLVM_DEBUG(
540 dbgs()
541 << Candidates.size()
542 << ". Valid store-to-load forwarding across the loop backedge\n");
543 }
544 if (Candidates.empty())
545 return false;
546
547 // Check intervening may-alias stores. These need runtime checks for alias
548 // disambiguation.
549 SmallVector<RuntimePointerCheck, 4> Checks = collectMemchecks(Candidates);
550
551 // Too many checks are likely to outweigh the benefits of forwarding.
552 if (Checks.size() > Candidates.size() * CheckPerElim) {
553 LLVM_DEBUG(dbgs() << "Too many run-time checks needed.\n");
554 return false;
555 }
556
557 if (LAI.getPSE().getPredicate().getComplexity() >
558 LoadElimSCEVCheckThreshold) {
559 LLVM_DEBUG(dbgs() << "Too many SCEV run-time checks needed.\n");
560 return false;
561 }
562
563 if (!L->isLoopSimplifyForm()) {
564 LLVM_DEBUG(dbgs() << "Loop is not is loop-simplify form");
565 return false;
566 }
567
568 if (!Checks.empty() || !LAI.getPSE().getPredicate().isAlwaysTrue()) {
569 if (LAI.hasConvergentOp()) {
570 LLVM_DEBUG(dbgs() << "Versioning is needed but not allowed with "
571 "convergent calls\n");
572 return false;
573 }
574
575 auto *HeaderBB = L->getHeader();
576 auto *F = HeaderBB->getParent();
577 bool OptForSize = F->hasOptSize() ||
578 llvm::shouldOptimizeForSize(BB: HeaderBB, PSI, BFI,
579 QueryType: PGSOQueryType::IRPass);
580 if (OptForSize) {
581 LLVM_DEBUG(
582 dbgs() << "Versioning is needed but not allowed when optimizing "
583 "for size.\n");
584 return false;
585 }
586
587 // Point of no-return, start the transformation. First, version the loop
588 // if necessary.
589
590 LoopVersioning LV(LAI, Checks, L, LI, DT, PSE.getSE());
591 LV.versionLoop();
592
593 // After versioning, some of the candidates' pointers could stop being
594 // SCEVAddRecs. We need to filter them out.
595 auto NoLongerGoodCandidate = [this](
596 const StoreToLoadForwardingCandidate &Cand) {
597 return !isa<SCEVAddRecExpr>(
598 Val: PSE.getSCEV(V: Cand.Load->getPointerOperand())) ||
599 !isa<SCEVAddRecExpr>(
600 Val: PSE.getSCEV(V: Cand.Store->getPointerOperand()));
601 };
602 llvm::erase_if(C&: Candidates, P: NoLongerGoodCandidate);
603 }
604
605 // Next, propagate the value stored by the store to the users of the load.
606 // Also for the first iteration, generate the initial value of the load.
607 SCEVExpander SEE(*PSE.getSE(), L->getHeader()->getModule()->getDataLayout(),
608 "storeforward");
609 for (const auto &Cand : Candidates)
610 propagateStoredValueToLoadUsers(Cand, SEE);
611 NumLoopLoadEliminted += Candidates.size();
612
613 return true;
614 }
615
616private:
617 Loop *L;
618
619 /// Maps the load/store instructions to their index according to
620 /// program order.
621 DenseMap<Instruction *, unsigned> InstOrder;
622
623 // Analyses used.
624 LoopInfo *LI;
625 const LoopAccessInfo &LAI;
626 DominatorTree *DT;
627 BlockFrequencyInfo *BFI;
628 ProfileSummaryInfo *PSI;
629 PredicatedScalarEvolution PSE;
630};
631
632} // end anonymous namespace
633
634static bool eliminateLoadsAcrossLoops(Function &F, LoopInfo &LI,
635 DominatorTree &DT,
636 BlockFrequencyInfo *BFI,
637 ProfileSummaryInfo *PSI,
638 ScalarEvolution *SE, AssumptionCache *AC,
639 LoopAccessInfoManager &LAIs) {
640 // Build up a worklist of inner-loops to transform to avoid iterator
641 // invalidation.
642 // FIXME: This logic comes from other passes that actually change the loop
643 // nest structure. It isn't clear this is necessary (or useful) for a pass
644 // which merely optimizes the use of loads in a loop.
645 SmallVector<Loop *, 8> Worklist;
646
647 bool Changed = false;
648
649 for (Loop *TopLevelLoop : LI)
650 for (Loop *L : depth_first(G: TopLevelLoop)) {
651 Changed |= simplifyLoop(L, DT: &DT, LI: &LI, SE, AC, /*MSSAU*/ nullptr, PreserveLCSSA: false);
652 // We only handle inner-most loops.
653 if (L->isInnermost())
654 Worklist.push_back(Elt: L);
655 }
656
657 // Now walk the identified inner loops.
658 for (Loop *L : Worklist) {
659 // Match historical behavior
660 if (!L->isRotatedForm() || !L->getExitingBlock())
661 continue;
662 // The actual work is performed by LoadEliminationForLoop.
663 LoadEliminationForLoop LEL(L, &LI, LAIs.getInfo(L&: *L), &DT, BFI, PSI);
664 Changed |= LEL.processLoop();
665 if (Changed)
666 LAIs.clear();
667 }
668 return Changed;
669}
670
671PreservedAnalyses LoopLoadEliminationPass::run(Function &F,
672 FunctionAnalysisManager &AM) {
673 auto &LI = AM.getResult<LoopAnalysis>(IR&: F);
674 // There are no loops in the function. Return before computing other expensive
675 // analyses.
676 if (LI.empty())
677 return PreservedAnalyses::all();
678 auto &SE = AM.getResult<ScalarEvolutionAnalysis>(IR&: F);
679 auto &DT = AM.getResult<DominatorTreeAnalysis>(IR&: F);
680 auto &AC = AM.getResult<AssumptionAnalysis>(IR&: F);
681 auto &MAMProxy = AM.getResult<ModuleAnalysisManagerFunctionProxy>(IR&: F);
682 auto *PSI = MAMProxy.getCachedResult<ProfileSummaryAnalysis>(IR&: *F.getParent());
683 auto *BFI = (PSI && PSI->hasProfileSummary()) ?
684 &AM.getResult<BlockFrequencyAnalysis>(IR&: F) : nullptr;
685 LoopAccessInfoManager &LAIs = AM.getResult<LoopAccessAnalysis>(IR&: F);
686
687 bool Changed = eliminateLoadsAcrossLoops(F, LI, DT, BFI, PSI, SE: &SE, AC: &AC, LAIs);
688
689 if (!Changed)
690 return PreservedAnalyses::all();
691
692 PreservedAnalyses PA;
693 PA.preserve<DominatorTreeAnalysis>();
694 PA.preserve<LoopAnalysis>();
695 return PA;
696}
697

source code of llvm/lib/Transforms/Scalar/LoopLoadElimination.cpp