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