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