[Polly][NFC][ScopBuilder] Move addUserAssumptions to ScopBuilder

[domada]

Summary

Scope of changes:

1. Moved addUserAssumptions function to ScopBuilder class.
2. Moved buildConditionSets functions to polly namespace.
3. Moved getRepresentingInvariantLoadSCEV to public section of the Scop class

[Meinersbur]

[remark] Summary: getRepresentingInvariantLoadSCEV is already in the Scop class. Did you want to say changing its visibility to public?

[serious] buildConditionSets is now in the ScopInfo header and therefore made made accessible to the world. This is the opposite of the goal of moving things to ScopBuilder. Is this maybe an intermediate step before also moving buildConditionSets to ScopBuilder?

polly/include/polly/ScopInfo.h

1644

[nit] Missing space before doxygen comment

polly/lib/Analysis/ScopInfo.cpp

2820

[nit] Unrelated change

[domada]

In D65241#1601213, @Meinersbur wrote:

[remark] Summary: getRepresentingInvariantLoadSCEV is already in the Scop class. Did you want to say changing its visibility to public?

Indeed. I want to make it public, because I think that it can be hellpful in the future if we want to remove friendship between ScopBuilder and Scop class. I have fixed summary.

In D65241#1601213, @Meinersbur wrote:

[serious] buildConditionSets is now in the ScopInfo header and therefore made made accessible to the world. This is the opposite of the goal of moving things to ScopBuilder. Is this maybe an intermediate step before also moving buildConditionSets to ScopBuilder?

Yes. It is an intermediate step. I have noticed, that buildConditionSets functions are also used by buildDomains which are still inside Scop class. In the next step I want to move buildDomains and buildConditionSets to ScopBuilder.

Maybe you can make a final review when I propose next patch with moved buildDomains functions?

[Meinersbur]

In D65241#1601609, @domada wrote:

Maybe you can make a final review when I propose next patch with moved buildDomains functions?

Sure

[domada]

Remove duplicated buildConditionSets declaration.

[domada]

https://reviews.llvm.org/D65729 -> this patch moves buildConditionSets functions to ScopBuilder class. It is not possible to move them enterily in patch 65241 because some Scop functions use these functions.

That's why I have decided to make them visible by adding their declaration to ScopInfo.h file. Patch 65729 solves this dependency and it moves all buildConditionSets functions to ScopBuilder class.

[Meinersbur]

LGTM (with D65729)

polly/include/polly/ScopBuilder.h

class ScopBuilder {
   /// @see MemoryKind
   void ensurePHIWrite(PHINode *PHI, ScopStmt *IncomintStmt,
                       BasicBlock *IncomingBlock, Value *IncomingValue,
                       bool IsExitBlock);
 
   /// Add user provided parameter constraints to context (command line).
   void addUserContext();
 
+  /// Add user provided parameter constraints to context (source code).
+  void addUserAssumptions(AssumptionCache &AC,
+                          DenseMap<BasicBlock *, isl::set> &InvalidDomainMap);
+
   /// Add all recorded assumptions to the assumed context.
   void addRecordedAssumptions();
 
   /// Create a MemoryAccess for reading the value of a phi.
   ///
   /// The modeling assumes that all incoming blocks write their incoming value
   /// to the same location. Thus, this access will read the incoming block's
   /// value as instructed by this @p PHI.

polly/include/polly/ScopInfo.h

struct Assumption {
   isl::set Set;
 
   /// The location that caused this assumption.
   DebugLoc Loc;
 
