[LAA] Merge memchecks for accesses separated by a constant offset

[oota-llvm.git] / include / llvm / Analysis / LoopAccessAnalysis.h

diff --git a/include/llvm/Analysis/LoopAccessAnalysis.h b/include/llvm/Analysis/LoopAccessAnalysis.h
index 7b635a8b49602bf83831af630ed10a370a1d4731..15bc100c329951f46b7264627fe8e97a4710eb35 100644 (file)
--- a/include/llvm/Analysis/LoopAccessAnalysis.h
+++ b/include/llvm/Analysis/LoopAccessAnalysis.h
@@ -311,7 +311,7 @@ public:
   /// This struct holds information about the memory runtime legality check that
   /// a group of pointers do not overlap.
   struct RuntimePointerCheck {
-    RuntimePointerCheck() : Need(false) {}
+    RuntimePointerCheck(ScalarEvolution *SE) : Need(false), SE(SE) {}
 
     /// Reset the state of the pointer runtime information.
     void reset() {
@@ -322,16 +322,55 @@ public:
       IsWritePtr.clear();
       DependencySetId.clear();
       AliasSetId.clear();
+      Exprs.clear();
     }
 
     /// Insert a pointer and calculate the start and end SCEVs.
-    void insert(ScalarEvolution *SE, Loop *Lp, Value *Ptr, bool WritePtr,
-                unsigned DepSetId, unsigned ASId,
-                const ValueToValueMap &Strides);
+    void insert(Loop *Lp, Value *Ptr, bool WritePtr, unsigned DepSetId,
+                unsigned ASId, const ValueToValueMap &Strides);
 
     /// \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, RuntimePointerCheck &RtCheck)
+          : RtCheck(RtCheck), High(RtCheck.Ends[Index]),
+            Low(RtCheck.Starts[Index]) {
+        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.
+      RuntimePointerCheck &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<unsigned, 2> Members;
+    };
+
+    /// \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 Decide whether we need to issue a run-time check for pointer at
     /// index \p I and \p J to prove their independence.
     ///
@@ -341,6 +380,12 @@ public:
     bool needsChecking(unsigned I, unsigned J,
                        const SmallVectorImpl<int> *PtrPartition) const;
 
+    /// \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 SmallVectorImpl<int> *PtrPartition) const;
+
     /// \brief Return true if any pointer requires run-time checking according
     /// to needsChecking.
     bool needsAnyChecking(const SmallVectorImpl<int> *PtrPartition) const;
@@ -372,6 +417,12 @@ public:
     SmallVector<unsigned, 2> DependencySetId;
     /// Holds the id of the disjoint alias set to which this pointer belongs.
     SmallVector<unsigned, 2> AliasSetId;
+    /// Holds at position i the SCEV for the access i
+    SmallVector<const SCEV *, 2> Exprs;
+    /// Holds a partitioning of pointers into "check groups".
+    SmallVector<CheckingPtrGroup, 2> CheckingGroups;
+    /// Holds a pointer to the ScalarEvolution analysis.
+    ScalarEvolution *SE;
   };
 
   LoopAccessInfo(Loop *L, ScalarEvolution *SE, const DataLayout &DL,