Index: include/llvm/Analysis/LoopAccessAnalysis.h =================================================================== --- include/llvm/Analysis/LoopAccessAnalysis.h +++ include/llvm/Analysis/LoopAccessAnalysis.h @@ -15,665 +15,61 @@ #ifndef LLVM_ANALYSIS_LOOPACCESSANALYSIS_H #define LLVM_ANALYSIS_LOOPACCESSANALYSIS_H -#include "llvm/ADT/EquivalenceClasses.h" -#include "llvm/ADT/Optional.h" -#include "llvm/ADT/SetVector.h" +#include "llvm/ADT/DenseMap.h" #include "llvm/Analysis/AliasAnalysis.h" -#include "llvm/Analysis/AliasSetTracker.h" -#include "llvm/Analysis/ScalarEvolutionExpressions.h" -#include "llvm/IR/ValueHandle.h" +#include "llvm/IR/PassManager.h" +#include "llvm/InitializePasses.h" #include "llvm/Pass.h" -#include "llvm/Support/raw_ostream.h" namespace llvm { -class Value; -class DataLayout; -class ScalarEvolution; +class DominatorTree; class Loop; -class SCEV; -class SCEVUnionPredicate; class LoopAccessInfo; +class LoopInfo; +class ScalarEvolution; +class TargetLibraryInfo; +class Value; -/// Optimization analysis message produced during vectorization. Messages inform -/// the user why vectorization did not occur. -class LoopAccessReport { - std::string Message; - const Instruction *Instr; - -protected: - LoopAccessReport(const Twine &Message, const Instruction *I) - : Message(Message.str()), Instr(I) {} - -public: - LoopAccessReport(const Instruction *I = nullptr) : Instr(I) {} - - template LoopAccessReport &operator<<(const A &Value) { - raw_string_ostream Out(Message); - Out << Value; - return *this; - } - - const Instruction *getInstr() const { return Instr; } - - std::string &str() { return Message; } - const std::string &str() const { return Message; } - operator Twine() { return Message; } - - /// \brief Emit an analysis note for \p PassName with the debug location from - /// the instruction in \p Message if available. Otherwise use the location of - /// \p TheLoop. - static void emitAnalysis(const LoopAccessReport &Message, - const Function *TheFunction, - const Loop *TheLoop, - const char *PassName); -}; - -/// \brief Collection of parameters shared beetween the Loop Vectorizer and the -/// Loop Access Analysis. -struct VectorizerParams { - /// \brief Maximum SIMD width. - static const unsigned MaxVectorWidth; - - /// \brief VF as overridden by the user. - static unsigned VectorizationFactor; - /// \brief Interleave factor as overridden by the user. - static unsigned VectorizationInterleave; - /// \brief True if force-vector-interleave was specified by the user. - static bool isInterleaveForced(); - - /// \\brief When performing memory disambiguation checks at runtime do not - /// make more than this number of comparisons. - static unsigned RuntimeMemoryCheckThreshold; -}; +typedef DenseMap ValueToValueMap; -/// \brief Checks memory dependences among accesses to the same underlying -/// object to determine whether there vectorization is legal or not (and at -/// which vectorization factor). -/// -/// Note: This class will compute a conservative dependence for access to -/// different underlying pointers. Clients, such as the loop vectorizer, will -/// sometimes deal these potential dependencies by emitting runtime checks. -/// -/// We use the ScalarEvolution framework to symbolically evalutate access -/// functions pairs. Since we currently don't restructure the loop we can rely -/// on the program order of memory accesses to determine their safety. -/// At the moment we will only deem accesses as safe for: -/// * A negative constant distance assuming program order. -/// -/// Safe: tmp = a[i + 1]; OR a[i + 1] = x; -/// a[i] = tmp; y = a[i]; -/// -/// The latter case is safe because later checks guarantuee that there can't -/// be a cycle through a phi node (that is, we check that "x" and "y" is not -/// the same variable: a header phi can only be an induction or a reduction, a -/// reduction can't have a memory sink, an induction can't have a memory -/// source). This is important and must not be violated (or we have to -/// resort to checking for cycles through memory). -/// -/// * A positive constant distance assuming program order that is bigger -/// than the biggest memory access. -/// -/// tmp = a[i] OR b[i] = x -/// a[i+2] = tmp y = b[i+2]; -/// -/// Safe distance: 2 x sizeof(a[0]), and 2 x sizeof(b[0]), respectively. -/// -/// * Zero distances and all accesses have the same size. -/// -class MemoryDepChecker { +// Analysis manager base +class LoopAccessAMBase { public: - typedef PointerIntPair MemAccessInfo; - typedef SmallPtrSet MemAccessInfoSet; - /// \brief Set of potential dependent memory accesses. - typedef EquivalenceClasses DepCandidates; - - /// \brief Dependece between memory access instructions. - struct Dependence { - /// \brief The type of the dependence. - enum DepType { - // No dependence. - NoDep, - // We couldn't determine the direction or the distance. - Unknown, - // Lexically forward. - // - // FIXME: If we only have loop-independent forward dependences (e.g. a - // read and write of A[i]), LAA will locally deem the dependence "safe" - // without querying the MemoryDepChecker. Therefore we can miss - // enumerating loop-independent forward dependences in - // getDependences. Note that as soon as there are different - // indices used to access the same array, the MemoryDepChecker *is* - // queried and the dependence list is complete. - Forward, - // Forward, but if vectorized, is likely to prevent store-to-load - // forwarding. - ForwardButPreventsForwarding, - // Lexically backward. - Backward, - // Backward, but the distance allows a vectorization factor of - // MaxSafeDepDistBytes. - BackwardVectorizable, - // Same, but may prevent store-to-load forwarding. - BackwardVectorizableButPreventsForwarding - }; - - /// \brief String version of the types. - static const char *DepName[]; - - /// \brief Index of the source of the dependence in the InstMap vector. - unsigned Source; - /// \brief Index of the destination of the dependence in the InstMap vector. - unsigned Destination; - /// \brief The type of the dependence. - DepType Type; - - Dependence(unsigned Source, unsigned Destination, DepType Type) - : Source(Source), Destination(Destination), Type(Type) {} - - /// \brief Return the source instruction of the dependence. - Instruction *getSource(const LoopAccessInfo &LAI) const; - /// \brief Return the destination instruction of the dependence. - Instruction *getDestination(const LoopAccessInfo &LAI) const; - - /// \brief Dependence types that don't prevent vectorization. - static bool isSafeForVectorization(DepType Type); - - /// \brief Lexically forward dependence. - bool isForward() const; - /// \brief Lexically backward dependence. - bool isBackward() const; - - /// \brief May be a lexically backward dependence type (includes Unknown). - bool isPossiblyBackward() const; - - /// \brief Print the dependence. \p Instr is used to map the instruction - /// indices to instructions. - void print(raw_ostream &OS, unsigned Depth, - const SmallVectorImpl &Instrs) const; - }; - - MemoryDepChecker(PredicatedScalarEvolution &PSE, const Loop *L) - : PSE(PSE), InnermostLoop(L), AccessIdx(0), - ShouldRetryWithRuntimeCheck(false), SafeForVectorization(true), - RecordDependences(true) {} - - /// \brief Register the location (instructions are given increasing numbers) - /// of a write access. - void addAccess(StoreInst *SI) { - Value *Ptr = SI->getPointerOperand(); - Accesses[MemAccessInfo(Ptr, true)].push_back(AccessIdx); - InstMap.push_back(SI); - ++AccessIdx; - } - - /// \brief Register the location (instructions are given increasing numbers) - /// of a write access. - void addAccess(LoadInst *LI) { - Value *Ptr = LI->getPointerOperand(); - Accesses[MemAccessInfo(Ptr, false)].push_back(AccessIdx); - InstMap.push_back(LI); - ++AccessIdx; - } - - /// \brief Check whether the dependencies between the accesses are safe. - /// - /// Only checks sets with elements in \p CheckDeps. - bool areDepsSafe(DepCandidates &AccessSets, MemAccessInfoSet &CheckDeps, - const ValueToValueMap &Strides); - - /// \brief No memory dependence was encountered that would inhibit - /// vectorization. - bool isSafeForVectorization() const { return SafeForVectorization; } - - /// \brief The maximum number of bytes of a vector register we can vectorize - /// the accesses safely with. - unsigned getMaxSafeDepDistBytes() { return MaxSafeDepDistBytes; } - - /// \brief In same cases when the dependency check fails we can still - /// vectorize the loop with a dynamic array access check. - bool shouldRetryWithRuntimeCheck() { return ShouldRetryWithRuntimeCheck; } - - /// \brief Returns the memory dependences. If null is returned we exceeded - /// the MaxDependences threshold and this information is not - /// available. - const SmallVectorImpl *getDependences() const { - return RecordDependences ? &Dependences : nullptr; - } - - void clearDependences() { Dependences.clear(); } - - /// \brief The vector of memory access instructions. The indices are used as - /// instruction identifiers in the Dependence class. - const SmallVectorImpl &getMemoryInstructions() const { - return InstMap; - } - - /// \brief Generate a mapping between the memory instructions and their - /// indices according to program order. - DenseMap generateInstructionOrderMap() const { - DenseMap OrderMap; - - for (unsigned I = 0; I < InstMap.size(); ++I) - OrderMap[InstMap[I]] = I; - - return OrderMap; - } - - /// \brief Find the set of instructions that read or write via \p Ptr. - SmallVector getInstructionsForAccess(Value *Ptr, - bool isWrite) const; - -private: - /// A wrapper around ScalarEvolution, used to add runtime SCEV checks, and - /// applies dynamic knowledge to simplify SCEV expressions and convert them - /// to a more usable form. We need this in case assumptions about SCEV - /// expressions need to be made in order to avoid unknown dependences. For - /// example we might assume a unit stride for a pointer in order to prove - /// that a memory access is strided and doesn't wrap. - PredicatedScalarEvolution &PSE; - const Loop *InnermostLoop; - - /// \brief Maps access locations (ptr, read/write) to program order. - DenseMap > Accesses; - - /// \brief Memory access instructions in program order. - SmallVector InstMap; - - /// \brief The program order index to be used for the next instruction. - unsigned AccessIdx; - - // We can access this many bytes in parallel safely. - unsigned MaxSafeDepDistBytes; - - /// \brief If we see a non-constant dependence distance we can still try to - /// vectorize this loop with runtime checks. - bool ShouldRetryWithRuntimeCheck; - - /// \brief No memory dependence was encountered that would inhibit - /// vectorization. - bool SafeForVectorization; - - //// \brief True if Dependences reflects the dependences in the - //// loop. If false we exceeded MaxDependences and - //// Dependences is invalid. - bool RecordDependences; - - /// \brief Memory dependences collected during the analysis. Only valid if - /// RecordDependences is true. - SmallVector Dependences; - - /// \brief Check whether there is a plausible dependence between the two - /// accesses. - /// - /// Access \p A must happen before \p B in program order. The two indices - /// identify the index into the program order map. - /// - /// This function checks whether there is a plausible dependence (or the - /// absence of such can't be proved) between the two accesses. If there is a - /// plausible dependence but the dependence distance is bigger than one - /// element access it records this distance in \p MaxSafeDepDistBytes (if this - /// distance is smaller than any other distance encountered so far). - /// Otherwise, this function returns true signaling a possible dependence. - Dependence::DepType isDependent(const MemAccessInfo &A, unsigned AIdx, - const MemAccessInfo &B, unsigned BIdx, - const ValueToValueMap &Strides); - - /// \brief Check whether the data dependence could prevent store-load - /// forwarding. - /// - /// \return false if we shouldn't vectorize at all or avoid larger - /// vectorization factors by limiting MaxSafeDepDistBytes. - bool couldPreventStoreLoadForward(unsigned Distance, unsigned TypeByteSize); + virtual TargetLibraryInfo *getTLI() = 0; + virtual AliasAnalysis *getAAResults() = 0; + virtual DominatorTree *getDominatorTree() = 0; + virtual LoopInfo *getLoopInfo() = 0; + virtual ScalarEvolution *getSCEV() = 0; + virtual ~LoopAccessAMBase() {} }; -/// \brief Holds information about the memory runtime legality checks to verify -/// that a group of pointers do not overlap. -class RuntimePointerChecking { +class LoopAccessFuncInfo { public: - struct PointerInfo { - /// Holds the pointer value that we need to check. - TrackingVH PointerValue; - /// Holds the pointer value at the beginning of the loop. - const SCEV *Start; - /// Holds the pointer value at the end of the loop. - const SCEV *End; - /// Holds the information if this pointer is used for writing to memory. - bool IsWritePtr; - /// Holds the id of the set of pointers that could be dependent because of a - /// shared underlying object. - unsigned DependencySetId; - /// Holds the id of the disjoint alias set to which this pointer belongs. - unsigned AliasSetId; - /// SCEV for the access. - const SCEV *Expr; - - PointerInfo(Value *PointerValue, const SCEV *Start, const SCEV *End, - bool IsWritePtr, unsigned DependencySetId, unsigned AliasSetId, - const SCEV *Expr) - : PointerValue(PointerValue), Start(Start), End(End), - IsWritePtr(IsWritePtr), DependencySetId(DependencySetId), - AliasSetId(AliasSetId), Expr(Expr) {} - }; - - RuntimePointerChecking(ScalarEvolution *SE) : Need(false), SE(SE) {} - - /// Reset the state of the pointer runtime information. - void reset() { - Need = false; - Pointers.clear(); - Checks.clear(); - } - - /// Insert a pointer and calculate the start and end SCEVs. - /// 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 add new predicates to \p PSE. - void insert(Loop *Lp, Value *Ptr, bool WritePtr, unsigned DepSetId, - unsigned ASId, const ValueToValueMap &Strides, - PredicatedScalarEvolution &PSE); - - /// \brief No run-time memory checking is necessary. - bool empty() const { return Pointers.empty(); } - - /// A grouping of pointers. A single memcheck is required between - /// two groups. - struct CheckingPtrGroup { - /// \brief Create a new pointer checking group containing a single - /// pointer, with index \p Index in RtCheck. - CheckingPtrGroup(unsigned Index, RuntimePointerChecking &RtCheck) - : RtCheck(RtCheck), High(RtCheck.Pointers[Index].End), - Low(RtCheck.Pointers[Index].Start) { - Members.push_back(Index); - } - - /// \brief Tries to add the pointer recorded in RtCheck at index - /// \p Index to this pointer checking group. We can only add a pointer - /// to a checking group if we will still be able to get - /// the upper and lower bounds of the check. Returns true in case - /// of success, false otherwise. - bool addPointer(unsigned Index); - - /// Constitutes the context of this pointer checking group. For each - /// pointer that is a member of this group we will retain the index - /// at which it appears in RtCheck. - RuntimePointerChecking &RtCheck; - /// The SCEV expression which represents the upper bound of all the - /// pointers in this group. - const SCEV *High; - /// The SCEV expression which represents the lower bound of all the - /// pointers in this group. - const SCEV *Low; - /// Indices of all the pointers that constitute this grouping. - SmallVector Members; - }; - - /// \brief A memcheck which made up of a pair of grouped pointers. - /// - /// These *have* to be const for now, since checks are generated from - /// CheckingPtrGroups in LAI::addRuntimeChecks which is a const member - /// function. FIXME: once check-generation is moved inside this class (after - /// the PtrPartition hack is removed), we could drop const. - typedef std::pair - PointerCheck; - - /// \brief Generate the checks and store it. This also performs the grouping - /// of pointers to reduce the number of memchecks necessary. - void generateChecks(MemoryDepChecker::DepCandidates &DepCands, - bool UseDependencies); - - /// \brief Returns the checks that generateChecks created. - const SmallVector &getChecks() const { return Checks; } - - /// \brief Decide if we need to add a check between two groups of pointers, - /// according to needsChecking. - bool needsChecking(const CheckingPtrGroup &M, - const CheckingPtrGroup &N) const; - - /// \brief Returns the number of run-time checks required according to - /// needsChecking. - unsigned getNumberOfChecks() const { return Checks.size(); } - - /// \brief Print the list run-time memory checks necessary. - void print(raw_ostream &OS, unsigned Depth = 0) const; - - /// Print \p Checks. - void printChecks(raw_ostream &OS, const SmallVectorImpl &Checks, - unsigned Depth = 0) const; - - /// This flag indicates if we need to add the runtime check. - bool Need; - - /// Information about the pointers that may require checking. - SmallVector Pointers; - - /// Holds a partitioning of pointers into "check groups". - SmallVector CheckingGroups; - - /// \brief Check if pointers are in the same partition - /// - /// \p PtrToPartition contains the partition number for pointers (-1 if the - /// pointer belongs to multiple partitions). - static bool - arePointersInSamePartition(const SmallVectorImpl &PtrToPartition, - unsigned PtrIdx1, unsigned PtrIdx2); - - /// \brief Decide whether we need to issue a run-time check for pointer at - /// index \p I and \p J to prove their independence. - bool needsChecking(unsigned I, unsigned J) const; - - /// \brief Return PointerInfo for pointer at index \p PtrIdx. - const PointerInfo &getPointerInfo(unsigned PtrIdx) const { - return Pointers[PtrIdx]; - } - -private: - /// \brief Groups pointers such that a single memcheck is required - /// between two different groups. This will clear the CheckingGroups vector - /// and re-compute it. We will only group dependecies if \p UseDependencies - /// is true, otherwise we will create a separate group for each pointer. - void groupChecks(MemoryDepChecker::DepCandidates &DepCands, - bool UseDependencies); - - /// Generate the checks and return them. - SmallVector - generateChecks() const; - - /// Holds a pointer to the ScalarEvolution analysis. - ScalarEvolution *SE; - - /// \brief Set of run-time checks required to establish independence of - /// otherwise may-aliasing pointers in the loop. - SmallVector Checks; -}; - -/// \brief Drive the analysis of memory accesses in the loop -/// -/// This class is responsible for analyzing the memory accesses of a loop. It -/// collects the accesses and then its main helper the AccessAnalysis class -/// finds and categorizes the dependences in buildDependenceSets. -/// -/// For memory dependences that can be analyzed at compile time, it determines -/// whether the dependence is part of cycle inhibiting vectorization. This work -/// is delegated to the MemoryDepChecker class. -/// -/// For memory dependences that cannot be determined at compile time, it -/// generates run-time checks to prove independence. This is done by -/// AccessAnalysis::canCheckPtrAtRT and the checks are maintained by the -/// RuntimePointerCheck class. -/// -/// If pointers can wrap or can't be expressed as affine AddRec expressions by -/// ScalarEvolution, we will generate run-time checks by emitting a -/// SCEVUnionPredicate. -/// -/// Checks for both memory dependences and the SCEV predicates contained in the -/// 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); - - /// 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; - } - - /// \brief Number of memchecks required to prove independence of otherwise - /// may-alias pointers. - unsigned getNumRuntimePointerChecks() const { - return PtrRtChecking.getNumberOfChecks(); - } - - /// Return true if the block BB needs to be predicated in order for the loop - /// to be vectorized. - static bool blockNeedsPredication(BasicBlock *BB, Loop *TheLoop, - DominatorTree *DT); - - /// Returns true if the value V is uniform within the loop. - bool isUniform(Value *V) const; - - unsigned getMaxSafeDepDistBytes() const { return MaxSafeDepDistBytes; } - unsigned getNumStores() const { return NumStores; } - unsigned getNumLoads() const { return NumLoads;} - - /// \brief Add code that checks at runtime if the accessed arrays overlap. - /// - /// Returns a pair of instructions where the first element is the first - /// instruction generated in possibly a sequence of instructions and the - /// second value is the final comparator value or NULL if no check is needed. - std::pair - addRuntimeChecks(Instruction *Loc) const; - - /// \brief Generete the instructions for the checks in \p PointerChecks. + LoopAccessFuncInfo() : LoopAccessInfoMap(), AM(nullptr) {} + /// \brief Query the result of the loop access information for the loop \p L. /// - /// Returns a pair of instructions where the first element is the first - /// instruction generated in possibly a sequence of instructions and the - /// second value is the final comparator value or NULL if no check is needed. - std::pair - addRuntimeChecks(Instruction *Loc, - const SmallVectorImpl - &PointerChecks) const; - - /// \brief The diagnostics report generated for the analysis. E.g. why we - /// couldn't analyze the loop. - const Optional &getReport() const { return Report; } - - /// \brief the Memory Dependence Checker which can determine the - /// loop-independent and loop-carried dependences between memory accesses. - const MemoryDepChecker &getDepChecker() const { return DepChecker; } - - /// \brief Return the list of instructions that use \p Ptr to read or write - /// memory. - SmallVector getInstructionsForAccess(Value *Ptr, - bool isWrite) const { - return DepChecker.getInstructionsForAccess(Ptr, isWrite); - } + /// 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); - /// \brief Print the information about the memory accesses in the loop. - void print(raw_ostream &OS, unsigned Depth = 0) const; + void print(raw_ostream &OS, const Module *M = nullptr) 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. - bool hasStoreToLoopInvariantAddress() const { - return StoreToLoopInvariantAddress; + void releaseMemory() { + // Invalidate the cache when the pass is freed. + LoopAccessInfoMap.clear(); } - /// Used to add runtime SCEV checks. Simplifies SCEV expressions and converts - /// them to a more usable form. All SCEV expressions during the analysis - /// 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; + void setAM(LoopAccessAMBase *AM_) { AM.reset(AM_); } private: - /// \brief Analyze the loop. Substitute symbolic strides using Strides. - void analyzeLoop(const ValueToValueMap &Strides); - - /// \brief Check if the structure of the loop allows it to be analyzed by this - /// pass. - bool canAnalyzeLoop(); - - void emitAnalysis(LoopAccessReport &Message); - - /// We need to check that all of the pointers in this list are disjoint - /// at runtime. - RuntimePointerChecking PtrRtChecking; - - /// \brief the Memory Dependence Checker which can determine the - /// loop-independent and loop-carried dependences between memory accesses. - MemoryDepChecker DepChecker; - - Loop *TheLoop; - const DataLayout &DL; - const TargetLibraryInfo *TLI; - AliasAnalysis *AA; - DominatorTree *DT; - LoopInfo *LI; - - unsigned NumLoads; - unsigned NumStores; - - unsigned MaxSafeDepDistBytes; - - /// \brief Cache the result of analyzeLoop. - bool CanVecMem; - - /// \brief Indicator for storing to uniform addresses. - /// If a loop has write to a loop invariant address then it should be true. - bool StoreToLoopInvariantAddress; - - /// \brief The diagnostics report generated for the analysis. E.g. why we - /// couldn't analyze the loop. - Optional Report; + /// \brief The cache. + DenseMap> LoopAccessInfoMap; + std::unique_ptr AM; }; -Value *stripIntegerCast(Value *V); - -/// \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 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 -/// stride as collected by LoopVectorizationLegality::collectStridedAccess. -const SCEV *replaceSymbolicStrideSCEV(PredicatedScalarEvolution &PSE, - const ValueToValueMap &PtrToStride, - Value *Ptr, Value *OrigPtr = nullptr); - -/// \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 further predicates to \p PSE. -/// The \p Assume parameter indicates if we are allowed to make additional -/// run-time assumptions. -int 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. /// @@ -685,7 +81,7 @@ public: static char ID; - LoopAccessAnalysis() : FunctionPass(ID) { + LoopAccessAnalysis() : FunctionPass(ID), LAFI() { initializeLoopAccessAnalysisPass(*PassRegistry::getPassRegistry()); } @@ -693,44 +89,22 @@ void getAnalysisUsage(AnalysisUsage &AU) const override; - /// \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); + LoopAccessFuncInfo &getInfo() { return LAFI; } void releaseMemory() override { // Invalidate the cache when the pass is freed. - LoopAccessInfoMap.clear(); + LAFI.releaseMemory(); } /// \brief Print the result of the analysis when invoked with -analyze. - void print(raw_ostream &OS, const Module *M = nullptr) const override; + void print(raw_ostream &OS, const Module *M = nullptr) const override { + LAFI.print(OS, M); + } private: - /// \brief The cache. - DenseMap> LoopAccessInfoMap; - - // The used analysis passes. - ScalarEvolution *SE; - const TargetLibraryInfo *TLI; - AliasAnalysis *AA; - DominatorTree *DT; - LoopInfo *LI; + LoopAccessFuncInfo LAFI; }; -inline Instruction *MemoryDepChecker::Dependence::getSource( - const LoopAccessInfo &LAI) const { - return LAI.getDepChecker().getMemoryInstructions()[Source]; -} - -inline Instruction *MemoryDepChecker::Dependence::getDestination( - const LoopAccessInfo &LAI) const { - return LAI.getDepChecker().getMemoryInstructions()[Destination]; -} - } // End llvm namespace #endif Index: include/llvm/Analysis/LoopAccessInfo.h =================================================================== --- include/llvm/Analysis/LoopAccessInfo.h +++ include/llvm/Analysis/LoopAccessInfo.h @@ -12,8 +12,8 @@ // //===----------------------------------------------------------------------===// -#ifndef LLVM_ANALYSIS_LOOPACCESSANALYSIS_H -#define LLVM_ANALYSIS_LOOPACCESSANALYSIS_H +#ifndef LLVM_ANALYSIS_LOOPACCESSINFO_H +#define LLVM_ANALYSIS_LOOPACCESSINFO_H #include "llvm/ADT/EquivalenceClasses.h" #include "llvm/ADT/Optional.h" @@ -22,7 +22,6 @@ #include "llvm/Analysis/AliasSetTracker.h" #include "llvm/Analysis/ScalarEvolutionExpressions.h" #include "llvm/IR/ValueHandle.h" -#include "llvm/Pass.h" #include "llvm/Support/raw_ostream.h" namespace llvm { @@ -670,59 +669,12 @@ 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. +/// 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. -/// -/// It runs the analysis for a loop on demand. This can be initiated by -/// 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 { -public: - static char ID; - - LoopAccessAnalysis() : FunctionPass(ID) { - initializeLoopAccessAnalysisPass(*PassRegistry::getPassRegistry()); - } - - bool runOnFunction(Function &F) override; - - void getAnalysisUsage(AnalysisUsage &AU) const override; - - /// \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); - - void releaseMemory() override { - // Invalidate the cache when the pass is freed. - LoopAccessInfoMap.clear(); - } - - /// \brief Print the result of the analysis when invoked with -analyze. - void print(raw_ostream &OS, const Module *M = nullptr) const override; - -private: - /// \brief The cache. - DenseMap> LoopAccessInfoMap; - - // The used analysis passes. - ScalarEvolution *SE; - const TargetLibraryInfo *TLI; - AliasAnalysis *AA; - DominatorTree *DT; - LoopInfo *LI; -}; - -inline Instruction *MemoryDepChecker::Dependence::getSource( - const LoopAccessInfo &LAI) const { +inline Instruction * +MemoryDepChecker::Dependence::getSource(const LoopAccessInfo &LAI) const { return LAI.getDepChecker().getMemoryInstructions()[Source]; } Index: include/llvm/Transforms/Utils/LoopVersioning.h =================================================================== --- include/llvm/Transforms/Utils/LoopVersioning.h +++ include/llvm/Transforms/Utils/LoopVersioning.h @@ -17,9 +17,10 @@ #define LLVM_TRANSFORMS_UTILS_LOOPVERSIONING_H #include "llvm/Analysis/LoopAccessAnalysis.h" +#include "llvm/Analysis/LoopAccessInfo.h" #include "llvm/Analysis/ScalarEvolution.h" -#include "llvm/Transforms/Utils/ValueMapper.h" #include "llvm/Transforms/Utils/LoopUtils.h" +#include "llvm/Transforms/Utils/ValueMapper.h" namespace llvm { Index: lib/Analysis/LoopAccessAnalysis.cpp =================================================================== --- lib/Analysis/LoopAccessAnalysis.cpp +++ lib/Analysis/LoopAccessAnalysis.cpp @@ -13,16 +13,17 @@ //===----------------------------------------------------------------------===// #include "llvm/Analysis/LoopAccessAnalysis.h" +#include "llvm/Analysis/LoopAccessInfo.h" #include "llvm/Analysis/LoopInfo.h" #include "llvm/Analysis/ScalarEvolutionExpander.h" #include "llvm/Analysis/TargetLibraryInfo.h" #include "llvm/Analysis/ValueTracking.h" +#include "llvm/Analysis/VectorUtils.h" #include "llvm/IR/DiagnosticInfo.h" #include "llvm/IR/Dominators.h" #include "llvm/IR/IRBuilder.h" #include "llvm/Support/Debug.h" #include "llvm/Support/raw_ostream.h" -#include "llvm/Analysis/VectorUtils.h" using namespace llvm; #define DEBUG_TYPE "loop-accesses" @@ -1926,7 +1927,7 @@ } const LoopAccessInfo & -LoopAccessAnalysis::getInfo(Loop *L, const ValueToValueMap &Strides) { +LoopAccessFuncInfo::getInfo(Loop *L, const ValueToValueMap &Strides) { auto &LAI = LoopAccessInfoMap[L]; #ifndef NDEBUG @@ -1936,8 +1937,9 @@ if (!LAI) { const DataLayout &DL = L->getHeader()->getModule()->getDataLayout(); - LAI = - llvm::make_unique(L, SE, DL, TLI, AA, DT, LI, Strides); + LAI = llvm::make_unique( + L, AM->getSCEV(), DL, AM->getTLI(), AM->getAAResults(), + AM->getDominatorTree(), AM->getLoopInfo(), Strides); #ifndef NDEBUG LAI->NumSymbolicStrides = Strides.size(); #endif @@ -1945,27 +1947,46 @@ return *LAI.get(); } -void LoopAccessAnalysis::print(raw_ostream &OS, const Module *M) const { - LoopAccessAnalysis &LAA = *const_cast(this); +void LoopAccessFuncInfo::print(raw_ostream &OS, const Module *M) const { + LoopInfo *LI = AM->getLoopInfo(); ValueToValueMap NoSymbolicStrides; for (Loop *TopLevelLoop : *LI) for (Loop *L : depth_first(TopLevelLoop)) { OS.indent(2) << L->getHeader()->getName() << ":\n"; - auto &LAI = LAA.getInfo(L, NoSymbolicStrides); + auto &LAI = + const_cast(this)->getInfo(L, NoSymbolicStrides); LAI.print(OS, 4); } } -bool LoopAccessAnalysis::runOnFunction(Function &F) { - SE = &getAnalysis().getSE(); - auto *TLIP = getAnalysisIfAvailable(); - TLI = TLIP ? &TLIP->getTLI() : nullptr; - AA = &getAnalysis().getAAResults(); - DT = &getAnalysis().getDomTree(); - LI = &getAnalysis().getLoopInfo(); +class LoopAccessAMLegacy : public LoopAccessAMBase { +public: + LoopAccessAMLegacy(LoopAccessAnalysis &LAA) { + SE = &LAA.getAnalysis().getSE(); + auto *TLIP = LAA.getAnalysisIfAvailable(); + TLI = TLIP ? &TLIP->getTLI() : nullptr; + AA = &LAA.getAnalysis().getAAResults(); + DT = &LAA.getAnalysis().getDomTree(); + LI = &LAA.getAnalysis().getLoopInfo(); + } + TargetLibraryInfo *getTLI() override { return TLI; } + AliasAnalysis *getAAResults() override { return AA; } + DominatorTree *getDominatorTree() override { return DT; } + LoopInfo *getLoopInfo() override { return LI; } + ScalarEvolution *getSCEV() override { return SE; } +private: + ScalarEvolution *SE; + TargetLibraryInfo *TLI; + AliasAnalysis *AA; + DominatorTree *DT; + LoopInfo *LI; +}; + +bool LoopAccessAnalysis::runOnFunction(Function &F) { + LAFI.setAM(new LoopAccessAMLegacy(*this)); return false; } Index: lib/Transforms/Scalar/LoopDistribute.cpp =================================================================== --- lib/Transforms/Scalar/LoopDistribute.cpp +++ lib/Transforms/Scalar/LoopDistribute.cpp @@ -608,7 +608,7 @@ return fail("multiple exit blocks"); // LAA will check that we only have a single exiting block. - LAI = &LAA->getInfo(L, ValueToValueMap()); + LAI = &LAA->getInfo().getInfo(L, ValueToValueMap()); // Currently, we only distribute to isolate the part of the loop with // dependence cycles to enable partial vectorization. Index: lib/Transforms/Scalar/LoopIdiomRecognize.cpp =================================================================== --- lib/Transforms/Scalar/LoopIdiomRecognize.cpp +++ lib/Transforms/Scalar/LoopIdiomRecognize.cpp @@ -31,15 +31,15 @@ // //===----------------------------------------------------------------------===// -#include "llvm/Transforms/Scalar.h" #include "llvm/ADT/MapVector.h" #include "llvm/ADT/SetVector.h" #include "llvm/ADT/Statistic.h" #include "llvm/Analysis/AliasAnalysis.h" #include "llvm/Analysis/BasicAliasAnalysis.h" #include "llvm/Analysis/GlobalsModRef.h" -#include "llvm/Analysis/LoopPass.h" #include "llvm/Analysis/LoopAccessAnalysis.h" +#include "llvm/Analysis/LoopAccessInfo.h" +#include "llvm/Analysis/LoopPass.h" #include "llvm/Analysis/ScalarEvolutionAliasAnalysis.h" #include "llvm/Analysis/ScalarEvolutionExpander.h" #include "llvm/Analysis/ScalarEvolutionExpressions.h" @@ -53,6 +53,7 @@ #include "llvm/IR/Module.h" #include "llvm/Support/Debug.h" #include "llvm/Support/raw_ostream.h" +#include "llvm/Transforms/Scalar.h" #include "llvm/Transforms/Utils/BuildLibCalls.h" #include "llvm/Transforms/Utils/Local.h" #include "llvm/Transforms/Utils/LoopUtils.h" Index: lib/Transforms/Scalar/LoopLoadElimination.cpp =================================================================== --- lib/Transforms/Scalar/LoopLoadElimination.cpp +++ lib/Transforms/Scalar/LoopLoadElimination.cpp @@ -552,7 +552,7 @@ // Now walk the identified inner loops. bool Changed = false; for (Loop *L : Worklist) { - const LoopAccessInfo &LAI = LAA->getInfo(L, ValueToValueMap()); + const LoopAccessInfo &LAI = LAA->getInfo().getInfo(L, ValueToValueMap()); // The actual work is performed by LoadEliminationForLoop. LoadEliminationForLoop LEL(L, LI, LAI, DT); Changed |= LEL.processLoop(); Index: lib/Transforms/Scalar/LoopVersioningLICM.cpp =================================================================== --- lib/Transforms/Scalar/LoopVersioningLICM.cpp +++ lib/Transforms/Scalar/LoopVersioningLICM.cpp @@ -411,7 +411,7 @@ return false; } // Get LoopAccessInfo from current loop. - LAI = &LAA->getInfo(CurLoop, Strides); + LAI = &LAA->getInfo().getInfo(CurLoop, Strides); // Check LoopAccessInfo for need of runtime check. if (LAI->getRuntimePointerChecking()->getChecks().empty()) { DEBUG(dbgs() << " LAA: Runtime check not found !!\n"); Index: lib/Transforms/Utils/LoopVersioning.cpp =================================================================== --- lib/Transforms/Utils/LoopVersioning.cpp +++ lib/Transforms/Utils/LoopVersioning.cpp @@ -268,7 +268,7 @@ // Now walk the identified inner loops. bool Changed = false; for (Loop *L : Worklist) { - const LoopAccessInfo &LAI = LAA->getInfo(L, ValueToValueMap()); + const LoopAccessInfo &LAI = LAA->getInfo().getInfo(L, ValueToValueMap()); if (LAI.getNumRuntimePointerChecks() || !LAI.PSE.getUnionPredicate().isAlwaysTrue()) { LoopVersioning LVer(LAI, L, LI, DT, SE); Index: lib/Transforms/Vectorize/LoopVectorize.cpp =================================================================== --- lib/Transforms/Vectorize/LoopVectorize.cpp +++ lib/Transforms/Vectorize/LoopVectorize.cpp @@ -4875,7 +4875,7 @@ } bool LoopVectorizationLegality::canVectorizeMemory() { - LAI = &LAA->getInfo(TheLoop, Strides); + LAI = &LAA->getInfo().getInfo(TheLoop, Strides); auto &OptionalReport = LAI->getReport(); if (OptionalReport) emitAnalysis(VectorizationReport(*OptionalReport)); Index: lib/Transforms/Vectorize/SLPVectorizer.cpp =================================================================== --- lib/Transforms/Vectorize/SLPVectorizer.cpp +++ lib/Transforms/Vectorize/SLPVectorizer.cpp @@ -26,7 +26,7 @@ #include "llvm/Analysis/DemandedBits.h" #include "llvm/Analysis/GlobalsModRef.h" #include "llvm/Analysis/LoopAccessAnalysis.h" -#include "llvm/Analysis/LoopAccessAnalysis.h" +#include "llvm/Analysis/LoopAccessInfo.h" #include "llvm/Analysis/LoopInfo.h" #include "llvm/Analysis/ScalarEvolution.h" #include "llvm/Analysis/ScalarEvolutionExpressions.h"