   /// An optional block whose domain can simplify the assumption.
   BasicBlock *BB;
 };
 
+/// Build the conditions sets for the branch condition @p Condition in
+/// the @p Domain.
+///
+/// This will fill @p ConditionSets with the conditions under which control
+/// will be moved from @p TI to its successors. Hence, @p ConditionSets will
+/// have as many elements as @p TI has successors. If @p TI is nullptr the
+/// context under which @p Condition is true/false will be returned as the
+/// new elements of @p ConditionSets.
+bool buildConditionSets(Scop &S, BasicBlock *BB, Value *Condition,
+                        Instruction *TI, Loop *L, __isl_keep isl_set *Domain,
+                        DenseMap<BasicBlock *, isl::set> &InvalidDomainMap,
+                        SmallVectorImpl<__isl_give isl_set *> &ConditionSets);
+
+/// Build condition sets for unsigned ICmpInst(s).
+/// Special handling is required for unsigned operands to ensure that if
+/// MSB (aka the Sign bit) is set for an operands in an unsigned ICmpInst
+/// it should wrap around.
+///
+/// @param IsStrictUpperBound holds information on the predicate relation
+/// between TestVal and UpperBound, i.e,
+/// TestVal < UpperBound  OR  TestVal <= UpperBound
+__isl_give isl_set *
+buildUnsignedConditionSets(Scop &S, BasicBlock *BB, Value *Condition,
+                           __isl_keep isl_set *Domain, const SCEV *SCEV_TestVal,
+                           const SCEV *SCEV_UpperBound,
+                           DenseMap<BasicBlock *, isl::set> &InvalidDomainMap,
+                           bool IsStrictUpperBound);
+
+/// Build the conditions sets for the terminator @p TI in the @p Domain.
+///
+/// This will fill @p ConditionSets with the conditions under which control
+/// will be moved from @p TI to its successors. Hence, @p ConditionSets will
+/// have as many elements as @p TI has successors.
+bool buildConditionSets(Scop &S, BasicBlock *BB, Instruction *TI, Loop *L,
+                        __isl_keep isl_set *Domain,
+                        DenseMap<BasicBlock *, isl::set> &InvalidDomainMap,
+                        SmallVectorImpl<__isl_give isl_set *> &ConditionSets);
+
 /// Static Control Part
 ///
 /// A Scop is the polyhedral representation of a control flow region detected
 /// by the Scop detection. It is generated by translating the LLVM-IR and
 /// abstracting its effects.
 ///
 /// A Scop consists of a set of:
 ///
private:
   MemoryAccess *lookupBasePtrAccess(MemoryAccess *MA);
 
   /// 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,
-                          DenseMap<BasicBlock *, isl::set> &InvalidDomainMap);
-
   /// Add the bounds of the parameters to the context.
   void addParameterBounds();
 
   /// Simplify the assumed and invalid context.
   void simplifyContexts();
 
-  /// Get the representing SCEV for @p S if applicable, otherwise @p S.
-  ///
-  /// Invariant loads of the same location are put in an equivalence class and
-  /// only one of them is chosen as a representing element that will be
-  /// modeled as a parameter. The others have to be normalized, i.e.,
-  /// replaced by the representing element of their equivalence class, in order
-  /// to get the correct parameter value, e.g., in the SCEVAffinator.
-  ///
-  /// @param S The SCEV to normalize.
-  ///
-  /// @return The representing SCEV for invariant loads or @p S if none.
-  const SCEV *getRepresentingInvariantLoadSCEV(const SCEV *S) const;
-
   /// Create a new SCoP statement for @p BB.
   ///
   /// A new statement for @p BB will be created and added to the statement
   /// vector
   /// and map.
   ///
   /// @param BB              The basic block we build the statement for.
   /// @param Name            The name of the new statement.
public:
   /// Return the LoopInfo used for this Scop.
   LoopInfo *getLI() const { return Affinator.getLI(); }
 
   /// Get the count of parameters used in this Scop.
   ///
   /// @return The count of parameters used in this Scop.
   size_t getNumParams() const { return Parameters.size(); }
 
+  /// Return whether given SCEV is used as the parameter in this Scop.
+  bool isParam(const SCEV *Param) const { return Parameters.count(Param); }
+
   /// 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());
   }
 
#endif
   long getNextArrayIdx() { return ArrayIdx++; }
 
   /// Get the next free statement index.
   ///
   /// This function returns a unique index which can be used to identify a
   /// statement.
   long getNextStmtIdx() { return StmtIdx++; }
 
