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 | std::max_element(first: Candidates.begin(), last: Candidates.end(), |
353 | comp: [&](const StoreToLoadForwardingCandidate &A, |
354 | const StoreToLoadForwardingCandidate &B) { |
355 | return getInstrIndex(Inst: A.Load) < getInstrIndex(Inst: B.Load); |
356 | }) |
357 | ->Load; |
358 | StoreInst *FirstStore = |
359 | std::min_element(first: Candidates.begin(), last: Candidates.end(), |
360 | comp: [&](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 | Value *Initial = new LoadInst( |
444 | Cand.Load->getType(), InitialPtr, "load_initial" , |
445 | /* isVolatile */ false, Cand.Load->getAlign(), PH->getTerminator()); |
446 | |
447 | PHINode *PHI = PHINode::Create(Ty: Initial->getType(), NumReservedValues: 2, NameStr: "store_forwarded" ); |
448 | PHI->insertBefore(InsertPos: L->getHeader()->begin()); |
449 | PHI->addIncoming(V: Initial, BB: PH); |
450 | |
451 | Type *LoadType = Initial->getType(); |
452 | Type *StoreType = Cand.Store->getValueOperand()->getType(); |
453 | auto &DL = Cand.Load->getParent()->getModule()->getDataLayout(); |
454 | (void)DL; |
455 | |
456 | assert(DL.getTypeSizeInBits(LoadType) == DL.getTypeSizeInBits(StoreType) && |
457 | "The type sizes should match!" ); |
458 | |
459 | Value *StoreValue = Cand.Store->getValueOperand(); |
460 | if (LoadType != StoreType) |
461 | StoreValue = CastInst::CreateBitOrPointerCast( |
462 | S: StoreValue, Ty: LoadType, Name: "store_forward_cast" , InsertBefore: Cand.Store); |
463 | |
464 | PHI->addIncoming(V: StoreValue, BB: L->getLoopLatch()); |
465 | |
466 | Cand.Load->replaceAllUsesWith(V: PHI); |
467 | } |
468 | |
469 | /// Top-level driver for each loop: find store->load forwarding |
470 | /// candidates, add run-time checks and perform transformation. |
471 | bool processLoop() { |
472 | LLVM_DEBUG(dbgs() << "\nIn \"" << L->getHeader()->getParent()->getName() |
473 | << "\" checking " << *L << "\n" ); |
474 | |
475 | // Look for store-to-load forwarding cases across the |
476 | // backedge. E.g.: |
477 | // |
478 | // loop: |
479 | // %x = load %gep_i |
480 | // = ... %x |
481 | // store %y, %gep_i_plus_1 |
482 | // |
483 | // => |
484 | // |
485 | // ph: |
486 | // %x.initial = load %gep_0 |
487 | // loop: |
488 | // %x.storeforward = phi [%x.initial, %ph] [%y, %loop] |
489 | // %x = load %gep_i <---- now dead |
490 | // = ... %x.storeforward |
491 | // store %y, %gep_i_plus_1 |
492 | |
493 | // First start with store->load dependences. |
494 | auto StoreToLoadDependences = findStoreToLoadDependences(LAI); |
495 | if (StoreToLoadDependences.empty()) |
496 | return false; |
497 | |
498 | // Generate an index for each load and store according to the original |
499 | // program order. This will be used later. |
500 | InstOrder = LAI.getDepChecker().generateInstructionOrderMap(); |
501 | |
502 | // To keep things simple for now, remove those where the load is potentially |
503 | // fed by multiple stores. |
504 | removeDependencesFromMultipleStores(Candidates&: StoreToLoadDependences); |
505 | if (StoreToLoadDependences.empty()) |
506 | return false; |
507 | |
508 | // Filter the candidates further. |
509 | SmallVector<StoreToLoadForwardingCandidate, 4> Candidates; |
510 | for (const StoreToLoadForwardingCandidate &Cand : StoreToLoadDependences) { |
511 | LLVM_DEBUG(dbgs() << "Candidate " << Cand); |
512 | |
513 | // Make sure that the stored values is available everywhere in the loop in |
514 | // the next iteration. |
515 | if (!doesStoreDominatesAllLatches(StoreBlock: Cand.Store->getParent(), L, DT)) |
516 | continue; |
517 | |
518 | // If the load is conditional we can't hoist its 0-iteration instance to |
519 | // the preheader because that would make it unconditional. Thus we would |
520 | // access a memory location that the original loop did not access. |
521 | if (isLoadConditional(Load: Cand.Load, L)) |
522 | continue; |
523 | |
524 | // Check whether the SCEV difference is the same as the induction step, |
525 | // thus we load the value in the next iteration. |
526 | if (!Cand.isDependenceDistanceOfOne(PSE, L)) |
527 | continue; |
528 | |
529 | assert(isa<SCEVAddRecExpr>(PSE.getSCEV(Cand.Load->getPointerOperand())) && |
530 | "Loading from something other than indvar?" ); |
531 | assert( |
532 | isa<SCEVAddRecExpr>(PSE.getSCEV(Cand.Store->getPointerOperand())) && |
533 | "Storing to something other than indvar?" ); |
534 | |
535 | Candidates.push_back(Elt: Cand); |
536 | LLVM_DEBUG( |
537 | dbgs() |
538 | << Candidates.size() |
539 | << ". Valid store-to-load forwarding across the loop backedge\n" ); |
540 | } |
541 | if (Candidates.empty()) |
542 | return false; |
543 | |
544 | // Check intervening may-alias stores. These need runtime checks for alias |
545 | // disambiguation. |
546 | SmallVector<RuntimePointerCheck, 4> Checks = collectMemchecks(Candidates); |
547 | |
548 | // Too many checks are likely to outweigh the benefits of forwarding. |
549 | if (Checks.size() > Candidates.size() * CheckPerElim) { |
550 | LLVM_DEBUG(dbgs() << "Too many run-time checks needed.\n" ); |
551 | return false; |
552 | } |
553 | |
554 | if (LAI.getPSE().getPredicate().getComplexity() > |
555 | LoadElimSCEVCheckThreshold) { |
556 | LLVM_DEBUG(dbgs() << "Too many SCEV run-time checks needed.\n" ); |
557 | return false; |
558 | } |
559 | |
560 | if (!L->isLoopSimplifyForm()) { |
561 | LLVM_DEBUG(dbgs() << "Loop is not is loop-simplify form" ); |
562 | return false; |
563 | } |
564 | |
565 | if (!Checks.empty() || !LAI.getPSE().getPredicate().isAlwaysTrue()) { |
566 | if (LAI.hasConvergentOp()) { |
567 | LLVM_DEBUG(dbgs() << "Versioning is needed but not allowed with " |
568 | "convergent calls\n" ); |
569 | return false; |
570 | } |
571 | |
572 | auto * = L->getHeader(); |
573 | auto *F = HeaderBB->getParent(); |
574 | bool OptForSize = F->hasOptSize() || |
575 | llvm::shouldOptimizeForSize(BB: HeaderBB, PSI, BFI, |
576 | QueryType: PGSOQueryType::IRPass); |
577 | if (OptForSize) { |
578 | LLVM_DEBUG( |
579 | dbgs() << "Versioning is needed but not allowed when optimizing " |
580 | "for size.\n" ); |
581 | return false; |
582 | } |
583 | |
584 | // Point of no-return, start the transformation. First, version the loop |
585 | // if necessary. |
586 | |
587 | LoopVersioning LV(LAI, Checks, L, LI, DT, PSE.getSE()); |
588 | LV.versionLoop(); |
589 | |
590 | // After versioning, some of the candidates' pointers could stop being |
591 | // SCEVAddRecs. We need to filter them out. |
592 | auto NoLongerGoodCandidate = [this]( |
593 | const StoreToLoadForwardingCandidate &Cand) { |
594 | return !isa<SCEVAddRecExpr>( |
595 | Val: PSE.getSCEV(V: Cand.Load->getPointerOperand())) || |
596 | !isa<SCEVAddRecExpr>( |
597 | Val: PSE.getSCEV(V: Cand.Store->getPointerOperand())); |
598 | }; |
599 | llvm::erase_if(C&: Candidates, P: NoLongerGoodCandidate); |
600 | } |
601 | |
602 | // Next, propagate the value stored by the store to the users of the load. |
603 | // Also for the first iteration, generate the initial value of the load. |
604 | SCEVExpander SEE(*PSE.getSE(), L->getHeader()->getModule()->getDataLayout(), |
605 | "storeforward" ); |
606 | for (const auto &Cand : Candidates) |
607 | propagateStoredValueToLoadUsers(Cand, SEE); |
608 | NumLoopLoadEliminted += Candidates.size(); |
609 | |
610 | return true; |
611 | } |
612 | |
613 | private: |
614 | Loop *L; |
615 | |
616 | /// Maps the load/store instructions to their index according to |
617 | /// program order. |
618 | DenseMap<Instruction *, unsigned> InstOrder; |
619 | |
620 | // Analyses used. |
621 | LoopInfo *LI; |
622 | const LoopAccessInfo &LAI; |
623 | DominatorTree *DT; |
624 | BlockFrequencyInfo *BFI; |
625 | ProfileSummaryInfo *PSI; |
626 | PredicatedScalarEvolution PSE; |
627 | }; |
628 | |
629 | } // end anonymous namespace |
630 | |
631 | static bool eliminateLoadsAcrossLoops(Function &F, LoopInfo &LI, |
632 | DominatorTree &DT, |
633 | BlockFrequencyInfo *BFI, |
634 | ProfileSummaryInfo *PSI, |
635 | ScalarEvolution *SE, AssumptionCache *AC, |
636 | LoopAccessInfoManager &LAIs) { |
637 | // Build up a worklist of inner-loops to transform to avoid iterator |
638 | // invalidation. |
639 | // FIXME: This logic comes from other passes that actually change the loop |
640 | // nest structure. It isn't clear this is necessary (or useful) for a pass |
641 | // which merely optimizes the use of loads in a loop. |
642 | SmallVector<Loop *, 8> Worklist; |
643 | |
644 | bool Changed = false; |
645 | |
646 | for (Loop *TopLevelLoop : LI) |
647 | for (Loop *L : depth_first(G: TopLevelLoop)) { |
648 | Changed |= simplifyLoop(L, DT: &DT, LI: &LI, SE, AC, /*MSSAU*/ nullptr, PreserveLCSSA: false); |
649 | // We only handle inner-most loops. |
650 | if (L->isInnermost()) |
651 | Worklist.push_back(Elt: L); |
652 | } |
653 | |
654 | // Now walk the identified inner loops. |
655 | for (Loop *L : Worklist) { |
656 | // Match historical behavior |
657 | if (!L->isRotatedForm() || !L->getExitingBlock()) |
658 | continue; |
659 | // The actual work is performed by LoadEliminationForLoop. |
660 | LoadEliminationForLoop LEL(L, &LI, LAIs.getInfo(L&: *L), &DT, BFI, PSI); |
661 | Changed |= LEL.processLoop(); |
662 | if (Changed) |
663 | LAIs.clear(); |
664 | } |
665 | return Changed; |
666 | } |
667 | |
668 | PreservedAnalyses LoopLoadEliminationPass::run(Function &F, |
669 | FunctionAnalysisManager &AM) { |
670 | auto &LI = AM.getResult<LoopAnalysis>(IR&: F); |
671 | // There are no loops in the function. Return before computing other expensive |
672 | // analyses. |
673 | if (LI.empty()) |
674 | return PreservedAnalyses::all(); |
675 | auto &SE = AM.getResult<ScalarEvolutionAnalysis>(IR&: F); |
676 | auto &DT = AM.getResult<DominatorTreeAnalysis>(IR&: F); |
677 | auto &AC = AM.getResult<AssumptionAnalysis>(IR&: F); |
678 | auto &MAMProxy = AM.getResult<ModuleAnalysisManagerFunctionProxy>(IR&: F); |
679 | auto *PSI = MAMProxy.getCachedResult<ProfileSummaryAnalysis>(IR&: *F.getParent()); |
680 | auto *BFI = (PSI && PSI->hasProfileSummary()) ? |
681 | &AM.getResult<BlockFrequencyAnalysis>(IR&: F) : nullptr; |
682 | LoopAccessInfoManager &LAIs = AM.getResult<LoopAccessAnalysis>(IR&: F); |
683 | |
684 | bool Changed = eliminateLoadsAcrossLoops(F, LI, DT, BFI, PSI, SE: &SE, AC: &AC, LAIs); |
685 | |
686 | if (!Changed) |
687 | return PreservedAnalyses::all(); |
688 | |
689 | PreservedAnalyses PA; |
690 | PA.preserve<DominatorTreeAnalysis>(); |
691 | PA.preserve<LoopAnalysis>(); |
692 | return PA; |
693 | } |
694 | |