From 7063c7e0844bbd2e59ef639dd4b88907b2520aa9 Mon Sep 17 00:00:00 2001 From: Adam Nemet Date: Tue, 10 Mar 2015 17:40:37 +0000 Subject: [PATCH] [LoopAccesses 2/3] Allow querying of interesting dependences Gather an array of interesting dependences rather than just failing after the first unsafe one and regarding the loop unsafe. Loop Distribution needs to be able to collect all dependences in order to isolate the dependence cycles into their own partition. Since the dependence checking algorithm is quadratic in terms of accesses sharing the same underlying pointer, I am applying a cut-off threshold (MaxInterestingDependence). Exceeding that, the logic reverts back to the original approach deeming the loop unsafe upon encountering the first unsafe dependence. The main idea of the patch is to split isDepedent from directly answering the question whether the dep is safe for vectorization to return a dependence type which then gets mapped to old boolean result using Dependence::isSafeForVectorization. Tested that this was compile-time neutral on SpecINT2006 LTO bitcode inputs. No assembly change on the testsuite including external. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@231806 91177308-0d34-0410-b5e6-96231b3b80d8 --- include/llvm/Analysis/LoopAccessAnalysis.h | 82 +++++++++++++- lib/Analysis/LoopAccessAnalysis.cpp | 120 +++++++++++++++++---- 2 files changed, 178 insertions(+), 24 deletions(-) diff --git a/include/llvm/Analysis/LoopAccessAnalysis.h b/include/llvm/Analysis/LoopAccessAnalysis.h index 9d9b48d6f1a..a9517dd3d35 100644 --- a/include/llvm/Analysis/LoopAccessAnalysis.h +++ b/include/llvm/Analysis/LoopAccessAnalysis.h @@ -127,9 +127,52 @@ public: /// \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. + 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 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 Dependence types that don't prevent vectorization. + static bool isSafeForVectorization(DepType Type); + + /// \brief Dependence types that can be queried from the analysis. + static bool isInterestingDependence(DepType Type); + + /// \brief Lexically backward dependence types. + bool isPossiblyBackward() const; + }; + MemoryDepChecker(ScalarEvolution *Se, const Loop *L) : SE(Se), InnermostLoop(L), AccessIdx(0), - ShouldRetryWithRuntimeCheck(false) {} + ShouldRetryWithRuntimeCheck(false), SafeForVectorization(true), + RecordInterestingDependences(true) {} /// \brief Register the location (instructions are given increasing numbers) /// of a write access. @@ -155,6 +198,10 @@ public: 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; } @@ -163,6 +210,19 @@ public: /// vectorize the loop with a dynamic array access check. bool shouldRetryWithRuntimeCheck() { return ShouldRetryWithRuntimeCheck; } + /// \brief Returns the interesting dependences. If null is returned we + /// exceeded the MaxInterestingDependence threshold and this information is + /// not available. + const SmallVectorImpl *getInterestingDependences() const { + return RecordInterestingDependences ? &InterestingDependences : nullptr; + } + + /// \brief The vector of memory access instructions. The indices are used as + /// instruction identifiers in the Dependence class. + const SmallVectorImpl &getMemoryInstructions() const { + return InstMap; + } + private: ScalarEvolution *SE; const Loop *InnermostLoop; @@ -183,6 +243,20 @@ private: /// vectorize this loop with runtime checks. bool ShouldRetryWithRuntimeCheck; + /// \brief No memory dependence was encountered that would inhibit + /// vectorization. + bool SafeForVectorization; + + //// \brief True if InterestingDependences reflects the dependences in the + //// loop. If false we exceeded MaxInterestingDependence and + //// InterestingDependences is invalid. + bool RecordInterestingDependences; + + /// \brief Interesting memory dependences collected during the analysis as + /// defined by isInterestingDependence. Only valid if + /// RecordInterestingDependences is true. + SmallVector InterestingDependences; + /// \brief Check whether there is a plausible dependence between the two /// accesses. /// @@ -195,9 +269,9 @@ private: /// 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. - bool isDependent(const MemAccessInfo &A, unsigned AIdx, - const MemAccessInfo &B, unsigned BIdx, - const ValueToValueMap &Strides); + 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. diff --git a/lib/Analysis/LoopAccessAnalysis.cpp b/lib/Analysis/LoopAccessAnalysis.cpp index aafbc5eb1ab..a8f80545adc 100644 --- a/lib/Analysis/LoopAccessAnalysis.cpp +++ b/lib/Analysis/LoopAccessAnalysis.cpp @@ -49,6 +49,13 @@ unsigned VectorizerParams::RuntimeMemoryCheckThreshold; /// Maximum SIMD width. const unsigned VectorizerParams::MaxVectorWidth = 64; +/// \brief We collect interesting dependences up to this threshold. +static cl::opt MaxInterestingDependence( + "max-interesting-dependences", cl::Hidden, + cl::desc("Maximum number of interesting dependences collected by " + "loop-access analysis (default = 100)"), + cl::init(100)); + bool VectorizerParams::isInterleaveForced() { return ::VectorizationInterleave.getNumOccurrences() > 0; } @@ -360,7 +367,7 @@ void AccessAnalysis::processMemAccesses() { DEBUG(dbgs() << "LAA: Processing memory accesses...\n"); DEBUG(dbgs() << " AST: "; AST.dump()); - DEBUG(dbgs() << "LAA: Accesses:\n"); + DEBUG(dbgs() << "LAA: Accesses(" << Accesses.size() << "):\n"); DEBUG({ for (auto A : Accesses) dbgs() << "\t" << *A.getPointer() << " (" << @@ -546,6 +553,51 @@ static int isStridedPtr(ScalarEvolution *SE, Value *Ptr, const Loop *Lp, return Stride; } +bool MemoryDepChecker::Dependence::isSafeForVectorization(DepType Type) { + switch (Type) { + case NoDep: + case Forward: + case BackwardVectorizable: + return true; + + case Unknown: + case ForwardButPreventsForwarding: + case Backward: + case BackwardVectorizableButPreventsForwarding: + return false; + } +} + +bool MemoryDepChecker::Dependence::isInterestingDependence(DepType Type) { + switch (Type) { + case NoDep: + case Forward: + return false; + + case BackwardVectorizable: + case Unknown: + case ForwardButPreventsForwarding: + case Backward: + case BackwardVectorizableButPreventsForwarding: + return true; + } +} + +bool MemoryDepChecker::Dependence::isPossiblyBackward() const { + switch (Type) { + case NoDep: + case Forward: + case ForwardButPreventsForwarding: + return false; + + case Unknown: + case BackwardVectorizable: + case Backward: + case BackwardVectorizableButPreventsForwarding: + return true; + } +} + bool MemoryDepChecker::couldPreventStoreLoadForward(unsigned Distance, unsigned TypeByteSize) { // If loads occur at a distance that is not a multiple of a feasible vector @@ -585,9 +637,10 @@ bool MemoryDepChecker::couldPreventStoreLoadForward(unsigned Distance, return false; } -bool MemoryDepChecker::isDependent(const MemAccessInfo &A, unsigned AIdx, - const MemAccessInfo &B, unsigned BIdx, - const ValueToValueMap &Strides) { +MemoryDepChecker::Dependence::DepType +MemoryDepChecker::isDependent(const MemAccessInfo &A, unsigned AIdx, + const MemAccessInfo &B, unsigned BIdx, + const ValueToValueMap &Strides) { assert (AIdx < BIdx && "Must pass arguments in program order"); Value *APtr = A.getPointer(); @@ -597,12 +650,12 @@ bool MemoryDepChecker::isDependent(const MemAccessInfo &A, unsigned AIdx, // Two reads are independent. if (!AIsWrite && !BIsWrite) - return false; + return Dependence::NoDep; // We cannot check pointers in different address spaces. if (APtr->getType()->getPointerAddressSpace() != BPtr->getType()->getPointerAddressSpace()) - return true; + return Dependence::Unknown; const SCEV *AScev = replaceSymbolicStrideSCEV(SE, Strides, APtr); const SCEV *BScev = replaceSymbolicStrideSCEV(SE, Strides, BPtr); @@ -637,14 +690,14 @@ bool MemoryDepChecker::isDependent(const MemAccessInfo &A, unsigned AIdx, // the address space. if (!StrideAPtr || !StrideBPtr || StrideAPtr != StrideBPtr){ DEBUG(dbgs() << "Non-consecutive pointer access\n"); - return true; + return Dependence::Unknown; } const SCEVConstant *C = dyn_cast(Dist); if (!C) { DEBUG(dbgs() << "LAA: Dependence because of non-constant distance\n"); ShouldRetryWithRuntimeCheck = true; - return true; + return Dependence::Unknown; } Type *ATy = APtr->getType()->getPointerElementType(); @@ -659,19 +712,19 @@ bool MemoryDepChecker::isDependent(const MemAccessInfo &A, unsigned AIdx, if (IsTrueDataDependence && (couldPreventStoreLoadForward(Val.abs().getZExtValue(), TypeByteSize) || ATy != BTy)) - return true; + return Dependence::ForwardButPreventsForwarding; DEBUG(dbgs() << "LAA: Dependence is negative: NoDep\n"); - return false; + return Dependence::Forward; } // Write to the same location with the same size. // Could be improved to assert type sizes are the same (i32 == float, etc). if (Val == 0) { if (ATy == BTy) - return false; + return Dependence::NoDep; DEBUG(dbgs() << "LAA: Zero dependence difference but different types\n"); - return true; + return Dependence::Unknown; } assert(Val.isStrictlyPositive() && "Expect a positive value"); @@ -679,7 +732,7 @@ bool MemoryDepChecker::isDependent(const MemAccessInfo &A, unsigned AIdx, if (ATy != BTy) { DEBUG(dbgs() << "LAA: ReadWrite-Write positive dependency with different types\n"); - return true; + return Dependence::Unknown; } unsigned Distance = (unsigned) Val.getZExtValue(); @@ -698,7 +751,7 @@ bool MemoryDepChecker::isDependent(const MemAccessInfo &A, unsigned AIdx, Distance < TypeByteSize * ForcedUnroll * ForcedFactor) { DEBUG(dbgs() << "LAA: Failure because of Positive distance " << Val.getSExtValue() << '\n'); - return true; + return Dependence::Backward; } // Positive distance bigger than max vectorization factor. @@ -708,12 +761,12 @@ bool MemoryDepChecker::isDependent(const MemAccessInfo &A, unsigned AIdx, bool IsTrueDataDependence = (!AIsWrite && BIsWrite); if (IsTrueDataDependence && couldPreventStoreLoadForward(Distance, TypeByteSize)) - return true; + return Dependence::BackwardVectorizableButPreventsForwarding; DEBUG(dbgs() << "LAA: Positive distance " << Val.getSExtValue() << " with max VF = " << MaxSafeDepDistBytes / TypeByteSize << '\n'); - return false; + return Dependence::BackwardVectorizable; } bool MemoryDepChecker::areDepsSafe(DepCandidates &AccessSets, @@ -742,9 +795,33 @@ bool MemoryDepChecker::areDepsSafe(DepCandidates &AccessSets, I1E = Accesses[*AI].end(); I1 != I1E; ++I1) for (std::vector::iterator I2 = Accesses[*OI].begin(), I2E = Accesses[*OI].end(); I2 != I2E; ++I2) { - if (*I1 < *I2 && isDependent(*AI, *I1, *OI, *I2, Strides)) - return false; - if (*I2 < *I1 && isDependent(*OI, *I2, *AI, *I1, Strides)) + auto A = std::make_pair(&*AI, *I1); + auto B = std::make_pair(&*OI, *I2); + + assert(*I1 != *I2); + if (*I1 > *I2) + std::swap(A, B); + + Dependence::DepType Type = + isDependent(*A.first, A.second, *B.first, B.second, Strides); + SafeForVectorization &= Dependence::isSafeForVectorization(Type); + + // Gather dependences unless we accumulated MaxInterestingDependence + // dependences. In that case return as soon as we find the first + // unsafe dependence. This puts a limit on this quadratic + // algorithm. + if (RecordInterestingDependences) { + if (Dependence::isInterestingDependence(Type)) + InterestingDependences.push_back( + Dependence(A.second, B.second, Type)); + + if (InterestingDependences.size() >= MaxInterestingDependence) { + RecordInterestingDependences = false; + InterestingDependences.clear(); + DEBUG(dbgs() << "Too many dependences, stopped recording\n"); + } + } + if (!RecordInterestingDependences && !SafeForVectorization) return false; } ++OI; @@ -752,7 +829,10 @@ bool MemoryDepChecker::areDepsSafe(DepCandidates &AccessSets, AI++; } } - return true; + + DEBUG(dbgs() << "Total Interesting Dependences: " + << InterestingDependences.size() << "\n"); + return SafeForVectorization; } bool LoopAccessInfo::canAnalyzeLoop() { -- 2.34.1