[Polly][NFC][ScopBuilder] Move buildDomains and its callees to ScopBuilder.

[domada]

Summary

Scope of changes:

1. Moved buildDomains function to ScopBuilder class.
2. Moved buildDomainsWithBranchConstraints function to ScopBuilder class.
3. Moved propagateDomainConstraints to ScopBuilder class.
4. Moved propagateDomainConstraintsToRegionExit to ScopBuilder class.
5. Moved propagateInvalidStmtDomains to ScopBuilder class.
6. Moved getPredecessorDomainConstraints function to ScopBuilder class.
7. Moved addLoopBoundsToHeaderDomain function to ScopBuilder class.
8. Moved getPwAff function to ScopBuilder class.
9. Moved buildConditionSets functions to ScopBuilder class.
10. Added updateMaxLoopDepth, notifyErrorBlock, getOrInitEmptyDomain, isDomainDefined, setDomain functions to Scop class. They are used by ScopBuilder.
11. Moved helper functions: getRegionNodeBasicBlock, getRegionNodeSuccessor, containsErrorBlock, createNextIterationMap, collectBoundedParts, partitionSetParts, buildConditionSet to ScopBuilder.cpp file.

[Meinersbur]

polly/include/polly/ScopBuilder.h

294–300

[nit] unrelated noise (here and below). Possibly the result of adding and indention (e.g. by forgetting to close a { somewhere before these lines), running clang-format, then fixing it.

polly/include/polly/ScopInfo.h

2496

[typo] dpeth

2497

[bikeshedding] "set" might not be the right verb as it does not just overwrite the depth. How about update (or notify which you used below)?

2576

[bikeshedding] The idiom usually is named getOr... (e.g. LLVMContext::getOrAddScopeRecordIdxEntry, Scop::getOrCreateScopArrayInfo). How about getOrInitEmptyDomain?

[domada]

Applied @Meinersbur remarks.

[Meinersbur]

LGTM

polly/include/polly/ScopBuilder.h

class ScopBuilder {
   /// @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);
 
+  /// Adjust the dimensions of @p Dom that was constructed for @p OldL
+  ///        to be compatible to domains constructed for loop @p NewL.
+  ///
+  /// This function assumes @p NewL and @p OldL are equal or there is a CFG
+  /// edge from @p OldL to @p NewL.
+  isl::set adjustDomainDimensions(isl::set Dom, Loop *OldL, Loop *NewL);
+
+  /// Compute the domain for each basic block in @p R.
+  ///
+  /// @param R                The region we currently traverse.
+  /// @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,
+                    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 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, DenseMap<BasicBlock *, isl::set> &InvalidDomainMap);
+
+  /// Build the conditions sets for the terminator @p TI in the @p Domain.
+  ///
+  /// This will fill @p ConditionSets with the conditions under which control
+  /// will be moved from @p TI to its successors. Hence, @p ConditionSets will
+  /// have as many elements as @p TI has successors.
+  bool buildConditionSets(BasicBlock *BB, Instruction *TI, Loop *L,
+                          __isl_keep isl_set *Domain,
+                          DenseMap<BasicBlock *, isl::set> &InvalidDomainMap,
+                          SmallVectorImpl<__isl_give isl_set *> &ConditionSets);
+
+  /// Build the conditions sets for the branch condition @p Condition in
+  /// the @p Domain.
+  ///
+  /// This will fill @p ConditionSets with the conditions under which control
+  /// will be moved from @p TI to its successors. Hence, @p ConditionSets will
+  /// have as many elements as @p TI has successors. If @p TI is nullptr the
+  /// context under which @p Condition is true/false will be returned as the
+  /// new elements of @p ConditionSets.
+  bool buildConditionSets(BasicBlock *BB, Value *Condition, Instruction *TI,
+                          Loop *L, __isl_keep isl_set *Domain,
+                          DenseMap<BasicBlock *, isl::set> &InvalidDomainMap,
+                          SmallVectorImpl<__isl_give isl_set *> &ConditionSets);
+
+  /// Build the conditions sets for the switch @p SI in the @p Domain.
+  ///
+  /// This will fill @p ConditionSets with the conditions under which control
+  /// will be moved from @p SI to its successors. Hence, @p ConditionSets will
+  /// have as many elements as @p SI has successors.
+  bool buildConditionSets(BasicBlock *BB, SwitchInst *SI, Loop *L,
+                          __isl_keep isl_set *Domain,
+                          DenseMap<BasicBlock *, isl::set> &InvalidDomainMap,
+                          SmallVectorImpl<__isl_give isl_set *> &ConditionSets);
+
+  /// Build condition sets for unsigned ICmpInst(s).
+  /// Special handling is required for unsigned operands to ensure that if
+  /// MSB (aka the Sign bit) is set for an operands in an unsigned ICmpInst
+  /// it should wrap around.
+  ///
+  /// @param IsStrictUpperBound holds information on the predicate relation
+  /// between TestVal and UpperBound, i.e,
+  /// TestVal < UpperBound  OR  TestVal <= UpperBound
+  __isl_give isl_set *buildUnsignedConditionSets(
+      BasicBlock *BB, Value *Condition, __isl_keep isl_set *Domain,
+      const SCEV *SCEV_TestVal, const SCEV *SCEV_UpperBound,
+      DenseMap<BasicBlock *, isl::set> &InvalidDomainMap,
+      bool IsStrictUpperBound);
+
+  /// Propagate the domain constraints through the region @p R.
+  ///
+  /// @param R                The region we currently build branching
+  /// conditions for.
+  /// @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, DenseMap<BasicBlock *, isl::set> &InvalidDomainMap);
+
+  /// Propagate domains that are known due to graph properties.
+  ///
+  /// As a CFG is mostly structured we use the graph properties to propagate
+  /// domains without the need to compute all path conditions. In particular,
+  /// if a block A dominates a block B and B post-dominates A we know that the
+  /// domain of B is a superset of the domain of A. As we do not have
+  /// post-dominator information available here we use the less precise region
+  /// information. Given a region R, we know that the exit is always executed
+  /// if the entry was executed, thus the domain of the exit is a superset of
+  /// the domain of the entry. In case the exit can only be reached from
+  /// within the region the domains are in fact equal. This function will use
+  /// this property to avoid the generation of condition constraints that
+  /// determine when a branch is taken. If @p BB is a region entry block we
+  /// will propagate its domain to the region exit block. Additionally, we put
+  /// the region exit 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 InvalidDomainMap   BB to InvalidDomain map for the BB of current
+  ///                           region.
+  void propagateDomainConstraintsToRegionExit(
+      BasicBlock *BB, Loop *BBLoop,
+      SmallPtrSetImpl<BasicBlock *> &FinishedExitBlocks,
+      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 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, 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.
+  ///
+  /// @returns The domain under which @p BB is executed.
+  isl::set getPredecessorDomainConstraints(BasicBlock *BB, isl::set Domain);
+
+  /// Add loop carried constraints to the header block of the loop @p L.
+  ///
+  /// @param L                The loop to process.
+  /// @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, DenseMap<BasicBlock *, isl::set> &InvalidDomainMap);
+
+  /// Compute the isl representation for the SCEV @p E in this BB.
+  ///
+  /// @param BB               The BB for which isl representation is to be
+  /// computed.
+  /// @param InvalidDomainMap A map of BB to their invalid domains.
+  /// @param E                The SCEV that should be translated.
+  /// @param NonNegative      Flag to indicate the @p E has to be
+  /// non-negative.
+  ///
+  /// Note that this function will also adjust the invalid context
+  /// accordingly.
+  __isl_give isl_pw_aff *
+  getPwAff(BasicBlock *BB, DenseMap<BasicBlock *, isl::set> &InvalidDomainMap,
+           const SCEV *E, bool NonNegative = false);
+
   /// 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
+  /// 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
-  /// Scop::getRepresentingInvariantLoadSCEV() will replace each element from an
-  /// equivalence class with the representing element that is modeled. As a
+  /// Scop::getRepresentingInvariantLoadSCEV() will replace each element from
+  /// an equivalence class with the representing element that is modeled. As a
   /// consequence Scop::getIdForParam() will only return an id for the
   /// representing element of each equivalence class, thus for each required
   /// invariant location.
   void buildInvariantEquivalenceClasses();
 
   /// Try to build a multi-dimensional fixed sized MemoryAccess from the
   /// Load/Store instruction.
   ///
class ScopBuilder {
   ///
   /// @param Inst       The Load/Store instruction that access the memory
   /// @param Stmt       The parent statement of the instruction
   void buildAccessSingleDim(MemAccInst Inst, ScopStmt *Stmt);
 
   /// Finalize all access relations.
   ///
   /// When building up access relations, temporary access relations that
-  /// correctly represent each individual access are constructed. However, these
-  /// access relations can be inconsistent or non-optimal when looking at the
-  /// set of accesses as a whole. This function finalizes the memory accesses
-  /// and constructs a globally consistent state.
+  /// correctly represent each individual access are constructed. However,
+  /// these access relations can be inconsistent or non-optimal when looking
+  /// at the set of accesses as a whole. This function finalizes the memory
+  /// accesses and constructs a globally consistent state.
   void finalizeAccesses();
 
   /// Update access dimensionalities.
   ///
   /// When detecting memory accesses different accesses to the same array may
-  /// have built with different dimensionality, as outer zero-values dimensions
-  /// may not have been recognized as separate dimensions. This function goes
-  /// again over all memory accesses and updates their dimensionality to match
-  /// the dimensionality of the underlying ScopArrayInfo object.
+  /// have built with different dimensionality, as outer zero-values
+  /// dimensions may not have been recognized as separate dimensions. This
+  /// function goes again over all memory accesses and updates their
+  /// dimensionality to match the dimensionality of the underlying
+  /// ScopArrayInfo object.
   void updateAccessDimensionality();
 
   /// Fold size constants to the right.
   ///
   /// In case all memory accesses in a given dimension are multiplied with a
   /// common constant, we can remove this constant from the individual access
-  /// functions and move it to the size of the memory access. We do this as this
-  /// increases the size of the innermost dimension, consequently widens the
-  /// valid range the array subscript in this dimension can evaluate to, and
-  /// as a result increases the likelihood that our delinearization is
+  /// functions and move it to the size of the memory access. We do this as
+  /// this increases the size of the innermost dimension, consequently widens
+  /// the valid range the array subscript in this dimension can evaluate to,
+  /// and as a result increases the likelihood that our delinearization is
   /// correct.
   ///
   /// Example:
   ///
   ///    A[][n]
   ///    S[i,j] -> A[2i][2j+1]
   ///    S[i,j] -> A[2i][2j]
   ///
   ///    =>
   ///
   ///    A[][2n]
   ///    S[i,j] -> A[i][2j+1]
   ///    S[i,j] -> A[i][2j]
   ///
-  /// Constants in outer dimensions can arise when the elements of a parametric
-  /// multi-dimensional array are not elementary data types, but e.g.,
-  /// structures.
+  /// Constants in outer dimensions can arise when the elements of a
+  /// parametric multi-dimensional array are not elementary data types, but
+  /// e.g., structures.
   void foldSizeConstantsToRight();
 
   /// Fold memory accesses to handle parametric offset.
   ///
   /// As a post-processing step, we 'fold' memory accesses to parametric
   /// offsets in the access functions. @see MemoryAccess::foldAccess for
   /// details.
   void foldAccessRelations();
class ScopBuilder {
   /// 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
+  /// @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.
+  ///  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
class ScopBuilder {
   /// @param Inst The instruction to be analyzed.
   void buildEscapingDependences(Instruction *Inst);
 
   /// Create MemoryAccesses for the given PHI node in the given region.
   ///
   /// @param PHIStmt            The statement @p PHI resides in.
   /// @param PHI                The PHI node to be handled
   /// @param NonAffineSubRegion The non affine sub-region @p PHI is in.
-  /// @param IsExitBlock        Flag to indicate that @p PHI is in the exit BB.
+  /// @param IsExitBlock        Flag to indicate that @p PHI is in the exit
+  /// BB.
   void buildPHIAccesses(ScopStmt *PHIStmt, PHINode *PHI,
                         Region *NonAffineSubRegion, bool IsExitBlock = false);
 
   /// Build the access functions for the subregion @p SR.
   void buildAccessFunctions();
 
   /// Should an instruction be modeled in a ScopStmt.
   ///
class ScopBuilder {
   /// Create ScopStmt for all BBs and non-affine subregions of @p SR.
   ///
   /// @param SR A subregion of @p R.
   ///
   /// Some of the statements might be optimized away later when they do not
   /// access any memory and thus have no effect.
   void buildStmts(Region &SR);
 
-  /// Build the access functions for the statement @p Stmt in or represented by
+  /// Build the access functions for the statement @p Stmt in or represented
+  /// by
   /// @p BB.
   ///
   /// @param Stmt               Statement to add MemoryAccesses to.
   /// @param BB                 A basic block in @p R.
   /// @param NonAffineSubRegion The non affine sub-region @p BB is in.
   void buildAccessFunctions(ScopStmt *Stmt, BasicBlock &BB,
                             Region *NonAffineSubRegion = nullptr);
 
   /// Create a new MemoryAccess object and add it to #AccFuncMap.
   ///
   /// @param Stmt        The statement where the access takes place.
-  /// @param Inst        The instruction doing the access. It is not necessarily
+  /// @param Inst        The instruction doing the access. It is not
+  /// necessarily
   ///                    inside @p BB.
   /// @param AccType     The kind of access.
   /// @param BaseAddress The accessed array's base address.
   /// @param ElemType    The type of the accessed array elements.
   /// @param Affine      Whether all subscripts are affine expressions.
   /// @param AccessValue Value read or written.
   /// @param Subscripts  Access subscripts per dimension.
   /// @param Sizes       The array dimension's sizes.
class ScopBuilder {
   /// @param UserStmt Where to reload the value.
   ///
   /// @see ensureValueStore()
   /// @see MemoryKind
   void ensureValueRead(Value *V, ScopStmt *UserStmt);
 
   /// Create a write MemoryAccess for the incoming block of a phi node.
   ///
-  /// Each of the incoming blocks write their incoming value to be picked in the
-  /// phi's block.
+  /// Each of the incoming blocks write their incoming value to be picked in
+  /// the phi's block.
   ///
   /// @param PHI           PHINode under consideration.
   /// @param IncomingStmt  The statement to add the MemoryAccess to.
   /// @param IncomingBlock Some predecessor block.
   /// @param IncomingValue @p PHI's value when coming from @p IncomingBlock.
   /// @param IsExitBlock   When true, uses the .s2a alloca instead of the
   ///                      .phiops one. Required for values escaping through a
   ///                      PHINode in the SCoP region's exit block.
class ScopBuilder {
 
   /// Create a MemoryAccess for reading the value of a phi.
   ///
   /// The modeling assumes that all incoming blocks write their incoming value
   /// to the same location. Thus, this access will read the incoming block's
   /// value as instructed by this @p PHI.
   ///
   /// @param PHIStmt Statement @p PHI resides in.
-  /// @param PHI     PHINode under consideration; the READ access will be added
+  /// @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.
   ///
   /// Iterate over all store memory accesses and check for valid binary
   /// reduction like chains. For all candidates we check if they have the same
-  /// base address and there are no other accesses which overlap with them. The
-  /// base address check rules out impossible reductions candidates early. The
-  /// overlap check, together with the "only one user" check in
+  /// base address and there are no other accesses which overlap with them.
+  /// The base address check rules out impossible reductions candidates early.
+  /// The overlap check, together with the "only one user" check in
   /// collectCandidateReductionLoads, guarantees that none of the intermediate
-  /// results will escape during execution of the loop nest. We basically check
-  /// here that no other memory access can access the same memory as the
+  /// results will escape during execution of the loop nest. We basically
+  /// check here that no other memory access can access the same memory as the
   /// potential reduction.
   void checkForReductions(ScopStmt &Stmt);
 
   /// Verify that all required invariant loads have been hoisted.
   ///
   /// Invariant load hoisting is not guaranteed to hoist all loads that were
   /// assumed to be scop invariant during scop detection. This function checks
   /// for cases where the hoisting failed, but where it would have been
   /// necessary for our scop modeling to be correct. In case of insufficient
   /// hoisting the scop is marked as invalid.
   ///
   /// In the example below Bound[1] is required to be invariant:
   ///
   /// for (int i = 1; i < Bound[0]; i++)
   ///   for (int j = 1; j < Bound[1]; j++)
   ///     ...
   void verifyInvariantLoads();
 
   /// Hoist invariant memory loads and check for required ones.
   ///
-  /// We first identify "common" invariant loads, thus loads that are invariant
-  /// and can be hoisted. Then we check if all required invariant loads have
-  /// been identified as (common) invariant. A load is a required invariant load
-  /// if it was assumed to be invariant during SCoP detection, e.g., to assume
-  /// loop bounds to be affine or runtime alias checks to be placeable. In case
-  /// a required invariant load was not identified as (common) invariant we will
-  /// drop this SCoP. An example for both "common" as well as required invariant
-  /// loads is given below:
+  /// We first identify "common" invariant loads, thus loads that are
+  /// invariant and can be hoisted. Then we check if all required invariant
+  /// loads have been identified as (common) invariant. A load is a required
+  /// invariant load if it was assumed to be invariant during SCoP detection,
+  /// e.g., to assume loop bounds to be affine or runtime alias checks to be
+  /// placeable. In case a required invariant load was not identified as
+  /// (common) invariant we will drop this SCoP. An example for both "common"
+  /// as well as required invariant loads is given below:
   ///
   /// for (int i = 1; i < *LB[0]; i++)
   ///   for (int j = 1; j < *LB[1]; j++)
   ///     A[i][j] += A[0][0] + (*V);
   ///
   /// Common inv. loads: V, A[0][0], LB[0], LB[1]
   /// Required inv. loads: LB[0], LB[1], (V, if it may alias with A or LB)
   void hoistInvariantLoads();
class ScopBuilder {
   /// @param Writes The set of all memory writes in the scop.
   ///
   /// @return Return the context under which the access cannot be hoisted or a
   ///         nullptr if it cannot be hoisted at all.
   isl::set getNonHoistableCtx(MemoryAccess *Access, isl::union_map Writes);
 
   /// Collect loads which might form a reduction chain with @p StoreMA.
   ///
-  /// Check if the stored value for @p StoreMA is a binary operator with one or
-  /// two loads as operands. If the binary operand is commutative & associative,
-  /// used only once (by @p StoreMA) and its load operands are also used only
-  /// once, we have found a possible reduction chain. It starts at an operand
-  /// load and includes the binary operator and @p StoreMA.
+  /// Check if the stored value for @p StoreMA is a binary operator with one
+  /// or two loads as operands. If the binary operand is commutative &
+  /// associative, used only once (by @p StoreMA) and its load operands are
+  /// also used only once, we have found a possible reduction chain. It starts
+  /// at an operand load and includes the binary operator and @p StoreMA.
   ///
-  /// Note: We allow only one use to ensure the load and binary operator cannot
+  /// Note: We allow only one use to ensure the load and binary operator
+  /// cannot
   ///       escape this block or into any other store except @p StoreMA.
   void collectCandidateReductionLoads(MemoryAccess *StoreMA,
                                       SmallVectorImpl<MemoryAccess *> &Loads);
 
   /// Build the access relation of all memory accesses of @p Stmt.
   void buildAccessRelations(ScopStmt &Stmt);
 
   /// Canonicalize arrays with base pointers from the same equivalence class.
class ScopBuilder {
   /// This function makes sure that we do not generate consistently failing
   /// run-time checks for code that contains distinct arrays with known
   /// equivalent base pointers. It identifies for each invariant load
   /// equivalence class a single canonical array and canonicalizes all memory
   /// accesses that reference arrays that have base pointers that are known to
   /// be equal to the base pointer of such a canonical array to this canonical
   /// array.
   ///
-  /// We currently do not canonicalize arrays for which certain memory accesses
-  /// have been hoisted as loop invariant.
+  /// We currently do not canonicalize arrays for which certain memory
+  /// accesses have been hoisted as loop invariant.
   void canonicalizeDynamicBasePtrs();
 
   /// Construct the schedule of this SCoP.
   void buildSchedule();
 
   /// A loop stack element to keep track of per-loop information during
   ///        schedule construction.
   using LoopStackElementTy = struct LoopStackElement {
     // The loop for which we keep information.
     Loop *L;
 
     // The (possibly incomplete) schedule for this loop.
     isl::schedule Schedule;
 
-    // The number of basic blocks in the current loop, for which a schedule has
-    // already been constructed.
+    // The number of basic blocks in the current loop, for which a schedule
+    // has already been constructed.
     unsigned NumBlocksProcessed;
 
     LoopStackElement(Loop *L, isl::schedule S, unsigned NumBlocksProcessed)
         : L(L), Schedule(S), NumBlocksProcessed(NumBlocksProcessed) {}
   };
 
   /// The loop stack used for schedule construction.
   ///
class ScopBuilder {
 
   /// Build Schedule for the region node @p RN and add the derived
   ///        information to @p LoopStack.
   ///
   /// In case @p RN is a BasicBlock or a non-affine Region, we construct the
   /// schedule for this @p RN and also finalize loop schedules in case the
   /// current @p RN completes the loop.
   ///
-  /// In case @p RN is a not-non-affine Region, we delegate the construction to
-  /// buildSchedule(Region *R, ...).
+  /// In case @p RN is a not-non-affine Region, we delegate the construction
+  /// to buildSchedule(Region *R, ...).
   ///
   /// @param RN             The RegionNode region traversed.
   /// @param LoopStack      A stack of loops that are currently under
   ///                       construction.
   void buildSchedule(RegionNode *RN, LoopStackTy &LoopStack);
 
 public:
   explicit ScopBuilder(Region *R, AssumptionCache &AC, AliasAnalysis &AA,

polly/include/polly/ScopInfo.h

struct Assumption {
   isl::set Set;
 
   /// The location that caused this assumption.
   DebugLoc Loc;
 
   /// An optional block whose domain can simplify the assumption.
   BasicBlock *BB;
 };
-/// Build the conditions sets for the branch condition @p Condition in
-/// the @p Domain.
-///
-/// This will fill @p ConditionSets with the conditions under which control
-/// will be moved from @p TI to its successors. Hence, @p ConditionSets will
-/// have as many elements as @p TI has successors. If @p TI is nullptr the
-/// context under which @p Condition is true/false will be returned as the
-/// new elements of @p ConditionSets.
-bool buildConditionSets(Scop &S, BasicBlock *BB, Value *Condition,
-                        Instruction *TI, Loop *L, __isl_keep isl_set *Domain,
-                        DenseMap<BasicBlock *, isl::set> &InvalidDomainMap,
-                        SmallVectorImpl<__isl_give isl_set *> &ConditionSets);
-
-/// Build condition sets for unsigned ICmpInst(s).
-/// Special handling is required for unsigned operands to ensure that if
-/// MSB (aka the Sign bit) is set for an operands in an unsigned ICmpInst
-/// it should wrap around.
-///
-/// @param IsStrictUpperBound holds information on the predicate relation
-/// between TestVal and UpperBound, i.e,
-/// TestVal < UpperBound  OR  TestVal <= UpperBound
-__isl_give isl_set *
-buildUnsignedConditionSets(Scop &S, BasicBlock *BB, Value *Condition,
-                           __isl_keep isl_set *Domain, const SCEV *SCEV_TestVal,
-                           const SCEV *SCEV_UpperBound,
-                           DenseMap<BasicBlock *, isl::set> &InvalidDomainMap,
-                           bool IsStrictUpperBound);
-
-/// Build the conditions sets for the terminator @p TI in the @p Domain.
-///
-/// This will fill @p ConditionSets with the conditions under which control
-/// will be moved from @p TI to its successors. Hence, @p ConditionSets will
-/// have as many elements as @p TI has successors.
-bool buildConditionSets(Scop &S, BasicBlock *BB, Instruction *TI, Loop *L,
-                        __isl_keep isl_set *Domain,
-                        DenseMap<BasicBlock *, isl::set> &InvalidDomainMap,
-                        SmallVectorImpl<__isl_give isl_set *> &ConditionSets);
 
 /// Static Control Part
 ///
 /// A Scop is the polyhedral representation of a control flow region detected
 /// by the Scop detection. It is generated by translating the LLVM-IR and
 /// abstracting its effects.
 ///
 /// A Scop consists of a set of:
Scop(Region &R, ScalarEvolution &SE, LoopInfo &LI, DominatorTree &DT,
        ScopDetection::DetectionContext &DC, OptimizationRemarkEmitter &ORE);
 
   //@}
 
   /// Initialize this ScopBuilder.
   void init(AliasAnalysis &AA, AssumptionCache &AC, DominatorTree &DT,
             LoopInfo &LI);
 
-  /// Propagate domains that are known due to graph properties.
-  ///
-  /// As a CFG is mostly structured we use the graph properties to propagate
-  /// domains without the need to compute all path conditions. In particular, if
-  /// a block A dominates a block B and B post-dominates A we know that the
-  /// domain of B is a superset of the domain of A. As we do not have
-  /// post-dominator information available here we use the less precise region
-  /// information. Given a region R, we know that the exit is always executed if
-  /// the entry was executed, thus the domain of the exit is a superset of the
-  /// domain of the entry. In case the exit can only be reached from within the
-  /// region the domains are in fact equal. This function will use this property
-  /// to avoid the generation of condition constraints that determine when a
-  /// branch is taken. If @p BB is a region entry block we will propagate its
-  /// domain to the region exit block. Additionally, we put the region exit
-  /// 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 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> &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.
-  ///
-  /// @returns The domain under which @p BB is executed.
-  isl::set getPredecessorDomainConstraints(BasicBlock *BB, isl::set Domain,
-                                           DominatorTree &DT, LoopInfo &LI);
-
-  /// 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 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,
-      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 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> &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 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> &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 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> &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 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> &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);
public:
   void invalidateScopArrayInfo(Value *BasePtr, MemoryKind Kind) {
     auto It = ScopArrayInfoMap.find(std::make_pair(BasePtr, Kind));
     if (It == ScopArrayInfoMap.end())
       return;
     ScopArrayInfoSet.remove(It->second.get());
     ScopArrayInfoMap.erase(It);
   }
 
+  /// Set new isl context.
   void setContext(isl::set NewContext);
 
+  /// Set new maximal loop depth. If @p Depth is smaller than current value,
+  /// then maximal loop dpeth is not updated.
+  void setMaxLoopDepth(unsigned Depth) {
+    MaxLoopDepth = std::max(MaxLoopDepth, Depth);
+  }
+
   /// Align the parameters in the statement to the scop context
   void realignParams();
 
   /// Return true if this SCoP can be profitably optimized.
   ///
   /// @param ScalarsAreUnprofitable Never consider statements with scalar writes
   ///                               as profitably optimizable.
   ///
   /// @return Whether this SCoP can be profitably optimized.
   bool isProfitable(bool ScalarsAreUnprofitable) const;
 
   /// Return true if the SCoP contained at least one error block.
   bool hasErrorBlock() const { return HasErrorBlock; }
 
+  /// Notify SCoP that it contains an error block
+  void notifyErrorBlock() { HasErrorBlock = true; }
+
   /// Return true if the underlying region has a single exiting block.
   bool hasSingleExitEdge() const { return HasSingleExitEdge; }
 
   /// Print the static control part.
   ///
   /// @param OS The output stream the static control part is printed to.
   /// @param PrintInstructions Whether to print the statement's instructions as
   ///                          well.
PWACtx getPwAff(const SCEV *E, BasicBlock *BB = nullptr,
                   bool NonNegative = false);
 
   /// Compute the isl representation for the SCEV @p E
   ///
   /// This function is like @see Scop::getPwAff() but strips away the invalid
   /// domain part associated with the piecewise affine function.
   isl::pw_aff getPwAffOnly(const SCEV *E, BasicBlock *BB = nullptr);
 
+  /// Check if an <nsw> AddRec for the loop L is cached.
+  bool hasNSWAddRecForLoop(Loop *L) { return Affinator.hasNSWAddRecForLoop(L); }
+
   /// Return the domain of @p Stmt.
   ///
   /// @param Stmt The statement for which the conditions should be returned.
   isl::set getDomainConditions(const ScopStmt *Stmt) const;
 
   /// Return the domain of @p BB.
   ///
   /// @param BB The block for which the conditions should be returned.
   isl::set getDomainConditions(BasicBlock *BB) const;
 
+  /// Return the domain of @p BB. If it does not exist, create an empty one.
+  isl::set &findAndConstructDomain(BasicBlock *BB) { return DomainMap[BB]; }
+
+  /// Check if domain is determined for @p BB.
+  bool isDomainDefined(BasicBlock *BB) const { return DomainMap.count(BB) > 0; }
+
+  /// Set domain for @p BB.
+  void setDomain(BasicBlock *BB, isl::set &Domain) { DomainMap[BB] = Domain; }
+
   /// Get a union set containing the iteration domains of all statements.
   isl::union_set getDomains() const;
 
   /// Get a union map of all may-writes performed in the SCoP.
   isl::union_map getMayWrites();
 
   /// Get a union map of all must-writes performed in the SCoP.
   isl::union_map getMustWrites();

polly/lib/Analysis/ScopBuilder.cpp

 #include "polly/Support/GICHelper.h"
 #include "polly/Support/ISLTools.h"
 #include "polly/Support/SCEVValidator.h"
 #include "polly/Support/ScopHelper.h"
 #include "polly/Support/VirtualInstruction.h"
 #include "llvm/ADT/ArrayRef.h"
 #include "llvm/ADT/EquivalenceClasses.h"
 #include "llvm/ADT/PostOrderIterator.h"
+#include "llvm/ADT/SmallSet.h"
 #include "llvm/ADT/Statistic.h"
 #include "llvm/Analysis/AliasAnalysis.h"
 #include "llvm/Analysis/AssumptionCache.h"
 #include "llvm/Analysis/Loads.h"
 #include "llvm/Analysis/LoopInfo.h"
 #include "llvm/Analysis/OptimizationRemarkEmitter.h"
 #include "llvm/Analysis/RegionInfo.h"
 #include "llvm/Analysis/RegionIterator.h"
static cl::opt<GranularityChoice> StmtGranularity(
     cl::values(clEnumValN(GranularityChoice::BasicBlocks, "bb",
                           "One statement per basic block"),
                clEnumValN(GranularityChoice::ScalarIndependence, "scalar-indep",
                           "Scalar independence heuristic"),
                clEnumValN(GranularityChoice::Stores, "store",
                           "Store-level granularity")),
     cl::init(GranularityChoice::ScalarIndependence), cl::cat(PollyCategory));
 
+/// 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>();
+}
+
+/// Return the @p idx'th block that is executed after @p RN.
+static inline BasicBlock *
+getRegionNodeSuccessor(RegionNode *RN, Instruction *TI, unsigned idx) {
+  if (RN->isSubRegion()) {
+    assert(idx == 0);
+    return RN->getNodeAs<Region>()->getExit();
+  }
+  return TI->getSuccessor(idx);
+}
+
+static bool containsErrorBlock(RegionNode *RN, const Region &R, LoopInfo &LI,
+                               const DominatorTree &DT) {
+  if (!RN->isSubRegion())
+    return isErrorBlock(*RN->getNodeAs<BasicBlock>(), R, LI, DT);
+  for (BasicBlock *BB : RN->getNodeAs<Region>()->blocks())
+    if (isErrorBlock(*BB, R, LI, DT))
+      return true;
+  return false;
+}
+
+///}
+
+/// Create a map to map from a given iteration to a subsequent iteration.
+///
+/// This map maps from SetSpace -> SetSpace where the dimensions @p Dim
+/// is incremented by one and all other dimensions are equal, e.g.,
+///             [i0, i1, i2, i3] -> [i0, i1, i2 + 1, i3]
+///
+/// if @p Dim is 2 and @p SetSpace has 4 dimensions.
+static isl::map createNextIterationMap(isl::space SetSpace, unsigned Dim) {
+  isl::space MapSpace = SetSpace.map_from_set();
+  isl::map NextIterationMap = isl::map::universe(MapSpace);
+  for (unsigned u = 0; u < NextIterationMap.dim(isl::dim::in); u++)
+    if (u != Dim)
+      NextIterationMap =
+          NextIterationMap.equate(isl::dim::in, u, isl::dim::out, u);
+  isl::constraint C =
+      isl::constraint::alloc_equality(isl::local_space(MapSpace));
+  C = C.set_constant_si(1);
+  C = C.set_coefficient_si(isl::dim::in, Dim, 1);
+  C = C.set_coefficient_si(isl::dim::out, Dim, -1);
+  NextIterationMap = NextIterationMap.add_constraint(C);
+  return NextIterationMap;
+}
+
+/// Add @p BSet to set @p BoundedParts if @p BSet is bounded.
+static isl::set collectBoundedParts(isl::set S) {
+  isl::set BoundedParts = isl::set::empty(S.get_space());
+  for (isl::basic_set BSet : S.get_basic_set_list())
+    if (BSet.is_bounded())
+      BoundedParts = BoundedParts.unite(isl::set(BSet));
+  return BoundedParts;
+}
+
+/// Compute the (un)bounded parts of @p S wrt. to dimension @p Dim.
+///
+/// @returns A separation of @p S into first an unbounded then a bounded subset,
+///          both with regards to the dimension @p Dim.
+static std::pair<isl::set, isl::set> partitionSetParts(isl::set S,
+                                                       unsigned Dim) {
+  for (unsigned u = 0, e = S.n_dim(); u < e; u++)
+    S = S.lower_bound_si(isl::dim::set, u, 0);
+
+  unsigned NumDimsS = S.n_dim();
+  isl::set OnlyDimS = S;
+
+  // Remove dimensions that are greater than Dim as they are not interesting.
+  assert(NumDimsS >= Dim + 1);
+  OnlyDimS = OnlyDimS.project_out(isl::dim::set, Dim + 1, NumDimsS - Dim - 1);
+
+  // Create artificial parametric upper bounds for dimensions smaller than Dim
+  // as we are not interested in them.
+  OnlyDimS = OnlyDimS.insert_dims(isl::dim::param, 0, Dim);
+
+  for (unsigned u = 0; u < Dim; u++) {
+    isl::constraint C = isl::constraint::alloc_inequality(
+        isl::local_space(OnlyDimS.get_space()));
+    C = C.set_coefficient_si(isl::dim::param, u, 1);
+    C = C.set_coefficient_si(isl::dim::set, u, -1);
+    OnlyDimS = OnlyDimS.add_constraint(C);
+  }
+
+  // Collect all bounded parts of OnlyDimS.
+  isl::set BoundedParts = collectBoundedParts(OnlyDimS);
+
+  // Create the dimensions greater than Dim again.
+  BoundedParts =
+      BoundedParts.insert_dims(isl::dim::set, Dim + 1, NumDimsS - Dim - 1);
+
+  // Remove the artificial upper bound parameters again.
+  BoundedParts = BoundedParts.remove_dims(isl::dim::param, 0, Dim);
+
+  isl::set UnboundedParts = S.subtract(BoundedParts);
+  return std::make_pair(UnboundedParts, BoundedParts);
+}
+
+/// Create the conditions under which @p L @p Pred @p R is true.
+static isl::set buildConditionSet(ICmpInst::Predicate Pred, isl::pw_aff L,
+                                  isl::pw_aff R) {
+  switch (Pred) {
+  case ICmpInst::ICMP_EQ:
+    return L.eq_set(R);
+  case ICmpInst::ICMP_NE:
+    return L.ne_set(R);
+  case ICmpInst::ICMP_SLT:
+    return L.lt_set(R);
+  case ICmpInst::ICMP_SLE:
+    return L.le_set(R);
+  case ICmpInst::ICMP_SGT:
+    return L.gt_set(R);
+  case ICmpInst::ICMP_SGE:
+    return L.ge_set(R);
+  case ICmpInst::ICMP_ULT:
+    return L.lt_set(R);
+  case ICmpInst::ICMP_UGT:
+    return L.gt_set(R);
+  case ICmpInst::ICMP_ULE:
+    return L.le_set(R);
+  case ICmpInst::ICMP_UGE:
+    return L.ge_set(R);
+  default:
+    llvm_unreachable("Non integer predicate not supported");
+  }
+}
+
+isl::set ScopBuilder::adjustDomainDimensions(isl::set Dom, Loop *OldL,
+                                             Loop *NewL) {
+  // If the loops are the same there is nothing to do.
+  if (NewL == OldL)
+    return Dom;
+
+  int OldDepth = scop->getRelativeLoopDepth(OldL);
+  int NewDepth = scop->getRelativeLoopDepth(NewL);
+  // If both loops are non-affine loops there is nothing to do.
+  if (OldDepth == -1 && NewDepth == -1)
+    return Dom;
+
+  // Distinguish three cases:
+  //   1) The depth is the same but the loops are not.
+  //      => One loop was left one was entered.
+  //   2) The depth increased from OldL to NewL.
+  //      => One loop was entered, none was left.
+  //   3) The depth decreased from OldL to NewL.
+  //      => Loops were left were difference of the depths defines how many.
+  if (OldDepth == NewDepth) {
+    assert(OldL->getParentLoop() == NewL->getParentLoop());
+    Dom = Dom.project_out(isl::dim::set, NewDepth, 1);
+    Dom = Dom.add_dims(isl::dim::set, 1);
+  } else if (OldDepth < NewDepth) {
+    assert(OldDepth + 1 == NewDepth);
+    auto &R = scop->getRegion();
+    (void)R;
+    assert(NewL->getParentLoop() == OldL ||
+           ((!OldL || !R.contains(OldL)) && R.contains(NewL)));
+    Dom = Dom.add_dims(isl::dim::set, 1);
+  } else {
+    assert(OldDepth > NewDepth);
+    int Diff = OldDepth - NewDepth;
+    int NumDim = Dom.n_dim();
+    assert(NumDim >= Diff);
+    Dom = Dom.project_out(isl::dim::set, NumDim - Diff, Diff);
+  }
+
+  return Dom;
+}
+
+/// Compute the isl representation for the SCEV @p E in this BB.
+///
+/// @param BB               The BB for which isl representation is to be
+/// computed.
+/// @param InvalidDomainMap A map of BB to their invalid domains.
+/// @param E                The SCEV that should be translated.
+/// @param NonNegative      Flag to indicate the @p E has to be non-negative.
+///
+/// Note that this function will also adjust the invalid context accordingly.
+
+__isl_give isl_pw_aff *
+ScopBuilder::getPwAff(BasicBlock *BB,
+                      DenseMap<BasicBlock *, isl::set> &InvalidDomainMap,
+                      const SCEV *E, bool NonNegative) {
+  PWACtx PWAC = scop->getPwAff(E, BB, NonNegative);
+  InvalidDomainMap[BB] = InvalidDomainMap[BB].unite(PWAC.second);
+  return PWAC.first.release();
+}
+
+/// Build condition sets for unsigned ICmpInst(s).
+/// Special handling is required for unsigned operands to ensure that if
+/// MSB (aka the Sign bit) is set for an operands in an unsigned ICmpInst
+/// it should wrap around.
+///
+/// @param IsStrictUpperBound holds information on the predicate relation
+/// between TestVal and UpperBound, i.e,
+/// TestVal < UpperBound  OR  TestVal <= UpperBound
+__isl_give isl_set *ScopBuilder::buildUnsignedConditionSets(
+    BasicBlock *BB, Value *Condition, __isl_keep isl_set *Domain,
+    const SCEV *SCEV_TestVal, const SCEV *SCEV_UpperBound,
+    DenseMap<BasicBlock *, isl::set> &InvalidDomainMap,
+    bool IsStrictUpperBound) {
+  // Do not take NonNeg assumption on TestVal
+  // as it might have MSB (Sign bit) set.
+  isl_pw_aff *TestVal = getPwAff(BB, InvalidDomainMap, SCEV_TestVal, false);
+  // Take NonNeg assumption on UpperBound.
+  isl_pw_aff *UpperBound =
+      getPwAff(BB, InvalidDomainMap, SCEV_UpperBound, true);
+
+  // 0 <= TestVal
+  isl_set *First =
+      isl_pw_aff_le_set(isl_pw_aff_zero_on_domain(isl_local_space_from_space(
+                            isl_pw_aff_get_domain_space(TestVal))),
+                        isl_pw_aff_copy(TestVal));
+
+  isl_set *Second;
+  if (IsStrictUpperBound)
+    // TestVal < UpperBound
+    Second = isl_pw_aff_lt_set(TestVal, UpperBound);
+  else
+    // TestVal <= UpperBound
+    Second = isl_pw_aff_le_set(TestVal, UpperBound);
+
+  isl_set *ConsequenceCondSet = isl_set_intersect(First, Second);
+  return ConsequenceCondSet;
+}
+
+bool ScopBuilder::buildConditionSets(
+    BasicBlock *BB, SwitchInst *SI, Loop *L, __isl_keep isl_set *Domain,
+    DenseMap<BasicBlock *, isl::set> &InvalidDomainMap,
+    SmallVectorImpl<__isl_give isl_set *> &ConditionSets) {
+  Value *Condition = getConditionFromTerminator(SI);
+  assert(Condition && "No condition for switch");
+
+  isl_pw_aff *LHS, *RHS;
+  LHS = getPwAff(BB, InvalidDomainMap, SE.getSCEVAtScope(Condition, L));
+
+  unsigned NumSuccessors = SI->getNumSuccessors();
+  ConditionSets.resize(NumSuccessors);
+  for (auto &Case : SI->cases()) {
+    unsigned Idx = Case.getSuccessorIndex();
+    ConstantInt *CaseValue = Case.getCaseValue();
+
+    RHS = getPwAff(BB, InvalidDomainMap, SE.getSCEV(CaseValue));
+    isl_set *CaseConditionSet =
+        buildConditionSet(ICmpInst::ICMP_EQ, isl::manage_copy(LHS),
+                          isl::manage(RHS))
+            .release();
+    ConditionSets[Idx] = isl_set_coalesce(
+        isl_set_intersect(CaseConditionSet, isl_set_copy(Domain)));
+  }
+
+  assert(ConditionSets[0] == nullptr && "Default condition set was set");
+  isl_set *ConditionSetUnion = isl_set_copy(ConditionSets[1]);
+  for (unsigned u = 2; u < NumSuccessors; u++)
+    ConditionSetUnion =
+        isl_set_union(ConditionSetUnion, isl_set_copy(ConditionSets[u]));
+  ConditionSets[0] = isl_set_subtract(isl_set_copy(Domain), ConditionSetUnion);
+
+  isl_pw_aff_free(LHS);
+
+  return true;
+}
+
+bool ScopBuilder::buildConditionSets(
+    BasicBlock *BB, Value *Condition, Instruction *TI, Loop *L,
+    __isl_keep isl_set *Domain,
+    DenseMap<BasicBlock *, isl::set> &InvalidDomainMap,
+    SmallVectorImpl<__isl_give isl_set *> &ConditionSets) {
+  isl_set *ConsequenceCondSet = nullptr;
+
+  if (auto Load = dyn_cast<LoadInst>(Condition)) {
+    const SCEV *LHSSCEV = SE.getSCEVAtScope(Load, L);
+    const SCEV *RHSSCEV = SE.getZero(LHSSCEV->getType());
+    bool NonNeg = false;
+    isl_pw_aff *LHS = getPwAff(BB, InvalidDomainMap, LHSSCEV, NonNeg);
+    isl_pw_aff *RHS = getPwAff(BB, InvalidDomainMap, RHSSCEV, NonNeg);
+    ConsequenceCondSet = buildConditionSet(ICmpInst::ICMP_SLE, isl::manage(LHS),
+                                           isl::manage(RHS))
+                             .release();
+  } else if (auto *PHI = dyn_cast<PHINode>(Condition)) {
+    auto *Unique = dyn_cast<ConstantInt>(
+        getUniqueNonErrorValue(PHI, &scop->getRegion(), LI, DT));
+
+    if (Unique->isZero())
+      ConsequenceCondSet = isl_set_empty(isl_set_get_space(Domain));
+    else
+      ConsequenceCondSet = isl_set_universe(isl_set_get_space(Domain));
+  } else if (auto *CCond = dyn_cast<ConstantInt>(Condition)) {
+    if (CCond->isZero())
+      ConsequenceCondSet = isl_set_empty(isl_set_get_space(Domain));
+    else
+      ConsequenceCondSet = isl_set_universe(isl_set_get_space(Domain));
+  } else if (BinaryOperator *BinOp = dyn_cast<BinaryOperator>(Condition)) {
+    auto Opcode = BinOp->getOpcode();
+    assert(Opcode == Instruction::And || Opcode == Instruction::Or);
+
+    bool Valid = buildConditionSets(BB, BinOp->getOperand(0), TI, L, Domain,
+                                    InvalidDomainMap, ConditionSets) &&
+                 buildConditionSets(BB, BinOp->getOperand(1), TI, L, Domain,
+                                    InvalidDomainMap, ConditionSets);
+    if (!Valid) {
+      while (!ConditionSets.empty())
+        isl_set_free(ConditionSets.pop_back_val());
+      return false;
+    }
+
+    isl_set_free(ConditionSets.pop_back_val());
+    isl_set *ConsCondPart0 = ConditionSets.pop_back_val();
+    isl_set_free(ConditionSets.pop_back_val());
+    isl_set *ConsCondPart1 = ConditionSets.pop_back_val();
+
+    if (Opcode == Instruction::And)
+      ConsequenceCondSet = isl_set_intersect(ConsCondPart0, ConsCondPart1);
+    else
+      ConsequenceCondSet = isl_set_union(ConsCondPart0, ConsCondPart1);
+  } else {
+    auto *ICond = dyn_cast<ICmpInst>(Condition);
+    assert(ICond &&
+           "Condition of exiting branch was neither constant nor ICmp!");
+
+    Region &R = scop->getRegion();
+
+    isl_pw_aff *LHS, *RHS;
+    // For unsigned comparisons we assumed the signed bit of neither operand
+    // to be set. The comparison is equal to a signed comparison under this
+    // assumption.
+    bool NonNeg = ICond->isUnsigned();
+    const SCEV *LeftOperand = SE.getSCEVAtScope(ICond->getOperand(0), L),
+               *RightOperand = SE.getSCEVAtScope(ICond->getOperand(1), L);
+
+    LeftOperand = tryForwardThroughPHI(LeftOperand, R, SE, LI, DT);
+    RightOperand = tryForwardThroughPHI(RightOperand, R, SE, LI, DT);
+
+    switch (ICond->getPredicate()) {
+    case ICmpInst::ICMP_ULT:
+      ConsequenceCondSet =
+          buildUnsignedConditionSets(BB, Condition, Domain, LeftOperand,
+                                     RightOperand, InvalidDomainMap, true);
+      break;
+    case ICmpInst::ICMP_ULE:
+      ConsequenceCondSet =
+          buildUnsignedConditionSets(BB, Condition, Domain, LeftOperand,
+                                     RightOperand, InvalidDomainMap, false);
+      break;
+    case ICmpInst::ICMP_UGT:
+      ConsequenceCondSet =
+          buildUnsignedConditionSets(BB, Condition, Domain, RightOperand,
+                                     LeftOperand, InvalidDomainMap, true);
+      break;
+    case ICmpInst::ICMP_UGE:
+      ConsequenceCondSet =
+          buildUnsignedConditionSets(BB, Condition, Domain, RightOperand,
+                                     LeftOperand, InvalidDomainMap, false);
+      break;
+    default:
+      LHS = getPwAff(BB, InvalidDomainMap, LeftOperand, NonNeg);
+      RHS = getPwAff(BB, InvalidDomainMap, RightOperand, NonNeg);
+      ConsequenceCondSet = buildConditionSet(ICond->getPredicate(),
+                                             isl::manage(LHS), isl::manage(RHS))
+                               .release();
+      break;
+    }
+  }
+
+  // If no terminator was given we are only looking for parameter constraints
+  // under which @p Condition is true/false.
+  if (!TI)
+    ConsequenceCondSet = isl_set_params(ConsequenceCondSet);
+  assert(ConsequenceCondSet);
+  ConsequenceCondSet = isl_set_coalesce(
+      isl_set_intersect(ConsequenceCondSet, isl_set_copy(Domain)));
+
+  isl_set *AlternativeCondSet = nullptr;
+  bool TooComplex =
+      isl_set_n_basic_set(ConsequenceCondSet) >= MaxDisjunctsInDomain;
+
+  if (!TooComplex) {
+    AlternativeCondSet = isl_set_subtract(isl_set_copy(Domain),
+                                          isl_set_copy(ConsequenceCondSet));
+    TooComplex =
+        isl_set_n_basic_set(AlternativeCondSet) >= MaxDisjunctsInDomain;
+  }
+
+  if (TooComplex) {
+    scop->invalidate(COMPLEXITY, TI ? TI->getDebugLoc() : DebugLoc(),
+                     TI ? TI->getParent() : nullptr /* BasicBlock */);
+    isl_set_free(AlternativeCondSet);
+    isl_set_free(ConsequenceCondSet);
+    return false;
+  }
+
+  ConditionSets.push_back(ConsequenceCondSet);
+  ConditionSets.push_back(isl_set_coalesce(AlternativeCondSet));
+
+  return true;
+}
+
+bool ScopBuilder::buildConditionSets(
+    BasicBlock *BB, Instruction *TI, Loop *L, __isl_keep isl_set *Domain,
+    DenseMap<BasicBlock *, isl::set> &InvalidDomainMap,
+    SmallVectorImpl<__isl_give isl_set *> &ConditionSets) {
+  if (SwitchInst *SI = dyn_cast<SwitchInst>(TI))
+    return buildConditionSets(BB, SI, L, Domain, InvalidDomainMap,
+                              ConditionSets);
+
+  assert(isa<BranchInst>(TI) && "Terminator was neither branch nor switch.");
+
+  if (TI->getNumSuccessors() == 1) {
+    ConditionSets.push_back(isl_set_copy(Domain));
+    return true;
+  }
+
+  Value *Condition = getConditionFromTerminator(TI);
+  assert(Condition && "No condition for Terminator");
+
+  return buildConditionSets(BB, Condition, TI, L, Domain, InvalidDomainMap,
+                            ConditionSets);
+}
+
+bool ScopBuilder::propagateDomainConstraints(
+    Region *R, 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.
+
+  ReversePostOrderTraversal<Region *> RTraversal(R);
+  for (auto *RN : RTraversal) {
+    // Recurse for affine subregions but go on for basic blocks and non-affine
+    // subregions.
+    if (RN->isSubRegion()) {
+      Region *SubRegion = RN->getNodeAs<Region>();
+      if (!scop->isNonAffineSubRegion(SubRegion)) {
+        if (!propagateDomainConstraints(SubRegion, InvalidDomainMap))
+          return false;
+        continue;
+      }
+    }
+
+    BasicBlock *BB = getRegionNodeBasicBlock(RN);
+    isl::set &Domain = scop->findAndConstructDomain(BB);
+    assert(Domain);
+
+    // Under the union of all predecessor conditions we can reach this block.
+    isl::set PredDom = getPredecessorDomainConstraints(BB, Domain);
+    Domain = Domain.intersect(PredDom).coalesce();
+    Domain = Domain.align_params(scop->getParamSpace());
+
+    Loop *BBLoop = getRegionNodeLoop(RN, LI);
+    if (BBLoop && BBLoop->getHeader() == BB && scop->contains(BBLoop))
+      if (!addLoopBoundsToHeaderDomain(BBLoop, InvalidDomainMap))
+        return false;
+  }
+
+  return true;
+}
+
+void ScopBuilder::propagateDomainConstraintsToRegionExit(
+    BasicBlock *BB, Loop *BBLoop,
+    SmallPtrSetImpl<BasicBlock *> &FinishedExitBlocks,
+    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.
+  auto *RI = scop->getRegion().getRegionInfo();
+  auto *BBReg = RI ? RI->getRegionFor(BB) : nullptr;
+  auto *ExitBB = BBReg ? BBReg->getExit() : nullptr;
+  if (!BBReg || BBReg->getEntry() != BB || !scop->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.
+  auto *L = BBLoop;
+  while (L && scop->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 = scop->findAndConstructDomain(BB);
+  assert(Domain && "Cannot propagate a nullptr");
+
+  Loop *ExitBBLoop = getFirstNonBoxedLoopFor(ExitBB, LI, scop->getBoxedLoops());
+
+  // 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 = adjustDomainDimensions(Domain, BBLoop, ExitBBLoop);
+  isl::set &ExitDomain = scop->findAndConstructDomain(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);
+}
+
+isl::set ScopBuilder::getPredecessorDomainConstraints(BasicBlock *BB,
+                                                      isl::set Domain) {
+  // If @p BB is the ScopEntry we are done
+  if (scop->getRegion().getEntry() == BB)
+    return isl::set::universe(Domain.get_space());
+
+  // The region info of this function.
+  auto &RI = *scop->getRegion().getRegionInfo();
+
+  Loop *BBLoop = getFirstNonBoxedLoopFor(BB, LI, scop->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.
+  isl::set PredDom = isl::set::empty(Domain.get_space());
+
+  // 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.
+    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.
+    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 (PredR->getExit() == BB) {
+      PredBB = PredR->getEntry();
+      PropagatedRegions.insert(PredR);
+    }
+
+    isl::set PredBBDom = scop->getDomainConditions(PredBB);
+    Loop *PredBBLoop =
+        getFirstNonBoxedLoopFor(PredBB, LI, scop->getBoxedLoops());
+    PredBBDom = adjustDomainDimensions(PredBBDom, PredBBLoop, BBLoop);
+    PredDom = PredDom.unite(PredBBDom);
+  }
+
+  return PredDom;
+}
+
+bool ScopBuilder::addLoopBoundsToHeaderDomain(
+    Loop *L, DenseMap<BasicBlock *, isl::set> &InvalidDomainMap) {
+  int LoopDepth = scop->getRelativeLoopDepth(L);
+  assert(LoopDepth >= 0 && "Loop in region should have at least depth one");
+
+  BasicBlock *HeaderBB = L->getHeader();
+  assert(scop->isDomainDefined(HeaderBB));
+  isl::set &HeaderBBDom = scop->findAndConstructDomain(HeaderBB);
+
+  isl::map NextIterationMap =
+      createNextIterationMap(HeaderBBDom.get_space(), LoopDepth);
+
+  isl::set UnionBackedgeCondition = HeaderBBDom.empty(HeaderBBDom.get_space());
+
+  SmallVector<BasicBlock *, 4> LatchBlocks;
+  L->getLoopLatches(LatchBlocks);
+
+  for (BasicBlock *LatchBB : LatchBlocks) {
+    // If the latch is only reachable via error statements we skip it.
+    if (!scop->isDomainDefined(LatchBB))
+      continue;
+
+    isl::set LatchBBDom = scop->getDomainConditions(LatchBB);
+
+    isl::set BackedgeCondition = nullptr;
+
+    Instruction *TI = LatchBB->getTerminator();
+    BranchInst *BI = dyn_cast<BranchInst>(TI);
+    assert(BI && "Only branch instructions allowed in loop latches");
+
+    if (BI->isUnconditional())
+      BackedgeCondition = LatchBBDom;
+    else {
+      SmallVector<isl_set *, 8> ConditionSets;
+      int idx = BI->getSuccessor(0) != HeaderBB;
+      if (!buildConditionSets(LatchBB, TI, L, LatchBBDom.get(),
+                              InvalidDomainMap, ConditionSets))
+        return false;
+
+      // Free the non back edge condition set as we do not need it.
+      isl_set_free(ConditionSets[1 - idx]);
+
+      BackedgeCondition = isl::manage(ConditionSets[idx]);
+    }
+
+    int LatchLoopDepth = scop->getRelativeLoopDepth(LI.getLoopFor(LatchBB));
+    assert(LatchLoopDepth >= LoopDepth);
+    BackedgeCondition = BackedgeCondition.project_out(
+        isl::dim::set, LoopDepth + 1, LatchLoopDepth - LoopDepth);
+    UnionBackedgeCondition = UnionBackedgeCondition.unite(BackedgeCondition);
+  }
+
+  isl::map ForwardMap = ForwardMap.lex_le(HeaderBBDom.get_space());
+  for (int i = 0; i < LoopDepth; i++)
+    ForwardMap = ForwardMap.equate(isl::dim::in, i, isl::dim::out, i);
+
+  isl::set UnionBackedgeConditionComplement =
+      UnionBackedgeCondition.complement();
+  UnionBackedgeConditionComplement =
+      UnionBackedgeConditionComplement.lower_bound_si(isl::dim::set, LoopDepth,
+                                                      0);
+  UnionBackedgeConditionComplement =
+      UnionBackedgeConditionComplement.apply(ForwardMap);
+  HeaderBBDom = HeaderBBDom.subtract(UnionBackedgeConditionComplement);
+  HeaderBBDom = HeaderBBDom.apply(NextIterationMap);
+
+  auto Parts = partitionSetParts(HeaderBBDom, LoopDepth);
+  HeaderBBDom = 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.
+  if (scop->hasNSWAddRecForLoop(L))
+    return true;
+
+  isl::set UnboundedCtx = Parts.first.params();
+  scop->recordAssumption(INFINITELOOP, UnboundedCtx,
+                         HeaderBB->getTerminator()->getDebugLoc(),
+                         AS_RESTRICTION);
+  return true;
+}
+
 void ScopBuilder::buildInvariantEquivalenceClasses() {
   DenseMap<std::pair<const SCEV *, Type *>, LoadInst *> EquivClasses;
 
   const InvariantLoadsSetTy &RIL = scop->getRequiredInvariantLoads();
   for (LoadInst *LInst : RIL) {
     const SCEV *PointerSCEV = SE.getSCEV(LInst->getPointerOperand());
 
     Type *Ty = LInst->getType();
     LoadInst *&ClassRep = EquivClasses[std::make_pair(PointerSCEV, Ty)];
     if (ClassRep) {
       scop->addInvariantLoadMapping(LInst, ClassRep);
       continue;
     }
 
     ClassRep = LInst;
     scop->addInvariantEquivClass(
         InvariantEquivClassTy{PointerSCEV, MemoryAccessList(), nullptr, Ty});
   }
 }
 
+bool ScopBuilder::buildDomains(
+    Region *R, DenseMap<BasicBlock *, isl::set> &InvalidDomainMap) {
+  bool IsOnlyNonAffineRegion = scop->isNonAffineSubRegion(R);
+  auto *EntryBB = R->getEntry();
+  auto *L = IsOnlyNonAffineRegion ? nullptr : LI.getLoopFor(EntryBB);
+  int LD = scop->getRelativeLoopDepth(L);
+  auto *S =
+      isl_set_universe(isl_space_set_alloc(scop->getIslCtx().get(), 0, LD + 1));
+
+  while (LD-- >= 0) {
+    L = L->getParentLoop();
+  }
+
+  InvalidDomainMap[EntryBB] = isl::manage(isl_set_empty(isl_set_get_space(S)));
+  isl::noexceptions::set Domain = isl::manage(S);
+  scop->setDomain(EntryBB, Domain);
+
+  if (IsOnlyNonAffineRegion)
+    return !containsErrorBlock(R->getNode(), *R, LI, DT);
+
+  if (!buildDomainsWithBranchConstraints(R, InvalidDomainMap))
+    return false;
+
+  if (!propagateDomainConstraints(R, 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, InvalidDomainMap))
+    return false;
+
+  return true;
+}
+
+bool ScopBuilder::buildDomainsWithBranchConstraints(
+    Region *R, 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.
+
+  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.
+    if (RN->isSubRegion()) {
+      Region *SubRegion = RN->getNodeAs<Region>();
+      if (!scop->isNonAffineSubRegion(SubRegion)) {
+        if (!buildDomainsWithBranchConstraints(SubRegion, InvalidDomainMap))
+          return false;
+        continue;
+      }
+    }
+
+    if (containsErrorBlock(RN, scop->getRegion(), LI, DT))
+      scop->notifyErrorBlock();
+    ;
+
+    BasicBlock *BB = getRegionNodeBasicBlock(RN);
+    Instruction *TI = BB->getTerminator();
+
+    if (isa<UnreachableInst>(TI))
+      continue;
+
+    if (!scop->isDomainDefined(BB))
+      continue;
+    isl::set Domain = scop->getDomainConditions(BB);
+
+    scop->setMaxLoopDepth(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.
+    propagateDomainConstraintsToRegionExit(BB, BBLoop, FinishedExitBlocks,
+                                           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.
+    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.
+    SmallVector<isl_set *, 8> ConditionSets;
+    if (RN->isSubRegion())
+      ConditionSets.push_back(Domain.copy());
+    else if (!buildConditionSets(BB, TI, BBLoop, Domain.get(), InvalidDomainMap,
+                                 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.
+    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 (!scop->contains(SuccBB))
+        continue;
+
+      // 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, scop->getBoxedLoops());
+
+      CondSet = adjustDomainDimensions(CondSet, 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.
+      isl::set &SuccDomain = scop->findAndConstructDomain(SuccBB);
+
+      if (SuccDomain) {
+        SuccDomain = SuccDomain.unite(CondSet).coalesce();
+      } else {
+        // Initialize the invalid domain.
+        InvalidDomainMap[SuccBB] = CondSet.empty(CondSet.get_space());
+        SuccDomain = CondSet;
+      }
+
+      SuccDomain = SuccDomain.detect_equalities();
+
+      // Check if the maximal number of domain disjunctions was reached.
+      // In case this happens we will clean up and bail.
+      if (SuccDomain.n_basic_set() < MaxDisjunctsInDomain)
+        continue;
+
+      scop->invalidate(COMPLEXITY, DebugLoc());
+      while (++u < ConditionSets.size())
+        isl_set_free(ConditionSets[u]);
+      return false;
+    }
+  }
+
+  return true;
+}
+
+bool ScopBuilder::propagateInvalidStmtDomains(
+    Region *R, 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.
+    if (RN->isSubRegion()) {
+      Region *SubRegion = RN->getNodeAs<Region>();
+      if (!scop->isNonAffineSubRegion(SubRegion)) {
+        propagateInvalidStmtDomains(SubRegion, InvalidDomainMap);
+        continue;
+      }
+    }
+
+    bool ContainsErrorBlock = containsErrorBlock(RN, scop->getRegion(), LI, DT);
+    BasicBlock *BB = getRegionNodeBasicBlock(RN);
+    isl::set &Domain = scop->findAndConstructDomain(BB);
+    assert(Domain && "Cannot propagate a nullptr");
+
+    isl::set InvalidDomain = InvalidDomainMap[BB];
+
+    bool IsInvalidBlock = ContainsErrorBlock || Domain.is_subset(InvalidDomain);
+
+    if (!IsInvalidBlock) {
+      InvalidDomain = InvalidDomain.intersect(Domain);
+    } else {
+      InvalidDomain = Domain;
+      isl::set DomPar = Domain.params();
+      scop->recordAssumption(ERRORBLOCK, DomPar,
+                             BB->getTerminator()->getDebugLoc(),
+                             AS_RESTRICTION);
+      Domain = isl::set::empty(Domain.get_space());
+    }
+
+    if (InvalidDomain.is_empty()) {
+      InvalidDomainMap[BB] = InvalidDomain;
+      continue;
+    }
+
+    auto *BBLoop = getRegionNodeLoop(RN, LI);
+    auto *TI = BB->getTerminator();
+    unsigned NumSuccs = RN->isSubRegion() ? 1 : TI->getNumSuccessors();
+    for (unsigned u = 0; u < NumSuccs; u++) {
+      auto *SuccBB = getRegionNodeSuccessor(RN, TI, u);
+
+      // Skip successors outside the SCoP.
+      if (!scop->contains(SuccBB))
+        continue;
+
+      // Skip backedges.
+      if (DT.dominates(SuccBB, BB))
+        continue;
+
+      Loop *SuccBBLoop =
+          getFirstNonBoxedLoopFor(SuccBB, LI, scop->getBoxedLoops());
+
+      auto AdjustedInvalidDomain =
+          adjustDomainDimensions(InvalidDomain, BBLoop, SuccBBLoop);
+
+      isl::set SuccInvalidDomain = InvalidDomainMap[SuccBB];
+      SuccInvalidDomain = SuccInvalidDomain.unite(AdjustedInvalidDomain);
+      SuccInvalidDomain = SuccInvalidDomain.coalesce();
+
+      InvalidDomainMap[SuccBB] = SuccInvalidDomain;
+
+      // Check if the maximal number of domain disjunctions was reached.
+      // In case this happens we will bail.
+      if (SuccInvalidDomain.n_basic_set() < MaxDisjunctsInDomain)
+        continue;
+
+      InvalidDomainMap.erase(BB);
+      scop->invalidate(COMPLEXITY, TI->getDebugLoc(), TI->getParent());
+      return false;
+    }
+
+    InvalidDomainMap[BB] = InvalidDomain;
+  }
+
+  return true;
+}
+
 void ScopBuilder::buildPHIAccesses(ScopStmt *PHIStmt, PHINode *PHI,
                                    Region *NonAffineSubRegion,
                                    bool IsExitBlock) {
   // PHI nodes that are in the exit block of the region, hence if IsExitBlock is
   // true, are not modeled as ordinary PHI nodes as they are not part of the
   // region. However, we model the operands in the predecessor blocks that are
   // part of the region as regular scalar accesses.
 
for (auto &Assumption : AC.assumptions()) {
     }
 
     SmallVector<isl_set *, 2> ConditionSets;
     auto *TI = InScop ? CI->getParent()->getTerminator() : nullptr;
     BasicBlock *BB = InScop ? CI->getParent() : R.getEntry();
     auto *Dom = InScop ? isl_set_copy(scop->getDomainConditions(BB).get())
                        : isl_set_copy(scop->getContext().get());
     assert(Dom && "Cannot propagate a nullptr.");
-    bool Valid = buildConditionSets(*scop, BB, Val, TI, L, Dom,
-                                    InvalidDomainMap, ConditionSets);
+    bool Valid = buildConditionSets(BB, Val, TI, L, Dom, InvalidDomainMap,
+                                    ConditionSets);
     isl_set_free(Dom);
 
     if (!Valid)
       continue;
 
     isl_set *AssumptionCtx = nullptr;
     if (InScop) {
       AssumptionCtx = isl_set_complement(isl_set_params(ConditionSets[1]));
for (auto &Inst : *S->getRegion().getExit()) {
 
       for (auto &Op : Inst.operands())
         verifyUse(S, Op, LI);
     }
   }
 }
 #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) {
   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.
for (auto *BP : ArrayBasePointers)
                      BP, BP->getType(), false, {AF}, {nullptr}, GlobalRead);
   }
 
   buildInvariantEquivalenceClasses();
 
   /// A map from basic blocks to their invalid domains.
   DenseMap<BasicBlock *, isl::set> InvalidDomainMap;
 
-  if (!scop->buildDomains(&R, DT, LI, InvalidDomainMap)) {
+  if (!buildDomains(&R, InvalidDomainMap)) {
     LLVM_DEBUG(
         dbgs() << "Bailing-out because buildDomains encountered problems\n");
     return;
   }
 
   addUserAssumptions(AC, InvalidDomainMap);
 
   // Initialize the invalid domain.

polly/lib/Analysis/ScopInfo.cpp

void ScopStmt::realignParams() {
   for (MemoryAccess *MA : *this)
     MA->realignParams();
 
   isl::set Ctx = Parent.getContext();
   InvalidDomain = InvalidDomain.gist_params(Ctx);
   Domain = Domain.gist_params(Ctx);
 }
 
-/// Add @p BSet to set @p BoundedParts if @p BSet is bounded.
-static isl::set collectBoundedParts(isl::set S) {
-  isl::set BoundedParts = isl::set::empty(S.get_space());
-  for (isl::basic_set BSet : S.get_basic_set_list())
-    if (BSet.is_bounded())
-      BoundedParts = BoundedParts.unite(isl::set(BSet));
-  return BoundedParts;
-}
-
-/// Compute the (un)bounded parts of @p S wrt. to dimension @p Dim.
-///
-/// @returns A separation of @p S into first an unbounded then a bounded subset,
-///          both with regards to the dimension @p Dim.
-static std::pair<isl::set, isl::set> partitionSetParts(isl::set S,
-                                                       unsigned Dim) {
-  for (unsigned u = 0, e = S.n_dim(); u < e; u++)
-    S = S.lower_bound_si(isl::dim::set, u, 0);
-
-  unsigned NumDimsS = S.n_dim();
-  isl::set OnlyDimS = S;
-
-  // Remove dimensions that are greater than Dim as they are not interesting.
-  assert(NumDimsS >= Dim + 1);
-  OnlyDimS = OnlyDimS.project_out(isl::dim::set, Dim + 1, NumDimsS - Dim - 1);
-
-  // Create artificial parametric upper bounds for dimensions smaller than Dim
-  // as we are not interested in them.
-  OnlyDimS = OnlyDimS.insert_dims(isl::dim::param, 0, Dim);
-
-  for (unsigned u = 0; u < Dim; u++) {
-    isl::constraint C = isl::constraint::alloc_inequality(
-        isl::local_space(OnlyDimS.get_space()));
-    C = C.set_coefficient_si(isl::dim::param, u, 1);
-    C = C.set_coefficient_si(isl::dim::set, u, -1);
-    OnlyDimS = OnlyDimS.add_constraint(C);
-  }
-
-  // Collect all bounded parts of OnlyDimS.
-  isl::set BoundedParts = collectBoundedParts(OnlyDimS);
-
-  // Create the dimensions greater than Dim again.
-  BoundedParts =
-      BoundedParts.insert_dims(isl::dim::set, Dim + 1, NumDimsS - Dim - 1);
-
-  // Remove the artificial upper bound parameters again.
-  BoundedParts = BoundedParts.remove_dims(isl::dim::param, 0, Dim);
-
-  isl::set UnboundedParts = S.subtract(BoundedParts);
-  return std::make_pair(UnboundedParts, BoundedParts);
-}
-
-/// Create the conditions under which @p L @p Pred @p R is true.
-static isl::set buildConditionSet(ICmpInst::Predicate Pred, isl::pw_aff L,
-                                  isl::pw_aff R) {
-  switch (Pred) {
-  case ICmpInst::ICMP_EQ:
-    return L.eq_set(R);
-  case ICmpInst::ICMP_NE:
-    return L.ne_set(R);
-  case ICmpInst::ICMP_SLT:
-    return L.lt_set(R);
-  case ICmpInst::ICMP_SLE:
-    return L.le_set(R);
-  case ICmpInst::ICMP_SGT:
-    return L.gt_set(R);
-  case ICmpInst::ICMP_SGE:
-    return L.ge_set(R);
-  case ICmpInst::ICMP_ULT:
-    return L.lt_set(R);
-  case ICmpInst::ICMP_UGT:
-    return L.gt_set(R);
-  case ICmpInst::ICMP_ULE:
-    return L.le_set(R);
-  case ICmpInst::ICMP_UGE:
-    return L.ge_set(R);
-  default:
-    llvm_unreachable("Non integer predicate not supported");
-  }
-}
-
-/// Compute the isl representation for the SCEV @p E in this BB.
-///
-/// @param S                The Scop in which @p BB resides in.
-/// @param BB               The BB for which isl representation is to be
-/// computed.
-/// @param InvalidDomainMap A map of BB to their invalid domains.
-/// @param E                The SCEV that should be translated.
-/// @param NonNegative      Flag to indicate the @p E has to be non-negative.
-///
-/// Note that this function will also adjust the invalid context accordingly.
-
-__isl_give isl_pw_aff *
-getPwAff(Scop &S, BasicBlock *BB,
-         DenseMap<BasicBlock *, isl::set> &InvalidDomainMap, const SCEV *E,
-         bool NonNegative = false) {
-  PWACtx PWAC = S.getPwAff(E, BB, NonNegative);
-  InvalidDomainMap[BB] = InvalidDomainMap[BB].unite(PWAC.second);
-  return PWAC.first.release();
-}
-
-/// Build the conditions sets for the switch @p SI in the @p Domain.
-///
-/// This will fill @p ConditionSets with the conditions under which control
-/// will be moved from @p SI to its successors. Hence, @p ConditionSets will
-/// have as many elements as @p SI has successors.
-bool buildConditionSets(Scop &S, BasicBlock *BB, SwitchInst *SI, Loop *L,
-                        __isl_keep isl_set *Domain,
-                        DenseMap<BasicBlock *, isl::set> &InvalidDomainMap,
-                        SmallVectorImpl<__isl_give isl_set *> &ConditionSets) {
-  Value *Condition = getConditionFromTerminator(SI);
-  assert(Condition && "No condition for switch");
-
-  ScalarEvolution &SE = *S.getSE();
-  isl_pw_aff *LHS, *RHS;
-  LHS = getPwAff(S, BB, InvalidDomainMap, SE.getSCEVAtScope(Condition, L));
-
-  unsigned NumSuccessors = SI->getNumSuccessors();
-  ConditionSets.resize(NumSuccessors);
-  for (auto &Case : SI->cases()) {
-    unsigned Idx = Case.getSuccessorIndex();
-    ConstantInt *CaseValue = Case.getCaseValue();
-
-    RHS = getPwAff(S, BB, InvalidDomainMap, SE.getSCEV(CaseValue));
-    isl_set *CaseConditionSet =
-        buildConditionSet(ICmpInst::ICMP_EQ, isl::manage_copy(LHS),
-                          isl::manage(RHS))
-            .release();
-    ConditionSets[Idx] = isl_set_coalesce(
-        isl_set_intersect(CaseConditionSet, isl_set_copy(Domain)));
-  }
-
-  assert(ConditionSets[0] == nullptr && "Default condition set was set");
-  isl_set *ConditionSetUnion = isl_set_copy(ConditionSets[1]);
-  for (unsigned u = 2; u < NumSuccessors; u++)
-    ConditionSetUnion =
-        isl_set_union(ConditionSetUnion, isl_set_copy(ConditionSets[u]));
-  ConditionSets[0] = isl_set_subtract(isl_set_copy(Domain), ConditionSetUnion);
-
-  isl_pw_aff_free(LHS);
-
-  return true;
-}
-
-/// Build condition sets for unsigned ICmpInst(s).
-/// Special handling is required for unsigned operands to ensure that if
-/// MSB (aka the Sign bit) is set for an operands in an unsigned ICmpInst
-/// it should wrap around.
-///
-/// @param IsStrictUpperBound holds information on the predicate relation
-/// between TestVal and UpperBound, i.e,
-/// TestVal < UpperBound  OR  TestVal <= UpperBound
-__isl_give isl_set *polly::buildUnsignedConditionSets(
-    Scop &S, BasicBlock *BB, Value *Condition, __isl_keep isl_set *Domain,
-    const SCEV *SCEV_TestVal, const SCEV *SCEV_UpperBound,
-    DenseMap<BasicBlock *, isl::set> &InvalidDomainMap,
-    bool IsStrictUpperBound) {
-  // Do not take NonNeg assumption on TestVal
-  // as it might have MSB (Sign bit) set.
-  isl_pw_aff *TestVal = getPwAff(S, BB, InvalidDomainMap, SCEV_TestVal, false);
-  // Take NonNeg assumption on UpperBound.
-  isl_pw_aff *UpperBound =
-      getPwAff(S, BB, InvalidDomainMap, SCEV_UpperBound, true);
-
-  // 0 <= TestVal
-  isl_set *First =
-      isl_pw_aff_le_set(isl_pw_aff_zero_on_domain(isl_local_space_from_space(
-                            isl_pw_aff_get_domain_space(TestVal))),
-                        isl_pw_aff_copy(TestVal));
-
-  isl_set *Second;
-  if (IsStrictUpperBound)
-    // TestVal < UpperBound
-    Second = isl_pw_aff_lt_set(TestVal, UpperBound);
-  else
-    // TestVal <= UpperBound
-    Second = isl_pw_aff_le_set(TestVal, UpperBound);
-
-  isl_set *ConsequenceCondSet = isl_set_intersect(First, Second);
-  return ConsequenceCondSet;
-}
-
-bool polly::buildConditionSets(
-    Scop &S, BasicBlock *BB, Value *Condition, Instruction *TI, Loop *L,
-    __isl_keep isl_set *Domain,
-    DenseMap<BasicBlock *, isl::set> &InvalidDomainMap,
-    SmallVectorImpl<__isl_give isl_set *> &ConditionSets) {
-  ScalarEvolution &SE = *S.getSE();
-  isl_set *ConsequenceCondSet = nullptr;
-
-  if (auto Load = dyn_cast<LoadInst>(Condition)) {
-    const SCEV *LHSSCEV = SE.getSCEVAtScope(Load, L);
-    const SCEV *RHSSCEV = SE.getZero(LHSSCEV->getType());
-    bool NonNeg = false;
-    isl_pw_aff *LHS = getPwAff(S, BB, InvalidDomainMap, LHSSCEV, NonNeg);
-    isl_pw_aff *RHS = getPwAff(S, BB, InvalidDomainMap, RHSSCEV, NonNeg);
-    ConsequenceCondSet = buildConditionSet(ICmpInst::ICMP_SLE, isl::manage(LHS),
-                                           isl::manage(RHS))
-                             .release();
-  } else if (auto *PHI = dyn_cast<PHINode>(Condition)) {
-    auto *Unique = dyn_cast<ConstantInt>(
-        getUniqueNonErrorValue(PHI, &S.getRegion(), *S.getLI(), *S.getDT()));
-
-    if (Unique->isZero())
-      ConsequenceCondSet = isl_set_empty(isl_set_get_space(Domain));
-    else
-      ConsequenceCondSet = isl_set_universe(isl_set_get_space(Domain));
-  } else if (auto *CCond = dyn_cast<ConstantInt>(Condition)) {
-    if (CCond->isZero())
-      ConsequenceCondSet = isl_set_empty(isl_set_get_space(Domain));
-    else
-      ConsequenceCondSet = isl_set_universe(isl_set_get_space(Domain));
-  } else if (BinaryOperator *BinOp = dyn_cast<BinaryOperator>(Condition)) {
-    auto Opcode = BinOp->getOpcode();
-    assert(Opcode == Instruction::And || Opcode == Instruction::Or);
-
-    bool Valid = buildConditionSets(S, BB, BinOp->getOperand(0), TI, L, Domain,
-                                    InvalidDomainMap, ConditionSets) &&
-                 buildConditionSets(S, BB, BinOp->getOperand(1), TI, L, Domain,
-                                    InvalidDomainMap, ConditionSets);
-    if (!Valid) {
-      while (!ConditionSets.empty())
-        isl_set_free(ConditionSets.pop_back_val());
-      return false;
-    }
-
-    isl_set_free(ConditionSets.pop_back_val());
-    isl_set *ConsCondPart0 = ConditionSets.pop_back_val();
-    isl_set_free(ConditionSets.pop_back_val());
-    isl_set *ConsCondPart1 = ConditionSets.pop_back_val();
-
-    if (Opcode == Instruction::And)
-      ConsequenceCondSet = isl_set_intersect(ConsCondPart0, ConsCondPart1);
-    else
-      ConsequenceCondSet = isl_set_union(ConsCondPart0, ConsCondPart1);
-  } else {
-    auto *ICond = dyn_cast<ICmpInst>(Condition);
-    assert(ICond &&
-           "Condition of exiting branch was neither constant nor ICmp!");
-
-    LoopInfo &LI = *S.getLI();
-    DominatorTree &DT = *S.getDT();
-    Region &R = S.getRegion();
-
-    isl_pw_aff *LHS, *RHS;
-    // For unsigned comparisons we assumed the signed bit of neither operand
-    // to be set. The comparison is equal to a signed comparison under this
-    // assumption.
-    bool NonNeg = ICond->isUnsigned();
-    const SCEV *LeftOperand = SE.getSCEVAtScope(ICond->getOperand(0), L),
-               *RightOperand = SE.getSCEVAtScope(ICond->getOperand(1), L);
-
-    LeftOperand = tryForwardThroughPHI(LeftOperand, R, SE, LI, DT);
-    RightOperand = tryForwardThroughPHI(RightOperand, R, SE, LI, DT);
-
-    switch (ICond->getPredicate()) {
-    case ICmpInst::ICMP_ULT:
-      ConsequenceCondSet =
-          buildUnsignedConditionSets(S, BB, Condition, Domain, LeftOperand,
-                                     RightOperand, InvalidDomainMap, true);
-      break;
-    case ICmpInst::ICMP_ULE:
-      ConsequenceCondSet =
-          buildUnsignedConditionSets(S, BB, Condition, Domain, LeftOperand,
-                                     RightOperand, InvalidDomainMap, false);
-      break;
-    case ICmpInst::ICMP_UGT:
-      ConsequenceCondSet =
-          buildUnsignedConditionSets(S, BB, Condition, Domain, RightOperand,
-                                     LeftOperand, InvalidDomainMap, true);
-      break;
-    case ICmpInst::ICMP_UGE:
-      ConsequenceCondSet =
-          buildUnsignedConditionSets(S, BB, Condition, Domain, RightOperand,
-                                     LeftOperand, InvalidDomainMap, false);
-      break;
-    default:
-      LHS = getPwAff(S, BB, InvalidDomainMap, LeftOperand, NonNeg);
-      RHS = getPwAff(S, BB, InvalidDomainMap, RightOperand, NonNeg);
-      ConsequenceCondSet = buildConditionSet(ICond->getPredicate(),
-                                             isl::manage(LHS), isl::manage(RHS))
-                               .release();
-      break;
-    }
-  }
-
-  // If no terminator was given we are only looking for parameter constraints
-  // under which @p Condition is true/false.
-  if (!TI)
-    ConsequenceCondSet = isl_set_params(ConsequenceCondSet);
-  assert(ConsequenceCondSet);
-  ConsequenceCondSet = isl_set_coalesce(
-      isl_set_intersect(ConsequenceCondSet, isl_set_copy(Domain)));
-
-  isl_set *AlternativeCondSet = nullptr;
-  bool TooComplex =
-      isl_set_n_basic_set(ConsequenceCondSet) >= MaxDisjunctsInDomain;
-
-  if (!TooComplex) {
-    AlternativeCondSet = isl_set_subtract(isl_set_copy(Domain),
-                                          isl_set_copy(ConsequenceCondSet));
-    TooComplex =
-        isl_set_n_basic_set(AlternativeCondSet) >= MaxDisjunctsInDomain;
-  }
-
-  if (TooComplex) {
-    S.invalidate(COMPLEXITY, TI ? TI->getDebugLoc() : DebugLoc(),
-                 TI ? TI->getParent() : nullptr /* BasicBlock */);
-    isl_set_free(AlternativeCondSet);
-    isl_set_free(ConsequenceCondSet);
-    return false;
-  }
-
-  ConditionSets.push_back(ConsequenceCondSet);
-  ConditionSets.push_back(isl_set_coalesce(AlternativeCondSet));
-
-  return true;
-}
-
-bool polly::buildConditionSets(
-    Scop &S, BasicBlock *BB, Instruction *TI, Loop *L,
-    __isl_keep isl_set *Domain,
-    DenseMap<BasicBlock *, isl::set> &InvalidDomainMap,
-    SmallVectorImpl<__isl_give isl_set *> &ConditionSets) {
-  if (SwitchInst *SI = dyn_cast<SwitchInst>(TI))
-    return buildConditionSets(S, BB, SI, L, Domain, InvalidDomainMap,
-                              ConditionSets);
-
-  assert(isa<BranchInst>(TI) && "Terminator was neither branch nor switch.");
-
-  if (TI->getNumSuccessors() == 1) {
-    ConditionSets.push_back(isl_set_copy(Domain));
-    return true;
-  }
-
-  Value *Condition = getConditionFromTerminator(TI);
-  assert(Condition && "No condition for Terminator");
-
-  return buildConditionSets(S, BB, Condition, TI, L, Domain, InvalidDomainMap,
-                            ConditionSets);
-}
-
 ScopStmt::ScopStmt(Scop &parent, Region &R, StringRef Name,
                    Loop *SurroundingLoop,
                    std::vector<Instruction *> EntryBlockInstructions)
     : Parent(parent), InvalidDomain(nullptr), Domain(nullptr), R(&R),
       Build(nullptr), BaseName(Name), SurroundingLoop(SurroundingLoop),
       Instructions(EntryBlockInstructions) {}
 
 ScopStmt::ScopStmt(Scop &parent, BasicBlock &bb, StringRef Name,
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());
 }
 
-/// 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>();
-}
-
-/// Return the @p idx'th block that is executed after @p RN.
-static inline BasicBlock *
-getRegionNodeSuccessor(RegionNode *RN, Instruction *TI, unsigned idx) {
-  if (RN->isSubRegion()) {
-    assert(idx == 0);
-    return RN->getNodeAs<Region>()->getExit();
-  }
-  return TI->getSuccessor(idx);
-}
-
-static bool containsErrorBlock(RegionNode *RN, const Region &R, LoopInfo &LI,
-                               const DominatorTree &DT) {
-  if (!RN->isSubRegion())
-    return isErrorBlock(*RN->getNodeAs<BasicBlock>(), R, LI, DT);
-  for (BasicBlock *BB : RN->getNodeAs<Region>()->blocks())
-    if (isErrorBlock(*BB, R, LI, DT))
-      return true;
-  return false;
-}
-
-///}
-
 isl::set Scop::getDomainConditions(const ScopStmt *Stmt) const {
   return getDomainConditions(Stmt->getEntryBlock());
 }
 
 isl::set Scop::getDomainConditions(BasicBlock *BB) const {
   auto DIt = DomainMap.find(BB);
   if (DIt != DomainMap.end())
     return DIt->getSecond();
 
   auto &RI = *R.getRegionInfo();
   auto *BBR = RI.getRegionFor(BB);
   while (BBR->getEntry() == BB)
     BBR = BBR->getParent();
   return getDomainConditions(BBR->getEntry());
 }
 
-bool Scop::buildDomains(Region *R, DominatorTree &DT, LoopInfo &LI,
-                        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().get(), 0, LD + 1));
-
-  while (LD-- >= 0) {
-    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))
-    return false;
-
-  if (!propagateDomainConstraints(R, DT, LI, 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))
-    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.
-///
-/// This function assumes @p NewL and @p OldL are equal or there is a CFG
-/// edge from @p OldL to @p NewL.
-static isl::set adjustDomainDimensions(Scop &S, isl::set Dom, Loop *OldL,
-                                       Loop *NewL) {
-  // If the loops are the same there is nothing to do.
-  if (NewL == OldL)
-    return Dom;
-
-  int OldDepth = S.getRelativeLoopDepth(OldL);
-  int NewDepth = S.getRelativeLoopDepth(NewL);
-  // If both loops are non-affine loops there is nothing to do.
-  if (OldDepth == -1 && NewDepth == -1)
-    return Dom;
-
-  // Distinguish three cases:
-  //   1) The depth is the same but the loops are not.
-  //      => One loop was left one was entered.
-  //   2) The depth increased from OldL to NewL.
-  //      => One loop was entered, none was left.
-  //   3) The depth decreased from OldL to NewL.
-  //      => Loops were left were difference of the depths defines how many.
-  if (OldDepth == NewDepth) {
-    assert(OldL->getParentLoop() == NewL->getParentLoop());
-    Dom = Dom.project_out(isl::dim::set, NewDepth, 1);
-    Dom = Dom.add_dims(isl::dim::set, 1);
-  } else if (OldDepth < NewDepth) {
-    assert(OldDepth + 1 == NewDepth);
-    auto &R = S.getRegion();
-    (void)R;
-    assert(NewL->getParentLoop() == OldL ||
-           ((!OldL || !R.contains(OldL)) && R.contains(NewL)));
-    Dom = Dom.add_dims(isl::dim::set, 1);
-  } else {
-    assert(OldDepth > NewDepth);
-    int Diff = OldDepth - NewDepth;
-    int NumDim = Dom.n_dim();
-    assert(NumDim >= Diff);
-    Dom = Dom.project_out(isl::dim::set, NumDim - Diff, Diff);
-  }
-
-  return Dom;
-}
-
-bool Scop::propagateInvalidStmtDomains(
-    Region *R, DominatorTree &DT, LoopInfo &LI,
-    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.
-    if (RN->isSubRegion()) {
-      Region *SubRegion = RN->getNodeAs<Region>();
-      if (!isNonAffineSubRegion(SubRegion)) {
-        propagateInvalidStmtDomains(SubRegion, DT, LI, InvalidDomainMap);
-        continue;
-      }
-    }
-
-    bool ContainsErrorBlock = containsErrorBlock(RN, getRegion(), LI, DT);
-    BasicBlock *BB = getRegionNodeBasicBlock(RN);
-    isl::set &Domain = DomainMap[BB];
-    assert(Domain && "Cannot propagate a nullptr");
-
-    isl::set InvalidDomain = InvalidDomainMap[BB];
-
-    bool IsInvalidBlock = ContainsErrorBlock || Domain.is_subset(InvalidDomain);
-
-    if (!IsInvalidBlock) {
-      InvalidDomain = InvalidDomain.intersect(Domain);
-    } else {
-      InvalidDomain = Domain;
-      isl::set DomPar = Domain.params();
-      recordAssumption(ERRORBLOCK, DomPar, BB->getTerminator()->getDebugLoc(),
-                       AS_RESTRICTION);
-      Domain = isl::set::empty(Domain.get_space());
-    }
-
-    if (InvalidDomain.is_empty()) {
-      InvalidDomainMap[BB] = InvalidDomain;
-      continue;
-    }
-
-    auto *BBLoop = getRegionNodeLoop(RN, LI);
-    auto *TI = BB->getTerminator();
-    unsigned NumSuccs = RN->isSubRegion() ? 1 : TI->getNumSuccessors();
-    for (unsigned u = 0; u < NumSuccs; u++) {
-      auto *SuccBB = getRegionNodeSuccessor(RN, TI, u);
-
-      // Skip successors outside the SCoP.
-      if (!contains(SuccBB))
-        continue;
-
-      // Skip backedges.
-      if (DT.dominates(SuccBB, BB))
-        continue;
-
-      Loop *SuccBBLoop = getFirstNonBoxedLoopFor(SuccBB, LI, getBoxedLoops());
-
-      auto AdjustedInvalidDomain =
-          adjustDomainDimensions(*this, InvalidDomain, BBLoop, SuccBBLoop);
-
-      isl::set SuccInvalidDomain = InvalidDomainMap[SuccBB];
-      SuccInvalidDomain = SuccInvalidDomain.unite(AdjustedInvalidDomain);
-      SuccInvalidDomain = SuccInvalidDomain.coalesce();
-      unsigned NumConjucts = SuccInvalidDomain.n_basic_set();
-
-      InvalidDomainMap[SuccBB] = SuccInvalidDomain;
-
-      // Check if the maximal number of domain disjunctions was reached.
-      // In case this happens we will bail.
-      if (NumConjucts < MaxDisjunctsInDomain)
-        continue;
-
-      InvalidDomainMap.erase(BB);
-      invalidate(COMPLEXITY, TI->getDebugLoc(), TI->getParent());
-      return false;
-    }
-
-    InvalidDomainMap[BB] = InvalidDomain;
-  }
-
-  return true;
-}
-
-void Scop::propagateDomainConstraintsToRegionExit(
-    BasicBlock *BB, Loop *BBLoop,
-    SmallPtrSetImpl<BasicBlock *> &FinishedExitBlocks, LoopInfo &LI,
-    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.
-  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.
-  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.
-  isl::set AdjustedDomain =
-      adjustDomainDimensions(*this, Domain, 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> &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.
-
-  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.
-    if (RN->isSubRegion()) {
-      Region *SubRegion = RN->getNodeAs<Region>();
-      if (!isNonAffineSubRegion(SubRegion)) {
-        if (!buildDomainsWithBranchConstraints(SubRegion, DT, LI,
-                                               InvalidDomainMap))
-          return false;
-        continue;
-      }
-    }
-
-    if (containsErrorBlock(RN, getRegion(), LI, DT))
-      HasErrorBlock = true;
-
-    BasicBlock *BB = getRegionNodeBasicBlock(RN);
-    Instruction *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.
-    propagateDomainConstraintsToRegionExit(BB, BBLoop, FinishedExitBlocks, LI,
-                                           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.
-    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.
-    SmallVector<isl_set *, 8> ConditionSets;
-    if (RN->isSubRegion())
-      ConditionSets.push_back(Domain.copy());
-    else if (!buildConditionSets(*this, BB, TI, BBLoop, Domain.get(),
-                                 InvalidDomainMap, 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.
-    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 (FinishedExitBlocks.count(SuccBB))
-        continue;
-
-      // Skip back edges.
-      if (DT.dominates(SuccBB, BB))
-        continue;
-
-      Loop *SuccBBLoop = getFirstNonBoxedLoopFor(SuccBB, LI, getBoxedLoops());
-
-      CondSet = adjustDomainDimensions(*this, CondSet, 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.
-      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;
-      }
-
-      SuccDomain = SuccDomain.detect_equalities();
-
-      // Check if the maximal number of domain disjunctions was reached.
-      // In case this happens we will clean up and bail.
-      if (SuccDomain.n_basic_set() < MaxDisjunctsInDomain)
-        continue;
-
-      invalidate(COMPLEXITY, DebugLoc());
-      while (++u < ConditionSets.size())
-        isl_set_free(ConditionSets[u]);
-      return false;
-    }
-  }
-
-  return true;
-}
-
-isl::set Scop::getPredecessorDomainConstraints(BasicBlock *BB, isl::set Domain,
-                                               DominatorTree &DT,
-                                               LoopInfo &LI) {
-  // If @p BB is the ScopEntry we are done
-  if (R.getEntry() == BB)
-    return isl::set::universe(Domain.get_space());
-
-  // 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.
-  isl::set PredDom = isl::set::empty(Domain.get_space());
-
-  // 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.
-    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.
-    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 (PredR->getExit() == BB) {
-      PredBB = PredR->getEntry();
-      PropagatedRegions.insert(PredR);
-    }
-
-    isl::set PredBBDom = getDomainConditions(PredBB);
-    Loop *PredBBLoop = getFirstNonBoxedLoopFor(PredBB, LI, getBoxedLoops());
-    PredBBDom = adjustDomainDimensions(*this, PredBBDom, PredBBLoop, BBLoop);
-    PredDom = PredDom.unite(PredBBDom);
-  }
-
-  return PredDom;
-}
-
-bool Scop::propagateDomainConstraints(
-    Region *R, DominatorTree &DT, LoopInfo &LI,
-    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.
-
-  ReversePostOrderTraversal<Region *> RTraversal(R);
-  for (auto *RN : RTraversal) {
-    // 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))
-          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 = getPredecessorDomainConstraints(BB, Domain, DT, LI);
-    Domain = Domain.intersect(PredDom).coalesce();
-    Domain = Domain.align_params(getParamSpace());
-
-    Loop *BBLoop = getRegionNodeLoop(RN, LI);
-    if (BBLoop && BBLoop->getHeader() == BB && contains(BBLoop))
-      if (!addLoopBoundsToHeaderDomain(BBLoop, LI, InvalidDomainMap))
-        return false;
-  }
-
-  return true;
-}
-
-/// Create a map to map from a given iteration to a subsequent iteration.
-///
-/// This map maps from SetSpace -> SetSpace where the dimensions @p Dim
-/// is incremented by one and all other dimensions are equal, e.g.,
-///             [i0, i1, i2, i3] -> [i0, i1, i2 + 1, i3]
-///
-/// if @p Dim is 2 and @p SetSpace has 4 dimensions.
-static isl::map createNextIterationMap(isl::space SetSpace, unsigned Dim) {
-  isl::space MapSpace = SetSpace.map_from_set();
-  isl::map NextIterationMap = isl::map::universe(MapSpace);
-  for (unsigned u = 0; u < NextIterationMap.dim(isl::dim::in); u++)
-    if (u != Dim)
-      NextIterationMap =
-          NextIterationMap.equate(isl::dim::in, u, isl::dim::out, u);
-  isl::constraint C =
-      isl::constraint::alloc_equality(isl::local_space(MapSpace));
-  C = C.set_constant_si(1);
-  C = C.set_coefficient_si(isl::dim::in, Dim, 1);
-  C = C.set_coefficient_si(isl::dim::out, Dim, -1);
-  NextIterationMap = NextIterationMap.add_constraint(C);
-  return NextIterationMap;
-}
-
-bool Scop::addLoopBoundsToHeaderDomain(
-    Loop *L, LoopInfo &LI, 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 =
-      createNextIterationMap(HeaderBBDom.get_space(), LoopDepth);
-
-  isl::set UnionBackedgeCondition = HeaderBBDom.empty(HeaderBBDom.get_space());
-
-  SmallVector<BasicBlock *, 4> LatchBlocks;
-  L->getLoopLatches(LatchBlocks);
-
-  for (BasicBlock *LatchBB : LatchBlocks) {
-    // If the latch is only reachable via error statements we skip it.
-    isl::set LatchBBDom = DomainMap.lookup(LatchBB);
-    if (!LatchBBDom)
-      continue;
-
-    isl::set BackedgeCondition = nullptr;
-
-    Instruction *TI = LatchBB->getTerminator();
-    BranchInst *BI = dyn_cast<BranchInst>(TI);
-    assert(BI && "Only branch instructions allowed in loop latches");
-
-    if (BI->isUnconditional())
-      BackedgeCondition = LatchBBDom;
-    else {
-      SmallVector<isl_set *, 8> ConditionSets;
-      int idx = BI->getSuccessor(0) != HeaderBB;
-      if (!buildConditionSets(*this, LatchBB, TI, L, LatchBBDom.get(),
-                              InvalidDomainMap, ConditionSets))
-        return false;
-
-      // Free the non back edge condition set as we do not need it.
-      isl_set_free(ConditionSets[1 - idx]);
-
-      BackedgeCondition = isl::manage(ConditionSets[idx]);
-    }
-
-    int LatchLoopDepth = getRelativeLoopDepth(LI.getLoopFor(LatchBB));
-    assert(LatchLoopDepth >= LoopDepth);
-    BackedgeCondition = BackedgeCondition.project_out(
-        isl::dim::set, LoopDepth + 1, LatchLoopDepth - LoopDepth);
-    UnionBackedgeCondition = UnionBackedgeCondition.unite(BackedgeCondition);
-  }
-
-  isl::map ForwardMap = ForwardMap.lex_le(HeaderBBDom.get_space());
-  for (int i = 0; i < LoopDepth; i++)
-    ForwardMap = ForwardMap.equate(isl::dim::in, i, isl::dim::out, i);
-
-  isl::set UnionBackedgeConditionComplement =
-      UnionBackedgeCondition.complement();
-  UnionBackedgeConditionComplement =
-      UnionBackedgeConditionComplement.lower_bound_si(isl::dim::set, LoopDepth,
-                                                      0);
-  UnionBackedgeConditionComplement =
-      UnionBackedgeConditionComplement.apply(ForwardMap);
-  HeaderBBDom = HeaderBBDom.subtract(UnionBackedgeConditionComplement);
-  HeaderBBDom = HeaderBBDom.apply(NextIterationMap);
-
-  auto Parts = partitionSetParts(HeaderBBDom, LoopDepth);
-  HeaderBBDom = 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.
-  if (Affinator.hasNSWAddRecForLoop(L))
-    return true;
-
-  isl::set UnboundedCtx = Parts.first.params();
-  recordAssumption(INFINITELOOP, UnboundedCtx,
-                   HeaderBB->getTerminator()->getDebugLoc(), AS_RESTRICTION);
-  return true;
-}
-
 int Scop::NextScopID = 0;
 
 std::string Scop::CurrentFunc;
 
 int Scop::getNextID(std::string ParentFunc) {
   if (ParentFunc != CurrentFunc) {
     CurrentFunc = ParentFunc;
     NextScopID = 0;