+  /// Get the representing SCEV for @p S if applicable, otherwise @p S.
+  ///
+  /// Invariant loads of the same location are put in an equivalence class and
+  /// only one of them is chosen as a representing element that will be
+  /// modeled as a parameter. The others have to be normalized, i.e.,
+  /// replaced by the representing element of their equivalence class, in order
+  /// to get the correct parameter value, e.g., in the SCEVAffinator.
+  ///
+  /// @param S The SCEV to normalize.
+  ///
+  /// @return The representing SCEV for invariant loads or @p S if none.
+  const SCEV *getRepresentingInvariantLoadSCEV(const SCEV *S) const;
+
   /// Return the MemoryAccess that writes an llvm::Value, represented by a
   /// ScopArrayInfo.
   ///
   /// There can be at most one such MemoryAccess per llvm::Value in the SCoP.
   /// Zero is possible for read-only values.
   MemoryAccess *getValueDef(const ScopArrayInfo *SAI) const;
 
   /// Return all MemoryAccesses that us an llvm::Value, represented by a

polly/lib/Analysis/ScopBuilder.cpp

 #include "polly/Support/SCEVValidator.h"
 #include "polly/Support/ScopHelper.h"
 #include "polly/Support/VirtualInstruction.h"
 #include "llvm/ADT/ArrayRef.h"
 #include "llvm/ADT/EquivalenceClasses.h"
 #include "llvm/ADT/PostOrderIterator.h"
 #include "llvm/ADT/Statistic.h"
 #include "llvm/Analysis/AliasAnalysis.h"
+#include "llvm/Analysis/AssumptionCache.h"
 #include "llvm/Analysis/Loads.h"
 #include "llvm/Analysis/LoopInfo.h"
 #include "llvm/Analysis/OptimizationRemarkEmitter.h"
 #include "llvm/Analysis/RegionInfo.h"
 #include "llvm/Analysis/RegionIterator.h"
 #include "llvm/Analysis/ScalarEvolution.h"
 #include "llvm/Analysis/ScalarEvolutionExpressions.h"
 #include "llvm/IR/BasicBlock.h"
for (auto &AS : llvm::reverse(scop->recorded_assumptions())) {
     else /* (AS.Sign == AS_ASSUMPTION) */
       S = isl_set_params(isl_set_subtract(Dom, S));
 
     scop->addAssumption(AS.Kind, isl::manage(S), AS.Loc, AS_RESTRICTION, AS.BB);
   }
   scop->clearRecordedAssumptions();
 }
 
