Go to the documentation of this file.
14 #ifndef LLVM_ANALYSIS_LOOPACCESSANALYSIS_H
15 #define LLVM_ANALYSIS_LOOPACCESSANALYSIS_H
31 class SCEVUnionPredicate;
172 : PSE(PSE), InnermostLoop(L) {}
197 return MaxSafeVectorWidthInBits == UINT_MAX;
207 return MaxSafeVectorWidthInBits;
213 return FoundNonConstantDistanceDependence &&
221 return RecordDependences ? &Dependences :
nullptr;
237 for (
unsigned I = 0;
I < InstMap.size(); ++
I)
250 auto I = Accesses.find({Ptr, IsWrite});
251 if (
I != Accesses.end())
264 const Loop *InnermostLoop;
273 unsigned AccessIdx = 0;
282 uint64_t MaxSafeVectorWidthInBits = -1U;
286 bool FoundNonConstantDistanceDependence =
false;
296 bool RecordDependences =
true;
323 bool couldPreventStoreLoadForward(
uint64_t Distance,
uint64_t TypeByteSize);
331 class RuntimePointerChecking;
431 bool WritePtr,
unsigned DepSetId,
unsigned ASId,
440 bool UseDependencies);
454 if (!CanUseDiffCheck)
474 unsigned Depth = 0)
const;
491 unsigned PtrIdx1,
unsigned PtrIdx2);
510 bool UseDependencies);
531 bool CanUseDiffCheck =
true;
574 return PtrRtChecking.get();
580 return PtrRtChecking->getNumberOfChecks();
606 bool isWrite)
const {
607 return DepChecker->getInstructionsForAccess(Ptr, isWrite);
623 return HasDependenceInvolvingLoopInvariantAddress;
628 return StoresToInvariantAddresses;
645 bool canAnalyzeLoop();
659 void collectStridedAccess(
Value *LoadOrStoreInst);
664 void emitUnsafeDependenceRemark();
666 std::unique_ptr<PredicatedScalarEvolution> PSE;
670 std::unique_ptr<RuntimePointerChecking> PtrRtChecking;
674 std::unique_ptr<MemoryDepChecker> DepChecker;
678 unsigned NumLoads = 0;
679 unsigned NumStores = 0;
684 bool CanVecMem =
false;
685 bool HasConvergentOp =
false;
688 bool HasDependenceInvolvingLoopInvariantAddress =
false;
695 std::unique_ptr<OptimizationRemarkAnalysis> Report;
733 bool Assume =
false,
bool ShouldCheckWrap =
true);
741 Value *PtrB,
const DataLayout &
DL,
742 ScalarEvolution &SE,
bool StrictCheck =
false,
757 SmallVectorImpl<unsigned> &SortedIndices);
762 ScalarEvolution &SE,
bool CheckType =
true);
788 LoopAccessInfoMap.clear();
bool sortPtrAccesses(ArrayRef< Value * > VL, Type *ElemTy, const DataLayout &DL, ScalarEvolution &SE, SmallVectorImpl< unsigned > &SortedIndices)
Attempt to sort the pointers in VL and return the sorted indices in SortedIndices,...
bool isBackward() const
Lexically backward dependence.
Checks memory dependences among accesses to the same underlying object to determine whether there vec...
This analysis provides dependence information for the memory accesses of a loop.
This is an optimization pass for GlobalISel generic memory operations.
std::pair< const RuntimeCheckingPtrGroup *, const RuntimeCheckingPtrGroup * > RuntimePointerCheck
A memcheck which made up of a pair of grouped pointers.
bool isUniform(Value *V) const
Returns true if the value V is uniform within the loop.
MemoryDepChecker(PredicatedScalarEvolution &PSE, const Loop *L)
RuntimeCheckingPtrGroup(unsigned Index, RuntimePointerChecking &RtCheck)
Create a new pointer checking group containing a single pointer, with index Index in RtCheck.
Represents a single loop in the control flow graph.
An interface layer with SCEV used to manage how we see SCEV expressions for values in the context of ...
Instruction * getSource(const LoopAccessInfo &LAI) const
Return the source instruction of the dependence.
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
static LLVM_ATTRIBUTE_ALWAYS_INLINE bool CheckType(const unsigned char *MatcherTable, unsigned &MatcherIndex, SDValue N, const TargetLowering *TLI, const DataLayout &DL)
EquivalenceClasses - This represents a collection of equivalence classes and supports three efficient...
The main scalar evolution driver.
static unsigned VectorizationInterleave
Interleave factor as overridden by the user.
const LoopAccessInfo & getInfo(Loop *L)
Query the result of the loop access information for the loop L.
DenseMap< Instruction *, unsigned > generateInstructionOrderMap() const
Generate a mapping between the memory instructions and their indices according to program order.
Concrete subclass of DominatorTreeBase that is used to compute a normal dominator tree.
bool isPossiblyBackward() const
May be a lexically backward dependence type (includes Unknown).
This analysis provides dependence information for the memory accesses of a loop.
uint64_t getMaxSafeVectorWidthInBits() const
Return the number of elements that are safe to operate on simultaneously, multiplied by the size of t...
The instances of the Type class are immutable: once they are created, they are never changed.
int64_t getPtrStride(PredicatedScalarEvolution &PSE, Type *AccessTy, Value *Ptr, const Loop *Lp, const ValueToValueMap &StridesMap=ValueToValueMap(), bool Assume=false, bool ShouldCheckWrap=true)
If the pointer has a constant stride return it in units of the access type size.
bool needsChecking(const RuntimeCheckingPtrGroup &M, const RuntimeCheckingPtrGroup &N) const
Decide if we need to add a check between two groups of pointers, according to needsChecking.
The adaptor from a function pass to a loop pass computes these analyses and makes them available to t...
bool areDepsSafe(DepCandidates &AccessSets, MemAccessInfoList &CheckDeps, const ValueToValueMap &Strides)
Check whether the dependencies between the accesses are safe.
Optional< ArrayRef< PointerDiffInfo > > getDiffChecks() const
bool isConsecutiveAccess(Value *A, Value *B, const DataLayout &DL, ScalarEvolution &SE, bool CheckType=true)
Returns true if the memory operations A and B are consecutive.
SmallPtrSet - This class implements a set which is optimized for holding SmallSize or less elements.
unsigned getNumberOfChecks() const
Returns the number of run-time checks required according to needsChecking.
Dependence(unsigned Source, unsigned Destination, DepType Type)
EquivalenceClasses< MemAccessInfo > DepCandidates
Set of potential dependent memory accesses.
Value * stripIntegerCast(Value *V)
DepType
The type of the dependence.
LLVM Basic Block Representation.
bool isForward() const
Lexically forward dependence.
void print(raw_ostream &OS, const Module *M=nullptr) const override
Print the result of the analysis when invoked with -analyze.
Result run(Loop &L, LoopAnalysisManager &AM, LoopStandardAnalysisResults &AR)
bool hasDependenceInvolvingLoopInvariantAddress() const
If the loop has memory dependence involving an invariant address, i.e.
VectorizationSafetyStatus
Type to keep track of the status of the dependence check.
static bool blockNeedsPredication(BasicBlock *BB, Loop *TheLoop, DominatorTree *DT)
Return true if the block BB needs to be predicated in order for the loop to be vectorized.
DenseMap< const Value *, Value * > ValueToValueMap
ArrayRef< unsigned > getOrderForAccess(Value *Ptr, bool IsWrite) const
Return the program order indices for the access location (Ptr, IsWrite).
unsigned getNumLoads() const
unsigned Source
Index of the source of the dependence in the InstMap vector.
Represent the analysis usage information of a pass.
void print(raw_ostream &OS, unsigned Depth, const SmallVectorImpl< Instruction * > &Instrs) const
Print the dependence.
unsigned AddressSpace
Address space of the involved pointers.
static GCRegistry::Add< OcamlGC > B("ocaml", "ocaml 3.10-compatible GC")
void addAccess(StoreInst *SI)
Register the location (instructions are given increasing numbers) of a write access.
@ BackwardVectorizableButPreventsForwarding
This class implements an extremely fast bulk output stream that can only output to a stream.
bool hasStride(Value *V) const
Pointer has a symbolic stride.
const SmallVectorImpl< Dependence > * getDependences() const
Returns the memory dependences.
const SCEV * Start
Holds the smallest byte address accessed by the pointer throughout all iterations of the loop.
Optional< int > getPointersDiff(Type *ElemTyA, Value *PtrA, Type *ElemTyB, Value *PtrB, const DataLayout &DL, ScalarEvolution &SE, bool StrictCheck=false, bool CheckType=true)
Returns the distance between the pointers PtrA and PtrB iff they are compatible and it is possible to...
RuntimePointerChecking(MemoryDepChecker &DC, ScalarEvolution *SE)
void reset()
Reset the state of the pointer runtime information.
unsigned AliasSetId
Holds the id of the disjoint alias set to which this pointer belongs.
bool hasConvergentOp() const
Return true if there is a convergent operation in the loop.
uint64_t getMaxSafeDepDistBytes()
The maximum number of bytes of a vector register we can vectorize the accesses safely with.
SmallVector< Instruction *, 4 > getInstructionsForAccess(Value *Ptr, bool isWrite) const
Find the set of instructions that read or write via Ptr.
This class represents an analyzed expression in the program.
An instruction for storing to memory.
const ValueToValueMap & getSymbolicStrides() const
If an access has a symbolic strides, this maps the pointer value to the stride symbol.
Holds information about the memory runtime legality checks to verify that a group of pointers do not ...
static unsigned VectorizationFactor
VF as overridden by the user.
bool Need
This flag indicates if we need to add the runtime check.
Dependece between memory access instructions.
unsigned DependencySetId
Holds the id of the set of pointers that could be dependent because of a shared underlying object.
SmallVector< Instruction *, 4 > getInstructionsForAccess(Value *Ptr, bool isWrite) const
Return the list of instructions that use Ptr to read or write memory.
const SmallVectorImpl< RuntimePointerCheck > & getChecks() const
Returns the checks that generateChecks created.
SmallVector< RuntimeCheckingPtrGroup, 2 > CheckingGroups
Holds a partitioning of pointers into "check groups".
SmallVector< MemAccessInfo, 8 > MemAccessInfoList
A special type used by analysis passes to provide an address that identifies that particular analysis...
const RuntimePointerChecking * getRuntimePointerChecking() const
Drive the analysis of memory accesses in the loop.
static const unsigned MaxVectorWidth
Maximum SIMD width.
const OptimizationRemarkAnalysis * getReport() const
The diagnostics report generated for the analysis.
const ArrayRef< StoreInst * > getStoresToInvariantAddresses() const
Return the list of stores to invariant addresses.
void releaseMemory() override
releaseMemory() - This member can be implemented by a pass if it wants to be able to release its memo...
bool isSafeForVectorization() const
No memory dependence was encountered that would inhibit vectorization.
const SmallVectorImpl< Instruction * > & getMemoryInstructions() const
The vector of memory access instructions.
StandardInstrumentations SI(Debug, VerifyEach)
static unsigned RuntimeMemoryCheckThreshold
\When performing memory disambiguation checks at runtime do not make more than this number of compari...
bool canVectorizeMemory() const
Return true we can analyze the memory accesses in the loop and there are no memory dependence cycles.
ScalarEvolution * getSE() const
A Module instance is used to store all the information related to an LLVM module.
A CRTP mix-in that provides informational APIs needed for analysis passes.
const SCEV * High
The SCEV expression which represents the upper bound of all the pointers in this group.
const SCEV * Low
The SCEV expression which represents the lower bound of all the pointers in this group.
const MemoryDepChecker & getDepChecker() const
the Memory Dependence Checker which can determine the loop-independent and loop-carried dependences b...
const SCEV * End
Holds the largest byte address accessed by the pointer throughout all iterations of the loop,...
const SCEV * replaceSymbolicStrideSCEV(PredicatedScalarEvolution &PSE, const ValueToValueMap &PtrToStride, Value *Ptr)
Return the SCEV corresponding to a pointer with the symbolic stride replaced with constant one,...
StringRef - Represent a constant reference to a string, i.e.
PointerIntPair< Value *, 1, bool > MemAccessInfo
MachineBasicBlock MachineBasicBlock::iterator DebugLoc DL
bool addPointer(unsigned Index, RuntimePointerChecking &RtCheck)
Tries to add the pointer recorded in RtCheck at index Index to this pointer checking group.
add sub stmia L5 ldr r0 bl L_printf $stub Instead of a and a wouldn t it be better to do three moves *Return an aggregate type is even return S
bool NeedsFreeze
True if the pointer expressions needs to be frozen after expansion.
An instruction for reading from memory.
uint64_t getMaxSafeDepDistBytes() const
static bool isInterleaveForced()
True if force-vector-interleave was specified by the user.
const SCEV * Expr
SCEV for the access.
void getAnalysisUsage(AnalysisUsage &AU) const override
getAnalysisUsage - This function should be overriden by passes that need analysis information to do t...
SmallVector< PointerInfo, 2 > Pointers
Information about the pointers that may require checking.
unsigned getNumStores() const
static bool arePointersInSamePartition(const SmallVectorImpl< int > &PtrToPartition, unsigned PtrIdx1, unsigned PtrIdx2)
Check if pointers are in the same partition.
bool shouldRetryWithRuntimeCheck() const
In same cases when the dependency check fails we can still vectorize the loop with a dynamic array ac...
LoopAccessLegacyAnalysis()
bool isSafeForAnyVectorWidth() const
Return true if the number of elements that are safe to operate on simultaneously is not bounded.
TrackingVH< Value > PointerValue
Holds the pointer value that we need to check.
bool empty() const
No run-time memory checking is necessary.
void printChecks(raw_ostream &OS, const SmallVectorImpl< RuntimePointerCheck > &Checks, unsigned Depth=0) const
Print Checks.
LoopAccessInfo(Loop *L, ScalarEvolution *SE, const TargetLibraryInfo *TLI, AAResults *AA, DominatorTree *DT, LoopInfo *LI)
static const char * DepName[]
String version of the types.
bool IsWritePtr
Holds the information if this pointer is used for writing to memory.
Provides information about what library functions are available for the current target.
unsigned getNumRuntimePointerChecks() const
Number of memchecks required to prove independence of otherwise may-alias pointers.
void insert(Loop *Lp, Value *Ptr, const SCEV *PtrExpr, Type *AccessTy, bool WritePtr, unsigned DepSetId, unsigned ASId, PredicatedScalarEvolution &PSE, bool NeedsFreeze)
Insert a pointer and calculate the start and end SCEVs.
DepType Type
The type of the dependence.
void print(raw_ostream &OS, unsigned Depth=0) const
Print the information about the memory accesses in the loop.
Collection of parameters shared beetween the Loop Vectorizer and the Loop Access Analysis.
const PointerInfo & getPointerInfo(unsigned PtrIdx) const
Return PointerInfo for pointer at index PtrIdx.
PointerDiffInfo(const SCEV *SrcStart, const SCEV *SinkStart, unsigned AccessSize, bool NeedsFreeze)
static VectorizationSafetyStatus isSafeForVectorization(DepType Type)
Dependence types that don't prevent vectorization.
A container for analyses that lazily runs them and caches their results.
FunctionPass class - This class is used to implement most global optimizations.
Common register allocation spilling lr str ldr sxth r3 ldr mla r4 can lr mov lr str ldr sxth r3 mla r4 and then merge mul and lr str ldr sxth r3 mla r4 It also increase the likelihood the store may become dead bb27 Successors according to LLVM BB
PointerInfo(Value *PointerValue, const SCEV *Start, const SCEV *End, bool IsWritePtr, unsigned DependencySetId, unsigned AliasSetId, const SCEV *Expr, bool NeedsFreeze)
const PredicatedScalarEvolution & getPSE() const
Used to add runtime SCEV checks.
MapVector< const Value *, unsigned > OrderMap
unsigned Destination
Index of the destination of the dependence in the InstMap vector.
void print(raw_ostream &OS, unsigned Depth=0) const
Print the list run-time memory checks necessary.
SmallVector< unsigned, 2 > Members
Indices of all the pointers that constitute this grouping.
LLVM Value Representation.
bool NeedsFreeze
Whether the pointer needs to be frozen after expansion, e.g.
@ ForwardButPreventsForwarding
Instruction * getDestination(const LoopAccessInfo &LAI) const
Return the destination instruction of the dependence.
bool runOnFunction(Function &F) override
runOnFunction - Virtual method overriden by subclasses to do the per-function processing of the pass.
@ PossiblySafeWithRtChecks