[Polly] [WIP] Move Scop::DomainMap to a local scope

[nandini12396]

Hello Sir,

I am not sure if this is a good idea. Please comment whether I should proceed with this.

lib/Support/SCEVAffinator.cpp

138 ↗

(On Diff #106804)

No idea how to pass DomainMap here.

lib/Transform/Simplify.cpp

310 ↗

(On Diff #106804)

No idea how to pass DomainMap here.

[grosser]

Hi Nandini,

this looks very good. Here some feedback regarding your questions.

Best,
Tobias

lib/Transform/Simplify.cpp

310 ↗

(On Diff #106804)

Should not be needed any more after r308152,

[grosser]

And one more:

lib/Support/SCEVAffinator.cpp

138 ↗

(On Diff #106804)

I would try to pass the domain of BB rather than BB itself to getPwAff. You likely need to change a couple of the getPwAff declarations (there are various variants).

I suggest to do this in a separate patch, similar to how I committed 308152.

[nandini12396]

Rebased over D36056.

include/polly/ScopInfo.h

public:
   /// @param SourceRel  The source location.
   /// @param TargetRel  The target location.
   /// @param Domain     The original domain under which the copy statement would
   ///                   be executed.
   ScopStmt(Scop &parent, __isl_take isl_map *SourceRel,
            __isl_take isl_map *TargetRel, __isl_take isl_set *Domain);
 
   /// Initialize members after all MemoryAccesses have been added.
-  void init(LoopInfo &LI);
+  void init(LoopInfo &LI, DenseMap<BasicBlock *, isl::set> &DomainMap);
 
 private:
   /// Polyhedral description
   //@{
 
   /// The Scop containing this ScopStmt.
   Scop &Parent;
 
private:
   /// The closest loop that contains this statement.
   Loop *SurroundingLoop;
 
   /// Vector for Instructions in a BB.
   std::vector<Instruction *> Instructions;
 
   /// Build the statement.
   //@{
-  void buildDomain();
+  void buildDomain(DenseMap<BasicBlock *, isl::set> &DomainMap);
 
   /// Fill NestLoops with loops surrounding this statement.
   void collectSurroundingLoops();
 
   /// Build the access relation of all memory accesses.
   void buildAccessRelations();
 
   /// Detect and mark reductions in the ScopStmt
private:
   /// counter. By doing this, we guarantee that the context is deleted when we
   /// delete the last object that creates isl objects with the context.
   std::shared_ptr<isl_ctx> IslCtx;
 
   /// A map from basic blocks to vector of SCoP statements. Currently this
   /// vector comprises only of a single statement.
   DenseMap<BasicBlock *, std::vector<ScopStmt *>> StmtMap;
 
-  /// A map from basic blocks to their domains.
-  DenseMap<BasicBlock *, isl::set> DomainMap;
-
   /// Constraints on parameters.
   isl_set *Context;
 
   /// The affinator used to translate SCEVs to isl expressions.
   SCEVAffinator Affinator;
 
   typedef std::map<std::pair<AssertingVH<const Value>, MemoryKind>,
                    std::unique_ptr<ScopArrayInfo>>
private:
   /// block in the @p FinishedExitBlocks set so we can later skip edges from
   /// within the region to that block.
   ///
   /// @param BB                 The block for which the domain is currently
   ///                           propagated.
   /// @param BBLoop             The innermost affine loop surrounding @p BB.
   /// @param FinishedExitBlocks Set of region exits the domain was set for.
   /// @param LI                 The LoopInfo for the current function.
+  /// @param DomainMap        BB to Domain map for the BB of current region.
   /// @param InvalidDomainMap   BB to InvalidDomain map for the BB of current
   ///                           region.
   void propagateDomainConstraintsToRegionExit(
       BasicBlock *BB, Loop *BBLoop,
       SmallPtrSetImpl<BasicBlock *> &FinishedExitBlocks, LoopInfo &LI,
+      DenseMap<BasicBlock *, isl::set> &DomainMap,
       DenseMap<BasicBlock *, isl::set> &InvalidDomainMap);
 
   /// Compute the union of predecessor domains for @p BB.
   ///
   /// To compute the union of all domains of predecessors of @p BB this
   /// function applies similar reasoning on the CFG structure as described for
   ///   @see propagateDomainConstraintsToRegionExit
   ///
   /// @param BB     The block for which the predecessor domains are collected.
   /// @param Domain The domain under which BB is executed.
   /// @param DT     The DominatorTree for the current function.
   /// @param LI     The LoopInfo for the current function.
+  /// @param DomainMap        BB to Domain map for the BB of current region.
   ///
   /// @returns The domain under which @p BB is executed.
   __isl_give isl_set *
   getPredecessorDomainConstraints(BasicBlock *BB, __isl_keep isl_set *Domain,
-                                  DominatorTree &DT, LoopInfo &LI);
+                                  DominatorTree &DT, LoopInfo &LI,
+                                  DenseMap<BasicBlock *, isl::set> &DomainMap);
 
   /// Add loop carried constraints to the header block of the loop @p L.
   ///
   /// @param L                The loop to process.
   /// @param LI               The LoopInfo for the current function.
+  /// @param DomainMap        BB to Domain map for the BB of current region.
   /// @param InvalidDomainMap BB to InvalidDomain map for the BB of current
   ///                         region.
   ///
   /// @returns True if there was no problem and false otherwise.
   bool addLoopBoundsToHeaderDomain(
-      Loop *L, LoopInfo &LI,
+      Loop *L, LoopInfo &LI, DenseMap<BasicBlock *, isl::set> &DomainMap,
       DenseMap<BasicBlock *, isl::set> &InvalidDomainMap);
 
   /// Compute the branching constraints for each basic block in @p R.
   ///
   /// @param R                The region we currently build branching conditions
   ///                         for.
   /// @param DT               The DominatorTree for the current function.
   /// @param LI               The LoopInfo for the current function.
+  /// @param DomainMap        BB to Domain map for the BB of current region.
   /// @param InvalidDomainMap BB to InvalidDomain map for the BB of current
   ///                         region.
   ///
   /// @returns True if there was no problem and false otherwise.
   bool buildDomainsWithBranchConstraints(
       Region *R, DominatorTree &DT, LoopInfo &LI,
+      DenseMap<BasicBlock *, isl::set> &DomainMap,
       DenseMap<BasicBlock *, isl::set> &InvalidDomainMap);
 
   /// Propagate the domain constraints through the region @p R.
   ///
   /// @param R                The region we currently build branching conditions
   /// for.
   /// @param DT               The DominatorTree for the current function.
   /// @param LI               The LoopInfo for the current function.
+  /// @param DomainMap        BB to Domain map for the BB of current region.
   /// @param InvalidDomainMap BB to InvalidDomain map for the BB of current
   ///                         region.
   ///
   /// @returns True if there was no problem and false otherwise.
   bool propagateDomainConstraints(
       Region *R, DominatorTree &DT, LoopInfo &LI,
+      DenseMap<BasicBlock *, isl::set> &DomainMap,
       DenseMap<BasicBlock *, isl::set> &InvalidDomainMap);
 
   /// Propagate invalid domains of statements through @p R.
   ///
   /// This method will propagate invalid statement domains through @p R and at
   /// the same time add error block domains to them. Additionally, the domains
   /// of error statements and those only reachable via error statements will be
   /// replaced by an empty set. Later those will be removed completely.
   ///
   /// @param R                The currently traversed region.
   /// @param DT               The DominatorTree for the current function.
   /// @param LI               The LoopInfo for the current function.
+  /// @param DomainMap        BB to Domain map for the BB of current region.
   /// @param InvalidDomainMap BB to InvalidDomain map for the BB of current
   ///                         region.
   //
   /// @returns True if there was no problem and false otherwise.
   bool propagateInvalidStmtDomains(
       Region *R, DominatorTree &DT, LoopInfo &LI,
+      DenseMap<BasicBlock *, isl::set> &DomainMap,
       DenseMap<BasicBlock *, isl::set> &InvalidDomainMap);
 
   /// Compute the domain for each basic block in @p R.
   ///
   /// @param R                The region we currently traverse.
   /// @param DT               The DominatorTree for the current function.
   /// @param LI               The LoopInfo for the current function.
+  /// @param DomainMap        BB to Domain map for the BB of current region.
   /// @param InvalidDomainMap BB to InvalidDomain map for the BB of current
   ///                         region.
   ///
   /// @returns True if there was no problem and false otherwise.
   bool buildDomains(Region *R, DominatorTree &DT, LoopInfo &LI,
+                    DenseMap<BasicBlock *, isl::set> &DomainMap,
                     DenseMap<BasicBlock *, isl::set> &InvalidDomainMap);
 
   /// Add parameter constraints to @p C that imply a non-empty domain.
   __isl_give isl_set *addNonEmptyDomainConstraints(__isl_take isl_set *C) const;
 
   /// Return the access for the base ptr of @p MA if any.
   MemoryAccess *lookupBasePtrAccess(MemoryAccess *MA);
 
private:
   /// Create an id for @p Param and store it in the ParameterIds map.
   void createParameterId(const SCEV *Param);
 
   /// Build the Context of the Scop.
   void buildContext();
 
   /// Add user provided parameter constraints to context (source code).
   void addUserAssumptions(AssumptionCache &AC, DominatorTree &DT, LoopInfo &LI,
+                          DenseMap<BasicBlock *, isl::set> &DomainMap,
                           DenseMap<BasicBlock *, isl::set> &InvalidDomainMap);
 
   /// Add user provided parameter constraints to context (command line).
   void addUserContext();
 
   /// Add the bounds of the parameters to the context.
   void addParameterBounds();
 
private:
   ///                     to it should be deleted.
   void removeStmts(std::function<bool(ScopStmt &)> ShouldDelete);
 
   /// Removes @p Stmt from the StmtMap.
   void removeFromStmtMap(ScopStmt &Stmt);
 
   /// Removes all statements where the entry block of the statement does not
   /// have a corresponding domain in the domain map.
-  void removeStmtNotInDomainMap();
+  void removeStmtNotInDomainMap(DenseMap<BasicBlock *, isl::set> &DomainMap);
 
   /// Mark arrays that have memory accesses with FortranArrayDescriptor.
   void markFortranArrays();
 
   /// Finalize all access relations.
   ///
   /// When building up access relations, temporary access relations that
   /// correctly represent each individual access are constructed. However, these
public:
   ///             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_take isl_set *Set,
                         DebugLoc Loc, AssumptionSign Sign,
                         BasicBlock *BB = nullptr);
 
   /// Add all recorded assumptions to the assumed context.
-  void addRecordedAssumptions();
+  void addRecordedAssumptions(DenseMap<BasicBlock *, isl::set> &DomainMap);
 
   /// 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.
   ///
#endif
   ///
   /// This function is like @see Scop::getPwAff() but strips away the invalid
   /// domain part associated with the piecewise affine function.
   __isl_give isl_pw_aff *getPwAffOnly(const SCEV *E, BasicBlock *BB = nullptr);
 
   /// Return the domain of @p Stmt.
   ///
   /// @param Stmt The statement for which the conditions should be returned.
-  __isl_give isl_set *getDomainConditions(const ScopStmt *Stmt) const;
+  __isl_give isl_set *
+  getDomainConditions(DenseMap<BasicBlock *, isl::set> &DomainMap,
+                      const ScopStmt *Stmt) const;
 
   /// Return the domain of @p BB.
   ///
-  /// @param BB The block for which the conditions should be returned.
-  __isl_give isl_set *getDomainConditions(BasicBlock *BB) const;
+  /// @param DomainMap BB to Domain map for the BB of current region.
+  /// @param BB        The block for which the conditions should be returned.
+  __isl_give isl_set *
+  getDomainConditions(DenseMap<BasicBlock *, isl::set> &DomainMap,
+                      BasicBlock *BB) const;
 
   /// Get a union set containing the iteration domains of all statements.
   __isl_give isl_union_set *getDomains() const;
 
   /// Get a union map of all may-writes performed in the SCoP.
   __isl_give isl_union_map *getMayWrites();
 
   /// Get a union map of all must-writes performed in the SCoP.

lib/Analysis/ScopBuilder.cpp

for (auto GlobalReadPair : GlobalReads) {
     Instruction *GlobalRead = GlobalReadPair.second;
     for (auto *BP : ArrayBasePointers)
       addArrayAccess(GlobalReadStmt, MemAccInst(GlobalRead), MemoryAccess::READ,
                      BP, BP->getType(), false, {AF}, {nullptr}, GlobalRead);
   }
 
   scop->buildInvariantEquivalenceClasses();
 
+  /// A map from basic blocks to their domains.
+  DenseMap<BasicBlock *, isl::set> DomainMap;
+
   /// A map from basic blocks to their invalid domains.
   DenseMap<BasicBlock *, isl::set> InvalidDomainMap;
 
-  if (!scop->buildDomains(&R, DT, LI, InvalidDomainMap))
+  if (!scop->buildDomains(&R, DT, LI, DomainMap, InvalidDomainMap))
     return;
 
-  scop->addUserAssumptions(AC, DT, LI, InvalidDomainMap);
+  scop->addUserAssumptions(AC, DT, LI, DomainMap, InvalidDomainMap);
 
   // Initialize the invalid domain.
   for (ScopStmt &Stmt : scop->Stmts)
     if (Stmt.isBlockStmt())
       Stmt.setInvalidDomain(InvalidDomainMap[Stmt.getEntryBlock()].copy());
     else
       Stmt.setInvalidDomain(
           InvalidDomainMap[getRegionNodeBasicBlock(Stmt.getRegion()->getNode())]
               .copy());
 
   // Remove empty statements.
   // Exit early in case there are no executable statements left in this scop.
-  scop->removeStmtNotInDomainMap();
+  scop->removeStmtNotInDomainMap(DomainMap);
   scop->simplifySCoP(false);
   if (scop->isEmpty())
     return;
 
   // The ScopStmts now have enough information to initialize themselves.
   for (ScopStmt &Stmt : *scop)
-    Stmt.init(LI);
+    Stmt.init(LI, DomainMap);
 
   // Check early for a feasible runtime context.
   if (!scop->hasFeasibleRuntimeContext())
     return;
 
   // Check early for profitability. Afterwards it cannot change anymore,
   // only the runtime context could become infeasible.
   if (!scop->isProfitable(UnprofitableScalarAccs)) {
     scop->invalidate(PROFITABLE, DebugLoc());
     return;
   }
 
   scop->buildSchedule(LI);
 
   scop->finalizeAccesses();
 
   scop->realignParams();
   scop->addUserContext();
 
   // After the context was fully constructed, thus all our knowledge about
   // the parameters is in there, we add all recorded assumptions to the
   // assumed/invalid context.
-  scop->addRecordedAssumptions();
+  scop->addRecordedAssumptions(DomainMap);
 
   scop->simplifyContexts();
   if (!scop->buildAliasChecks(AA))
     return;
 
   scop->hoistInvariantLoads();
   scop->canonicalizeDynamicBasePtrs();
   scop->verifyInvariantLoads();

lib/Analysis/ScopInfo.cpp

buildConditionSets(Scop &S, BasicBlock *BB, TerminatorInst *TI, Loop *L,
 
   Value *Condition = getConditionFromTerminator(TI);
   assert(Condition && "No condition for Terminator");
 
   return buildConditionSets(S, BB, Condition, TI, L, Domain, InvalidDomain,
                             ConditionSets);
 }
 
-void ScopStmt::buildDomain() {
+void ScopStmt::buildDomain(DenseMap<BasicBlock *, isl::set> &DomainMap) {
   isl_id *Id = isl_id_alloc(getIslCtx(), getBaseName(), this);
 
-  Domain = getParent()->getDomainConditions(this);
+  Domain = getParent()->getDomainConditions(DomainMap, this);
   Domain = isl_set_set_tuple_id(Domain, Id);
 }
 
 void ScopStmt::collectSurroundingLoops() {
   for (unsigned u = 0, e = isl_set_n_dim(Domain); u < e; u++) {
     isl_id *DimId = isl_set_get_dim_id(Domain, isl_dim_set, u);
     NestLoops.push_back(static_cast<Loop *>(isl_id_get_user(DimId)));
     isl_id_free(DimId);
ScopStmt::ScopStmt(Scop &parent, __isl_take isl_map *SourceRel,
   addAccess(Access);
   SourceRel = isl_map_set_tuple_id(SourceRel, isl_dim_in, isl_id_copy(Id));
   Access = new MemoryAccess(this, MemoryAccess::AccessType::READ,
                             isl::manage(SourceRel));
   parent.addAccessFunction(Access);
   addAccess(Access);
 }
 
-void ScopStmt::init(LoopInfo &LI) {
+void ScopStmt::init(LoopInfo &LI, DenseMap<BasicBlock *, isl::set> &DomainMap) {
   assert(!Domain && "init must be called only once");
 
-  buildDomain();
+  buildDomain(DomainMap);
   collectSurroundingLoops();
   buildAccessRelations();
 
   if (DetectReductions)
     checkForReductions();
 }
 
 /// Collect loads which might form a reduction chain with @p StoreMA.

 }
 
 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> &DomainMap,
     DenseMap<BasicBlock *, isl::set> &InvalidDomainMap) {
+
   for (auto &Assumption : AC.assumptions()) {
     auto *CI = dyn_cast_or_null<CallInst>(Assumption);
     if (!CI || CI->getNumArgOperands() != 1)
       continue;
 
     bool InScop = contains(CI);
     if (!InScop && !isDominatedBy(DT, CI->getParent()))
       continue;
for (auto &Assumption : AC.assumptions()) {
     if (InScop) {
       AssumptionCtx = isl_set_complement(isl_set_params(ConditionSets[1]));
       isl_set_free(ConditionSets[0]);
     } else {
       AssumptionCtx = isl_set_complement(ConditionSets[1]);
       AssumptionCtx = isl_set_intersect(AssumptionCtx, ConditionSets[0]);
     }
 
-    // Project out newly introduced parameters as they are not otherwise useful.
+    // Project out newly introduced parameters as they are not otherwise
+    // useful.
     if (!NewParams.empty()) {
       for (unsigned u = 0; u < isl_set_n_param(AssumptionCtx); u++) {
         auto *Id = isl_set_get_dim_id(AssumptionCtx, isl_dim_param, u);
         auto *Param = static_cast<const SCEV *>(isl_id_get_user(Id));
         isl_id_free(Id);
 
         if (!NewParams.count(Param))
           continue;
void Scop::addParameterBounds() {
   for (auto *Parameter : Parameters) {
     ConstantRange SRange = SE->getSignedRange(Parameter);
     Context =
         addRangeBoundsToSet(give(Context), SRange, PDim++, isl::dim::param)
             .release();
   }
 }
 
-// We use the outermost dimension to generate GPU transfers for Fortran arrays
-// even when the array bounds are not known statically. To do so, we need the
-// outermost dimension information. We add this into the context so that the
-// outermost dimension is available during codegen.
-// We currently do not care about dimensions other than the outermost
-// dimension since it doesn't affect transfers.
+// We use the outermost dimension to generate GPU transfers for Fortran
+// arrays even when the array bounds are not known statically. To do so, we
+// need the outermost dimension information. We add this into the context so
+// that the outermost dimension is available during codegen. We currently do
+// not care about dimensions other than the outermost dimension since it
+// doesn't affect transfers.
 static isl_set *addFortranArrayOutermostDimParams(__isl_give isl_set *Context,
                                                   Scop::array_range Arrays) {
 
   std::vector<isl_id *> OutermostSizeIds;
   for (auto Array : Arrays) {
-    // To check if an array is a Fortran array, we check if it has a isl_pw_aff
-    // for its outermost dimension. Fortran arrays will have this since the
-    // outermost dimension size can be picked up from their runtime description.
+    // To check if an array is a Fortran array, we check if it has a
+    // isl_pw_aff for its outermost dimension. Fortran arrays will have this
+    // since the outermost dimension size can be picked up from their
+    // runtime description.
     // TODO: actually need to check if it has a FAD, but for now this works.
     if (Array->getNumberOfDimensions() > 0) {
       isl_pw_aff *PwAff = Array->getDimensionSizePw(0).release();
       if (!PwAff)
         continue;
 
       isl_id *Id = isl_pw_aff_get_dim_id(PwAff, isl_dim_param, 0);
       isl_pw_aff_free(PwAff);
void Scop::realignParams() {
   // Simplify the schedule according to the context too.
   Schedule = isl_schedule_gist_domain_params(Schedule, getContext());
 }
 
 static __isl_give isl_set *
 simplifyAssumptionContext(__isl_take isl_set *AssumptionContext,
                           const Scop &S) {
   // If we have modeled all blocks in the SCoP that have side effects we can
-  // simplify the context with the constraints that are needed for anything to
-  // be executed at all. However, if we have error blocks in the SCoP we already
-  // assumed some parameter combinations cannot occur and removed them from the
-  // domains, thus we cannot use the remaining domain to simplify the
-  // assumptions.
+  // simplify the context with the constraints that are needed for anything
+  // to be executed at all. However, if we have error blocks in the SCoP we
+  // already assumed some parameter combinations cannot occur and removed
+  // them from the domains, thus we cannot use the remaining domain to
+  // simplify the assumptions.
   if (!S.hasErrorBlock()) {
     isl_set *DomainParameters = isl_union_set_params(S.getDomains());
     AssumptionContext =
         isl_set_gist_params(AssumptionContext, DomainParameters);
   }
 
   AssumptionContext = isl_set_gist_params(AssumptionContext, S.getContext());
   return AssumptionContext;
 }
 
 void Scop::simplifyContexts() {
   // The parameter constraints of the iteration domains give us a set of
   // constraints that need to hold for all cases where at least a single
   // statement iteration is executed in the whole scop. We now simplify the
   // assumed context under the assumption that such constraints hold and at
   // least a single statement iteration is executed. For cases where no
   // statement instances are executed, the assumptions we have taken about
   // the executed code do not matter and can be changed.
   //
   // WARNING: This only holds if the assumptions we have taken do not reduce
   //          the set of statement instances that are executed. Otherwise we
   //          may run into a case where the iteration domains suggest that
-  //          for a certain set of parameter constraints no code is executed,
-  //          but in the original program some computation would have been
-  //          performed. In such a case, modifying the run-time conditions and
-  //          possibly influencing the run-time check may cause certain scops
-  //          to not be executed.
+  //          for a certain set of parameter constraints no code is
+  //          executed, but in the original program some computation would
+  //          have been performed. In such a case, modifying the run-time
+  //          conditions and possibly influencing the run-time check may
+  //          cause certain scops to not be executed.
   //
   // Example:
   //
   //   When delinearizing the following code:
   //
   //     for (long i = 0; i < 100; i++)
   //       for (long j = 0; j < m; j++)
   //         A[i+p][j] = 1.0;
   //
   //   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.
+  //   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 = isl_set_align_params(InvalidContext, getParamSpace());
 }
 
 /// Add the minimal/maximal access in @p Set to @p User.
 static isl::stat
 buildMinMaxAccess(isl::set Set, Scop::MinMaxVectorTy &MinMaxAccesses, Scop &S) {
   isl::pw_multi_aff MinPMA, MaxPMA;

 }
 
 /// Return the smallest loop surrounding @p RN.
 static inline Loop *getRegionNodeLoop(RegionNode *RN, LoopInfo &LI) {
   if (!RN->isSubRegion()) {
     BasicBlock *BB = RN->getNodeAs<BasicBlock>();
     Loop *L = LI.getLoopFor(BB);
 
-    // Unreachable statements are not considered to belong to a LLVM loop, as
-    // they are not part of an actual loop in the control flow graph.
-    // Nevertheless, we handle certain unreachable statements that are common
-    // when modeling run-time bounds checks as being part of the loop to be
-    // able to model them and to later eliminate the run-time bounds checks.
+    // Unreachable statements are not considered to belong to a LLVM loop,
+    // as they are not part of an actual loop in the control flow graph.
+    // Nevertheless, we handle certain unreachable statements that are
+    // common when modeling run-time bounds checks as being part of the loop
+    // to be able to model them and to later eliminate the run-time bounds
+    // checks.
     //
     // Specifically, for basic blocks that terminate in an unreachable and
     // where the immediate predecessor is part of a loop, we assume these
     // basic blocks belong to the loop the predecessor belongs to. This
     // allows us to model the following code.
     //
     // for (i = 0; i < N; i++) {
     //   if (i > 1024)

 static inline __isl_give isl_set *addDomainDimId(__isl_take isl_set *Domain,
                                                  unsigned Dim, Loop *L) {
   Domain = isl_set_lower_bound_si(Domain, isl_dim_set, Dim, -1);
   isl_id *DimId =
       isl_id_alloc(isl_set_get_ctx(Domain), nullptr, static_cast<void *>(L));
   return isl_set_set_dim_id(Domain, isl_dim_set, Dim, DimId);
 }
 
-__isl_give isl_set *Scop::getDomainConditions(const ScopStmt *Stmt) const {
-  return getDomainConditions(Stmt->getEntryBlock());
+__isl_give isl_set *
+Scop::getDomainConditions(DenseMap<BasicBlock *, isl::set> &DomainMap,
+                          const ScopStmt *Stmt) const {
+  return getDomainConditions(DomainMap, Stmt->getEntryBlock());
 }
 
-__isl_give isl_set *Scop::getDomainConditions(BasicBlock *BB) const {
+__isl_give isl_set *
+Scop::getDomainConditions(DenseMap<BasicBlock *, isl::set> &DomainMap,
+                          BasicBlock *BB) const {
   auto DIt = DomainMap.find(BB);
   if (DIt != DomainMap.end())
     return DIt->getSecond().copy();
 
   auto &RI = *R.getRegionInfo();
   auto *BBR = RI.getRegionFor(BB);
   while (BBR->getEntry() == BB)
     BBR = BBR->getParent();
-  return getDomainConditions(BBR->getEntry());
+  return getDomainConditions(DomainMap, BBR->getEntry());
 }
 
 bool Scop::buildDomains(Region *R, DominatorTree &DT, LoopInfo &LI,
+                        DenseMap<BasicBlock *, isl::set> &DomainMap,
                         DenseMap<BasicBlock *, isl::set> &InvalidDomainMap) {
 
   bool IsOnlyNonAffineRegion = isNonAffineSubRegion(R);
   auto *EntryBB = R->getEntry();
   auto *L = IsOnlyNonAffineRegion ? nullptr : LI.getLoopFor(EntryBB);
   int LD = getRelativeLoopDepth(L);
   auto *S = isl_set_universe(isl_space_set_alloc(getIslCtx(), 0, LD + 1));
 
   while (LD-- >= 0) {
     S = addDomainDimId(S, LD + 1, L);
     L = L->getParentLoop();
   }
 
   InvalidDomainMap[EntryBB] = isl::manage(isl_set_empty(isl_set_get_space(S)));
   DomainMap[EntryBB] = isl::manage(S);
 
   if (IsOnlyNonAffineRegion)
     return !containsErrorBlock(R->getNode(), *R, LI, DT);
 
-  if (!buildDomainsWithBranchConstraints(R, DT, LI, InvalidDomainMap))
+  if (!buildDomainsWithBranchConstraints(R, DT, LI, DomainMap,
+                                         InvalidDomainMap))
     return false;
 
-  if (!propagateDomainConstraints(R, DT, LI, InvalidDomainMap))
+  if (!propagateDomainConstraints(R, DT, LI, DomainMap, InvalidDomainMap))
     return false;
 
   // Error blocks and blocks dominated by them have been assumed to never be
-  // executed. Representing them in the Scop does not add any value. In fact,
-  // it is likely to cause issues during construction of the ScopStmts. The
-  // contents of error blocks have not been verified to be expressible and
-  // will cause problems when building up a ScopStmt for them.
-  // Furthermore, basic blocks dominated by error blocks may reference
-  // instructions in the error block which, if the error block is not modeled,
-  // can themselves not be constructed properly. To this end we will replace
-  // the domains of error blocks and those only reachable via error blocks
-  // with an empty set. Additionally, we will record for each block under which
-  // parameter combination it would be reached via an error block in its
-  // InvalidDomain. This information is needed during load hoisting.
-  if (!propagateInvalidStmtDomains(R, DT, LI, InvalidDomainMap))
+  // executed. Representing them in the Scop does not add any value. In
+  // fact, it is likely to cause issues during construction of the
+  // ScopStmts. The contents of error blocks have not been verified to be
+  // expressible and will cause problems when building up a ScopStmt for
+  // them. Furthermore, basic blocks dominated by error blocks may reference
+  // instructions in the error block which, if the error block is not
+  // modeled, can themselves not be constructed properly. To this end we
+  // will replace the domains of error blocks and those only reachable via
+  // error blocks with an empty set. Additionally, we will record for each
+  // block under which parameter combination it would be reached via an
+  // error block in its InvalidDomain. This information is needed during
+  // load hoisting.
+  if (!propagateInvalidStmtDomains(R, DT, LI, DomainMap, InvalidDomainMap))
     return false;
 
   return true;
 }
 
 /// Adjust the dimensions of @p Dom that was constructed for @p OldL
 ///        to be compatible to domains constructed for loop @p NewL.
 ///
if (OldDepth == NewDepth) {
     Dom = isl_set_project_out(Dom, isl_dim_set, NumDim - Diff, Diff);
   }
 
   return Dom;
 }
 
 bool Scop::propagateInvalidStmtDomains(
     Region *R, DominatorTree &DT, LoopInfo &LI,
+    DenseMap<BasicBlock *, isl::set> &DomainMap,
     DenseMap<BasicBlock *, isl::set> &InvalidDomainMap) {
 
   ReversePostOrderTraversal<Region *> RTraversal(R);
   for (auto *RN : RTraversal) {
 
-    // Recurse for affine subregions but go on for basic blocks and non-affine
-    // subregions.
+    // Recurse for affine subregions but go on for basic blocks and
+    // non-affine subregions.
     if (RN->isSubRegion()) {
       Region *SubRegion = RN->getNodeAs<Region>();
       if (!isNonAffineSubRegion(SubRegion)) {
-        propagateInvalidStmtDomains(SubRegion, DT, LI, InvalidDomainMap);
+        propagateInvalidStmtDomains(SubRegion, DT, LI, DomainMap,
+                                    InvalidDomainMap);
         continue;
       }
     }
 
     bool ContainsErrorBlock = containsErrorBlock(RN, getRegion(), LI, DT);
     BasicBlock *BB = getRegionNodeBasicBlock(RN);
     isl::set &Domain = DomainMap[BB];
     assert(Domain && "Cannot propagate a nullptr");
bool Scop::propagateInvalidStmtDomains(
   }
 
   return true;
 }
 
 void Scop::propagateDomainConstraintsToRegionExit(
     BasicBlock *BB, Loop *BBLoop,
     SmallPtrSetImpl<BasicBlock *> &FinishedExitBlocks, LoopInfo &LI,
+    DenseMap<BasicBlock *, isl::set> &DomainMap,
     DenseMap<BasicBlock *, isl::set> &InvalidDomainMap) {
 
-  // Check if the block @p BB is the entry of a region. If so we propagate it's
-  // domain to the exit block of the region. Otherwise we are done.
+  // Check if the block @p BB is the entry of a region. If so we propagate
+  // it's domain to the exit block of the region. Otherwise we are done.
   auto *RI = R.getRegionInfo();
   auto *BBReg = RI ? RI->getRegionFor(BB) : nullptr;
   auto *ExitBB = BBReg ? BBReg->getExit() : nullptr;
   if (!BBReg || BBReg->getEntry() != BB || !contains(ExitBB))
     return;
 
-  // Do not propagate the domain if there is a loop backedge inside the region
-  // that would prevent the exit block from being executed.
+  // Do not propagate the domain if there is a loop backedge inside the
+  // region that would prevent the exit block from being executed.
   auto *L = BBLoop;
   while (L && contains(L)) {
     SmallVector<BasicBlock *, 4> LatchBBs;
     BBLoop->getLoopLatches(LatchBBs);
     for (auto *LatchBB : LatchBBs)
       if (BB != LatchBB && BBReg->contains(LatchBB))
         return;
     L = L->getParentLoop();
   }
 
   isl::set Domain = DomainMap[BB];
   assert(Domain && "Cannot propagate a nullptr");
 
   Loop *ExitBBLoop = getFirstNonBoxedLoopFor(ExitBB, LI, getBoxedLoops());
 
-  // Since the dimensions of @p BB and @p ExitBB might be different we have to
-  // adjust the domain before we can propagate it.
+  // Since the dimensions of @p BB and @p ExitBB might be different we have
+  // to adjust the domain before we can propagate it.
   isl::set AdjustedDomain = isl::manage(
       adjustDomainDimensions(*this, Domain.copy(), BBLoop, ExitBBLoop));
   isl::set &ExitDomain = DomainMap[ExitBB];
 
   // If the exit domain is not yet created we set it otherwise we "add" the
   // current domain.
   ExitDomain = ExitDomain ? AdjustedDomain.unite(ExitDomain) : AdjustedDomain;
 
   // Initialize the invalid domain.
   InvalidDomainMap[ExitBB] = ExitDomain.empty(ExitDomain.get_space());
 
   FinishedExitBlocks.insert(ExitBB);
 }
 
 bool Scop::buildDomainsWithBranchConstraints(
     Region *R, DominatorTree &DT, LoopInfo &LI,
+    DenseMap<BasicBlock *, isl::set> &DomainMap,
     DenseMap<BasicBlock *, isl::set> &InvalidDomainMap) {
 
   // To create the domain for each block in R we iterate over all blocks and
-  // subregions in R and propagate the conditions under which the current region
-  // element is executed. To this end we iterate in reverse post order over R as
-  // it ensures that we first visit all predecessors of a region node (either a
-  // basic block or a subregion) before we visit the region node itself.
-  // Initially, only the domain for the SCoP region entry block is set and from
-  // there we propagate the current domain to all successors, however we add the
-  // condition that the successor is actually executed next.
-  // As we are only interested in non-loop carried constraints here we can
-  // simply skip loop back edges.
+  // subregions in R and propagate the conditions under which the current
+  // region element is executed. To this end we iterate in reverse post
+  // order over R as it ensures that we first visit all predecessors of a
+  // region node (either a basic block or a subregion) before we visit the
+  // region node itself. Initially, only the domain for the SCoP region
+  // entry block is set and from there we propagate the current domain to
+  // all successors, however we add the condition that the successor is
+  // actually executed next. As we are only interested in non-loop carried
+  // constraints here we can simply skip loop back edges.
 
   SmallPtrSet<BasicBlock *, 8> FinishedExitBlocks;
   ReversePostOrderTraversal<Region *> RTraversal(R);
   for (auto *RN : RTraversal) {
 
-    // Recurse for affine subregions but go on for basic blocks and non-affine
-    // subregions.
+    // Recurse for affine subregions but go on for basic blocks and
+    // non-affine subregions.
     if (RN->isSubRegion()) {
       Region *SubRegion = RN->getNodeAs<Region>();
       if (!isNonAffineSubRegion(SubRegion)) {
-        if (!buildDomainsWithBranchConstraints(SubRegion, DT, LI,
+        if (!buildDomainsWithBranchConstraints(SubRegion, DT, LI, DomainMap,
                                                InvalidDomainMap))
           return false;
         continue;
       }
     }
 
     if (containsErrorBlock(RN, getRegion(), LI, DT))
       HasErrorBlock = true;
 
     BasicBlock *BB = getRegionNodeBasicBlock(RN);
     TerminatorInst *TI = BB->getTerminator();
 
     if (isa<UnreachableInst>(TI))
       continue;
 
     isl::set Domain = DomainMap.lookup(BB);
     if (!Domain)
       continue;
     MaxLoopDepth = std::max(MaxLoopDepth, isl_set_n_dim(Domain.get()));
 
     auto *BBLoop = getRegionNodeLoop(RN, LI);
     // Propagate the domain from BB directly to blocks that have a superset
-    // domain, at the moment only region exit nodes of regions that start in BB.
+    // domain, at the moment only region exit nodes of regions that start in
+    // BB.
     propagateDomainConstraintsToRegionExit(BB, BBLoop, FinishedExitBlocks, LI,
-                                           InvalidDomainMap);
+                                           DomainMap, InvalidDomainMap);
 
-    // If all successors of BB have been set a domain through the propagation
-    // above we do not need to build condition sets but can just skip this
-    // block. However, it is important to note that this is a local property
-    // with regards to the region @p R. To this end FinishedExitBlocks is a
-    // local variable.
+    // If all successors of BB have been set a domain through the
+    // propagation above we do not need to build condition sets but can just
+    // skip this block. However, it is important to note that this is a
+    // local property with regards to the region @p R. To this end
+    // FinishedExitBlocks is a local variable.
     auto IsFinishedRegionExit = [&FinishedExitBlocks](BasicBlock *SuccBB) {
       return FinishedExitBlocks.count(SuccBB);
     };
     if (std::all_of(succ_begin(BB), succ_end(BB), IsFinishedRegionExit))
       continue;
 
-    // Build the condition sets for the successor nodes of the current region
-    // node. If it is a non-affine subregion we will always execute the single
-    // exit node, hence the single entry node domain is the condition set. For
-    // basic blocks we use the helper function buildConditionSets.
+    // Build the condition sets for the successor nodes of the current
+    // region node. If it is a non-affine subregion we will always execute
+    // the single exit node, hence the single entry node domain is the
+    // condition set. For basic blocks we use the helper function
+    // buildConditionSets.
     SmallVector<isl_set *, 8> ConditionSets;
     if (RN->isSubRegion())
       ConditionSets.push_back(Domain.copy());
     else if (!buildConditionSets(*this, BB, TI, BBLoop, Domain,
                                  InvalidDomainMap[BB], ConditionSets))
       return false;
 
     // Now iterate over the successors and set their initial domain based on
-    // their condition set. We skip back edges here and have to be careful when
-    // we leave a loop not to keep constraints over a dimension that doesn't
-    // exist anymore.
+    // their condition set. We skip back edges here and have to be careful
+    // when we leave a loop not to keep constraints over a dimension that
+    // doesn't exist anymore.
     assert(RN->isSubRegion() || TI->getNumSuccessors() == ConditionSets.size());
     for (unsigned u = 0, e = ConditionSets.size(); u < e; u++) {
       isl::set CondSet = isl::manage(ConditionSets[u]);
       BasicBlock *SuccBB = getRegionNodeSuccessor(RN, TI, u);
 
       // Skip blocks outside the region.
       if (!contains(SuccBB))
         continue;
 
-      // If we propagate the domain of some block to "SuccBB" we do not have to
-      // adjust the domain.
+      // If we propagate the domain of some block to "SuccBB" we do not have
+      // to adjust the domain.
       if (FinishedExitBlocks.count(SuccBB))
         continue;
 
       // Skip back edges.
       if (DT.dominates(SuccBB, BB))
         continue;
 
       Loop *SuccBBLoop = getFirstNonBoxedLoopFor(SuccBB, LI, getBoxedLoops());
 
       CondSet = isl::manage(
           adjustDomainDimensions(*this, CondSet.copy(), BBLoop, SuccBBLoop));
 
-      // Set the domain for the successor or merge it with an existing domain in
-      // case there are multiple paths (without loop back edges) to the
-      // successor block.
+      // Set the domain for the successor or merge it with an existing
+      // domain in case there are multiple paths (without loop back edges)
+      // to the successor block.
       isl::set &SuccDomain = DomainMap[SuccBB];
 
       if (SuccDomain) {
         SuccDomain = SuccDomain.unite(CondSet).coalesce();
       } else {
         // Initialize the invalid domain.
         InvalidDomainMap[SuccBB] = CondSet.empty(CondSet.get_space());
         SuccDomain = CondSet;
for (unsigned u = 0, e = ConditionSets.size(); u < e; u++) {
         isl_set_free(ConditionSets[u]);
       return false;
     }
   }
 
   return true;
 }
 
-__isl_give isl_set *
-Scop::getPredecessorDomainConstraints(BasicBlock *BB,
-                                      __isl_keep isl_set *Domain,
-                                      DominatorTree &DT, LoopInfo &LI) {
+__isl_give isl_set *Scop::getPredecessorDomainConstraints(
+    BasicBlock *BB, __isl_keep isl_set *Domain, DominatorTree &DT, LoopInfo &LI,
+    DenseMap<BasicBlock *, isl::set> &DomainMap) {
+
   // If @p BB is the ScopEntry we are done
   if (R.getEntry() == BB)
     return isl_set_universe(isl_set_get_space(Domain));
 
   // The region info of this function.
   auto &RI = *R.getRegionInfo();
 
   Loop *BBLoop = getFirstNonBoxedLoopFor(BB, LI, getBoxedLoops());
 
   // A domain to collect all predecessor domains, thus all conditions under
-  // which the block is executed. To this end we start with the empty domain.
+  // which the block is executed. To this end we start with the empty
+  // domain.
   isl_set *PredDom = isl_set_empty(isl_set_get_space(Domain));
 
-  // Set of regions of which the entry block domain has been propagated to BB.
-  // all predecessors inside any of the regions can be skipped.
+  // Set of regions of which the entry block domain has been propagated to
+  // BB. all predecessors inside any of the regions can be skipped.
   SmallSet<Region *, 8> PropagatedRegions;
 
   for (auto *PredBB : predecessors(BB)) {
     // Skip backedges.
     if (DT.dominates(BB, PredBB))
       continue;
 
-    // If the predecessor is in a region we used for propagation we can skip it.
+    // If the predecessor is in a region we used for propagation we can skip
+    // it.
     auto PredBBInRegion = [PredBB](Region *PR) { return PR->contains(PredBB); };
     if (std::any_of(PropagatedRegions.begin(), PropagatedRegions.end(),
                     PredBBInRegion)) {
       continue;
     }
 
-    // Check if there is a valid region we can use for propagation, thus look
-    // for a region that contains the predecessor and has @p BB as exit block.
+    // Check if there is a valid region we can use for propagation, thus
+    // look for a region that contains the predecessor and has @p BB as exit
+    // block.
     auto *PredR = RI.getRegionFor(PredBB);
     while (PredR->getExit() != BB && !PredR->contains(BB))
       PredR->getParent();
 
-    // If a valid region for propagation was found use the entry of that region
-    // for propagation, otherwise the PredBB directly.
+    // If a valid region for propagation was found use the entry of that
+    // region for propagation, otherwise the PredBB directly.
     if (PredR->getExit() == BB) {
       PredBB = PredR->getEntry();
       PropagatedRegions.insert(PredR);
     }
 
-    auto *PredBBDom = getDomainConditions(PredBB);
+    auto *PredBBDom = getDomainConditions(DomainMap, PredBB);
     Loop *PredBBLoop = getFirstNonBoxedLoopFor(PredBB, LI, getBoxedLoops());
 
     PredBBDom = adjustDomainDimensions(*this, PredBBDom, PredBBLoop, BBLoop);
 
     PredDom = isl_set_union(PredDom, PredBBDom);
   }
 
   return PredDom;
 }
 
 bool Scop::propagateDomainConstraints(
     Region *R, DominatorTree &DT, LoopInfo &LI,
+    DenseMap<BasicBlock *, isl::set> &DomainMap,
     DenseMap<BasicBlock *, isl::set> &InvalidDomainMap) {
   // Iterate over the region R and propagate the domain constrains from the
   // predecessors to the current node. In contrast to the
-  // buildDomainsWithBranchConstraints function, this one will pull the domain
-  // information from the predecessors instead of pushing it to the successors.
-  // Additionally, we assume the domains to be already present in the domain
-  // map here. However, we iterate again in reverse post order so we know all
-  // predecessors have been visited before a block or non-affine subregion is
-  // visited.
+  // buildDomainsWithBranchConstraints function, this one will pull the
+  // domain information from the predecessors instead of pushing it to the
+  // successors. Additionally, we assume the domains to be already present
+  // in the domain map here. However, we iterate again in reverse post order
+  // so we know all predecessors have been visited before a block or
+  // non-affine subregion is visited.
 
   ReversePostOrderTraversal<Region *> RTraversal(R);
   for (auto *RN : RTraversal) {
 
-    // Recurse for affine subregions but go on for basic blocks and non-affine
-    // subregions.
+    // Recurse for affine subregions but go on for basic blocks and
+    // non-affine subregions.
     if (RN->isSubRegion()) {
       Region *SubRegion = RN->getNodeAs<Region>();
       if (!isNonAffineSubRegion(SubRegion)) {
-        if (!propagateDomainConstraints(SubRegion, DT, LI, InvalidDomainMap))
+        if (!propagateDomainConstraints(SubRegion, DT, LI, DomainMap,
+                                        InvalidDomainMap))
           return false;
         continue;
       }
     }
 
     BasicBlock *BB = getRegionNodeBasicBlock(RN);
     isl::set &Domain = DomainMap[BB];
     assert(Domain);
 
-    // Under the union of all predecessor conditions we can reach this block.
-    isl::set PredDom =
-        isl::manage(getPredecessorDomainConstraints(BB, Domain.get(), DT, LI));
+    // Under the union of all predecessor conditions we can reach this
+    // block.
+    isl::set PredDom = isl::manage(
+        getPredecessorDomainConstraints(BB, Domain.get(), DT, LI, DomainMap));
     Domain = Domain.intersect(PredDom).coalesce();
     Domain = Domain.align_params(isl::manage(getParamSpace()));
 
     Loop *BBLoop = getRegionNodeLoop(RN, LI);
     if (BBLoop && BBLoop->getHeader() == BB && contains(BBLoop))
-      if (!addLoopBoundsToHeaderDomain(BBLoop, LI, InvalidDomainMap))
+      if (!addLoopBoundsToHeaderDomain(BBLoop, LI, DomainMap, InvalidDomainMap))
         return false;
   }
 
   return true;
 }
 
 /// Create a map to map from a given iteration to a subsequent iteration.
 ///
createNextIterationMap(__isl_take isl_space *SetSpace, unsigned Dim) {
   C = isl_constraint_set_constant_si(C, 1);
   C = isl_constraint_set_coefficient_si(C, isl_dim_in, Dim, 1);
   C = isl_constraint_set_coefficient_si(C, isl_dim_out, Dim, -1);
   NextIterationMap = isl_map_add_constraint(NextIterationMap, C);
   return NextIterationMap;
 }
 
 bool Scop::addLoopBoundsToHeaderDomain(
-    Loop *L, LoopInfo &LI, DenseMap<BasicBlock *, isl::set> &InvalidDomainMap) {
+    Loop *L, LoopInfo &LI, DenseMap<BasicBlock *, isl::set> &DomainMap,
+    DenseMap<BasicBlock *, isl::set> &InvalidDomainMap) {
+
   int LoopDepth = getRelativeLoopDepth(L);
   assert(LoopDepth >= 0 && "Loop in region should have at least depth one");
 
   BasicBlock *HeaderBB = L->getHeader();
   assert(DomainMap.count(HeaderBB));
   isl::set &HeaderBBDom = DomainMap[HeaderBB];
 
   isl::map NextIterationMap = isl::manage(
bool Scop::addLoopBoundsToHeaderDomain(
   UnionBackedgeConditionComplement =
       UnionBackedgeConditionComplement.apply(ForwardMap);
   HeaderBBDom = HeaderBBDom.subtract(UnionBackedgeConditionComplement);
   HeaderBBDom = HeaderBBDom.apply(NextIterationMap);
 
   auto Parts = partitionSetParts(HeaderBBDom.copy(), LoopDepth);
   HeaderBBDom = isl::manage(Parts.second);
 
-  // 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.
+  // 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 (Affinator.hasNSWAddRecForLoop(L)) {
     isl_set_free(Parts.first);
     return true;
   }
 
   isl_set *UnboundedCtx = isl_set_params(Parts.first);
   recordAssumption(INFINITELOOP, UnboundedCtx,
                    HeaderBB->getTerminator()->getDebugLoc(), AS_RESTRICTION);
bool Scop::hasNonHoistableBasePtrInScop(MemoryAccess *MA,
   return false;
 }
 
 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.
+    // 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.
if (NewAG.size() > 1)
       AliasGroups.push_back(std::move(NewAG));
     isl_set_free(AGDomain);
   }
 }
 
 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
+  //   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);
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 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
for (MinMaxAccessTy &MMA : MinMaxAccessPair.second) {
       isl_pw_multi_aff_free(MMA.first);
       isl_pw_multi_aff_free(MMA.second);
     }
   }
 
   for (const auto &IAClass : InvariantEquivClasses)
     isl_set_free(IAClass.ExecutionContext);
 
-  // Explicitly release all Scop objects and the underlying isl objects before
-  // we release the isl context.
+  // Explicitly release all Scop objects and the underlying isl objects
+  // before we release the isl context.
   Stmts.clear();
   ScopArrayInfoSet.clear();
   ScopArrayInfoMap.clear();
   ScopArrayNameMap.clear();
   AccessFunctions.clear();
 }
 
 void Scop::updateAccessDimensionality() {
-  // Check all array accesses for each base pointer and find a (virtual) element
-  // size for the base pointer that divides all access functions.
+  // Check all array accesses for each base pointer and find a (virtual)
+  // element size for the base pointer that divides all access functions.
   for (ScopStmt &Stmt : *this)
     for (MemoryAccess *Access : Stmt) {
       if (!Access->isArrayKind())
         continue;
       ScopArrayInfo *Array =
           const_cast<ScopArrayInfo *>(Access->getScopArrayInfo());
 
       if (Array->getNumberOfDimensions() != 1)
if (!ShouldDelete(*StmtIt)) {
       continue;
     }
 
     removeFromStmtMap(*StmtIt);
     StmtIt = Stmts.erase(StmtIt);
   }
 }
 
-void Scop::removeStmtNotInDomainMap() {
-  auto ShouldDelete = [this](ScopStmt &Stmt) -> bool {
-    return !this->DomainMap.lookup(Stmt.getEntryBlock());
+void Scop::removeStmtNotInDomainMap(
+    DenseMap<BasicBlock *, isl::set> &DomainMap) {
+  auto ShouldDelete = [&DomainMap](ScopStmt &Stmt) -> bool {
+    return !DomainMap.lookup(Stmt.getEntryBlock());
   };
   removeStmts(ShouldDelete);
 }
 
 void Scop::simplifySCoP(bool AfterHoisting) {
 
   auto ShouldDelete = [AfterHoisting](ScopStmt &Stmt) -> bool {
     bool RemoveStmt = Stmt.isEmpty();
static bool canAlwaysBeHoisted(MemoryAccess *MA, bool StmtInvalidCtxIsEmpty,
   LoadInst *LInst = cast<LoadInst>(MA->getAccessInstruction());
   const DataLayout &DL = LInst->getParent()->getModule()->getDataLayout();
   // TODO: We can provide more information for better but more expensive
   //       results.
   if (!isDereferenceableAndAlignedPointer(LInst->getPointerOperand(),
                                           LInst->getAlignment(), DL))
     return false;
 
-  // If the location might be overwritten we do not hoist it unconditionally.
+  // If the location might be overwritten we do not hoist it
+  // unconditionally.
   //
   // TODO: This is probably to conservative.
   if (!NonHoistableCtxIsEmpty)
     return false;
 
-  // If a dereferenceable load is in a statement that is modeled precisely we
-  // can hoist it.
+  // 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.
+  // Even if the statement is not modeled precisely we can hoist the load if
+  // it does not involve any parameters that might have been specialized by
+  // the statement domain.
   for (unsigned u = 0, e = MA->getNumSubscripts(); u < e; u++)
     if (!isa<SCEVConstant>(MA->getSubscript(u)))
       return false;
   return true;
 }
 
 void Scop::addInvariantLoads(ScopStmt &Stmt, InvariantAccessesTy &InvMAs) {
 
   if (InvMAs.empty())
     return;
 
   auto *StmtInvalidCtx = Stmt.getInvalidContext();
   bool StmtInvalidCtxIsEmpty = isl_set_is_empty(StmtInvalidCtx);
 
-  // Get the context under which the statement is executed but remove the error
-  // context under which this statement is reached.
+  // Get the context under which the statement is executed but remove the
+  // error context under which this statement is reached.
   isl_set *DomainCtx = isl_set_params(Stmt.getDomain());
   DomainCtx = isl_set_subtract(DomainCtx, StmtInvalidCtx);
 
   if (isl_set_n_basic_set(DomainCtx) >= MaxDisjunctsInDomain) {
     auto *AccInst = InvMAs.front().MA->getAccessInstruction();
     invalidate(COMPLEXITY, AccInst->getDebugLoc(), AccInst->getParent());
     isl_set_free(DomainCtx);
     for (auto &InvMA : InvMAs)
       isl_set_free(InvMA.NonHoistableCtx);
     return;
   }
 
-  // Project out all parameters that relate to loads in the statement. Otherwise
-  // we could have cyclic dependences on the constraints under which the
-  // hoisted loads are executed and we could not determine an order in which to
-  // pre-load them. This happens because not only lower bounds are part of the
-  // domain but also upper bounds.
+  // Project out all parameters that relate to loads in the statement.
+  // Otherwise we could have cyclic dependences on the constraints under
+  // which the hoisted loads are executed and we could not determine an
+  // order in which to pre-load them. This happens because not only lower
+  // bounds are part of the domain but also upper bounds.
   for (auto &InvMA : InvMAs) {
     auto *MA = InvMA.MA;
     Instruction *AccInst = MA->getAccessInstruction();
     if (SE->isSCEVable(AccInst->getType())) {
       SetVector<Value *> Values;
       for (const SCEV *Parameter : Parameters) {
         Values.clear();
         findValues(Parameter, *SE, Values);
if (canAlwaysBeHoisted(MA, StmtInvalidCtxIsEmpty, MAInvalidCtxIsEmpty,
       MACtx = isl_set_gist_params(MACtx, getContext());
     }
 
     bool Consolidated = false;
     for (auto &IAClass : InvariantEquivClasses) {
       if (PointerSCEV != IAClass.IdentifyingPointer || Ty != IAClass.AccessType)
         continue;
 
-      // If the pointer and the type is equal check if the access function wrt.
-      // to the domain is equal too. It can happen that the domain fixes
-      // parameter values and these can be different for distinct part of the
-      // SCoP. If this happens we cannot consolidate the loads but need to
-      // create a new invariant load equivalence class.
+      // If the pointer and the type is equal check if the access function
+      // wrt. to the domain is equal too. It can happen that the domain
+      // fixes parameter values and these can be different for distinct part
+      // of the SCoP. If this happens we cannot consolidate the loads but
+      // need to create a new invariant load equivalence class.
       auto &MAs = IAClass.InvariantAccesses;
       if (!MAs.empty()) {
         auto *LastMA = MAs.front();
 
         auto *AR = isl_map_range(MA->getAccessRelation().release());
         auto *LastAR = isl_map_range(LastMA->getAccessRelation().release());
         bool SameAR = isl_set_is_equal(AR, LastAR);
         isl_set_free(AR);
static bool isAccessRangeTooComplex(isl::set AccessRange) {
 
   return false;
 }
 
 isl::set Scop::getNonHoistableCtx(MemoryAccess *Access, isl::union_map Writes) {
   // TODO: Loads that are not loop carried, hence are in a statement with
   //       zero iterators, are by construction invariant, though we
   //       currently "hoist" them anyway. This is necessary because we allow
-  //       them to be treated as parameters (e.g., in conditions) and our code
-  //       generation would otherwise use the old value.
+  //       them to be treated as parameters (e.g., in conditions) and our
+  //       code generation would otherwise use the old value.
 
   auto &Stmt = *Access->getStatement();
   BasicBlock *BB = Stmt.getEntryBlock();
 
   if (Access->isScalarKind() || Access->isWrite() || !Access->isAffine() ||
       Access->isMemoryIntrinsic())
     return nullptr;
 

 static bool isUsedForIndirectHoistedLoad(Scop *S, const ScopArrayInfo *Array) {
   for (InvariantEquivClassTy &EqClass2 : S->getInvariantAccesses())
     for (MemoryAccess *Access2 : EqClass2.InvariantAccesses)
       if (Access2->getScopArrayInfo() == Array)
         return true;
   return false;
 }
 
-/// Replace the base pointer arrays in all memory accesses referencing @p Old,
-/// with a reference to @p New.
+/// Replace the base pointer arrays in all memory accesses referencing @p
+/// Old, with a reference to @p New.
 static void replaceBasePtrArrays(Scop *S, const ScopArrayInfo *Old,
                                  const ScopArrayInfo *New) {
   for (ScopStmt &Stmt : *S)
     for (MemoryAccess *Access : Stmt) {
       if (Access->getLatestScopArrayInfo() != Old)
         continue;
 
       isl_id *Id = New->getBasePtrId().release();
for (InvariantEquivClassTy &EqClass : InvariantEquivClasses) {
     for (MemoryAccess *BasePtrAccess : BasePtrAccesses) {
       const ScopArrayInfo *BasePtrSAI = getScopArrayInfoOrNull(
           BasePtrAccess->getAccessInstruction(), MemoryKind::Array);
       if (!BasePtrSAI || BasePtrSAI == CanonicalBasePtrSAI ||
           !BasePtrSAI->isCompatibleWith(CanonicalBasePtrSAI))
         continue;
 
       // we currently do not canonicalize arrays where some accesses are
-      // hoisted as invariant loads. If we would, we need to update the access
-      // function of the invariant loads as well. However, as this is not a
-      // very common situation, we leave this for now to avoid further
+      // hoisted as invariant loads. If we would, we need to update the
+      // access function of the invariant loads as well. However, as this is
+      // not a very common situation, we leave this for now to avoid further
       // complexity increases.
       if (isUsedForIndirectHoistedLoad(this, BasePtrSAI))
         continue;
 
       replaceBasePtrArrays(this, BasePtrSAI, CanonicalBasePtrSAI);
     }
   }
 }
auto &SAI = BasePtr ? ScopArrayInfoMap[std::make_pair(BasePtr, Kind)]
                       : ScopArrayNameMap[BaseName];
   if (!SAI) {
     auto &DL = getFunction().getParent()->getDataLayout();
     SAI.reset(new ScopArrayInfo(BasePtr, ElementType, getIslCtx(), Sizes, Kind,
                                 DL, this, BaseName));
     ScopArrayInfoSet.insert(SAI.get());
   } else {
     SAI->updateElementType(ElementType);
-    // In case of mismatching array sizes, we bail out by setting the run-time
-    // context to false.
+    // In case of mismatching array sizes, we bail out by setting the
+    // run-time context to false.
     if (!SAI->updateSizes(Sizes))
       invalidate(DELINEARIZATION, DebugLoc());
   }
   return SAI.get();
 }
 
 ScopArrayInfo *Scop::createScopArrayInfo(Type *ElementType,
                                          const std::string &BaseName,

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

 void Scop::buildSchedule(LoopInfo &LI) {
   Loop *L = getLoopSurroundingScop(*this, LI);
   LoopStackTy LoopStack({LoopStackElementTy(L, nullptr, 0)});
   buildSchedule(getRegion().getNode(), LoopStack, LI);
   assert(LoopStack.size() == 1 && LoopStack.back().L == L);
   Schedule = LoopStack[0].Schedule;
 }
 
-/// To generate a schedule for the elements in a Region we traverse the Region
-/// in reverse-post-order and add the contained RegionNodes in traversal order
-/// to the schedule of the loop that is currently at the top of the LoopStack.
-/// For loop-free codes, this results in a correct sequential ordering.
+/// To generate a schedule for the elements in a Region we traverse the
+/// Region in reverse-post-order and add the contained RegionNodes in
+/// traversal order to the schedule of the loop that is currently at the top
+/// of the LoopStack. For loop-free codes, this results in a correct
+/// sequential ordering.
 ///
 /// Example:
 ///           bb1(0)
 ///         /     \.
 ///      bb2(1)   bb3(2)
 ///         \    /  \.
 ///          bb4(3)  bb5(4)
 ///             \   /
 ///              bb6(5)
 ///
-/// Including loops requires additional processing. Whenever a loop header is
-/// encountered, the corresponding loop is added to the @p LoopStack. Starting
-/// from an empty schedule, we first process all RegionNodes that are within
-/// this loop and complete the sequential schedule at this loop-level before
-/// processing about any other nodes. To implement this
+/// Including loops requires additional processing. Whenever a loop header
+/// is encountered, the corresponding loop is added to the @p LoopStack.
+/// Starting from an empty schedule, we first process all RegionNodes that
+/// are within this loop and complete the sequential schedule at this
+/// loop-level before processing about any other nodes. To implement this
 /// loop-nodes-first-processing, the reverse post-order traversal is
 /// insufficient. Hence, we additionally check if the traversal yields
-/// sub-regions or blocks that are outside the last loop on the @p LoopStack.
-/// These region-nodes are then queue and only traverse after the all nodes
-/// within the current loop have been processed.
+/// sub-regions or blocks that are outside the last loop on the @p
+/// LoopStack. These region-nodes are then queue and only traverse after the
+/// all nodes within the current loop have been processed.
 void Scop::buildSchedule(Region *R, LoopStackTy &LoopStack, LoopInfo &LI) {
   Loop *OuterScopLoop = getLoopSurroundingScop(*this, LI);
 
   ReversePostOrderTraversal<Region *> RTraversal(R);
   std::deque<RegionNode *> WorkList(RTraversal.begin(), RTraversal.end());
   std::deque<RegionNode *> DelayList;
   bool LastRNWaiting = false;
 
   // Iterate over the region @p R in reverse post-order but queue
-  // sub-regions/blocks iff they are not part of the last encountered but not
-  // completely traversed loop. The variable LastRNWaiting is a flag to indicate
-  // that we queued the last sub-region/block from the reverse post-order
-  // iterator. If it is set we have to explore the next sub-region/block from
-  // the iterator (if any) to guarantee progress. If it is not set we first try
-  // the next queued sub-region/blocks.
+  // sub-regions/blocks iff they are not part of the last encountered but
+  // not completely traversed loop. The variable LastRNWaiting is a flag to
+  // indicate that we queued the last sub-region/block from the reverse
+  // post-order iterator. If it is set we have to explore the next
+  // sub-region/block from the iterator (if any) to guarantee progress. If
+  // it is not set we first try the next queued sub-region/blocks.
   while (!WorkList.empty() || !DelayList.empty()) {
     RegionNode *RN;
 
     if ((LastRNWaiting && !WorkList.empty()) || DelayList.size() == 0) {
       RN = WorkList.front();
       WorkList.pop_front();
       LastRNWaiting = false;
     } else {
void Scop::buildSchedule(RegionNode *RN, LoopStackTy &LoopStack, LoopInfo &LI) {
   LoopData.NumBlocksProcessed += getNumBlocksInRegionNode(RN);
 
   for (auto *Stmt : getStmtListFor(RN)) {
     auto *UDomain = isl_union_set_from_set(Stmt->getDomain());
     auto *StmtSchedule = isl_schedule_from_domain(UDomain);
     LoopData.Schedule = combineInSequence(LoopData.Schedule, StmtSchedule);
   }
 
-  // Check if we just processed the last node in this loop. If we did, finalize
-  // the loop by:
+  // Check if we just processed the last node in this loop. If we did,
+  // finalize the loop by:
   //
   //   - adding new schedule dimensions
   //   - folding the resulting schedule into the parent loop schedule
   //   - dropping the loop schedule from the LoopStack.
   //
   // Then continue to check surrounding loops, which might also have been
   // completed by this node.
   while (LoopData.L &&
bool Scop::isEscaping(Instruction *Inst) {
   assert(contains(Inst) && "The concept of escaping makes only sense for "
                            "values defined inside the SCoP");
 
   for (Use &Use : Inst->uses()) {
     BasicBlock *UserBB = getUseBlock(Use);
     if (!contains(UserBB))
       return true;
 
-    // When the SCoP region exit needs to be simplified, PHIs in the region exit
-    // move to a new basic block such that its incoming blocks are not in the
-    // SCoP anymore.
+    // When the SCoP region exit needs to be simplified, PHIs in the region
+    // exit move to a new basic block such that its incoming blocks are not
+    // in the SCoP anymore.
     if (hasSingleExitEdge() && isa<PHINode>(Use.getUser()) &&
         isExit(cast<PHINode>(Use.getUser())->getParent()))
       return true;
   }
   return false;
 }
 
 raw_ostream &polly::operator<<(raw_ostream &O, const Scop &scop) {

lib/CodeGen/IslNodeBuilder.cpp

for (auto *Val : Values) {
           // there is a statement or the domain is not empty Inst is not dead.
           auto MemInst = MemAccInst::dyn_cast(Inst);
           auto Address = MemInst ? MemInst.getPointerOperand() : nullptr;
           if (Address && SE.getUnknown(UndefValue::get(Address->getType())) ==
                              SE.getPointerBase(SE.getSCEV(Address))) {
           } else if (S.getStmtFor(Inst)) {
             IsDead = false;
           } else {
-            auto *Domain = S.getDomainConditions(Inst->getParent());
+            auto *Domain = S.getStmtFor(Inst)->getDomain();
             IsDead = isl_set_is_empty(Domain);
             isl_set_free(Domain);
           }
 
           if (IsDead) {
             V = UndefValue::get(ParamSCEV->getType());
             break;
           }