[Polly][NFC][ScopBuilder] Move RecordedAssumptions vector to ScopBuilder.

[domada]

Summary

Scope of changes:

1. Moved RecordedAssumptions vector to ScopBuilder. RecordedAssumptions are used only for Scop constructions.
2. Moved definition of RecordedAssumptionsTy to ScopHelper. It is required both by ScopBuilder and SCEVAffinator.
3. Add new function recordAssumption to ScopHelper. One of its argument is a reference to RecordedAssumption vector. This function is used by ScopBuilder and SCEVAffinator.
4. All RecordedAssumptions are created by ScopBuilder. isl::pw_aff objects for corresponding SCEVs are created inside ScopBuilder. Scop functions do not record any assumptions. Scop can use isl::pw_aff objects which were created by ScopBuilder.
5. Removed functions for handling RecordedAssumptions from Scop class.
6. Removed constness from getScopArrayInfo functions.
7. Replaced SCEVVisitor struct from SCEVAffinator with taylored version, which allow to pass pointer to RecordedAssumptions as function argument.

[Meinersbur]

Nice one.

polly/lib/Analysis/ScopBuilder.cpp

1494–1495

[style] llvm::reverse(RecordedAssumptions) should work as well.

1523–1524

[suggestion] Now that RecordedAssumptions is part of ScopBuilder, it will be freed together with ScopBuilder, so explicitly clearing it should not be necessary.

polly/lib/Analysis/ScopInfo.cpp

700–701

Nice to have this moved out of MemoryAccess

1353

Is this an intentional change? Depending on the iteration order over basic blocks, the value might be used before its write is seem, in which case we'd need getOrCreateScopArrayInfo.

1694

The RecordedAssumptions stored inside ScopBuilder has a shorter lifetime than the Affinator stored inside this Scop object. Meaning that any use of Affinator after the destruction of ScopBuilder will lead to a use-after-free error. It should not happen since adding an assumption after the Scop has been constructed will have no effect. Now new assumptions should be detectable using Valgrind/AddressSanitizer, which might be a good thing, but the potential memory corruption worries me.

Do you have any plans how to ensure no use-after-free happens? E.g. set the RecordedAssumption to nullptr after the Scop has been built. We might even work on even moving the Affinator into ScopBuilder. I would at least appreciate a comment in the code explaining this.

polly/lib/Support/ScopHelper.cpp

155–162

[serious] The comment above applies to simplifyRegion, not recordAssumption.

[domada]

polly/lib/Analysis/ScopInfo.cpp

1808

This function is still used in polly/lib/CodeGen/PPCGCodeGeneration.cpp file. That's why I haven't moved it to ScopBuilder.

[domada]

polly/lib/Analysis/ScopInfo.cpp

1353

Yes, it was an intentional change. I wanted to move getOrCreateScopArrayInfo to ScopBuilder. Currently this function is used in lib/CodeGen/PPCGCodeGeneration.cpp and in ScopBuilder. That's why I haven't moved it in this patch. I need to rethink this change.

1694

Thank you for your comment. Initially I will set RecordedAssumption to nullptr. Finally I will try to move Affinator into ScopBuilder. I think that it should be the most elegant way.

[domada]

1. Reworked mechanism of collecting assumptions. All assumptions are now taken inside ScopBuilder.
2. Internal functions of Scop class do not record any assumption. They use cached isl::pw_aff objects which are created by ScopBuilder.

[domada]

polly/lib/Analysis/ScopInfo.cpp

1694

Initial change is reverted.

[Meinersbur]

Could you upload the nest diff with context (git diff -U999999)?

polly/include/polly/ScopBuilder.h

74

[style] RecordedAssumptionsTy RecordedAssumptions = nullptr preferable over initializer in the ctor.

polly/lib/Analysis/ScopBuilder.cpp

3230

[style] No Almost Always Auto: for (const SCEV *Size: Access->Sizes)

[style] Variable start with upper cases.

3241

[style] No Almost Always Auto: for (const SCEV *Subscript : Access->Subscripts)

[suggestion] Access using a getter might be preferable

3799

[suggestion] Clearing may not be necessary.

polly/lib/Support/SCEVAffinator.cpp

120

[serious] Assigning the field in one of the methods instead of in the ctor makes the lifetime issue even worse. Is there a reason not to pass RecordedAssumptions by function arguments?

[domada]

Uploaded the same changes with the more context: git format-patch -U999999 HEAD~1

[domada]

polly/lib/Support/SCEVAffinator.cpp

120

Some RecordedAssumptions are added inside visit and other visit_type_of_scev functions functions (for example visitTruncateExpr ). visit function and other visit_type_of_scev functions are part of` llvm::SCEVVisitor` struct. I cannot modify number of parameters for these functions, because they are part of LLVM infrastructure.

That's why I am trying to add pointer of RecordedAssumption vector to SCEVAffinator. This pointer is visible inside all functions inside SCEVAffinator class and I don't need to pass it as function argument.

I am wondering if it is worth to split SCEVAffinator into two classes? The first class will be responsible only for delivering PWACtx, and the second will be responsible for recording assumptions. The class for collecting assumptions will be instantiated only in ScopBuilder so the problem with object lifetime will be solved. The drawback of this approach is duplicated traversing of some SCEVs.

[Meinersbur]

LGTM. Please consider the [style] remarks as well before committing.

Thanks for the effort.

polly/lib/Support/SCEVAffinator.cpp

120

I see, thanks for the explanation.

