diff options
Diffstat (limited to 'include/llvm/Analysis/LoopAccessAnalysis.h')
| -rw-r--r-- | include/llvm/Analysis/LoopAccessAnalysis.h | 177 |
1 files changed, 130 insertions, 47 deletions
diff --git a/include/llvm/Analysis/LoopAccessAnalysis.h b/include/llvm/Analysis/LoopAccessAnalysis.h index 871d35e99b748..ceee1be5e1e75 100644 --- a/include/llvm/Analysis/LoopAccessAnalysis.h +++ b/include/llvm/Analysis/LoopAccessAnalysis.h @@ -228,7 +228,7 @@ public: /// \brief The maximum number of bytes of a vector register we can vectorize /// the accesses safely with. - unsigned getMaxSafeDepDistBytes() { return MaxSafeDepDistBytes; } + uint64_t getMaxSafeDepDistBytes() { return MaxSafeDepDistBytes; } /// \brief In same cases when the dependency check fails we can still /// vectorize the loop with a dynamic array access check. @@ -284,7 +284,7 @@ private: unsigned AccessIdx; // We can access this many bytes in parallel safely. - unsigned MaxSafeDepDistBytes; + uint64_t MaxSafeDepDistBytes; /// \brief If we see a non-constant dependence distance we can still try to /// vectorize this loop with runtime checks. @@ -321,7 +321,10 @@ private: /// \brief Check whether the data dependence could prevent store-load /// forwarding. - bool couldPreventStoreLoadForward(unsigned Distance, unsigned TypeByteSize); + /// + /// \return false if we shouldn't vectorize at all or avoid larger + /// vectorization factors by limiting MaxSafeDepDistBytes. + bool couldPreventStoreLoadForward(uint64_t Distance, uint64_t TypeByteSize); }; /// \brief Holds information about the memory runtime legality checks to verify @@ -363,10 +366,10 @@ public: } /// Insert a pointer and calculate the start and end SCEVs. - /// \p We need Preds in order to compute the SCEV expression of the pointer + /// We need \p PSE in order to compute the SCEV expression of the pointer /// according to the assumptions that we've made during the analysis. /// The method might also version the pointer stride according to \p Strides, - /// and change \p Preds. + /// and add new predicates to \p PSE. void insert(Loop *Lp, Value *Ptr, bool WritePtr, unsigned DepSetId, unsigned ASId, const ValueToValueMap &Strides, PredicatedScalarEvolution &PSE); @@ -508,23 +511,53 @@ private: /// PSE must be emitted in order for the results of this analysis to be valid. class LoopAccessInfo { public: - LoopAccessInfo(Loop *L, ScalarEvolution *SE, const DataLayout &DL, - const TargetLibraryInfo *TLI, AliasAnalysis *AA, - DominatorTree *DT, LoopInfo *LI, - const ValueToValueMap &Strides); + LoopAccessInfo(Loop *L, ScalarEvolution *SE, const TargetLibraryInfo *TLI, + AliasAnalysis *AA, DominatorTree *DT, LoopInfo *LI); + + // FIXME: + // Hack for MSVC 2013 which sems like it can't synthesize this even + // with default keyword: + // LoopAccessInfo(LoopAccessInfo &&LAI) = default; + LoopAccessInfo(LoopAccessInfo &&LAI) + : PSE(std::move(LAI.PSE)), PtrRtChecking(std::move(LAI.PtrRtChecking)), + DepChecker(std::move(LAI.DepChecker)), TheLoop(LAI.TheLoop), + NumLoads(LAI.NumLoads), NumStores(LAI.NumStores), + MaxSafeDepDistBytes(LAI.MaxSafeDepDistBytes), CanVecMem(LAI.CanVecMem), + StoreToLoopInvariantAddress(LAI.StoreToLoopInvariantAddress), + Report(std::move(LAI.Report)), + SymbolicStrides(std::move(LAI.SymbolicStrides)), + StrideSet(std::move(LAI.StrideSet)) {} + // LoopAccessInfo &operator=(LoopAccessInfo &&LAI) = default; + LoopAccessInfo &operator=(LoopAccessInfo &&LAI) { + assert(this != &LAI); + + PSE = std::move(LAI.PSE); + PtrRtChecking = std::move(LAI.PtrRtChecking); + DepChecker = std::move(LAI.DepChecker); + TheLoop = LAI.TheLoop; + NumLoads = LAI.NumLoads; + NumStores = LAI.NumStores; + MaxSafeDepDistBytes = LAI.MaxSafeDepDistBytes; + CanVecMem = LAI.CanVecMem; + StoreToLoopInvariantAddress = LAI.StoreToLoopInvariantAddress; + Report = std::move(LAI.Report); + SymbolicStrides = std::move(LAI.SymbolicStrides); + StrideSet = std::move(LAI.StrideSet); + return *this; + } /// Return true we can analyze the memory accesses in the loop and there are /// no memory dependence cycles. bool canVectorizeMemory() const { return CanVecMem; } const RuntimePointerChecking *getRuntimePointerChecking() const { - return &PtrRtChecking; + return PtrRtChecking.get(); } /// \brief Number of memchecks required to prove independence of otherwise /// may-alias pointers. unsigned getNumRuntimePointerChecks() const { - return PtrRtChecking.getNumberOfChecks(); + return PtrRtChecking->getNumberOfChecks(); } /// Return true if the block BB needs to be predicated in order for the loop @@ -535,7 +568,7 @@ public: /// Returns true if the value V is uniform within the loop. bool isUniform(Value *V) const; - unsigned getMaxSafeDepDistBytes() const { return MaxSafeDepDistBytes; } + uint64_t getMaxSafeDepDistBytes() const { return MaxSafeDepDistBytes; } unsigned getNumStores() const { return NumStores; } unsigned getNumLoads() const { return NumLoads;} @@ -563,23 +596,25 @@ public: /// \brief the Memory Dependence Checker which can determine the /// loop-independent and loop-carried dependences between memory accesses. - const MemoryDepChecker &getDepChecker() const { return DepChecker; } + const MemoryDepChecker &getDepChecker() const { return *DepChecker; } /// \brief Return the list of instructions that use \p Ptr to read or write /// memory. SmallVector<Instruction *, 4> getInstructionsForAccess(Value *Ptr, bool isWrite) const { - return DepChecker.getInstructionsForAccess(Ptr, isWrite); + return DepChecker->getInstructionsForAccess(Ptr, isWrite); } + /// \brief If an access has a symbolic strides, this maps the pointer value to + /// the stride symbol. + const ValueToValueMap &getSymbolicStrides() const { return SymbolicStrides; } + + /// \brief Pointer has a symbolic stride. + bool hasStride(Value *V) const { return StrideSet.count(V); } + /// \brief Print the information about the memory accesses in the loop. void print(raw_ostream &OS, unsigned Depth = 0) const; - /// \brief Used to ensure that if the analysis was run with speculating the - /// value of symbolic strides, the client queries it with the same assumption. - /// Only used in DEBUG build but we don't want NDEBUG-dependent ABI. - unsigned NumSymbolicStrides; - /// \brief Checks existence of store to invariant address inside loop. /// If the loop has any store to invariant address, then it returns true, /// else returns false. @@ -592,11 +627,12 @@ public: /// should be re-written (and therefore simplified) according to PSE. /// A user of LoopAccessAnalysis will need to emit the runtime checks /// associated with this predicate. - PredicatedScalarEvolution PSE; + const PredicatedScalarEvolution &getPSE() const { return *PSE; } private: - /// \brief Analyze the loop. Substitute symbolic strides using Strides. - void analyzeLoop(const ValueToValueMap &Strides); + /// \brief Analyze the loop. + void analyzeLoop(AliasAnalysis *AA, LoopInfo *LI, + const TargetLibraryInfo *TLI, DominatorTree *DT); /// \brief Check if the structure of the loop allows it to be analyzed by this /// pass. @@ -604,25 +640,28 @@ private: void emitAnalysis(LoopAccessReport &Message); + /// \brief Collect memory access with loop invariant strides. + /// + /// Looks for accesses like "a[i * StrideA]" where "StrideA" is loop + /// invariant. + void collectStridedAccess(Value *LoadOrStoreInst); + + std::unique_ptr<PredicatedScalarEvolution> PSE; + /// We need to check that all of the pointers in this list are disjoint - /// at runtime. - RuntimePointerChecking PtrRtChecking; + /// at runtime. Using std::unique_ptr to make using move ctor simpler. + std::unique_ptr<RuntimePointerChecking> PtrRtChecking; /// \brief the Memory Dependence Checker which can determine the /// loop-independent and loop-carried dependences between memory accesses. - MemoryDepChecker DepChecker; + std::unique_ptr<MemoryDepChecker> DepChecker; Loop *TheLoop; - const DataLayout &DL; - const TargetLibraryInfo *TLI; - AliasAnalysis *AA; - DominatorTree *DT; - LoopInfo *LI; unsigned NumLoads; unsigned NumStores; - unsigned MaxSafeDepDistBytes; + uint64_t MaxSafeDepDistBytes; /// \brief Cache the result of analyzeLoop. bool CanVecMem; @@ -634,15 +673,23 @@ private: /// \brief The diagnostics report generated for the analysis. E.g. why we /// couldn't analyze the loop. Optional<LoopAccessReport> Report; + + /// \brief If an access has a symbolic strides, this maps the pointer value to + /// the stride symbol. + ValueToValueMap SymbolicStrides; + + /// \brief Set of symbolic strides values. + SmallPtrSet<Value *, 8> StrideSet; }; Value *stripIntegerCast(Value *V); -///\brief Return the SCEV corresponding to a pointer with the symbolic stride -/// replaced with constant one, assuming \p Preds is true. +/// \brief Return the SCEV corresponding to a pointer with the symbolic stride +/// replaced with constant one, assuming the SCEV predicate associated with +/// \p PSE is true. /// /// If necessary this method will version the stride of the pointer according -/// to \p PtrToStride and therefore add a new predicate to \p Preds. +/// to \p PtrToStride and therefore add further predicates to \p PSE. /// /// If \p OrigPtr is not null, use it to look up the stride value instead of \p /// Ptr. \p PtrToStride provides the mapping between the pointer value and its @@ -651,13 +698,24 @@ const SCEV *replaceSymbolicStrideSCEV(PredicatedScalarEvolution &PSE, const ValueToValueMap &PtrToStride, Value *Ptr, Value *OrigPtr = nullptr); -/// \brief Check the stride of the pointer and ensure that it does not wrap in -/// the address space, assuming \p Preds is true. +/// \brief If the pointer has a constant stride return it in units of its +/// element size. Otherwise return zero. +/// +/// Ensure that it does not wrap in the address space, assuming the predicate +/// associated with \p PSE is true. /// /// If necessary this method will version the stride of the pointer according -/// to \p PtrToStride and therefore add a new predicate to \p Preds. -int isStridedPtr(PredicatedScalarEvolution &PSE, Value *Ptr, const Loop *Lp, - const ValueToValueMap &StridesMap); +/// to \p PtrToStride and therefore add further predicates to \p PSE. +/// The \p Assume parameter indicates if we are allowed to make additional +/// run-time assumptions. +int64_t getPtrStride(PredicatedScalarEvolution &PSE, Value *Ptr, const Loop *Lp, + const ValueToValueMap &StridesMap = ValueToValueMap(), + bool Assume = false); + +/// \brief Returns true if the memory operations \p A and \p B are consecutive. +/// This is a simple API that does not depend on the analysis pass. +bool isConsecutiveAccess(Value *A, Value *B, const DataLayout &DL, + ScalarEvolution &SE, bool CheckType = true); /// \brief This analysis provides dependence information for the memory accesses /// of a loop. @@ -666,12 +724,12 @@ int isStridedPtr(PredicatedScalarEvolution &PSE, Value *Ptr, const Loop *Lp, /// querying the loop access info via LAA::getInfo. getInfo return a /// LoopAccessInfo object. See this class for the specifics of what information /// is provided. -class LoopAccessAnalysis : public FunctionPass { +class LoopAccessLegacyAnalysis : public FunctionPass { public: static char ID; - LoopAccessAnalysis() : FunctionPass(ID) { - initializeLoopAccessAnalysisPass(*PassRegistry::getPassRegistry()); + LoopAccessLegacyAnalysis() : FunctionPass(ID) { + initializeLoopAccessLegacyAnalysisPass(*PassRegistry::getPassRegistry()); } bool runOnFunction(Function &F) override; @@ -680,11 +738,8 @@ public: /// \brief Query the result of the loop access information for the loop \p L. /// - /// If the client speculates (and then issues run-time checks) for the values - /// of symbolic strides, \p Strides provides the mapping (see - /// replaceSymbolicStrideSCEV). If there is no cached result available run - /// the analysis. - const LoopAccessInfo &getInfo(Loop *L, const ValueToValueMap &Strides); + /// If there is no cached result available run the analysis. + const LoopAccessInfo &getInfo(Loop *L); void releaseMemory() override { // Invalidate the cache when the pass is freed. @@ -706,6 +761,34 @@ private: LoopInfo *LI; }; +/// \brief This analysis provides dependence information for the memory +/// accesses of a loop. +/// +/// It runs the analysis for a loop on demand. This can be initiated by +/// querying the loop access info via AM.getResult<LoopAccessAnalysis>. +/// getResult return a LoopAccessInfo object. See this class for the +/// specifics of what information is provided. +class LoopAccessAnalysis + : public AnalysisInfoMixin<LoopAccessAnalysis> { + friend AnalysisInfoMixin<LoopAccessAnalysis>; + static char PassID; + +public: + typedef LoopAccessInfo Result; + Result run(Loop &, AnalysisManager<Loop> &); + static StringRef name() { return "LoopAccessAnalysis"; } +}; + +/// \brief Printer pass for the \c LoopAccessInfo results. +class LoopAccessInfoPrinterPass + : public PassInfoMixin<LoopAccessInfoPrinterPass> { + raw_ostream &OS; + +public: + explicit LoopAccessInfoPrinterPass(raw_ostream &OS) : OS(OS) {} + PreservedAnalyses run(Loop &L, AnalysisManager<Loop> &AM); +}; + inline Instruction *MemoryDepChecker::Dependence::getSource( const LoopAccessInfo &LAI) const { return LAI.getDepChecker().getMemoryInstructions()[Source]; |