[LAA] Move CheckingPtrGroup/PointerCheck outside class (NFC).

[fhahn]

Summary

This allows forward declarations of PointerCheck, which in turn reduce
the number of times LoopAccessAnalysis needs to be included.

Ultimately this helps with moving runtime check generation to
Transforms/Utils/LoopUtils.h, without having to include it there.

[fhahn]

ping

[Ayal]

Given that CheckingPtrGroup and PointerCheck are taken out of RuntimePointerChecking to become externally visible, would it make sense to rename them RuntimeCheckingPtrGroup and RuntimePointerCheck?

llvm/include/llvm/Analysis/LoopAccessAnalysis.h

416

The const's are not dropped, but the comment is?

[fhahn]

In D78458#2004257, @Ayal wrote:

Given that CheckingPtrGroup and PointerCheck are taken out of RuntimePointerChecking to become externally visible, would it make sense to rename them RuntimeCheckingPtrGroup and RuntimePointerCheck?

Thanks Ayal, I renamed it.

llvm/include/llvm/Analysis/LoopAccessAnalysis.h

416

Unfortunately I am not really sure if there's a benefit from dropping the const, unless there is a need to have them non-const.

I did not spot any const_casts or similar related to that pair and thought we can just drop the FIXME all together. If there's a benefit for them to not be const I am missing, I'll drop it.

[Ayal]

llvm/include/llvm/Analysis/LoopAccessAnalysis.h

330

Ah, suggested this struct be renamed RuntimeCheckingPtrGroup instead of RuntimePointerChecking::CheckingPtrGroup, rather than RuntimePointerCheck,

358

and this typedef be renamed RuntimePointerCheck instead of RuntimePointerChecking::PointerCheck, rather than only PointerCheck.

416

Not sure either; the "since checks are generated from CheckingPtrGroups in LAI::addRuntimeChecks which is a const member function" - still holds. This traces back to D11205; @anemet - do you recall this FIXME and/or agree it is now obsolete?

[fhahn]

Update renaming, PointerCheck -> RuntimePointerCheck, CheckingPtrGroup -> RuntimeCheckingPtrGroup.

[fhahn]

llvm/include/llvm/Analysis/LoopAccessAnalysis.h

358

Ah, I didn't read your comment carefully enough it seems, sorry about that. Updated the names as suggested.

[Ayal]

llvm/lib/Transforms/Utils/LoopVersioning.cpp

48

Unrelated, while we're here: better use SmallVectorImpl or ArrayRef instead of returning, constructing and moving SmallVector<4>'s?

[anemet]

llvm/include/llvm/Analysis/LoopAccessAnalysis.h

416

Yes, that looks like a stale comment now, please kill it.

[fhahn]

Thanks Ayal & Adam!

llvm/lib/Transforms/Utils/LoopVersioning.cpp

48

Will do in a follow up, thanks!

[fhahn]

llvm/lib/Transforms/Utils/LoopVersioning.cpp

48

pushed fix in 19ab53f1e2c3

llvm/include/llvm/Analysis/LoopAccessAnalysis.h

private:
   bool couldPreventStoreLoadForward(uint64_t Distance, uint64_t TypeByteSize);
 
   /// Updates the current safety status with \p S. We can go from Safe to
   /// either PossiblySafeWithRtChecks or Unsafe and from
   /// PossiblySafeWithRtChecks to Unsafe.
   void mergeInStatus(VectorizationSafetyStatus S);
 };
 
