[Polly][NFC][ScopBuilder] Move canonicalizeDynamicsBasePtrs from ScopInfo

[domada]

Summary

Refactor Scop and ScopBuilder class. Move canonicalizeDynamicsBasePtrs and corresponding static functions from ScopInfo.cpp to ScopBuilder.cpp

[Meinersbur]

LGTM.

Do you want me to commit?

[domada]

Yes, please do a commit.

polly/trunk/include/polly/ScopBuilder.h

class ScopBuilder {
   /// Note: We allow only one use to ensure the load and binary operator cannot
   ///       escape this block or into any other store except @p StoreMA.
   void collectCandidateReductionLoads(MemoryAccess *StoreMA,
                                       SmallVectorImpl<MemoryAccess *> &Loads);
 
   /// Build the access relation of all memory accesses of @p Stmt.
   void buildAccessRelations(ScopStmt &Stmt);
 
+  /// Canonicalize arrays with base pointers from the same equivalence class.
+  ///
+  /// Some context: in our normal model we assume that each base pointer is
+  /// related to a single specific memory region, where memory regions
+  /// associated with different base pointers are disjoint. Consequently we do
+  /// not need to compute additional data dependences that model possible
+  /// overlaps of these memory regions. To verify our assumption we compute
+  /// alias checks that verify that modeled arrays indeed do not overlap. In
+  /// case an overlap is detected the runtime check fails and we fall back to
+  /// the original code.
+  ///
+  /// In case of arrays where the base pointers are know to be identical,
+  /// because they are dynamically loaded by accesses that are in the same
+  /// invariant load equivalence class, such run-time alias check would always
+  /// be false.
+  ///
+  /// This function makes sure that we do not generate consistently failing
+  /// run-time checks for code that contains distinct arrays with known
+  /// equivalent base pointers. It identifies for each invariant load
+  /// equivalence class a single canonical array and canonicalizes all memory
+  /// accesses that reference arrays that have base pointers that are known to
+  /// be equal to the base pointer of such a canonical array to this canonical
+  /// array.
+  ///
+  /// We currently do not canonicalize arrays for which certain memory accesses
+  /// have been hoisted as loop invariant.
+  void canonicalizeDynamicBasePtrs();
+
 public:
   explicit ScopBuilder(Region *R, AssumptionCache &AC, AliasAnalysis &AA,
                        const DataLayout &DL, DominatorTree &DT, LoopInfo &LI,
                        ScopDetection &SD, ScalarEvolution &SE,
                        OptimizationRemarkEmitter &ORE);
   ScopBuilder(const ScopBuilder &) = delete;
   ScopBuilder &operator=(const ScopBuilder &) = delete;
   ~ScopBuilder() = default;

polly/trunk/include/polly/ScopInfo.h

private:
   /// for (int i = 1; i < *LB[0]; i++)
   ///   for (int j = 1; j < *LB[1]; j++)
   ///     A[i][j] += A[0][0] + (*V);
   ///
   /// Common inv. loads: V, A[0][0], LB[0], LB[1]
   /// Required inv. loads: LB[0], LB[1], (V, if it may alias with A or LB)
   void hoistInvariantLoads();
 
-  /// Canonicalize arrays with base pointers from the same equivalence class.
-  ///
-  /// Some context: in our normal model we assume that each base pointer is
-  /// related to a single specific memory region, where memory regions
-  /// associated with different base pointers are disjoint. Consequently we do
-  /// not need to compute additional data dependences that model possible
-  /// overlaps of these memory regions. To verify our assumption we compute
-  /// alias checks that verify that modeled arrays indeed do not overlap. In
-  /// case an overlap is detected the runtime check fails and we fall back to
-  /// the original code.
-  ///
-  /// In case of arrays where the base pointers are know to be identical,
-  /// because they are dynamically loaded by accesses that are in the same
-  /// invariant load equivalence class, such run-time alias check would always
-  /// be false.
-  ///
-  /// This function makes sure that we do not generate consistently failing
-  /// run-time checks for code that contains distinct arrays with known
-  /// equivalent base pointers. It identifies for each invariant load
-  /// equivalence class a single canonical array and canonicalizes all memory
-  /// accesses that reference arrays that have base pointers that are known to
-  /// be equal to the base pointer of such a canonical array to this canonical
-  /// array.
-  ///
-  /// We currently do not canonicalize arrays for which certain memory accesses
-  /// have been hoisted as loop invariant.
-  void canonicalizeDynamicBasePtrs();
-
   /// Check if @p MA can always be hoisted without execution context.
   bool canAlwaysBeHoisted(MemoryAccess *MA, bool StmtInvalidCtxIsEmpty,
                           bool MAInvalidCtxIsEmpty,
                           bool NonHoistableCtxIsEmpty);
 
