LLVM 19.0.0git
LoopLoadElimination.cpp
Go to the documentation of this file.
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
23#include "llvm/ADT/APInt.h"
24#include "llvm/ADT/DenseMap.h"
26#include "llvm/ADT/STLExtras.h"
29#include "llvm/ADT/Statistic.h"
42#include "llvm/IR/DataLayout.h"
43#include "llvm/IR/Dominators.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"
51#include "llvm/Support/Debug.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
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(1));
73
75 "loop-load-elimination-scev-check-threshold", cl::init(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(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, LoadType, LoadPtr, L).value_or(0);
108 int64_t StrideStore = getPtrStride(PSE, LoadType, StorePtr, L).value_or(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(StrideLoad) != 1)
120 return false;
121
122 unsigned TypeByteSize = DL.getTypeAllocSize(const_cast<Type *>(LoadType));
123
124 auto *LoadPtrSCEV = cast<SCEVAddRecExpr>(PSE.getSCEV(LoadPtr));
125 auto *StorePtrSCEV = cast<SCEVAddRecExpr>(PSE.getSCEV(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 PSE.getSE()->getMinusSCEV(StorePtrSCEV, 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
139 const StoreToLoadForwardingCandidate &Cand) {
140 OS << *Cand.Store << " -->\n";
141 OS.indent(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) {
154 L->getLoopLatches(Latches);
155 return llvm::all_of(Latches, [&](const BasicBlock *Latch) {
156 return DT->dominates(StoreBlock, 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,
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
200 if (isa<LoadInst>(Source))
201 LoadsWithUnknownDepedence.insert(Source);
202 if (isa<LoadInst>(Destination))
203 LoadsWithUnknownDepedence.insert(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(Source, Destination);
212 else
213 assert(Dep.isForward() && "Needs to be a forward dependence");
214
215 auto *Store = dyn_cast<StoreInst>(Source);
216 if (!Store)
217 continue;
218 auto *Load = dyn_cast<LoadInst>(Destination);
219 if (!Load)
220 continue;
221
222 // Only propagate if the stored values are bit/pointer castable.
225 Store->getParent()->getModule()->getDataLayout()))
226 continue;
227
228 Candidates.emplace_front(Load, Store);
229 }
230
231 if (!LoadsWithUnknownDepedence.empty())
232 Candidates.remove_if([&](const StoreToLoadForwardingCandidate &C) {
233 return LoadsWithUnknownDepedence.count(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(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 =
271 LoadToSingleCandT LoadToSingleCand;
272
273 for (const auto &Cand : Candidates) {
274 bool NewElt;
275 LoadToSingleCandT::iterator Iter;
276
277 std::tie(Iter, NewElt) =
278 LoadToSingleCand.insert(std::make_pair(Cand.Load, &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(OtherCand->Store) < getInstrIndex(Cand.Store))
293 OtherCand = &Cand;
294 } else
295 OtherCand = nullptr;
296 }
297 }
298
299 Candidates.remove_if([&](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 =
322 Value *Ptr2 =
324 return ((PtrsWrittenOnFwdingPath.count(Ptr1) && CandLoadPtrs.count(Ptr2)) ||
325 (PtrsWrittenOnFwdingPath.count(Ptr2) && CandLoadPtrs.count(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(
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(Candidates,
353 [&](const StoreToLoadForwardingCandidate &A,
354 const StoreToLoadForwardingCandidate &B) {
355 return getInstrIndex(A.Load) <
356 getInstrIndex(B.Load);
357 })
358 ->Load;
359 StoreInst *FirstStore =
360 llvm::min_element(Candidates,
361 [&](const StoreToLoadForwardingCandidate &A,
362 const StoreToLoadForwardingCandidate &B) {
363 return getInstrIndex(A.Store) <
364 getInstrIndex(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>(I))
375 PtrsWrittenOnFwdingPath.insert(S->getPointerOperand());
376 };
377 const auto &MemInstrs = LAI.getDepChecker().getMemoryInstructions();
378 std::for_each(MemInstrs.begin() + getInstrIndex(FirstStore) + 1,
379 MemInstrs.end(), InsertStorePtr);
380 std::for_each(MemInstrs.begin(), &MemInstrs[getInstrIndex(LastLoad)],
381 InsertStorePtr);
382
383 return PtrsWrittenOnFwdingPath;
384 }
385
386 /// Determine the pointer alias checks to prove that there are no
387 /// intervening stores.
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(Candidate.getLoadPtr());
398
399 const auto &AllChecks = LAI.getRuntimePointerChecking()->getChecks();
401
402 copy_if(AllChecks, std::back_inserter(Checks),
403 [&](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");
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>(PSE.getSCEV(Ptr));
440 auto *PH = L->getLoopPreheader();
441 assert(PH && "Preheader should exist!");
442 Value *InitialPtr = SEE.expandCodeFor(PtrSCEV->getStart(), Ptr->getType(),
443 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(Initial->getType(), 2, "store_forwarded");
450 PHI->insertBefore(L->getHeader()->begin());
451 PHI->addIncoming(Initial, 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(StoreValue, LoadType,
464 "store_forward_cast",
465 Cand.Store->getIterator());
466
467 PHI->addIncoming(StoreValue, L->getLoopLatch());
468
469 Cand.Load->replaceAllUsesWith(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(StoreToLoadDependences);
508 if (StoreToLoadDependences.empty())
509 return false;
510
511 // Filter the candidates further.
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(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(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(Cand);
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() >
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(HeaderBB, PSI, BFI,
579 PGSOQueryType::IRPass);
580 if (OptForSize) {
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 PSE.getSCEV(Cand.Load->getPointerOperand())) ||
599 !isa<SCEVAddRecExpr>(
600 PSE.getSCEV(Cand.Store->getPointerOperand()));
601 };
602 llvm::erase_if(Candidates, 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.
622
623 // Analyses used.
624 LoopInfo *LI;
625 const LoopAccessInfo &LAI;
626 DominatorTree *DT;
630};
631
632} // end anonymous namespace
633
635 DominatorTree &DT,
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(TopLevelLoop)) {
651 Changed |= simplifyLoop(L, &DT, &LI, SE, AC, /*MSSAU*/ nullptr, false);
652 // We only handle inner-most loops.
653 if (L->isInnermost())
654 Worklist.push_back(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), &DT, BFI, PSI);
664 Changed |= LEL.processLoop();
665 if (Changed)
666 LAIs.clear();
667 }
668 return Changed;
669}
670
673 auto &LI = AM.getResult<LoopAnalysis>(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>(F);
679 auto &DT = AM.getResult<DominatorTreeAnalysis>(F);
680 auto &AC = AM.getResult<AssumptionAnalysis>(F);
681 auto &MAMProxy = AM.getResult<ModuleAnalysisManagerFunctionProxy>(F);
682 auto *PSI = MAMProxy.getCachedResult<ProfileSummaryAnalysis>(*F.getParent());
683 auto *BFI = (PSI && PSI->hasProfileSummary()) ?
684 &AM.getResult<BlockFrequencyAnalysis>(F) : nullptr;
686
687 bool Changed = eliminateLoadsAcrossLoops(F, LI, DT, BFI, PSI, &SE, &AC, LAIs);
688
689 if (!Changed)
690 return PreservedAnalyses::all();
691
695 return PA;
696}
for(const MachineOperand &MO :llvm::drop_begin(OldMI.operands(), Desc.getNumOperands()))
MachineBasicBlock MachineBasicBlock::iterator DebugLoc DL
Rewrite undef for PHI
This file implements a class to represent arbitrary precision integral constant values and operations...
static GCRegistry::Add< OcamlGC > B("ocaml", "ocaml 3.10-compatible GC")
static GCRegistry::Add< ErlangGC > A("erlang", "erlang-compatible garbage collector")
#define LLVM_DEBUG(X)
Definition: Debug.h:101
This file defines the DenseMap class.
This file builds on the ADT/GraphTraits.h file to build generic depth first graph iterator.
#define Check(C,...)
This is the interface for a simple mod/ref and alias analysis over globals.
This header provides classes for managing per-loop analyses.
static bool eliminateLoadsAcrossLoops(Function &F, LoopInfo &LI, DominatorTree &DT, BlockFrequencyInfo *BFI, ProfileSummaryInfo *PSI, ScalarEvolution *SE, AssumptionCache *AC, LoopAccessInfoManager &LAIs)
static cl::opt< unsigned > LoadElimSCEVCheckThreshold("loop-load-elimination-scev-check-threshold", cl::init(8), cl::Hidden, cl::desc("The maximum number of SCEV checks allowed for Loop " "Load Elimination"))
static bool isLoadConditional(LoadInst *Load, Loop *L)
Return true if the load is not executed on all paths in the loop.
static bool doesStoreDominatesAllLatches(BasicBlock *StoreBlock, Loop *L, DominatorTree *DT)
Check if the store dominates all latches, so as long as there is no intervening store this value will...
static cl::opt< unsigned > CheckPerElim("runtime-check-per-loop-load-elim", cl::Hidden, cl::desc("Max number of memchecks allowed per eliminated load on average"), cl::init(1))
This header defines the LoopLoadEliminationPass object.
#define F(x, y, z)
Definition: MD5.cpp:55
#define I(x, y, z)
Definition: MD5.cpp:58
Module.h This file contains the declarations for the Module class.
if(VerifyEach)
This header defines various interfaces for pass management in LLVM.
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
This file contains some templates that are useful if you are working with the STL at all.
raw_pwrite_stream & OS
This file defines the SmallPtrSet class.
This file defines the SmallVector class.
This file defines the 'Statistic' class, which is designed to be an easy way to expose various metric...
#define STATISTIC(VARNAME, DESC)
Definition: Statistic.h:167
This pass exposes codegen information to IR-level passes.
Class for arbitrary precision integers.
Definition: APInt.h:76
A container for analyses that lazily runs them and caches their results.
Definition: PassManager.h:348
PassT::Result & getResult(IRUnitT &IR, ExtraArgTs... ExtraArgs)
Get the result of an analysis pass for a given IR unit.
Definition: PassManager.h:500
A function analysis which provides an AssumptionCache.
A cache of @llvm.assume calls within a function.
LLVM Basic Block Representation.
Definition: BasicBlock.h:60
Analysis pass which computes BlockFrequencyInfo.
BlockFrequencyInfo pass uses BlockFrequencyInfoImpl implementation to estimate IR basic block frequen...
static bool isBitOrNoopPointerCastable(Type *SrcTy, Type *DestTy, const DataLayout &DL)
Check whether a bitcast, inttoptr, or ptrtoint cast between these types is valid and a no-op.
static CastInst * CreateBitOrPointerCast(Value *S, Type *Ty, const Twine &Name, BasicBlock::iterator InsertBefore)
Create a BitCast, a PtrToInt, or an IntToPTr cast instruction.
std::pair< iterator, bool > insert(const std::pair< KeyT, ValueT > &KV)
Definition: DenseMap.h:220
Analysis pass which computes a DominatorTree.
Definition: Dominators.h:279
Concrete subclass of DominatorTreeBase that is used to compute a normal dominator tree.
Definition: Dominators.h:162
bool dominates(const BasicBlock *BB, const Use &U) const
Return true if the (end of the) basic block BB dominates the use U.
Definition: Dominators.cpp:122
An instruction for reading from memory.
Definition: Instructions.h:184
This analysis provides dependence information for the memory accesses of a loop.
const LoopAccessInfo & getInfo(Loop &L)
Drive the analysis of memory accesses in the loop.
const MemoryDepChecker & getDepChecker() const
the Memory Dependence Checker which can determine the loop-independent and loop-carried dependences b...
const RuntimePointerChecking * getRuntimePointerChecking() const
const PredicatedScalarEvolution & getPSE() const
Used to add runtime SCEV checks.
bool hasConvergentOp() const
Return true if there is a convergent operation in the loop.
Analysis pass that exposes the LoopInfo for a function.
Definition: LoopInfo.h:566
This class emits a version of the loop where run-time checks ensure that may-alias pointers can't ove...
Represents a single loop in the control flow graph.
Definition: LoopInfo.h:44
const MachineFunction * getParent() const
Return the MachineFunction containing this basic block.
const DataLayout & getDataLayout() const
Return the DataLayout attached to the Module associated to this MF.
const SmallVectorImpl< Instruction * > & getMemoryInstructions() const
The vector of memory access instructions.
const SmallVectorImpl< Dependence > * getDependences() const
Returns the memory dependences.
DenseMap< Instruction *, unsigned > generateInstructionOrderMap() const
Generate a mapping between the memory instructions and their indices according to program order.
An analysis over an "inner" IR unit that provides access to an analysis manager over a "outer" IR uni...
Definition: PassManager.h:783
static PHINode * Create(Type *Ty, unsigned NumReservedValues, const Twine &NameStr, BasicBlock::iterator InsertBefore)
Constructors - NumReservedValues is a hint for the number of incoming edges that this phi node will h...
An interface layer with SCEV used to manage how we see SCEV expressions for values in the context of ...
ScalarEvolution * getSE() const
Returns the ScalarEvolution analysis used.
const SCEVPredicate & getPredicate() const
const SCEV * getSCEV(Value *V)
Returns the SCEV expression of V, in the context of the current SCEV predicate.
A set of analyses that are preserved following a run of a transformation pass.
Definition: Analysis.h:109
static PreservedAnalyses all()
Construct a special preserved set that preserves all passes.
Definition: Analysis.h:115
void preserve()
Mark an analysis as preserved.
Definition: Analysis.h:129
An analysis pass based on the new PM to deliver ProfileSummaryInfo.
Analysis providing profile information.
void printChecks(raw_ostream &OS, const SmallVectorImpl< RuntimePointerCheck > &Checks, unsigned Depth=0) const
Print Checks.
const SmallVectorImpl< RuntimePointerCheck > & getChecks() const
Returns the checks that generateChecks created.
const PointerInfo & getPointerInfo(unsigned PtrIdx) const
Return PointerInfo for pointer at index PtrIdx.
This class uses information about analyze scalars to rewrite expressions in canonical form.
virtual unsigned getComplexity() const
Returns the estimated complexity of this predicate.
virtual bool isAlwaysTrue() const =0
Returns true if the predicate is always true.
Analysis pass that exposes the ScalarEvolution for a function.
The main scalar evolution driver.
const SCEV * getMinusSCEV(const SCEV *LHS, const SCEV *RHS, SCEV::NoWrapFlags Flags=SCEV::FlagAnyWrap, unsigned Depth=0)
Return LHS-RHS.
A templated base class for SmallPtrSet which provides the typesafe interface that is common across al...
Definition: SmallPtrSet.h:321
size_type count(ConstPtrType Ptr) const
count - Return 1 if the specified pointer is in the set, 0 otherwise.
Definition: SmallPtrSet.h:360
std::pair< iterator, bool > insert(PtrType Ptr)
Inserts Ptr if and only if there is no element in the container equal to Ptr.
Definition: SmallPtrSet.h:342
SmallPtrSet - This class implements a set which is optimized for holding SmallSize or less elements.
Definition: SmallPtrSet.h:427
bool empty() const
Definition: SmallVector.h:94
size_t size() const
Definition: SmallVector.h:91
This class consists of common code factored out of the SmallVector class to reduce code duplication b...
Definition: SmallVector.h:586
void push_back(const T &Elt)
Definition: SmallVector.h:426
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
Definition: SmallVector.h:1209
An instruction for storing to memory.
Definition: Instructions.h:317
The instances of the Type class are immutable: once they are created, they are never changed.
Definition: Type.h:45
unsigned getPointerAddressSpace() const
Get the address space of this pointer or pointer vector type.
LLVM Value Representation.
Definition: Value.h:74
Type * getType() const
All values are typed, get the type of this value.
Definition: Value.h:255
This class implements an extremely fast bulk output stream that can only output to a stream.
Definition: raw_ostream.h:52
raw_ostream & indent(unsigned NumSpaces)
indent - Insert 'NumSpaces' spaces.
@ C
The default llvm calling convention, compatible with C.
Definition: CallingConv.h:34
initializer< Ty > init(const Ty &Val)
Definition: CommandLine.h:450
This is an optimization pass for GlobalISel generic memory operations.
Definition: AddressRanges.h:18
bool simplifyLoop(Loop *L, DominatorTree *DT, LoopInfo *LI, ScalarEvolution *SE, AssumptionCache *AC, MemorySSAUpdater *MSSAU, bool PreserveLCSSA)
Simplify each loop in a loop nest recursively.
auto min_element(R &&Range)
Definition: STLExtras.h:1987
bool all_of(R &&range, UnaryPredicate P)
Provide wrappers to std::all_of which take ranges instead of having to pass begin/end explicitly.
Definition: STLExtras.h:1731
std::pair< const RuntimeCheckingPtrGroup *, const RuntimeCheckingPtrGroup * > RuntimePointerCheck
A memcheck which made up of a pair of grouped pointers.
bool shouldOptimizeForSize(const MachineFunction *MF, ProfileSummaryInfo *PSI, const MachineBlockFrequencyInfo *BFI, PGSOQueryType QueryType=PGSOQueryType::Other)
Returns true if machine function MF is suggested to be size-optimized based on the profile.
OutputIt copy_if(R &&Range, OutputIt Out, UnaryPredicate P)
Provide wrappers to std::copy_if which take ranges instead of having to pass begin/end explicitly.
Definition: STLExtras.h:1777
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
Definition: Debug.cpp:163
std::optional< int64_t > getPtrStride(PredicatedScalarEvolution &PSE, Type *AccessTy, Value *Ptr, const Loop *Lp, const DenseMap< Value *, const SCEV * > &StridesMap=DenseMap< Value *, const SCEV * >(), bool Assume=false, bool ShouldCheckWrap=true)
If the pointer has a constant stride return it in units of the access type size.
auto max_element(R &&Range)
Definition: STLExtras.h:1995
raw_ostream & operator<<(raw_ostream &OS, const APFixedPoint &FX)
Definition: APFixedPoint.h:293
void erase_if(Container &C, UnaryPredicate P)
Provide a container algorithm similar to C++ Library Fundamentals v2's erase_if which is equivalent t...
Definition: STLExtras.h:2060
iterator_range< df_iterator< T > > depth_first(const T &G)
Type * getLoadStoreType(Value *I)
A helper function that returns the type of a load or store instruction.
void swap(llvm::BitVector &LHS, llvm::BitVector &RHS)
Implement std::swap in terms of BitVector swap.
Definition: BitVector.h:860
#define SEE(c)
Definition: regcomp.c:254
PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM)
TrackingVH< Value > PointerValue
Holds the pointer value that we need to check.