+class RuntimePointerChecking;
+/// A grouping of pointers. A single memcheck is required between
+/// two groups.
+struct RuntimeCheckingPtrGroup {
+  /// Create a new pointer checking group containing a single
+  /// pointer, with index \p Index in RtCheck.
+  RuntimeCheckingPtrGroup(unsigned Index, RuntimePointerChecking &RtCheck);
+
+  /// 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.
+  RuntimePointerChecking &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;
+};
+
+/// A memcheck which made up of a pair of grouped pointers.
+typedef std::pair<const RuntimeCheckingPtrGroup *,
+                  const RuntimeCheckingPtrGroup *>
+    RuntimePointerCheck;
+
 /// Holds information about the memory runtime legality checks to verify
 /// that a group of pointers do not overlap.
 class RuntimePointerChecking {
+  friend struct RuntimeCheckingPtrGroup;
+
 public:
   struct PointerInfo {
     /// Holds the pointer value that we need to check.
     TrackingVH<Value> PointerValue;
     /// Holds the smallest byte address accessed by the pointer throughout all
     /// iterations of the loop.
     const SCEV *Start;
     /// Holds the largest byte address accessed by the pointer throughout all
public:
   /// and add new predicates to \p PSE.
   void insert(Loop *Lp, Value *Ptr, bool WritePtr, unsigned DepSetId,
               unsigned ASId, const ValueToValueMap &Strides,
               PredicatedScalarEvolution &PSE);
 
   /// 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 {
-    /// Create a new pointer checking group containing a single
-    /// pointer, with index \p Index in RtCheck.
-    CheckingPtrGroup(unsigned Index, RuntimePointerChecking &RtCheck)
-        : RtCheck(RtCheck), High(RtCheck.Pointers[Index].End),
-          Low(RtCheck.Pointers[Index].Start) {
-      Members.push_back(Index);
-    }
-
-    /// 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.
-    RuntimePointerChecking &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;
-  };
-
-  /// A memcheck which made up of a pair of grouped pointers.
-  ///
-  /// These *have* to be const for now, since checks are generated from
-  /// CheckingPtrGroups in LAI::addRuntimeChecks which is a const member
-  /// function.  FIXME: once check-generation is moved inside this class (after
-  /// the PtrPartition hack is removed), we could drop const.
-  typedef std::pair<const CheckingPtrGroup *, const CheckingPtrGroup *>
-      PointerCheck;
-
   /// 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);
 
   /// Returns the checks that generateChecks created.
-  const SmallVector<PointerCheck, 4> &getChecks() const { return Checks; }
+  const SmallVector<RuntimePointerCheck, 4> &getChecks() const {
+    return Checks;
+  }
 
   /// 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;
+  bool needsChecking(const RuntimeCheckingPtrGroup &M,
+                     const RuntimeCheckingPtrGroup &N) const;
 
   /// Returns the number of run-time checks required according to
   /// needsChecking.
   unsigned getNumberOfChecks() const { return Checks.size(); }
 
   /// Print the list run-time memory checks necessary.
   void print(raw_ostream &OS, unsigned Depth = 0) const;
 
   /// Print \p Checks.
-  void printChecks(raw_ostream &OS, const SmallVectorImpl<PointerCheck> &Checks,
+  void printChecks(raw_ostream &OS,
+                   const SmallVectorImpl<RuntimePointerCheck> &Checks,
                    unsigned Depth = 0) const;
 
   /// 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<CheckingPtrGroup, 2> CheckingGroups;
+  SmallVector<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);
private:
   /// 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.
-  SmallVector<PointerCheck, 4>
-  generateChecks() const;
+  SmallVector<RuntimePointerCheck, 4> generateChecks() const;
 
   /// Holds a pointer to the ScalarEvolution analysis.
   ScalarEvolution *SE;
 
   /// Set of run-time checks required to establish independence of
   /// otherwise may-aliasing pointers in the loop.
-  SmallVector<PointerCheck, 4> Checks;
+  SmallVector<RuntimePointerCheck, 4> Checks;
 };
 
 /// Drive the analysis of memory accesses in the loop
 ///
 /// This class is responsible for analyzing the memory accesses of a loop.  It
 /// collects the accesses and then its main helper the AccessAnalysis class
 /// finds and categorizes the dependences in buildDependenceSets.
 ///
public:
   std::pair<Instruction *, Instruction *>
   addRuntimeChecks(Instruction *Loc) const;
 
   /// Generete the instructions for the checks in \p PointerChecks.
   ///
   /// 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.
