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