Index: include/llvm/Analysis/LoopAccessAnalysis.h =================================================================== --- include/llvm/Analysis/LoopAccessAnalysis.h +++ include/llvm/Analysis/LoopAccessAnalysis.h @@ -22,6 +22,7 @@ #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 { @@ -132,12 +133,7 @@ LoopAccessInfo(Loop *L, ScalarEvolution *SE, const DataLayout *DL, const TargetLibraryInfo *TLI, AliasAnalysis *AA, - DominatorTree *DT) : - TheLoop(L), SE(SE), DL(DL), TLI(TLI), AA(AA), DT(DT), NumLoads(0), - NumStores(0), MaxSafeDepDistBytes(-1U), CanVecMem(false) {} - - /// \brief Analyze the loop. Replaces symbolic strides using Strides. - void analyzeLoop(ValueToValueMap &Strides); + DominatorTree *DT, ValueToValueMap &Strides); /// Return true we can analyze the memory accesses in the loop and there are /// no memory dependence cycles. @@ -169,7 +165,15 @@ /// couldn't analyze the loop. Optional &getReport() { return Report; } + /// \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-depedent ABI. + unsigned NumSymbolicStrides; + private: + /// \brief Analyze the loop. Substitute symbolic strides using Strides. + void analyzeLoop(ValueToValueMap &Strides); + void emitAnalysis(VectorizationReport &Message); /// We need to check that all of the pointers in this list are disjoint @@ -207,6 +211,49 @@ ValueToValueMap &PtrToStride, Value *Ptr, Value *OrigPtr = nullptr); +/// \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. + LoopAccessInfo &getInfo(Loop *L, ValueToValueMap &Strides); + + void releaseMemory() override { + // Invalidate the cache when the pass is freed. + LoopAccessInfoMap.clear(); + } + +private: + /// \brief The cache. + DenseMap> LoopAccessInfoMap; + + // The used analysis passes. + ScalarEvolution *SE; + const DataLayout *DL; + const TargetLibraryInfo *TLI; + AliasAnalysis *AA; + DominatorTree *DT; +}; } // End llvm namespace #endif Index: include/llvm/InitializePasses.h =================================================================== --- include/llvm/InitializePasses.h +++ include/llvm/InitializePasses.h @@ -280,6 +280,7 @@ void initializeInstSimplifierPass(PassRegistry&); void initializeUnpackMachineBundlesPass(PassRegistry&); void initializeFinalizeMachineBundlesPass(PassRegistry&); +void initializeLoopAccessAnalysisPass(PassRegistry&); void initializeLoopVectorizePass(PassRegistry&); void initializeSLPVectorizerPass(PassRegistry&); void initializeBBVectorizePass(PassRegistry&); Index: lib/Analysis/LoopAccessAnalysis.cpp =================================================================== --- lib/Analysis/LoopAccessAnalysis.cpp +++ lib/Analysis/LoopAccessAnalysis.cpp @@ -1200,3 +1200,64 @@ FirstInst = getFirstInst(FirstInst, Check, Loc); return std::make_pair(FirstInst, Check); } + +LoopAccessInfo::LoopAccessInfo(Loop *L, ScalarEvolution *SE, + const DataLayout *DL, + const TargetLibraryInfo *TLI, AliasAnalysis *AA, + DominatorTree *DT, ValueToValueMap &Strides) + : TheLoop(L), SE(SE), DL(DL), TLI(TLI), AA(AA), DT(DT), NumLoads(0), + NumStores(0), MaxSafeDepDistBytes(-1U), CanVecMem(false) { + analyzeLoop(Strides); +} + +LoopAccessInfo &LoopAccessAnalysis::getInfo(Loop *L, ValueToValueMap &Strides) { + auto &LAI = LoopAccessInfoMap[L]; + +#ifndef NDEBUG + assert((!LAI || LAI->NumSymbolicStrides == Strides.size()) && + "Symbolic strides changed for loop"); +#endif + + if (!LAI) { + LAI = make_unique(L, SE, DL, TLI, AA, DT, Strides); +#ifndef NDEBUG + LAI->NumSymbolicStrides = Strides.size(); +#endif + } + return *LAI.get(); +} + +bool LoopAccessAnalysis::runOnFunction(Function &F) { + SE = &getAnalysis(); + DL = F.getParent()->getDataLayout(); + auto *TLIP = getAnalysisIfAvailable(); + TLI = TLIP ? &TLIP->getTLI() : nullptr; + AA = &getAnalysis(); + DT = &getAnalysis().getDomTree(); + + return false; +} + +void LoopAccessAnalysis::getAnalysisUsage(AnalysisUsage &AU) const { + AU.addRequired(); + AU.addRequired(); + AU.addRequired(); + + AU.setPreservesAll(); +} + +char LoopAccessAnalysis::ID = 0; +static const char laa_name[] = "Loop Access Analysis"; +#define LAA_NAME "loop-accesses" + +INITIALIZE_PASS_BEGIN(LoopAccessAnalysis, LAA_NAME, laa_name, false, true) +INITIALIZE_AG_DEPENDENCY(AliasAnalysis) +INITIALIZE_PASS_DEPENDENCY(ScalarEvolution) +INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass) +INITIALIZE_PASS_END(LoopAccessAnalysis, LAA_NAME, laa_name, false, true) + +namespace llvm { + Pass *createLAAPass() { + return new LoopAccessAnalysis(); + } +} Index: lib/Transforms/Scalar/Scalar.cpp =================================================================== --- lib/Transforms/Scalar/Scalar.cpp +++ lib/Transforms/Scalar/Scalar.cpp @@ -45,6 +45,7 @@ initializeJumpThreadingPass(Registry); initializeLICMPass(Registry); initializeLoopDeletionPass(Registry); + initializeLoopAccessAnalysisPass(Registry); initializeLoopInstSimplifyPass(Registry); initializeLoopRotatePass(Registry); initializeLoopStrengthReducePass(Registry); Index: lib/Transforms/Vectorize/LoopVectorize.cpp =================================================================== --- lib/Transforms/Vectorize/LoopVectorize.cpp +++ lib/Transforms/Vectorize/LoopVectorize.cpp @@ -552,12 +552,11 @@ LoopVectorizationLegality(Loop *L, ScalarEvolution *SE, const DataLayout *DL, DominatorTree *DT, TargetLibraryInfo *TLI, AliasAnalysis *AA, Function *F, - const TargetTransformInfo *TTI) + const TargetTransformInfo *TTI, + LoopAccessAnalysis *LAA) : NumPredStores(0), TheLoop(L), SE(SE), DL(DL), - TLI(TLI), TheFunction(F), TTI(TTI), DT(DT), Induction(nullptr), - WidestIndTy(nullptr), - LAI(L, SE, DL, TLI, AA, DT), - HasFunNoNaNAttr(false) {} + TLI(TLI), TheFunction(F), TTI(TTI), DT(DT), LAA(LAA), LAI(nullptr), + Induction(nullptr), WidestIndTy(nullptr), HasFunNoNaNAttr(false) {} /// This enum represents the kinds of reductions that we support. enum ReductionKind { @@ -743,18 +742,18 @@ /// Returns the information that we collected about runtime memory check. LoopAccessInfo::RuntimePointerCheck *getRuntimePointerCheck() { - return LAI.getRuntimePointerCheck(); + return LAI->getRuntimePointerCheck(); } LoopAccessInfo *getLAI() { - return &LAI; + return LAI; } /// This function returns the identity element (or neutral element) for /// the operation K. static Constant *getReductionIdentity(ReductionKind K, Type *Tp); - unsigned getMaxSafeDepDistBytes() { return LAI.getMaxSafeDepDistBytes(); } + unsigned getMaxSafeDepDistBytes() { return LAI->getMaxSafeDepDistBytes(); } bool hasStride(Value *V) { return StrideSet.count(V); } bool mustCheckStrides() { return !StrideSet.empty(); } @@ -779,10 +778,10 @@ return (MaskedOp.count(I) != 0); } unsigned getNumStores() const { - return LAI.getNumStores(); + return LAI->getNumStores(); } unsigned getNumLoads() const { - return LAI.getNumLoads(); + return LAI->getNumLoads(); } unsigned getNumPredStores() const { return NumPredStores; @@ -857,6 +856,11 @@ const TargetTransformInfo *TTI; /// Dominator Tree. DominatorTree *DT; + // LoopAccess analysis. + LoopAccessAnalysis *LAA; + // And the loop-accesses info corresponding to this loop. This pointer is + // null until canVectorizeMemory sets it up. + LoopAccessInfo *LAI; // --- vectorization state --- // @@ -878,7 +882,7 @@ /// This set holds the variables which are known to be uniform after /// vectorization. SmallPtrSet Uniforms; - LoopAccessInfo LAI; + /// Can we assume the absence of NaNs. bool HasFunNoNaNAttr; @@ -1259,6 +1263,7 @@ TargetLibraryInfo *TLI; AliasAnalysis *AA; AssumptionCache *AC; + LoopAccessAnalysis *LAA; bool DisableUnrolling; bool AlwaysVectorize; @@ -1276,6 +1281,7 @@ TLI = TLIP ? &TLIP->getTLI() : nullptr; AA = &getAnalysis(); AC = &getAnalysis().getAssumptionCache(F); + LAA = &getAnalysis(); // Compute some weights outside of the loop over the loops. Compute this // using a BranchProbability to re-use its scaling math. @@ -1386,7 +1392,7 @@ } // Check if it is legal to vectorize the loop. - LoopVectorizationLegality LVL(L, SE, DL, DT, TLI, AA, F, TTI); + LoopVectorizationLegality LVL(L, SE, DL, DT, TLI, AA, F, TTI, LAA); if (!LVL.canVectorize()) { DEBUG(dbgs() << "LV: Not vectorizing: Cannot prove legality.\n"); emitMissedWarning(F, L, Hints); @@ -1491,6 +1497,7 @@ AU.addRequired(); AU.addRequired(); AU.addRequired(); + AU.addRequired(); AU.addPreserved(); AU.addPreserved(); AU.addPreserved(); @@ -1662,7 +1669,7 @@ } bool LoopVectorizationLegality::isUniform(Value *V) { - return LAI.isUniform(V); + return LAI->isUniform(V); } InnerLoopVectorizer::VectorParts& @@ -3402,7 +3409,7 @@ collectLoopUniforms(); DEBUG(dbgs() << "LV: We can vectorize this loop" << - (LAI.getRuntimePointerCheck()->Need ? " (with a runtime bound check)" : + (LAI->getRuntimePointerCheck()->Need ? " (with a runtime bound check)" : "") <<"!\n"); @@ -3828,11 +3835,11 @@ } bool LoopVectorizationLegality::canVectorizeMemory() { - LAI.analyzeLoop(Strides); - auto &OptionalReport = LAI.getReport(); + LAI = &LAA->getInfo(TheLoop, Strides); + auto &OptionalReport = LAI->getReport(); if (OptionalReport) emitAnalysis(*OptionalReport); - return LAI.canVectorizeMemory(); + return LAI->canVectorizeMemory(); } static bool hasMultipleUsesOf(Instruction *I, @@ -5003,6 +5010,7 @@ INITIALIZE_PASS_DEPENDENCY(LCSSA) INITIALIZE_PASS_DEPENDENCY(LoopInfoWrapperPass) INITIALIZE_PASS_DEPENDENCY(LoopSimplify) +INITIALIZE_PASS_DEPENDENCY(LoopAccessAnalysis) INITIALIZE_PASS_END(LoopVectorize, LV_NAME, lv_name, false, false) namespace llvm {