Traverse the SCoP to compute non-loop-carried domain conditions

  In order to compute domain conditions for conditionals we will now
  traverse the region in the ScopInfo once and build the domains for
  each block in the region. The SCoP statements can then use these
  constraints when they build their domain.

  The reason behind this change is twofold:
    1) This removes a big chunk of preprocessing logic from the
       TempScopInfo, namely the Conditionals we used to build there.
       Additionally to moving this logic it is also simplified. Instead
       of walking the dominance tree up for each basic block in the
       region (as we did before), we now traverse the region only
       once in order to collect the domain conditions.
    2) This is the first step towards the isl based domain creation.
       The second step will traverse the region similar to this step,
       however it will propagate back edge conditions. Once both are in
       place this conditional handling will allow multiple exit loops
       additional logic.

Reviewers: grosser

Differential Revision: http://reviews.llvm.org/D12428

llvm-svn: 246398

42 files changed, 946 insertions, 348 deletions

diff --git a/polly/include/polly/ScopInfo.h b/polly/include/polly/ScopInfo.h
index 540136dd82d..4550ee8bb90 100644
--- a/polly/include/polly/ScopInfo.h
+++ b/polly/include/polly/ScopInfo.h
@@ -554,7 +554,6 @@ private:
 
   /// Build the statement.
   //@{
-  __isl_give isl_set *buildConditionSet(const Comparison &Cmp);
   void addConditionsToDomain(TempScop &tempScop, const Region &CurRegion);
   void addLoopBoundsToDomain(TempScop &tempScop);
   void addLoopTripCountToDomain(const Loop *L);
@@ -788,6 +787,7 @@ private:
   Scop(const Scop &) = delete;
   const Scop &operator=(const Scop &) = delete;
 
+  DominatorTree &DT;
   ScalarEvolution *SE;
 
   /// The underlying Region.
@@ -817,6 +817,9 @@ private:
   /// @brief A map from basic blocks to SCoP statements.
   DenseMap<BasicBlock *, ScopStmt *> StmtMap;
 
+  /// @brief A map from basic blocks to their domains.
+  DenseMap<BasicBlock *, isl_set *> DomainMap;
+
   /// Constraints on parameters.
   isl_set *Context;
 
@@ -893,7 +896,8 @@ private:
   MinMaxVectorPairVectorTy MinMaxAliasGroups;
 
   /// @brief Scop constructor; used by static createFromTempScop
-  Scop(Region &R, ScalarEvolution &SE, isl_ctx *ctx, unsigned MaxLoopDepth);
+  Scop(Region &R, ScalarEvolution &SE, DominatorTree &DT, isl_ctx *ctx,
+       unsigned MaxLoopDepth);
 
   /// @brief Initialize this ScopInfo using a TempScop object.
   void initFromTempScop(TempScop &TempScop, LoopInfo &LI, ScopDetection &SD,
@@ -903,7 +907,26 @@ private:
   /// region and parameters used in this region.
   static Scop *createFromTempScop(TempScop &TempScop, LoopInfo &LI,
                                   ScalarEvolution &SE, ScopDetection &SD,
-                                  AliasAnalysis &AA, isl_ctx *ctx);
+                                  AliasAnalysis &AA, DominatorTree &DT,
+                                  isl_ctx *ctx);
+
+  /// @brief Compute the branching constraints for each basic block in @p R.
+  ///
+  /// @param R  The region we currently build branching conditions for.
+  /// @param LI The LoopInfo analysis to obtain the number of iterators.
+  /// @param SD The ScopDetection analysis to identify non-affine sub-regions.
+  /// @param DT The dominator tree of the current function.
+  void buildDomainsWithBranchConstraints(Region *R, LoopInfo &LI,
+                                         ScopDetection &SD, DominatorTree &DT);
+
+  /// @brief Compute the domain for each basic block in @p R.
+  ///
+  /// @param R  The region we currently traverse.
+  /// @param LI The LoopInfo analysis to argue about the number of iterators.
+  /// @param SD The ScopDetection analysis to identify non-affine sub-regions.
+  /// @param DT The dominator tree of the current function.
+  void buildDomains(Region *R, LoopInfo &LI, ScopDetection &SD,
+                    DominatorTree &DT);
 
   /// @brief Check if a basic block is trivial.
   ///
@@ -1187,6 +1210,11 @@ public:
   __isl_give isl_pw_aff *getPwAff(const SCEV *E,
                                   __isl_keep isl_set *Domain = nullptr);
 
+  /// @brief Return the non-loop carried conditions on the domain of @p Stmt.
+  ///
+  /// @param Stmt The statement for which the conditions should be returned.
+  __isl_give isl_set *getDomainConditions(ScopStmt *Stmt);
+
   /// @brief Get a union set containing the iteration domains of all statements.
   __isl_give isl_union_set *getDomains() const;
 
@@ -1224,7 +1252,12 @@ public:
   bool restrictDomains(__isl_take isl_union_set *Domain);
 
   /// @brief Get the depth of a loop relative to the outermost loop in the Scop.
-  unsigned getRelativeLoopDepth(const Loop *L) const;
+  ///
+  /// This will return
+  ///    0 if @p L is an outermost loop in the SCoP
+  ///   >0 for other loops in the SCoP
+  ///   -1 if @p L is nullptr or there is no outermost loop in the SCoP
+  int getRelativeLoopDepth(const Loop *L) const;
 };
 
 /// @brief Print Scop scop to raw_ostream O.
diff --git a/polly/include/polly/TempScopInfo.h b/polly/include/polly/TempScopInfo.h
index d12cc5b5dd5..4c839c4eb23 100644
--- a/polly/include/polly/TempScopInfo.h
+++ b/polly/include/polly/TempScopInfo.h
@@ -118,9 +118,6 @@ public:
 };
 
 //===---------------------------------------------------------------------===//
-/// Types
-// The condition of a Basicblock, combine brcond with "And" operator.
-typedef SmallVector<Comparison, 4> BBCond;
 
 /// Maps from a loop to the affine function expressing its backedge taken count.
 /// The backedge taken count already enough to express iteration domain as we
@@ -130,9 +127,6 @@ typedef SmallVector<Comparison, 4> BBCond;
 /// through the loop.
 typedef std::map<const Loop *, const SCEV *> LoopBoundMapType;
 
-/// Mapping BBs to its condition constrains
-typedef std::map<const BasicBlock *, BBCond> BBCondMapType;
-
 typedef std::vector<std::pair<IRAccess, Instruction *>> AccFuncSetType;
 typedef std::map<const BasicBlock *, AccFuncSetType> AccFuncMapType;
 
