From 32dd24633dbb1c9b807fe06f194799ebd7c1407b Mon Sep 17 00:00:00 2001 From: Adam Nemet Date: Fri, 7 Aug 2015 22:44:15 +0000 Subject: [PATCH] [LAA] Make the set of runtime checks part of the state of LAA, NFC This is the full set of checks that clients can further filter. IOW, it's client-agnostic. This makes LAA complete in the sense that it now provides the two main results of its analysis precomputed: 1. memory dependences via getDepChecker().getInsterestingDependences() 2. run-time checks via getRuntimePointerCheck().getChecks() However, as a consequence we now compute this information pro-actively. Thus if the client decides to skip the loop based on the dependences we've computed the checks unnecessarily. In order to see whether this was a significant overhead I checked compile time on SPEC2k6 LTO bitcode files. The change was in the noise. The checks are generated in canCheckPtrAtRT, at the same place where we used to call groupChecks to merge checks. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@244368 91177308-0d34-0410-b5e6-96231b3b80d8 --- include/llvm/Analysis/LoopAccessAnalysis.h | 41 ++++++++++++++-------- lib/Analysis/LoopAccessAnalysis.cpp | 13 +++++-- lib/Transforms/Scalar/LoopDistribute.cpp | 2 +- 3 files changed, 38 insertions(+), 18 deletions(-) diff --git a/include/llvm/Analysis/LoopAccessAnalysis.h b/include/llvm/Analysis/LoopAccessAnalysis.h index 46a83a1c928..2aa19ca682d 100644 --- a/include/llvm/Analysis/LoopAccessAnalysis.h +++ b/include/llvm/Analysis/LoopAccessAnalysis.h @@ -327,6 +327,7 @@ public: void reset() { Need = false; Pointers.clear(); + Checks.clear(); } /// Insert a pointer and calculate the start and end SCEVs. @@ -377,21 +378,13 @@ public: typedef std::pair PointerCheck; - /// \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); + /// \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); - /// Generate the checks and return them. - /// - /// \p PtrToPartition contains the partition number for pointers. If passed, - /// omit checks between pointers belonging to the same partition. Partition - /// number -1 means that the pointer is used in multiple partitions. In this - /// case we can't safely omit the check. - SmallVector - generateChecks(const SmallVectorImpl *PtrPartition = nullptr) const; + /// \brief \return the checks that generateChecks created. + const SmallVectorImpl &getChecks() const { return Checks; } /// \brief Decide if we need to add a check between two groups of pointers, /// according to needsChecking. @@ -436,8 +429,28 @@ public: const SmallVectorImpl *PtrPartition = nullptr) const; 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. + /// + /// \p PtrToPartition contains the partition number for pointers. If passed, + /// omit checks between pointers belonging to the same partition. Partition + /// number -1 means that the pointer is used in multiple partitions. In this + /// case we can't safely omit the check. + SmallVector + generateChecks(const SmallVectorImpl *PtrPartition = nullptr) 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 diff --git a/lib/Analysis/LoopAccessAnalysis.cpp b/lib/Analysis/LoopAccessAnalysis.cpp index c41ecdad9db..645b47758de 100644 --- a/lib/Analysis/LoopAccessAnalysis.cpp +++ b/lib/Analysis/LoopAccessAnalysis.cpp @@ -165,6 +165,13 @@ RuntimePointerChecking::generateChecks( return Checks; } +void RuntimePointerChecking::generateChecks( + MemoryDepChecker::DepCandidates &DepCands, bool UseDependencies) { + assert(Checks.empty() && "Checks is not empty"); + groupChecks(DepCands, UseDependencies); + Checks = generateChecks(); +} + bool RuntimePointerChecking::needsChecking( const CheckingPtrGroup &M, const CheckingPtrGroup &N, const SmallVectorImpl *PtrPartition) const { @@ -389,7 +396,7 @@ void RuntimePointerChecking::printChecks( void RuntimePointerChecking::print(raw_ostream &OS, unsigned Depth) const { OS.indent(Depth) << "Run-time memory checks:\n"; - printChecks(OS, generateChecks(), Depth); + printChecks(OS, Checks, Depth); OS.indent(Depth) << "Grouped accesses:\n"; for (unsigned I = 0; I < CheckingGroups.size(); ++I) { @@ -639,7 +646,7 @@ bool AccessAnalysis::canCheckPtrAtRT(RuntimePointerChecking &RtCheck, } if (NeedRTCheck && CanDoRT) - RtCheck.groupChecks(DepCands, IsDepCheckNeeded); + RtCheck.generateChecks(DepCands, IsDepCheckNeeded); DEBUG(dbgs() << "LAA: We need to do " << RtCheck.getNumberOfChecks(nullptr) << " pointer comparisons.\n"); @@ -1728,7 +1735,7 @@ std::pair LoopAccessInfo::addRuntimeCheck( if (!PtrRtChecking.Need) return std::make_pair(nullptr, nullptr); - return addRuntimeCheck(Loc, PtrRtChecking.generateChecks()); + return addRuntimeCheck(Loc, PtrRtChecking.getChecks()); } LoopAccessInfo::LoopAccessInfo(Loop *L, ScalarEvolution *SE, diff --git a/lib/Transforms/Scalar/LoopDistribute.cpp b/lib/Transforms/Scalar/LoopDistribute.cpp index b2a3e28c3f0..ffcfd8bad90 100644 --- a/lib/Transforms/Scalar/LoopDistribute.cpp +++ b/lib/Transforms/Scalar/LoopDistribute.cpp @@ -787,7 +787,7 @@ private: // the loop now. auto PtrToPartition = Partitions.computePartitionSetForPointers(LAI); const auto *RtPtrChecking = LAI.getRuntimePointerChecking(); - auto AllChecks = RtPtrChecking->generateChecks(); + const auto &AllChecks = RtPtrChecking->getChecks(); auto Checks = includeOnlyCrossPartitionChecks(AllChecks, PtrToPartition, RtPtrChecking); if (!Checks.empty()) { -- 2.34.1