[LAA-memchecks 3/3] Introduce pointer partitions for memchecks

[anemet]

Summary

This is the final patch that actually introduces the new parameter of
partition mapping to RuntimePointerCheck::needsChecking.

Another API (LAI::getInstructionsForAccess) is also exposed that helps
to map pointers to instructions because ultimately we partition
instructions.

The WIP version of the Loop Distribution pass in D6930 has been adapted
to use all this. See for example, how
InstrPartitionContainer::computePartitionSetForPointers sets up the
partitions using the above API and then calls to LAI::addRuntimeCheck
with pointer partitions.

[hfinkel]

LGTM.

[anemet]

r231818

include/llvm/Analysis/LoopAccessAnalysis.h

public:
   }
 
   /// \brief The vector of memory access instructions.  The indices are used as
   /// instruction identifiers in the Dependence class.
   const SmallVectorImpl<Instruction *> &getMemoryInstructions() const {
     return InstMap;
   }
 
+  /// \brief Find the set of instructions that read or write via \p Ptr.
+  SmallVector<Instruction *, 4> getInstructionsForAccess(Value *Ptr,
+                                                         bool isWrite) const;
+
 private:
   ScalarEvolution *SE;
   const DataLayout *DL;
   const Loop *InnermostLoop;
 
   /// \brief Maps access locations (ptr, read/write) to program order.
   DenseMap<MemAccessInfo, std::vector<unsigned> > Accesses;
 
void insert(ScalarEvolution *SE, 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(); }
 
     /// \brief Decide whether we need to issue a run-time check for pointer at
     /// index \p I and \p J to prove their independence.
-    bool needsChecking(unsigned I, unsigned J) const;
+    ///
+    /// If \p PtrPartition is set, it contains the partition number for
+    /// pointers (-1 if the pointer belongs to multiple partitions).  In this
+    /// case omit checks between pointers belonging to the same partition.
+    bool needsChecking(unsigned I, unsigned J,
+                       const SmallVectorImpl<int> *PtrPartition) const;
 
     /// \brief Print the list run-time memory checks necessary.
-    void print(raw_ostream &OS, unsigned Depth = 0) const;
+    ///
+    /// If \p PtrPartition is set, it contains the partition number for
+    /// pointers (-1 if the pointer belongs to multiple partitions).  In this
+    /// case omit checks between pointers belonging to the same partition.
+    void print(raw_ostream &OS, unsigned Depth = 0,
+               const SmallVectorImpl<int> *PtrPartition = nullptr) const;
 
     /// This flag indicates if we need to add the runtime check.
     bool Need;
     /// Holds the pointers that we need to check.
     SmallVector<TrackingVH<Value>, 2> Pointers;
     /// Holds the pointer value at the beginning of the loop.
     SmallVector<const SCEV*, 2> Starts;
     /// Holds the pointer value at the end of the loop.
public:
   unsigned getNumStores() const { return NumStores; }
   unsigned getNumLoads() const { return NumLoads;}
 
   /// \brief Add code that checks at runtime if the accessed arrays overlap.
   ///
   /// Returns a pair of instructions where the first element is the first
   /// instruction generated in possibly a sequence of instructions and the
   /// second value is the final comparator value or NULL if no check is needed.
+  ///
+  /// If \p PtrPartition is set, it contains the partition number for pointers
+  /// (-1 if the pointer belongs to multiple partitions).  In this case omit
+  /// checks between pointers belonging to the same partition.
   std::pair<Instruction *, Instruction *>
-    addRuntimeCheck(Instruction *Loc) const;
+  addRuntimeCheck(Instruction *Loc,
+                  const SmallVectorImpl<int> *PtrPartition = nullptr) const;
 
   /// \brief The diagnostics report generated for the analysis.  E.g. why we
   /// couldn't analyze the loop.
   const Optional<LoopAccessReport> &getReport() const { return Report; }
 
   /// \brief the Memory Dependence Checker which can determine the
   /// loop-independent and loop-carried dependences between memory accesses.
   const MemoryDepChecker &getDepChecker() const { return DepChecker; }
 
+  /// \brief Return the list of instructions that use \p Ptr to read or write
+  /// memory.
+  SmallVector<Instruction *, 4> getInstructionsForAccess(Value *Ptr,
+                                                         bool isWrite) const {
+    return DepChecker.getInstructionsForAccess(Ptr, isWrite);
+  }
+
   /// \brief Print the information about the memory accesses in the loop.
   void print(raw_ostream &OS, unsigned Depth = 0) const;
 
   /// \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-dependent ABI.
   unsigned NumSymbolicStrides;
 

lib/Analysis/LoopAccessAnalysis.cpp

void LoopAccessInfo::RuntimePointerCheck::insert(
   Pointers.push_back(Ptr);
   Starts.push_back(AR->getStart());
   Ends.push_back(ScEnd);
   IsWritePtr.push_back(WritePtr);
   DependencySetId.push_back(DepSetId);
   AliasSetId.push_back(ASId);
 }
 
