[Polly][NFC][ScopBuilder] Move buildAliasChecks and its implementing methods to ScopBuilder

[domada]

Summary

Scope of changes:

1. Moved buildAliasChecks to ScopBuilder.
2. Moved buildAliasGroup to ScopBuilder.
3. Moved buildAliasGroups to ScopBuilder.
4. Moved buildAliasGroupsForAccesses to ScopBuilder.
5. Moved splitAliasGroupsByDomain to ScopBuilder.
6. Moved addNonEmptyDomainConstraints to ScopBuilder.
7. Moved buildMinMaxAccess to ScopBuilder.
8. Moved calculateMinMaxAccess to ScopBuilder.
9. Moved getAccessDomain to ScopBuilder.
10. Moved command line options used only by buildAliasChecks functions to ScopBuilder
11. Refactored buildAliasGroup function. Added addAliasGroup function to Scop class for pushing back calculated min/max accesses.
12. Added function incrementNumberOfAliasingAssumptions which increments number of statistic variable AssumptionsAliasing. AssumptionsAliasing variable is defined by STATISTIC macro inside ScopInfo.cpp and it is also used by function trackAssumption from Scop class.
13. Added reference to OptimizationRemarkEmitter to ScopBuilder class.
14. Moved calculateMinMaxAccess function to ScopBuilder class.

[domada]

Please let me know if such big patch is acceptable. I have moved all functions referenced only by buildAliasChecks function to ScopBuilder class.

[Meinersbur]

In D63693#1554880, @domada wrote:

Please let me know if such big patch is acceptable. I have moved all functions referenced only by buildAliasChecks function to ScopBuilder class.

Yes, if all changes have a common topic, in this case moving the alias check functionality. Even if we wanted tom move them, I don't think hasFeasibleRuntimeContext and lookupBasePtrAccess are specific to this functionality.

Could you change the title to reflect the topic, such as "Move buildAliasChecks and its implementing methods to ScopBuilder"?

polly/include/polly/ScopBuilder.h

35–38

AFICS these types are only used in private functions, i.e. could be private themselves.

polly/include/polly/ScopInfo.h

2035

I think this accessor might still be useful after havind constructed a SCoP on should stay.

2502

This function might also be useful after the SCoP has been constructed and should stay.

2601

I don't think modifying an object's internals through a get-accessor is a good idea.

polly/lib/Analysis/ScopBuilder.cpp

2336

After being moved to ScopBuilder, buildAliasChecks can just use this->AA. Similarly, as a uitility object ORE can be made a member of ScopBuilder so it's not needed to be passed every time.

[domada]

Applied cod review remarks:

1. Leave lookupBasePtrAccess in Scop class.
2. Leave hasFeasibleRuntimeContext in Scop class.
3. Added Optimization Remark Emitter to ScopBuilder class,
4. Make types AliasGroupTy and AliasGroupVectorTy private.

[Meinersbur]

LGTM! Many thanks!

Can I commit for you?

polly/include/polly/ScopInfo.h

2605–2607

[suggestion]

MinMaxAliasGroups.emplace_back(MinMaxAccessesReadWrite, MinMaxAccessesReadOnly);

