[LAA] Dynamically allocate RuntimeCheckingPtrGroup (NFC).

[fhahn]

Summary

Currently parts in RuntimePointerChecking owns
RuntimeCheckingPtrGroup directly, which is reference from other
datastructures in RuntimePointerChecking. This prevents copying of
RuntimePointerChecking and couples things tightly.

This patch allows sharing, which will be used in a follow-on patch. It
use shared_ptr, but alternatively LAI could own the groups, but that
might couple LAI and RuntimePointerChecking unnecessarily.

[fhahn]

ping :)

[lebedev.ri]

Ignoring the question of direction, the code change itself seems ok to me.

llvm/include/llvm/Analysis/LoopAccessAnalysis.h

22–24

I don't recall seeing such separation between llvm and STD headers with newline elsewhere in llvm.

[fhahn]

rebase & ping

[fhahn]

ping

[Meinersbur]

I don't understand the motivation. Sharing RuntimeCheckingPtrGroup between multiple objects will increase coupling between them.

Summary:

Currently parts in RuntimePointerChecking owns RuntimeCheckingPtrGroup directly, which is reference from other datastructures in RuntimePointerChecking.

The grammar of this sentence seems off.

llvm/include/llvm/Analysis/LoopAccessAnalysis.h

21–23

llvm/lib/Analysis/LoopAccessAnalysis.cpp

66–68

llvm/include/llvm/Analysis/LoopAccessAnalysis.h

 
 #ifndef LLVM_ANALYSIS_LOOPACCESSANALYSIS_H
 #define LLVM_ANALYSIS_LOOPACCESSANALYSIS_H
 
 #include "llvm/ADT/EquivalenceClasses.h"
 #include "llvm/Analysis/LoopAnalysisManager.h"
 #include "llvm/Analysis/ScalarEvolutionExpressions.h"
 #include "llvm/IR/DiagnosticInfo.h"
 #include "llvm/Pass.h"
 
+#include <memory>
+
 namespace llvm {
 
 class AAResults;
 class DataLayout;
 class Loop;
 class LoopAccessInfo;
 class OptimizationRemarkEmitter;
 class raw_ostream;
public:
 
   /// This flag indicates if we need to add the runtime check.
   bool Need;
 
   /// Information about the pointers that may require checking.
   SmallVector<PointerInfo, 2> Pointers;
 
   /// Holds a partitioning of pointers into "check groups".
-  SmallVector<RuntimeCheckingPtrGroup, 2> CheckingGroups;
+  SmallVector<std::shared_ptr<RuntimeCheckingPtrGroup>, 2> CheckingGroups;
 
   /// Check if pointers are in the same partition
   ///
   /// \p PtrToPartition contains the partition number for pointers (-1 if the
   /// pointer belongs to multiple partitions).
   static bool
   arePointersInSamePartition(const SmallVectorImpl<int> &PtrToPartition,
                              unsigned PtrIdx1, unsigned PtrIdx2);

llvm/lib/Analysis/LoopAccessAnalysis.cpp

 #include "llvm/Support/ErrorHandling.h"
 #include "llvm/Support/raw_ostream.h"
 #include <algorithm>
 #include <cassert>
 #include <cstdint>
 #include <cstdlib>
 #include <iterator>
 #include <utility>
 #include <vector>
 
+#include <memory>
+
 using namespace llvm;
 
 #define DEBUG_TYPE "loop-accesses"
 
 static cl::opt<unsigned, true>
 VectorizationFactor("force-vector-width", cl::Hidden,
                     cl::desc("Sets the SIMD width. Zero is autoselect."),
                     cl::location(VectorizerParams::VectorizationFactor));

 }
 
 SmallVector<RuntimePointerCheck, 4>
 RuntimePointerChecking::generateChecks() const {
   SmallVector<RuntimePointerCheck, 4> Checks;
 
   for (unsigned I = 0; I < CheckingGroups.size(); ++I) {
     for (unsigned J = I + 1; J < CheckingGroups.size(); ++J) {
-      const RuntimeCheckingPtrGroup &CGI = CheckingGroups[I];
-      const RuntimeCheckingPtrGroup &CGJ = CheckingGroups[J];
+      const RuntimeCheckingPtrGroup &CGI = *CheckingGroups[I];
+      const RuntimeCheckingPtrGroup &CGJ = *CheckingGroups[J];
 
       if (needsChecking(CGI, CGJ))
         Checks.push_back(std::make_pair(&CGI, &CGJ));
     }
   }
   return Checks;
 }
 