-bool LoopAccessInfo::RuntimePointerCheck::needsChecking(unsigned I,
-                                                        unsigned J) const {
+bool LoopAccessInfo::RuntimePointerCheck::needsChecking(
+    unsigned I, unsigned J, const SmallVectorImpl<int> *PtrPartition) const {
   // No need to check if two readonly pointers intersect.
   if (!IsWritePtr[I] && !IsWritePtr[J])
     return false;
 
   // Only need to check pointers between two different dependency sets.
   if (DependencySetId[I] == DependencySetId[J])
     return false;
 
   // Only need to check pointers in the same alias set.
   if (AliasSetId[I] != AliasSetId[J])
     return false;
 
+  // If PtrPartition is set omit checks between pointers of the same partition.
+  // Partition number -1 means that the pointer is used in multiple partitions.
+  // In this case we can't omit the check.
+  if (PtrPartition && (*PtrPartition)[I] != -1 &&
+      (*PtrPartition)[I] == (*PtrPartition)[J])
+    return false;
+
   return true;
 }
 
-void LoopAccessInfo::RuntimePointerCheck::print(raw_ostream &OS,
-                                                unsigned Depth) const {
+void LoopAccessInfo::RuntimePointerCheck::print(
+    raw_ostream &OS, unsigned Depth,
+    const SmallVectorImpl<int> *PtrPartition) const {
   unsigned NumPointers = Pointers.size();
   if (NumPointers == 0)
     return;
 
   OS.indent(Depth) << "Run-time memory checks:\n";
   unsigned N = 0;
   for (unsigned I = 0; I < NumPointers; ++I)
     for (unsigned J = I + 1; J < NumPointers; ++J)
-      if (needsChecking(I, J)) {
+      if (needsChecking(I, J, PtrPartition)) {
         OS.indent(Depth) << N++ << ":\n";
-        OS.indent(Depth + 2) << *Pointers[I] << "\n";
-        OS.indent(Depth + 2) << *Pointers[J] << "\n";
+        OS.indent(Depth + 2) << *Pointers[I];
+        if (PtrPartition)
+          OS << " (Partition: " << (*PtrPartition)[I] << ")";
+        OS << "\n";
+        OS.indent(Depth + 2) << *Pointers[J];
+        if (PtrPartition)
+          OS << " (Partition: " << (*PtrPartition)[J] << ")";
+        OS << "\n";
       }
 }
 
 namespace {
 /// \brief Analyses memory accesses in a loop.
 ///
 /// Checks whether run time pointer checks are needed and builds sets for data
 /// dependence checking.
while (!CheckDeps.empty()) {
     }
   }
 
   DEBUG(dbgs() << "Total Interesting Dependences: "
                << InterestingDependences.size() << "\n");
   return SafeForVectorization;
 }
 
+SmallVector<Instruction *, 4>
+MemoryDepChecker::getInstructionsForAccess(Value *Ptr, bool isWrite) const {
+  MemAccessInfo Access(Ptr, isWrite);
+  auto &IndexVector = Accesses.find(Access)->second;
+
+  SmallVector<Instruction *, 4> Insts;
+  std::transform(IndexVector.begin(), IndexVector.end(),
+                 std::back_inserter(Insts),
+                 [&](unsigned Idx) { return this->InstMap[Idx]; });
+  return Insts;
+}
+
 const char *MemoryDepChecker::Dependence::DepName[] = {
     "NoDep", "Unknown", "Forward", "ForwardButPreventsForwarding", "Backward",
     "BackwardVectorizable", "BackwardVectorizableButPreventsForwarding"};
 
 void MemoryDepChecker::Dependence::print(
     raw_ostream &OS, unsigned Depth,
     const SmallVectorImpl<Instruction *> &Instrs) const {
   OS.indent(Depth) << DepName[Type] << ":\n";
static Instruction *getFirstInst(Instruction *FirstInst, Value *V,
                                  Instruction *Loc) {
   if (FirstInst)
     return FirstInst;
   if (Instruction *I = dyn_cast<Instruction>(V))
     return I->getParent() == Loc->getParent() ? I : nullptr;
   return nullptr;
 }
 
-std::pair<Instruction *, Instruction *>
-LoopAccessInfo::addRuntimeCheck(Instruction *Loc) const {
+std::pair<Instruction *, Instruction *> LoopAccessInfo::addRuntimeCheck(
+    Instruction *Loc, const SmallVectorImpl<int> *PtrPartition) const {
   Instruction *tnullptr = nullptr;
   if (!PtrRtCheck.Need)
     return std::pair<Instruction *, Instruction *>(tnullptr, tnullptr);
 
   unsigned NumPointers = PtrRtCheck.Pointers.size();
   SmallVector<TrackingVH<Value> , 2> Starts;
   SmallVector<TrackingVH<Value> , 2> Ends;
 
for (unsigned i = 0; i < NumPointers; ++i) {
     }
   }
 
   IRBuilder<> ChkBuilder(Loc);
   // Our instructions might fold to a constant.
   Value *MemoryRuntimeCheck = nullptr;
   for (unsigned i = 0; i < NumPointers; ++i) {
     for (unsigned j = i+1; j < NumPointers; ++j) {
-      if (!PtrRtCheck.needsChecking(i, j))
+      if (!PtrRtCheck.needsChecking(i, j, PtrPartition))
         continue;
 
       unsigned AS0 = Starts[i]->getType()->getPointerAddressSpace();
       unsigned AS1 = Starts[j]->getType()->getPointerAddressSpace();
 
       assert((AS0 == Ends[j]->getType()->getPointerAddressSpace()) &&
              (AS1 == Ends[i]->getType()->getPointerAddressSpace()) &&
              "Trying to bounds check pointers with different address spaces");