58#include <forward_list>
64#define LLE_OPTION "loop-load-elim"
65#define DEBUG_TYPE LLE_OPTION
68 "runtime-check-per-loop-load-elim",
cl::Hidden,
69 cl::desc(
"Max number of memchecks allowed per eliminated load on average"),
74 cl::desc(
"The maximum number of SCEV checks allowed for Loop "
77STATISTIC(NumLoopLoadEliminted,
"Number of loads eliminated by LLE");
82struct StoreToLoadForwardingCandidate {
87 : Load(Load), Store(Store) {}
94 Value *LoadPtr =
Load->getPointerOperand();
97 auto &
DL =
Load->getDataLayout();
101 DL.getTypeSizeInBits(LoadType) ==
103 "Should be a known dependence");
105 int64_t StrideLoad =
getPtrStride(PSE, LoadType, LoadPtr, L).value_or(0);
106 int64_t StrideStore =
getPtrStride(PSE, LoadType, StorePtr, L).value_or(0);
107 if (!StrideLoad || !StrideStore || StrideLoad != StrideStore)
117 if (std::abs(StrideLoad) != 1)
120 unsigned TypeByteSize =
DL.getTypeAllocSize(LoadType);
122 auto *LoadPtrSCEV = cast<SCEVAddRecExpr>(PSE.
getSCEV(LoadPtr));
123 auto *StorePtrSCEV = cast<SCEVAddRecExpr>(PSE.
getSCEV(StorePtr));
127 auto *Dist = dyn_cast<SCEVConstant>(
131 const APInt &Val = Dist->getAPInt();
132 return Val == TypeByteSize * StrideLoad;
135 Value *getLoadPtr()
const {
return Load->getPointerOperand(); }
139 const StoreToLoadForwardingCandidate &Cand) {
140 OS << *Cand.Store <<
" -->\n";
154 L->getLoopLatches(Latches);
162 return Load->getParent() != L->getHeader();
168class LoadEliminationForLoop {
173 :
L(
L), LI(LI), LAI(LAI), DT(DT),
BFI(
BFI), PSI(PSI), PSE(LAI.getPSE()) {}
180 std::forward_list<StoreToLoadForwardingCandidate>
182 std::forward_list<StoreToLoadForwardingCandidate> Candidates;
195 for (
const auto &Dep : *Deps) {
197 Instruction *Destination = Dep.getDestination(DepChecker);
201 if (isa<LoadInst>(Source))
202 LoadsWithUnknownDependence.
insert(Source);
203 if (isa<LoadInst>(Destination))
204 LoadsWithUnknownDependence.
insert(Destination);
208 if (Dep.isBackward())
214 assert(Dep.isForward() &&
"Needs to be a forward dependence");
216 auto *
Store = dyn_cast<StoreInst>(Source);
219 auto *
Load = dyn_cast<LoadInst>(Destination);
226 Store->getDataLayout()))
229 Candidates.emplace_front(Load, Store);
232 if (!LoadsWithUnknownDependence.
empty())
233 Candidates.remove_if([&](
const StoreToLoadForwardingCandidate &
C) {
234 return LoadsWithUnknownDependence.
count(
C.Load);
242 auto I = InstOrder.find(Inst);
243 assert(
I != InstOrder.end() &&
"No index for instruction");
266 void removeDependencesFromMultipleStores(
267 std::forward_list<StoreToLoadForwardingCandidate> &Candidates) {
270 using LoadToSingleCandT =
272 LoadToSingleCandT LoadToSingleCand;
274 for (
const auto &Cand : Candidates) {
276 LoadToSingleCandT::iterator Iter;
278 std::tie(Iter, NewElt) =
279 LoadToSingleCand.
insert(std::make_pair(Cand.Load, &Cand));
281 const StoreToLoadForwardingCandidate *&OtherCand = Iter->second;
283 if (OtherCand ==
nullptr)
289 if (Cand.Store->getParent() == OtherCand->Store->getParent() &&
290 Cand.isDependenceDistanceOfOne(PSE, L) &&
291 OtherCand->isDependenceDistanceOfOne(PSE, L)) {
293 if (getInstrIndex(OtherCand->Store) < getInstrIndex(Cand.Store))
300 Candidates.remove_if([&](
const StoreToLoadForwardingCandidate &Cand) {
301 if (LoadToSingleCand[Cand.Load] != &Cand) {
303 dbgs() <<
"Removing from candidates: \n"
305 <<
" The load may have multiple stores forwarding to "
318 bool needsChecking(
unsigned PtrIdx1,
unsigned PtrIdx2,
325 return ((PtrsWrittenOnFwdingPath.
count(Ptr1) && CandLoadPtrs.
count(Ptr2)) ||
326 (PtrsWrittenOnFwdingPath.
count(Ptr2) && CandLoadPtrs.
count(Ptr1)));
354 [&](
const StoreToLoadForwardingCandidate &
A,
355 const StoreToLoadForwardingCandidate &
B) {
356 return getInstrIndex(
A.Load) <
357 getInstrIndex(
B.Load);
362 [&](
const StoreToLoadForwardingCandidate &
A,
363 const StoreToLoadForwardingCandidate &
B) {
364 return getInstrIndex(
A.Store) <
365 getInstrIndex(
B.Store);
375 if (
auto *S = dyn_cast<StoreInst>(
I))
376 PtrsWrittenOnFwdingPath.
insert(S->getPointerOperand());
379 std::for_each(MemInstrs.begin() + getInstrIndex(FirstStore) + 1,
380 MemInstrs.end(), InsertStorePtr);
381 std::for_each(MemInstrs.begin(), &MemInstrs[getInstrIndex(LastLoad)],
384 return PtrsWrittenOnFwdingPath;
393 findPointersWrittenOnForwardingPath(Candidates);
397 for (
const auto &Candidate : Candidates)
398 CandLoadPtrs.
insert(Candidate.getLoadPtr());
403 copy_if(AllChecks, std::back_inserter(Checks),
405 for (
auto PtrIdx1 :
Check.first->Members)
406 for (
auto PtrIdx2 :
Check.second->Members)
407 if (needsChecking(PtrIdx1, PtrIdx2, PtrsWrittenOnFwdingPath,
422 propagateStoredValueToLoadUsers(
const StoreToLoadForwardingCandidate &Cand,
439 Value *
Ptr = Cand.Load->getPointerOperand();
440 auto *PtrSCEV = cast<SCEVAddRecExpr>(PSE.
getSCEV(
Ptr));
441 auto *PH =
L->getLoopPreheader();
442 assert(PH &&
"Preheader should exist!");
443 Value *InitialPtr =
SEE.expandCodeFor(PtrSCEV->getStart(),
Ptr->getType(),
444 PH->getTerminator());
446 new LoadInst(Cand.Load->getType(), InitialPtr,
"load_initial",
447 false, Cand.Load->getAlign(),
448 PH->getTerminator()->getIterator());
456 PHI->insertBefore(
L->getHeader()->begin());
457 PHI->addIncoming(Initial, PH);
460 Type *StoreType = Cand.Store->getValueOperand()->getType();
461 auto &
DL = Cand.Load->getDataLayout();
464 assert(
DL.getTypeSizeInBits(LoadType) ==
DL.getTypeSizeInBits(StoreType) &&
465 "The type sizes should match!");
467 Value *StoreValue = Cand.Store->getValueOperand();
468 if (LoadType != StoreType) {
470 "store_forward_cast",
471 Cand.Store->getIterator());
475 cast<Instruction>(StoreValue)->setDebugLoc(Cand.Load->getDebugLoc());
478 PHI->addIncoming(StoreValue,
L->getLoopLatch());
480 Cand.Load->replaceAllUsesWith(
PHI);
481 PHI->setDebugLoc(Cand.Load->getDebugLoc());
487 LLVM_DEBUG(
dbgs() <<
"\nIn \"" <<
L->getHeader()->getParent()->getName()
488 <<
"\" checking " << *L <<
"\n");
509 auto StoreToLoadDependences = findStoreToLoadDependences(LAI);
510 if (StoreToLoadDependences.empty())
519 removeDependencesFromMultipleStores(StoreToLoadDependences);
520 if (StoreToLoadDependences.empty())
525 for (
const StoreToLoadForwardingCandidate &Cand : StoreToLoadDependences) {
541 if (!Cand.isDependenceDistanceOfOne(PSE, L))
544 assert(isa<SCEVAddRecExpr>(PSE.
getSCEV(Cand.Load->getPointerOperand())) &&
545 "Loading from something other than indvar?");
547 isa<SCEVAddRecExpr>(PSE.
getSCEV(Cand.Store->getPointerOperand())) &&
548 "Storing to something other than indvar?");
554 <<
". Valid store-to-load forwarding across the loop backedge\n");
556 if (Candidates.
empty())
575 if (!
L->isLoopSimplifyForm()) {
583 "convergent calls\n");
587 auto *HeaderBB =
L->getHeader();
589 PGSOQueryType::IRPass)) {
591 dbgs() <<
"Versioning is needed but not allowed when optimizing "
604 auto NoLongerGoodCandidate = [
this](
605 const StoreToLoadForwardingCandidate &Cand) {
606 return !isa<SCEVAddRecExpr>(
607 PSE.
getSCEV(Cand.Load->getPointerOperand())) ||
608 !isa<SCEVAddRecExpr>(
609 PSE.
getSCEV(Cand.Store->getPointerOperand()));
618 for (
const auto &Cand : Candidates)
619 propagateStoredValueToLoadUsers(Cand,
SEE);
620 NumLoopLoadEliminted += Candidates.size();
656 bool Changed =
false;
658 for (
Loop *TopLevelLoop : LI)
660 Changed |=
simplifyLoop(L, &DT, &LI, SE, AC,
nullptr,
false);
662 if (L->isInnermost())
667 for (
Loop *L : Worklist) {
669 if (!L->isRotatedForm() || !L->getExitingBlock())
672 LoadEliminationForLoop LEL(L, &LI, LAIs.
getInfo(*L), &DT, BFI, PSI);
673 Changed |= LEL.processLoop();
692 auto *BFI = (PSI && PSI->hasProfileSummary()) ?
for(const MachineOperand &MO :llvm::drop_begin(OldMI.operands(), Desc.getNumOperands()))
assert(UImm &&(UImm !=~static_cast< T >(0)) &&"Invalid immediate!")
This file implements a class to represent arbitrary precision integral constant values and operations...
MachineBasicBlock MachineBasicBlock::iterator DebugLoc DL
static GCRegistry::Add< OcamlGC > B("ocaml", "ocaml 3.10-compatible GC")
static GCRegistry::Add< ErlangGC > A("erlang", "erlang-compatible garbage collector")
This file defines the DenseMap class.
This file builds on the ADT/GraphTraits.h file to build generic depth first graph iterator.
This is the interface for a simple mod/ref and alias analysis over globals.
This header defines various interfaces for pass management in LLVM.
This header provides classes for managing per-loop analyses.
static bool eliminateLoadsAcrossLoops(Function &F, LoopInfo &LI, DominatorTree &DT, BlockFrequencyInfo *BFI, ProfileSummaryInfo *PSI, ScalarEvolution *SE, AssumptionCache *AC, LoopAccessInfoManager &LAIs)
static cl::opt< unsigned > LoadElimSCEVCheckThreshold("loop-load-elimination-scev-check-threshold", cl::init(8), cl::Hidden, cl::desc("The maximum number of SCEV checks allowed for Loop " "Load Elimination"))
static bool isLoadConditional(LoadInst *Load, Loop *L)
Return true if the load is not executed on all paths in the loop.
static bool doesStoreDominatesAllLatches(BasicBlock *StoreBlock, Loop *L, DominatorTree *DT)
Check if the store dominates all latches, so as long as there is no intervening store this value will...
static cl::opt< unsigned > CheckPerElim("runtime-check-per-loop-load-elim", cl::Hidden, cl::desc("Max number of memchecks allowed per eliminated load on average"), cl::init(1))
This header defines the LoopLoadEliminationPass object.
This file defines the SmallPtrSet class.
This file defines the SmallVector class.
This file defines the 'Statistic' class, which is designed to be an easy way to expose various metric...
#define STATISTIC(VARNAME, DESC)
Class for arbitrary precision integers.
A container for analyses that lazily runs them and caches their results.
PassT::Result & getResult(IRUnitT &IR, ExtraArgTs... ExtraArgs)
Get the result of an analysis pass for a given IR unit.
A function analysis which provides an AssumptionCache.
A cache of @llvm.assume calls within a function.
LLVM Basic Block Representation.
Analysis pass which computes BlockFrequencyInfo.
BlockFrequencyInfo pass uses BlockFrequencyInfoImpl implementation to estimate IR basic block frequen...
static LLVM_ABI bool isBitOrNoopPointerCastable(Type *SrcTy, Type *DestTy, const DataLayout &DL)
Check whether a bitcast, inttoptr, or ptrtoint cast between these types is valid and a no-op.
static LLVM_ABI CastInst * CreateBitOrPointerCast(Value *S, Type *Ty, const Twine &Name="", InsertPosition InsertBefore=nullptr)
Create a BitCast, a PtrToInt, or an IntToPTr cast instruction.
static DebugLoc getDropped()
std::pair< iterator, bool > insert(const std::pair< KeyT, ValueT > &KV)
Analysis pass which computes a DominatorTree.
Concrete subclass of DominatorTreeBase that is used to compute a normal dominator tree.
LLVM_ABI bool dominates(const BasicBlock *BB, const Use &U) const
Return true if the (end of the) basic block BB dominates the use U.
An instruction for reading from memory.
This analysis provides dependence information for the memory accesses of a loop.
LLVM_ABI const LoopAccessInfo & getInfo(Loop &L, bool AllowPartial=false)
Drive the analysis of memory accesses in the loop.
const MemoryDepChecker & getDepChecker() const
the Memory Dependence Checker which can determine the loop-independent and loop-carried dependences b...
const RuntimePointerChecking * getRuntimePointerChecking() const
const PredicatedScalarEvolution & getPSE() const
Used to add runtime SCEV checks.
bool hasConvergentOp() const
Return true if there is a convergent operation in the loop.
Analysis pass that exposes the LoopInfo for a function.
This class emits a version of the loop where run-time checks ensure that may-alias pointers can't ove...
Represents a single loop in the control flow graph.
const SmallVectorImpl< Instruction * > & getMemoryInstructions() const
The vector of memory access instructions.
const SmallVectorImpl< Dependence > * getDependences() const
Returns the memory dependences.
DenseMap< Instruction *, unsigned > generateInstructionOrderMap() const
Generate a mapping between the memory instructions and their indices according to program order.
An analysis over an "inner" IR unit that provides access to an analysis manager over a "outer" IR uni...
static PHINode * Create(Type *Ty, unsigned NumReservedValues, const Twine &NameStr="", InsertPosition InsertBefore=nullptr)
Constructors - NumReservedValues is a hint for the number of incoming edges that this phi node will h...
An interface layer with SCEV used to manage how we see SCEV expressions for values in the context of ...
ScalarEvolution * getSE() const
Returns the ScalarEvolution analysis used.
LLVM_ABI const SCEVPredicate & getPredicate() const
LLVM_ABI const SCEV * getSCEV(Value *V)
Returns the SCEV expression of V, in the context of the current SCEV predicate.
A set of analyses that are preserved following a run of a transformation pass.
static PreservedAnalyses all()
Construct a special preserved set that preserves all passes.
PreservedAnalyses & preserve()
Mark an analysis as preserved.
An analysis pass based on the new PM to deliver ProfileSummaryInfo.
Analysis providing profile information.
LLVM_ABI void printChecks(raw_ostream &OS, const SmallVectorImpl< RuntimePointerCheck > &Checks, unsigned Depth=0) const
Print Checks.
const SmallVectorImpl< RuntimePointerCheck > & getChecks() const
Returns the checks that generateChecks created.
const PointerInfo & getPointerInfo(unsigned PtrIdx) const
Return PointerInfo for pointer at index PtrIdx.
This class uses information about analyze scalars to rewrite expressions in canonical form.
virtual unsigned getComplexity() const
Returns the estimated complexity of this predicate.
virtual bool isAlwaysTrue() const =0
Returns true if the predicate is always true.
Analysis pass that exposes the ScalarEvolution for a function.
The main scalar evolution driver.
LLVM_ABI const SCEV * getMinusSCEV(const SCEV *LHS, const SCEV *RHS, SCEV::NoWrapFlags Flags=SCEV::FlagAnyWrap, unsigned Depth=0)
Return LHS-RHS.
A templated base class for SmallPtrSet which provides the typesafe interface that is common across al...
size_type count(ConstPtrType Ptr) const
count - Return 1 if the specified pointer is in the set, 0 otherwise.
std::pair< iterator, bool > insert(PtrType Ptr)
Inserts Ptr if and only if there is no element in the container equal to Ptr.
SmallPtrSet - This class implements a set which is optimized for holding SmallSize or less elements.
This class consists of common code factored out of the SmallVector class to reduce code duplication b...
void push_back(const T &Elt)
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
An instruction for storing to memory.
The instances of the Type class are immutable: once they are created, they are never changed.
LLVM_ABI unsigned getPointerAddressSpace() const
Get the address space of this pointer or pointer vector type.
LLVM Value Representation.
Type * getType() const
All values are typed, get the type of this value.
This class implements an extremely fast bulk output stream that can only output to a stream.
raw_ostream & indent(unsigned NumSpaces)
indent - Insert 'NumSpaces' spaces.
@ C
The default llvm calling convention, compatible with C.
initializer< Ty > init(const Ty &Val)
This is an optimization pass for GlobalISel generic memory operations.
LLVM_ABI bool simplifyLoop(Loop *L, DominatorTree *DT, LoopInfo *LI, ScalarEvolution *SE, AssumptionCache *AC, MemorySSAUpdater *MSSAU, bool PreserveLCSSA)
Simplify each loop in a loop nest recursively.
auto min_element(R &&Range)
Provide wrappers to std::min_element which take ranges instead of having to pass begin/end explicitly...
bool all_of(R &&range, UnaryPredicate P)
Provide wrappers to std::all_of which take ranges instead of having to pass begin/end explicitly.
std::pair< const RuntimeCheckingPtrGroup *, const RuntimeCheckingPtrGroup * > RuntimePointerCheck
A memcheck which made up of a pair of grouped pointers.
LLVM_ABI bool shouldOptimizeForSize(const MachineFunction *MF, ProfileSummaryInfo *PSI, const MachineBlockFrequencyInfo *BFI, PGSOQueryType QueryType=PGSOQueryType::Other)
Returns true if machine function MF is suggested to be size-optimized based on the profile.
OutputIt copy_if(R &&Range, OutputIt Out, UnaryPredicate P)
Provide wrappers to std::copy_if which take ranges instead of having to pass begin/end explicitly.
LLVM_ABI raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
LLVM_ABI std::optional< int64_t > getPtrStride(PredicatedScalarEvolution &PSE, Type *AccessTy, Value *Ptr, const Loop *Lp, const DenseMap< Value *, const SCEV * > &StridesMap=DenseMap< Value *, const SCEV * >(), bool Assume=false, bool ShouldCheckWrap=true)
If the pointer has a constant stride return it in units of the access type size.
auto max_element(R &&Range)
Provide wrappers to std::max_element which take ranges instead of having to pass begin/end explicitly...
raw_ostream & operator<<(raw_ostream &OS, const APFixedPoint &FX)
void erase_if(Container &C, UnaryPredicate P)
Provide a container algorithm similar to C++ Library Fundamentals v2's erase_if which is equivalent t...
Type * getLoadStoreType(const Value *I)
A helper function that returns the type of a load or store instruction.
iterator_range< df_iterator< T > > depth_first(const T &G)
void swap(llvm::BitVector &LHS, llvm::BitVector &RHS)
Implement std::swap in terms of BitVector swap.
PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM)
TrackingVH< Value > PointerValue
Holds the pointer value that we need to check.