Index: polly/trunk/include/polly/ScopInfo.h
===================================================================
--- polly/trunk/include/polly/ScopInfo.h
+++ polly/trunk/include/polly/ScopInfo.h
@@ -554,7 +554,6 @@
 
   /// 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 @@
   Scop(const Scop &) = delete;
   const Scop &operator=(const Scop &) = delete;
 
+  DominatorTree &DT;
   ScalarEvolution *SE;
 
   /// The underlying Region.
@@ -817,6 +817,9 @@
   /// @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 @@
   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 @@
   /// 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 @@
   __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 @@
   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.
Index: polly/trunk/include/polly/TempScopInfo.h
===================================================================
--- polly/trunk/include/polly/TempScopInfo.h
+++ polly/trunk/include/polly/TempScopInfo.h
@@ -118,9 +118,6 @@
 };
 
 //===---------------------------------------------------------------------===//
-/// 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 @@
 /// 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 @@
   // 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 @@
   /// @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 @@
   // 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 @@
   // 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);
Index: polly/trunk/lib/Analysis/ScopInfo.cpp
===================================================================
--- polly/trunk/lib/Analysis/ScopInfo.cpp
+++ polly/trunk/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 @@
   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 @@
     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 @@
   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 @@
   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 @@
 
   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 @@
   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 @@
   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 @@
 
 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 @@
   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 @@
   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 @@
 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 @@
   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 @@
     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(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)
Index: polly/trunk/lib/Analysis/TempScopInfo.cpp
===================================================================
--- polly/trunk/lib/Analysis/TempScopInfo.cpp
+++ polly/trunk/lib/Analysis/TempScopInfo.cpp
@@ -60,21 +60,6 @@
   // 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 @@
   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 @@
     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 @@
 }
 
 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 @@
 TempScopInfo::~TempScopInfo() { clear(); }
 
 void TempScopInfo::clear() {
-  BBConds.clear();
   AccFuncMap.clear();
   if (TempScopOfRegion)
     delete TempScopOfRegion;
@@ -527,9 +393,7 @@
                       "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",
Index: polly/trunk/test/DependenceInfo/reduction_simple_iv_debug_wrapped_dependences.ll
===================================================================
--- polly/trunk/test/DependenceInfo/reduction_simple_iv_debug_wrapped_dependences.ll
+++ polly/trunk/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 }
Index: polly/trunk/test/Isl/CodeGen/OpenMP/two-parallel-loops-reference-outer-indvar.ll
===================================================================
--- polly/trunk/test/Isl/CodeGen/OpenMP/two-parallel-loops-reference-outer-indvar.ll
+++ polly/trunk/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
Index: polly/trunk/test/Isl/CodeGen/if-conditions-in-vector-code.ll
===================================================================
--- polly/trunk/test/Isl/CodeGen/if-conditions-in-vector-code.ll
+++ polly/trunk/test/Isl/CodeGen/if-conditions-in-vector-code.ll
@@ -17,10 +17,10 @@
 
 ; 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: }
 
Index: polly/trunk/test/ScopInfo/20111108-Parameter-not-detected.ll
===================================================================
--- polly/trunk/test/ScopInfo/20111108-Parameter-not-detected.ll
+++ polly/trunk/test/ScopInfo/20111108-Parameter-not-detected.ll
@@ -54,5 +54,11 @@
 ; 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:          }
 