-  std::pair<Instruction *, Instruction *>
-  addRuntimeChecks(Instruction *Loc,
-                   const SmallVectorImpl<RuntimePointerChecking::PointerCheck>
-                       &PointerChecks) const;
+  std::pair<Instruction *, Instruction *> addRuntimeChecks(
+      Instruction *Loc,
+      const SmallVectorImpl<RuntimePointerCheck> &PointerChecks) const;
 
   /// The diagnostics report generated for the analysis.  E.g. why we
   /// couldn't analyze the loop.
   const OptimizationRemarkAnalysis *getReport() const { return Report.get(); }
 
   /// the Memory Dependence Checker which can determine the
   /// loop-independent and loop-carried dependences between memory accesses.
   const MemoryDepChecker &getDepChecker() const { return *DepChecker; }

llvm/include/llvm/Transforms/Utils/LoopVersioning.h

 // loop speculates that otherwise may-aliasing memory accesses don't overlap and
 // emits checks to prove this.
 //
 //===----------------------------------------------------------------------===//
 
 #ifndef LLVM_TRANSFORMS_UTILS_LOOPVERSIONING_H
 #define LLVM_TRANSFORMS_UTILS_LOOPVERSIONING_H
 
-#include "llvm/Analysis/LoopAccessAnalysis.h"
 #include "llvm/Analysis/ScalarEvolution.h"
 #include "llvm/Transforms/Utils/LoopUtils.h"
 #include "llvm/Transforms/Utils/ValueMapper.h"
 
 namespace llvm {
 
 class Loop;
 class LoopAccessInfo;
 class LoopInfo;
 class ScalarEvolution;
+struct RuntimeCheckingPtrGroup;
+typedef std::pair<const RuntimeCheckingPtrGroup *,
+                  const RuntimeCheckingPtrGroup *>
+    RuntimePointerCheck;
 
 /// This class emits a version of the loop where run-time checks ensure
 /// that may-alias pointers can't overlap.
 ///
 /// It currently only supports single-exit loops and assumes that the loop
 /// already has a preheader.
 class LoopVersioning {
 public:
public:
   /// same as the original loop that we got constructed with.)
   Loop *getVersionedLoop() { return VersionedLoop; }
 
   /// Returns the fall-back loop.  Control flows here if pointers in the
   /// loop may alias (i.e. one of the memchecks failed).
   Loop *getNonVersionedLoop() { return NonVersionedLoop; }
 
   /// Sets the runtime alias checks for versioning the loop.
-  void setAliasChecks(
-      SmallVector<RuntimePointerChecking::PointerCheck, 4> Checks);
+  void setAliasChecks(SmallVector<RuntimePointerCheck, 4> Checks);
 
   /// Sets the runtime SCEV checks for versioning the loop.
   void setSCEVChecks(SCEVUnionPredicate Check);
 
   /// Annotate memory instructions in the versioned loop with no-alias
   /// metadata based on the memchecks issued.
   ///
   /// This is just wrapper that calls prepareNoAliasMetadata and
private:
   /// loop may alias (memchecks failed).
   Loop *NonVersionedLoop;
 
   /// This maps the instructions from VersionedLoop to their counterpart
   /// in NonVersionedLoop.
   ValueToValueMapTy VMap;
 
   /// The set of alias checks that we are versioning for.
-  SmallVector<RuntimePointerChecking::PointerCheck, 4> AliasChecks;
+  SmallVector<RuntimePointerCheck, 4> AliasChecks;
 
   /// The set of SCEV checks that we are versioning for.
   SCEVUnionPredicate Preds;
 
   /// Maps a pointer to the pointer checking group that the pointer
   /// belongs to.
-  DenseMap<const Value *, const RuntimePointerChecking::CheckingPtrGroup *>
-      PtrToGroup;
+  DenseMap<const Value *, const RuntimeCheckingPtrGroup *> PtrToGroup;
 
   /// The alias scope corresponding to a pointer checking group.
-  DenseMap<const RuntimePointerChecking::CheckingPtrGroup *, MDNode *>
-      GroupToScope;
+  DenseMap<const RuntimeCheckingPtrGroup *, MDNode *> GroupToScope;
 
   /// The list of alias scopes that a pointer checking group can't alias.
-  DenseMap<const RuntimePointerChecking::CheckingPtrGroup *, MDNode *>
+  DenseMap<const RuntimeCheckingPtrGroup *, MDNode *>
       GroupToNonAliasingScopeList;
 
   /// Analyses used.
   const LoopAccessInfo &LAI;
   LoopInfo *LI;
   DominatorTree *DT;
   ScalarEvolution *SE;
 };
 }
 
 #endif