void RuntimePointerChecking::groupChecks(
   // separate checking groups for all pointers.
 
   // If we don't have the dependency partitions, construct a new
   // checking pointer group for each pointer. This is also required
   // for correctness, because in this case we can have checking between
   // pointers to the same underlying object.
   if (!UseDependencies) {
     for (unsigned I = 0; I < Pointers.size(); ++I)
-      CheckingGroups.push_back(RuntimeCheckingPtrGroup(I, *this));
+      CheckingGroups.push_back(
+          std::make_shared<RuntimeCheckingPtrGroup>(I, *this));
     return;
   }
 
   unsigned TotalComparisons = 0;
 
   DenseMap<Value *, unsigned> PositionMap;
   for (unsigned Index = 0; Index < Pointers.size(); ++Index)
     PositionMap[Pointers[Index].PointerValue] = Index;
for (unsigned I = 0; I < Pointers.size(); ++I) {
     // We've seen this pointer before, and therefore already processed
     // its equivalence class.
     if (Seen.count(I))
       continue;
 
     MemoryDepChecker::MemAccessInfo Access(Pointers[I].PointerValue,
                                            Pointers[I].IsWritePtr);
 
-    SmallVector<RuntimeCheckingPtrGroup, 2> Groups;
+    SmallVector<std::shared_ptr<RuntimeCheckingPtrGroup>, 2> Groups;
     auto LeaderI = DepCands.findValue(DepCands.getLeaderValue(Access));
 
     // Because DepCands is constructed by visiting accesses in the order in
     // which they appear in alias sets (which is deterministic) and the
     // iteration order within an equivalence class member is only dependent on
     // the order in which unions and insertions are performed on the
     // equivalence class, the iteration order is deterministic.
     for (auto MI = DepCands.member_begin(LeaderI), ME = DepCands.member_end();
          MI != ME; ++MI) {
       auto PointerI = PositionMap.find(MI->getPointer());
       assert(PointerI != PositionMap.end() &&
              "pointer in equivalence class not found in PositionMap");
       unsigned Pointer = PointerI->second;
       bool Merged = false;
       // Mark this pointer as seen.
       Seen.insert(Pointer);
 
       // Go through all the existing sets and see if we can find one
       // which can include this pointer.
-      for (RuntimeCheckingPtrGroup &Group : Groups) {
+      for (auto &Group : Groups) {
         // Don't perform more than a certain amount of comparisons.
         // This should limit the cost of grouping the pointers to something
         // reasonable.  If we do end up hitting this threshold, the algorithm
         // will create separate groups for all remaining pointers.
         if (TotalComparisons > MemoryCheckMergeThreshold)
           break;
 
         TotalComparisons++;
 
-        if (Group.addPointer(Pointer)) {
+        if (Group->addPointer(Pointer)) {
           Merged = true;
           break;
         }
       }
 
       if (!Merged)
         // We couldn't add this pointer to any existing set or the threshold
         // for the number of comparisons has been reached. Create a new group
         // to hold the current pointer.
-        Groups.push_back(RuntimeCheckingPtrGroup(Pointer, *this));
+        Groups.push_back(
+            std::make_shared<RuntimeCheckingPtrGroup>(Pointer, *this));
     }
 
     // We've computed the grouped checks for this partition.
     // Save the results and continue with the next one.
     llvm::copy(Groups, std::back_inserter(CheckingGroups));
   }
 }
 

 
 void RuntimePointerChecking::print(raw_ostream &OS, unsigned Depth) const {
 
   OS.indent(Depth) << "Run-time memory checks:\n";
   printChecks(OS, Checks, Depth);
 
   OS.indent(Depth) << "Grouped accesses:\n";
   for (unsigned I = 0; I < CheckingGroups.size(); ++I) {
-    const auto &CG = CheckingGroups[I];
+    const auto &CG = *CheckingGroups[I];
 
     OS.indent(Depth + 2) << "Group " << &CG << ":\n";
     OS.indent(Depth + 4) << "(Low: " << *CG.Low << " High: " << *CG.High
                          << ")\n";
     for (unsigned J = 0; J < CG.Members.size(); ++J) {
       OS.indent(Depth + 6) << "Member: " << *Pointers[CG.Members[J]].Expr
                            << "\n";
     }

llvm/lib/Transforms/Utils/LoopVersioning.cpp

void LoopVersioning::prepareNoAliasMetadata() {
   //
   // While traversing through the checking groups in the loop, also create a
   // reverse map from pointers to the pointer checking group they were assigned
   // to.
   MDBuilder MDB(Context);
   MDNode *Domain = MDB.createAnonymousAliasScopeDomain("LVerDomain");
 
   for (const auto &Group : RtPtrChecking->CheckingGroups) {
-    GroupToScope[&Group] = MDB.createAnonymousAliasScope(Domain);
+    GroupToScope[&*Group] = MDB.createAnonymousAliasScope(Domain);
 
-    for (unsigned PtrIdx : Group.Members)
-      PtrToGroup[RtPtrChecking->getPointerInfo(PtrIdx).PointerValue] = &Group;
+    for (unsigned PtrIdx : Group->Members)
+      PtrToGroup[RtPtrChecking->getPointerInfo(PtrIdx).PointerValue] = &*Group;
   }
 
   // Go through the checks and for each pointer group, collect the scopes for
   // each non-aliasing pointer group.
   DenseMap<const RuntimeCheckingPtrGroup *, SmallVector<Metadata *, 4>>
       GroupToNonAliasingScopes;
 
   for (const auto &Check : AliasChecks)