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 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(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, LoadType, LoadPtr, L).value_or(0); 108 int64_t StrideStore = getPtrStride(PSE, LoadType, StorePtr, L).value_or(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(StrideLoad) != 1) 120 return false; 121 122 unsigned TypeByteSize = DL.getTypeAllocSize(const_cast<Type *>(LoadType)); 123 124 auto *LoadPtrSCEV = cast<SCEVAddRecExpr>(PSE.getSCEV(LoadPtr)); 125 auto *StorePtrSCEV = cast<SCEVAddRecExpr>(PSE.getSCEV(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 PSE.getSE()->getMinusSCEV(StorePtrSCEV, 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(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(Latches); 155 return llvm::all_of(Latches, [&](const BasicBlock *Latch) { 156 return DT->dominates(StoreBlock, 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>(Source)) 201 LoadsWithUnknownDepedence.insert(Source); 202 if (isa<LoadInst>(Destination)) 203 LoadsWithUnknownDepedence.insert(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(Source, Destination); 212 else 213 assert(Dep.isForward() && "Needs to be a forward dependence"); 214 215 auto *Store = dyn_cast<StoreInst>(Source); 216 if (!Store) 217 continue; 218 auto *Load = dyn_cast<LoadInst>(Destination); 219 if (!Load) 220 continue; 221 222 // Only propagate if the stored values are bit/pointer castable. 223 if (!CastInst::isBitOrNoopPointerCastable( 224 getLoadStoreType(Store), getLoadStoreType(Load), 225 Store->getParent()->getModule()->getDataLayout())) 226 continue; 227 228 Candidates.emplace_front(Load, Store); 229 } 230 231 if (!LoadsWithUnknownDepedence.empty()) 232 Candidates.remove_if([&](const StoreToLoadForwardingCandidate &C) { 233 return LoadsWithUnknownDepedence.count(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(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(Iter, NewElt) = 278 LoadToSingleCand.insert(std::make_pair(Cand.Load, &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(OtherCand->Store) < getInstrIndex(Cand.Store)) 293 OtherCand = &Cand; 294 } else 295 OtherCand = nullptr; 296 } 297 } 298 299 Candidates.remove_if([&](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(PtrIdx1).PointerValue; 322 Value *Ptr2 = 323 LAI.getRuntimePointerChecking()->getPointerInfo(PtrIdx2).PointerValue; 324 return ((PtrsWrittenOnFwdingPath.count(Ptr1) && CandLoadPtrs.count(Ptr2)) || 325 (PtrsWrittenOnFwdingPath.count(Ptr2) && CandLoadPtrs.count(Ptr1))); 326 } 327 328 /// Return pointers that are possibly written to on the path from a 329 /// forwarding store to a load. 330 /// 331 /// These pointers need to be alias-checked against the forwarding candidates. 332 SmallPtrSet<Value *, 4> findPointersWrittenOnForwardingPath( 333 const SmallVectorImpl<StoreToLoadForwardingCandidate> &Candidates) { 334 // From FirstStore to LastLoad neither of the elimination candidate loads 335 // should overlap with any of the stores. 336 // 337 // E.g.: 338 // 339 // st1 C[i] 340 // ld1 B[i] <-------, 341 // ld0 A[i] <----, | * LastLoad 342 // ... | | 343 // st2 E[i] | | 344 // st3 B[i+1] -- | -' * FirstStore 345 // st0 A[i+1] ---' 346 // st4 D[i] 347 // 348 // st0 forwards to ld0 if the accesses in st4 and st1 don't overlap with 349 // ld0. 350 351 LoadInst *LastLoad = 352 llvm::max_element(Candidates, 353 [&](const StoreToLoadForwardingCandidate &A, 354 const StoreToLoadForwardingCandidate &B) { 355 return getInstrIndex(A.Load) < 356 getInstrIndex(B.Load); 357 }) 358 ->Load; 359 StoreInst *FirstStore = 360 llvm::min_element(Candidates, 361 [&](const StoreToLoadForwardingCandidate &A, 362 const StoreToLoadForwardingCandidate &B) { 363 return getInstrIndex(A.Store) < 364 getInstrIndex(B.Store); 365 }) 366 ->Store; 367 368 // We're looking for stores after the first forwarding store until the end 369 // of the loop, then from the beginning of the loop until the last 370 // forwarded-to load. Collect the pointer for the stores. 371 SmallPtrSet<Value *, 4> PtrsWrittenOnFwdingPath; 372 373 auto InsertStorePtr = [&](Instruction *I) { 374 if (auto *S = dyn_cast<StoreInst>(I)) 375 PtrsWrittenOnFwdingPath.insert(S->getPointerOperand()); 376 }; 377 const auto &MemInstrs = LAI.getDepChecker().getMemoryInstructions(); 378 std::for_each(MemInstrs.begin() + getInstrIndex(FirstStore) + 1, 379 MemInstrs.end(), InsertStorePtr); 380 std::for_each(MemInstrs.begin(), &MemInstrs[getInstrIndex(LastLoad)], 381 InsertStorePtr); 382 383 return PtrsWrittenOnFwdingPath; 384 } 385 386 /// Determine the pointer alias checks to prove that there are no 387 /// intervening stores. 388 SmallVector<RuntimePointerCheck, 4> collectMemchecks( 389 const SmallVectorImpl<StoreToLoadForwardingCandidate> &Candidates) { 390 391 SmallPtrSet<Value *, 4> PtrsWrittenOnFwdingPath = 392 findPointersWrittenOnForwardingPath(Candidates); 393 394 // Collect the pointers of the candidate loads. 395 SmallPtrSet<Value *, 4> CandLoadPtrs; 396 for (const auto &Candidate : Candidates) 397 CandLoadPtrs.insert(Candidate.getLoadPtr()); 398 399 const auto &AllChecks = LAI.getRuntimePointerChecking()->getChecks(); 400 SmallVector<RuntimePointerCheck, 4> Checks; 401 402 copy_if(AllChecks, std::back_inserter(Checks), 403 [&](const RuntimePointerCheck &Check) { 404 for (auto PtrIdx1 : Check.first->Members) 405 for (auto PtrIdx2 : Check.second->Members) 406 if (needsChecking(PtrIdx1, PtrIdx2, PtrsWrittenOnFwdingPath, 407 CandLoadPtrs)) 408 return true; 409 return false; 410 }); 411 412 LLVM_DEBUG(dbgs() << "\nPointer Checks (count: " << Checks.size() 413 << "):\n"); 414 LLVM_DEBUG(LAI.getRuntimePointerChecking()->printChecks(dbgs(), Checks)); 415 416 return Checks; 417 } 418 419 /// Perform the transformation for a candidate. 420 void 421 propagateStoredValueToLoadUsers(const StoreToLoadForwardingCandidate &Cand, 422 SCEVExpander &SEE) { 423 // loop: 424 // %x = load %gep_i 425 // = ... %x 426 // store %y, %gep_i_plus_1 427 // 428 // => 429 // 430 // ph: 431 // %x.initial = load %gep_0 432 // loop: 433 // %x.storeforward = phi [%x.initial, %ph] [%y, %loop] 434 // %x = load %gep_i <---- now dead 435 // = ... %x.storeforward 436 // store %y, %gep_i_plus_1 437 438 Value *Ptr = Cand.Load->getPointerOperand(); 439 auto *PtrSCEV = cast<SCEVAddRecExpr>(PSE.getSCEV(Ptr)); 440 auto *PH = L->getLoopPreheader(); 441 assert(PH && "Preheader should exist!"); 442 Value *InitialPtr = SEE.expandCodeFor(PtrSCEV->getStart(), Ptr->getType(), 443 PH->getTerminator()); 444 Value *Initial = 445 new LoadInst(Cand.Load->getType(), InitialPtr, "load_initial", 446 /* isVolatile */ false, Cand.Load->getAlign(), 447 PH->getTerminator()->getIterator()); 448 449 PHINode *PHI = PHINode::Create(Initial->getType(), 2, "store_forwarded"); 450 PHI->insertBefore(L->getHeader()->begin()); 451 PHI->addIncoming(Initial, PH); 452 453 Type *LoadType = Initial->getType(); 454 Type *StoreType = Cand.Store->getValueOperand()->getType(); 455 auto &DL = Cand.Load->getParent()->getModule()->getDataLayout(); 456 (void)DL; 457 458 assert(DL.getTypeSizeInBits(LoadType) == DL.getTypeSizeInBits(StoreType) && 459 "The type sizes should match!"); 460 461 Value *StoreValue = Cand.Store->getValueOperand(); 462 if (LoadType != StoreType) 463 StoreValue = CastInst::CreateBitOrPointerCast(StoreValue, LoadType, 464 "store_forward_cast", 465 Cand.Store->getIterator()); 466 467 PHI->addIncoming(StoreValue, L->getLoopLatch()); 468 469 Cand.Load->replaceAllUsesWith(PHI); 470 } 471 472 /// Top-level driver for each loop: find store->load forwarding 473 /// candidates, add run-time checks and perform transformation. 474 bool processLoop() { 475 LLVM_DEBUG(dbgs() << "\nIn \"" << L->getHeader()->getParent()->getName() 476 << "\" checking " << *L << "\n"); 477 478 // Look for store-to-load forwarding cases across the 479 // backedge. E.g.: 480 // 481 // loop: 482 // %x = load %gep_i 483 // = ... %x 484 // store %y, %gep_i_plus_1 485 // 486 // => 487 // 488 // ph: 489 // %x.initial = load %gep_0 490 // loop: 491 // %x.storeforward = phi [%x.initial, %ph] [%y, %loop] 492 // %x = load %gep_i <---- now dead 493 // = ... %x.storeforward 494 // store %y, %gep_i_plus_1 495 496 // First start with store->load dependences. 497 auto StoreToLoadDependences = findStoreToLoadDependences(LAI); 498 if (StoreToLoadDependences.empty()) 499 return false; 500 501 // Generate an index for each load and store according to the original 502 // program order. This will be used later. 503 InstOrder = LAI.getDepChecker().generateInstructionOrderMap(); 504 505 // To keep things simple for now, remove those where the load is potentially 506 // fed by multiple stores. 507 removeDependencesFromMultipleStores(StoreToLoadDependences); 508 if (StoreToLoadDependences.empty()) 509 return false; 510 511 // Filter the candidates further. 512 SmallVector<StoreToLoadForwardingCandidate, 4> Candidates; 513 for (const StoreToLoadForwardingCandidate &Cand : StoreToLoadDependences) { 514 LLVM_DEBUG(dbgs() << "Candidate " << Cand); 515 516 // Make sure that the stored values is available everywhere in the loop in 517 // the next iteration. 518 if (!doesStoreDominatesAllLatches(Cand.Store->getParent(), L, DT)) 519 continue; 520 521 // If the load is conditional we can't hoist its 0-iteration instance to 522 // the preheader because that would make it unconditional. Thus we would 523 // access a memory location that the original loop did not access. 524 if (isLoadConditional(Cand.Load, L)) 525 continue; 526 527 // Check whether the SCEV difference is the same as the induction step, 528 // thus we load the value in the next iteration. 529 if (!Cand.isDependenceDistanceOfOne(PSE, L)) 530 continue; 531 532 assert(isa<SCEVAddRecExpr>(PSE.getSCEV(Cand.Load->getPointerOperand())) && 533 "Loading from something other than indvar?"); 534 assert( 535 isa<SCEVAddRecExpr>(PSE.getSCEV(Cand.Store->getPointerOperand())) && 536 "Storing to something other than indvar?"); 537 538 Candidates.push_back(Cand); 539 LLVM_DEBUG( 540 dbgs() 541 << Candidates.size() 542 << ". Valid store-to-load forwarding across the loop backedge\n"); 543 } 544 if (Candidates.empty()) 545 return false; 546 547 // Check intervening may-alias stores. These need runtime checks for alias 548 // disambiguation. 549 SmallVector<RuntimePointerCheck, 4> Checks = collectMemchecks(Candidates); 550 551 // Too many checks are likely to outweigh the benefits of forwarding. 552 if (Checks.size() > Candidates.size() * CheckPerElim) { 553 LLVM_DEBUG(dbgs() << "Too many run-time checks needed.\n"); 554 return false; 555 } 556 557 if (LAI.getPSE().getPredicate().getComplexity() > 558 LoadElimSCEVCheckThreshold) { 559 LLVM_DEBUG(dbgs() << "Too many SCEV run-time checks needed.\n"); 560 return false; 561 } 562 563 if (!L->isLoopSimplifyForm()) { 564 LLVM_DEBUG(dbgs() << "Loop is not is loop-simplify form"); 565 return false; 566 } 567 568 if (!Checks.empty() || !LAI.getPSE().getPredicate().isAlwaysTrue()) { 569 if (LAI.hasConvergentOp()) { 570 LLVM_DEBUG(dbgs() << "Versioning is needed but not allowed with " 571 "convergent calls\n"); 572 return false; 573 } 574 575 auto *HeaderBB = L->getHeader(); 576 auto *F = HeaderBB->getParent(); 577 bool OptForSize = F->hasOptSize() || 578 llvm::shouldOptimizeForSize(HeaderBB, PSI, BFI, 579 PGSOQueryType::IRPass); 580 if (OptForSize) { 581 LLVM_DEBUG( 582 dbgs() << "Versioning is needed but not allowed when optimizing " 583 "for size.\n"); 584 return false; 585 } 586 587 // Point of no-return, start the transformation. First, version the loop 588 // if necessary. 589 590 LoopVersioning LV(LAI, Checks, L, LI, DT, PSE.getSE()); 591 LV.versionLoop(); 592 593 // After versioning, some of the candidates' pointers could stop being 594 // SCEVAddRecs. We need to filter them out. 595 auto NoLongerGoodCandidate = [this]( 596 const StoreToLoadForwardingCandidate &Cand) { 597 return !isa<SCEVAddRecExpr>( 598 PSE.getSCEV(Cand.Load->getPointerOperand())) || 599 !isa<SCEVAddRecExpr>( 600 PSE.getSCEV(Cand.Store->getPointerOperand())); 601 }; 602 llvm::erase_if(Candidates, NoLongerGoodCandidate); 603 } 604 605 // Next, propagate the value stored by the store to the users of the load. 606 // Also for the first iteration, generate the initial value of the load. 607 SCEVExpander SEE(*PSE.getSE(), L->getHeader()->getModule()->getDataLayout(), 608 "storeforward"); 609 for (const auto &Cand : Candidates) 610 propagateStoredValueToLoadUsers(Cand, SEE); 611 NumLoopLoadEliminted += Candidates.size(); 612 613 return true; 614 } 615 616 private: 617 Loop *L; 618 619 /// Maps the load/store instructions to their index according to 620 /// program order. 621 DenseMap<Instruction *, unsigned> InstOrder; 622 623 // Analyses used. 624 LoopInfo *LI; 625 const LoopAccessInfo &LAI; 626 DominatorTree *DT; 627 BlockFrequencyInfo *BFI; 628 ProfileSummaryInfo *PSI; 629 PredicatedScalarEvolution PSE; 630 }; 631 632 } // end anonymous namespace 633 634 static bool eliminateLoadsAcrossLoops(Function &F, LoopInfo &LI, 635 DominatorTree &DT, 636 BlockFrequencyInfo *BFI, 637 ProfileSummaryInfo *PSI, 638 ScalarEvolution *SE, AssumptionCache *AC, 639 LoopAccessInfoManager &LAIs) { 640 // Build up a worklist of inner-loops to transform to avoid iterator 641 // invalidation. 642 // FIXME: This logic comes from other passes that actually change the loop 643 // nest structure. It isn't clear this is necessary (or useful) for a pass 644 // which merely optimizes the use of loads in a loop. 645 SmallVector<Loop *, 8> Worklist; 646 647 bool Changed = false; 648 649 for (Loop *TopLevelLoop : LI) 650 for (Loop *L : depth_first(TopLevelLoop)) { 651 Changed |= simplifyLoop(L, &DT, &LI, SE, AC, /*MSSAU*/ nullptr, false); 652 // We only handle inner-most loops. 653 if (L->isInnermost()) 654 Worklist.push_back(L); 655 } 656 657 // Now walk the identified inner loops. 658 for (Loop *L : Worklist) { 659 // Match historical behavior 660 if (!L->isRotatedForm() || !L->getExitingBlock()) 661 continue; 662 // The actual work is performed by LoadEliminationForLoop. 663 LoadEliminationForLoop LEL(L, &LI, LAIs.getInfo(*L), &DT, BFI, PSI); 664 Changed |= LEL.processLoop(); 665 if (Changed) 666 LAIs.clear(); 667 } 668 return Changed; 669 } 670 671 PreservedAnalyses LoopLoadEliminationPass::run(Function &F, 672 FunctionAnalysisManager &AM) { 673 auto &LI = AM.getResult<LoopAnalysis>(F); 674 // There are no loops in the function. Return before computing other expensive 675 // analyses. 676 if (LI.empty()) 677 return PreservedAnalyses::all(); 678 auto &SE = AM.getResult<ScalarEvolutionAnalysis>(F); 679 auto &DT = AM.getResult<DominatorTreeAnalysis>(F); 680 auto &AC = AM.getResult<AssumptionAnalysis>(F); 681 auto &MAMProxy = AM.getResult<ModuleAnalysisManagerFunctionProxy>(F); 682 auto *PSI = MAMProxy.getCachedResult<ProfileSummaryAnalysis>(*F.getParent()); 683 auto *BFI = (PSI && PSI->hasProfileSummary()) ? 684 &AM.getResult<BlockFrequencyAnalysis>(F) : nullptr; 685 LoopAccessInfoManager &LAIs = AM.getResult<LoopAccessAnalysis>(F); 686 687 bool Changed = eliminateLoadsAcrossLoops(F, LI, DT, BFI, PSI, &SE, &AC, LAIs); 688 689 if (!Changed) 690 return PreservedAnalyses::all(); 691 692 PreservedAnalyses PA; 693 PA.preserve<DominatorTreeAnalysis>(); 694 PA.preserve<LoopAnalysis>(); 695 return PA; 696 } 697