llvm/lib/Analysis/LoopAccessAnalysis.cpp

LLVM_DEBUG(dbgs() << "LAA: Replacing SCEV: " << *OrigSCEV
                       << " by: " << *Expr << "\n");
     return Expr;
   }
 
   // Otherwise, just return the SCEV of the original pointer.
   return OrigSCEV;
 }
 
+RuntimeCheckingPtrGroup::RuntimeCheckingPtrGroup(
+    unsigned Index, RuntimePointerChecking &RtCheck)
+    : RtCheck(RtCheck), High(RtCheck.Pointers[Index].End),
+      Low(RtCheck.Pointers[Index].Start) {
+  Members.push_back(Index);
+}
+
 /// Calculate Start and End points of memory access.
 /// Let's assume A is the first access and B is a memory access on N-th loop
 /// iteration. Then B is calculated as:
 ///   B = A + Step*N .
 /// Step value may be positive or negative.
 /// N is a calculated back-edge taken count:
 ///     N = (TripCount > 0) ? RoundDown(TripCount -1 , VF) : 0
 /// Start and End points are calculated in the following way:
unsigned EltSize =
       Ptr->getType()->getPointerElementType()->getScalarSizeInBits() / 8;
     const SCEV *EltSizeSCEV = SE->getConstant(ScEnd->getType(), EltSize);
     ScEnd = SE->getAddExpr(ScEnd, EltSizeSCEV);
   }
 
   Pointers.emplace_back(Ptr, ScStart, ScEnd, WritePtr, DepSetId, ASId, Sc);
 }
 