polly/include/polly/ScopBuilder.h

 
 class ScopDetection;
 
 /// Command line switch whether to model read-only accesses.
 extern bool ModelReadOnlyScalars;
 
 /// Build the Polly IR (Scop and ScopStmt) on a Region.
 class ScopBuilder {
+
   /// The AliasAnalysis to build AliasSetTracker.
   AliasAnalysis &AA;
 
   /// Target data for element size computing.
   const DataLayout &DL;
 
   /// DominatorTree to reason about guaranteed execution.
   DominatorTree &DT;
 
   /// LoopInfo for information about loops.
   LoopInfo &LI;
 
   /// Valid Regions for Scop
   ScopDetection &SD;
 
   /// The ScalarEvolution to help building Scop.
   ScalarEvolution &SE;
 
+  /// An optimization diagnostic interface to add optimization remarks.
+  OptimizationRemarkEmitter &ORE;
+
   /// Set of instructions that might read any memory location.
   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;
class ScopBuilder {
   /// @param Inst The LoadInst/StoreInst that accesses the memory.
   ///
   /// @returns Reference to %untypedmem on success, nullptr on failure.
   Value *findFADAllocationVisible(MemAccInst Inst);
 
   // @}
 
   // Build the SCoP for Region @p R.
-  void buildScop(Region &R, AssumptionCache &AC,
-                 OptimizationRemarkEmitter &ORE);
+  void buildScop(Region &R, AssumptionCache &AC);
 
   /// Create equivalence classes for required invariant accesses.
   ///
   /// These classes will consolidate multiple required invariant loads from the
   /// same address in order to keep the number of dimensions in the SCoP
   /// description small. For each such class equivalence class only one
   /// representing element, hence one required invariant load, will be chosen
   /// and modeled as parameter. The method
class ScopBuilder {
 
   /// Build a single-dimensional parametric sized MemoryAccess
   ///        from the Load/Store instruction.
   ///
   /// @param Inst       The Load/Store instruction that access the memory
   /// @param Stmt       The parent statement of the instruction
   void buildAccessSingleDim(MemAccInst Inst, ScopStmt *Stmt);
 
+  /// Build the alias checks for this SCoP.
+  bool buildAliasChecks();
+
+  /// A vector of memory accesses that belong to an alias group.
+  using AliasGroupTy = SmallVector<MemoryAccess *, 4>;
+
+  /// A vector of alias groups.
+  using AliasGroupVectorTy = SmallVector<AliasGroupTy, 4>;
+
+  /// Build a given alias group and its access data.
+  ///
+  /// @param AliasGroup     The alias group to build.
+  /// @param HasWriteAccess A set of arrays through which memory is not only
+  ///                       read, but also written.
+  //
+  /// @returns True if __no__ error occurred, false otherwise.
+  bool buildAliasGroup(AliasGroupTy &AliasGroup,
+                       DenseSet<const ScopArrayInfo *> HasWriteAccess);
+
+  /// Build all alias groups for this SCoP.
+  ///
+  /// @returns True if __no__ error occurred, false otherwise.
+  bool buildAliasGroups();
+
+  /// Build alias groups for all memory accesses in the Scop.
+  ///
+  /// Using the alias analysis and an alias set tracker we build alias sets
+  /// for all memory accesses inside the Scop. For each alias set we then map
+  /// the aliasing pointers back to the memory accesses we know, thus obtain
+  /// groups of memory accesses which might alias. We also collect the set of
+  /// arrays through which memory is written.
+  ///
+  /// @returns A pair consistent of a vector of alias groups and a set of arrays
+  ///          through which memory is written.
+  std::tuple<AliasGroupVectorTy, DenseSet<const ScopArrayInfo *>>
+  buildAliasGroupsForAccesses();
+
+  ///  Split alias groups by iteration domains.
+  ///
+  ///  We split each group based on the domains of the minimal/maximal accesses.
+  ///  That means two minimal/maximal accesses are only in a group if their
+  ///  access domains intersect. Otherwise, they are in different groups.
+  ///
+  ///  @param AliasGroups The alias groups to split
+  void splitAliasGroupsByDomain(AliasGroupVectorTy &AliasGroups);
+
   /// Build an instance of MemoryAccess from the Load/Store instruction.
   ///
   /// @param Inst       The Load/Store instruction that access the memory
   /// @param Stmt       The parent statement of the instruction
   void buildMemoryAccess(MemAccInst Inst, ScopStmt *Stmt);
 
   /// Analyze and extract the cross-BB scalar dependences (or, dataflow
   /// dependencies) of an instruction.
class ScopBuilder {
   /// @param PHIStmt Statement @p PHI resides in.
   /// @param PHI     PHINode under consideration; the READ access will be added
   ///                here.
   ///
   /// @see ensurePHIWrite()
   /// @see MemoryKind
   void addPHIReadAccess(ScopStmt *PHIStmt, PHINode *PHI);
 
+  /// Wrapper function to calculate minimal/maximal accesses to each array.
+  bool calculateMinMaxAccess(AliasGroupTy AliasGroup,
+                             Scop::MinMaxVectorTy &MinMaxAccesses);
   /// Build the domain of @p Stmt.
   void buildDomain(ScopStmt &Stmt);
 
   /// Fill NestLoops with loops surrounding @p Stmt.
   void collectSurroundingLoops(ScopStmt &Stmt);
 
   /// Check for reductions in @p Stmt.
   ///

polly/include/polly/ScopInfo.h

private:
   /// @returns True if there was no problem and false otherwise.
   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);
 
   /// 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).
private:
   void printAliasAssumptions(raw_ostream &OS) const;
   //@}
 
 public:
   Scop(const Scop &) = delete;
   Scop &operator=(const Scop &) = delete;
   ~Scop();
 
+  /// Increment actual number of aliasing assumptions taken
+  ///
+  /// @param Step    Number of new aliasing assumptions which should be added to
+  /// the number of already taken assumptions.
+  static void incrementNumberOfAliasingAssumptions(unsigned Step);
+
   /// Get the count of copy statements added to this Scop.
   ///
   /// @return The count of copy statements added to this Scop.
   unsigned getCopyStmtsNum() { return CopyStmtsNum; }
 
   /// Create a new copy statement.
   ///
   /// A new statement will be created and added to the statement vector.
public:
   isl::set getAssumedContext() const;
 
   /// 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
public:
   /// Get the invalid context for this Scop.
   ///
   /// @return The invalid context of this Scop.
   isl::set getInvalidContext() const;
 
   /// Return true if and only if the InvalidContext is trivial (=empty).
   bool hasTrivialInvalidContext() const { return InvalidContext.is_empty(); }
 
-  /// A vector of memory accesses that belong to an alias group.
-  using AliasGroupTy = SmallVector<MemoryAccess *, 4>;
-
-  /// A vector of alias groups.
-  using AliasGroupVectorTy = SmallVector<Scop::AliasGroupTy, 4>;
-
-  /// Build the alias checks for this SCoP.
-  bool buildAliasChecks(AliasAnalysis &AA);
-
-  /// Build all alias groups for this SCoP.
-  ///
-  /// @returns True if __no__ error occurred, false otherwise.
-  bool buildAliasGroups(AliasAnalysis &AA);
-
-  /// Build alias groups for all memory accesses in the Scop.
-  ///
-  /// Using the alias analysis and an alias set tracker we build alias sets
-  /// for all memory accesses inside the Scop. For each alias set we then map
-  /// the aliasing pointers back to the memory accesses we know, thus obtain
-  /// groups of memory accesses which might alias. We also collect the set of
-  /// arrays through which memory is written.
-  ///
-  /// @param AA A reference to the alias analysis.
-  ///
-  /// @returns A pair consistent of a vector of alias groups and a set of arrays
-  ///          through which memory is written.
-  std::tuple<AliasGroupVectorTy, DenseSet<const ScopArrayInfo *>>
-  buildAliasGroupsForAccesses(AliasAnalysis &AA);
-
-  ///  Split alias groups by iteration domains.
-  ///
-  ///  We split each group based on the domains of the minimal/maximal accesses.
-  ///  That means two minimal/maximal accesses are only in a group if their
-  ///  access domains intersect. Otherwise, they are in different groups.
-  ///
-  ///  @param AliasGroups The alias groups to split
-  void splitAliasGroupsByDomain(AliasGroupVectorTy &AliasGroups);
-
-  /// Build a given alias group and its access data.
-  ///
-  /// @param AliasGroup     The alias group to build.
-  /// @param HasWriteAccess A set of arrays through which memory is not only
-  ///                       read, but also written.
-  ///
-  /// @returns True if __no__ error occurred, false otherwise.
-  bool buildAliasGroup(Scop::AliasGroupTy &AliasGroup,
-                       DenseSet<const ScopArrayInfo *> HasWriteAccess);
-
   /// Return all alias groups for this SCoP.
   const MinMaxVectorPairVectorTy &getAliasGroups() const {
     return MinMaxAliasGroups;
   }
 
+  void addAliasGroup(MinMaxVectorTy &MinMaxAccessesReadWrite,
+                     MinMaxVectorTy &MinMaxAccessesReadOnly) {
+    MinMaxAliasGroups.emplace_back();
+    MinMaxAliasGroups.back().first = MinMaxAccessesReadWrite;
+    MinMaxAliasGroups.back().second = MinMaxAccessesReadOnly;
+  }
   /// Get an isl string representing the context.
   std::string getContextStr() const;
 
   /// Get an isl string representing the assumed context.
   std::string getAssumedContextStr() const;
 
   /// Get an isl string representing the invalid context.
   std::string getInvalidContextStr() const;

polly/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<int>
+    OptComputeOut("polly-analysis-computeout",
+                  cl::desc("Bound the scop analysis by a maximal amount of "
+                           "computational steps (0 means no bound)"),
+                  cl::Hidden, cl::init(800000), cl::ZeroOrMore,
+                  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<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 "
+             "to build RTCs."),
+    cl::Hidden, cl::ZeroOrMore, cl::init(8), cl::cat(PollyCategory));
+
+static cl::opt<unsigned> RunTimeChecksMaxParameters(
+    "polly-rtc-max-parameters",
+    cl::desc("The maximal number of parameters allowed in RTCs."), cl::Hidden,
+    cl::ZeroOrMore, cl::init(8), 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 (MemoryAccess *Access : Stmt.MemAccs) {
 
     auto *SAI = scop->getOrCreateScopArrayInfo(Access->getOriginalBaseAddr(),
                                                ElementType, Access->Sizes, Ty);
     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
+///         maximal number of run-time checks to be generated.
+static bool buildMinMaxAccess(isl::set Set,
+                              Scop::MinMaxVectorTy &MinMaxAccesses, Scop &S) {
+  isl::pw_multi_aff MinPMA, MaxPMA;
+  isl::pw_aff LastDimAff;
+  isl::aff OneAff;
+  unsigned Pos;
+
+  Set = Set.remove_divs();
+  polly::simplify(Set);
+
+  if (Set.n_basic_set() > RunTimeChecksMaxAccessDisjuncts)
+    Set = Set.simple_hull();
+
+  // Restrict the number of parameters involved in the access as the lexmin/
+  // lexmax computation will take too long if this number is high.
+  //
+  // Experiments with a simple test case using an i7 4800MQ:
+  //
+  //  #Parameters involved | Time (in sec)
+  //            6          |     0.01
+  //            7          |     0.04
+  //            8          |     0.12
+  //            9          |     0.40
+  //           10          |     1.54
+  //           11          |     6.78
+  //           12          |    30.38
+  //
+  if (isl_set_n_param(Set.get()) > RunTimeChecksMaxParameters) {
+    unsigned InvolvedParams = 0;
+    for (unsigned u = 0, e = isl_set_n_param(Set.get()); u < e; u++)
+      if (Set.involves_dims(isl::dim::param, u, 1))
+        InvolvedParams++;
+
+    if (InvolvedParams > RunTimeChecksMaxParameters)
+      return false;
+  }
+
+  MinPMA = Set.lexmin_pw_multi_aff();
+  MaxPMA = Set.lexmax_pw_multi_aff();
+
+  MinPMA = MinPMA.coalesce();
+  MaxPMA = MaxPMA.coalesce();
+
+  // Adjust the last dimension of the maximal access by one as we want to
+  // enclose the accessed memory region by MinPMA and MaxPMA. The pointer
+  // we test during code generation might now point after the end of the
+  // allocated array but we will never dereference it anyway.
+  assert((!MaxPMA || MaxPMA.dim(isl::dim::out)) &&
+         "Assumed at least one output dimension");
+
+  Pos = MaxPMA.dim(isl::dim::out) - 1;
+  LastDimAff = MaxPMA.get_pw_aff(Pos);
+  OneAff = isl::aff(isl::local_space(LastDimAff.get_domain_space()));
+  OneAff = OneAff.add_constant_si(1);
+  LastDimAff = LastDimAff.add(OneAff);
+  MaxPMA = MaxPMA.set_pw_aff(Pos, LastDimAff);
+
+  if (!MinPMA || !MaxPMA)
+    return false;
+
+  MinMaxAccesses.push_back(std::make_pair(MinPMA, MaxPMA));
+
+  return true;
+}
+
+/// Wrapper function to calculate minimal/maximal accesses to each array.
+bool ScopBuilder::calculateMinMaxAccess(AliasGroupTy AliasGroup,
+                                        Scop::MinMaxVectorTy &MinMaxAccesses) {
+  MinMaxAccesses.reserve(AliasGroup.size());
+
+  isl::union_set Domains = scop->getDomains();
+  isl::union_map Accesses = isl::union_map::empty(scop->getParamSpace());
+
+  for (MemoryAccess *MA : AliasGroup)
+    Accesses = Accesses.add_map(MA->getAccessRelation());
+
+  Accesses = Accesses.intersect_domain(Domains);
+  isl::union_set Locations = Accesses.range();
+
+  bool LimitReached = false;
+  for (isl::set Set : Locations.get_set_list()) {
+    LimitReached |= !buildMinMaxAccess(Set, MinMaxAccesses, *scop);
+    if (LimitReached)
+      break;
+  }
+
+  return !LimitReached;
+}
+
+static isl::set getAccessDomain(MemoryAccess *MA) {
+  isl::set Domain = MA->getStatement()->getDomain();
+  Domain = Domain.project_out(isl::dim::set, 0, Domain.n_dim());
+  return Domain.reset_tuple_id();
+}
+
+bool ScopBuilder::buildAliasChecks() {
+  if (!PollyUseRuntimeAliasChecks)
+    return true;
+
+  if (buildAliasGroups()) {
+    // Aliasing assumptions do not go through addAssumption but we still want to
+    // collect statistics so we do it here explicitly.
+    if (scop->getAliasGroups().size())
+      Scop::incrementNumberOfAliasingAssumptions(1);
+    return true;
+  }
+
+  // If a problem occurs while building the alias groups we need to delete
+  // this SCoP and pretend it wasn't valid in the first place. To this end
+  // we make the assumed context infeasible.
+  scop->invalidate(ALIASING, DebugLoc());
+
+  LLVM_DEBUG(
+      dbgs() << "\n\nNOTE: Run time checks for " << scop->getNameStr()
+             << " could not be created as the number of parameters involved "
+                "is too high. The SCoP will be "
+                "dismissed.\nUse:\n\t--polly-rtc-max-parameters=X\nto adjust "
+                "the maximal number of parameters but be advised that the "
+                "compile time might increase exponentially.\n\n");
+  return false;
+}
+
+std::tuple<ScopBuilder::AliasGroupVectorTy, DenseSet<const ScopArrayInfo *>>
+ScopBuilder::buildAliasGroupsForAccesses() {
+  AliasSetTracker AST(AA);
+
+  DenseMap<Value *, MemoryAccess *> PtrToAcc;
+  DenseSet<const ScopArrayInfo *> HasWriteAccess;
+  for (ScopStmt &Stmt : *scop) {
+
+    isl::set StmtDomain = Stmt.getDomain();
+    bool StmtDomainEmpty = StmtDomain.is_empty();
+
+    // Statements with an empty domain will never be executed.
+    if (StmtDomainEmpty)
+      continue;
+
+    for (MemoryAccess *MA : Stmt) {
+      if (MA->isScalarKind())
+        continue;
+      if (!MA->isRead())
+        HasWriteAccess.insert(MA->getScopArrayInfo());
+      MemAccInst Acc(MA->getAccessInstruction());
+      if (MA->isRead() && isa<MemTransferInst>(Acc))
+        PtrToAcc[cast<MemTransferInst>(Acc)->getRawSource()] = MA;
+      else
+        PtrToAcc[Acc.getPointerOperand()] = MA;
+      AST.add(Acc);
+    }
+  }
+
+  AliasGroupVectorTy AliasGroups;
+  for (AliasSet &AS : AST) {
+    if (AS.isMustAlias() || AS.isForwardingAliasSet())
+      continue;
+    AliasGroupTy AG;
+    for (auto &PR : AS)
+      AG.push_back(PtrToAcc[PR.getValue()]);
+    if (AG.size() < 2)
+      continue;
+    AliasGroups.push_back(std::move(AG));
+  }
+
+  return std::make_tuple(AliasGroups, HasWriteAccess);
+}
+
+bool ScopBuilder::buildAliasGroups() {
+  // To create sound alias checks we perform the following steps:
+  //   o) We partition each group into read only and non read only accesses.
+  //   o) For each group with more than one base pointer we then compute minimal
+  //      and maximal accesses to each array of a group in read only and non
+  //      read only partitions separately.
+  AliasGroupVectorTy AliasGroups;
+  DenseSet<const ScopArrayInfo *> HasWriteAccess;
+
+  std::tie(AliasGroups, HasWriteAccess) = buildAliasGroupsForAccesses();
+
+  splitAliasGroupsByDomain(AliasGroups);
+
+  for (AliasGroupTy &AG : AliasGroups) {
+    if (!scop->hasFeasibleRuntimeContext())
+      return false;
+
+    {
+      IslMaxOperationsGuard MaxOpGuard(scop->getIslCtx().get(), OptComputeOut);
+      bool Valid = buildAliasGroup(AG, HasWriteAccess);
+      if (!Valid)
+        return false;
+    }
+    if (isl_ctx_last_error(scop->getIslCtx().get()) == isl_error_quota) {
+      scop->invalidate(COMPLEXITY, DebugLoc());
+      return false;
+    }
+  }
+
+  return true;
+}
+
+bool ScopBuilder::buildAliasGroup(
+    AliasGroupTy &AliasGroup, DenseSet<const ScopArrayInfo *> HasWriteAccess) {
+  AliasGroupTy ReadOnlyAccesses;
+  AliasGroupTy ReadWriteAccesses;
+  SmallPtrSet<const ScopArrayInfo *, 4> ReadWriteArrays;
+  SmallPtrSet<const ScopArrayInfo *, 4> ReadOnlyArrays;
+
+  if (AliasGroup.size() < 2)
+    return true;
+
+  for (MemoryAccess *Access : AliasGroup) {
+    ORE.emit(OptimizationRemarkAnalysis(DEBUG_TYPE, "PossibleAlias",
+                                        Access->getAccessInstruction())
+             << "Possibly aliasing pointer, use restrict keyword.");
+    const ScopArrayInfo *Array = Access->getScopArrayInfo();
+    if (HasWriteAccess.count(Array)) {
+      ReadWriteArrays.insert(Array);
+      ReadWriteAccesses.push_back(Access);
+    } else {
+      ReadOnlyArrays.insert(Array);
+      ReadOnlyAccesses.push_back(Access);
+    }
+  }
+
+  // If there are no read-only pointers, and less than two read-write pointers,
+  // no alias check is needed.
+  if (ReadOnlyAccesses.empty() && ReadWriteArrays.size() <= 1)
+    return true;
+
+  // If there is no read-write pointer, no alias check is needed.
+  if (ReadWriteArrays.empty())
+    return true;
+
+  // For non-affine accesses, no alias check can be generated as we cannot
+  // compute a sufficiently tight lower and upper bound: bail out.
+  for (MemoryAccess *MA : AliasGroup) {
+    if (!MA->isAffine()) {
+      scop->invalidate(ALIASING, MA->getAccessInstruction()->getDebugLoc(),
+                       MA->getAccessInstruction()->getParent());
+      return false;
+    }
+  }
+
+  // Ensure that for all memory accesses for which we generate alias checks,
+  // their base pointers are available.
+  for (MemoryAccess *MA : AliasGroup) {
+    if (MemoryAccess *BasePtrMA = scop->lookupBasePtrAccess(MA))
+      scop->addRequiredInvariantLoad(
+          cast<LoadInst>(BasePtrMA->getAccessInstruction()));
+  }
+
+  //  scop->getAliasGroups().emplace_back();
+  //  Scop::MinMaxVectorPairTy &pair = scop->getAliasGroups().back();
+  Scop::MinMaxVectorTy MinMaxAccessesReadWrite;
+  Scop::MinMaxVectorTy MinMaxAccessesReadOnly;
+
+  bool Valid;
+
+  Valid = calculateMinMaxAccess(ReadWriteAccesses, MinMaxAccessesReadWrite);
+
+  if (!Valid)
+    return false;
+
+  // Bail out if the number of values we need to compare is too large.
+  // This is important as the number of comparisons grows quadratically with
+  // the number of values we need to compare.
+  if (MinMaxAccessesReadWrite.size() + ReadOnlyArrays.size() >
+      RunTimeChecksMaxArraysPerGroup)
+    return false;
+
+  Valid = calculateMinMaxAccess(ReadOnlyAccesses, MinMaxAccessesReadOnly);
+
+  scop->addAliasGroup(MinMaxAccessesReadWrite, MinMaxAccessesReadOnly);
+  if (!Valid)
+    return false;
+
+  return true;
+}
+
+void ScopBuilder::splitAliasGroupsByDomain(AliasGroupVectorTy &AliasGroups) {
+  for (unsigned u = 0; u < AliasGroups.size(); u++) {
+    AliasGroupTy NewAG;
+    AliasGroupTy &AG = AliasGroups[u];
+    AliasGroupTy::iterator AGI = AG.begin();
+    isl::set AGDomain = getAccessDomain(*AGI);
+    while (AGI != AG.end()) {
+      MemoryAccess *MA = *AGI;
+      isl::set MADomain = getAccessDomain(MA);
+      if (AGDomain.is_disjoint(MADomain)) {
+        NewAG.push_back(MA);
+        AGI = AG.erase(AGI);
+      } else {
+        AGDomain = AGDomain.unite(MADomain);
+        AGI++;
+      }
+    }
+    if (NewAG.size() > 1)
+      AliasGroups.push_back(std::move(NewAG));
+  }
+}
+
 #ifndef NDEBUG
 static void verifyUse(Scop *S, Use &Op, LoopInfo &LI) {
   auto PhysUse = VirtualUse::create(S, Op, &LI, false);
   auto VirtUse = VirtualUse::create(S, Op, &LI, true);
   assert(PhysUse.getKind() == VirtUse.getKind());
 }
 
 /// Check the consistency of every statement's MemoryAccesses.

 #endif
 
 /// Return the block that is the representing block for @p RN.
 static inline BasicBlock *getRegionNodeBasicBlock(RegionNode *RN) {
   return RN->isSubRegion() ? RN->getNodeAs<Region>()->getEntry()
                            : RN->getNodeAs<BasicBlock>();
 }
 
-void ScopBuilder::buildScop(Region &R, AssumptionCache &AC,
-                            OptimizationRemarkEmitter &ORE) {
+void ScopBuilder::buildScop(Region &R, AssumptionCache &AC) {
   scop.reset(new Scop(R, SE, LI, DT, *SD.getDetectionContext(&R), ORE));
 
   buildStmts(R);
 
   // Create all invariant load instructions first. These are categorized as
   // 'synthesizable', therefore are not part of any ScopStmt but need to be
   // created somewhere.
   const InvariantLoadsSetTy &RIL = scop->getRequiredInvariantLoads();
void ScopBuilder::buildScop(Region &R, AssumptionCache &AC) {
   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.
   addRecordedAssumptions();
 
   scop->simplifyContexts();
-  if (!scop->buildAliasChecks(AA)) {
+  if (!buildAliasChecks()) {
     LLVM_DEBUG(dbgs() << "Bailing-out because could not build alias checks\n");
     return;
   }
 
   hoistInvariantLoads();
   canonicalizeDynamicBasePtrs();
   verifyInvariantLoads();
   scop->simplifySCoP(true);
#ifndef NDEBUG
   verifyUses(scop.get(), LI, DT);
 #endif
 }
 
 ScopBuilder::ScopBuilder(Region *R, AssumptionCache &AC, AliasAnalysis &AA,
                          const DataLayout &DL, DominatorTree &DT, LoopInfo &LI,
                          ScopDetection &SD, ScalarEvolution &SE,
                          OptimizationRemarkEmitter &ORE)
-    : AA(AA), DL(DL), DT(DT), LI(LI), SD(SD), SE(SE) {
+    : AA(AA), DL(DL), DT(DT), LI(LI), SD(SD), SE(SE), ORE(ORE) {
   DebugLoc Beg, End;
   auto P = getBBPairForRegion(R);
   getDebugLocations(P, Beg, End);
 
   std::string Msg = "SCoP begins here.";
   ORE.emit(OptimizationRemarkAnalysis(DEBUG_TYPE, "ScopEntry", Beg, P.first)
            << Msg);
 
-  buildScop(*R, AC, ORE);
+  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");
     scop.reset();

polly/lib/Analysis/ScopInfo.cpp

 
 int const polly::MaxDisjunctsInDomain = 20;
 
 // The number of disjunct in the context after which we stop to add more
 // disjuncts. This parameter is there to avoid exponential growth in the
 // number of disjunct when adding non-convex sets to the context.
 static int const MaxDisjunctsInContext = 4;
 
-static cl::opt<int>
-    OptComputeOut("polly-analysis-computeout",
-                  cl::desc("Bound the scop analysis by a maximal amount of "
-                           "computational steps (0 means no bound)"),
-                  cl::Hidden, cl::init(800000), cl::ZeroOrMore,
-                  cl::cat(PollyCategory));
-
 static cl::opt<bool> PollyRemarksMinimal(
     "polly-remarks-minimal",
     cl::desc("Do not emit remarks about assumptions that are known"),
     cl::Hidden, cl::ZeroOrMore, cl::init(false), 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 "
-             "to build RTCs."),
-    cl::Hidden, cl::ZeroOrMore, cl::init(8), cl::cat(PollyCategory));
-
-static cl::opt<unsigned> RunTimeChecksMaxParameters(
-    "polly-rtc-max-parameters",
-    cl::desc("The maximal number of parameters allowed in RTCs."), cl::Hidden,
-    cl::ZeroOrMore, cl::init(8), 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<std::string> UserContextStr(
     "polly-context", cl::value_desc("isl parameter set"),
     cl::desc("Provide additional constraints on the context parameters"),
     cl::init(""), cl::cat(PollyCategory));
 
 static cl::opt<bool>
     IslOnErrorAbort("polly-on-isl-error-abort",
                     cl::desc("Abort if an isl error is encountered"),

 }
 
 isl::id Scop::getIdForParam(const SCEV *Parameter) const {
   // Normalize the SCEV to get the representing element for an invariant load.
   Parameter = getRepresentingInvariantLoadSCEV(Parameter);
   return ParameterIds.lookup(Parameter);
 }
 
-isl::set Scop::addNonEmptyDomainConstraints(isl::set C) const {
-  isl::set DomainContext = getDomains().params();
-  return C.intersect_params(DomainContext);
-}
-
 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()) {
void Scop::simplifyContexts() {
   //
   //   we assume that the condition m <= 0 or (m >= 1 and p >= 0) holds as
   //   otherwise we would access out of bound data. Now, knowing that code is
   //   only executed for the case m >= 0, it is sufficient to assume p >= 0.
   AssumedContext = simplifyAssumptionContext(AssumedContext, *this);
   InvalidContext = InvalidContext.align_params(getParamSpace());
 }
 
-/// Add the minimal/maximal access in @p Set to @p User.
-///
-/// @return True if more accesses should be added, false if we reached the
-///         maximal number of run-time checks to be generated.
-static bool buildMinMaxAccess(isl::set Set,
-                              Scop::MinMaxVectorTy &MinMaxAccesses, Scop &S) {
-  isl::pw_multi_aff MinPMA, MaxPMA;
-  isl::pw_aff LastDimAff;
-  isl::aff OneAff;
-  unsigned Pos;
-
-  Set = Set.remove_divs();
-  polly::simplify(Set);
-
-  if (Set.n_basic_set() > RunTimeChecksMaxAccessDisjuncts)
-    Set = Set.simple_hull();
-
-  // Restrict the number of parameters involved in the access as the lexmin/
-  // lexmax computation will take too long if this number is high.
-  //
-  // Experiments with a simple test case using an i7 4800MQ:
-  //
-  //  #Parameters involved | Time (in sec)
-  //            6          |     0.01
-  //            7          |     0.04
-  //            8          |     0.12
-  //            9          |     0.40
-  //           10          |     1.54
-  //           11          |     6.78
-  //           12          |    30.38
-  //
-  if (isl_set_n_param(Set.get()) > RunTimeChecksMaxParameters) {
-    unsigned InvolvedParams = 0;
-    for (unsigned u = 0, e = isl_set_n_param(Set.get()); u < e; u++)
-      if (Set.involves_dims(isl::dim::param, u, 1))
-        InvolvedParams++;
-
-    if (InvolvedParams > RunTimeChecksMaxParameters)
-      return false;
-  }
-
-  MinPMA = Set.lexmin_pw_multi_aff();
-  MaxPMA = Set.lexmax_pw_multi_aff();
-
-  MinPMA = MinPMA.coalesce();
-  MaxPMA = MaxPMA.coalesce();
-
-  // Adjust the last dimension of the maximal access by one as we want to
-  // enclose the accessed memory region by MinPMA and MaxPMA. The pointer
-  // we test during code generation might now point after the end of the
-  // allocated array but we will never dereference it anyway.
-  assert((!MaxPMA || MaxPMA.dim(isl::dim::out)) &&
-         "Assumed at least one output dimension");
-
-  Pos = MaxPMA.dim(isl::dim::out) - 1;
-  LastDimAff = MaxPMA.get_pw_aff(Pos);
-  OneAff = isl::aff(isl::local_space(LastDimAff.get_domain_space()));
-  OneAff = OneAff.add_constant_si(1);
-  LastDimAff = LastDimAff.add(OneAff);
-  MaxPMA = MaxPMA.set_pw_aff(Pos, LastDimAff);
-
-  if (!MinPMA || !MaxPMA)
-    return false;
-
-  MinMaxAccesses.push_back(std::make_pair(MinPMA, MaxPMA));
-
-  return true;
-}
-
-static isl::set getAccessDomain(MemoryAccess *MA) {
-  isl::set Domain = MA->getStatement()->getDomain();
-  Domain = Domain.project_out(isl::dim::set, 0, Domain.n_dim());
-  return Domain.reset_tuple_id();
-}
-
-/// Wrapper function to calculate minimal/maximal accesses to each array.
-static bool calculateMinMaxAccess(Scop::AliasGroupTy AliasGroup, Scop &S,
-                                  Scop::MinMaxVectorTy &MinMaxAccesses) {
-  MinMaxAccesses.reserve(AliasGroup.size());
-
-  isl::union_set Domains = S.getDomains();
-  isl::union_map Accesses = isl::union_map::empty(S.getParamSpace());
-
-  for (MemoryAccess *MA : AliasGroup)
-    Accesses = Accesses.add_map(MA->getAccessRelation());
-
-  Accesses = Accesses.intersect_domain(Domains);
-  isl::union_set Locations = Accesses.range();
-
-  bool LimitReached = false;
-  for (isl::set Set : Locations.get_set_list()) {
-    LimitReached |= !buildMinMaxAccess(Set, MinMaxAccesses, S);
-    if (LimitReached)
-      break;
-  }
-
-  return !LimitReached;
-}
-
 /// Helper to treat non-affine regions and basic blocks the same.
 ///
 ///{
 
 /// Return the block that is the representing block for @p RN.
 static inline BasicBlock *getRegionNodeBasicBlock(RegionNode *RN) {
   return RN->isSubRegion() ? RN->getNodeAs<Region>()->getEntry()
                            : RN->getNodeAs<BasicBlock>();
if (Affinator.hasNSWAddRecForLoop(L))
     return true;
 
   isl::set UnboundedCtx = Parts.first.params();
   recordAssumption(INFINITELOOP, UnboundedCtx,
                    HeaderBB->getTerminator()->getDebugLoc(), AS_RESTRICTION);
   return true;
 }
 
-MemoryAccess *Scop::lookupBasePtrAccess(MemoryAccess *MA) {
-  Value *PointerBase = MA->getOriginalBaseAddr();
-
-  auto *PointerBaseInst = dyn_cast<Instruction>(PointerBase);
-  if (!PointerBaseInst)
-    return nullptr;
-
-  auto *BasePtrStmt = getStmtFor(PointerBaseInst);
-  if (!BasePtrStmt)
-    return nullptr;
-
-  return BasePtrStmt->getArrayAccessOrNULLFor(PointerBaseInst);
-}
-
-bool Scop::buildAliasChecks(AliasAnalysis &AA) {
-  if (!PollyUseRuntimeAliasChecks)
-    return true;
-
-  if (buildAliasGroups(AA)) {
-    // Aliasing assumptions do not go through addAssumption but we still want to
-    // collect statistics so we do it here explicitly.
-    if (MinMaxAliasGroups.size())
-      AssumptionsAliasing++;
-    return true;
-  }
-
-  // If a problem occurs while building the alias groups we need to delete
-  // this SCoP and pretend it wasn't valid in the first place. To this end
-  // we make the assumed context infeasible.
-  invalidate(ALIASING, DebugLoc());
-
-  LLVM_DEBUG(
-      dbgs() << "\n\nNOTE: Run time checks for " << getNameStr()
-             << " could not be created as the number of parameters involved "
-                "is too high. The SCoP will be "
-                "dismissed.\nUse:\n\t--polly-rtc-max-parameters=X\nto adjust "
-                "the maximal number of parameters but be advised that the "
-                "compile time might increase exponentially.\n\n");
-  return false;
-}
-
-std::tuple<Scop::AliasGroupVectorTy, DenseSet<const ScopArrayInfo *>>
-Scop::buildAliasGroupsForAccesses(AliasAnalysis &AA) {
-  AliasSetTracker AST(AA);
-
-  DenseMap<Value *, MemoryAccess *> PtrToAcc;
-  DenseSet<const ScopArrayInfo *> HasWriteAccess;
-  for (ScopStmt &Stmt : *this) {
-
-    isl::set StmtDomain = Stmt.getDomain();
-    bool StmtDomainEmpty = StmtDomain.is_empty();
-
-    // Statements with an empty domain will never be executed.
-    if (StmtDomainEmpty)
-      continue;
-
-    for (MemoryAccess *MA : Stmt) {
-      if (MA->isScalarKind())
-        continue;
-      if (!MA->isRead())
-        HasWriteAccess.insert(MA->getScopArrayInfo());
-      MemAccInst Acc(MA->getAccessInstruction());
-      if (MA->isRead() && isa<MemTransferInst>(Acc))
-        PtrToAcc[cast<MemTransferInst>(Acc)->getRawSource()] = MA;
-      else
-        PtrToAcc[Acc.getPointerOperand()] = MA;
-      AST.add(Acc);
-    }
-  }
-
-  AliasGroupVectorTy AliasGroups;
-  for (AliasSet &AS : AST) {
-    if (AS.isMustAlias() || AS.isForwardingAliasSet())
-      continue;
-    AliasGroupTy AG;
-    for (auto &PR : AS)
-      AG.push_back(PtrToAcc[PR.getValue()]);
-    if (AG.size() < 2)
-      continue;
-    AliasGroups.push_back(std::move(AG));
-  }
-
-  return std::make_tuple(AliasGroups, HasWriteAccess);
-}
-
-void Scop::splitAliasGroupsByDomain(AliasGroupVectorTy &AliasGroups) {
-  for (unsigned u = 0; u < AliasGroups.size(); u++) {
-    AliasGroupTy NewAG;
-    AliasGroupTy &AG = AliasGroups[u];
-    AliasGroupTy::iterator AGI = AG.begin();
-    isl::set AGDomain = getAccessDomain(*AGI);
-    while (AGI != AG.end()) {
-      MemoryAccess *MA = *AGI;
-      isl::set MADomain = getAccessDomain(MA);
-      if (AGDomain.is_disjoint(MADomain)) {
-        NewAG.push_back(MA);
-        AGI = AG.erase(AGI);
-      } else {
-        AGDomain = AGDomain.unite(MADomain);
-        AGI++;
-      }
-    }
-    if (NewAG.size() > 1)
-      AliasGroups.push_back(std::move(NewAG));
-  }
-}
-
-bool Scop::buildAliasGroups(AliasAnalysis &AA) {
-  // To create sound alias checks we perform the following steps:
-  //   o) We partition each group into read only and non read only accesses.
-  //   o) For each group with more than one base pointer we then compute minimal
-  //      and maximal accesses to each array of a group in read only and non
-  //      read only partitions separately.
-  AliasGroupVectorTy AliasGroups;
-  DenseSet<const ScopArrayInfo *> HasWriteAccess;
-
-  std::tie(AliasGroups, HasWriteAccess) = buildAliasGroupsForAccesses(AA);
-
-  splitAliasGroupsByDomain(AliasGroups);
-
-  for (AliasGroupTy &AG : AliasGroups) {
-    if (!hasFeasibleRuntimeContext())
-      return false;
-
-    {
-      IslMaxOperationsGuard MaxOpGuard(getIslCtx().get(), OptComputeOut);
-      bool Valid = buildAliasGroup(AG, HasWriteAccess);
-      if (!Valid)
-        return false;
-    }
-    if (isl_ctx_last_error(getIslCtx().get()) == isl_error_quota) {
-      invalidate(COMPLEXITY, DebugLoc());
-      return false;
-    }
-  }
-
-  return true;
-}
-
-bool Scop::buildAliasGroup(Scop::AliasGroupTy &AliasGroup,
-                           DenseSet<const ScopArrayInfo *> HasWriteAccess) {
-  AliasGroupTy ReadOnlyAccesses;
-  AliasGroupTy ReadWriteAccesses;
-  SmallPtrSet<const ScopArrayInfo *, 4> ReadWriteArrays;
-  SmallPtrSet<const ScopArrayInfo *, 4> ReadOnlyArrays;
-
-  if (AliasGroup.size() < 2)
-    return true;
-
-  for (MemoryAccess *Access : AliasGroup) {
-    ORE.emit(OptimizationRemarkAnalysis(DEBUG_TYPE, "PossibleAlias",
-                                        Access->getAccessInstruction())
-             << "Possibly aliasing pointer, use restrict keyword.");
-    const ScopArrayInfo *Array = Access->getScopArrayInfo();
-    if (HasWriteAccess.count(Array)) {
-      ReadWriteArrays.insert(Array);
-      ReadWriteAccesses.push_back(Access);
-    } else {
-      ReadOnlyArrays.insert(Array);
-      ReadOnlyAccesses.push_back(Access);
-    }
-  }
-
-  // If there are no read-only pointers, and less than two read-write pointers,
-  // no alias check is needed.
-  if (ReadOnlyAccesses.empty() && ReadWriteArrays.size() <= 1)
-    return true;
-
-  // If there is no read-write pointer, no alias check is needed.
-  if (ReadWriteArrays.empty())
-    return true;
-
-  // For non-affine accesses, no alias check can be generated as we cannot
-  // compute a sufficiently tight lower and upper bound: bail out.
-  for (MemoryAccess *MA : AliasGroup) {
-    if (!MA->isAffine()) {
-      invalidate(ALIASING, MA->getAccessInstruction()->getDebugLoc(),
-                 MA->getAccessInstruction()->getParent());
-      return false;
-    }
-  }
-
-  // Ensure that for all memory accesses for which we generate alias checks,
-  // their base pointers are available.
-  for (MemoryAccess *MA : AliasGroup) {
-    if (MemoryAccess *BasePtrMA = lookupBasePtrAccess(MA))
-      addRequiredInvariantLoad(
-          cast<LoadInst>(BasePtrMA->getAccessInstruction()));
-  }
-
-  MinMaxAliasGroups.emplace_back();
-  MinMaxVectorPairTy &pair = MinMaxAliasGroups.back();
-  MinMaxVectorTy &MinMaxAccessesReadWrite = pair.first;
-  MinMaxVectorTy &MinMaxAccessesReadOnly = pair.second;
-
-  bool Valid;
-
-  Valid =
-      calculateMinMaxAccess(ReadWriteAccesses, *this, MinMaxAccessesReadWrite);
-
-  if (!Valid)
-    return false;
-
-  // Bail out if the number of values we need to compare is too large.
-  // This is important as the number of comparisons grows quadratically with
-  // the number of values we need to compare.
-  if (MinMaxAccessesReadWrite.size() + ReadOnlyArrays.size() >
-      RunTimeChecksMaxArraysPerGroup)
-    return false;
-
-  Valid =
-      calculateMinMaxAccess(ReadOnlyAccesses, *this, MinMaxAccessesReadOnly);
-
-  if (!Valid)
-    return false;
-
-  return true;
-}
-
 /// Get the smallest loop that contains @p S but is not in @p S.
 static Loop *getLoopSurroundingScop(Scop &S, LoopInfo &LI) {
   // Start with the smallest loop containing the entry and expand that
   // loop until it contains all blocks in the region. If there is a loop
   // containing all blocks in the region check if it is itself contained
   // and if so take the parent loop as it will be the smallest containing
   // the region but not contained by it.
   Loop *L = LI.getLoopFor(S.getEntry());
bool Scop::hasFeasibleRuntimeContext() const {
 
   bool IsFeasible = !(PositiveContext.is_empty() ||
                       PositiveContext.is_subset(NegativeContext));
   if (!IsFeasible)
     return false;
 
   auto DomainContext = getDomains().params();
   IsFeasible = !DomainContext.is_subset(NegativeContext);
-  IsFeasible &= !Context.is_subset(NegativeContext);
+  IsFeasible &= !getContext().is_subset(NegativeContext);
 
   return IsFeasible;
 }
 
+isl::set Scop::addNonEmptyDomainConstraints(isl::set C) const {
+  isl::set DomainContext = getDomains().params();
+  return C.intersect_params(DomainContext);
+}
+
+MemoryAccess *Scop::lookupBasePtrAccess(MemoryAccess *MA) {
+  Value *PointerBase = MA->getOriginalBaseAddr();
+
+  auto *PointerBaseInst = dyn_cast<Instruction>(PointerBase);
+  if (!PointerBaseInst)
+    return nullptr;
+
+  auto *BasePtrStmt = getStmtFor(PointerBaseInst);
+  if (!BasePtrStmt)
+    return nullptr;
+
+  return BasePtrStmt->getArrayAccessOrNULLFor(PointerBaseInst);
+}
+
 static std::string toString(AssumptionKind Kind) {
   switch (Kind) {
   case ALIASING:
     return "No-aliasing";
   case INBOUNDS:
     return "Inbounds";
   case WRAPPING:
     return "No-overflows";
for (Use &Use : Inst->uses()) {
     // SCoP anymore.
     if (hasSingleExitEdge() && isa<PHINode>(Use.getUser()) &&
         isExit(cast<PHINode>(Use.getUser())->getParent()))
       return true;
   }
   return false;
 }
 
+void Scop::incrementNumberOfAliasingAssumptions(unsigned step) {
+  AssumptionsAliasing += step;
+}
+
 Scop::ScopStatistics Scop::getStatistics() const {
   ScopStatistics Result;
 #if !defined(NDEBUG) || defined(LLVM_ENABLE_STATS)
   auto LoopStat = ScopDetection::countBeneficialLoops(&R, *SE, *getLI(), 0);
 
   int NumTotalLoops = LoopStat.NumLoops;
   Result.NumBoxedLoops = getBoxedLoops().size();
   Result.NumAffineLoops = NumTotalLoops - Result.NumBoxedLoops;