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