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 | |
64 | using namespace llvm; |
65 | |
66 | #define LLE_OPTION "loop-load-elim" |
67 | #define DEBUG_TYPE LLE_OPTION |
68 | |
69 | static 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 | |
74 | static 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 | |
79 | STATISTIC(NumLoopLoadEliminted, "Number of loads eliminated by LLE" ); |
80 | |
81 | namespace { |
82 | |
83 | /// Represent a store-to-forwarding candidate. |
84 | struct 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. |
151 | static 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. |
161 | static bool isLoadConditional(LoadInst *Load, Loop *L) { |
162 | return Load->getParent() != L->getHeader(); |
163 | } |
164 | |
165 | namespace { |
166 | |
167 | /// The per-loop class that does most of the work. |
168 | class LoadEliminationForLoop { |
169 | public: |
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 * = 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 | |
616 | private: |
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 | |
634 | static 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 | |
671 | PreservedAnalyses 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 | |