[Polly][NFC][ScopBuilder] Move hoistInvariantLoads to ScopBuilder

[domada]

Summary

Refactor Scop and ScopBuilder class:

1.Move hoistInvariantLoads function from Scop ScopBuilder class.

2. Private functions (addInvariantLoads, getNonHoistableCtx) are moved to public section of Scop class. hoistInvariantLoads function references these functions. These functions will be moved to ScopBuilder as well in the next steps.

[Meinersbur]

Can you move getNonHoistableCtx/addInvariantLoads to ScopBuilder as well? they contain logic only relevant for hoisting.

[domada]

Ok, I can do it.

Shall I do it in the same patch, or can I do it in the next patch? I prefer to do it in the next patch just to keep patches as small as possible.

[domada]

https://reviews.llvm.org/D63066 -> this child review implements moving of getNonHoistableCtx to ScopBuilder.

[Meinersbur]

In D62925#1535142, @domada wrote:

Shall I do it in the same patch, or can I do it in the next patch? I prefer to do it in the next patch just to keep patches as small as possible.

I think it would be easier to do it in one patch, but since you prefer splitting it into another patch, it's fine with me.

LGTM. Do you want me to commit for you?

[domada]

Yes, please do a commit.
I have updated patch for moving getNonHoistableCtx to ScopBuilder.

polly/trunk/include/polly/ScopBuilder.h

class ScopBuilder {
   ///
   /// In the example below Bound[1] is required to be invariant:
   ///
   /// for (int i = 1; i < Bound[0]; i++)
   ///   for (int j = 1; j < Bound[1]; j++)
   ///     ...
   void verifyInvariantLoads();
 
+  /// Hoist invariant memory loads and check for required ones.
+  ///
+  /// We first identify "common" invariant loads, thus loads that are invariant
+  /// and can be hoisted. Then we check if all required invariant loads have
+  /// been identified as (common) invariant. A load is a required invariant load
+  /// if it was assumed to be invariant during SCoP detection, e.g., to assume
+  /// loop bounds to be affine or runtime alias checks to be placeable. In case
+  /// a required invariant load was not identified as (common) invariant we will
+  /// drop this SCoP. An example for both "common" as well as required invariant
+  /// loads is given below:
+  ///
+  /// 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();
+
   /// Collect loads which might form a reduction chain with @p StoreMA.
   ///
   /// Check if the stored value for @p StoreMA is a binary operator with one or
   /// two loads as operands. If the binary operand is commutative & associative,
   /// used only once (by @p StoreMA) and its load operands are also used only
   /// once, we have found a possible reduction chain. It starts at an operand
   /// load and includes the binary operator and @p StoreMA.
   ///

polly/trunk/include/polly/ScopInfo.h

private:
   isl::set addNonEmptyDomainConstraints(isl::set C) const;
 
   /// Return the access for the base ptr of @p MA if any.
   MemoryAccess *lookupBasePtrAccess(MemoryAccess *MA);
 
   /// Check if the base ptr of @p MA is in the SCoP but not hoistable.
   bool hasNonHoistableBasePtrInScop(MemoryAccess *MA, isl::union_map Writes);
 
-  /// Return the context under which the access cannot be hoisted.
-  ///
-  /// @param Access The access to check.
-  /// @param Writes The set of all memory writes in the scop.
-  ///
-  /// @return Return the context under which the access cannot be hoisted or a
-  ///         nullptr if it cannot be hoisted at all.
-  isl::set getNonHoistableCtx(MemoryAccess *Access, isl::union_map Writes);
-
-  /// Hoist invariant memory loads and check for required ones.
-  ///
-  /// We first identify "common" invariant loads, thus loads that are invariant
-  /// and can be hoisted. Then we check if all required invariant loads have
-  /// been identified as (common) invariant. A load is a required invariant load
-  /// if it was assumed to be invariant during SCoP detection, e.g., to assume
-  /// loop bounds to be affine or runtime alias checks to be placeable. In case
-  /// a required invariant load was not identified as (common) invariant we will
-  /// drop this SCoP. An example for both "common" as well as required invariant
-  /// loads is given below:
-  ///
-  /// 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();
-
   /// 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);
-
   /// Create an id for @p Param and store it in the ParameterIds map.
   void createParameterId(const SCEV *Param);
 
   /// Build the Context of the Scop.
   void buildContext();
 
   /// Add user provided parameter constraints to context (source code).
   void addUserAssumptions(AssumptionCache &AC, DominatorTree &DT, LoopInfo &LI,
public:
   }
 