@@ -145,17 +139,13 @@ class TempScop {
   // The Region.
   Region &R;
 
-  // Remember the bounds of loops, to help us build iteration domain of BBs.
-  const BBCondMapType &BBConds;
-
   // Access function of bbs.
   AccFuncMapType &AccFuncMap;
 
   friend class TempScopInfo;
 
-  explicit TempScop(Region &r, BBCondMapType &BBCmps,
-                    AccFuncMapType &accFuncMap)
-      : R(r), BBConds(BBCmps), AccFuncMap(accFuncMap) {}
+  explicit TempScop(Region &r, AccFuncMapType &accFuncMap)
+      : R(r), AccFuncMap(accFuncMap) {}
 
 public:
   ~TempScop();
@@ -165,17 +155,6 @@ public:
   /// @return The maximum Region contained by this Scop.
   Region &getMaxRegion() const { return R; }
 
-  /// @brief Get the condition from entry block of the Scop to a BasicBlock
-  ///
-  /// @param BB The BasicBlock
-  ///
-  /// @return The condition from entry block of the Scop to a BB
-  ///
-  const BBCond *getBBCond(const BasicBlock *BB) const {
-    BBCondMapType::const_iterator at = BBConds.find(BB);
-    return at != BBConds.end() ? &(at->second) : 0;
-  }
-
   /// @brief Get all access functions in a BasicBlock
   ///
   /// @param  BB The BasicBlock that containing the access functions.
@@ -227,16 +206,9 @@ class TempScopInfo : public RegionPass {
   // Valid Regions for Scop
   ScopDetection *SD;
 
-  // For condition extraction support.
-  DominatorTree *DT;
-  PostDominatorTree *PDT;
-
   // Target data for element size computing.
   const DataLayout *TD;
 
-  // And also Remember the constrains for BBs
-  BBCondMapType BBConds;
-
   // Access function of statements (currently BasicBlocks) .
   AccFuncMapType AccFuncMap;
 
@@ -250,15 +222,6 @@ class TempScopInfo : public RegionPass {
   // Clear the context.
   void clear();
 
-  /// @brief Build condition constrains to BBs in a valid Scop.
-  ///
-  /// @param BB The BasicBlock to build condition constrains
-  /// @param R  The region for the current TempScop.
-  void buildCondition(BasicBlock *BB, Region &R);
-
-  // Build the affine function of the given condition
-  Comparison buildAffineCondition(Value &V, bool inverted);
-
   // Build the temprory information of Region R, where R must be a valid part
   // of Scop.
   TempScop *buildTempScop(Region &R);
diff --git a/polly/lib/Analysis/ScopInfo.cpp b/polly/lib/Analysis/ScopInfo.cpp
index 206e42b4576..b209c3576ef 100644
--- a/polly/lib/Analysis/ScopInfo.cpp
+++ b/polly/lib/Analysis/ScopInfo.cpp
@@ -29,6 +29,7 @@
 #include "llvm/ADT/Statistic.h"
 #include "llvm/ADT/STLExtras.h"
 #include "llvm/ADT/StringExtras.h"
+#include "llvm/ADT/PostOrderIterator.h"
 #include "llvm/Analysis/AliasAnalysis.h"
 #include "llvm/Analysis/LoopInfo.h"
 #include "llvm/Analysis/RegionIterator.h"
@@ -739,9 +740,85 @@ void ScopStmt::realignParams() {
   Domain = isl_set_align_params(Domain, Parent.getParamSpace());
 }
 
+static __isl_give isl_set *buildConditionSet(ICmpInst::Predicate Pred,
+                                             isl_pw_aff *L, isl_pw_aff *R) {
+  switch (Pred) {
+  case ICmpInst::ICMP_EQ:
+    return isl_pw_aff_eq_set(L, R);
+  case ICmpInst::ICMP_NE:
+    return isl_pw_aff_ne_set(L, R);
+  case ICmpInst::ICMP_SLT:
+    return isl_pw_aff_lt_set(L, R);
+  case ICmpInst::ICMP_SLE:
+    return isl_pw_aff_le_set(L, R);
+  case ICmpInst::ICMP_SGT:
+    return isl_pw_aff_gt_set(L, R);
+  case ICmpInst::ICMP_SGE:
+    return isl_pw_aff_ge_set(L, R);
+  case ICmpInst::ICMP_ULT:
+    return isl_pw_aff_lt_set(L, R);
+  case ICmpInst::ICMP_UGT:
+    return isl_pw_aff_gt_set(L, R);
+  case ICmpInst::ICMP_ULE:
+    return isl_pw_aff_le_set(L, R);
+  case ICmpInst::ICMP_UGE:
+    return isl_pw_aff_ge_set(L, R);
+  default:
+    llvm_unreachable("Non integer predicate not supported");
+  }
+}
+
+/// @brief Build the conditions sets for the branch @p BI in the @p Domain.
+///
+/// This will fill @p ConditionSets with the conditions under which control
+/// will be moved from @p BI to its successors. Hence, @p ConditionSets will
+/// have as many elements as @p BI has successors.
+static void
+buildConditionSets(Scop &S, BranchInst *BI, Loop *L, __isl_keep isl_set *Domain,
+                   SmallVectorImpl<__isl_give isl_set *> &ConditionSets) {
+
+  if (BI->isUnconditional()) {
+    ConditionSets.push_back(isl_set_copy(Domain));
+    return;
+  }
+
+  Value *Condition = BI->getCondition();
+
+  isl_set *ConsequenceCondSet = nullptr;
+  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 {
+    auto *ICond = dyn_cast<ICmpInst>(Condition);
+    assert(ICond &&
+           "Condition of exiting branch was neither constant nor ICmp!");
+
+    ScalarEvolution &SE = *S.getSE();
+    isl_pw_aff *LHS, *RHS;
+    LHS = S.getPwAff(SE.getSCEVAtScope(ICond->getOperand(0), L), Domain);
+    RHS = S.getPwAff(SE.getSCEVAtScope(ICond->getOperand(1), L), Domain);
+    ConsequenceCondSet = buildConditionSet(ICond->getPredicate(), LHS, RHS);
+  }
+
+  assert(ConsequenceCondSet);
+  isl_set *AlternativeCondSet =
+      isl_set_complement(isl_set_copy(ConsequenceCondSet));
+
+  ConditionSets.push_back(isl_set_coalesce(
+      isl_set_intersect(ConsequenceCondSet, isl_set_copy(Domain))));
+  ConditionSets.push_back(isl_set_coalesce(
+      isl_set_intersect(AlternativeCondSet, isl_set_copy(Domain))));
+}
+
 void ScopStmt::addLoopTripCountToDomain(const Loop *L) {
 
-  unsigned loopDimension = getParent()->getRelativeLoopDepth(L);
+  int RelativeLoopDimension = getParent()->getRelativeLoopDepth(L);
+  assert(RelativeLoopDimension >= 0 &&
+         "Expected relative loop depth of L to be non-negative");
+  unsigned loopDimension = RelativeLoopDimension;
+
   ScalarEvolution *SE = getParent()->getSE();
   isl_space *DomSpace = isl_set_get_space(Domain);
 
@@ -781,7 +858,10 @@ void ScopStmt::addLoopTripCountToDomain(const Loop *L) {
     Pred = ICmpInst::getInversePredicate(Pred);
   Comparison Comp(LHS, RHS, Pred);
 
-  isl_set *CondSet = buildConditionSet(Comp);
+  isl_pw_aff *LPWA = getPwAff(Comp.getLHS());
+  isl_pw_aff *RPWA = getPwAff(Comp.getRHS());
+
+  isl_set *CondSet = buildConditionSet(Comp.getPred(), LPWA, RPWA);
   isl_map *ForwardMap = isl_map_lex_le(isl_space_copy(DomSpace));
   for (unsigned i = 0; i < isl_set_n_dim(Domain); i++)
     if (i != loopDimension)
@@ -798,36 +878,6 @@ void ScopStmt::addLoopTripCountToDomain(const Loop *L) {
   isl_space_free(DomSpace);
 }
 
-__isl_give isl_set *ScopStmt::buildConditionSet(const Comparison &Comp) {
-  isl_pw_aff *L = getPwAff(Comp.getLHS());
-  isl_pw_aff *R = getPwAff(Comp.getRHS());
-
-  switch (Comp.getPred()) {
-  case ICmpInst::ICMP_EQ:
-    return isl_pw_aff_eq_set(L, R);
-  case ICmpInst::ICMP_NE:
-    return isl_pw_aff_ne_set(L, R);
-  case ICmpInst::ICMP_SLT:
-    return isl_pw_aff_lt_set(L, R);
-  case ICmpInst::ICMP_SLE:
-    return isl_pw_aff_le_set(L, R);
-  case ICmpInst::ICMP_SGT:
-    return isl_pw_aff_gt_set(L, R);
-  case ICmpInst::ICMP_SGE:
-    return isl_pw_aff_ge_set(L, R);
-  case ICmpInst::ICMP_ULT:
-    return isl_pw_aff_lt_set(L, R);
-  case ICmpInst::ICMP_UGT:
-    return isl_pw_aff_gt_set(L, R);
-  case ICmpInst::ICMP_ULE:
-    return isl_pw_aff_le_set(L, R);
-  case ICmpInst::ICMP_UGE:
-    return isl_pw_aff_ge_set(L, R);
-  default:
-    llvm_unreachable("Non integer predicate not supported");
-  }
-}
-
 void ScopStmt::addLoopBoundsToDomain(TempScop &tempScop) {
   isl_space *Space;
   isl_local_space *LocalSpace;
@@ -862,25 +912,6 @@ void ScopStmt::addLoopBoundsToDomain(TempScop &tempScop) {
   isl_local_space_free(LocalSpace);
 }
 
-void ScopStmt::addConditionsToDomain(TempScop &tempScop,
-                                     const Region &CurRegion) {
-  const Region *TopRegion = tempScop.getMaxRegion().getParent(),
-               *CurrentRegion = &CurRegion;
-  const BasicBlock *BranchingBB = BB ? BB : R->getEntry();
-
-  do {
-    if (BranchingBB != CurrentRegion->getEntry()) {
-      if (const BBCond *Condition = tempScop.getBBCond(BranchingBB))
-        for (const auto &C : *Condition) {
-          isl_set *ConditionSet = buildConditionSet(C);
-          Domain = isl_set_intersect(Domain, ConditionSet);
-        }
-    }
-    BranchingBB = CurrentRegion->getEntry();
-    CurrentRegion = CurrentRegion->getParent();
-  } while (TopRegion != CurrentRegion);
-}
-
 void ScopStmt::buildDomain(TempScop &tempScop, const Region &CurRegion) {
   isl_space *Space;
   isl_id *Id;
@@ -891,7 +922,8 @@ void ScopStmt::buildDomain(TempScop &tempScop, const Region &CurRegion) {
 
   Domain = isl_set_universe(Space);
   addLoopBoundsToDomain(tempScop);
-  addConditionsToDomain(tempScop, CurRegion);
+  Domain = isl_set_intersect(Domain, getParent()->getDomainConditions(this));
+  Domain = isl_set_coalesce(Domain);
   Domain = isl_set_set_tuple_id(Domain, Id);
 }
 
@@ -1419,6 +1451,151 @@ static bool calculateMinMaxAccess(__isl_take isl_union_map *Accesses,
   return Valid;
 }
 
+/// @brief Helper to treat non-affine regions and basic blocks the same.
+///
+///{
+
+/// @brief 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>();
+}
+
+/// @brief Return the @p idx'th block that is executed after @p RN.
+static inline BasicBlock *getRegionNodeSuccessor(RegionNode *RN, BranchInst *BI,
+                                                 unsigned idx) {
+  if (RN->isSubRegion()) {
+    assert(idx == 0);
+    return RN->getNodeAs<Region>()->getExit();
+  }
+  return BI->getSuccessor(idx);
+}
+
+/// @brief Return the smallest loop surrounding @p RN.
+static inline Loop *getRegionNodeLoop(RegionNode *RN, LoopInfo &LI) {
+  if (!RN->isSubRegion())
+    return LI.getLoopFor(RN->getNodeAs<BasicBlock>());
+
+  Region *NonAffineSubRegion = RN->getNodeAs<Region>();
+  Loop *L = LI.getLoopFor(NonAffineSubRegion->getEntry());
+  while (L && NonAffineSubRegion->contains(L))
+    L = L->getParentLoop();
+  return L;
+}
+
+///}
+
+isl_set *Scop::getDomainConditions(ScopStmt *Stmt) {
+  BasicBlock *BB = Stmt->isBlockStmt() ? Stmt->getBasicBlock()
+                                       : Stmt->getRegion()->getEntry();
+  isl_set *Domain = isl_set_copy(DomainMap[BB]);
+
+  unsigned NumDims = Stmt->getNumIterators();
+  Domain = isl_set_remove_dims(Domain, isl_dim_set, NumDims,
+                               getMaxLoopDepth() - NumDims);
+  return Domain;
+}
+
+void Scop::buildDomains(Region *R, LoopInfo &LI, ScopDetection &SD,
+                        DominatorTree &DT) {
+
+  auto *S = isl_set_universe(isl_space_set_alloc(getIslCtx(), 0, MaxLoopDepth));
+  DomainMap[R->getEntry()] = S;
+
+  buildDomainsWithBranchConstraints(R, LI, SD, DT);
+}
+
+void Scop::buildDomainsWithBranchConstraints(Region *R, LoopInfo &LI,
+                                             ScopDetection &SD,
+                                             DominatorTree &DT) {
+
+  // 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.
+
+  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 (!SD.isNonAffineSubRegion(SubRegion, &getRegion())) {
+        buildDomainsWithBranchConstraints(SubRegion, LI, SD, DT);
+        continue;
+      }
+    }
+
+    BasicBlock *BB = getRegionNodeBasicBlock(RN);
+    isl_set *Domain = DomainMap[BB];
+    DEBUG(dbgs() << "\tVisit: " << BB->getName() << " : " << Domain << "\n");
+    assert(Domain && "Due to reverse post order traversal of the region all "
+                     "predecessor of the current region node should have been "
+                     "visited and a domain for this region node should have "
+                     "been set.");
+
+    Loop *BBLoop = getRegionNodeLoop(RN, LI);
+    int BBLoopDepth = getRelativeLoopDepth(BBLoop);
+
+    // 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 *, 2> ConditionSets;
+    BranchInst *BI = cast<BranchInst>(BB->getTerminator());
+    if (RN->isSubRegion())
+      ConditionSets.push_back(isl_set_copy(Domain));
+    else
+      buildConditionSets(*this, BI, BBLoop, Domain, ConditionSets);
+
+    // 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.
+    for (unsigned u = 0, e = ConditionSets.size(); u < e; u++) {
+      BasicBlock *SuccBB = getRegionNodeSuccessor(RN, BI, u);
+      isl_set *CondSet = ConditionSets[u];
+
+      // Skip back edges.
+      if (DT.dominates(SuccBB, BB)) {
+        isl_set_free(CondSet);
+        continue;
+      }
+
+      // Check if the edge to SuccBB is a loop exit edge. If so drop the
+      // constrains on the loop/dimension we leave.
+      Loop *SuccBBLoop = LI.getLoopFor(SuccBB);
+      if (SuccBBLoop != BBLoop &&
+          BBLoopDepth > getRelativeLoopDepth(SuccBBLoop)) {
+        assert(BBLoopDepth >= 0 &&
+               "Can only remove a dimension if we exit a loop");
+        CondSet = isl_set_drop_constraints_involving_dims(CondSet, isl_dim_set,
+                                                          BBLoopDepth, 1);
+      }
+
+      // 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 = CondSet;
+      else
+        SuccDomain = isl_set_union(SuccDomain, CondSet);
+
+      SuccDomain = isl_set_coalesce(SuccDomain);
+      DEBUG(dbgs() << "\tSet SuccBB: " << SuccBB->getName() << " : " << Domain
+                   << "\n");
+    }
+  }
+}
+
 void Scop::buildAliasChecks(AliasAnalysis &AA) {
   if (!PollyUseRuntimeAliasChecks)
     return;
@@ -1619,15 +1796,17 @@ static unsigned getMaxLoopDepthInRegion(const Region &R, LoopInfo &LI,
   return MaxLD - MinLD + 1;
 }
 
-Scop::Scop(Region &R, ScalarEvolution &ScalarEvolution, isl_ctx *Context,
-           unsigned MaxLoopDepth)
-    : SE(&ScalarEvolution), R(R), IsOptimized(false),
+Scop::Scop(Region &R, ScalarEvolution &ScalarEvolution, DominatorTree &DT,
+           isl_ctx *Context, unsigned MaxLoopDepth)
+    : DT(DT), SE(&ScalarEvolution), R(R), IsOptimized(false),
       MaxLoopDepth(MaxLoopDepth), IslCtx(Context), Affinator(this) {}
 
 void Scop::initFromTempScop(TempScop &TempScop, LoopInfo &LI, ScopDetection &SD,
                             AliasAnalysis &AA) {
   buildContext();
 
+  buildDomains(&R, LI, SD, DT);
+
   SmallVector<Loop *, 8> NestLoops;
 
   // Build the iteration domain, access functions and schedule functions
@@ -1647,10 +1826,11 @@ void Scop::initFromTempScop(TempScop &TempScop, LoopInfo &LI, ScopDetection &SD,
 
 Scop *Scop::createFromTempScop(TempScop &TempScop, LoopInfo &LI,
                                ScalarEvolution &SE, ScopDetection &SD,
-                               AliasAnalysis &AA, isl_ctx *ctx) {
+                               AliasAnalysis &AA, DominatorTree &DT,
+                               isl_ctx *ctx) {
   auto &R = TempScop.getMaxRegion();
   auto MaxLoopDepth = getMaxLoopDepthInRegion(R, LI, SD);
-  auto S = new Scop(R, SE, ctx, MaxLoopDepth);
+  auto S = new Scop(R, SE, DT, ctx, MaxLoopDepth);
   S->initFromTempScop(TempScop, LI, SD, AA);
 
   return S;
@@ -1661,6 +1841,9 @@ Scop::~Scop() {
   isl_set_free(AssumedContext);
   isl_schedule_free(Schedule);
 
+  for (auto It : DomainMap)
+    isl_set_free(It.second);
+
   // Free the alias groups
   for (MinMaxVectorPairTy &MinMaxAccessPair : MinMaxAliasGroups) {
     for (MinMaxAccessTy &MMA : MinMaxAccessPair.first) {
@@ -2124,9 +2307,11 @@ ScopStmt *Scop::getStmtForBasicBlock(BasicBlock *BB) const {
   return StmtMapIt->second;
 }
 
-unsigned Scop::getRelativeLoopDepth(const Loop *L) const {
-  Loop *OuterLoop = R.outermostLoopInRegion(const_cast<Loop *>(L));
-  assert(OuterLoop && "Scop does not contain this loop");
+int Scop::getRelativeLoopDepth(const Loop *L) const {
+  Loop *OuterLoop =
+      L ? R.outermostLoopInRegion(const_cast<Loop *>(L)) : nullptr;
+  if (!OuterLoop)
+    return -1;
   return L->getLoopDepth() - OuterLoop->getLoopDepth();
 }
 
@@ -2144,6 +2329,7 @@ ScopInfo::~ScopInfo() {
 void ScopInfo::getAnalysisUsage(AnalysisUsage &AU) const {
   AU.addRequired<LoopInfoWrapperPass>();
   AU.addRequired<RegionInfoPass>();
+  AU.addRequired<DominatorTreeWrapperPass>();
   AU.addRequired<ScalarEvolutionWrapperPass>();
   AU.addRequired<ScopDetection>();
   AU.addRequired<TempScopInfo>();
@@ -2156,6 +2342,7 @@ bool ScopInfo::runOnRegion(Region *R, RGPassManager &RGM) {
   AliasAnalysis &AA = getAnalysis<AliasAnalysis>();
   ScopDetection &SD = getAnalysis<ScopDetection>();
   ScalarEvolution &SE = getAnalysis<ScalarEvolutionWrapperPass>().getSE();
+  DominatorTree &DT = getAnalysis<DominatorTreeWrapperPass>().getDomTree();
 
   TempScop *tempScop = getAnalysis<TempScopInfo>().getTempScop();
 
@@ -2165,7 +2352,7 @@ bool ScopInfo::runOnRegion(Region *R, RGPassManager &RGM) {
     return false;
   }
 
-  scop = Scop::createFromTempScop(*tempScop, LI, SE, SD, AA, ctx);
+  scop = Scop::createFromTempScop(*tempScop, LI, SE, SD, AA, DT, ctx);
 
   DEBUG(scop->print(dbgs()));
 
@@ -2195,6 +2382,7 @@ INITIALIZE_PASS_DEPENDENCY(RegionInfoPass);
 INITIALIZE_PASS_DEPENDENCY(ScalarEvolutionWrapperPass);
 INITIALIZE_PASS_DEPENDENCY(ScopDetection);
 INITIALIZE_PASS_DEPENDENCY(TempScopInfo);
+INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass);
 INITIALIZE_PASS_END(ScopInfo, "polly-scops",
                     "Polly - Create polyhedral description of Scops", false,
                     false)
diff --git a/polly/lib/Analysis/TempScopInfo.cpp b/polly/lib/Analysis/TempScopInfo.cpp
index 16aeced9c10..c669f5544f8 100644
--- a/polly/lib/Analysis/TempScopInfo.cpp
+++ b/polly/lib/Analysis/TempScopInfo.cpp
@@ -60,21 +60,6 @@ void Comparison::print(raw_ostream &OS) const {
   // Not yet implemented.
 }
 
-/// Helper function to print the condition
-static void printBBCond(raw_ostream &OS, const BBCond &Cond) {
-  assert(!Cond.empty() && "Unexpected empty condition!");
-  Cond[0].print(OS);
-  for (unsigned i = 1, e = Cond.size(); i != e; ++i) {
-    OS << " && ";
-    Cond[i].print(OS);
-  }
-}
-
-inline raw_ostream &operator<<(raw_ostream &OS, const BBCond &Cond) {
-  printBBCond(OS, Cond);
-  return OS;
-}
-
 //===----------------------------------------------------------------------===//
 // TempScop implementation
 TempScop::~TempScop() {}
@@ -346,125 +331,11 @@ void TempScopInfo::buildAccessFunctions(Region &R, BasicBlock &BB,
   Accs.insert(Accs.end(), Functions.begin(), Functions.end());
 }
 
-Comparison TempScopInfo::buildAffineCondition(Value &V, bool inverted) {
-  if (ConstantInt *C = dyn_cast<ConstantInt>(&V)) {
-    // If this is always true condition, we will create 0 <= 1,
-    // otherwise we will create 0 >= 1.
-    const SCEV *LHS = SE->getConstant(C->getType(), 0);
-    const SCEV *RHS = SE->getConstant(C->getType(), 1);
-
-    if (C->isOne() == inverted)
-      return Comparison(LHS, RHS, ICmpInst::ICMP_SLE);
-    else
-      return Comparison(LHS, RHS, ICmpInst::ICMP_SGE);
-  }
-
-  ICmpInst *ICmp = dyn_cast<ICmpInst>(&V);
-  assert(ICmp && "Only ICmpInst of constant as condition supported!");
-
-  Loop *L = LI->getLoopFor(ICmp->getParent());
-  const SCEV *LHS = SE->getSCEVAtScope(ICmp->getOperand(0), L);
-  const SCEV *RHS = SE->getSCEVAtScope(ICmp->getOperand(1), L);
-
-  ICmpInst::Predicate Pred = ICmp->getPredicate();
-
-  // Invert the predicate if needed.
-  if (inverted)
-    Pred = ICmpInst::getInversePredicate(Pred);
-
-  switch (Pred) {
-  case ICmpInst::ICMP_UGT:
-  case ICmpInst::ICMP_UGE:
-  case ICmpInst::ICMP_ULT:
-  case ICmpInst::ICMP_ULE:
-    // TODO: At the moment we need to see everything as signed. This is an
-    //       correctness issue that needs to be solved.
-    // AffLHS->setUnsigned();
-    // AffRHS->setUnsigned();
-    break;
-  default:
-    break;
-  }
-
-  return Comparison(LHS, RHS, Pred);
-}
-
-void TempScopInfo::buildCondition(BasicBlock *BB, Region &R) {
-  BasicBlock *RegionEntry = R.getEntry();
-  BBCond Cond;
-
-  DomTreeNode *BBNode = DT->getNode(BB), *EntryNode = DT->getNode(RegionEntry);
-  assert(BBNode && EntryNode && "Get null node while building condition!");
-
-  // Walk up the dominance tree until reaching the entry node. Collect all
-  // branching blocks on the path to BB except if BB postdominates the block
-  // containing the condition.
-  SmallVector<BasicBlock *, 4> DominatorBrBlocks;
-  while (BBNode != EntryNode) {
-    BasicBlock *CurBB = BBNode->getBlock();
-    BBNode = BBNode->getIDom();
-    assert(BBNode && "BBNode should not reach the root node!");
-
-    if (PDT->dominates(CurBB, BBNode->getBlock()))
-      continue;
-
-    BranchInst *Br = dyn_cast<BranchInst>(BBNode->getBlock()->getTerminator());
-    assert(Br && "A Valid Scop should only contain branch instruction");
-
-    if (Br->isUnconditional())
-      continue;
-
-    DominatorBrBlocks.push_back(BBNode->getBlock());
-  }
-
-  RegionInfo *RI = R.getRegionInfo();
-  // Iterate in reverse order over the dominating blocks.  Until a non-affine
-  // branch was encountered add all conditions collected. If a non-affine branch
-  // was encountered, stop as we overapproximate from here on anyway.
-  for (auto BIt = DominatorBrBlocks.rbegin(), BEnd = DominatorBrBlocks.rend();
-       BIt != BEnd; BIt++) {
-
-    BasicBlock *BBNode = *BIt;
-    BranchInst *Br = dyn_cast<BranchInst>(BBNode->getTerminator());
-    assert(Br && "A Valid Scop should only contain branch instruction");
-    assert(Br->isConditional() && "Assumed a conditional branch");
-
-    if (SD->isNonAffineSubRegion(RI->getRegionFor(BBNode), &R))
-      break;
-
-    BasicBlock *TrueBB = Br->getSuccessor(0), *FalseBB = Br->getSuccessor(1);
-
-    // Is BB on the ELSE side of the branch?
-    bool inverted = DT->dominates(FalseBB, BB);
-
-    // If both TrueBB and FalseBB dominate BB, one of them must be the target of
-    // a back-edge, i.e. a loop header.
-    if (inverted && DT->dominates(TrueBB, BB)) {
-      assert(
-          (DT->dominates(TrueBB, FalseBB) || DT->dominates(FalseBB, TrueBB)) &&
-          "One of the successors should be the loop header and dominate the"
-          "other!");
-
-      // It is not an invert if the FalseBB is the header.
-      if (DT->dominates(FalseBB, TrueBB))
-        inverted = false;
-    }
-
-    Cond.push_back(buildAffineCondition(*(Br->getCondition()), inverted));
-  }
-
-  if (!Cond.empty())
-    BBConds[BB] = Cond;
-}
-
 TempScop *TempScopInfo::buildTempScop(Region &R) {
-  TempScop *TScop = new TempScop(R, BBConds, AccFuncMap);
+  TempScop *TScop = new TempScop(R, AccFuncMap);
 
   buildAccessFunctions(R, R);
 
-  for (const auto &BB : R.blocks())
-    buildCondition(BB, R);
-
   return TScop;
 }
 
@@ -482,8 +353,6 @@ bool TempScopInfo::runOnRegion(Region *R, RGPassManager &RGM) {
     return false;
 
   Function *F = R->getEntry()->getParent();
-  DT = &getAnalysis<DominatorTreeWrapperPass>().getDomTree();
-  PDT = &getAnalysis<PostDominatorTree>();
   SE = &getAnalysis<ScalarEvolutionWrapperPass>().getSE();
   LI = &getAnalysis<LoopInfoWrapperPass>().getLoopInfo();
   AA = &getAnalysis<AliasAnalysis>();
@@ -497,8 +366,6 @@ bool TempScopInfo::runOnRegion(Region *R, RGPassManager &RGM) {
 }
 
 void TempScopInfo::getAnalysisUsage(AnalysisUsage &AU) const {
-  AU.addRequiredTransitive<DominatorTreeWrapperPass>();
-  AU.addRequiredTransitive<PostDominatorTree>();
   AU.addRequiredTransitive<LoopInfoWrapperPass>();
   AU.addRequiredTransitive<ScalarEvolutionWrapperPass>();
   AU.addRequiredTransitive<ScopDetection>();
@@ -510,7 +377,6 @@ void TempScopInfo::getAnalysisUsage(AnalysisUsage &AU) const {
 TempScopInfo::~TempScopInfo() { clear(); }
 
 void TempScopInfo::clear() {
-  BBConds.clear();
   AccFuncMap.clear();
   if (TempScopOfRegion)
     delete TempScopOfRegion;
@@ -527,9 +393,7 @@ INITIALIZE_PASS_BEGIN(TempScopInfo, "polly-analyze-ir",
                       "Polly - Analyse the LLVM-IR in the detected regions",
                       false, false);
 INITIALIZE_AG_DEPENDENCY(AliasAnalysis);
-INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass);
 INITIALIZE_PASS_DEPENDENCY(LoopInfoWrapperPass);
-INITIALIZE_PASS_DEPENDENCY(PostDominatorTree);
 INITIALIZE_PASS_DEPENDENCY(RegionInfoPass);
 INITIALIZE_PASS_DEPENDENCY(ScalarEvolutionWrapperPass);
 INITIALIZE_PASS_END(TempScopInfo, "polly-analyze-ir",
diff --git a/polly/test/DependenceInfo/reduction_simple_iv_debug_wrapped_dependences.ll b/polly/test/DependenceInfo/reduction_simple_iv_debug_wrapped_dependences.ll
index 30e89eade51..d12b6fa8aa8 100644
--- a/polly/test/DependenceInfo/reduction_simple_iv_debug_wrapped_dependences.ll
+++ b/polly/test/DependenceInfo/reduction_simple_iv_debug_wrapped_dependences.ll
@@ -2,8 +2,16 @@
 ;
 ; REQUIRES: asserts
 ;
-; CHECK: Read: { [Stmt_for_cond[i0] -> MemRef_sum[0]] -> MemRef_sum[0] : i0 >= 0 and i0 <= 100 }
-; CHECK: Write: { [Stmt_for_cond[i0] -> MemRef_sum[0]] -> MemRef_sum[0] : i0 >= 0 and i0 <= 100 }
+; CHECK: Read: { [Stmt_for_cond[i0] -> MemRef_sum[0]] -> MemRef_sum[0] :
+; CHECK-DAG:          i0 >= 0
+; CHECK-DAG:       and
+; CHECK-DAG:          i0 <= 100
+; CHECK:       }
+; CHECK: Write: { [Stmt_for_cond[i0] -> MemRef_sum[0]] -> MemRef_sum[0] :
+; CHECK-DAG:          i0 >= 0
+; CHECK-DAG:       and
+; CHECK-DAG:          i0 <= 100
+; CHECK:       }
 ; CHECK: Wrapped Dependences:
 ; CHECK: RAW dependences:
 ; CHECK:   { [Stmt_for_cond[i0] -> MemRef_sum[0]] -> [Stmt_for_cond[1 + i0] -> MemRef_sum[0]] : i0 <= 99 and i0 >= 0 }
diff --git a/polly/test/Isl/CodeGen/OpenMP/two-parallel-loops-reference-outer-indvar.ll b/polly/test/Isl/CodeGen/OpenMP/two-parallel-loops-reference-outer-indvar.ll
index 9e11057b910..9ba3f4a3a33 100644
--- a/polly/test/Isl/CodeGen/OpenMP/two-parallel-loops-reference-outer-indvar.ll
+++ b/polly/test/Isl/CodeGen/OpenMP/two-parallel-loops-reference-outer-indvar.ll
@@ -4,15 +4,15 @@
 ; This test case verifies that we create correct code even if two OpenMP loops
 ; share common outer variables.
 
-; AST: if (nj >= p_1 + 3) {
+; AST: if (nj >= p_0 + 3) {
 ; AST:   #pragma simd
 ; AST:   #pragma omp parallel for
-; AST:   for (int c0 = 0; c0 < p_0 + nj - 1; c0 += 1)
+; AST:   for (int c0 = 0; c0 < nj + p_2 - 1; c0 += 1)
 ; AST:     Stmt_for_body35(c0);
 ; AST: } else
 ; AST:   #pragma simd
 ; AST:   #pragma omp parallel for
-; AST:   for (int c0 = 0; c0 <= p_0 + p_1; c0 += 1)
+; AST:   for (int c0 = 0; c0 <= p_0 + p_2; c0 += 1)
 ; AST:     Stmt_for_body35(c0);
 
 ; IR: @foo.polly.subfn
diff --git a/polly/test/Isl/CodeGen/if-conditions-in-vector-code.ll b/polly/test/Isl/CodeGen/if-conditions-in-vector-code.ll
index 6d1bc4bb2bf..d629c928051 100644
--- a/polly/test/Isl/CodeGen/if-conditions-in-vector-code.ll
+++ b/polly/test/Isl/CodeGen/if-conditions-in-vector-code.ll
@@ -17,10 +17,10 @@ target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
 
 ; AST: #pragma simd
 ; AST: #pragma known-parallel
-; AST: for (int c0 = 0; c0 <= 15; c0 += 1) {
+; AST: for (int c0 = 0; c0 <= 16; c0 += 1) {
 ; AST:   if ((c0 - 1) % 2 == 0)
 ; AST:     Stmt_bb4(c0);
-; AST:   if (c0 % 3 >= 1)
+; AST:   if (c0 <= 15 && c0 % 3 >= 1)
 ; AST:     Stmt_bb11(c0);
 ; AST: }
 
diff --git a/polly/test/ScopInfo/20111108-Parameter-not-detected.ll b/polly/test/ScopInfo/20111108-Parameter-not-detected.ll
index 7759955eabe..83cb5a0ad1e 100644
--- a/polly/test/ScopInfo/20111108-Parameter-not-detected.ll
+++ b/polly/test/ScopInfo/20111108-Parameter-not-detected.ll
@@ -54,5 +54,11 @@ for.end7:                                         ; preds = %for.cond
 ; CHECK: p0: {0,+,1}<%for.cond>
 
 ; CHECK: Domain :=
-; CHECK: [p_0] -> { Stmt_if_then[i0] : i0 >= 0 and i0 <= 1022 and i0 >= 999 - p_0 };
+; CHECK: [p_0] -> { Stmt_if_then[i0] :
+; CHECK-DAG:         i0 >= 0
+; CHECK-DAG:       and
+; CHECK-DAG:         i0 <= 1022
+; CHECK-DAG:       and
+; CHECK-DAG:         i0 >= 999 - p_0
+; CHECK:          }
 
diff --git a/polly/test/ScopInfo/NonAffine/non-affine-loop-condition-dependent-access_1.ll b/polly/test/ScopInfo/NonAffine/non-affine-loop-condition-dependent-access_1.ll
index ebc9a4ab525..e1da56717ac 100644
--- a/polly/test/ScopInfo/NonAffine/non-affine-loop-condition-dependent-access_1.ll
+++ b/polly/test/ScopInfo/NonAffine/non-affine-loop-condition-dependent-access_1.ll
@@ -12,7 +12,11 @@
 ; SCALAR:    Statements {
 ; SCALAR:      Stmt_bb3__TO__bb11
 ; SCALAR:            Domain :=
-; SCALAR:                { Stmt_bb3__TO__bb11[i0] : i0 >= 0 and i0 <= 1023 };
+; SCALAR:                { Stmt_bb3__TO__bb11[i0] :
+; SCALAR-DAG:               i0 >= 0
+; SCALAR-DAG:             and
+; SCALAR-DAG:               i0 <= 1023
+; SCALAR:                }
 ; SCALAR:            Schedule :=
 ; SCALAR:                { Stmt_bb3__TO__bb11[i0] -> [i0] };
 ; SCALAR:            ReadAccess := [Reduction Type: NONE] [Scalar: 0]
diff --git a/polly/test/ScopInfo/NonAffine/non-affine-loop-condition-dependent-access_2.ll b/polly/test/ScopInfo/NonAffine/non-affine-loop-condition-dependent-access_2.ll
index 5af2b3a34d2..9d272a8a672 100644
--- a/polly/test/ScopInfo/NonAffine/non-affine-loop-condition-dependent-access_2.ll
+++ b/polly/test/ScopInfo/NonAffine/non-affine-loop-condition-dependent-access_2.ll
@@ -18,8 +18,8 @@
 ; INNERMOST:    Function: f
 ; INNERMOST:    Region: %bb15---%bb26
 ; INNERMOST:    Max Loop Depth:  1
-; INNERMOST:    p0: {0,+,{0,+,-1}<nw><%bb11>}<nw><%bb13>
-; INNERMOST:    p1: {0,+,{0,+,1}<nuw><nsw><%bb11>}<nuw><nsw><%bb13>
+; INNERMOST:    p0: {0,+,{0,+,1}<nuw><nsw><%bb11>}<nuw><nsw><%bb13>
+; INNERMOST:    p1: {0,+,{0,+,-1}<nw><%bb11>}<nw><%bb13>
 ; INNERMOST:    p2: {0,+,4}<nuw><nsw><%bb11>
 ; INNERMOST:    p3: {0,+,4}<nuw><nsw><%bb13>
 ; INNERMOST:    p4: {0,+,{0,+,4}<nuw><nsw><%bb11>}<%bb13>
@@ -28,9 +28,9 @@
 ; INNERMOST:    Statements {
 ; INNERMOST:      Stmt_bb16
 ; INNERMOST:            Domain :=
-; INNERMOST:                [p_0, p_1, p_2, p_3, p_4] -> { Stmt_bb16[i0] : (i0 <= 1023 - p_1 and i0 >= 0 and i0 <= 1024 + p_0) or (i0 >= 0 and i0 >= 1025 - p_1 and i0 <= 1024 + p_0) };
+; TODO-INNERMOST:                [p_0, p_1, p_2, p_3, p_4] -> { Stmt_bb16[i0] : i0 <= 1023 - p_0 and i0 >= 0 }
 ; INNERMOST:            Schedule :=
-; INNERMOST:                [p_0, p_1, p_2, p_3, p_4] -> { Stmt_bb16[i0] -> [i0] : i0 >= 1025 - p_1 or i0 <= 1023 - p_1 };
+; TODO-INNERMOST:                [p_0, p_1, p_2, p_3, p_4] -> { Stmt_bb16[i0] -> [i0] }
 ; INNERMOST:            ReadAccess := [Reduction Type: NONE] [Scalar: 0]
 ; INNERMOST:                [p_0, p_1, p_2, p_3, p_4] -> { Stmt_bb16[i0] -> MemRef_A[o0] : 4o0 = p_2 };
 ; INNERMOST:            ReadAccess := [Reduction Type: NONE] [Scalar: 0]
@@ -53,7 +53,15 @@
 ; ALL:    Statements {
 ; ALL:      Stmt_bb15__TO__bb25
 ; ALL:            Domain :=
-; ALL:                { Stmt_bb15__TO__bb25[i0, i1] : i0 >= 0 and i0 <= 1023 and i1 >= 0 and i1 <= 1023 };
+; ALL:                { Stmt_bb15__TO__bb25[i0, i1] :
+; ALL-DAG:               i0 >= 0
+; ALL-DAG:             and
+; ALL-DAG:               i0 <= 1023
+; ALL-DAG:             and
+; ALL-DAG:               i1 >= 0
+; ALL-DAG:             and
+; ALL-DAG:               i1 <= 1023
+; ALL:                }
 ; ALL:            Schedule :=
 ; ALL:                { Stmt_bb15__TO__bb25[i0, i1] -> [i0, i1] };
 ; ALL:            ReadAccess := [Reduction Type: NONE] [Scalar: 0]
diff --git a/polly/test/ScopInfo/NonAffine/non-affine-loop-condition-dependent-access_3.ll b/polly/test/ScopInfo/NonAffine/non-affine-loop-condition-dependent-access_3.ll
index f7c49eb8180..b15f2970a8a 100644
--- a/polly/test/ScopInfo/NonAffine/non-affine-loop-condition-dependent-access_3.ll
+++ b/polly/test/ScopInfo/NonAffine/non-affine-loop-condition-dependent-access_3.ll
@@ -29,7 +29,11 @@
 ; INNERMOST:    Statements {
 ; INNERMOST:      Stmt_bb16
 ; INNERMOST:            Domain :=
-; INNERMOST:                [p_0, p_1, p_2] -> { Stmt_bb16[i0] : i0 >= 0 and i0 <= -1 + p_0 };
+; INNERMOST:                [p_0, p_1, p_2] -> { Stmt_bb16[i0] :
+; INNERMOST-DAG:               i0 >= 0
+; INNERMOST-DAG:             and
+; INNERMOST-DAG:               i0 <= -1 + p_0
+; INNERMOST-DAG:             };
 ; INNERMOST:            Schedule :=
 ; INNERMOST:                [p_0, p_1, p_2] -> { Stmt_bb16[i0] -> [i0] };
 ; INNERMOST:            ReadAccess := [Reduction Type: NONE] [Scalar: 0]
@@ -54,7 +58,15 @@
 ; ALL:    Statements {
 ; ALL:      Stmt_bb15__TO__bb25
 ; ALL:            Domain :=
-; ALL:                { Stmt_bb15__TO__bb25[i0, i1] : i0 >= 0 and i0 <= 1023 and i1 >= 0 and i1 <= 1023 };
+; ALL:                { Stmt_bb15__TO__bb25[i0, i1] :
+; ALL-DAG:               i0 >= 0
+; ALL-DAG:             and
+; ALL-DAG:               i0 <= 1023
+; ALL-DAG:             and
+; ALL-DAG:               i1 >= 0
+; ALL-DAG:             and
+; ALL-DAG:               i1 <= 1023
+; ALL:                }
 ; ALL:            Schedule :=
 ; ALL:                { Stmt_bb15__TO__bb25[i0, i1] -> [i0, i1] };
 ; ALL:            ReadAccess := [Reduction Type: NONE] [Scalar: 0]
diff --git a/polly/test/ScopInfo/NonAffine/non_affine_conditional_nested.ll b/polly/test/ScopInfo/NonAffine/non_affine_conditional_nested.ll
index f453a81f329..e4771cc91f9 100644
--- a/polly/test/ScopInfo/NonAffine/non_affine_conditional_nested.ll
+++ b/polly/test/ScopInfo/NonAffine/non_affine_conditional_nested.ll
@@ -12,8 +12,6 @@
 ; CHECK:    Max Loop Depth:  1
 ; CHECK:    Statements {
 ; CHECK:      Stmt_bb2__TO__bb16
-; CHECK:            Domain :=
-; CHECK:                { Stmt_bb2__TO__bb16[i0] : i0 >= 0 and i0 <= 1023 };
 ; CHECK:            Schedule :=
 ; CHECK:                { Stmt_bb2__TO__bb16[i0] -> [i0] };
 ; CHECK:            ReadAccess := [Reduction Type: NONE] [Scalar: 0]
diff --git a/polly/test/ScopInfo/NonAffine/non_affine_conditional_surrounding_affine_loop.ll b/polly/test/ScopInfo/NonAffine/non_affine_conditional_surrounding_affine_loop.ll
index 26ba60c785f..acde943b478 100644
--- a/polly/test/ScopInfo/NonAffine/non_affine_conditional_surrounding_affine_loop.ll
+++ b/polly/test/ScopInfo/NonAffine/non_affine_conditional_surrounding_affine_loop.ll
@@ -19,7 +19,11 @@
 ; INNERMOST:    Statements {
 ; INNERMOST:      Stmt_bb11
 ; INNERMOST:            Domain :=
-; INNERMOST:                [N] -> { Stmt_bb11[i0] : i0 >= 0 and N >= 1 and i0 <= -1 + N };
+; INNERMOST:                [N] -> { Stmt_bb11[i0] :
+; INNERMOST-DAG:                i0 >= 0
+; INNERMOST-DAG:              and
+; INNERMOST-DAG:                i0 <= -1 + N
+; INNERMOST:                  }
 ; INNERMOST:            Schedule :=
 ; INNERMOST:                [N] -> { Stmt_bb11[i0] -> [i0] };
 ; INNERMOST:            ReadAccess := [Reduction Type: +] [Scalar: 0]
@@ -40,7 +44,11 @@
 ; ALL:    Statements {
 ; ALL:      Stmt_bb4__TO__bb17
 ; ALL:            Domain :=
-; ALL:                { Stmt_bb4__TO__bb17[i0] : i0 >= 0 and i0 <= 1023 };
+; ALL:                { Stmt_bb4__TO__bb17[i0] :
+; ALL-DAG:               i0 >= 0
+; ALL-DAG:             and
+; ALL-DAG:               i0 <= 1023
+; ALL:                }
 ; ALL:            Schedule :=
 ; ALL:                { Stmt_bb4__TO__bb17[i0] -> [i0] };
 ; ALL:            ReadAccess := [Reduction Type: NONE] [Scalar: 0]
diff --git a/polly/test/ScopInfo/NonAffine/non_affine_conditional_surrounding_non_affine_loop.ll b/polly/test/ScopInfo/NonAffine/non_affine_conditional_surrounding_non_affine_loop.ll
index 57252793549..99edaa5f9dc 100644
--- a/polly/test/ScopInfo/NonAffine/non_affine_conditional_surrounding_non_affine_loop.ll
+++ b/polly/test/ScopInfo/NonAffine/non_affine_conditional_surrounding_non_affine_loop.ll
@@ -18,7 +18,11 @@
 ; INNERMOST:    Statements {
 ; INNERMOST:      Stmt_bb12
 ; INNERMOST:            Domain :=
-; INNERMOST:                [p_0] -> { Stmt_bb12[i0] : i0 >= 0 and p_0 >= 1 and i0 <= -1 + p_0 };
+; INNERMOST:                [p_0] -> { Stmt_bb12[i0] :
+; INNERMOST-DAG:                i0 >= 0
+; INNERMOST-DAG:              and
+; INNERMOST-DAG:                i0 <= -1 + p_0
+; INNERMOST:                  }
 ; INNERMOST:            Schedule :=
 ; INNERMOST:                [p_0] -> { Stmt_bb12[i0] -> [i0] };
 ; INNERMOST:            ReadAccess := [Reduction Type: +] [Scalar: 0]
@@ -39,7 +43,11 @@
 ; ALL:    Statements {
 ; ALL:      Stmt_bb4__TO__bb18
 ; ALL:            Domain :=
-; ALL:                { Stmt_bb4__TO__bb18[i0] : i0 >= 0 and i0 <= 1023 };
+; ALL:                { Stmt_bb4__TO__bb18[i0] :
+; ALL-DAG:               i0 >= 0
+; ALL-DAG:             and
+; ALL-DAG:               i0 <= 1023
+; ALL:                }
 ; ALL:            Schedule :=
 ; ALL:                { Stmt_bb4__TO__bb18[i0] -> [i0] };
 ; ALL:            ReadAccess := [Reduction Type: NONE] [Scalar: 0]
diff --git a/polly/test/ScopInfo/NonAffine/non_affine_float_compare.ll b/polly/test/ScopInfo/NonAffine/non_affine_float_compare.ll
index 243048c25e5..f6b93295d53 100644
--- a/polly/test/ScopInfo/NonAffine/non_affine_float_compare.ll
+++ b/polly/test/ScopInfo/NonAffine/non_affine_float_compare.ll
@@ -13,7 +13,11 @@
 ; CHECK:    Statements {
 ; CHECK:      Stmt_bb2__TO__bb12
 ; CHECK:            Domain :=
-; CHECK:                { Stmt_bb2__TO__bb12[i0] : i0 >= 0 and i0 <= 1023 };
+; CHECK:                { Stmt_bb2__TO__bb12[i0] :
+; CHECK-DAG:               i0 >= 0
+; CHECK-DAG:             and
+; CHECK-DAG:               i0 <= 1023
+; CHECK:                }
 ; CHECK:            Schedule :=
 ; CHECK:                { Stmt_bb2__TO__bb12[i0] -> [i0] };
 ; CHECK:            ReadAccess := [Reduction Type: NONE] [Scalar: 0]
diff --git a/polly/test/ScopInfo/NonAffine/non_affine_loop_condition.ll b/polly/test/ScopInfo/NonAffine/non_affine_loop_condition.ll
index bf17db95248..66f8bd95f84 100644
--- a/polly/test/ScopInfo/NonAffine/non_affine_loop_condition.ll
+++ b/polly/test/ScopInfo/NonAffine/non_affine_loop_condition.ll
@@ -20,7 +20,11 @@
 ; CHECK:    Statements {
 ; CHECK:      Stmt_bb3__TO__bb10
 ; CHECK:            Domain :=
-; CHECK:                { Stmt_bb3__TO__bb10[i0] : i0 >= 0 and i0 <= 1023 };
+; CHECK:                { Stmt_bb3__TO__bb10[i0] :
+; CHECK-DAG:               i0 >= 0
+; CHECK-DAG:             and
+; CHECK-DAG:               i0 <= 1023
+; CHECK:                }
 ; CHECK:            Schedule :=
 ; CHECK:                { Stmt_bb3__TO__bb10[i0] -> [i0] };
 ; CHECK:            ReadAccess := [Reduction Type: NONE] [Scalar: 0]
diff --git a/polly/test/ScopInfo/NonAffine/non_affine_loop_used_later.ll b/polly/test/ScopInfo/NonAffine/non_affine_loop_used_later.ll
index 8d8f7a72043..37e6b97046c 100644
--- a/polly/test/ScopInfo/NonAffine/non_affine_loop_used_later.ll
+++ b/polly/test/ScopInfo/NonAffine/non_affine_loop_used_later.ll
@@ -15,17 +15,10 @@
 ; CHECK:        n/a
 ; CHECK:    Statements {
 ; CHECK:      Stmt_bb2
-; CHECK:            Domain :=
-; CHECK:                [N] -> { Stmt_bb2[i0] : i0 >= 0 and N >= 1 and i0 <= N; Stmt_bb2[0] : N <= 0 }
-; CHECK:            Schedule :=
-; CHECK:                [N] -> { Stmt_bb2[i0] -> [i0, 0] : N >= 1 and i0 <= N; Stmt_bb2[0] -> [0, 0] : N <= 0 }
-; CHECK:            ReadAccess := [Reduction Type: NONE] [Scalar: 1]
 ; CHECK:                [N] -> { Stmt_bb2[i0] -> MemRef_j_0__phi[] };
 ; CHECK:            MustWriteAccess :=  [Reduction Type: NONE] [Scalar: 1]
 ; CHECK:                [N] -> { Stmt_bb2[i0] -> MemRef_j_0[] };
 ; CHECK:      Stmt_bb4__TO__bb18
-; CHECK:            Domain :=
-; CHECK:                [N] -> { Stmt_bb4__TO__bb18[i0] : i0 >= 0 and N >= 1 and i0 <= -1 + N };
 ; CHECK:            Schedule :=
 ; CHECK:                [N] -> { Stmt_bb4__TO__bb18[i0] -> [i0, 1] };
 ; CHECK:            ReadAccess := [Reduction Type: NONE] [Scalar: 0]
@@ -43,8 +36,6 @@
 ; CHECK:            MayWriteAccess := [Reduction Type: NONE] [Scalar: 1]
 ; CHECK:                [N] -> { Stmt_bb4__TO__bb18[i0] -> MemRef_j_2__phi[] };
 ; CHECK:      Stmt_bb18
-; CHECK:            Domain :=
-; CHECK:                [N] -> { Stmt_bb18[i0] : i0 >= 0 and N >= 1 and i0 <= -1 + N };
 ; CHECK:            Schedule :=
 ; CHECK:                [N] -> { Stmt_bb18[i0] -> [i0, 2] };
 ; CHECK:            MustWriteAccess :=  [Reduction Type: NONE] [Scalar: 1]
@@ -56,8 +47,6 @@
 ; CHECK:            MustWriteAccess :=  [Reduction Type: NONE] [Scalar: 0]
 ; CHECK:                [N] -> { Stmt_bb18[i0] -> MemRef_A[i0] };
 ; CHECK:      Stmt_bb23
-; CHECK:            Domain :=
-; CHECK:                [N] -> { Stmt_bb23[i0] : i0 >= 0 and N >= 1 and i0 <= -1 + N };
 ; CHECK:            Schedule :=
 ; CHECK:                [N] -> { Stmt_bb23[i0] -> [i0, 3] };
 ; CHECK:            ReadAccess := [Reduction Type: NONE] [Scalar: 1]
diff --git a/polly/test/ScopInfo/NonAffine/non_affine_parametric_loop.ll b/polly/test/ScopInfo/NonAffine/non_affine_parametric_loop.ll
index 5bdd6c29076..3583acb66e6 100644
--- a/polly/test/ScopInfo/NonAffine/non_affine_parametric_loop.ll
+++ b/polly/test/ScopInfo/NonAffine/non_affine_parametric_loop.ll
@@ -26,8 +26,6 @@ for.end:
 
 ; CHECK: p0: %n
 
-; CHECK: Domain
-; CHECK:   [n] -> { Stmt_for_body[i0] : i0 >= 0 and i0 <= -1 + n };
 ; CHECK: Schedule
 ; CHECK:   [n] -> { Stmt_for_body[i0] -> [i0] };
 ; CHECK: ReadAccess
diff --git a/polly/test/ScopInfo/cfg_consequences.ll b/polly/test/ScopInfo/cfg_consequences.ll
new file mode 100644
index 00000000000..dd51038a557
--- /dev/null
+++ b/polly/test/ScopInfo/cfg_consequences.ll
@@ -0,0 +1,331 @@
+; RUN: opt %loadPolly -analyze -polly-scops -polly-detect-scops-in-functions-without-loops -polly-detect-scops-in-regions-without-loops -polly-detect-unprofitable < %s | FileCheck %s
+;
+; void consequences(int *A, int bool_cond, int lhs, int rhs) {
+;
+;   BC: *A = 0;
+;     if (bool_cond)
+;   S_BC:     *A = 0;
+;   M_BC: *A = 0;
+;
+;   NEG_BC: *A = 0;
+;     if (!bool_cond)
+;   S_NEG_BC: *A = 0;
+;   M_NEG_BC: *A = 0;
+;
+;   SLT: *A = 0;
+;     if (lhs < rhs)
+;   S_SLT:    *A = 0;
+;   M_SLT: *A = 0;
+;
+;   SLE: *A = 0;
+;     if (lhs <= rhs)
+;   S_SLE:    *A = 0;
+;   M_SLE: *A = 0;
+;
+;   SGT: *A = 0;
+;     if (lhs > rhs)
+;   S_SGT:    *A = 0;
+;   M_SGT: *A = 0;
+;
+;   SGE: *A = 0;
+;     if (lhs >= rhs)
+;   S_SGE:    *A = 0;
+;   M_SGE: *A = 0;
+;
+;   EQ: *A = 0;
+;     if (lhs == rhs)
+;   S_EQ:    *A = 0;
+;   M_EQ: *A = 0;
+;
+;   NEQ: *A = 0;
+;     if (lhs != rhs)
+;   S_NEQ:   *A = 0;
+;   M_NEQ: *A = 0;
+;
+; }
+; CHECK:           Stmt_BC
+; CHECK-NEXT:            Domain :=
+; CHECK-NEXT:                [bool_cond, lhs, rhs] -> { Stmt_BC[] };
+; CHECK-NEXT:            Schedule :=
+; CHECK-NEXT:                [bool_cond, lhs, rhs] -> { Stmt_BC[] -> [0] };
+; CHECK-NEXT:            MustWriteAccess :=  [Reduction Type: NONE] [Scalar: 0]
+; CHECK-NEXT:                [bool_cond, lhs, rhs] -> { Stmt_BC[] -> MemRef_A[0] };
+; CHECK-NEXT:      Stmt_S_BC
+; CHECK-NEXT:            Domain :=
+; CHECK-NEXT:                [bool_cond, lhs, rhs] -> { Stmt_S_BC[] : bool_cond <= -1 or bool_cond >= 1 };
+; CHECK-NEXT:            Schedule :=
+; CHECK-NEXT:                [bool_cond, lhs, rhs] -> { Stmt_S_BC[] -> [1] : bool_cond <= -1 or bool_cond >= 1 };
+; CHECK-NEXT:            MustWriteAccess :=  [Reduction Type: NONE] [Scalar: 0]
+; CHECK-NEXT:                [bool_cond, lhs, rhs] -> { Stmt_S_BC[] -> MemRef_A[0] };
+; CHECK-NEXT:      Stmt_M_BC
+; CHECK-NEXT:            Domain :=
+; CHECK-NEXT:                [bool_cond, lhs, rhs] -> { Stmt_M_BC[] };
+; CHECK-NEXT:            Schedule :=
+; CHECK-NEXT:                [bool_cond, lhs, rhs] -> { Stmt_M_BC[] -> [2] };
+; CHECK-NEXT:            MustWriteAccess :=  [Reduction Type: NONE] [Scalar: 0]
+; CHECK-NEXT:                [bool_cond, lhs, rhs] -> { Stmt_M_BC[] -> MemRef_A[0] };
+; CHECK-NEXT:      Stmt_NEG_BC
+; CHECK-NEXT:            Domain :=
+; CHECK-NEXT:                [bool_cond, lhs, rhs] -> { Stmt_NEG_BC[] };
+; CHECK-NEXT:            Schedule :=
+; CHECK-NEXT:                [bool_cond, lhs, rhs] -> { Stmt_NEG_BC[] -> [3] };
+; CHECK-NEXT:            MustWriteAccess :=  [Reduction Type: NONE] [Scalar: 0]
+; CHECK-NEXT:                [bool_cond, lhs, rhs] -> { Stmt_NEG_BC[] -> MemRef_A[0] };
+; CHECK-NEXT:      Stmt_S_NEG_BC
+; CHECK-NEXT:            Domain :=
+; CHECK-NEXT:                [bool_cond, lhs, rhs] -> { Stmt_S_NEG_BC[] : bool_cond = 0 };
+; CHECK-NEXT:            Schedule :=
+; CHECK-NEXT:                [bool_cond, lhs, rhs] -> { Stmt_S_NEG_BC[] -> [4] };
+; CHECK-NEXT:            MustWriteAccess :=  [Reduction Type: NONE] [Scalar: 0]
+; CHECK-NEXT:                [bool_cond, lhs, rhs] -> { Stmt_S_NEG_BC[] -> MemRef_A[0] };
+; CHECK-NEXT:      Stmt_M_NEG_BC
+; CHECK-NEXT:            Domain :=
+; CHECK-NEXT:                [bool_cond, lhs, rhs] -> { Stmt_M_NEG_BC[] };
+; CHECK-NEXT:            Schedule :=
+; CHECK-NEXT:                [bool_cond, lhs, rhs] -> { Stmt_M_NEG_BC[] -> [5] };
+; CHECK-NEXT:            MustWriteAccess :=  [Reduction Type: NONE] [Scalar: 0]
+; CHECK-NEXT:                [bool_cond, lhs, rhs] -> { Stmt_M_NEG_BC[] -> MemRef_A[0] };
+; CHECK-NEXT:      Stmt_SLT
+; CHECK-NEXT:            Domain :=
+; CHECK-NEXT:                [bool_cond, lhs, rhs] -> { Stmt_SLT[] };
+; CHECK-NEXT:            Schedule :=
+; CHECK-NEXT:                [bool_cond, lhs, rhs] -> { Stmt_SLT[] -> [6] };
+; CHECK-NEXT:            MustWriteAccess :=  [Reduction Type: NONE] [Scalar: 0]
+; CHECK-NEXT:                [bool_cond, lhs, rhs] -> { Stmt_SLT[] -> MemRef_A[0] };
+; CHECK-NEXT:      Stmt_S_SLT
+; CHECK-NEXT:            Domain :=
+; CHECK-NEXT:                [bool_cond, lhs, rhs] -> { Stmt_S_SLT[] : rhs >= 1 + lhs };
+; CHECK-NEXT:            Schedule :=
+; CHECK-NEXT:                [bool_cond, lhs, rhs] -> { Stmt_S_SLT[] -> [7] };
+; CHECK-NEXT:            MustWriteAccess :=  [Reduction Type: NONE] [Scalar: 0]
+; CHECK-NEXT:                [bool_cond, lhs, rhs] -> { Stmt_S_SLT[] -> MemRef_A[0] };
+; CHECK-NEXT:      Stmt_M_SLT
+; CHECK-NEXT:            Domain :=
+; CHECK-NEXT:                [bool_cond, lhs, rhs] -> { Stmt_M_SLT[] };
+; CHECK-NEXT:            Schedule :=
+; CHECK-NEXT:                [bool_cond, lhs, rhs] -> { Stmt_M_SLT[] -> [8] };
+; CHECK-NEXT:            MustWriteAccess :=  [Reduction Type: NONE] [Scalar: 0]
+; CHECK-NEXT:                [bool_cond, lhs, rhs] -> { Stmt_M_SLT[] -> MemRef_A[0] };
+; CHECK-NEXT:      Stmt_SLE
+; CHECK-NEXT:            Domain :=
+; CHECK-NEXT:                [bool_cond, lhs, rhs] -> { Stmt_SLE[] };
+; CHECK-NEXT:            Schedule :=
+; CHECK-NEXT:                [bool_cond, lhs, rhs] -> { Stmt_SLE[] -> [9] };
+; CHECK-NEXT:            MustWriteAccess :=  [Reduction Type: NONE] [Scalar: 0]
+; CHECK-NEXT:                [bool_cond, lhs, rhs] -> { Stmt_SLE[] -> MemRef_A[0] };
+; CHECK-NEXT:      Stmt_S_SLE
+; CHECK-NEXT:            Domain :=
+; CHECK-NEXT:                [bool_cond, lhs, rhs] -> { Stmt_S_SLE[] : rhs >= lhs };
+; CHECK-NEXT:            Schedule :=
+; CHECK-NEXT:                [bool_cond, lhs, rhs] -> { Stmt_S_SLE[] -> [10] };
+; CHECK-NEXT:            MustWriteAccess :=  [Reduction Type: NONE] [Scalar: 0]
+; CHECK-NEXT:                [bool_cond, lhs, rhs] -> { Stmt_S_SLE[] -> MemRef_A[0] };
+; CHECK-NEXT:      Stmt_M_SLE
+; CHECK-NEXT:            Domain :=
+; CHECK-NEXT:                [bool_cond, lhs, rhs] -> { Stmt_M_SLE[] };
+; CHECK-NEXT:            Schedule :=
+; CHECK-NEXT:                [bool_cond, lhs, rhs] -> { Stmt_M_SLE[] -> [11] };
+; CHECK-NEXT:            MustWriteAccess :=  [Reduction Type: NONE] [Scalar: 0]
+; CHECK-NEXT:                [bool_cond, lhs, rhs] -> { Stmt_M_SLE[] -> MemRef_A[0] };
+; CHECK-NEXT:      Stmt_SGT
+; CHECK-NEXT:            Domain :=
+; CHECK-NEXT:                [bool_cond, lhs, rhs] -> { Stmt_SGT[] };
+; CHECK-NEXT:            Schedule :=
+; CHECK-NEXT:                [bool_cond, lhs, rhs] -> { Stmt_SGT[] -> [12] };
+; CHECK-NEXT:            MustWriteAccess :=  [Reduction Type: NONE] [Scalar: 0]
+; CHECK-NEXT:                [bool_cond, lhs, rhs] -> { Stmt_SGT[] -> MemRef_A[0] };
+; CHECK-NEXT:      Stmt_S_SGT
+; CHECK-NEXT:            Domain :=
+; CHECK-NEXT:                [bool_cond, lhs, rhs] -> { Stmt_S_SGT[] : rhs <= -1 + lhs };
+; CHECK-NEXT:            Schedule :=
+; CHECK-NEXT:                [bool_cond, lhs, rhs] -> { Stmt_S_SGT[] -> [13] };
+; CHECK-NEXT:            MustWriteAccess :=  [Reduction Type: NONE] [Scalar: 0]
+; CHECK-NEXT:                [bool_cond, lhs, rhs] -> { Stmt_S_SGT[] -> MemRef_A[0] };
+; CHECK-NEXT:      Stmt_M_SGT
+; CHECK-NEXT:            Domain :=
+; CHECK-NEXT:                [bool_cond, lhs, rhs] -> { Stmt_M_SGT[] };
+; CHECK-NEXT:            Schedule :=
+; CHECK-NEXT:                [bool_cond, lhs, rhs] -> { Stmt_M_SGT[] -> [14] };
+; CHECK-NEXT:            MustWriteAccess :=  [Reduction Type: NONE] [Scalar: 0]
+; CHECK-NEXT:                [bool_cond, lhs, rhs] -> { Stmt_M_SGT[] -> MemRef_A[0] };
+; CHECK-NEXT:      Stmt_SGE
+; CHECK-NEXT:            Domain :=
+; CHECK-NEXT:                [bool_cond, lhs, rhs] -> { Stmt_SGE[] };
+; CHECK-NEXT:            Schedule :=
+; CHECK-NEXT:                [bool_cond, lhs, rhs] -> { Stmt_SGE[] -> [15] };
+; CHECK-NEXT:            MustWriteAccess :=  [Reduction Type: NONE] [Scalar: 0]
+; CHECK-NEXT:                [bool_cond, lhs, rhs] -> { Stmt_SGE[] -> MemRef_A[0] };
+; CHECK-NEXT:      Stmt_S_SGE
+; CHECK-NEXT:            Domain :=
+; CHECK-NEXT:                [bool_cond, lhs, rhs] -> { Stmt_S_SGE[] : rhs <= lhs };
+; CHECK-NEXT:            Schedule :=
+; CHECK-NEXT:                [bool_cond, lhs, rhs] -> { Stmt_S_SGE[] -> [16] };
+; CHECK-NEXT:            MustWriteAccess :=  [Reduction Type: NONE] [Scalar: 0]
+; CHECK-NEXT:                [bool_cond, lhs, rhs] -> { Stmt_S_SGE[] -> MemRef_A[0] };
+; CHECK-NEXT:      Stmt_M_SGE
+; CHECK-NEXT:            Domain :=
+; CHECK-NEXT:                [bool_cond, lhs, rhs] -> { Stmt_M_SGE[] };
+; CHECK-NEXT:            Schedule :=
+; CHECK-NEXT:                [bool_cond, lhs, rhs] -> { Stmt_M_SGE[] -> [17] };
+; CHECK-NEXT:            MustWriteAccess :=  [Reduction Type: NONE] [Scalar: 0]
+; CHECK-NEXT:                [bool_cond, lhs, rhs] -> { Stmt_M_SGE[] -> MemRef_A[0] };
+; CHECK-NEXT:      Stmt_EQ
+; CHECK-NEXT:            Domain :=
+; CHECK-NEXT:                [bool_cond, lhs, rhs] -> { Stmt_EQ[] };
+; CHECK-NEXT:            Schedule :=
+; CHECK-NEXT:                [bool_cond, lhs, rhs] -> { Stmt_EQ[] -> [18] };
+; CHECK-NEXT:            MustWriteAccess :=  [Reduction Type: NONE] [Scalar: 0]
+; CHECK-NEXT:                [bool_cond, lhs, rhs] -> { Stmt_EQ[] -> MemRef_A[0] };
+; CHECK-NEXT:      Stmt_S_EQ
+; CHECK-NEXT:            Domain :=
+; CHECK-NEXT:                [bool_cond, lhs, rhs] -> { Stmt_S_EQ[] : rhs = lhs };
+; CHECK-NEXT:            Schedule :=
+; CHECK-NEXT:                [bool_cond, lhs, rhs] -> { Stmt_S_EQ[] -> [19] };
+; CHECK-NEXT:            MustWriteAccess :=  [Reduction Type: NONE] [Scalar: 0]
+; CHECK-NEXT:                [bool_cond, lhs, rhs] -> { Stmt_S_EQ[] -> MemRef_A[0] };
+; CHECK-NEXT:      Stmt_M_EQ
+; CHECK-NEXT:            Domain :=
+; CHECK-NEXT:                [bool_cond, lhs, rhs] -> { Stmt_M_EQ[] };
+; CHECK-NEXT:            Schedule :=
+; CHECK-NEXT:                [bool_cond, lhs, rhs] -> { Stmt_M_EQ[] -> [20] };
+; CHECK-NEXT:            MustWriteAccess :=  [Reduction Type: NONE] [Scalar: 0]
+; CHECK-NEXT:                [bool_cond, lhs, rhs] -> { Stmt_M_EQ[] -> MemRef_A[0] };
+; CHECK-NEXT:      Stmt_NEQ
+; CHECK-NEXT:            Domain :=
+; CHECK-NEXT:                [bool_cond, lhs, rhs] -> { Stmt_NEQ[] };
+; CHECK-NEXT:            Schedule :=
+; CHECK-NEXT:                [bool_cond, lhs, rhs] -> { Stmt_NEQ[] -> [21] };
+; CHECK-NEXT:            MustWriteAccess :=  [Reduction Type: NONE] [Scalar: 0]
+; CHECK-NEXT:                [bool_cond, lhs, rhs] -> { Stmt_NEQ[] -> MemRef_A[0] };
+; CHECK-NEXT:      Stmt_S_NEQ
+; CHECK-NEXT:            Domain :=
+; CHECK-NEXT:                [bool_cond, lhs, rhs] -> { Stmt_S_NEQ[] :
+; CHECK-DAG:                                             rhs >= 1 + lhs 
+; CHECK-DAG:                                           or
+; CHECK-DAG:                                             rhs <= -1 + lhs
+; CHECK:                                              };
+; CHECK-NEXT:            Schedule :=
+; CHECK-NEXT:                [bool_cond, lhs, rhs] -> { Stmt_S_NEQ[] -> [22] : rhs >= 1 + lhs or rhs <= -1 + lhs };
+; CHECK-NEXT:            MustWriteAccess :=  [Reduction Type: NONE] [Scalar: 0]
+; CHECK-NEXT:                [bool_cond, lhs, rhs] -> { Stmt_S_NEQ[] -> MemRef_A[0] };
+; CHECK-NEXT:      Stmt_M_NEQ
+; CHECK-NEXT:            Domain :=
+; CHECK-NEXT:                [bool_cond, lhs, rhs] -> { Stmt_M_NEQ[] };
+; CHECK-NEXT:            Schedule :=
+; CHECK-NEXT:                [bool_cond, lhs, rhs] -> { Stmt_M_NEQ[] -> [23] };
+; CHECK-NEXT:            MustWriteAccess :=  [Reduction Type: NONE] [Scalar: 0]
+; CHECK-NEXT:                [bool_cond, lhs, rhs] -> { Stmt_M_NEQ[] -> MemRef_A[0] };
+;
+target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
+
+define void @consequences(i32* %A, i32 %bool_cond, i32 %lhs, i32 %rhs) {
+entry:
+  br label %BC
+
+BC:                                               ; preds = %entry
+  store i32 0, i32* %A, align 4
+  %tobool = icmp eq i32 %bool_cond, 0
+  br i1 %tobool, label %M_BC, label %S_BC
+
+S_BC:                                             ; preds = %if.then
+  store i32 0, i32* %A, align 4
+  br label %M_BC
+
+M_BC:                                           ; preds = %BC, %S_BC
+  store i32 0, i32* %A, align 4
+  br label %NEG_BC
+
+NEG_BC:                                           ; preds = %if.end
+  store i32 0, i32* %A, align 4
+  %tobool1 = icmp eq i32 %bool_cond, 0
+  br i1 %tobool1, label %S_NEG_BC, label %M_NEG_BC
+
+S_NEG_BC:                                         ; preds = %if.then.2
+  store i32 0, i32* %A, align 4
+  br label %M_NEG_BC
+
+M_NEG_BC:                                         ; preds = %NEG_BC, %S_NEG_BC
+  store i32 0, i32* %A, align 4
+  br label %SLT
+
+SLT:                                              ; preds = %if.end.3
+  store i32 0, i32* %A, align 4
+  %cmp = icmp slt i32 %lhs, %rhs
+  br i1 %cmp, label %S_SLT, label %M_SLT
+
+S_SLT:                                            ; preds = %if.then.4
+  store i32 0, i32* %A, align 4
+  br label %M_SLT
+
+M_SLT:                                         ; preds = %S_SLT, %SLT
+  store i32 0, i32* %A, align 4
+  br label %SLE
+
+SLE:                                              ; preds = %if.end.5
+  store i32 0, i32* %A, align 4
+  %cmp6 = icmp sgt i32 %lhs, %rhs
+  br i1 %cmp6, label %M_SLE, label %S_SLE
+
+S_SLE:                                            ; preds = %if.then.7
+  store i32 0, i32* %A, align 4
+  br label %M_SLE
+
+M_SLE:                                         ; preds = %SLE, %S_SLE
+  store i32 0, i32* %A, align 4
+  br label %SGT
+
+SGT:                                              ; preds = %if.end.8
+  store i32 0, i32* %A, align 4
+  %cmp9 = icmp sgt i32 %lhs, %rhs
+  br i1 %cmp9, label %S_SGT, label %M_SGT
+
+S_SGT:                                            ; preds = %if.then.10
+  store i32 0, i32* %A, align 4
+  br label %M_SGT
+
+M_SGT:                                        ; preds = %S_SGT, %SGT
+  store i32 0, i32* %A, align 4
+  br label %SGE
+
+SGE:                                              ; preds = %if.end.11
+  store i32 0, i32* %A, align 4
+  %cmp12 = icmp slt i32 %lhs, %rhs
+  br i1 %cmp12, label %M_SGE, label %S_SGE
+
+S_SGE:                                            ; preds = %if.then.13
+  store i32 0, i32* %A, align 4
+  br label %M_SGE
+
+M_SGE:                                        ; preds = %SGE, %S_SGE
+  store i32 0, i32* %A, align 4
+  br label %EQ
+
+EQ:                                               ; preds = %if.end.14
+  store i32 0, i32* %A, align 4
+  %cmp15 = icmp eq i32 %lhs, %rhs
+  br i1 %cmp15, label %S_EQ, label %M_EQ
+
+S_EQ:                                             ; preds = %if.then.16
+  store i32 0, i32* %A, align 4
+  br label %M_EQ
+
+M_EQ:                                        ; preds = %S_EQ, %EQ
+  store i32 0, i32* %A, align 4
+  br label %NEQ
+
+NEQ:                                              ; preds = %if.end.17
+  store i32 0, i32* %A, align 4
+  %cmp18 = icmp eq i32 %lhs, %rhs
+  br i1 %cmp18, label %M_NEQ, label %S_NEQ
+
+S_NEQ:                                            ; preds = %if.then.19
+  store i32 0, i32* %A, align 4
+  br label %M_NEQ
+
+M_NEQ:                                        ; preds = %NEQ, %S_NEQ
+  store i32 0, i32* %A, align 4
+  br label %exit
+
+exit:
+  ret void
+}
diff --git a/polly/test/ScopInfo/delinearize-together-all-data-refs.ll b/polly/test/ScopInfo/delinearize-together-all-data-refs.ll
index 446c95104e2..99e769ce36f 100644
--- a/polly/test/ScopInfo/delinearize-together-all-data-refs.ll
+++ b/polly/test/ScopInfo/delinearize-together-all-data-refs.ll
@@ -14,8 +14,8 @@
 ; CHECK:     double MemRef_A[*][%m][%o][8] // Element size 8
 ; CHECK: }
 
-; CHECK: [n, m, o] -> { Stmt_for_body6[i0, i1, i2] -> MemRef_A[3 + i0, i1, 7 + i2] };
-; CHECK: [n, m, o] -> { Stmt_for_body6[i0, i1, i2] -> MemRef_A[i0, 0, i2] };
+; CHECK: [m, o, n] -> { Stmt_for_body6[i0, i1, i2] -> MemRef_A[3 + i0, i1, 7 + i2] };
+; CHECK: [m, o, n] -> { Stmt_for_body6[i0, i1, i2] -> MemRef_A[i0, 0, i2] };
 
 target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
 
diff --git a/polly/test/ScopInfo/loop_affine_bound_0.ll b/polly/test/ScopInfo/loop_affine_bound_0.ll
index 3e42cf2a0c2..1e409c1a210 100644
--- a/polly/test/ScopInfo/loop_affine_bound_0.ll
+++ b/polly/test/ScopInfo/loop_affine_bound_0.ll
@@ -55,7 +55,17 @@ return:                                           ; preds = %bb.nph8, %bb3, %ent
 ; CHECK:  Statements {
 ; CHECK:    Stmt_bb1
 ; CHECK:          Domain :=
-; CHECK:              [N, M] -> { Stmt_bb1[i0, i1] : i0 >= 0 and i0 <= 2 + 4N + 7M and i1 >= 0 and i1 <= 1 + 5N and N >= 0 };
+; CHECK:              [N, M] -> { Stmt_bb1[i0, i1] :
+; CHECK-DAG:             i0 >= 0
+; CHECK-DAG:          and
+; CHECK-DAG:             i0 <= 2 + 4N + 7M
+; CHECK-DAG:          and
+; CHECK-DAG:             i1 >= 0
+; CHECK-DAG:          and
+; CHECK-DAG:             i1 <= 1 + 5N
+; CHECK-DAG:          and
+; CHECK-DAG:             N >= 0
+; CHECK:               }
 ; CHECK:          Schedule :=
 ; CHECK:              [N, M] -> { Stmt_bb1[i0, i1] -> [i0, i1] };
 ; CHECK:          MustWriteAccess := [Reduction Type: NONE]
diff --git a/polly/test/ScopInfo/loop_affine_bound_1.ll b/polly/test/ScopInfo/loop_affine_bound_1.ll
index 09fb65226b8..0da94f79e62 100644
--- a/polly/test/ScopInfo/loop_affine_bound_1.ll
+++ b/polly/test/ScopInfo/loop_affine_bound_1.ll
@@ -23,12 +23,12 @@ bb1:                                              ; preds = %bb2.preheader, %bb1
   %scevgep = getelementptr [128 x i64], [128 x i64]* %a, i64 %indvar, i64 %tmp10 ; <i64*> [#uses=1]
   store i64 0, i64* %scevgep, align 8
   %indvar.next = add i64 %indvar, 1               ; <i64> [#uses=2]
-  %exitcond = icmp eq i64 %indvar.next, %tmp9     ; <i1> [#uses=1]
+  %exitcond = icmp sge i64 %indvar.next, %tmp9     ; <i1> [#uses=1]
   br i1 %exitcond, label %bb3, label %bb1
 
 bb3:                                              ; preds = %bb2.preheader, %bb1
   %5 = add i64 %8, 1                              ; <i64> [#uses=2]
-  %exitcond14 = icmp eq i64 %5, %tmp13            ; <i1> [#uses=1]
+  %exitcond14 = icmp sge i64 %5, %tmp13            ; <i1> [#uses=1]
   br i1 %exitcond14, label %return, label %bb2.preheader
 
 bb.nph8:                                          ; preds = %entry
@@ -54,7 +54,17 @@ return:                                           ; preds = %bb3, %entry
 ; CHECK: Statements {
 ; CHECK:   Stmt_bb1
 ; CHECK:         Domain :=
-; CHECK:             [N, M] -> { Stmt_bb1[i0, i1] : i0 >= 0 and i0 <= 2 + 4N + 7M and i1 >= 0 and i1 <= 1 + 5N - i0 and i0 <= 1 + 5N };
+; CHECK:             [N, M] -> { Stmt_bb1[i0, i1] :
+; CHECK-DAG:             i0 >= 0
+; CHECK-DAG:          and
+; CHECK-DAG:             i0 <= 2 + 4N + 7M
+; CHECK-DAG:          and
+; CHECK-DAG:             i1 >= 0
+; CHECK-DAG:          and
+; CHECK-DAG:             i1 <= 1 + 5N - i0
+; CHECK-DAG:          and
+; CHECK-DAG:             i0 <= 1 + 5N
+; CHECK:               }
 ; CHECK:         Schedule :=
 ; CHECK:             [N, M] -> { Stmt_bb1[i0, i1] -> [i0, i1] };
 ; CHECK:         MustWriteAccess := [Reduction Type: NONE]
diff --git a/polly/test/ScopInfo/loop_affine_bound_2.ll b/polly/test/ScopInfo/loop_affine_bound_2.ll
index 5ba94fdde05..41f67138d1b 100644
--- a/polly/test/ScopInfo/loop_affine_bound_2.ll
+++ b/polly/test/ScopInfo/loop_affine_bound_2.ll
@@ -65,9 +65,19 @@ return:                                           ; preds = %bb3, %entry
 ; CHECK: Statements {
 ; CHECK:   Stmt_bb1
 ; CHECK:         Domain :=
-; CHECK:             [N, M] -> { Stmt_bb1[i0, i1] : i0 >= 0 and i0 <= 2 + 4N + 7M and i1 >= 0 and i1 <= 10 + 5N - 6M - 4i0 and 4i0 <= 10 + 5N - 6M };
+; CHECK:             [N, M] -> { Stmt_bb1[i0, i1] :
+; CHECK-DAG:                  i0 >= 0
+; CHECK-DAG:                and
+; CHECK-DAG:                  i0 <= 2 + 4N + 7M
+; CHECK-DAG:                and
+; CHECK-DAG:                  i1 >= 0
+; CHECK-DAG:                and
+; CHECK-DAG:                  i1 <= 10 + 5N - 6M - 4i0
+; CHECK-DAG:                and
+; CHECK-DAG:                  4i0 <= 10 + 5N - 6M
+; CHECK-DAG:                }
 ; CHECK:         Schedule :=
-; CHECK:             [N, M] -> { Stmt_bb1[i0, i1] -> [i0, i1] };
+; CHECK:             [N, M] -> { Stmt_bb1[i0, i1] -> [i0, i1]
 ; CHECK:         MustWriteAccess := [Reduction Type: NONE]
 ; CHECK:             [N, M] -> { Stmt_bb1[i0, i1] -> MemRef_a[-1152 + 768M + 897i0 + 128i1] };
 ; CHECK: }
diff --git a/polly/test/ScopInfo/multidim_2d-diagonal-matrix.ll b/polly/test/ScopInfo/multidim_2d-diagonal-matrix.ll
index 2aa12ceef86..e99c5633aca 100644
--- a/polly/test/ScopInfo/multidim_2d-diagonal-matrix.ll
+++ b/polly/test/ScopInfo/multidim_2d-diagonal-matrix.ll
@@ -15,8 +15,6 @@ target datalayout = "e-p:64:64:64-i1:8:8-i8:8:8-i16:16:16-i32:32:32-i64:64:64-f3
 ; CHECK: p0: %n
 ; CHECK-NOT: p1
 
-; CHECK: Domain :=
-; CHECK:   [n] -> { Stmt_for_i[i0] : i0 >= 0 and i0 <= -1 + n };
 ; CHECK: Schedule :=
 ; CHECK:   [n] -> { Stmt_for_i[i0] -> [i0] };
 ; CHECK: MustWriteAccess :=
diff --git a/polly/test/ScopInfo/multidim_2d_outer_parametric_offset.ll b/polly/test/ScopInfo/multidim_2d_outer_parametric_offset.ll
index 609eeacad5f..11113e4a6d4 100644
--- a/polly/test/ScopInfo/multidim_2d_outer_parametric_offset.ll
+++ b/polly/test/ScopInfo/multidim_2d_outer_parametric_offset.ll
@@ -16,7 +16,15 @@ target datalayout = "e-p:64:64:64-i1:8:8-i8:8:8-i16:16:16-i32:32:32-i64:64:64-f3
 ; CHECK:  Statements {
 ; CHECK:    Stmt_for_j
 ; CHECK:          Domain :=
-; CHECK:              [m, p] -> { Stmt_for_j[i0, i1] : i0 >= 0 and i0 <= 99 and i1 >= 0 and i1 <= -1 + m };
+; CHECK:              [m, p] -> { Stmt_for_j[i0, i1] :
+; CHECK-DAG:             i0 >= 0
+; CHECK-DAG:          and
+; CHECK-DAG:             i0 <= 99
+; CHECK-DAG:          and
+; CHECK-DAG:             i1 >= 0
+; CHECK-DAG:          and
+; CHECK-DAG:             i1 <= -1 + m
+; CHECK:              }
 ; CHECK:          Schedule :=
 ; CHECK:              [m, p] -> { Stmt_for_j[i0, i1] -> [i0, i1] };
 ; CHECK:          MustWriteAccess := [Reduction Type: NONE]
diff --git a/polly/test/ScopInfo/multidim_2d_parametric_array_static_loop_bounds.ll b/polly/test/ScopInfo/multidim_2d_parametric_array_static_loop_bounds.ll
index 48db6b3a4a6..70285c37e39 100644
--- a/polly/test/ScopInfo/multidim_2d_parametric_array_static_loop_bounds.ll
+++ b/polly/test/ScopInfo/multidim_2d_parametric_array_static_loop_bounds.ll
@@ -14,7 +14,15 @@ target datalayout = "e-p:64:64:64-i1:8:8-i8:8:8-i16:16:16-i32:32:32-i64:64:64-f3
 ; CHECK: Statements {
 ; CHECK:   Stmt_for_j
 ; CHECK:         Domain :=
-; CHECK:             [m] -> { Stmt_for_j[i0, i1] : i0 >= 0 and i0 <= 99 and i1 >= 0 and i1 <= 149 };
+; CHECK:             [m] -> { Stmt_for_j[i0, i1]
+; CHECK-DAG:             i0 >= 0
+; CHECK-DAG:          and
+; CHECK-DAG:             i0 <= 99
+; CHECK-DAG:          and
+; CHECK-DAG:             i1 >= 0
+; CHECK-DAG:          and
+; CHECK-DAG:             i1 <= 149
+; CHECK:              }
 ; CHECK:         Schedule :=
 ; CHECK:             [m] -> { Stmt_for_j[i0, i1] -> [i0, i1] };
 ; CHECK:         MustWriteAccess := [Reduction Type: NONE]
diff --git a/polly/test/ScopInfo/multidim_3d_parametric_array_static_loop_bounds.ll b/polly/test/ScopInfo/multidim_3d_parametric_array_static_loop_bounds.ll
index 6ff616d5e39..e42aa73886c 100644
--- a/polly/test/ScopInfo/multidim_3d_parametric_array_static_loop_bounds.ll
+++ b/polly/test/ScopInfo/multidim_3d_parametric_array_static_loop_bounds.ll
@@ -20,7 +20,19 @@ target datalayout = "e-p:64:64:64-i1:8:8-i8:8:8-i16:16:16-i32:32:32-i64:64:64-f3
 ; CHECK:   Statements {
 ; CHECK:     Stmt_for_k
 ; CHECK:           Domain :=
-; CHECK:               [m, o] -> { Stmt_for_k[i0, i1, i2] : i0 >= 0 and i0 <= 99 and i1 >= 0 and i1 <= 149 and i2 >= 0 and i2 <= 199 };
+; CHECK:               [m, o] -> { Stmt_for_k[i0, i1, i2] :
+; CHECK-DAG:             i0 >= 0
+; CHECK-DAG:          and
+; CHECK-DAG:             i0 <= 99
+; CHECK-DAG:          and
+; CHECK-DAG:             i1 >= 0
+; CHECK-DAG:          and
+; CHECK-DAG:             i1 <= 149
+; CHECK-DAG:          and
+; CHECK-DAG:             i2 >= 0
+; CHECK-DAG:          and
+; CHECK-DAG:             i2 <= 199
+; CHECK:              }
 ; CHECK:           Schedule :=
 ; CHECK:               [m, o] -> { Stmt_for_k[i0, i1, i2] -> [i0, i1, i2] };
 ; CHECK:           MustWriteAccess := [Reduction Type: NONE]
diff --git a/polly/test/ScopInfo/multidim_ivs_and_integer_offsets_3d.ll b/polly/test/ScopInfo/multidim_ivs_and_integer_offsets_3d.ll
index bd414ce73d2..391d128a31f 100644
--- a/polly/test/ScopInfo/multidim_ivs_and_integer_offsets_3d.ll
+++ b/polly/test/ScopInfo/multidim_ivs_and_integer_offsets_3d.ll
@@ -12,17 +12,29 @@ target datalayout = "e-p:64:64:64-i1:8:8-i8:8:8-i16:16:16-i32:32:32-i64:64:64-f3
 ; CHECK: Assumed Context:
 ; CHECK: {  :  }
 
-; CHECK: p0: %n
+; CHECK: p0: %o
 ; CHECK: p1: %m
-; CHECK: p2: %o
+; CHECK: p2: %n
 ; CHECK-NOT: p3
 
 ; CHECK: Domain
-; CHECK:   [n, m, o] -> { Stmt_for_k[i0, i1, i2] : i0 >= 0 and i0 <= -4 + n and i1 >= 0 and i1 <= -5 + m and i2 >= 0 and i2 <= -8 + o };
+; CHECK:   [o, m, n] -> { Stmt_for_k[i0, i1, i2] :
+; CHECK-DAG:             i0 >= 0
+; CHECK-DAG:          and
+; CHECK-DAG:             i0 <= -4 + n
+; CHECK-DAG:          and
+; CHECK-DAG:             i1 >= 0
+; CHECK-DAG:          and
+; CHECK-DAG:             i1 <= -5 + m
+; CHECK-DAG:          and
+; CHECK-DAG:             i2 >= 0
+; CHECK-DAG:          and
+; CHECK-DAG:             i2 <= -8 + o
+; CHECK:              }
 ; CHECK: Schedule
-; CHECK:   [n, m, o] -> { Stmt_for_k[i0, i1, i2] -> [i0, i1, i2] };
+; CHECK:   [o, m, n] -> { Stmt_for_k[i0, i1, i2] -> [i0, i1, i2] };
 ; CHECK: MustWriteAccess
-; CHECK:   [n, m, o] -> { Stmt_for_k[i0, i1, i2] -> MemRef_A[3 + i0, i1, 7 + i2] };
+; CHECK:   [o, m, n] -> { Stmt_for_k[i0, i1, i2] -> MemRef_A[3 + i0, i1, 7 + i2] };
 
 define void @foo(i64 %n, i64 %m, i64 %o, double* %A) {
 entry:
diff --git a/polly/test/ScopInfo/multidim_ivs_and_parameteric_offsets_3d.ll b/polly/test/ScopInfo/multidim_ivs_and_parameteric_offsets_3d.ll
index cb442b30ba5..b917557a3cf 100644
--- a/polly/test/ScopInfo/multidim_ivs_and_parameteric_offsets_3d.ll
+++ b/polly/test/ScopInfo/multidim_ivs_and_parameteric_offsets_3d.ll
@@ -14,22 +14,34 @@ target datalayout = "e-p:64:64:64-i1:8:8-i8:8:8-i16:16:16-i32:32:32-i64:64:64-f3
 ;        (8 * %o)}<%for.j>,+,8}<%for.k>
 
 ; CHECK: Assumed Context:
-; CHECK: [n, m, o, p, q, r] -> { : (q <= 0 and q >= 1 - m and r <= -1 and r >= 1 - o) or (r = 0 and q <= 0 and q >= -m) or (r = -o and q <= 1 and q >= 1 - m) }
+; CHECK: [o, m, n, p, q, r] -> { : (q <= 0 and q >= 1 - m and r <= -1 and r >= 1 - o) or (r = 0 and q <= 0 and q >= -m) or (r = -o and q <= 1 and q >= 1 - m) }
 ;
-; CHECK: p0: %n
+; CHECK: p0: %o
 ; CHECK: p1: %m
-; CHECK: p2: %o
+; CHECK: p2: %n
 ; CHECK: p3: %p
 ; CHECK: p4: %q
 ; CHECK: p5: %r
 ; CHECK-NOT: p6
 ;
 ; CHECK: Domain
-; CHECK:   [n, m, o, p, q, r] -> { Stmt_for_k[i0, i1, i2] : i0 >= 0 and i0 <= -1 + n and i1 >= 0 and i1 <= -1 + m and i2 >= 0 and i2 <= -1 + o };
+; CHECK:   [o, m, n, p, q, r] -> { Stmt_for_k[i0, i1, i2] :
+; CHECK-DAG:             i0 >= 0
+; CHECK-DAG:          and
+; CHECK-DAG:             i0 <= -1 + n
+; CHECK-DAG:          and
+; CHECK-DAG:             i1 >= 0
+; CHECK-DAG:          and
+; CHECK-DAG:             i1 <= -1 + m
+; CHECK-DAG:          and
+; CHECK-DAG:             i2 >= 0
+; CHECK-DAG:          and
+; CHECK-DAG:             i2 <= -1 + o
+; CHECK:              }
 ; CHECK: Schedule
-; CHECK:   [n, m, o, p, q, r] -> { Stmt_for_k[i0, i1, i2] -> [i0, i1, i2] };
+; CHECK:   [o, m, n, p, q, r] -> { Stmt_for_k[i0, i1, i2] -> [i0, i1, i2] };
 ; CHECK: MustWriteAccess
-; CHECK: [n, m, o, p, q, r] -> { Stmt_for_k[i0, i1, i2] -> MemRef_A[-1 + p + i0, -1 + m + q + i1, o + r + i2] : i1 <= -q and i2 <= -1 - r; Stmt_for_k[i0, i1, i2] -> MemRef_A[p + i0, -1 + q + i1, o + r + i2] : i1 >= 1 - q and i2 <= -1 - r; Stmt_for_k[i0, i1, i2] -> MemRef_A[-1 + p + i0, m + q + i1, r + i2] : i1 <= -1 - q and i2 >= -r; Stmt_for_k[i0, i1, i2] -> MemRef_A[p + i0, q + i1, r + i2] : i1 >= -q and i2 >= -r };
+; CHECK: [o, m, n, p, q, r] -> { Stmt_for_k[i0, i1, i2] -> MemRef_A[-1 + p + i0, -1 + m + q + i1, o + r + i2] : i1 <= -q and i2 <= -1 - r; Stmt_for_k[i0, i1, i2] -> MemRef_A[p + i0, -1 + q + i1, o + r + i2] : i1 >= 1 - q and i2 <= -1 - r; Stmt_for_k[i0, i1, i2] -> MemRef_A[-1 + p + i0, m + q + i1, r + i2] : i1 <= -1 - q and i2 >= -r; Stmt_for_k[i0, i1, i2] -> MemRef_A[p + i0, q + i1, r + i2] : i1 >= -q and i2 >= -r };
 
 
 define void @foo(i64 %n, i64 %m, i64 %o, double* %A, i64 %p, i64 %q, i64 %r) {
diff --git a/polly/test/ScopInfo/multidim_nested_start_integer.ll b/polly/test/ScopInfo/multidim_nested_start_integer.ll
index 5bde3dfb457..69fd88d34cb 100644
--- a/polly/test/ScopInfo/multidim_nested_start_integer.ll
+++ b/polly/test/ScopInfo/multidim_nested_start_integer.ll
@@ -10,16 +10,28 @@ target datalayout = "e-p:64:64:64-i1:8:8-i8:8:8-i16:16:16-i32:32:32-i64:64:64-f3
 ;
 ; CHECK: Assumed Context:
 ; CHECK:   {  :  }
-; CHECK: p0: %n
+; CHECK: p0: %o
 ; CHECK: p1: %m
-; CHECK: p2: %o
+; CHECK: p2: %n
 ; CHECK-NOT: p3
 ; CHECK: Domain
-; CHECK:   [n, m, o] -> { Stmt_for_k[i0, i1, i2] : i0 >= 0 and i0 <= -4 + n and i1 >= 0 and i1 <= -5 + m and i2 >= 0 and i2 <= -8 + o };
+; CHECK:   [o, m, n] -> { Stmt_for_k[i0, i1, i2] :
+; CHECK-DAG:             i0 >= 0
+; CHECK-DAG:          and
+; CHECK-DAG:             i0 <= -4 + n
+; CHECK-DAG:          and
+; CHECK-DAG:             i1 >= 0
+; CHECK-DAG:          and
+; CHECK-DAG:             i1 <= -5 + m
+; CHECK-DAG:          and
+; CHECK-DAG:             i2 >= 0
+; CHECK-DAG:          and
+; CHECK-DAG:             i2 <= -8 + o
+; CHECK:              }
 ; CHECK: Schedule
-; CHECK:   [n, m, o] -> { Stmt_for_k[i0, i1, i2] -> [i0, i1, i2] };
+; CHECK:   [o, m, n] -> { Stmt_for_k[i0, i1, i2] -> [i0, i1, i2] };
 ; CHECK: MustWriteAccess
-; CHECK:   [n, m, o] -> { Stmt_for_k[i0, i1, i2] -> MemRef_A[3 + i0, i1, 7 + i2] };
+; CHECK:   [o, m, n] -> { Stmt_for_k[i0, i1, i2] -> MemRef_A[3 + i0, i1, 7 + i2] };
 
 define void @foo(i64 %n, i64 %m, i64 %o, double* %A) {
 entry:
diff --git a/polly/test/ScopInfo/multidim_nested_start_share_parameter.ll b/polly/test/ScopInfo/multidim_nested_start_share_parameter.ll
index 32c193e5b43..4a2baebdecc 100644
--- a/polly/test/ScopInfo/multidim_nested_start_share_parameter.ll
+++ b/polly/test/ScopInfo/multidim_nested_start_share_parameter.ll
@@ -13,13 +13,13 @@ target datalayout = "e-p:64:64:64-i1:8:8-i8:8:8-i16:16:16-i32:32:32-i64:64:64-f3
 ;
 ; CHECK: Assumed Context:
 ; CHECK:   {  :  }
-; CHECK: p0: %n
+; CHECK: p0: %o
 ; CHECK: p1: %m
-; CHECK: p2: %o
+; CHECK: p2: %n
 ; CHECK-NOT: p3
 ;
-; CHECK:   [n, m, o] -> { Stmt_for_k[i0, i1, i2] -> MemRef_A[3 + i0, 10 + i1, 7 + i2] };
-; CHECK:   [n, m, o] -> { Stmt_for_k[i0, i1, i2] -> MemRef_A[13 + i0, i1, 17 + i2] };
+; CHECK:   [o, m, n] -> { Stmt_for_k[i0, i1, i2] -> MemRef_A[3 + i0, 10 + i1, 7 + i2] };
+; CHECK:   [o, m, n] -> { Stmt_for_k[i0, i1, i2] -> MemRef_A[13 + i0, i1, 17 + i2] };
 
 define void @foo(i64 %n, i64 %m, i64 %o, double* %A) {
 entry:
diff --git a/polly/test/ScopInfo/multidim_only_ivs_2d.ll b/polly/test/ScopInfo/multidim_only_ivs_2d.ll
index b2753107bb9..f2bc6672da1 100644
--- a/polly/test/ScopInfo/multidim_only_ivs_2d.ll
+++ b/polly/test/ScopInfo/multidim_only_ivs_2d.ll
@@ -10,17 +10,25 @@ target datalayout = "e-p:64:64:64-i1:8:8-i8:8:8-i16:16:16-i32:32:32-i64:64:64-f3
 ; }
 
 ; CHECK: Assumed Context:
-; CHECK:   [n, m] -> {  :  }
-; CHECK: p0: %n
-; CHECK: p1: %m
+; CHECK:   [m, n] -> {  :  }
+; CHECK: p0: %m
+; CHECK: p1: %n
 ; CHECK-NOT: p3
 
 ; CHECK: Domain
-; CHECK:   [n, m] -> { Stmt_for_j[i0, i1] : i0 >= 0 and i0 <= -1 + n and i1 >= 0 and i1 <= -1 + m };
+; CHECK:   [m, n] -> { Stmt_for_j[i0, i1] :
+; CHECK-DAG:             i0 >= 0
+; CHECK-DAG:          and
+; CHECK-DAG:             i0 <= -1 + n
+; CHECK-DAG:          and
+; CHECK-DAG:             i1 >= 0
+; CHECK-DAG:          and
+; CHECK-DAG:             i1 <= -1 + m
+; CHECK:              }
 ; CHECK: Schedule
-; CHECK:   [n, m] -> { Stmt_for_j[i0, i1] -> [i0, i1] };
+; CHECK:   [m, n] -> { Stmt_for_j[i0, i1] -> [i0, i1] };
 ; CHECK: MustWriteAccess
-; CHECK:   [n, m] -> { Stmt_for_j[i0, i1] -> MemRef_A[i0, i1] };
+; CHECK:   [m, n] -> { Stmt_for_j[i0, i1] -> MemRef_A[i0, i1] };
 
 define void @foo(i64 %n, i64 %m, double* %A) {
 entry:
diff --git a/polly/test/ScopInfo/multidim_only_ivs_3d.ll b/polly/test/ScopInfo/multidim_only_ivs_3d.ll
index e2806ac572f..9bdf3f4cfb6 100644
--- a/polly/test/ScopInfo/multidim_only_ivs_3d.ll
+++ b/polly/test/ScopInfo/multidim_only_ivs_3d.ll
@@ -10,18 +10,30 @@ target datalayout = "e-p:64:64:64-i1:8:8-i8:8:8-i16:16:16-i32:32:32-i64:64:64-f3
 ; }
 
 ; CHECK: Assumed Context:
-; CHECK:   [n, m, o] -> {  :  }
-; CHECK: p0: %n
+; CHECK:   [o, m, n] -> {  :  }
+; CHECK: p0: %o
 ; CHECK: p1: %m
-; CHECK: p2: %o
+; CHECK: p2: %n
 ; CHECK-NOT: p3
 ;
 ; CHECK: Domain
-; CHECK:   [n, m, o] -> { Stmt_for_k[i0, i1, i2] : i0 >= 0 and i0 <= -1 + n and i1 >= 0 and i1 <= -1 + m and i2 >= 0 and i2 <= -1 + o };
+; CHECK:   [o, m, n] -> { Stmt_for_k[i0, i1, i2] :
+; CHECK-DAG:             i0 >= 0
+; CHECK-DAG:          and
+; CHECK-DAG:             i0 <= -1 + n
+; CHECK-DAG:          and
+; CHECK-DAG:             i1 >= 0
+; CHECK-DAG:          and
+; CHECK-DAG:             i1 <= -1 + m
+; CHECK-DAG:          and
+; CHECK-DAG:             i2 >= 0
+; CHECK-DAG:          and
+; CHECK-DAG:             i2 <= -1 + o
+; CHECK:              }
 ; CHECK: Schedule
-; CHECK:   [n, m, o] -> { Stmt_for_k[i0, i1, i2] -> [i0, i1, i2] };
+; CHECK:   [o, m, n] -> { Stmt_for_k[i0, i1, i2] -> [i0, i1, i2] };
 ; CHECK: WriteAccess
-; CHECK:   [n, m, o] -> { Stmt_for_k[i0, i1, i2] -> MemRef_A[i0, i1, i2] };
+; CHECK:   [o, m, n] -> { Stmt_for_k[i0, i1, i2] -> MemRef_A[i0, i1, i2] };
 
 define void @foo(i64 %n, i64 %m, i64 %o, double* %A) {
 entry:
diff --git a/polly/test/ScopInfo/multidim_only_ivs_3d_cast.ll b/polly/test/ScopInfo/multidim_only_ivs_3d_cast.ll
index 38390c20106..482c67d8769 100644
--- a/polly/test/ScopInfo/multidim_only_ivs_3d_cast.ll
+++ b/polly/test/ScopInfo/multidim_only_ivs_3d_cast.ll
@@ -13,13 +13,13 @@
 ; correctness issue, but could be improved.
 
 ; CHECK: Assumed Context:
-; CHECK:  [n, m, o, p_3, p_4] -> { :
+; CHECK:  [o, m, n, p_3, p_4] -> { :
 ; CHECK-DAG: p_3 >= m
 ; CHECK-DAG: p_4 >= o
 ; CHECK:  }
-; CHECK: p0: %n
+; CHECK: p0: %o
 ; CHECK: p1: %m
-; CHECK: p2: %o
+; CHECK: p2: %n
 ; CHECK: p3: (zext i32 %m to i64)
 ; CHECK: p4: (zext i32 %o to i64)
 ; CHECK-NOT: p5
@@ -33,11 +33,23 @@
 
 
 ; CHECK: Domain
-; CHECK:   [n, m, o, p_3, p_4] -> { Stmt_for_k[i0, i1, i2] : i0 >= 0 and i0 <= -1 + n and i1 >= 0 and i1 <= -1 + m and i2 >= 0 and i2 <= -1 + o };
+; CHECK:   [o, m, n, p_3, p_4] -> { Stmt_for_k[i0, i1, i2] :
+; CHECK-DAG:             i0 >= 0
+; CHECK-DAG:          and
+; CHECK-DAG:             i0 <= -1 + n
+; CHECK-DAG:          and
+; CHECK-DAG:             i1 >= 0
+; CHECK-DAG:          and
+; CHECK-DAG:             i1 <= -1 + m
+; CHECK-DAG:          and
+; CHECK-DAG:             i2 >= 0
+; CHECK-DAG:          and
+; CHECK-DAG:             i2 <= -1 + o
+; CHECK:              }
 ; CHECK: Schedule
-; CHECK:   [n, m, o, p_3, p_4] -> { Stmt_for_k[i0, i1, i2] -> [i0, i1, i2] };
+; CHECK:   [o, m, n, p_3, p_4] -> { Stmt_for_k[i0, i1, i2] -> [i0, i1, i2] };
 ; CHECK: WriteAccess
-; CHECK:   [n, m, o, p_3, p_4] -> { Stmt_for_k[i0, i1, i2] -> MemRef_A[i0, i1, i2] };
+; CHECK:   [o, m, n, p_3, p_4] -> { Stmt_for_k[i0, i1, i2] -> MemRef_A[i0, i1, i2] };
 
 target datalayout = "e-p:64:64:64-i1:8:8-i8:8:8-i16:16:16-i32:32:32-i64:64:64-f32:32:32-f64:64:64-v64:64:64-v128:128:128-a0:0:64-s0:64:64-f80:128:128-n8:16:32:64-S128"
 
diff --git a/polly/test/ScopInfo/multidim_only_ivs_3d_reverse.ll b/polly/test/ScopInfo/multidim_only_ivs_3d_reverse.ll
index 90fbda37479..e74f6487fc6 100644
--- a/polly/test/ScopInfo/multidim_only_ivs_3d_reverse.ll
+++ b/polly/test/ScopInfo/multidim_only_ivs_3d_reverse.ll
@@ -16,17 +16,29 @@ target datalayout = "e-p:64:64:64-i1:8:8-i8:8:8-i16:16:16-i32:32:32-i64:64:64-f3
 
 ; CHECK: Assumed Context:
 ; CHECK:   {  :  }
-; CHECK: p0: %n
+; CHECK: p0: %m
 ; CHECK: p1: %o
-; CHECK: p2: %m
+; CHECK: p2: %n
 ; CHECK-NOT: p3
 ;
 ; CHECK: Domain
-; CHECK:  [n, o, m] -> { Stmt_for_j[i0, i1, i2] : i0 >= 0 and i0 <= -1 + n and i1 >= 0 and i1 <= -1 + o and i2 >= 0 and i2 <= -1 + m };
+; CHECK:  [m, o, n] -> { Stmt_for_j[i0, i1, i2] :
+; CHECK-DAG:             i0 >= 0
+; CHECK-DAG:          and
+; CHECK-DAG:             i0 <= -1 + n
+; CHECK-DAG:          and
+; CHECK-DAG:             i1 >= 0
+; CHECK-DAG:          and
+; CHECK-DAG:             i1 <= -1 + o
+; CHECK-DAG:          and
+; CHECK-DAG:             i2 >= 0
+; CHECK-DAG:          and
+; CHECK-DAG:             i2 <= -1 + m
+; CHECK:              }
 ; CHECK: Schedule
-; CHECK:   [n, o, m] -> { Stmt_for_j[i0, i1, i2] -> [i0, i1, i2] };
+; CHECK:   [m, o, n] -> { Stmt_for_j[i0, i1, i2] -> [i0, i1, i2] };
 ; CHECK: WriteAccess
-; CHECK:   [n, o, m] -> { Stmt_for_j[i0, i1, i2] -> MemRef_A[i0, i2, i1] };
+; CHECK:   [m, o, n] -> { Stmt_for_j[i0, i1, i2] -> MemRef_A[i0, i2, i1] };
 
 define void @foo(i64 %n, i64 %m, i64 %o, double* %A) {
 entry:
diff --git a/polly/test/ScopInfo/non_affine_region_1.ll b/polly/test/ScopInfo/non_affine_region_1.ll
index d86422138f5..0af44cd7351 100644
--- a/polly/test/ScopInfo/non_affine_region_1.ll
+++ b/polly/test/ScopInfo/non_affine_region_1.ll
@@ -30,7 +30,11 @@
 ; CHECK:                 [b] -> { Stmt_bb8[i0] -> MemRef_x_1__phi[] };
 ; CHECK:       Stmt_bb10__TO__bb18
 ; CHECK-NEXT:        Domain :=
-; CHECK-NEXT:            [b] -> { Stmt_bb10__TO__bb18[i0] : i0 >= 0 and i0 <= 1023 };
+; CHECK-NEXT:            [b] -> { Stmt_bb10__TO__bb18[i0] :
+; CHECK-DAG:               i0 >= 0
+; CHECK-DAG:             and
+; CHECK-DAG:               i0 <= 1023
+; CHECK:                };
 ; CHECK-NEXT:        Schedule :=
 ; CHECK-NEXT:            [b] -> { Stmt_bb10__TO__bb18[i0] -> [i0, 3] };
 ; CHECK-NEXT:        ReadAccess := [Reduction Type: NONE] [Scalar: 1]
diff --git a/polly/test/ScopInfo/non_affine_region_2.ll b/polly/test/ScopInfo/non_affine_region_2.ll
index fd39cafa0bd..93921dce863 100644
--- a/polly/test/ScopInfo/non_affine_region_2.ll
+++ b/polly/test/ScopInfo/non_affine_region_2.ll
@@ -22,7 +22,11 @@
 ; CHECK: Region: %bb2---%bb21
 ; CHECK:   Stmt_bb3__TO__bb18
 ; CHECK:         Domain :=
-; CHECK:             { Stmt_bb3__TO__bb18[i0] : i0 >= 0 and i0 <= 1023 };
+; CHECK:             { Stmt_bb3__TO__bb18[i0] :
+; CHECK-DAG:               i0 >= 0
+; CHECK-DAG:             and
+; CHECK-DAG:               i0 <= 1023
+; CHECK:                };
 ; CHECK:         Schedule :=
 ; CHECK:             { Stmt_bb3__TO__bb18[i0] -> [i0, 0] };
 ; CHECK-NOT:         { Stmt_bb3__TO__bb18[i0] -> MemRef_x_0[] };
@@ -41,7 +45,11 @@
 ; CHECK-NOT:         { Stmt_bb3__TO__bb18[i0] -> MemRef_x_1[] };
 ; CHECK:   Stmt_bb18
 ; CHECK:         Domain :=
-; CHECK:             { Stmt_bb18[i0] : i0 >= 0 and i0 <= 1023 };
+; CHECK:             { Stmt_bb18[i0] :
+; CHECK-DAG:               i0 >= 0
+; CHECK-DAG:             and
+; CHECK-DAG:               i0 <= 1023
+; CHECK:                };
 ; CHECK:         Schedule :=
 ; CHECK:             { Stmt_bb18[i0] -> [i0, 1] };
 ; CHECK:         ReadAccess := [Reduction Type: NONE] [Scalar: 1]
diff --git a/polly/test/ScopInfo/non_affine_region_3.ll b/polly/test/ScopInfo/non_affine_region_3.ll
index ad359cd546b..9bc29840207 100644
--- a/polly/test/ScopInfo/non_affine_region_3.ll
+++ b/polly/test/ScopInfo/non_affine_region_3.ll
@@ -22,7 +22,11 @@
 ; CHECK: Region: %bb2---%bb21
 ; CHECK:   Stmt_bb3__TO__bb18
 ; CHECK:         Domain :=
-; CHECK:             { Stmt_bb3__TO__bb18[i0] : i0 >= 0 and i0 <= 1023 };
+; CHECK:             { Stmt_bb3__TO__bb18[i0] :
+; CHECK-DAG:           i0 >= 0
+; CHECK-DAG:         and
+; CHECK-DAG:           i0 <= 1023
+; CHECK:              }
 ; CHECK:         Schedule :=
 ; CHECK:             { Stmt_bb3__TO__bb18[i0] -> [i0, 0] };
 ; CHECK:         ReadAccess := [Reduction Type: NONE] [Scalar: 0]
@@ -37,7 +41,11 @@
 ; CHECK:             { Stmt_bb3__TO__bb18[i0] -> MemRef_x_2__phi[] };
 ; CHECK:   Stmt_bb18
 ; CHECK:         Domain :=
-; CHECK:             { Stmt_bb18[i0] : i0 >= 0 and i0 <= 1023 };
+; CHECK:             { Stmt_bb18[i0] :
+; CHECK-DAG:           i0 >= 0
+; CHECK-DAG:         and
+; CHECK-DAG:           i0 <= 1023
+; CHECK:              }
 ; CHECK:         Schedule :=
 ; CHECK:             { Stmt_bb18[i0] -> [i0, 1] };
 ; CHECK:         ReadAccess := [Reduction Type: NONE] [Scalar: 1]
diff --git a/polly/test/ScopInfo/non_affine_region_4.ll b/polly/test/ScopInfo/non_affine_region_4.ll
index dcad02c7236..1497186608b 100644
--- a/polly/test/ScopInfo/non_affine_region_4.ll
+++ b/polly/test/ScopInfo/non_affine_region_4.ll
@@ -28,7 +28,11 @@
 ;
 ; CHECK:      Stmt_bb2__TO__bb7
 ; CHECK:            Domain :=
-; CHECK:                { Stmt_bb2__TO__bb7[i0] : i0 >= 0 and i0 <= 1023 };
+; CHECK:                { Stmt_bb2__TO__bb7[i0] :
+; CHECK-DAG:               i0 >= 0
+; CHECK-DAG:             and
+; CHECK-DAG:               i0 <= 1023
+; CHECK:                };
 ; CHECK:            Schedule :=
 ; CHECK:                { Stmt_bb2__TO__bb7[i0] -> [i0, 0] };
 ; CHECK:            ReadAccess := [Reduction Type: NONE] [Scalar: 0]
@@ -41,7 +45,11 @@
 ; CHECK:                { Stmt_bb2__TO__bb7[i0] -> MemRef_y__phi[] };
 ; CHECK:      Stmt_bb7
 ; CHECK:            Domain :=
-; CHECK:                { Stmt_bb7[i0] : i0 >= 0 and i0 <= 1023 };
+; CHECK:                { Stmt_bb7[i0] :
+; CHECK-DAG:               i0 >= 0
+; CHECK-DAG:             and
+; CHECK-DAG:               i0 <= 1023
+; CHECK:                };
 ; CHECK:            Schedule :=
 ; CHECK:                { Stmt_bb7[i0] -> [i0, 1] };
 ; CHECK:            ReadAccess := [Reduction Type: NONE] [Scalar: 1]
diff --git a/polly/test/ScopInfo/pointer-type-expressions.ll b/polly/test/ScopInfo/pointer-type-expressions.ll
index 6fe2b828fdf..cf25e4d6697 100644
--- a/polly/test/ScopInfo/pointer-type-expressions.ll
+++ b/polly/test/ScopInfo/pointer-type-expressions.ll
@@ -37,12 +37,12 @@ return:
 
 ; CHECK:  Stmt_store
 ; CHECK:        Domain :=
-; CHECK:            [N, P] -> { Stmt_store[i0] :
+; CHECK:            [P, N] -> { Stmt_store[i0] :
 ; CHECK:              (P <= -1 and i0 >= 0 and i0 <= -1 + N)
 ; CHECK:                or
 ; CHECK:              (P >= 1 and i0 >= 0 and i0 <= -1 + N)
 ; CHECK:                   };
 ; CHECK:        Schedule :=
-; CHECK:            [N, P] -> { Stmt_store[i0] -> [i0] : P <= -1 or P >= 1 };
+; CHECK:            [P, N] -> { Stmt_store[i0] -> [i0] : P <= -1 or P >= 1 };
 ; CHECK:        MustWriteAccess := [Reduction Type: NONE]
-; CHECK:            [N, P] -> { Stmt_store[i0] -> MemRef_a[i0] };
+; CHECK:            [P, N] -> { Stmt_store[i0] -> MemRef_a[i0] };
diff --git a/polly/test/ScopInfo/unsigned-condition.ll b/polly/test/ScopInfo/unsigned-condition.ll
index 759022e1701..eadffb4d3e4 100644
--- a/polly/test/ScopInfo/unsigned-condition.ll
+++ b/polly/test/ScopInfo/unsigned-condition.ll
@@ -37,10 +37,10 @@ return:
 
 ; CHECK:  Stmt_store
 ; CHECK:        Domain :=
-; CHECK:            [N, P] -> { Stmt_store[i0] :
+; CHECK:            [P, N] -> { Stmt_store[i0] :
 ; CHECK:              i0 >= 0 and i0 <= -1 + N and P >= 42
 ; CHECK:                   };
 ; CHECK:        Schedule :=
-; CHECK:            [N, P] -> { Stmt_store[i0] -> [i0] };
+; CHECK:            [P, N] -> { Stmt_store[i0] -> [i0] };
 ; CHECK:        MustWriteAccess := [Reduction Type: NONE]
-; CHECK:            [N, P] -> { Stmt_store[i0] -> MemRef_a[i0] };
+; CHECK:            [P, N] -> { Stmt_store[i0] -> MemRef_a[i0] };
diff --git a/polly/test/TempScop/nested-loops.ll b/polly/test/TempScop/nested-loops.ll
index e5b21818546..1c4e3447e30 100644
--- a/polly/test/TempScop/nested-loops.ll
+++ b/polly/test/TempScop/nested-loops.ll
@@ -29,4 +29,12 @@ return:
 
 ; CHECK: body
 ; CHECK:        Domain :=
-; CHECK:           { Stmt_body[i0, i1] : i0 >= 0 and i0 <= 2046 and i1 >= 0 and i1 <= 1022 }
+; CHECK:           { Stmt_body[i0, i1] :
+; CHECK-DAG:         i0 >= 0
+; CHECK-DAG:       and
+; CHECK-DAG:         i0 <= 2046
+; CHECK-DAG:       and
+; CHECK-DAG:         i1 >= 0
+; CHECK-DAG:       and
+; CHECK-DAG:         i1 <= 1022
+; CHECK:           }