For the [[ https://github.com/llvm/llvm-project/blob/master/polly/lib/Transform/ScheduleTreeTransform.cpp#L25 | ScheduleTreeVisitor ]] my solution was to implement visitor methods with variadic arguments, so you actually can pass additional parameters.

But I also think any workaround will be overkill for now and we just use the solution already done for BB.

[domada]

This patch implements individual version of SCEVVisitor. Taylored version of SCEVVisitor is required to pass pointer to RecordedAssumptions to visit_type_scev functions.

Please let me know if you prefer this solution or the previous one.

Before commit I will also fix style remarks.

[domada]

polly/lib/Support/SCEVAffinator.cpp

120

I have implemented something similar to ScheduleTreeVisitor, please look at function visitSCEV and please express your opinion.

On one hand implementation of own SCEVVisitor resolves problem of lifetime issue, but on the other hand I have created more code which is to some extent redundant to LLVM code.

polly/include/polly/ScopBuilder.h

class ScopBuilder {
   SmallVector<std::pair<ScopStmt *, Instruction *>, 16> GlobalReads;
 
   /// Set of all accessed array base pointers.
   SmallSetVector<Value *, 16> ArrayBasePointers;
 
   // The Scop
   std::unique_ptr<Scop> scop;
 
+  /// 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.
+  RecordedAssumptionsTy RecordedAssumptions;
+
   // Methods for pattern matching against Fortran code generated by dragonegg.
   // @{
 
   /// Try to match for the descriptor of a Fortran array whose allocation
   /// is not visible. That is, we can see the load/store into the memory, but
   /// we don't actually know where the memory is allocated. If ALLOCATE had been
   /// called on the Fortran array, then we will see the lowered malloc() call.
   /// If not, this is dubbed as an "invisible allocation".

polly/include/polly/ScopInfo.h

 //
 //===----------------------------------------------------------------------===//
 
 #ifndef POLLY_SCOPINFO_H
 #define POLLY_SCOPINFO_H
 
 #include "polly/ScopDetection.h"
 #include "polly/Support/SCEVAffinator.h"
+#include "polly/Support/ScopHelper.h"
 #include "llvm/ADT/ArrayRef.h"
 #include "llvm/ADT/MapVector.h"
 #include "llvm/ADT/SetVector.h"
 #include "llvm/Analysis/RegionPass.h"
 #include "llvm/IR/DebugLoc.h"
 #include "llvm/IR/Instruction.h"
 #include "llvm/IR/Instructions.h"
 #include "llvm/IR/PassManager.h"

 
 extern bool UseInstructionNames;
 
 // The maximal number of basic sets we allow during domain construction to
 // be created. More complex scops will result in very high compile time and
 // are also unlikely to result in good code.
 extern int const MaxDisjunctsInDomain;
 
-/// Enumeration of assumptions Polly can take.
-enum AssumptionKind {
-  ALIASING,
-  INBOUNDS,
-  WRAPPING,
-  UNSIGNED,
-  PROFITABLE,
-  ERRORBLOCK,
-  COMPLEXITY,
-  INFINITELOOP,
-  INVARIANTLOAD,
-  DELINEARIZATION,
-};
-
-/// Enum to distinguish between assumptions and restrictions.
-enum AssumptionSign { AS_ASSUMPTION, AS_RESTRICTION };
-
 /// The different memory kinds used in Polly.
 ///
 /// We distinguish between arrays and various scalar memory objects. We use
 /// the term ``array'' to describe memory objects that consist of a set of
 /// individual data elements arranged in a multi-dimensional grid. A scalar
 /// memory object describes an individual data element and is used to model
 /// the definition and uses of llvm::Values.
 ///
enum ReductionType {
     RT_NONE, ///< Indicate no reduction at all
     RT_ADD,  ///< Addition
     RT_MUL,  ///< Multiplication
     RT_BOR,  ///< Bitwise Or
     RT_BXOR, ///< Bitwise XOr
     RT_BAND, ///< Bitwise And
   };
 
+  using SubscriptsTy = SmallVector<const SCEV *, 4>;
+
 private:
   /// A unique identifier for this memory access.
   ///
   /// The identifier is unique between all memory accesses belonging to the same
   /// scop statement.
   isl::id Id;
 
   /// What is modeled by this MemoryAccess.
private:
   ///    PHI node itself (for both, READ and WRITE accesses).
   ///
   AssertingVH<Value> AccessValue;
 
   /// Are all the subscripts affine expression?
   bool IsAffine = true;
 
   /// Subscript expression for each dimension.
-  SmallVector<const SCEV *, 4> Subscripts;
+  SubscriptsTy Subscripts;
 
   /// Relation from statement instances to the accessed array elements.
   ///
   /// In the common case this relation is a function that maps a set of loop
   /// indices to the memory address from which a value is loaded/stored:
   ///
   ///      for i
   ///        for j
private:
   /// along with auxiliary fields with information such as dimensions.
   /// We hold a reference to the descriptor corresponding to a MemoryAccess
   /// into a Fortran array. FAD for "Fortran Array Descriptor"
   AssertingVH<Value> FAD;
   // @}
 
   isl::basic_map createBasicAccessMap(ScopStmt *Statement);
 
-  void assumeNoOutOfBound();
+  isl::set assumeNoOutOfBound();
 
   /// Compute bounds on an over approximated  access relation.
   ///
   /// @param ElementSize The size of one element accessed.
   void computeBoundsOnAccessRelation(unsigned ElementSize);
 
   /// Get the original access function as read from IR.
   isl::map getOriginalAccessRelation() const;
if (isAnyPHIKind()) {
       return nullptr;
     }
     return AccessValue;
   }
 
   /// Return the access instruction of this memory access.
   Instruction *getAccessInstruction() const { return AccessInstruction; }
 
+  ///  Return an iterator range containing the subscripts.
+  iterator_range<SubscriptsTy::const_iterator> subscripts() const {
+    return make_range(Subscripts.begin(), Subscripts.end());
+  }
+
   /// Return the number of access function subscript.
   unsigned getNumSubscripts() const { return Subscripts.size(); }
 
   /// Return the access function subscript in the dimension @p Dim.
   const SCEV *getSubscript(unsigned Dim) const { return Subscripts[Dim]; }
 
   /// Compute the isl representation for the SCEV @p E wrt. this access.
   ///
#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;
-};
-
 /// 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.
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;
 
-  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.
-  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.
   ///
   /// The most common nodes in a schedule tree are so-called band nodes. Band
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 an iterator range containing all the MemoryAccess objects of the
   /// Scop.
   iterator_range<AccFuncVector::iterator> access_functions() {
     return make_range(AccessFunctions.begin(), AccessFunctions.end());
   }
 
   /// Return whether this scop is empty, i.e. contains no statements that
   /// could be executed.
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:
   /// @param Loc  The location in the source that caused this assumption.
   /// @param Sign Enum to indicate if the assumptions in @p Set are positive
   ///             (needed/assumptions) or negative (invalid/restrictions).
   /// @param BB   The block in which this assumption was taken. Used to
   ///             calculate hotness when emitting remark.
   void addAssumption(AssumptionKind Kind, isl::set Set, DebugLoc Loc,
                      AssumptionSign Sign, BasicBlock *BB);
 
-  /// Record an assumption for later addition to the assumed context.
-  ///
-  /// This function will add the assumption to the RecordedAssumptions. This
-  /// collection will be added (@see addAssumption) to the assumed context once
-  /// all paramaters are known and the context is fully built.
-  ///
-  /// @param Kind The assumption kind describing the underlying cause.
-  /// @param Set  The relations between parameters that are assumed to hold.
-  /// @param Loc  The location in the source that caused this assumption.
-  /// @param Sign Enum to indicate if the assumptions in @p Set are positive
-  ///             (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);
-
   /// 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.
public:
 
   /// Return the cached ScopArrayInfo object for @p BasePtr.
   ///
   /// @param BasePtr   The base pointer the object has been stored for.
   /// @param Kind      The kind of array info object.
   ///
   /// @returns The ScopArrayInfo pointer or NULL if no such pointer is
   ///          available.
-  const ScopArrayInfo *getScopArrayInfoOrNull(Value *BasePtr, MemoryKind Kind);
+  ScopArrayInfo *getScopArrayInfoOrNull(Value *BasePtr, MemoryKind Kind);
 
   /// Return the cached ScopArrayInfo object for @p BasePtr.
   ///
   /// @param BasePtr   The base pointer the object has been stored for.
   /// @param Kind      The kind of array info object.
   ///
   /// @returns The ScopArrayInfo pointer (may assert if no such pointer is
   ///          available).
-  const ScopArrayInfo *getScopArrayInfo(Value *BasePtr, MemoryKind Kind);
+  ScopArrayInfo *getScopArrayInfo(Value *BasePtr, MemoryKind Kind);
 
   /// Invalidate ScopArrayInfo object for base address.
   ///
   /// @param BasePtr The base pointer of the ScopArrayInfo object to invalidate.
   /// @param Kind    The Kind of the ScopArrayInfo object.
   void invalidateScopArrayInfo(Value *BasePtr, MemoryKind Kind) {
     auto It = ScopArrayInfoMap.find(std::make_pair(BasePtr, Kind));
     if (It == ScopArrayInfoMap.end())
#endif
   ///           passed without a @p BB.
   /// @param NonNegative Flag to indicate the @p E has to be non-negative.
   ///
   /// Note that this function will always return a valid isl_pw_aff. However, if
   /// the translation of @p E was deemed to complex the SCoP is invalidated and
   /// a dummy value of appropriate dimension is returned. This allows to bail
   /// for complex cases without "error handling code" needed on the users side.
   PWACtx getPwAff(const SCEV *E, BasicBlock *BB = nullptr,
-                  bool NonNegative = false);
+                  bool NonNegative = false,
+                  RecordedAssumptionsTy *RecordedAssumptions = nullptr);
 
   /// Compute the isl representation for the SCEV @p E
   ///
   /// This function is like @see Scop::getPwAff() but strips away the invalid
   /// domain part associated with the piecewise affine function.
-  isl::pw_aff getPwAffOnly(const SCEV *E, BasicBlock *BB = nullptr);
+  isl::pw_aff
+  getPwAffOnly(const SCEV *E, BasicBlock *BB = nullptr,
+               RecordedAssumptionsTy *RecordedAssumptions = nullptr);
 
   /// Check if an <nsw> AddRec for the loop L is cached.
   bool hasNSWAddRecForLoop(Loop *L) { return Affinator.hasNSWAddRecForLoop(L); }
 
   /// Return the domain of @p Stmt.
   ///
   /// @param Stmt The statement for which the conditions should be returned.
   isl::set getDomainConditions(const ScopStmt *Stmt) const;

polly/include/polly/Support/SCEVAffinator.h

 //===------ polly/SCEVAffinator.h - Create isl expressions from SCEVs -----===//
 //
 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
 // See https://llvm.org/LICENSE.txt for license information.
 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
 //
 //===----------------------------------------------------------------------===//
 //
 // Create a polyhedral description for a SCEV value.
 //
 //===----------------------------------------------------------------------===//
 
 #ifndef POLLY_SCEV_AFFINATOR_H
 #define POLLY_SCEV_AFFINATOR_H
 
+#include "polly/Support/ScopHelper.h"
 #include "llvm/Analysis/ScalarEvolutionExpressions.h"
 #include "isl/isl-noexceptions.h"
 
 namespace polly {
 class Scop;
 
 /// The result type of the SCEVAffinator.
 ///
 /// The first element of the pair is the isl representation of the SCEV, the
 /// second is the domain under which it is __invalid__.
 typedef std::pair<isl::pw_aff, isl::set> PWACtx;
 
 /// Translate a SCEV to an isl::pw_aff and the domain on which it is invalid.
 struct SCEVAffinator : public llvm::SCEVVisitor<SCEVAffinator, PWACtx> {
 public:
   SCEVAffinator(Scop *S, llvm::LoopInfo &LI);
 
   /// Translate a SCEV to an isl::pw_aff.
   ///
   /// @param E  he expression that is translated.
   /// @param BB The block in which @p E is executed.
   ///
   /// @returns The isl representation of the SCEV @p E in @p Domain.
-  PWACtx getPwAff(const llvm::SCEV *E, llvm::BasicBlock *BB = nullptr);
+  PWACtx getPwAff(const llvm::SCEV *E, llvm::BasicBlock *BB = nullptr,
+                  RecordedAssumptionsTy *RecordedAssumptions = nullptr);
 
   /// Take the assumption that @p PWAC is non-negative.
-  void takeNonNegativeAssumption(PWACtx &PWAC);
+  void takeNonNegativeAssumption(
+      PWACtx &PWAC, RecordedAssumptionsTy *RecordedAssumptions = nullptr);
 
   /// Interpret the PWA in @p PWAC as an unsigned value.
   void interpretAsUnsigned(PWACtx &PWAC, unsigned Width);
 
   /// Check an <nsw> AddRec for the loop @p L is cached.
   bool hasNSWAddRecForLoop(llvm::Loop *L) const;
 
   /// Return the LoopInfo used by thi object.
   llvm::LoopInfo *getLI() const { return &LI; }
 
 private:
   /// Key to identify cached expressions.
   using CacheKey = std::pair<const llvm::SCEV *, llvm::BasicBlock *>;
 
   /// Map to remembered cached expressions.
   llvm::DenseMap<CacheKey, PWACtx> CachedExpressions;
 
   Scop *S;
   isl::ctx Ctx;
   unsigned NumIterators;
   llvm::ScalarEvolution &SE;
   llvm::LoopInfo &LI;
   llvm::BasicBlock *BB;
+  RecordedAssumptionsTy *RecordedAssumptions = nullptr;
 
   /// Target data for element size computing.
   const llvm::DataLayout &TD;
 
   /// Return the loop for the current block if any.
   llvm::Loop *getScope();
 
   /// Return a PWACtx for @p PWA that is always valid.

polly/include/polly/Support/ScopHelper.h

 
 #ifndef POLLY_SUPPORT_IRHELPER_H
 #define POLLY_SUPPORT_IRHELPER_H
 
 #include "llvm/ADT/SetVector.h"
 #include "llvm/IR/Instructions.h"
 #include "llvm/IR/IntrinsicInst.h"
 #include "llvm/IR/ValueHandle.h"
+#include "isl/isl-noexceptions.h"
 
 namespace llvm {
 class LoopInfo;
 class Loop;
 class ScalarEvolution;
 class SCEV;
 class Region;
 class Pass;
 class DominatorTree;
 class RegionInfo;
 class RegionNode;
 } // namespace llvm
 
 namespace polly {
 class Scop;
 class ScopStmt;
 
+/// Enumeration of assumptions Polly can take.
+enum AssumptionKind {
+  ALIASING,
+  INBOUNDS,
+  WRAPPING,
+  UNSIGNED,
+  PROFITABLE,
+  ERRORBLOCK,
+  COMPLEXITY,
+  INFINITELOOP,
+  INVARIANTLOAD,
+  DELINEARIZATION,
+};
+
+/// Enum to distinguish between assumptions and restrictions.
+enum AssumptionSign { AS_ASSUMPTION, AS_RESTRICTION };
+
+/// 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.
+  llvm::DebugLoc Loc;
+
+  /// An optional block whose domain can simplify the assumption.
+  llvm::BasicBlock *BB;
+};
+
+using RecordedAssumptionsTy = llvm::SmallVector<Assumption, 8>;
+
+/// Record an assumption for later addition to the assumed context.
+///
+/// This function will add the assumption to the RecordedAssumptions. This
+/// collection will be added (@see addAssumption) to the assumed context once
+/// all paramaters are known and the context is fully built.
+///
+/// @param RecordedAssumption container which keeps all recorded assumptions.
+/// @param Kind The assumption kind describing the underlying cause.
+/// @param Set  The relations between parameters that are assumed to hold.
+/// @param Loc  The location in the source that caused this assumption.
+/// @param Sign Enum to indicate if the assumptions in @p Set are positive
+///             (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(RecordedAssumptionsTy *RecordedAssumptions,
+                      AssumptionKind Kind, isl::set Set, llvm::DebugLoc Loc,
+                      AssumptionSign Sign, llvm::BasicBlock *BB = nullptr);
+
 /// Type to remap values.
 using ValueMapT = llvm::DenseMap<llvm::AssertingVH<llvm::Value>,
                                  llvm::AssertingVH<llvm::Value>>;
 
 /// Type for a set of invariant loads.
 using InvariantLoadsSetTy = llvm::SetVector<llvm::AssertingVH<llvm::LoadInst>>;
 
 /// Set type for parameters.

polly/lib/Analysis/ScopBuilder.cpp

static cl::opt<bool> PollyAllowDereferenceOfAllFunctionParams(
     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>
+    PollyIgnoreInbounds("polly-ignore-inbounds",
+                        cl::desc("Do not take inbounds assumptions at all"),
+                        cl::Hidden, cl::init(false), cl::cat(PollyCategory));
+
 static cl::opt<unsigned> RunTimeChecksMaxArraysPerGroup(
     "polly-rtc-max-arrays-per-group",
     cl::desc("The maximal number of arrays to compare in each alias group."),
     cl::Hidden, cl::ZeroOrMore, cl::init(20), cl::cat(PollyCategory));
 
 static cl::opt<int> RunTimeChecksMaxAccessDisjuncts(
     "polly-rtc-max-array-disjuncts",
     cl::desc("The maximal number of disjunts allowed in memory accesses to "

 /// @param NonNegative      Flag to indicate the @p E has to be non-negative.
 ///
 /// Note that this function will also adjust the invalid context accordingly.
 
 __isl_give isl_pw_aff *
 ScopBuilder::getPwAff(BasicBlock *BB,
                       DenseMap<BasicBlock *, isl::set> &InvalidDomainMap,
                       const SCEV *E, bool NonNegative) {
-  PWACtx PWAC = scop->getPwAff(E, BB, NonNegative);
+  PWACtx PWAC = scop->getPwAff(E, BB, NonNegative, &RecordedAssumptions);
   InvalidDomainMap[BB] = InvalidDomainMap[BB].unite(PWAC.second);
   return PWAC.first.release();
 }
 
 /// 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.
bool ScopBuilder::addLoopBoundsToHeaderDomain(
 
   // Check if there is a <nsw> tagged AddRec for this loop and if so do not add
   // the bounded assumptions to the context as they are already implied by the
   // <nsw> tag.
   if (scop->hasNSWAddRecForLoop(L))
     return true;
 
   isl::set UnboundedCtx = Parts.first.params();
-  scop->recordAssumption(INFINITELOOP, UnboundedCtx,
-                         HeaderBB->getTerminator()->getDebugLoc(),
-                         AS_RESTRICTION);
+  recordAssumption(&RecordedAssumptions, INFINITELOOP, UnboundedCtx,
+                   HeaderBB->getTerminator()->getDebugLoc(), AS_RESTRICTION);
   return true;
 }
 
 void ScopBuilder::buildInvariantEquivalenceClasses() {
   DenseMap<std::pair<const SCEV *, Type *>, LoadInst *> EquivClasses;
 
   const InvariantLoadsSetTy &RIL = scop->getRequiredInvariantLoads();
   for (LoadInst *LInst : RIL) {
for (auto *RN : RTraversal) {
 
     bool IsInvalidBlock = ContainsErrorBlock || Domain.is_subset(InvalidDomain);
 
     if (!IsInvalidBlock) {
       InvalidDomain = InvalidDomain.intersect(Domain);
     } else {
       InvalidDomain = Domain;
       isl::set DomPar = Domain.params();
-      scop->recordAssumption(ERRORBLOCK, DomPar,
-                             BB->getTerminator()->getDebugLoc(),
-                             AS_RESTRICTION);
+      recordAssumption(&RecordedAssumptions, ERRORBLOCK, DomPar,
+                       BB->getTerminator()->getDebugLoc(), AS_RESTRICTION);
       Domain = isl::set::empty(Domain.get_space());
     }
 
     if (InvalidDomain.is_empty()) {
       InvalidDomainMap[BB] = InvalidDomain;
       continue;
     }
 
Value *ScopBuilder::findFADAllocationInvisible(MemAccInst Inst) {
 
   if (!isFortranArrayDescriptor(Descriptor))
     return nullptr;
 
   return Descriptor;
 }
 
 void ScopBuilder::addRecordedAssumptions() {
-  for (auto &AS : llvm::reverse(scop->recorded_assumptions())) {
+  for (auto &AS : llvm::reverse(RecordedAssumptions)) {
 
     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();
for (auto &AS : llvm::reverse(RecordedAssumptions)) {
     // 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();
 }
 
 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;
 

 
 void ScopBuilder::foldAccessRelations() {
   for (auto &Stmt : *scop)
     for (auto &Access : Stmt)
       Access->foldAccessRelation();
 }
 
 void ScopBuilder::assumeNoOutOfBounds() {
+  if (PollyIgnoreInbounds)
+    return;
   for (auto &Stmt : *scop)
-    for (auto &Access : Stmt)
-      Access->assumeNoOutOfBound();
+    for (auto &Access : Stmt) {
+      isl::set Outside = Access->assumeNoOutOfBound();
+      const auto &Loc = Access->getAccessInstruction()
+                            ? Access->getAccessInstruction()->getDebugLoc()
+                            : DebugLoc();
+      recordAssumption(&RecordedAssumptions, INBOUNDS, Outside, Loc,
+                       AS_ASSUMPTION);
+    }
 }
 
 void ScopBuilder::ensureValueWrite(Instruction *Inst) {
   // Find the statement that defines the value of Inst. That statement has to
   // write the value to make it available to those statements that read it.
   ScopStmt *Stmt = scop->getStmtFor(Inst);
 
   // It is possible that the value is synthesizable within a loop (such that it
bool ScopBuilder::canAlwaysBeHoisted(MemoryAccess *MA,
   // 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)))
+  for (const SCEV *Subscript : MA->subscripts())
+    if (!isa<SCEVConstant>(Subscript))
       return false;
   return true;
 }
 
 void ScopBuilder::addInvariantLoads(ScopStmt &Stmt,
                                     InvariantAccessesTy &InvMAs) {
   if (InvMAs.empty())
     return;
if (Access->isPHIKind())
       Ty = MemoryKind::PHI;
     else if (Access->isExitPHIKind())
       Ty = MemoryKind::ExitPHI;
     else if (Access->isValueKind())
       Ty = MemoryKind::Value;
     else
       Ty = MemoryKind::Array;
 
+    // Create isl::pw_aff for SCEVs which describe sizes. Collect all
+    // assumptions which are taken. isl::pw_aff objects are cached internally
+    // and they are used later by scop.
+    for (const SCEV *Size : Access->Sizes) {
+      if (!Size)
+        continue;
+      scop->getPwAff(Size, nullptr, false, &RecordedAssumptions);
+    }
     auto *SAI = scop->getOrCreateScopArrayInfo(Access->getOriginalBaseAddr(),
                                                ElementType, Access->Sizes, Ty);
+
+    // Create isl::pw_aff for SCEVs which describe subscripts. Collect all
+    // assumptions which are taken. isl::pw_aff objects are cached internally
+    // and they are used later by scop.
+    for (const SCEV *Subscript : Access->subscripts()) {
+      if (!Access->isAffine() || !Subscript)
+        continue;
+      scop->getPwAff(Subscript, Stmt.getEntryBlock(), false,
+                     &RecordedAssumptions);
+    }
     Access->buildAccessRelation(SAI);
     scop->addAccessData(Access);
   }
 }
 
 /// Add the minimal/maximal access in @p Set to @p User.
 ///
 /// @return True if more accesses should be added, false if we reached the
ScopBuilder::ScopBuilder(Region *R, AssumptionCache &AC, AliasAnalysis &AA,
   buildScop(*R, AC);
 
   LLVM_DEBUG(dbgs() << *scop);
 
   if (!scop->hasFeasibleRuntimeContext()) {
     InfeasibleScops++;
     Msg = "SCoP ends here but was dismissed.";
     LLVM_DEBUG(dbgs() << "SCoP detected but dismissed\n");
+    RecordedAssumptions.clear();
     scop.reset();
   } else {
     Msg = "SCoP ends here.";
     ++ScopFound;
     if (scop->getMaxLoopDepth() > 0)
       ++RichScopFound;
   }
 
   if (R->isTopLevelRegion())
     ORE.emit(OptimizationRemarkAnalysis(DEBUG_TYPE, "ScopEnd", End, P.first)
              << Msg);
   else
     ORE.emit(OptimizationRemarkAnalysis(DEBUG_TYPE, "ScopEnd", End, P.second)
              << Msg);
 }

polly/lib/Analysis/ScopInfo.cpp

IslOnErrorAbort("polly-on-isl-error-abort",
                     cl::desc("Abort if an isl error is encountered"),
                     cl::init(true), cl::cat(PollyCategory));
 
 static cl::opt<bool> PollyPreciseInbounds(
     "polly-precise-inbounds",
     cl::desc("Take more precise inbounds assumptions (do not scale well)"),
     cl::Hidden, cl::init(false), cl::cat(PollyCategory));
 
-static cl::opt<bool>
-    PollyIgnoreInbounds("polly-ignore-inbounds",
-                        cl::desc("Do not take inbounds assumptions at all"),
-                        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> PollyPreciseFoldAccesses(
     "polly-precise-fold-accesses",

 // then apply the reverse access relation to obtain the set of iterations that
 // may contain invalid accesses and reduce this set of iterations to the ones
 // that are actually executed by intersecting them with the domain of the
 // statement. If we now project out all loop dimensions, we obtain a set of
 // parameters that may cause statement instances to be executed that may
 // possibly yield out of bound memory accesses. The complement of these
 // constraints is the set of constraints that needs to be assumed to ensure such
 // statement instances are never executed.
-void MemoryAccess::assumeNoOutOfBound() {
-  if (PollyIgnoreInbounds)
-    return;
+isl::set MemoryAccess::assumeNoOutOfBound() {
   auto *SAI = getScopArrayInfo();
   isl::space Space = getOriginalAccessRelationSpace().range();
   isl::set Outside = isl::set::empty(Space);
   for (int i = 1, Size = Space.dim(isl::dim::set); i < Size; ++i) {
     isl::local_space LS(Space);
     isl::pw_aff Var = isl::pw_aff::var_on_domain(LS, isl::dim::set, i);
     isl::pw_aff Zero = isl::pw_aff(LS);
 
isl::set MemoryAccess::assumeNoOutOfBound() {
   Outside = Outside.params();
 
   // Remove divs to avoid the construction of overly complicated assumptions.
   // Doing so increases the set of parameter combinations that are assumed to
   // not appear. This is always save, but may make the resulting run-time check
   // bail out more often than strictly necessary.
   Outside = Outside.remove_divs();
   Outside = Outside.complement();
-  const auto &Loc = getAccessInstruction()
-                        ? getAccessInstruction()->getDebugLoc()
-                        : DebugLoc();
+
   if (!PollyPreciseInbounds)
     Outside = Outside.gist_params(Statement->getDomain().params());
-  Statement->getParent()->recordAssumption(INBOUNDS, Outside, Loc,
-                                           AS_ASSUMPTION);
+  return Outside;
 }
 
 void MemoryAccess::buildMemIntrinsicAccessRelation() {
   assert(isMemoryIntrinsic());
   assert(Subscripts.size() == 2 && Sizes.size() == 1);
 
   isl::pw_aff SubscriptPWA = getPwAff(Subscripts[0]);
   isl::map SubscriptMap = isl::map::from_pw_aff(SubscriptPWA);

 }
 
 MemoryAccess *ScopStmt::ensureValueRead(Value *V) {
   MemoryAccess *Access = lookupInputAccessOf(V);
   if (Access)
     return Access;
 
   ScopArrayInfo *SAI =
       Parent.getOrCreateScopArrayInfo(V, V->getType(), {}, MemoryKind::Value);
   Access = new MemoryAccess(this, nullptr, MemoryAccess::READ, V, V->getType(),
                             true, {}, {}, V, MemoryKind::Value);
   Parent.addAccessFunction(Access);
   Access->buildAccessRelation(SAI);
   addAccess(Access);
   Parent.addAccessData(Access);
   return Access;
 }
int Scop::getNextID(std::string ParentFunc) {
   return NextScopID++;
 }
 
 Scop::Scop(Region &R, ScalarEvolution &ScalarEvolution, LoopInfo &LI,
            DominatorTree &DT, ScopDetection::DetectionContext &DC,
            OptimizationRemarkEmitter &ORE)
     : IslCtx(isl_ctx_alloc(), isl_ctx_free), SE(&ScalarEvolution), DT(&DT),
       R(R), name(None), HasSingleExitEdge(R.getExitingBlock()), DC(DC),
       ORE(ORE), Affinator(this, LI),
       ID(getNextID((*R.getEntry()->getParent()).getName().str())) {
   if (IslOnErrorAbort)
     isl_options_set_on_error(getIslCtx().get(), ISL_ON_ERROR_ABORT);
   buildContext();
 }
 
 Scop::~Scop() = default;
 
for (auto &IAClass : InvariantEquivClasses) {
     for (auto *MA : MAs)
       if (MA->getAccessInstruction() == Val)
         return &IAClass;
   }
 
   return nullptr;
 }
 
 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)]
                       : ScopArrayNameMap[BaseName];
for (auto size : Sizes)
     else
       SCEVSizes.push_back(nullptr);
 
   auto *SAI = getOrCreateScopArrayInfo(nullptr, ElementType, SCEVSizes,
                                        MemoryKind::Array, BaseName.c_str());
   return SAI;
 }
 
-const ScopArrayInfo *Scop::getScopArrayInfoOrNull(Value *BasePtr,
-                                                  MemoryKind Kind) {
+ScopArrayInfo *Scop::getScopArrayInfoOrNull(Value *BasePtr, MemoryKind Kind) {
   auto *SAI = ScopArrayInfoMap[std::make_pair(BasePtr, Kind)].get();
   return SAI;
 }
 
-const ScopArrayInfo *Scop::getScopArrayInfo(Value *BasePtr, MemoryKind Kind) {
+ScopArrayInfo *Scop::getScopArrayInfo(Value *BasePtr, MemoryKind Kind) {
   auto *SAI = getScopArrayInfoOrNull(BasePtr, Kind);
   assert(SAI && "No ScopArrayInfo available for this base pointer");
   return SAI;
 }
 
 std::string Scop::getContextStr() const { return getContext().to_str(); }
 
 std::string Scop::getAssumedContextStr() const {
if (!trackAssumption(Kind, Set, Loc, Sign, BB))
     return;
 
   if (Sign == AS_ASSUMPTION)
     AssumedContext = AssumedContext.intersect(Set).coalesce();
   else
     InvalidContext = InvalidContext.unite(Set).coalesce();
 }
 
-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::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 {

 
 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
 LLVM_DUMP_METHOD void Scop::dump() const { print(dbgs(), true); }
 #endif
 
 isl::ctx Scop::getIslCtx() const { return IslCtx.get(); }
 
 __isl_give PWACtx Scop::getPwAff(const SCEV *E, BasicBlock *BB,
-                                 bool NonNegative) {
+                                 bool NonNegative,
+                                 RecordedAssumptionsTy *RecordedAssumptions) {
   // First try to use the SCEVAffinator to generate a piecewise defined
   // affine function from @p E in the context of @p BB. If that tasks becomes to
   // complex the affinator might return a nullptr. In such a case we invalidate
   // the SCoP and return a dummy value. This way we do not need to add error
   // handling code to all users of this function.
-  auto PWAC = Affinator.getPwAff(E, BB);
+  auto PWAC = Affinator.getPwAff(E, BB, RecordedAssumptions);
   if (PWAC.first) {
     // TODO: We could use a heuristic and either use:
     //         SCEVAffinator::takeNonNegativeAssumption
     //       or
     //         SCEVAffinator::interpretAsUnsigned
     //       to deal with unsigned or "NonNegative" SCEVs.
     if (NonNegative)
-      Affinator.takeNonNegativeAssumption(PWAC);
+      Affinator.takeNonNegativeAssumption(PWAC, RecordedAssumptions);
     return PWAC;
   }
 
   auto DL = BB ? BB->getTerminator()->getDebugLoc() : DebugLoc();
   invalidate(COMPLEXITY, DL, BB);
-  return Affinator.getPwAff(SE->getZero(E->getType()), BB);
+  return Affinator.getPwAff(SE->getZero(E->getType()), BB, RecordedAssumptions);
 }
 
 isl::union_set Scop::getDomains() const {
   isl_space *EmptySpace = isl_space_params_alloc(getIslCtx().get(), 0);
   isl_union_set *Domain = isl_union_set_empty(EmptySpace);
 
   for (const ScopStmt &Stmt : *this)
     Domain = isl_union_set_add_set(Domain, Stmt.getDomain().release());
 
   return isl::manage(Domain);
 }
 
-isl::pw_aff Scop::getPwAffOnly(const SCEV *E, BasicBlock *BB) {
-  PWACtx PWAC = getPwAff(E, BB);
+isl::pw_aff Scop::getPwAffOnly(const SCEV *E, BasicBlock *BB,
+                               RecordedAssumptionsTy *RecordedAssumptions) {
+  PWACtx PWAC = getPwAff(E, BB, RecordedAssumptions);
   return PWAC.first;
 }
 
 isl::union_map
 Scop::getAccessesOfType(std::function<bool(MemoryAccess &)> Predicate) {
   isl::union_map Accesses = isl::union_map::empty(getParamSpace());
 
   for (ScopStmt &Stmt : *this) {

polly/lib/Support/SCEVAffinator.cpp

void SCEVAffinator::interpretAsUnsigned(PWACtx &PWAC, unsigned Width) {
   auto *NonNegDom = isl_pw_aff_nonneg_set(PWAC.first.copy());
   auto *NonNegPWA =
       isl_pw_aff_intersect_domain(PWAC.first.copy(), isl_set_copy(NonNegDom));
   auto *ExpPWA = getWidthExpValOnDomain(Width, isl_set_complement(NonNegDom));
   PWAC.first = isl::manage(isl_pw_aff_union_add(
       NonNegPWA, isl_pw_aff_add(PWAC.first.release(), ExpPWA)));
 }
 
-void SCEVAffinator::takeNonNegativeAssumption(PWACtx &PWAC) {
+void SCEVAffinator::takeNonNegativeAssumption(
+    PWACtx &PWAC, RecordedAssumptionsTy *RecordedAssumptions) {
+  this->RecordedAssumptions = RecordedAssumptions;
+
   auto *NegPWA = isl_pw_aff_neg(PWAC.first.copy());
   auto *NegDom = isl_pw_aff_pos_set(NegPWA);
   PWAC.second =
       isl::manage(isl_set_union(PWAC.second.release(), isl_set_copy(NegDom)));
   auto *Restriction = BB ? NegDom : isl_set_params(NegDom);
   auto DL = BB ? BB->getTerminator()->getDebugLoc() : DebugLoc();
-  S->recordAssumption(UNSIGNED, isl::manage(Restriction), DL, AS_RESTRICTION,
-                      BB);
+  recordAssumption(RecordedAssumptions, UNSIGNED, isl::manage(Restriction), DL,
+                   AS_RESTRICTION, BB);
 }
 
 PWACtx SCEVAffinator::getPWACtxFromPWA(isl::pw_aff PWA) {
   return std::make_pair(PWA, isl::set::empty(isl::space(Ctx, 0, NumIterators)));
 }
 
-PWACtx SCEVAffinator::getPwAff(const SCEV *Expr, BasicBlock *BB) {
+PWACtx SCEVAffinator::getPwAff(const SCEV *Expr, BasicBlock *BB,
+                               RecordedAssumptionsTy *RecordedAssumptions) {
   this->BB = BB;
+  this->RecordedAssumptions = RecordedAssumptions;
 
   if (BB) {
     auto *DC = S->getDomainConditions(BB).release();
     NumIterators = isl_set_n_dim(DC);
     isl_set_free(DC);
   } else
     NumIterators = 0;
 
   return visit(Expr);
PWACtx SCEVAffinator::checkForWrapping(const SCEV *Expr, PWACtx PWAC) const {
   PWAC.second = PWAC.second.unite(NotEqualSet).coalesce();
 
   const DebugLoc &Loc = BB ? BB->getTerminator()->getDebugLoc() : DebugLoc();
   if (!BB)
     NotEqualSet = NotEqualSet.params();
   NotEqualSet = NotEqualSet.coalesce();
 
   if (!NotEqualSet.is_empty())
-    S->recordAssumption(WRAPPING, NotEqualSet, Loc, AS_RESTRICTION, BB);
+    recordAssumption(RecordedAssumptions, WRAPPING, NotEqualSet, Loc,
+                     AS_RESTRICTION, BB);
 
   return PWAC;
 }
 
 isl::pw_aff SCEVAffinator::addModuloSemantic(isl::pw_aff PWA,
                                              Type *ExprType) const {
   unsigned Width = TD.getTypeSizeInBits(ExprType);
 
PWACtx SCEVAffinator::visitTruncateExpr(const SCEVTruncateExpr *Expr) {
   OpPWAC.second = OpPWAC.second.unite(isl::manage_copy(OutOfBoundsDom));
 
   if (!BB) {
     assert(isl_set_dim(OutOfBoundsDom, isl_dim_set) == 0 &&
            "Expected a zero dimensional set for non-basic-block domains");
     OutOfBoundsDom = isl_set_params(OutOfBoundsDom);
   }
 
-  S->recordAssumption(UNSIGNED, isl::manage(OutOfBoundsDom), DebugLoc(),
-                      AS_RESTRICTION, BB);
+  recordAssumption(RecordedAssumptions, UNSIGNED, isl::manage(OutOfBoundsDom),
+                   DebugLoc(), AS_RESTRICTION, BB);
 
   return OpPWAC;
 }
 
 PWACtx SCEVAffinator::visitZeroExtendExpr(const SCEVZeroExtendExpr *Expr) {
   // A zero-extended value can be interpreted as a piecewise defined signed
   // value. If the value was non-negative it stays the same, otherwise it
   // is the sum of the original value and 2^n where n is the bit-width of
PWACtx SCEVAffinator::visitZeroExtendExpr(const SCEVZeroExtendExpr *Expr) {
   // bit-width is bigger than MaxZextSmallBitWidth we will employ overflow
   // assumptions and assume the "former negative" piece will not exist.
 
   auto *Op = Expr->getOperand();
   auto OpPWAC = visit(Op);
 
   // If the width is to big we assume the negative part does not occur.
   if (!computeModuloForExpr(Op)) {
-    takeNonNegativeAssumption(OpPWAC);
+    takeNonNegativeAssumption(OpPWAC, RecordedAssumptions);
     return OpPWAC;
   }
 
   // If the width is small build the piece for the non-negative part and
   // the one for the negative part and unify them.
   unsigned Width = TD.getTypeSizeInBits(Op->getType());
   interpretAsUnsigned(OpPWAC, Width);
   return OpPWAC;
if (SE.isKnownNegative(Divisor)) {
     auto *WidthExpPWA = getWidthExpValOnDomain(Width, DivisorDom);
     DivisorPWAC.first = DivisorPWAC.first.add(isl::manage(WidthExpPWA));
   }
 
   // TODO: One can represent the dividend as piece-wise function to be more
   //       precise but therefor a heuristic is needed.
 
   // Assume a non-negative dividend.
-  takeNonNegativeAssumption(DividendPWAC);
+  takeNonNegativeAssumption(DividendPWAC, RecordedAssumptions);
 
   DividendPWAC = combine(DividendPWAC, DivisorPWAC, isl_pw_aff_div);
   DividendPWAC.first = DividendPWAC.first.floor();
 
   return DividendPWAC;
 }
 
 PWACtx SCEVAffinator::visitSDivInstruction(Instruction *SDiv) {

polly/lib/Support/ScopHelper.cpp

static void simplifyRegionExit(Region *R, DominatorTree *DT, LoopInfo *LI,
   // After:
   //
   //     \   /                //
   //    ExitingBB     _____/  //
   //          \      /        //
   //           ExitBB         //
   //           /    \         //
 }
 
 void polly::simplifyRegion(Region *R, DominatorTree *DT, LoopInfo *LI,
                            RegionInfo *RI) {
   assert(R && !R->isTopLevelRegion());
   assert(!RI || RI == R->getRegionInfo());
   assert((!RI || DT) &&
          "RegionInfo requires DominatorTree to be updated as well");
 
   simplifyRegionEntry(R, DT, LI, RI);
   simplifyRegionExit(R, DT, LI, RI);
   assert(R->isSimple());
 }
 
 // Split the block into two successive blocks.
 //
 // Like llvm::SplitBlock, but also preserves RegionInfo
void polly::splitEntryBlockForAlloca(BasicBlock *EntryBlock, Pass *P) {
   auto *LI = LIWP ? &LIWP->getLoopInfo() : nullptr;
   RegionInfoPass *RIP = P->getAnalysisIfAvailable<RegionInfoPass>();
   RegionInfo *RI = RIP ? &RIP->getRegionInfo() : nullptr;
 
   // splitBlock updates DT, LI and RI.
   polly::splitEntryBlockForAlloca(EntryBlock, DT, LI, RI);
 }
 
+void polly::recordAssumption(polly::RecordedAssumptionsTy *RecordedAssumptions,
+                             polly::AssumptionKind Kind, isl::set Set,
+                             DebugLoc Loc, polly::AssumptionSign Sign,
+                             BasicBlock *BB) {
+  assert((Set.is_params() || BB) &&
+         "Assumptions without a basic block must be parameter sets");
+  if (RecordedAssumptions)
+    RecordedAssumptions->push_back({Kind, Sign, Set, Loc, BB});
+}
+
 /// The SCEVExpander will __not__ generate any code for an existing SDiv/SRem
 /// instruction but just use it, if it is referenced as a SCEVUnknown. We want
 /// however to generate new code if the instruction is in the analyzed region
 /// and we generate code outside/in front of that region. Hence, we generate the
 /// code for the SDiv/SRem operands in front of the analyzed region and then
 /// create a new SDiv/SRem operation there too.
 struct ScopExpander : SCEVVisitor<ScopExpander, const SCEV *> {
   friend struct SCEVVisitor<ScopExpander, const SCEV *>;