[Polly][NFC][ScopBuilder] Move addRecordedAssumption to ScopBuilder

[domada]

Summary

Scope of changes:

1. Moved addRecordedAssumptions to ScopBuilder class.
2. Moved Assumption struct outside Scop class.
3. Refactored addRecordedAssumptions function. Replaced while loop by for_range loop.
4. Added function to clear processed Assumptions.

[domada]

1. Remove unused function.

[Meinersbur]

[suggestion] RecordedAssumptions itself is only used during SCoP constructions (since it's empty once the SCoP is full constructed). It could be removed entirely into ScopBuilder, maybe in a future patch?

polly/lib/Analysis/ScopBuilder.cpp

391 ↗

(On Diff #205689)

Please remove commented-out code entirely.

[domada]

1. Removed commented code
2. Renamed iterator range to RecordedAssumptions to recorded_assumptions

[domada]

Ok, I will move entirely RecordedAssumptions to ScopBuilder in a future patch.

[Meinersbur]

LGTM

polly/include/polly/ScopInfo.h

2344 ↗

(On Diff #206745)

[suggestion] Add const qualifier

2345 ↗

(On Diff #206745)

Why reverse iterator? The user could also use llvm::reverse

[domada]

polly/include/polly/ScopInfo.h

2345 ↗

(On Diff #206745)

I was not aware of llvm::reverse function.

I needed reverse iterator for refactored addRecordedAssumptions function. I will fix this issue. Should I update review request or can I fix it when I will commit?

[Meinersbur]

polly/include/polly/ScopInfo.h

2345 ↗

(On Diff #206745)

I do sometimes the diff with a "Update before commit (+ changes)" message; Phabricator 'complains' with a "Changed prior to commit:" line if it thinks the commit and the patch are not identical (but it's not reliable).

I'd say, update the review if you are unsure about how you resolved the pending comments, but it is not required.

[domada]

Applied @Meinersbur remarks.

[Meinersbur]

LGTM

polly/trunk/include/polly/ScopBuilder.h

class ScopBuilder {
   ///                      .phiops one. Required for values escaping through a
   ///                      PHINode in the SCoP region's exit block.
   /// @see addPHIReadAccess()
   /// @see MemoryKind
   void ensurePHIWrite(PHINode *PHI, ScopStmt *IncomintStmt,
                       BasicBlock *IncomingBlock, Value *IncomingValue,
                       bool IsExitBlock);
 
+  /// 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.
   ///
   /// @param PHIStmt Statement @p PHI resides in.
   /// @param PHI     PHINode under consideration; the READ access will be added

polly/trunk/include/polly/ScopInfo.h

#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
   /// Print the ScopStmt to stderr.
   void dump() const;
 #endif
 };
 
 /// Print ScopStmt S to raw_ostream OS.
 raw_ostream &operator<<(raw_ostream &OS, const ScopStmt &S);
 
+/// Helper struct to remember assumptions.
+struct Assumption {
+  /// The kind of the assumption (e.g., WRAPPING).
+  AssumptionKind Kind;
+
+  /// Flag to distinguish assumptions and restrictions.
+  AssumptionSign Sign;
+
+  /// The valid/invalid context if this is an assumption/restriction.
+  isl::set Set;
+
+  /// The location that caused this assumption.
+  DebugLoc Loc;
+
+  /// An optional block whose domain can simplify the assumption.
+  BasicBlock *BB;
+};
+
 /// 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:
   /// The restrictions under which this SCoP was built.
   ///
   /// The invalid context is similar to the assumed context as it contains
   /// constraints over the parameters. However, while we need the constraints
   /// in the assumed context to be "true" the constraints in the invalid context
   /// need to be "false". Otherwise they behave the same.
   isl::set InvalidContext;
 
-  /// Helper struct to remember assumptions.
-  struct Assumption {
-    /// The kind of the assumption (e.g., WRAPPING).
-    AssumptionKind Kind;
-
-    /// Flag to distinguish assumptions and restrictions.
-    AssumptionSign Sign;
-
-    /// The valid/invalid context if this is an assumption/restriction.
-    isl::set Set;
-
-    /// The location that caused this assumption.
-    DebugLoc Loc;
-
-    /// An optional block whose domain can simplify the assumption.
-    BasicBlock *BB;
-  };
-
+  using RecordedAssumptionsTy = SmallVector<Assumption, 8>;
   /// Collection to hold taken assumptions.
   ///
   /// There are two reasons why we want to record assumptions first before we
   /// add them to the assumed/invalid context:
   ///   1) If the SCoP is not profitable or otherwise invalid without the
   ///      assumed/invalid context we do not have to compute it.
   ///   2) Information about the context are gathered rather late in the SCoP
   ///      construction (basically after we know all parameters), thus the user
   ///      might see overly complicated assumptions to be taken while they will
   ///      only be simplified later on.
-  SmallVector<Assumption, 8> RecordedAssumptions;
+  RecordedAssumptionsTy RecordedAssumptions;
 
   /// The schedule of the SCoP
   ///
   /// The schedule of the SCoP describes the execution order of the statements
   /// in the scop by assigning each statement instance a possibly
   /// multi-dimensional execution time. The schedule is stored as a tree of
   /// schedule nodes.
   ///
public:
   }
 
   /// Return an iterator range containing invariant accesses.
   iterator_range<InvariantEquivClassesTy::iterator> invariantEquivClasses() {
     return make_range(InvariantEquivClasses.begin(),
                       InvariantEquivClasses.end());
   }
 
+  /// Return an iterator range containing hold assumptions.
+  iterator_range<RecordedAssumptionsTy::const_iterator>
+  recorded_assumptions() const {
+    return make_range(RecordedAssumptions.begin(), RecordedAssumptions.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;
public:
   /// Return true if the optimized SCoP can be executed.
   ///
   /// In addition to the runtime check context this will also utilize the domain
   /// constraints to decide it the optimized version can actually be executed.
   ///
   /// @returns True if the optimized SCoP can be executed.
   bool hasFeasibleRuntimeContext() const;
 
+  /// Clear assumptions which have been already processed.
+  void clearRecordedAssumptions() { return RecordedAssumptions.clear(); }
+
   /// Check if the assumption in @p Set is trivial or not.
   ///
   /// @param Set  The relations between parameters that are assumed to hold.
   /// @param Sign Enum to indicate if the assumptions in @p Set are positive
   ///             (needed/assumptions) or negative (invalid/restrictions).
   ///
   /// @returns True if the assumption @p Set is not trivial.
   bool isEffectiveAssumption(isl::set Set, AssumptionSign Sign);
public:
   ///             (needed/assumptions) or negative (invalid/restrictions).
   /// @param BB   The block in which this assumption was taken. If it is
   ///             set, the domain of that block will be used to simplify the
   ///             actual assumption in @p Set once it is added. This is useful
   ///             if the assumption was created prior to the domain.
   void recordAssumption(AssumptionKind Kind, isl::set Set, DebugLoc Loc,
                         AssumptionSign Sign, BasicBlock *BB = nullptr);
 
-  /// Add all recorded assumptions to the assumed context.
-  void addRecordedAssumptions();
-
   /// Mark the scop as invalid.
   ///
   /// This method adds an assumption to the scop that is always invalid. As a
   /// result, the scop will not be optimized later on. This function is commonly
   /// called when a condition makes it impossible (or too compile time
   /// expensive) to process this scop any further.
   ///
   /// @param Kind The assumption kind describing the underlying cause.

polly/trunk/lib/Analysis/ScopBuilder.cpp

if (!Descriptor)
     return nullptr;
 
   if (!isFortranArrayDescriptor(Descriptor))
     return nullptr;
 
   return Descriptor;
 }
 
+void ScopBuilder::addRecordedAssumptions() {
+  for (auto &AS : llvm::reverse(scop->recorded_assumptions())) {
+
+    if (!AS.BB) {
+      scop->addAssumption(AS.Kind, AS.Set, AS.Loc, AS.Sign,
+                          nullptr /* BasicBlock */);
+      continue;
+    }
+
+    // If the domain was deleted the assumptions are void.
+    isl_set *Dom = scop->getDomainConditions(AS.BB).release();
+    if (!Dom)
+      continue;
+
+    // If a basic block was given use its domain to simplify the assumption.
+    // In case of restrictions we know they only have to hold on the domain,
+    // thus we can intersect them with the domain of the block. However, for
+    // assumptions the domain has to imply them, thus:
+    //                     _              _____
+    //   Dom => S   <==>   A v B   <==>   A - B
+    //
+    // To avoid the complement we will register A - B as a restriction not an
+    // assumption.
+    isl_set *S = AS.Set.copy();
+    if (AS.Sign == AS_RESTRICTION)
+      S = isl_set_params(isl_set_intersect(S, Dom));
+    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();
+}
+
 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,
   scop->finalizeAccesses();
 
   scop->realignParams();
   scop->addUserContext();
 
   // After the context was fully constructed, thus all our knowledge about
   // the parameters is in there, we add all recorded assumptions to the
   // assumed/invalid context.
-  scop->addRecordedAssumptions();
+  addRecordedAssumptions();
 
   scop->simplifyContexts();
   if (!scop->buildAliasChecks(AA)) {
     LLVM_DEBUG(dbgs() << "Bailing-out because could not build alias checks\n");
     return;
   }
 
   hoistInvariantLoads();

polly/trunk/lib/Analysis/ScopInfo.cpp

 
 void Scop::recordAssumption(AssumptionKind Kind, isl::set Set, DebugLoc Loc,
                             AssumptionSign Sign, BasicBlock *BB) {
   assert((Set.is_params() || BB) &&
          "Assumptions without a basic block must be parameter sets");
   RecordedAssumptions.push_back({Kind, Sign, Set, Loc, BB});
 }
 
-void Scop::addRecordedAssumptions() {
-  while (!RecordedAssumptions.empty()) {
-    Assumption AS = RecordedAssumptions.pop_back_val();
-
-    if (!AS.BB) {
-      addAssumption(AS.Kind, AS.Set, AS.Loc, AS.Sign, nullptr /* BasicBlock */);
-      continue;
-    }
-
-    // If the domain was deleted the assumptions are void.
-    isl_set *Dom = getDomainConditions(AS.BB).release();
-    if (!Dom)
-      continue;
-
-    // If a basic block was given use its domain to simplify the assumption.
-    // In case of restrictions we know they only have to hold on the domain,
-    // thus we can intersect them with the domain of the block. However, for
-    // assumptions the domain has to imply them, thus:
-    //                     _              _____
-    //   Dom => S   <==>   A v B   <==>   A - B
-    //
-    // To avoid the complement we will register A - B as a restriction not an
-    // assumption.
-    isl_set *S = AS.Set.copy();
-    if (AS.Sign == AS_RESTRICTION)
-      S = isl_set_params(isl_set_intersect(S, Dom));
-    else /* (AS.Sign == AS_ASSUMPTION) */
-      S = isl_set_params(isl_set_subtract(Dom, S));
-
-    addAssumption(AS.Kind, isl::manage(S), AS.Loc, AS_RESTRICTION, AS.BB);
-  }
-}
-
 void Scop::invalidate(AssumptionKind Kind, DebugLoc Loc, BasicBlock *BB) {
   LLVM_DEBUG(dbgs() << "Invalidate SCoP because of reason " << Kind << "\n");
   addAssumption(Kind, isl::set::empty(getParamSpace()), Loc, AS_ASSUMPTION, BB);
 }
 
 isl::set Scop::getInvalidContext() const { return InvalidContext; }
 
 void Scop::printContext(raw_ostream &OS) const {