Index: polly/trunk/test/ScopInfo/NonAffine/non-affine-loop-condition-dependent-access_1.ll
===================================================================
--- polly/trunk/test/ScopInfo/NonAffine/non-affine-loop-condition-dependent-access_1.ll
+++ polly/trunk/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]
Index: polly/trunk/test/ScopInfo/NonAffine/non-affine-loop-condition-dependent-access_2.ll
===================================================================
--- polly/trunk/test/ScopInfo/NonAffine/non-affine-loop-condition-dependent-access_2.ll
+++ polly/trunk/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]
Index: polly/trunk/test/ScopInfo/NonAffine/non-affine-loop-condition-dependent-access_3.ll
===================================================================
--- polly/trunk/test/ScopInfo/NonAffine/non-affine-loop-condition-dependent-access_3.ll
+++ polly/trunk/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]
Index: polly/trunk/test/ScopInfo/NonAffine/non_affine_conditional_nested.ll
===================================================================
--- polly/trunk/test/ScopInfo/NonAffine/non_affine_conditional_nested.ll
+++ polly/trunk/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]
Index: polly/trunk/test/ScopInfo/NonAffine/non_affine_conditional_surrounding_affine_loop.ll
===================================================================
--- polly/trunk/test/ScopInfo/NonAffine/non_affine_conditional_surrounding_affine_loop.ll
+++ polly/trunk/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]
Index: polly/trunk/test/ScopInfo/NonAffine/non_affine_conditional_surrounding_non_affine_loop.ll
===================================================================
--- polly/trunk/test/ScopInfo/NonAffine/non_affine_conditional_surrounding_non_affine_loop.ll
+++ polly/trunk/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]
Index: polly/trunk/test/ScopInfo/NonAffine/non_affine_float_compare.ll
===================================================================
--- polly/trunk/test/ScopInfo/NonAffine/non_affine_float_compare.ll
+++ polly/trunk/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]
Index: polly/trunk/test/ScopInfo/NonAffine/non_affine_loop_condition.ll
===================================================================
--- polly/trunk/test/ScopInfo/NonAffine/non_affine_loop_condition.ll
+++ polly/trunk/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]
Index: polly/trunk/test/ScopInfo/NonAffine/non_affine_loop_used_later.ll
===================================================================
--- polly/trunk/test/ScopInfo/NonAffine/non_affine_loop_used_later.ll
+++ polly/trunk/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]
Index: polly/trunk/test/ScopInfo/NonAffine/non_affine_parametric_loop.ll
===================================================================
--- polly/trunk/test/ScopInfo/NonAffine/non_affine_parametric_loop.ll
+++ polly/trunk/test/ScopInfo/NonAffine/non_affine_parametric_loop.ll
@@ -26,8 +26,6 @@
 
 ; 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
Index: polly/trunk/test/ScopInfo/cfg_consequences.ll
===================================================================
--- polly/trunk/test/ScopInfo/cfg_consequences.ll
+++ polly/trunk/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
+}
Index: polly/trunk/test/ScopInfo/delinearize-together-all-data-refs.ll
===================================================================
--- polly/trunk/test/ScopInfo/delinearize-together-all-data-refs.ll
+++ polly/trunk/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"
 
Index: polly/trunk/test/ScopInfo/loop_affine_bound_0.ll
===================================================================
--- polly/trunk/test/ScopInfo/loop_affine_bound_0.ll
+++ polly/trunk/test/ScopInfo/loop_affine_bound_0.ll
@@ -55,7 +55,17 @@
 ; 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]
Index: polly/trunk/test/ScopInfo/loop_affine_bound_1.ll
===================================================================
--- polly/trunk/test/ScopInfo/loop_affine_bound_1.ll
+++ polly/trunk/test/ScopInfo/loop_affine_bound_1.ll
@@ -23,12 +23,12 @@
   %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 @@
 ; 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]
Index: polly/trunk/test/ScopInfo/loop_affine_bound_2.ll
===================================================================
--- polly/trunk/test/ScopInfo/loop_affine_bound_2.ll
+++ polly/trunk/test/ScopInfo/loop_affine_bound_2.ll
@@ -65,9 +65,19 @@
 ; 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: }
Index: polly/trunk/test/ScopInfo/multidim_2d-diagonal-matrix.ll
===================================================================
--- polly/trunk/test/ScopInfo/multidim_2d-diagonal-matrix.ll
+++ polly/trunk/test/ScopInfo/multidim_2d-diagonal-matrix.ll
@@ -15,8 +15,6 @@
 ; 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 :=
Index: polly/trunk/test/ScopInfo/multidim_2d_outer_parametric_offset.ll
===================================================================
--- polly/trunk/test/ScopInfo/multidim_2d_outer_parametric_offset.ll
+++ polly/trunk/test/ScopInfo/multidim_2d_outer_parametric_offset.ll
@@ -16,7 +16,15 @@
 ; 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]
Index: polly/trunk/test/ScopInfo/multidim_2d_parametric_array_static_loop_bounds.ll
===================================================================
--- polly/trunk/test/ScopInfo/multidim_2d_parametric_array_static_loop_bounds.ll
+++ polly/trunk/test/ScopInfo/multidim_2d_parametric_array_static_loop_bounds.ll
@@ -14,7 +14,15 @@
 ; 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]
Index: polly/trunk/test/ScopInfo/multidim_3d_parametric_array_static_loop_bounds.ll
===================================================================
--- polly/trunk/test/ScopInfo/multidim_3d_parametric_array_static_loop_bounds.ll
+++ polly/trunk/test/ScopInfo/multidim_3d_parametric_array_static_loop_bounds.ll
@@ -20,7 +20,19 @@
 ; 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]