   /// Add invariant loads listed in @p InvMAs with the domain of @p Stmt.
   void addInvariantLoads(ScopStmt &Stmt, InvariantAccessesTy &InvMAs);
 

polly/trunk/lib/Analysis/ScopBuilder.cpp

void ScopBuilder::collectCandidateReductionLoads(
   if (PossibleLoad0 && PossibleLoad0->getNumUses() == 1)
     if (PossibleLoad0->getParent() == Store->getParent())
       Loads.push_back(&Stmt->getArrayAccessFor(PossibleLoad0));
   if (PossibleLoad1 && PossibleLoad1->getNumUses() == 1)
     if (PossibleLoad1->getParent() == Store->getParent())
       Loads.push_back(&Stmt->getArrayAccessFor(PossibleLoad1));
 }
 
+/// Find the canonical scop array info object for a set of invariant load
+/// hoisted loads. The canonical array is the one that corresponds to the
+/// first load in the list of accesses which is used as base pointer of a
+/// scop array.
+static const ScopArrayInfo *findCanonicalArray(Scop &S,
+                                               MemoryAccessList &Accesses) {
+  for (MemoryAccess *Access : Accesses) {
+    const ScopArrayInfo *CanonicalArray = S.getScopArrayInfoOrNull(
+        Access->getAccessInstruction(), MemoryKind::Array);
+    if (CanonicalArray)
+      return CanonicalArray;
+  }
+  return nullptr;
+}
+
+/// Check if @p Array severs as base array in an invariant load.
+static bool isUsedForIndirectHoistedLoad(Scop &S, const ScopArrayInfo *Array) {
+  for (InvariantEquivClassTy &EqClass2 : S.getInvariantAccesses())
+    for (MemoryAccess *Access2 : EqClass2.InvariantAccesses)
+      if (Access2->getScopArrayInfo() == Array)
+        return true;
+  return false;
+}
+
+/// Replace the base pointer arrays in all memory accesses referencing @p Old,
+/// with a reference to @p New.
+static void replaceBasePtrArrays(Scop &S, const ScopArrayInfo *Old,
+                                 const ScopArrayInfo *New) {
+  for (ScopStmt &Stmt : S)
+    for (MemoryAccess *Access : Stmt) {
+      if (Access->getLatestScopArrayInfo() != Old)
+        continue;
+
+      isl::id Id = New->getBasePtrId();
+      isl::map Map = Access->getAccessRelation();
+      Map = Map.set_tuple_id(isl::dim::out, Id);
+      Access->setAccessRelation(Map);
+    }
+}
+
+void ScopBuilder::canonicalizeDynamicBasePtrs() {
+  for (InvariantEquivClassTy &EqClass : scop->InvariantEquivClasses) {
+    MemoryAccessList &BasePtrAccesses = EqClass.InvariantAccesses;
+
+    const ScopArrayInfo *CanonicalBasePtrSAI =
+        findCanonicalArray(*scop, BasePtrAccesses);
+
+    if (!CanonicalBasePtrSAI)
+      continue;
+
+    for (MemoryAccess *BasePtrAccess : BasePtrAccesses) {
+      const ScopArrayInfo *BasePtrSAI = scop->getScopArrayInfoOrNull(
+          BasePtrAccess->getAccessInstruction(), MemoryKind::Array);
+      if (!BasePtrSAI || BasePtrSAI == CanonicalBasePtrSAI ||
+          !BasePtrSAI->isCompatibleWith(CanonicalBasePtrSAI))
+        continue;
+
+      // we currently do not canonicalize arrays where some accesses are
+      // hoisted as invariant loads. If we would, we need to update the access
+      // function of the invariant loads as well. However, as this is not a
+      // very common situation, we leave this for now to avoid further
+      // complexity increases.
+      if (isUsedForIndirectHoistedLoad(*scop, BasePtrSAI))
+        continue;
+
+      replaceBasePtrArrays(*scop, BasePtrSAI, CanonicalBasePtrSAI);
+    }
+  }
+}
+
 void ScopBuilder::buildAccessRelations(ScopStmt &Stmt) {
   for (MemoryAccess *Access : Stmt.MemAccs) {
     Type *ElementType = Access->getElementType();
 
     MemoryKind Ty;
     if (Access->isPHIKind())
       Ty = MemoryKind::PHI;
     else if (Access->isExitPHIKind())
void ScopBuilder::buildScop(Region &R, AssumptionCache &AC,
 
   scop->simplifyContexts();
   if (!scop->buildAliasChecks(AA)) {
     LLVM_DEBUG(dbgs() << "Bailing-out because could not build alias checks\n");
     return;
   }
 
   scop->hoistInvariantLoads();
-  scop->canonicalizeDynamicBasePtrs();
+  canonicalizeDynamicBasePtrs();
   verifyInvariantLoads();
   scop->simplifySCoP(true);
 
   // Check late for a feasible runtime context because profitability did not
   // change.
   if (!scop->hasFeasibleRuntimeContext()) {
     LLVM_DEBUG(dbgs() << "Bailing-out because of unfeasible context (late)\n");
     return;

polly/trunk/lib/Analysis/ScopInfo.cpp

for (ScopStmt &Stmt : *this) {
 
     // Transfer the memory access from the statement to the SCoP.
     for (auto InvMA : InvariantAccesses)
       Stmt.removeMemoryAccess(InvMA.MA);
     addInvariantLoads(Stmt, InvariantAccesses);
   }
 }
 
-/// Find the canonical scop array info object for a set of invariant load
-/// hoisted loads. The canonical array is the one that corresponds to the
-/// first load in the list of accesses which is used as base pointer of a
-/// scop array.
-static const ScopArrayInfo *findCanonicalArray(Scop *S,
-                                               MemoryAccessList &Accesses) {
-  for (MemoryAccess *Access : Accesses) {
-    const ScopArrayInfo *CanonicalArray = S->getScopArrayInfoOrNull(
-        Access->getAccessInstruction(), MemoryKind::Array);
-    if (CanonicalArray)
-      return CanonicalArray;
-  }
-  return nullptr;
-}
-
-/// Check if @p Array severs as base array in an invariant load.
-static bool isUsedForIndirectHoistedLoad(Scop *S, const ScopArrayInfo *Array) {
-  for (InvariantEquivClassTy &EqClass2 : S->getInvariantAccesses())
-    for (MemoryAccess *Access2 : EqClass2.InvariantAccesses)
-      if (Access2->getScopArrayInfo() == Array)
-        return true;
-  return false;
-}
-
-/// Replace the base pointer arrays in all memory accesses referencing @p Old,
-/// with a reference to @p New.
-static void replaceBasePtrArrays(Scop *S, const ScopArrayInfo *Old,
-                                 const ScopArrayInfo *New) {
-  for (ScopStmt &Stmt : *S)
-    for (MemoryAccess *Access : Stmt) {
-      if (Access->getLatestScopArrayInfo() != Old)
-        continue;
-
-      isl::id Id = New->getBasePtrId();
-      isl::map Map = Access->getAccessRelation();
-      Map = Map.set_tuple_id(isl::dim::out, Id);
-      Access->setAccessRelation(Map);
-    }
-}
-
-void Scop::canonicalizeDynamicBasePtrs() {
-  for (InvariantEquivClassTy &EqClass : InvariantEquivClasses) {
-    MemoryAccessList &BasePtrAccesses = EqClass.InvariantAccesses;
-
-    const ScopArrayInfo *CanonicalBasePtrSAI =
-        findCanonicalArray(this, BasePtrAccesses);
-
-    if (!CanonicalBasePtrSAI)
-      continue;
-
-    for (MemoryAccess *BasePtrAccess : BasePtrAccesses) {
-      const ScopArrayInfo *BasePtrSAI = getScopArrayInfoOrNull(
-          BasePtrAccess->getAccessInstruction(), MemoryKind::Array);
-      if (!BasePtrSAI || BasePtrSAI == CanonicalBasePtrSAI ||
-          !BasePtrSAI->isCompatibleWith(CanonicalBasePtrSAI))
-        continue;
-
-      // we currently do not canonicalize arrays where some accesses are
-      // hoisted as invariant loads. If we would, we need to update the access
-      // function of the invariant loads as well. However, as this is not a
-      // very common situation, we leave this for now to avoid further
-      // complexity increases.
-      if (isUsedForIndirectHoistedLoad(this, BasePtrSAI))
-        continue;
-
-      replaceBasePtrArrays(this, BasePtrSAI, CanonicalBasePtrSAI);
-    }
-  }
-}
-
 ScopArrayInfo *Scop::getOrCreateScopArrayInfo(Value *BasePtr, Type *ElementType,
                                               ArrayRef<const SCEV *> Sizes,
                                               MemoryKind Kind,
                                               const char *BaseName) {
   assert((BasePtr || BaseName) &&
          "BasePtr and BaseName can not be nullptr at the same time.");
   assert(!(BasePtr && BaseName) && "BaseName is redundant.");
   auto &SAI = BasePtr ? ScopArrayInfoMap[std::make_pair(BasePtr, Kind)]