From 718b0230335beb99518719ca3af81d3cdec9e864 Mon Sep 17 00:00:00 2001 From: Adam Nemet Date: Wed, 18 Feb 2015 03:43:24 +0000 Subject: [PATCH] [LoopAccesses] Create the analysis pass This is a function pass that runs the analysis on demand. The analysis can be initiated by querying the loop access info via LAA::getInfo. It either returns the cached info or runs the analysis. Symbolic stride information continues to reside outside of this analysis pass. We may move it inside later but it's not a priority for me right now. The idea is that Loop Distribution won't support run-time stride checking at least initially. This means that when querying the analysis, symbolic stride information can be provided optionally. Whether stride information is used can invalidate the cache entry and rerun the analysis. Note that if the loop does not have any symbolic stride, the entry should be preserved across Loop Distribution and LV. Since currently the only user of the pass is LV, I just check that the symbolic stride information didn't change when using a cached result. On the LV side, LoopVectorizationLegality requests the info object corresponding to the loop from the analysis pass. A large chunk of the diff is due to LAI becoming a pointer from a reference. A test will be added as part of the -analyze patch. Also tested that with AVX, we generate identical assembly output for the testsuite (including the external testsuite) before and after. This is part of the patchset that converts LoopAccessAnalysis into an actual analysis pass. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@229626 91177308-0d34-0410-b5e6-96231b3b80d8 --- include/llvm/Analysis/LoopAccessAnalysis.h | 59 ++++++++++++++++++--- include/llvm/InitializePasses.h | 1 + lib/Analysis/LoopAccessAnalysis.cpp | 61 ++++++++++++++++++++++ lib/Transforms/Scalar/Scalar.cpp | 1 + lib/Transforms/Vectorize/LoopVectorize.cpp | 42 +++++++++------ 5 files changed, 141 insertions(+), 23 deletions(-) diff --git a/include/llvm/Analysis/LoopAccessAnalysis.h b/include/llvm/Analysis/LoopAccessAnalysis.h index 3fbdb8bb851..615b052ed73 100644 --- a/include/llvm/Analysis/LoopAccessAnalysis.h +++ b/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 @@ public: 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. @@ -168,7 +164,15 @@ public: /// 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 @@ -206,6 +210,49 @@ const SCEV *replaceSymbolicStrideSCEV(ScalarEvolution *SE, 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 diff --git a/include/llvm/InitializePasses.h b/include/llvm/InitializePasses.h index 36393731486..3c69399aecf 100644 --- a/include/llvm/InitializePasses.h +++ b/include/llvm/InitializePasses.h @@ -281,6 +281,7 @@ void initializeVirtRegRewriterPass(PassRegistry&); void initializeInstSimplifierPass(PassRegistry&); void initializeUnpackMachineBundlesPass(PassRegistry&); void initializeFinalizeMachineBundlesPass(PassRegistry&); +void initializeLoopAccessAnalysisPass(PassRegistry&); void initializeLoopVectorizePass(PassRegistry&); void initializeSLPVectorizerPass(PassRegistry&); void initializeBBVectorizePass(PassRegistry&); diff --git a/lib/Analysis/LoopAccessAnalysis.cpp b/lib/Analysis/LoopAccessAnalysis.cpp index ca6e7a83e57..d3e82fee3c5 100644 --- a/lib/Analysis/LoopAccessAnalysis.cpp +++ b/lib/Analysis/LoopAccessAnalysis.cpp @@ -1196,3 +1196,64 @@ LoopAccessInfo::addRuntimeCheck(Instruction *Loc) { 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(); + } +} diff --git a/lib/Transforms/Scalar/Scalar.cpp b/lib/Transforms/Scalar/Scalar.cpp index f0728dccd24..c8a7a2c27b0 100644 --- a/lib/Transforms/Scalar/Scalar.cpp +++ b/lib/Transforms/Scalar/Scalar.cpp @@ -46,6 +46,7 @@ void llvm::initializeScalarOpts(PassRegistry &Registry) { initializeJumpThreadingPass(Registry); initializeLICMPass(Registry); initializeLoopDeletionPass(Registry); + initializeLoopAccessAnalysisPass(Registry); initializeLoopInstSimplifyPass(Registry); initializeLoopRotatePass(Registry); initializeLoopStrengthReducePass(Registry); diff --git a/lib/Transforms/Vectorize/LoopVectorize.cpp b/lib/Transforms/Vectorize/LoopVectorize.cpp index 1dc4041a300..090b3d89a26 100644 --- a/lib/Transforms/Vectorize/LoopVectorize.cpp +++ b/lib/Transforms/Vectorize/LoopVectorize.cpp @@ -552,12 +552,11 @@ public: 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 @@ public: /// 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 @@ public: 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 @@ private: 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 @@ private: /// 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 @@ struct LoopVectorize : public FunctionPass { TargetLibraryInfo *TLI; AliasAnalysis *AA; AssumptionCache *AC; + LoopAccessAnalysis *LAA; bool DisableUnrolling; bool AlwaysVectorize; @@ -1276,6 +1281,7 @@ struct LoopVectorize : public FunctionPass { 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 @@ struct LoopVectorize : public FunctionPass { } // 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 @@ struct LoopVectorize : public FunctionPass { AU.addRequired(); AU.addRequired(); AU.addRequired(); + AU.addRequired(); AU.addPreserved(); AU.addPreserved(); AU.addPreserved(); @@ -1662,7 +1669,7 @@ int LoopVectorizationLegality::isConsecutivePtr(Value *Ptr) { } bool LoopVectorizationLegality::isUniform(Value *V) { - return LAI.isUniform(V); + return LAI->isUniform(V); } InnerLoopVectorizer::VectorParts& @@ -3402,7 +3409,7 @@ bool LoopVectorizationLegality::canVectorize() { 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"); @@ -3827,11 +3834,11 @@ void LoopVectorizationLegality::collectLoopUniforms() { } 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, @@ -5006,6 +5013,7 @@ INITIALIZE_PASS_DEPENDENCY(ScalarEvolution) 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 { -- 2.34.1