   /// Add mapping from invariant loads to the representing invariant load of
   ///        their equivalence class.
   void addInvariantLoadMapping(const Value *LoadInst, Value *ClassRep) {
     InvEquivClassVMap[LoadInst] = ClassRep;
   }
 
+  /// Add invariant loads listed in @p InvMAs with the domain of @p Stmt.
+  void addInvariantLoads(ScopStmt &Stmt, InvariantAccessesTy &InvMAs);
+
   /// Remove the metadata stored for @p Access.
   void removeAccessData(MemoryAccess *Access);
 
   /// Return the scalar evolution.
   ScalarEvolution *getSE() const;
 
   /// Return the dominator tree.
   DominatorTree *getDT() const { return DT; }
public:
   bool buildAliasGroup(Scop::AliasGroupTy &AliasGroup,
                        DenseSet<const ScopArrayInfo *> HasWriteAccess);
 
   /// Return all alias groups for this SCoP.
   const MinMaxVectorPairVectorTy &getAliasGroups() const {
     return MinMaxAliasGroups;
   }
 
+  /// Return the context under which the access cannot be hoisted.
+  ///
+  /// @param Access The access to check.
+  /// @param Writes The set of all memory writes in the scop.
+  ///
+  /// @return Return the context under which the access cannot be hoisted or a
+  ///         nullptr if it cannot be hoisted at all.
+  isl::set getNonHoistableCtx(MemoryAccess *Access, isl::union_map Writes);
+
   /// Get an isl string representing the context.
   std::string getContextStr() const;
 
   /// Get an isl string representing the assumed context.
   std::string getAssumedContextStr() const;
 
   /// Get an isl string representing the invalid context.
   std::string getInvalidContextStr() const;

polly/trunk/lib/Analysis/ScopBuilder.cpp

for (LoadInst *LI : RIL) {
     for (ScopStmt &Stmt : *scop)
       if (Stmt.getArrayAccessOrNULLFor(LI)) {
         scop->invalidate(INVARIANTLOAD, LI->getDebugLoc(), LI->getParent());
         return;
       }
   }
 }
 
+void ScopBuilder::hoistInvariantLoads() {
+  if (!PollyInvariantLoadHoisting)
+    return;
+
+  isl::union_map Writes = scop->getWrites();
+  for (ScopStmt &Stmt : *scop) {
+    InvariantAccessesTy InvariantAccesses;
+
+    for (MemoryAccess *Access : Stmt)
+      if (isl::set NHCtx = scop->getNonHoistableCtx(Access, Writes))
+        InvariantAccesses.push_back({Access, NHCtx});
+
+    // Transfer the memory access from the statement to the SCoP.
+    for (auto InvMA : InvariantAccesses)
+      Stmt.removeMemoryAccess(InvMA.MA);
+    scop->addInvariantLoads(Stmt, InvariantAccesses);
+  }
+}
+
 void ScopBuilder::collectCandidateReductionLoads(
     MemoryAccess *StoreMA, SmallVectorImpl<MemoryAccess *> &Loads) {
   ScopStmt *Stmt = StoreMA->getStatement();
 
   auto *Store = dyn_cast<StoreInst>(StoreMA->getAccessInstruction());
   if (!Store)
     return;
 
void ScopBuilder::buildScop(Region &R, AssumptionCache &AC,
   scop->addRecordedAssumptions();
 
   scop->simplifyContexts();
   if (!scop->buildAliasChecks(AA)) {
     LLVM_DEBUG(dbgs() << "Bailing-out because could not build alias checks\n");
     return;
   }
 
-  scop->hoistInvariantLoads();
+  hoistInvariantLoads();
   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");

polly/trunk/lib/Analysis/ScopInfo.cpp

isl::set Scop::getNonHoistableCtx(MemoryAccess *Access, isl::union_map Writes) {
   if (TooComplex || !isRequiredInvariantLoad(LI))
     return nullptr;
 
   addAssumption(INVARIANTLOAD, WrittenCtx, LI->getDebugLoc(), AS_RESTRICTION,
                 LI->getParent());
   return WrittenCtx;
 }
 
-void Scop::hoistInvariantLoads() {
-  if (!PollyInvariantLoadHoisting)
-    return;
-
-  isl::union_map Writes = getWrites();
-  for (ScopStmt &Stmt : *this) {
-    InvariantAccessesTy InvariantAccesses;
-
-    for (MemoryAccess *Access : Stmt)
-      if (isl::set NHCtx = getNonHoistableCtx(Access, Writes))
-        InvariantAccesses.push_back({Access, NHCtx});
-
-    // Transfer the memory access from the statement to the SCoP.
-    for (auto InvMA : InvariantAccesses)
-      Stmt.removeMemoryAccess(InvMA.MA);
-    addInvariantLoads(Stmt, InvariantAccesses);
-  }
-}
-
 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)]