[Polly][NFC][ScopBuilder] Move addInvariantLoads to ScopBuilder

[domada]

Summary

Moved addInvariantLoads and functions listed below to ScopBuilder:
isAParameter
canAlwaysBeHoisted

These functions were referenced only by getNonHoistableCtx.

Moved CLI parameter PollyAllowDereferenceOfAllFunctionParams to
ScopBuilder.

Added iterator range through InvariantEquivClasses

[Meinersbur]

LGTM apart from the nitpicks.

I can commit for you when you think it's ready.

polly/include/polly/ScopInfo.h

2335 ↗

(On Diff #204183)

[typo] interator

[nit] An iterator range does not contain any elements.

I usually don't nitpick on this: Sentence missing a dot at the end.

2336 ↗

(On Diff #204183)

nice

polly/lib/Analysis/ScopBuilder.cpp

1469 ↗

(On Diff #204183)

[suggestion] Make a static function?

[domada]

Updated new patch with applied remarks.

[domada]

Applied remarks.

[domada]

If there are no more remarks, I think the patch is ready for submission.

polly/trunk/include/polly/ScopBuilder.h

class ScopBuilder {
   /// 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();
 
+  /// Add invariant loads listed in @p InvMAs with the domain of @p Stmt.
+  void addInvariantLoads(ScopStmt &Stmt, InvariantAccessesTy &InvMAs);
+
+  /// Check if @p MA can always be hoisted without execution context.
+  bool canAlwaysBeHoisted(MemoryAccess *MA, bool StmtInvalidCtxIsEmpty,
+                          bool MAInvalidCtxIsEmpty,
+                          bool NonHoistableCtxIsEmpty);
+
   /// Return true if and only if @p LI is a required invariant load.
   bool isRequiredInvariantLoad(LoadInst *LI) const {
     return scop->getRequiredInvariantLoads().count(LI);
   }
 
   /// Check if the base ptr of @p MA is in the SCoP but not hoistable.
   bool hasNonHoistableBasePtrInScop(MemoryAccess *MA, isl::union_map Writes);
 

polly/trunk/include/polly/ScopInfo.h

bool buildDomains(Region *R, DominatorTree &DT, LoopInfo &LI,
                     DenseMap<BasicBlock *, isl::set> &InvalidDomainMap);
 
   /// Add parameter constraints to @p C that imply a non-empty domain.
   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 @p MA can always be hoisted without execution context.
-  bool canAlwaysBeHoisted(MemoryAccess *MA, bool StmtInvalidCtxIsEmpty,
-                          bool MAInvalidCtxIsEmpty,
-                          bool NonHoistableCtxIsEmpty);
-
   /// 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:
   /// Take a list of parameters and add the new ones to the scop.
   void addParams(const ParameterSetTy &NewParameters);
 
   /// Return an iterator range containing the scop parameters.
   iterator_range<ParameterSetTy::iterator> parameters() const {
     return make_range(Parameters.begin(), Parameters.end());
   }
 
+  /// Return an iterator range containing invariant accesses.
+  iterator_range<InvariantEquivClassesTy::iterator> invariantEquivClasses() {
+    return make_range(InvariantEquivClasses.begin(),
+                      InvariantEquivClasses.end());
+  }
+
   /// Return whether this scop is empty, i.e. contains no statements that
   /// could be executed.
   bool isEmpty() const { return Stmts.empty(); }
 
   StringRef getName() {
     if (!name)
       name = R.getNameStr();
     return *name;

polly/trunk/lib/Analysis/ScopBuilder.cpp

 static int const MaxDimensionsInAccessRange = 9;
 
 static cl::opt<bool, true> XModelReadOnlyScalars(
     "polly-analyze-read-only-scalars",
     cl::desc("Model read-only scalar values in the scop description"),
     cl::location(ModelReadOnlyScalars), cl::Hidden, cl::ZeroOrMore,
     cl::init(true), cl::cat(PollyCategory));
 
+static cl::opt<bool> PollyAllowDereferenceOfAllFunctionParams(
+    "polly-allow-dereference-of-all-function-parameters",
+    cl::desc(
+        "Treat all parameters to functions that are pointers as dereferencible."
+        " This is useful for invariant load hoisting, since we can generate"
+        " less runtime checks. This is only valid if all pointers to functions"
+        " are always initialized, so that Polly can choose to hoist"
+        " their loads. "),
+    cl::Hidden, cl::init(false), cl::cat(PollyCategory));
+
 static cl::opt<bool> UnprofitableScalarAccs(
     "polly-unprofitable-scalar-accs",
     cl::desc("Count statements with scalar accesses as not optimizable"),
     cl::Hidden, cl::init(false), cl::cat(PollyCategory));
 
 static cl::opt<bool> DetectFortranArrays(
     "polly-detect-fortran-arrays",
     cl::desc("Detect Fortran arrays and use this for code generation"),
for (ScopStmt &Stmt : *scop) {
 
     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);
-    scop->addInvariantLoads(Stmt, InvariantAccesses);
+    addInvariantLoads(Stmt, InvariantAccesses);
   }
 }
 
 /// Check if an access range is too complex.
 ///
 /// An access range is too complex, if it contains either many disjuncts or
 /// very complex expressions. As a simple heuristic, we assume if a set to
 /// be too complex if the sum of existentially quantified dimensions and
isl::set ScopBuilder::getNonHoistableCtx(MemoryAccess *Access,
   if (TooComplex || !isRequiredInvariantLoad(LI))
     return nullptr;
 
   scop->addAssumption(INVARIANTLOAD, WrittenCtx, LI->getDebugLoc(),
                       AS_RESTRICTION, LI->getParent());
   return WrittenCtx;
 }
 
+static bool isAParameter(llvm::Value *maybeParam, const Function &F) {
+  for (const llvm::Argument &Arg : F.args())
+    if (&Arg == maybeParam)
+      return true;
+
+  return false;
+}
+
+bool ScopBuilder::canAlwaysBeHoisted(MemoryAccess *MA,
+                                     bool StmtInvalidCtxIsEmpty,
+                                     bool MAInvalidCtxIsEmpty,
+                                     bool NonHoistableCtxIsEmpty) {
+  LoadInst *LInst = cast<LoadInst>(MA->getAccessInstruction());
+  const DataLayout &DL = LInst->getParent()->getModule()->getDataLayout();
+  if (PollyAllowDereferenceOfAllFunctionParams &&
+      isAParameter(LInst->getPointerOperand(), scop->getFunction()))
+    return true;
+
+  // TODO: We can provide more information for better but more expensive
+  //       results.
+  if (!isDereferenceableAndAlignedPointer(LInst->getPointerOperand(),
+                                          LInst->getAlignment(), DL))
+    return false;
+
+  // If the location might be overwritten we do not hoist it unconditionally.
+  //
+  // TODO: This is probably too conservative.
+  if (!NonHoistableCtxIsEmpty)
+    return false;
+
+  // If a dereferenceable load is in a statement that is modeled precisely we
+  // can hoist it.
+  if (StmtInvalidCtxIsEmpty && MAInvalidCtxIsEmpty)
+    return true;
+
+  // Even if the statement is not modeled precisely we can hoist the load if it
+  // does not involve any parameters that might have been specialized by the
+  // statement domain.
+  for (unsigned u = 0, e = MA->getNumSubscripts(); u < e; u++)
+    if (!isa<SCEVConstant>(MA->getSubscript(u)))
+      return false;
+  return true;
+}
+
+void ScopBuilder::addInvariantLoads(ScopStmt &Stmt,
+                                    InvariantAccessesTy &InvMAs) {
+  if (InvMAs.empty())
+    return;
+
+  isl::set StmtInvalidCtx = Stmt.getInvalidContext();
+  bool StmtInvalidCtxIsEmpty = StmtInvalidCtx.is_empty();
+
+  // Get the context under which the statement is executed but remove the error
+  // context under which this statement is reached.
+  isl::set DomainCtx = Stmt.getDomain().params();
+  DomainCtx = DomainCtx.subtract(StmtInvalidCtx);
+
+  if (DomainCtx.n_basic_set() >= MaxDisjunctsInDomain) {
+    auto *AccInst = InvMAs.front().MA->getAccessInstruction();
+    scop->invalidate(COMPLEXITY, AccInst->getDebugLoc(), AccInst->getParent());
+    return;
+  }
+
+  // Project out all parameters that relate to loads in the statement. Otherwise
+  // we could have cyclic dependences on the constraints under which the
+  // hoisted loads are executed and we could not determine an order in which to
+  // pre-load them. This happens because not only lower bounds are part of the
+  // domain but also upper bounds.
+  for (auto &InvMA : InvMAs) {
+    auto *MA = InvMA.MA;
+    Instruction *AccInst = MA->getAccessInstruction();
+    if (SE.isSCEVable(AccInst->getType())) {
+      SetVector<Value *> Values;
+      for (const SCEV *Parameter : scop->parameters()) {
+        Values.clear();
+        findValues(Parameter, SE, Values);
+        if (!Values.count(AccInst))
+          continue;
+
+        if (isl::id ParamId = scop->getIdForParam(Parameter)) {
+          int Dim = DomainCtx.find_dim_by_id(isl::dim::param, ParamId);
+          if (Dim >= 0)
+            DomainCtx = DomainCtx.eliminate(isl::dim::param, Dim, 1);
+        }
+      }
+    }
+  }
+
+  for (auto &InvMA : InvMAs) {
+    auto *MA = InvMA.MA;
+    isl::set NHCtx = InvMA.NonHoistableCtx;
+
+    // Check for another invariant access that accesses the same location as
+    // MA and if found consolidate them. Otherwise create a new equivalence
+    // class at the end of InvariantEquivClasses.
+    LoadInst *LInst = cast<LoadInst>(MA->getAccessInstruction());
+    Type *Ty = LInst->getType();
+    const SCEV *PointerSCEV = SE.getSCEV(LInst->getPointerOperand());
+
+    isl::set MAInvalidCtx = MA->getInvalidContext();
+    bool NonHoistableCtxIsEmpty = NHCtx.is_empty();
+    bool MAInvalidCtxIsEmpty = MAInvalidCtx.is_empty();
+
+    isl::set MACtx;
+    // Check if we know that this pointer can be speculatively accessed.
+    if (canAlwaysBeHoisted(MA, StmtInvalidCtxIsEmpty, MAInvalidCtxIsEmpty,
+                           NonHoistableCtxIsEmpty)) {
+      MACtx = isl::set::universe(DomainCtx.get_space());
+    } else {
+      MACtx = DomainCtx;
+      MACtx = MACtx.subtract(MAInvalidCtx.unite(NHCtx));
+      MACtx = MACtx.gist_params(scop->getContext());
+    }
+
+    bool Consolidated = false;
+    for (auto &IAClass : scop->invariantEquivClasses()) {
+      if (PointerSCEV != IAClass.IdentifyingPointer || Ty != IAClass.AccessType)
+        continue;
+
+      // If the pointer and the type is equal check if the access function wrt.
+      // to the domain is equal too. It can happen that the domain fixes
+      // parameter values and these can be different for distinct part of the
+      // SCoP. If this happens we cannot consolidate the loads but need to
+      // create a new invariant load equivalence class.
+      auto &MAs = IAClass.InvariantAccesses;
+      if (!MAs.empty()) {
+        auto *LastMA = MAs.front();
+
+        isl::set AR = MA->getAccessRelation().range();
+        isl::set LastAR = LastMA->getAccessRelation().range();
+        bool SameAR = AR.is_equal(LastAR);
+
+        if (!SameAR)
+          continue;
+      }
+
+      // Add MA to the list of accesses that are in this class.
+      MAs.push_front(MA);
+
+      Consolidated = true;
+
+      // Unify the execution context of the class and this statement.
+      isl::set IAClassDomainCtx = IAClass.ExecutionContext;
+      if (IAClassDomainCtx)
+        IAClassDomainCtx = IAClassDomainCtx.unite(MACtx).coalesce();
+      else
+        IAClassDomainCtx = MACtx;
+      IAClass.ExecutionContext = IAClassDomainCtx;
+      break;
+    }
+
+    if (Consolidated)
+      continue;
+
+    MACtx = MACtx.coalesce();
+
+    // If we did not consolidate MA, thus did not find an equivalence class
+    // for it, we create a new one.
+    scop->addInvariantEquivClass(
+        InvariantEquivClassTy{PointerSCEV, MemoryAccessList{MA}, MACtx, Ty});
+  }
+}
+
 void ScopBuilder::collectCandidateReductionLoads(
     MemoryAccess *StoreMA, SmallVectorImpl<MemoryAccess *> &Loads) {
   ScopStmt *Stmt = StoreMA->getStatement();
 
   auto *Store = dyn_cast<StoreInst>(StoreMA->getAccessInstruction());
   if (!Store)
     return;
 

polly/trunk/lib/Analysis/ScopInfo.cpp

PollyIgnoreInbounds("polly-ignore-inbounds",
                         cl::Hidden, cl::init(false), cl::cat(PollyCategory));
 
 static cl::opt<bool> PollyIgnoreParamBounds(
     "polly-ignore-parameter-bounds",
     cl::desc(
         "Do not add parameter bounds and do no gist simplify sets accordingly"),
     cl::Hidden, cl::init(false), cl::cat(PollyCategory));
 
-static cl::opt<bool> PollyAllowDereferenceOfAllFunctionParams(
-    "polly-allow-dereference-of-all-function-parameters",
-    cl::desc(
-        "Treat all parameters to functions that are pointers as dereferencible."
-        " This is useful for invariant load hoisting, since we can generate"
-        " less runtime checks. This is only valid if all pointers to functions"
-        " are always initialized, so that Polly can choose to hoist"
-        " their loads. "),
-    cl::Hidden, cl::init(false), cl::cat(PollyCategory));
-
 static cl::opt<bool> PollyPreciseFoldAccesses(
     "polly-precise-fold-accesses",
     cl::desc("Fold memory accesses to model more possible delinearizations "
              "(does not scale well)"),
     cl::Hidden, cl::init(false), cl::cat(PollyCategory));
 
 bool polly::UseInstructionNames;
 
for (auto &IAClass : InvariantEquivClasses) {
     for (auto *MA : MAs)
       if (MA->getAccessInstruction() == Val)
         return &IAClass;
   }
 
   return nullptr;
 }
 
-bool isAParameter(llvm::Value *maybeParam, const Function &F) {
-  for (const llvm::Argument &Arg : F.args())
-    if (&Arg == maybeParam)
-      return true;
-
-  return false;
-}
-
-bool Scop::canAlwaysBeHoisted(MemoryAccess *MA, bool StmtInvalidCtxIsEmpty,
-                              bool MAInvalidCtxIsEmpty,
-                              bool NonHoistableCtxIsEmpty) {
-  LoadInst *LInst = cast<LoadInst>(MA->getAccessInstruction());
-  const DataLayout &DL = LInst->getParent()->getModule()->getDataLayout();
-  if (PollyAllowDereferenceOfAllFunctionParams &&
-      isAParameter(LInst->getPointerOperand(), getFunction()))
-    return true;
-
-  // TODO: We can provide more information for better but more expensive
-  //       results.
-  if (!isDereferenceableAndAlignedPointer(LInst->getPointerOperand(),
-                                          LInst->getAlignment(), DL))
-    return false;
-
-  // If the location might be overwritten we do not hoist it unconditionally.
-  //
-  // TODO: This is probably too conservative.
-  if (!NonHoistableCtxIsEmpty)
-    return false;
-
-  // If a dereferenceable load is in a statement that is modeled precisely we
-  // can hoist it.
-  if (StmtInvalidCtxIsEmpty && MAInvalidCtxIsEmpty)
-    return true;
-
-  // Even if the statement is not modeled precisely we can hoist the load if it
-  // does not involve any parameters that might have been specialized by the
-  // statement domain.
-  for (unsigned u = 0, e = MA->getNumSubscripts(); u < e; u++)
-    if (!isa<SCEVConstant>(MA->getSubscript(u)))
-      return false;
-  return true;
-}
-
-void Scop::addInvariantLoads(ScopStmt &Stmt, InvariantAccessesTy &InvMAs) {
-  if (InvMAs.empty())
-    return;
-
-  isl::set StmtInvalidCtx = Stmt.getInvalidContext();
-  bool StmtInvalidCtxIsEmpty = StmtInvalidCtx.is_empty();
-
-  // Get the context under which the statement is executed but remove the error
-  // context under which this statement is reached.
-  isl::set DomainCtx = Stmt.getDomain().params();
-  DomainCtx = DomainCtx.subtract(StmtInvalidCtx);
-
-  if (DomainCtx.n_basic_set() >= MaxDisjunctsInDomain) {
-    auto *AccInst = InvMAs.front().MA->getAccessInstruction();
-    invalidate(COMPLEXITY, AccInst->getDebugLoc(), AccInst->getParent());
-    return;
-  }
-
-  // Project out all parameters that relate to loads in the statement. Otherwise
-  // we could have cyclic dependences on the constraints under which the
-  // hoisted loads are executed and we could not determine an order in which to
-  // pre-load them. This happens because not only lower bounds are part of the
-  // domain but also upper bounds.
-  for (auto &InvMA : InvMAs) {
-    auto *MA = InvMA.MA;
-    Instruction *AccInst = MA->getAccessInstruction();
-    if (SE->isSCEVable(AccInst->getType())) {
-      SetVector<Value *> Values;
-      for (const SCEV *Parameter : Parameters) {
-        Values.clear();
-        findValues(Parameter, *SE, Values);
-        if (!Values.count(AccInst))
-          continue;
-
-        if (isl::id ParamId = getIdForParam(Parameter)) {
-          int Dim = DomainCtx.find_dim_by_id(isl::dim::param, ParamId);
-          if (Dim >= 0)
-            DomainCtx = DomainCtx.eliminate(isl::dim::param, Dim, 1);
-        }
-      }
-    }
-  }
-
-  for (auto &InvMA : InvMAs) {
-    auto *MA = InvMA.MA;
-    isl::set NHCtx = InvMA.NonHoistableCtx;
-
-    // Check for another invariant access that accesses the same location as
-    // MA and if found consolidate them. Otherwise create a new equivalence
-    // class at the end of InvariantEquivClasses.
-    LoadInst *LInst = cast<LoadInst>(MA->getAccessInstruction());
-    Type *Ty = LInst->getType();
-    const SCEV *PointerSCEV = SE->getSCEV(LInst->getPointerOperand());
-
-    isl::set MAInvalidCtx = MA->getInvalidContext();
-    bool NonHoistableCtxIsEmpty = NHCtx.is_empty();
-    bool MAInvalidCtxIsEmpty = MAInvalidCtx.is_empty();
-
-    isl::set MACtx;
-    // Check if we know that this pointer can be speculatively accessed.
-    if (canAlwaysBeHoisted(MA, StmtInvalidCtxIsEmpty, MAInvalidCtxIsEmpty,
-                           NonHoistableCtxIsEmpty)) {
-      MACtx = isl::set::universe(DomainCtx.get_space());
-    } else {
-      MACtx = DomainCtx;
-      MACtx = MACtx.subtract(MAInvalidCtx.unite(NHCtx));
-      MACtx = MACtx.gist_params(getContext());
-    }
-
-    bool Consolidated = false;
-    for (auto &IAClass : InvariantEquivClasses) {
-      if (PointerSCEV != IAClass.IdentifyingPointer || Ty != IAClass.AccessType)
-        continue;
-
-      // If the pointer and the type is equal check if the access function wrt.
-      // to the domain is equal too. It can happen that the domain fixes
-      // parameter values and these can be different for distinct part of the
-      // SCoP. If this happens we cannot consolidate the loads but need to
-      // create a new invariant load equivalence class.
-      auto &MAs = IAClass.InvariantAccesses;
-      if (!MAs.empty()) {
-        auto *LastMA = MAs.front();
-
-        isl::set AR = MA->getAccessRelation().range();
-        isl::set LastAR = LastMA->getAccessRelation().range();
-        bool SameAR = AR.is_equal(LastAR);
-
-        if (!SameAR)
-          continue;
-      }
-
-      // Add MA to the list of accesses that are in this class.
-      MAs.push_front(MA);
-
-      Consolidated = true;
-
-      // Unify the execution context of the class and this statement.
-      isl::set IAClassDomainCtx = IAClass.ExecutionContext;
-      if (IAClassDomainCtx)
-        IAClassDomainCtx = IAClassDomainCtx.unite(MACtx).coalesce();
-      else
-        IAClassDomainCtx = MACtx;
-      IAClass.ExecutionContext = IAClassDomainCtx;
-      break;
-    }
-
-    if (Consolidated)
-      continue;
-
-    MACtx = MACtx.coalesce();
-
-    // If we did not consolidate MA, thus did not find an equivalence class
-    // for it, we create a new one.
-    addInvariantEquivClass(
-        InvariantEquivClassTy{PointerSCEV, MemoryAccessList{MA}, MACtx, Ty});
-  }
-}
-
 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)]