Index: polly/trunk/test/ScopInfo/multidim_ivs_and_integer_offsets_3d.ll
===================================================================
--- polly/trunk/test/ScopInfo/multidim_ivs_and_integer_offsets_3d.ll
+++ polly/trunk/test/ScopInfo/multidim_ivs_and_integer_offsets_3d.ll
@@ -12,17 +12,29 @@
 ; 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:
Index: polly/trunk/test/ScopInfo/multidim_ivs_and_parameteric_offsets_3d.ll
===================================================================
--- polly/trunk/test/ScopInfo/multidim_ivs_and_parameteric_offsets_3d.ll
+++ polly/trunk/test/ScopInfo/multidim_ivs_and_parameteric_offsets_3d.ll
@@ -14,22 +14,34 @@
 ;        (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) {
Index: polly/trunk/test/ScopInfo/multidim_nested_start_integer.ll
===================================================================
--- polly/trunk/test/ScopInfo/multidim_nested_start_integer.ll
+++ polly/trunk/test/ScopInfo/multidim_nested_start_integer.ll
@@ -10,16 +10,28 @@
 ;
 ; 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:
Index: polly/trunk/test/ScopInfo/multidim_nested_start_share_parameter.ll
===================================================================
--- polly/trunk/test/ScopInfo/multidim_nested_start_share_parameter.ll
+++ polly/trunk/test/ScopInfo/multidim_nested_start_share_parameter.ll
@@ -13,13 +13,13 @@
 ;
 ; 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:
Index: polly/trunk/test/ScopInfo/multidim_only_ivs_2d.ll
===================================================================
--- polly/trunk/test/ScopInfo/multidim_only_ivs_2d.ll
+++ polly/trunk/test/ScopInfo/multidim_only_ivs_2d.ll
@@ -10,17 +10,25 @@
 ; }
 
 ; 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:
Index: polly/trunk/test/ScopInfo/multidim_only_ivs_3d.ll
===================================================================
--- polly/trunk/test/ScopInfo/multidim_only_ivs_3d.ll
+++ polly/trunk/test/ScopInfo/multidim_only_ivs_3d.ll
@@ -10,18 +10,30 @@
 ; }
 
 ; 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:
Index: polly/trunk/test/ScopInfo/multidim_only_ivs_3d_cast.ll
===================================================================
--- polly/trunk/test/ScopInfo/multidim_only_ivs_3d_cast.ll
+++ polly/trunk/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"
 
Index: polly/trunk/test/ScopInfo/multidim_only_ivs_3d_reverse.ll
===================================================================
--- polly/trunk/test/ScopInfo/multidim_only_ivs_3d_reverse.ll
+++ polly/trunk/test/ScopInfo/multidim_only_ivs_3d_reverse.ll
@@ -16,17 +16,29 @@
 
 ; 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:
Index: polly/trunk/test/ScopInfo/non_affine_region_1.ll
===================================================================
--- polly/trunk/test/ScopInfo/non_affine_region_1.ll
+++ polly/trunk/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]
Index: polly/trunk/test/ScopInfo/non_affine_region_2.ll
===================================================================
--- polly/trunk/test/ScopInfo/non_affine_region_2.ll
+++ polly/trunk/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]
Index: polly/trunk/test/ScopInfo/non_affine_region_3.ll
===================================================================
--- polly/trunk/test/ScopInfo/non_affine_region_3.ll
+++ polly/trunk/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]
Index: polly/trunk/test/ScopInfo/non_affine_region_4.ll
===================================================================
--- polly/trunk/test/ScopInfo/non_affine_region_4.ll
+++ polly/trunk/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]
Index: polly/trunk/test/ScopInfo/pointer-type-expressions.ll
===================================================================
--- polly/trunk/test/ScopInfo/pointer-type-expressions.ll
+++ polly/trunk/test/ScopInfo/pointer-type-expressions.ll
@@ -37,12 +37,12 @@
 
 ; 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] };
Index: polly/trunk/test/ScopInfo/unsigned-condition.ll
===================================================================
--- polly/trunk/test/ScopInfo/unsigned-condition.ll
+++ polly/trunk/test/ScopInfo/unsigned-condition.ll
@@ -37,10 +37,10 @@
 
 ; 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] };
Index: polly/trunk/test/TempScop/nested-loops.ll
===================================================================
--- polly/trunk/test/TempScop/nested-loops.ll
+++ polly/trunk/test/TempScop/nested-loops.ll
@@ -29,4 +29,12 @@
 
 ; 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:           }