+void ScopBuilder::addUserAssumptions(
+    AssumptionCache &AC, DenseMap<BasicBlock *, isl::set> &InvalidDomainMap) {
+  for (auto &Assumption : AC.assumptions()) {
+    auto *CI = dyn_cast_or_null<CallInst>(Assumption);
+    if (!CI || CI->getNumArgOperands() != 1)
+      continue;
+
+    bool InScop = scop->contains(CI);
+    if (!InScop && !scop->isDominatedBy(DT, CI->getParent()))
+      continue;
+
+    auto *L = LI.getLoopFor(CI->getParent());
+    auto *Val = CI->getArgOperand(0);
+    ParameterSetTy DetectedParams;
+    auto &R = scop->getRegion();
+    if (!isAffineConstraint(Val, &R, L, SE, DetectedParams)) {
+      ORE.emit(
+          OptimizationRemarkAnalysis(DEBUG_TYPE, "IgnoreUserAssumption", CI)
+          << "Non-affine user assumption ignored.");
+      continue;
+    }
+
+    // Collect all newly introduced parameters.
+    ParameterSetTy NewParams;
+    for (auto *Param : DetectedParams) {
+      Param = extractConstantFactor(Param, SE).second;
+      Param = scop->getRepresentingInvariantLoadSCEV(Param);
+      if (scop->isParam(Param))
+        continue;
+      NewParams.insert(Param);
+    }
+
+    SmallVector<isl_set *, 2> ConditionSets;
+    auto *TI = InScop ? CI->getParent()->getTerminator() : nullptr;
+    BasicBlock *BB = InScop ? CI->getParent() : R.getEntry();
+    auto *Dom = InScop ? isl_set_copy(scop->getDomainConditions(BB).get())
+                       : isl_set_copy(scop->getContext().get());
+    assert(Dom && "Cannot propagate a nullptr.");
+    bool Valid = buildConditionSets(*scop, BB, Val, TI, L, Dom,
+                                    InvalidDomainMap, ConditionSets);
+    isl_set_free(Dom);
+
+    if (!Valid)
+      continue;
+
+    isl_set *AssumptionCtx = nullptr;
+    if (InScop) {
+      AssumptionCtx = isl_set_complement(isl_set_params(ConditionSets[1]));
+      isl_set_free(ConditionSets[0]);
+    } else {
+      AssumptionCtx = isl_set_complement(ConditionSets[1]);
+      AssumptionCtx = isl_set_intersect(AssumptionCtx, ConditionSets[0]);
+    }
+
+    // Project out newly introduced parameters as they are not otherwise useful.
+    if (!NewParams.empty()) {
+      for (unsigned u = 0; u < isl_set_n_param(AssumptionCtx); u++) {
+        auto *Id = isl_set_get_dim_id(AssumptionCtx, isl_dim_param, u);
+        auto *Param = static_cast<const SCEV *>(isl_id_get_user(Id));
+        isl_id_free(Id);
+
+        if (!NewParams.count(Param))
+          continue;
+
+        AssumptionCtx =
+            isl_set_project_out(AssumptionCtx, isl_dim_param, u--, 1);
+      }
+    }
+    ORE.emit(OptimizationRemarkAnalysis(DEBUG_TYPE, "UserAssumption", CI)
+             << "Use user assumption: " << stringFromIslObj(AssumptionCtx));
+    isl::set newContext =
+        scop->getContext().intersect(isl::manage(AssumptionCtx));
+    scop->setContext(newContext);
+  }
+}
+
 bool ScopBuilder::buildAccessMultiDimFixed(MemAccInst Inst, ScopStmt *Stmt) {
   Value *Val = Inst.getValueOperand();
   Type *ElementType = Val->getType();
   Value *Address = Inst.getPointerOperand();
   const SCEV *AccessFunction =
       SE.getSCEVAtScope(Address, LI.getLoopFor(Inst->getParent()));
   const SCEVUnknown *BasePointer =
       dyn_cast<SCEVUnknown>(SE.getPointerBase(AccessFunction));
void ScopBuilder::buildScop(Region &R, AssumptionCache &AC) {
   DenseMap<BasicBlock *, isl::set> InvalidDomainMap;
 
   if (!scop->buildDomains(&R, DT, LI, InvalidDomainMap)) {
     LLVM_DEBUG(
         dbgs() << "Bailing-out because buildDomains encountered problems\n");
     return;
   }
 
-  scop->addUserAssumptions(AC, DT, LI, InvalidDomainMap);
+  addUserAssumptions(AC, InvalidDomainMap);
 
   // Initialize the invalid domain.
   for (ScopStmt &Stmt : scop->Stmts)
     if (Stmt.isBlockStmt())
       Stmt.setInvalidDomain(InvalidDomainMap[Stmt.getEntryBlock()]);
     else
       Stmt.setInvalidDomain(InvalidDomainMap[getRegionNodeBasicBlock(
           Stmt.getRegion()->getNode())]);

polly/lib/Analysis/ScopInfo.cpp

 /// Build condition sets for unsigned ICmpInst(s).
 /// Special handling is required for unsigned operands to ensure that if
 /// MSB (aka the Sign bit) is set for an operands in an unsigned ICmpInst
 /// it should wrap around.
 ///
 /// @param IsStrictUpperBound holds information on the predicate relation
 /// between TestVal and UpperBound, i.e,
 /// TestVal < UpperBound  OR  TestVal <= UpperBound
-__isl_give isl_set *
-buildUnsignedConditionSets(Scop &S, BasicBlock *BB, Value *Condition,
-                           __isl_keep isl_set *Domain, const SCEV *SCEV_TestVal,
-                           const SCEV *SCEV_UpperBound,
-                           DenseMap<BasicBlock *, isl::set> &InvalidDomainMap,
-                           bool IsStrictUpperBound) {
+__isl_give isl_set *polly::buildUnsignedConditionSets(
+    Scop &S, BasicBlock *BB, Value *Condition, __isl_keep isl_set *Domain,
+    const SCEV *SCEV_TestVal, const SCEV *SCEV_UpperBound,
   // Do not take NonNeg assumption on TestVal
   // as it might have MSB (Sign bit) set.
   isl_pw_aff *TestVal = getPwAff(S, BB, InvalidDomainMap, SCEV_TestVal, false);
   // Take NonNeg assumption on UpperBound.
   isl_pw_aff *UpperBound =
       getPwAff(S, BB, InvalidDomainMap, SCEV_UpperBound, true);
 
   // 0 <= TestVal
__isl_give isl_set *polly::buildUnsignedConditionSets(
   else
     // TestVal <= UpperBound
     Second = isl_pw_aff_le_set(TestVal, UpperBound);
 
   isl_set *ConsequenceCondSet = isl_set_intersect(First, Second);
   return ConsequenceCondSet;
 }
 
-/// Build the conditions sets for the branch condition @p Condition in
-/// the @p Domain.
-///
-/// This will fill @p ConditionSets with the conditions under which control
-/// will be moved from @p TI to its successors. Hence, @p ConditionSets will
-/// have as many elements as @p TI has successors. If @p TI is nullptr the
-/// context under which @p Condition is true/false will be returned as the
-/// new elements of @p ConditionSets.
-bool buildConditionSets(Scop &S, BasicBlock *BB, Value *Condition,
-                        Instruction *TI, Loop *L, __isl_keep isl_set *Domain,
-                        DenseMap<BasicBlock *, isl::set> &InvalidDomainMap,
-                        SmallVectorImpl<__isl_give isl_set *> &ConditionSets) {
+bool polly::buildConditionSets(
+    Scop &S, BasicBlock *BB, Value *Condition, Instruction *TI, Loop *L,
+    __isl_keep isl_set *Domain,
   ScalarEvolution &SE = *S.getSE();
   isl_set *ConsequenceCondSet = nullptr;
 
   if (auto Load = dyn_cast<LoadInst>(Condition)) {
     const SCEV *LHSSCEV = SE.getSCEVAtScope(Load, L);
     const SCEV *RHSSCEV = SE.getZero(LHSSCEV->getType());
     bool NonNeg = false;
     isl_pw_aff *LHS = getPwAff(S, BB, InvalidDomainMap, LHSSCEV, NonNeg);
bool polly::buildConditionSets(
   }
 
   ConditionSets.push_back(ConsequenceCondSet);
   ConditionSets.push_back(isl_set_coalesce(AlternativeCondSet));
 
   return true;
 }
 
-/// Build the conditions sets for the terminator @p TI in the @p Domain.
-///
-/// This will fill @p ConditionSets with the conditions under which control
-/// will be moved from @p TI to its successors. Hence, @p ConditionSets will
-/// have as many elements as @p TI has successors.
-bool buildConditionSets(Scop &S, BasicBlock *BB, Instruction *TI, Loop *L,
-                        __isl_keep isl_set *Domain,
-                        DenseMap<BasicBlock *, isl::set> &InvalidDomainMap,
-                        SmallVectorImpl<__isl_give isl_set *> &ConditionSets) {
+bool polly::buildConditionSets(
+    Scop &S, BasicBlock *BB, Instruction *TI, Loop *L,
   if (SwitchInst *SI = dyn_cast<SwitchInst>(TI))
     return buildConditionSets(S, BB, SI, L, Domain, InvalidDomainMap,
                               ConditionSets);
 
   assert(isa<BranchInst>(TI) && "Terminator was neither branch nor switch.");
 
   if (TI->getNumSuccessors() == 1) {
     ConditionSets.push_back(isl_set_copy(Domain));
isl::id Scop::getIdForParam(const SCEV *Parameter) const {
   Parameter = getRepresentingInvariantLoadSCEV(Parameter);
   return ParameterIds.lookup(Parameter);
 }
 
 bool Scop::isDominatedBy(const DominatorTree &DT, BasicBlock *BB) const {
   return DT.dominates(BB, getEntry());
 }
 
-void Scop::addUserAssumptions(
-    AssumptionCache &AC, DominatorTree &DT, LoopInfo &LI,
-    DenseMap<BasicBlock *, isl::set> &InvalidDomainMap) {
-  for (auto &Assumption : AC.assumptions()) {
-    auto *CI = dyn_cast_or_null<CallInst>(Assumption);
-    if (!CI || CI->getNumArgOperands() != 1)
-      continue;
-
-    bool InScop = contains(CI);
-    if (!InScop && !isDominatedBy(DT, CI->getParent()))
-      continue;
-
-    auto *L = LI.getLoopFor(CI->getParent());
-    auto *Val = CI->getArgOperand(0);
-    ParameterSetTy DetectedParams;
-    if (!isAffineConstraint(Val, &R, L, *SE, DetectedParams)) {
-      ORE.emit(
-          OptimizationRemarkAnalysis(DEBUG_TYPE, "IgnoreUserAssumption", CI)
-          << "Non-affine user assumption ignored.");
-      continue;
-    }
-
-    // Collect all newly introduced parameters.
-    ParameterSetTy NewParams;
-    for (auto *Param : DetectedParams) {
-      Param = extractConstantFactor(Param, *SE).second;
-      Param = getRepresentingInvariantLoadSCEV(Param);
-      if (Parameters.count(Param))
-        continue;
-      NewParams.insert(Param);
-    }
-
-    SmallVector<isl_set *, 2> ConditionSets;
-    auto *TI = InScop ? CI->getParent()->getTerminator() : nullptr;
-    BasicBlock *BB = InScop ? CI->getParent() : getRegion().getEntry();
-    auto *Dom = InScop ? DomainMap[BB].copy() : Context.copy();
-    assert(Dom && "Cannot propagate a nullptr.");
-    bool Valid = buildConditionSets(*this, BB, Val, TI, L, Dom,
-                                    InvalidDomainMap, ConditionSets);
-    isl_set_free(Dom);
-
-    if (!Valid)
-      continue;
-
-    isl_set *AssumptionCtx = nullptr;
-    if (InScop) {
-      AssumptionCtx = isl_set_complement(isl_set_params(ConditionSets[1]));
-      isl_set_free(ConditionSets[0]);
-    } else {
-      AssumptionCtx = isl_set_complement(ConditionSets[1]);
-      AssumptionCtx = isl_set_intersect(AssumptionCtx, ConditionSets[0]);
-    }
-
-    // Project out newly introduced parameters as they are not otherwise useful.
-    if (!NewParams.empty()) {
-      for (unsigned u = 0; u < isl_set_n_param(AssumptionCtx); u++) {
-        auto *Id = isl_set_get_dim_id(AssumptionCtx, isl_dim_param, u);
-        auto *Param = static_cast<const SCEV *>(isl_id_get_user(Id));
-        isl_id_free(Id);
-
-        if (!NewParams.count(Param))
-          continue;
-
-        AssumptionCtx =
-            isl_set_project_out(AssumptionCtx, isl_dim_param, u--, 1);
-      }
-    }
-    ORE.emit(OptimizationRemarkAnalysis(DEBUG_TYPE, "UserAssumption", CI)
-             << "Use user assumption: " << stringFromIslObj(AssumptionCtx));
-    Context = Context.intersect(isl::manage(AssumptionCtx));
-  }
-}
-
 void Scop::buildContext() {
   isl::space Space = isl::space::params_alloc(getIslCtx(), 0);
   Context = isl::set::universe(Space);
   InvalidContext = isl::set::empty(Space);
   AssumedContext = isl::set::universe(Space);
 }
 
 void Scop::addParameterBounds() {
if (R.getExit()) {
     ExitStr.str();
   } else
     ExitName = "FunctionExit";
 
   return std::make_pair(EntryName, ExitName);
 }
 
 isl::set Scop::getContext() const { return Context; }
+
 isl::space Scop::getParamSpace() const { return getContext().get_space(); }
 
 isl::space Scop::getFullParamSpace() const {
   std::vector<isl::id> FortranIDs;
   FortranIDs = getFortranArrayIds(arrays());
 
   isl::space Space = isl::space::params_alloc(
       getIslCtx(), ParameterIds.size() + FortranIDs.size());