-SmallVector<RuntimePointerChecking::PointerCheck, 4>
+SmallVector<RuntimePointerCheck, 4>
 RuntimePointerChecking::generateChecks() const {
-  SmallVector<PointerCheck, 4> Checks;
+  SmallVector<RuntimePointerCheck, 4> Checks;
 
   for (unsigned I = 0; I < CheckingGroups.size(); ++I) {
     for (unsigned J = I + 1; J < CheckingGroups.size(); ++J) {
-      const RuntimePointerChecking::CheckingPtrGroup &CGI = CheckingGroups[I];
-      const RuntimePointerChecking::CheckingPtrGroup &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::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 {
+bool RuntimePointerChecking::needsChecking(
+    const RuntimeCheckingPtrGroup &M, const RuntimeCheckingPtrGroup &N) const {
   for (unsigned I = 0, EI = M.Members.size(); EI != I; ++I)
     for (unsigned J = 0, EJ = N.Members.size(); EJ != J; ++J)
       if (needsChecking(M.Members[I], N.Members[J]))
         return true;
   return false;
 }
 
 /// Compare \p I and \p J and return the minimum.
 /// Return nullptr in case we couldn't find an answer.
 static const SCEV *getMinFromExprs(const SCEV *I, const SCEV *J,
                                    ScalarEvolution *SE) {
   const SCEV *Diff = SE->getMinusSCEV(J, I);
   const SCEVConstant *C = dyn_cast<const SCEVConstant>(Diff);
 
   if (!C)
     return nullptr;
   if (C->getValue()->isNegative())
     return J;
   return I;
 }
 
-bool RuntimePointerChecking::CheckingPtrGroup::addPointer(unsigned Index) {
+bool RuntimeCheckingPtrGroup::addPointer(unsigned Index) {
   const SCEV *Start = RtCheck.Pointers[Index].Start;
   const SCEV *End = RtCheck.Pointers[Index].End;
 
   // Compare the starts and ends with the known minimum and maximum
   // of this set. We need to know how we compare against the min/max
   // of the set in order to be able to emit memchecks.
   const SCEV *Min0 = getMinFromExprs(Start, Low, RtCheck.SE);
   if (!Min0)
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(CheckingPtrGroup(I, *this));
+      CheckingGroups.push_back(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<CheckingPtrGroup, 2> Groups;
+    SmallVector<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) {
       unsigned Pointer = PositionMap[MI->getPointer()];
       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 (CheckingPtrGroup &Group : Groups) {
+      for (RuntimeCheckingPtrGroup &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)) {
           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(CheckingPtrGroup(Pointer, *this));
+        Groups.push_back(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));
   }
 }
 
bool RuntimePointerChecking::needsChecking(unsigned I, unsigned J) const {
   // Only need to check pointers in the same alias set.
   if (PointerI.AliasSetId != PointerJ.AliasSetId)
     return false;
 
   return true;
 }
 
 void RuntimePointerChecking::printChecks(
-    raw_ostream &OS, const SmallVectorImpl<PointerCheck> &Checks,
+    raw_ostream &OS, const SmallVectorImpl<RuntimePointerCheck> &Checks,
     unsigned Depth) const {
   unsigned N = 0;
   for (const auto &Check : Checks) {
     const auto &First = Check.first->Members, &Second = Check.second->Members;
 
     OS.indent(Depth) << "Check " << N++ << ":\n";
 
     OS.indent(Depth + 2) << "Comparing group (" << Check.first << "):\n";
struct PointerBounds {
   TrackingVH<Value> Start;
   TrackingVH<Value> End;
 };
 
 } // end anonymous namespace
 
 /// Expand code for the lower and upper bound of the pointer group \p CG
 /// in \p TheLoop.  \return the values for the bounds.
-static PointerBounds
-expandBounds(const RuntimePointerChecking::CheckingPtrGroup *CG, Loop *TheLoop,
-             Instruction *Loc, SCEVExpander &Exp, ScalarEvolution *SE,
+static PointerBounds expandBounds(const RuntimeCheckingPtrGroup *CG,
+                                  Loop *TheLoop, Instruction *Loc,
+                                  SCEVExpander &Exp, ScalarEvolution *SE,
                                   const RuntimePointerChecking &PtrRtChecking) {
   Value *Ptr = PtrRtChecking.Pointers[CG->Members[0]].PointerValue;
   const SCEV *Sc = SE->getSCEV(Ptr);
 
   unsigned AS = Ptr->getType()->getPointerAddressSpace();
   LLVMContext &Ctx = Loc->getContext();
 
   // Use this type for pointer arithmetic.
   Type *PtrArithTy = Type::getInt8PtrTy(Ctx, AS);
if (SE->isLoopInvariant(Sc, TheLoop)) {
     LLVM_DEBUG(dbgs() << "Start: " << *CG->Low << " End: " << *CG->High
                       << "\n");
     return {Start, End};
   }
 }
 
 /// Turns a collection of checks into a collection of expanded upper and
 /// lower bounds for both pointers in the check.
-static SmallVector<std::pair<PointerBounds, PointerBounds>, 4> expandBounds(
-    const SmallVectorImpl<RuntimePointerChecking::PointerCheck> &PointerChecks,
-    Loop *L, Instruction *Loc, ScalarEvolution *SE, SCEVExpander &Exp,
+static SmallVector<std::pair<PointerBounds, PointerBounds>, 4>
+expandBounds(const SmallVectorImpl<RuntimePointerCheck> &PointerChecks, Loop *L,
+             Instruction *Loc, ScalarEvolution *SE, SCEVExpander &Exp,
              const RuntimePointerChecking &PtrRtChecking) {
   SmallVector<std::pair<PointerBounds, PointerBounds>, 4> ChecksWithBounds;
 
   // Here we're relying on the SCEV Expander's cache to only emit code for the
   // same bounds once.
   transform(
       PointerChecks, std::back_inserter(ChecksWithBounds),
-      [&](const RuntimePointerChecking::PointerCheck &Check) {
+      [&](const RuntimePointerCheck &Check) {
         PointerBounds
           First = expandBounds(Check.first, L, Loc, Exp, SE, PtrRtChecking),
           Second = expandBounds(Check.second, L, Loc, Exp, SE, PtrRtChecking);
         return std::make_pair(First, Second);
       });
 
   return ChecksWithBounds;
 }
 
 std::pair<Instruction *, Instruction *> LoopAccessInfo::addRuntimeChecks(
     Instruction *Loc,
-    const SmallVectorImpl<RuntimePointerChecking::PointerCheck> &PointerChecks)
-    const {
+    const SmallVectorImpl<RuntimePointerCheck> &PointerChecks) const {
   const DataLayout &DL = TheLoop->getHeader()->getModule()->getDataLayout();
   auto *SE = PSE->getSE();
   SCEVExpander Exp(*SE, DL, "induction");
   auto ExpandedChecks =
       expandBounds(PointerChecks, TheLoop, Loc, SE, Exp, *PtrRtChecking);
 
   LLVMContext &Ctx = Loc->getContext();
   Instruction *FirstInst = nullptr;

llvm/lib/Transforms/Scalar/LoopDistribute.cpp

public:
   const Optional<bool> &isForced() const { return IsForced; }
 
 private:
   /// Filter out checks between pointers from the same partition.
   ///
   /// \p PtrToPartition contains the partition number for pointers.  Partition
   /// number -1 means that the pointer is used in multiple partitions.  In this
   /// case we can't safely omit the check.
-  SmallVector<RuntimePointerChecking::PointerCheck, 4>
-  includeOnlyCrossPartitionChecks(
-      const SmallVectorImpl<RuntimePointerChecking::PointerCheck> &AllChecks,
+  SmallVector<RuntimePointerCheck, 4> includeOnlyCrossPartitionChecks(
+      const SmallVectorImpl<RuntimePointerCheck> &AllChecks,
       const SmallVectorImpl<int> &PtrToPartition,
       const RuntimePointerChecking *RtPtrChecking) {
-    SmallVector<RuntimePointerChecking::PointerCheck, 4> Checks;
+    SmallVector<RuntimePointerCheck, 4> Checks;
 
     copy_if(AllChecks, std::back_inserter(Checks),
-            [&](const RuntimePointerChecking::PointerCheck &Check) {
+            [&](const RuntimePointerCheck &Check) {
               for (unsigned PtrIdx1 : Check.first->Members)
                 for (unsigned PtrIdx2 : Check.second->Members)
                   // Only include this check if there is a pair of pointers
                   // that require checking and the pointers fall into
                   // separate partitions.
                   //
                   // (Note that we already know at this point that the two
                   // pointer groups need checking but it doesn't follow

llvm/lib/Transforms/Scalar/LoopLoadElimination.cpp

SmallPtrSet<Value *, 4> findPointersWrittenOnForwardingPath(
     std::for_each(MemInstrs.begin(), &MemInstrs[getInstrIndex(LastLoad)],
                   InsertStorePtr);
 
     return PtrsWrittenOnFwdingPath;
   }
 
   /// Determine the pointer alias checks to prove that there are no
   /// intervening stores.
-  SmallVector<RuntimePointerChecking::PointerCheck, 4> collectMemchecks(
+  SmallVector<RuntimePointerCheck, 4> collectMemchecks(
       const SmallVectorImpl<StoreToLoadForwardingCandidate> &Candidates) {
 
     SmallPtrSet<Value *, 4> PtrsWrittenOnFwdingPath =
         findPointersWrittenOnForwardingPath(Candidates);
 
     // Collect the pointers of the candidate loads.
     // FIXME: SmallPtrSet does not work with std::inserter.
     std::set<Value *> CandLoadPtrs;
     transform(Candidates,
                    std::inserter(CandLoadPtrs, CandLoadPtrs.begin()),
                    std::mem_fn(&StoreToLoadForwardingCandidate::getLoadPtr));
 
     const auto &AllChecks = LAI.getRuntimePointerChecking()->getChecks();
-    SmallVector<RuntimePointerChecking::PointerCheck, 4> Checks;
+    SmallVector<RuntimePointerCheck, 4> Checks;
 
     copy_if(AllChecks, std::back_inserter(Checks),
-            [&](const RuntimePointerChecking::PointerCheck &Check) {
+            [&](const RuntimePointerCheck &Check) {
               for (auto PtrIdx1 : Check.first->Members)
                 for (auto PtrIdx2 : Check.second->Members)
                   if (needsChecking(PtrIdx1, PtrIdx2, PtrsWrittenOnFwdingPath,
                                     CandLoadPtrs))
                     return true;
               return false;
             });
 
for (const StoreToLoadForwardingCandidate &Cand : StoreToLoadDependences) {
           << ". Valid store-to-load forwarding across the loop backedge\n");
       Candidates.push_back(Cand);
     }
     if (Candidates.empty())
       return false;
 
     // Check intervening may-alias stores.  These need runtime checks for alias
     // disambiguation.
-    SmallVector<RuntimePointerChecking::PointerCheck, 4> Checks =
-        collectMemchecks(Candidates);
+    SmallVector<RuntimePointerCheck, 4> Checks = collectMemchecks(Candidates);
 
     // Too many checks are likely to outweigh the benefits of forwarding.
     if (Checks.size() > Candidates.size() * CheckPerElim) {
       LLVM_DEBUG(dbgs() << "Too many run-time checks needed.\n");
       return false;
     }
 
     if (LAI.getPSE().getUnionPredicate().getComplexity() >

llvm/lib/Transforms/Utils/LoopUtils.cpp

 #include "llvm/ADT/SetVector.h"
 #include "llvm/ADT/SmallPtrSet.h"
 #include "llvm/ADT/SmallVector.h"
 #include "llvm/Analysis/AliasAnalysis.h"
 #include "llvm/Analysis/BasicAliasAnalysis.h"
 #include "llvm/Analysis/DomTreeUpdater.h"
 #include "llvm/Analysis/GlobalsModRef.h"
 #include "llvm/Analysis/InstructionSimplify.h"
+#include "llvm/Analysis/LoopAccessAnalysis.h"
 #include "llvm/Analysis/LoopInfo.h"
 #include "llvm/Analysis/LoopPass.h"
 #include "llvm/Analysis/MemorySSA.h"
 #include "llvm/Analysis/MemorySSAUpdater.h"
 #include "llvm/Analysis/MustExecute.h"
 #include "llvm/Analysis/ScalarEvolution.h"
 #include "llvm/Analysis/ScalarEvolutionAliasAnalysis.h"
 #include "llvm/Analysis/ScalarEvolutionExpander.h"

llvm/lib/Transforms/Utils/LoopVersioning.cpp

LoopVersioning::LoopVersioning(const LoopAccessInfo &LAI, Loop *L, LoopInfo *LI,
   assert(L->isLoopSimplifyForm() && "Loop is not in loop-simplify form");
   if (UseLAIChecks) {
     setAliasChecks(LAI.getRuntimePointerChecking()->getChecks());
     setSCEVChecks(LAI.getPSE().getUnionPredicate());
   }
 }
 
 void LoopVersioning::setAliasChecks(
-    SmallVector<RuntimePointerChecking::PointerCheck, 4> Checks) {
+    SmallVector<RuntimePointerCheck, 4> Checks) {
   AliasChecks = std::move(Checks);
 }
 
 void LoopVersioning::setSCEVChecks(SCEVUnionPredicate Check) {
   Preds = std::move(Check);
 }
 
 void LoopVersioning::versionLoop(
for (const auto &Group : RtPtrChecking->CheckingGroups) {
     GroupToScope[&Group] = MDB.createAnonymousAliasScope(Domain);
 
     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 RuntimePointerChecking::CheckingPtrGroup *,
-           SmallVector<Metadata *, 4>>
+  DenseMap<const RuntimeCheckingPtrGroup *, SmallVector<Metadata *, 4>>
       GroupToNonAliasingScopes;
 
   for (const auto &Check : AliasChecks)
     GroupToNonAliasingScopes[Check.first].push_back(GroupToScope[Check.second]);
 
   // Finally, transform the above to actually map to scope list which is what
   // the metadata uses.