+ /// \brief 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::addRuntimeCheck 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;
+
+ /// \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);
+
+ /// \brief Returns the checks that generateChecks created.
+ const SmallVectorImpl<PointerCheck> &getChecks() const { return Checks; }
+
+ /// \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 Returns the number of run-time checks required according to
+ /// needsChecking.
+ unsigned getNumberOfChecks() const { return Checks.size(); }
+
+ /// \brief 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,
+ 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;
+
+ /// \brief 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);
+
+ /// \brief Decide whether we need to issue a run-time check for pointer at
+ /// index \p I and \p J to prove their independence.
+ ///
+ /// 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 = 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<PointerCheck, 4>
+ generateChecks(const SmallVectorImpl<int> *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<PointerCheck, 4> Checks;
+};
+
+/// \brief 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.
+///
+/// For memory dependences that can be analyzed at compile time, it determines
+/// whether the dependence is part of cycle inhibiting vectorization. This work
+/// is delegated to the MemoryDepChecker class.
+///
+/// For memory dependences that cannot be determined at compile time, it
+/// generates run-time checks to prove independence. This is done by
+/// AccessAnalysis::canCheckPtrAtRT and the checks are maintained by the
+/// RuntimePointerCheck class.
+class LoopAccessInfo {
+public:
+ LoopAccessInfo(Loop *L, ScalarEvolution *SE, const DataLayout &DL,