Allow general loops with one latch

  As we do not rely on ScalarEvolution any more we do not need to get
  the backedge taken count. Additionally, our domain generation handles
  everything that is affine and has one latch and our ScopDetection will
  over-approximate everything else.

  This change will therefor allow loops with:
    - one latch
    - exiting conditions that are affine

  Additionally, it will not check for structured control flow anymore.
  Hence, loops and conditionals are not necessarily single entry single
  exit regions any more.

Differential Version: http://reviews.llvm.org/D12758

llvm-svn: 247289

19 files changed, 286 insertions, 228 deletions

diff --git a/polly/include/polly/ScopInfo.h b/polly/include/polly/ScopInfo.h
index 736e4cde167..0ec166235a9 100644
--- a/polly/include/polly/ScopInfo.h
+++ b/polly/include/polly/ScopInfo.h
@@ -589,12 +589,10 @@ public:
   const ScopStmt &operator=(const ScopStmt &) = delete;
 
   /// Create the ScopStmt from a BasicBlock.
-  ScopStmt(Scop &parent, TempScop &tempScop, BasicBlock &bb,
-           SmallVectorImpl<Loop *> &NestLoops);
+  ScopStmt(Scop &parent, TempScop &tempScop, BasicBlock &bb);
 
   /// Create an overapproximating ScopStmt for the region @p R.
-  ScopStmt(Scop &parent, TempScop &tempScop, Region &R,
-           SmallVectorImpl<Loop *> &NestLoops);
+  ScopStmt(Scop &parent, TempScop &tempScop, Region &R);
 
 private:
   /// Polyhedral description
@@ -653,7 +651,7 @@ private:
   /// @brief The isl AST build for the new generated AST.
   isl_ast_build *Build;
 
-  std::vector<Loop *> NestLoops;
+  SmallVector<Loop *, 4> NestLoops;
 
   std::string BaseName;
 
@@ -661,6 +659,9 @@ private:
   //@{
   void buildDomain();
 
+  /// @brief Fill NestLoops with loops surrounding this statement.
+  void collectSurroundingLoops();
+
   /// @brief Create the accesses for instructions in @p Block.
   ///
   /// @param tempScop       The template SCoP.
@@ -1084,35 +1085,17 @@ private:
   /// @param BB         The basic block we build the statement for (or null)
   /// @param R          The region we build the statement for (or null).
   /// @param tempScop   The temp SCoP we use as model.
-  /// @param NestLoops  A vector of all surrounding loops.
-  ScopStmt *addScopStmt(BasicBlock *BB, Region *R, TempScop &tempScop,
-                        SmallVectorImpl<Loop *> &NestLoops);
+  ScopStmt *addScopStmt(BasicBlock *BB, Region *R, TempScop &tempScop);
 
-  /// @brief Create the ScopStmt for a BasicBlock and return its schedule.
-  ///
-  /// Returns null if the BB is trivial and no stmt has been created.
+  /// @brief Build Schedule and ScopStmts from a given TempScop.
   ///
-  /// @param BB         The basic block we build the statement for.
-  /// @param tempScop   The temp SCoP we use as model.
-  /// @param NestLoops  A vector of all surrounding loops.
-  ///
-  /// @return The ScopStmt's schedule.
-  __isl_give isl_schedule *buildBBScopStmt(BasicBlock *BB, TempScop &tempScop,
-                                           SmallVectorImpl<Loop *> &NestLoops);
-
-  /// @brief Build Scop and ScopStmts from a given TempScop.
-  ///
-  /// @param TempScop  The temporary scop that is translated into an actual
-  ///                  scop.
-  /// @param CurRegion The subregion of the current scop that we are currently
-  ///                  translating.
-  /// @param NestLoop  The set of loops that surround the current subregion.
-  /// @param LI        The LoopInfo object.
-  /// @param SD        The ScopDetection object.
-  __isl_give isl_schedule *buildScop(TempScop &TempScop,
-                                     const Region &CurRegion,
-                                     SmallVectorImpl<Loop *> &NestLoops,
-                                     LoopInfo &LI, ScopDetection &SD);
+  /// @param R  The current region traversed.
+  /// @param TS The temporary scop that is translated into an actual scop.
+  /// @param LI The LoopInfo object.
+  /// @param SD The ScopDetection object.
+  void buildSchedule(
+      Region *R, TempScop &TS, LoopInfo &LI, ScopDetection &SD,
+      DenseMap<Loop *, std::pair<isl_schedule *, unsigned>> &LoopSchedules);
 
   /// @name Helper function for printing the Scop.
   ///
diff --git a/polly/lib/Analysis/ScopDetection.cpp b/polly/lib/Analysis/ScopDetection.cpp
index 6cc8f6a1a74..45a69cf09cf 100644
--- a/polly/lib/Analysis/ScopDetection.cpp
+++ b/polly/lib/Analysis/ScopDetection.cpp
@@ -363,16 +363,6 @@ bool ScopDetection::isValidCFG(BasicBlock &BB,
     }
   }
 
-  // Allow loop exit conditions.
-  Loop *L = LI->getLoopFor(&BB);
-  if (L && L->getExitingBlock() == &BB)
-    return true;
-
-  // Allow perfectly nested conditions.
-  Region *R = RI->getRegionFor(&BB);
-  if (R->getEntry() != &BB)
-    return invalid<ReportCondition>(Context, /*Assert=*/true, &BB);
-
   return true;
 }
 
@@ -709,66 +699,37 @@ bool ScopDetection::isValidInstruction(Instruction &Inst,
 
 bool ScopDetection::canUseISLTripCount(Loop *L,
                                        DetectionContext &Context) const {
-
-  Region &CurRegion = Context.CurRegion;
-
   // Ensure the loop has a single back edge.
   if (L->getNumBackEdges() != 1)
     return false;
 
-  // Ensure the loop has a single exiting block.
-  BasicBlock *ExitingBB = L->getExitingBlock();
-  if (!ExitingBB)
-    return false;
-
-  // Ensure the exiting block is terminated by a conditional branch.
-  BranchInst *Term = dyn_cast<BranchInst>(ExitingBB->getTerminator());
-  if (!Term || !Term->isConditional())
-    return false;
-
-  Value *Cond = Term->getCondition();
-
-  // If the terminating condition is an integer comparison, ensure that it is a
-  // comparison between a recurrence and an invariant value.
-  if (ICmpInst *I = dyn_cast<ICmpInst>(Cond)) {
-    const Value *Op0 = I->getOperand(0);
-    const Value *Op1 = I->getOperand(1);
-    const SCEV *LHS = SE->getSCEVAtScope(const_cast<Value *>(Op0), L);
-    const SCEV *RHS = SE->getSCEVAtScope(const_cast<Value *>(Op1), L);
-    if ((isa<SCEVAddRecExpr>(LHS) && !isInvariant(*Op1, CurRegion)) ||
-        (isa<SCEVAddRecExpr>(RHS) && !isInvariant(*Op0, CurRegion)))
+  // Ensure the loop has valid exiting blocks, otherwise we need to
+  // overapproximate it as a boxed loop.
+  SmallVector<BasicBlock *, 4> ExitingBlocks;
+  L->getExitingBlocks(ExitingBlocks);
+  for (BasicBlock *ExitingBB : ExitingBlocks) {
+    if (!isValidCFG(*ExitingBB, Context))
       return false;
   }
 
-  // If the terminating condition is not an integer comparison, ensure that it
-  // is a constant.
-  else if (!isa<ConstantInt>(Cond))
-    return false;
-
   // We can use ISL to compute the trip count of L.
   return true;
 }
 
 bool ScopDetection::isValidLoop(Loop *L, DetectionContext &Context) const {
-  // Is the loop count affine?
-  bool IsLoopCountAffine = false;
-  const SCEV *LoopCount = SE->getBackedgeTakenCount(L);
-  if (!isa<SCEVCouldNotCompute>(LoopCount))
-    IsLoopCountAffine = isAffineExpr(&Context.CurRegion, LoopCount, *SE);
-  else
-    IsLoopCountAffine = canUseISLTripCount(L, Context);
-  if (IsLoopCountAffine) {
+  if (canUseISLTripCount(L, Context)) {
     Context.hasAffineLoops = true;
     return true;
   }
 
-  if (AllowNonAffineSubRegions) {
+  if (AllowNonAffineSubLoops && AllowNonAffineSubRegions) {
     Region *R = RI->getRegionFor(L->getHeader());
     if (R->contains(L))
       if (addOverApproximatedRegion(R, Context))
         return true;
   }
 
+  const SCEV *LoopCount = SE->getBackedgeTakenCount(L);
   return invalid<ReportLoopBound>(Context, /*Assert=*/true, L, LoopCount);
 }
 
diff --git a/polly/lib/Analysis/ScopInfo.cpp b/polly/lib/Analysis/ScopInfo.cpp
index dd291539f3c..04cd6e9e341 100644
--- a/polly/lib/Analysis/ScopInfo.cpp
+++ b/polly/lib/Analysis/ScopInfo.cpp
@@ -30,6 +30,7 @@
 #include "llvm/ADT/STLExtras.h"
 #include "llvm/ADT/StringExtras.h"
 #include "llvm/ADT/PostOrderIterator.h"
+#include "llvm/Analysis/LoopIterator.h"
 #include "llvm/Analysis/AliasAnalysis.h"
 #include "llvm/Analysis/LoopInfo.h"
 #include "llvm/Analysis/RegionIterator.h"
@@ -891,6 +892,12 @@ buildConditionSets(Scop &S, BranchInst *BI, Loop *L, __isl_keep isl_set *Domain,
     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);
+
+    for (unsigned u = 0, e = isl_set_n_dim(Domain); u < e; u++) {
+      isl_id *DimId = isl_set_get_dim_id(Domain, isl_dim_set, u);
+      ConsequenceCondSet =
+          isl_set_set_dim_id(ConsequenceCondSet, isl_dim_set, u, DimId);
+    }
   }
 
   assert(ConsequenceCondSet);
@@ -968,17 +975,21 @@ void ScopStmt::deriveAssumptions(BasicBlock *Block) {
       deriveAssumptionsFromGEP(GEP);
 }
 
-ScopStmt::ScopStmt(Scop &parent, TempScop &tempScop, Region &R,
-                   SmallVectorImpl<Loop *> &Nest)
-    : Parent(parent), BB(nullptr), R(&R), Build(nullptr),
-      NestLoops(Nest.size()) {
-  // Setup the induction variables.
-  for (unsigned i = 0, e = Nest.size(); i < e; ++i)
-    NestLoops[i] = Nest[i];
+void ScopStmt::collectSurroundingLoops() {
+  for (unsigned u = 0, e = isl_set_n_dim(Domain); u < e; u++) {
+    isl_id *DimId = isl_set_get_dim_id(Domain, isl_dim_set, u);
+    NestLoops.push_back(static_cast<Loop *>(isl_id_get_user(DimId)));
+    isl_id_free(DimId);
+  }
+}
+
+ScopStmt::ScopStmt(Scop &parent, TempScop &tempScop, Region &R)
+    : Parent(parent), BB(nullptr), R(&R), Build(nullptr) {
 
   BaseName = getIslCompatibleName("Stmt_", R.getNameStr(), "");
 
   buildDomain();
+  collectSurroundingLoops();
 
   BasicBlock *EntryBB = R.getEntry();
   for (BasicBlock *Block : R.blocks()) {
@@ -989,17 +1000,13 @@ ScopStmt::ScopStmt(Scop &parent, TempScop &tempScop, Region &R,
     checkForReductions();
 }
 
-ScopStmt::ScopStmt(Scop &parent, TempScop &tempScop, BasicBlock &bb,
-                   SmallVectorImpl<Loop *> &Nest)
-    : Parent(parent), BB(&bb), R(nullptr), Build(nullptr),
-      NestLoops(Nest.size()) {
-  // Setup the induction variables.
-  for (unsigned i = 0, e = Nest.size(); i < e; ++i)
-    NestLoops[i] = Nest[i];
+ScopStmt::ScopStmt(Scop &parent, TempScop &tempScop, BasicBlock &bb)
+    : Parent(parent), BB(&bb), R(nullptr), Build(nullptr) {
 
   BaseName = getIslCompatibleName("Stmt_", &bb, "");
 
   buildDomain();
+  collectSurroundingLoops();
   buildAccesses(tempScop, BB);
   deriveAssumptions(BB);
   if (DetectReductions)
@@ -1469,8 +1476,28 @@ static inline Loop *getRegionNodeLoop(RegionNode *RN, LoopInfo &LI) {
   return L;
 }
 
+static inline unsigned getNumBlocksInRegionNode(RegionNode *RN) {
+  if (!RN->isSubRegion())
+    return 1;
+
+  unsigned NumBlocks = 0;
+  Region *R = RN->getNodeAs<Region>();
+  for (auto BB : R->blocks()) {
+    (void)BB;
+    NumBlocks++;
+  }
+  return NumBlocks;
+}
+
 ///}
 
+static inline __isl_give isl_set *addDomainDimId(__isl_take isl_set *Domain,
+                                                 unsigned Dim, Loop *L) {
+  isl_id *DimId =
+      isl_id_alloc(isl_set_get_ctx(Domain), nullptr, static_cast<void *>(L));
+  return isl_set_set_dim_id(Domain, isl_dim_set, Dim, DimId);
+}
+
 isl_set *Scop::getDomainConditions(ScopStmt *Stmt) {
   BasicBlock *BB = Stmt->isBlockStmt() ? Stmt->getBasicBlock()
                                        : Stmt->getRegion()->getEntry();
@@ -1483,6 +1510,13 @@ void Scop::buildDomains(Region *R, LoopInfo &LI, ScopDetection &SD,
   auto *EntryBB = R->getEntry();
   int LD = getRelativeLoopDepth(LI.getLoopFor(EntryBB));
   auto *S = isl_set_universe(isl_space_set_alloc(getIslCtx(), 0, LD + 1));
+
+  Loop *L = LI.getLoopFor(EntryBB);
+  while (LD-- >= 0) {
+    S = addDomainDimId(S, LD + 1, L);
+    L = L->getParentLoop();
+  }
+
   DomainMap[EntryBB] = S;
 
   buildDomainsWithBranchConstraints(R, LI, SD, DT);
@@ -1572,9 +1606,11 @@ void Scop::buildDomainsWithBranchConstraints(Region *R, LoopInfo &LI,
           CondSet = isl_set_project_out(CondSet, isl_dim_set, BBLoopDepth, 1);
         } else if (SuccBBLoopDepth > BBLoopDepth) {
           CondSet = isl_set_add_dims(CondSet, isl_dim_set, 1);
+          CondSet = addDomainDimId(CondSet, SuccBBLoopDepth, SuccBBLoop);
         } else if (BBLoopDepth >= 0) {
           CondSet = isl_set_project_out(CondSet, isl_dim_set, BBLoopDepth, 1);
           CondSet = isl_set_add_dims(CondSet, isl_dim_set, 1);
+          CondSet = addDomainDimId(CondSet, SuccBBLoopDepth, SuccBBLoop);
         }
       }
 
@@ -1992,6 +2028,11 @@ bool Scop::buildAliasGroups(AliasAnalysis &AA) {
   return true;
 }
 
+static Loop *getLoopSurroundingRegion(Region &R, LoopInfo &LI) {
+  Loop *L = LI.getLoopFor(R.getEntry());
+  return L ? (R.contains(L) ? L->getParentLoop() : L) : nullptr;
+}
+
 static unsigned getMaxLoopDepthInRegion(const Region &R, LoopInfo &LI,
                                         ScopDetection &SD) {
 
@@ -2032,21 +2073,18 @@ void Scop::initFromTempScop(TempScop &TempScop, LoopInfo &LI, ScopDetection &SD,
 
   buildDomains(&R, LI, SD, DT);
 
-  SmallVector<Loop *, 8> NestLoops;
+  DenseMap<Loop *, std::pair<isl_schedule *, unsigned>> LoopSchedules;
 
-  // Build the iteration domain, access functions and schedule functions
-  // traversing the region tree.
-  Schedule = buildScop(TempScop, getRegion(), NestLoops, LI, SD);
-  if (!Schedule)
-    Schedule = isl_schedule_empty(getParamSpace());
+  Loop *L = getLoopSurroundingRegion(R, LI);
+  LoopSchedules[L];
+  buildSchedule(&R, TempScop, LI, SD, LoopSchedules);
+  Schedule = LoopSchedules[L].first;
 
   realignParams();
   addParameterBounds();
   addUserContext();
   simplifyAssumedContext();
   buildAliasChecks(AA);
-
-  assert(NestLoops.empty() && "NestLoops not empty at top level!");
 }
 
 Scop *Scop::createFromTempScop(TempScop &TempScop, LoopInfo &LI,
@@ -2435,6 +2473,11 @@ static isl_stat mapToDimension_AddSet(__isl_take isl_set *Set, void *User) {
 // @param N      The dimension to map to.
 static __isl_give isl_multi_union_pw_aff *
 mapToDimension(__isl_take isl_union_set *Domain, int N) {
+  if (N <= 0 || isl_union_set_is_empty(Domain)) {
+    isl_union_set_free(Domain);
+    return nullptr;
+  }
+
   struct MapToDimensionDataTy Data;
   isl_space *Space;
 
@@ -2448,16 +2491,15 @@ mapToDimension(__isl_take isl_union_set *Domain, int N) {
   return isl_multi_union_pw_aff_from_union_pw_multi_aff(Data.Res);
 }
 
-ScopStmt *Scop::addScopStmt(BasicBlock *BB, Region *R, TempScop &tempScop,
-                            SmallVectorImpl<Loop *> &NestLoops) {
+ScopStmt *Scop::addScopStmt(BasicBlock *BB, Region *R, TempScop &tempScop) {
   ScopStmt *Stmt;
   if (BB) {
-    Stmts.emplace_back(*this, tempScop, *BB, NestLoops);
+    Stmts.emplace_back(*this, tempScop, *BB);
     Stmt = &Stmts.back();
     StmtMap[BB] = Stmt;
   } else {
     assert(R && "Either basic block or a region expected.");
-    Stmts.emplace_back(*this, tempScop, *R, NestLoops);
+    Stmts.emplace_back(*this, tempScop, *R);
     Stmt = &Stmts.back();
     for (BasicBlock *BB : R->blocks())
       StmtMap[BB] = Stmt;
@@ -2465,62 +2507,59 @@ ScopStmt *Scop::addScopStmt(BasicBlock *BB, Region *R, TempScop &tempScop,
   return Stmt;
 }
 
-__isl_give isl_schedule *
-Scop::buildBBScopStmt(BasicBlock *BB, TempScop &tempScop,
-                      SmallVectorImpl<Loop *> &NestLoops) {
-  if (isTrivialBB(BB, tempScop))
-    return nullptr;
+void Scop::buildSchedule(
+    Region *R, TempScop &TS, LoopInfo &LI, ScopDetection &SD,
+    DenseMap<Loop *, std::pair<isl_schedule *, unsigned>> &LoopSchedules) {
 
-  auto *Stmt = addScopStmt(BB, nullptr, tempScop, NestLoops);
-  auto *Domain = Stmt->getDomain();
-  return isl_schedule_from_domain(isl_union_set_from_set(Domain));
-}
+  ReversePostOrderTraversal<Region *> RTraversal(R);
+  for (auto *RN : RTraversal) {
 
-__isl_give isl_schedule *Scop::buildScop(TempScop &tempScop,
-                                         const Region &CurRegion,
-                                         SmallVectorImpl<Loop *> &NestLoops,
-                                         LoopInfo &LI, ScopDetection &SD) {
-  if (SD.isNonAffineSubRegion(&CurRegion, &getRegion())) {
-    auto *Stmt = addScopStmt(nullptr, const_cast<Region *>(&CurRegion),
-                             tempScop, NestLoops);
-    auto *Domain = Stmt->getDomain();
-    return isl_schedule_from_domain(isl_union_set_from_set(Domain));
-  }
+    if (RN->isSubRegion()) {
+      Region *SubRegion = RN->getNodeAs<Region>();
+      if (!SD.isNonAffineSubRegion(SubRegion, &getRegion())) {
+        buildSchedule(SubRegion, TS, LI, SD, LoopSchedules);
+        continue;
+      }
+    }
 
-  Loop *L = castToLoop(CurRegion, LI);
+    Loop *L = getRegionNodeLoop(RN, LI);
+    int LD = getRelativeLoopDepth(L);
+    auto &LSchedulePair = LoopSchedules[L];
+    LSchedulePair.second += getNumBlocksInRegionNode(RN);
 
-  if (L)
-    NestLoops.push_back(L);
+    BasicBlock *BB = getRegionNodeBasicBlock(RN);
+    if (RN->isSubRegion() || !isTrivialBB(BB, TS)) {
 
-  unsigned loopDepth = NestLoops.size();
-  isl_schedule *Schedule = nullptr;
+      ScopStmt *Stmt;
+      if (RN->isSubRegion())
+        Stmt = addScopStmt(nullptr, RN->getNodeAs<Region>(), TS);
+      else
+        Stmt = addScopStmt(BB, nullptr, TS);
 
-  for (Region::const_element_iterator I = CurRegion.element_begin(),
-                                      E = CurRegion.element_end();
-       I != E; ++I) {
-    isl_schedule *StmtSchedule = nullptr;
-    if (I->isSubRegion()) {
-      StmtSchedule =
-          buildScop(tempScop, *I->getNodeAs<Region>(), NestLoops, LI, SD);
-    } else {
-      StmtSchedule =
-          buildBBScopStmt(I->getNodeAs<BasicBlock>(), tempScop, NestLoops);
+      auto *UDomain = isl_union_set_from_set(Stmt->getDomain());
+      auto *StmtSchedule = isl_schedule_from_domain(UDomain);
+      LSchedulePair.first =
+          combineInSequence(LSchedulePair.first, StmtSchedule);
     }
-    Schedule = combineInSequence(Schedule, StmtSchedule);
-  }
-
-  if (!L)
-    return Schedule;
 
-  auto *Domain = isl_schedule_get_domain(Schedule);
-  if (!isl_union_set_is_empty(Domain)) {
-    auto *MUPA = mapToDimension(isl_union_set_copy(Domain), loopDepth);
-    Schedule = isl_schedule_insert_partial_schedule(Schedule, MUPA);
+    unsigned NumVisited = LSchedulePair.second;
+    while (L && NumVisited == L->getNumBlocks()) {
+      auto *LDomain = isl_schedule_get_domain(LSchedulePair.first);
+      if (auto *MUPA = mapToDimension(LDomain, LD + 1))
+        LSchedulePair.first =
+            isl_schedule_insert_partial_schedule(LSchedulePair.first, MUPA);
+
+      auto *PL = L->getParentLoop();
+      assert(LoopSchedules.count(PL));
+      auto &PSchedulePair = LoopSchedules[PL];
+      PSchedulePair.first =
+          combineInSequence(PSchedulePair.first, LSchedulePair.first);
+      PSchedulePair.second += NumVisited;
+
+      L = PL;
+      NumVisited = PSchedulePair.second;
+    }
   }
-  isl_union_set_free(Domain);
-
-  NestLoops.pop_back();
-  return Schedule;
 }
 
 ScopStmt *Scop::getStmtForBasicBlock(BasicBlock *BB) const {
diff --git a/polly/lib/Support/ScopHelper.cpp b/polly/lib/Support/ScopHelper.cpp
index 602009cd0df..a535f98aa55 100644
--- a/polly/lib/Support/ScopHelper.cpp
+++ b/polly/lib/Support/ScopHelper.cpp
@@ -28,36 +28,6 @@ using namespace polly;
 
 #define DEBUG_TYPE "polly-scop-helper"
 
-// Helper function for Scop
-// TODO: Add assertion to not allow parameter to be null
-//===----------------------------------------------------------------------===//
-// Temporary Hack for extended region tree.
-// Cast the region to loop if there is a loop have the same header and exit.
-Loop *polly::castToLoop(const Region &R, LoopInfo &LI) {
-  BasicBlock *entry = R.getEntry();
-
-  if (!LI.isLoopHeader(entry))
-    return 0;
-
-  Loop *L = LI.getLoopFor(entry);
-
-  BasicBlock *exit = L->getExitBlock();
-
-  // Is the loop with multiple exits?
-  if (!exit)
-    return 0;
-
-  if (exit != R.getExit()) {
-    // SubRegion/ParentRegion with the same entry.
-    assert((R.getNode(R.getEntry())->isSubRegion() ||
-            R.getParent()->getEntry() == entry) &&
-           "Expect the loop is the smaller or bigger region");
-    return 0;
-  }
-
-  return L;
-}
-
 Value *polly::getPointerOperand(Instruction &Inst) {
   if (LoadInst *load = dyn_cast<LoadInst>(&Inst))
     return load->getPointerOperand();
diff --git a/polly/test/Isl/Ast/simple-run-time-condition.ll b/polly/test/Isl/Ast/simple-run-time-condition.ll
index ca0ccc44431..7a9f00dd1e9 100644
--- a/polly/test/Isl/Ast/simple-run-time-condition.ll
+++ b/polly/test/Isl/Ast/simple-run-time-condition.ll
@@ -23,14 +23,14 @@ target datalayout = "e-p:64:64:64-i1:8:8-i8:8:8-i16:16:16-i32:32:32-i64:64:64-f3
 ; CHECK; (o <= 0 && m + q >= 100 && q <= 100)
 ; CHECK: )
 
-; CHECK:     if (o >= 1) {
+; CHECK:     if (o <= 0) {
 ; CHECK:       for (int c0 = 0; c0 < n; c0 += 1)
 ; CHECK:         for (int c1 = 0; c1 < m; c1 += 1)
-; CHECK:           Stmt_for_j(c0, c1);
+; CHECK:           Stmt_for_j_1(c0, c1);
 ; CHECK:     } else
 ; CHECK:       for (int c0 = 0; c0 < n; c0 += 1)
 ; CHECK:         for (int c1 = 0; c1 < m; c1 += 1)
-; CHECK:           Stmt_for_j_1(c0, c1);
+; CHECK:           Stmt_for_j(c0, c1);
 
 ; CHECK: else
 ; CHECK:     {  /* original code */ }
diff --git a/polly/test/Isl/CodeGen/loop_with_condition.ll b/polly/test/Isl/CodeGen/loop_with_condition.ll
index bd55357172e..091d3a3120b 100644
--- a/polly/test/Isl/CodeGen/loop_with_condition.ll
+++ b/polly/test/Isl/CodeGen/loop_with_condition.ll
@@ -166,9 +166,9 @@ define i32 @main() nounwind {
 declare void @llvm.memset.p0i8.i64(i8* nocapture, i8, i64, i32, i1) nounwind
 
 ; CHECK: for (int c0 = 0; c0 <= 1023; c0 += 1) {
-; CHECK:   if (c0 <= 512) {
-; CHECK:     Stmt_4(c0);
-; CHECK:   } else
+; CHECK:   if (c0 >= 513) {
 ; CHECK:     Stmt_5(c0);
+; CHECK:   } else
+; CHECK:     Stmt_4(c0);
 ; CHECK:   Stmt_6(c0);
 ; CHECK: }
diff --git a/polly/test/Isl/CodeGen/loop_with_condition_2.ll b/polly/test/Isl/CodeGen/loop_with_condition_2.ll
index e013a752d2c..8aa04926c64 100644
--- a/polly/test/Isl/CodeGen/loop_with_condition_2.ll
+++ b/polly/test/Isl/CodeGen/loop_with_condition_2.ll
@@ -5,10 +5,10 @@
 
 ; CHECK: #pragma simd
 ; CHECK: for (int c0 = 0; c0 <= 1023; c0 += 1) {
-; CHECK:   if (m + 1024 >= c0) {
-; CHECK:     Stmt_if_then(c0);
-; CHECK:   } else
+; CHECK:   if (c0 >= m + 1025) {
 ; CHECK:     Stmt_if_else(c0);
+; CHECK:   } else
+; CHECK:     Stmt_if_then(c0);
 ; CHECK:   Stmt_if_end(c0);
 ; CHECK: }
 
diff --git a/polly/test/Isl/CodeGen/loop_with_condition_ineq.ll b/polly/test/Isl/CodeGen/loop_with_condition_ineq.ll
index d440b20c162..171a7d41324 100644
--- a/polly/test/Isl/CodeGen/loop_with_condition_ineq.ll
+++ b/polly/test/Isl/CodeGen/loop_with_condition_ineq.ll
@@ -166,9 +166,9 @@ define i32 @main() nounwind {
 declare void @llvm.memset.p0i8.i64(i8* nocapture, i8, i64, i32, i1) nounwind
 
 ; CHECK: for (int c0 = 0; c0 <= 1023; c0 += 1) {
-; CHECK:   if (c0 >= 513 || c0 <= 511) {
-; CHECK:     Stmt_4(c0);
-; CHECK:   } else
+; CHECK:   if (c0 == 512) {
 ; CHECK:     Stmt_5(512);
+; CHECK:   } else
+; CHECK:     Stmt_4(c0);
 ; CHECK:   Stmt_6(c0);
 ; CHECK: }
diff --git a/polly/test/Isl/CodeGen/loop_with_condition_nested.ll b/polly/test/Isl/CodeGen/loop_with_condition_nested.ll
index 411c2694f94..6fb6f4de40d 100644
--- a/polly/test/Isl/CodeGen/loop_with_condition_nested.ll
+++ b/polly/test/Isl/CodeGen/loop_with_condition_nested.ll
@@ -204,10 +204,10 @@ define i32 @main() nounwind {
 declare void @llvm.memset.p0i8.i64(i8* nocapture, i8, i64, i32, i1) nounwind
 
 ; CHECK: for (int c0 = 0; c0 <= 1023; c0 += 1) {
-; CHECK:   if (c0 >= 21 && c0 <= 512) {
-; CHECK:     Stmt_6(c0);
-; CHECK:   } else if (c0 <= 20)
+; CHECK:   if (c0 <= 20) {
 ; CHECK:     Stmt_7(c0);
+; CHECK:   } else if (c0 <= 512)
+; CHECK:     Stmt_6(c0);
 ; CHECK:   Stmt_9(c0);
 ; CHECK: }
 
diff --git a/polly/test/Isl/CodeGen/phi_condition_modeling_1.ll b/polly/test/Isl/CodeGen/phi_condition_modeling_1.ll
index 4d8e5a368a5..0400855a76f 100644
--- a/polly/test/Isl/CodeGen/phi_condition_modeling_1.ll
+++ b/polly/test/Isl/CodeGen/phi_condition_modeling_1.ll
@@ -16,10 +16,10 @@
 ; CHECK-LABEL: polly.stmt.bb8:
 ; CHECK:       %tmp.0.phiops.reload = load i32, i32* %tmp.0.phiops
 ; CHECK:       store i32 %tmp.0.phiops.reload, i32*
-; CHECK-LABEL: polly.stmt.bb6:
-; CHECK:       store i32 3, i32* %tmp.0.phiops
 ; CHECK-LABEL: polly.stmt.bb7:
 ; CHECK:       store i32 5, i32* %tmp.0.phiops
+; CHECK-LABEL: polly.stmt.bb6:
+; CHECK:       store i32 3, i32* %tmp.0.phiops
 
 target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
 
diff --git a/polly/test/Isl/CodeGen/phi_condition_modeling_2.ll b/polly/test/Isl/CodeGen/phi_condition_modeling_2.ll
index e9a64dd47a1..3c3248a45b5 100644
--- a/polly/test/Isl/CodeGen/phi_condition_modeling_2.ll
+++ b/polly/test/Isl/CodeGen/phi_condition_modeling_2.ll
@@ -20,10 +20,10 @@
 ; CHECK-LABEL: polly.stmt.bb8b:
 ; CHECK:       %tmp.0.s2a.reload = load i32, i32* %tmp.0.s2a
 ; CHECK:       store i32 %tmp.0.s2a.reload,
-; CHECK-LABEL: polly.stmt.bb6:
-; CHECK:       store i32 3, i32* %tmp.0.phiops
 ; CHECK-LABEL: polly.stmt.bb7:
 ; CHECK:       store i32 5, i32* %tmp.0.phiops
+; CHECK-LABEL: polly.stmt.bb6:
+; CHECK:       store i32 3, i32* %tmp.0.phiops
 
 target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
 
diff --git a/polly/test/Isl/CodeGen/phi_conditional_simple_1.ll b/polly/test/Isl/CodeGen/phi_conditional_simple_1.ll
index be017248612..a297cc2d28f 100644
--- a/polly/test/Isl/CodeGen/phi_conditional_simple_1.ll
+++ b/polly/test/Isl/CodeGen/phi_conditional_simple_1.ll
@@ -11,10 +11,10 @@
 ;    }
 
 ; AST:    for (int c0 = 0; c0 <= 1023; c0 += 1) {
-; AST:      if (c == 0) {
-; AST:        Stmt_if_else(c0);
-; AST:      } else if (c <= -1 || c >= 1)
+; AST:      if (c <= -1 || c >= 1) {
 ; AST:        Stmt_if_then(c0);
+; AST:      } else
+; AST:        Stmt_if_else(c0);
 ; AST:      Stmt_if_end(c0);
 ; AST:    }
 ;
@@ -24,12 +24,12 @@
 ; CHECK-NEXT:     %phi.phiops.reload = load i32, i32* %phi.phiops
 ; CHECK-NEXT:     %scevgep
 ; CHECK-NEXT:     store i32 %phi.phiops.reload, i32*
-; CHECK-LABEL:  polly.stmt.if.else:
-; CHECK-NEXT:     store i32 2, i32* %phi.phiops
-; CHECK-NEXT:     br label %polly.merge{{[.]?}}
 ; CHECK-LABEL:  polly.stmt.if.then:
 ; CHECK-NEXT:     store i32 1, i32* %phi.phiops
 ; CHECK-NEXT:     br label %polly.merge{{[.]?}}
+; CHECK-LABEL:  polly.stmt.if.else:
+; CHECK-NEXT:     store i32 2, i32* %phi.phiops
+; CHECK-NEXT:     br label %polly.merge{{[.]?}}
 ;
 target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
 
diff --git a/polly/test/ScopInfo/cond_constant_in_loop.ll b/polly/test/ScopInfo/cond_constant_in_loop.ll
index 5afd5fa7380..ae8964e6949 100644
--- a/polly/test/ScopInfo/cond_constant_in_loop.ll
+++ b/polly/test/ScopInfo/cond_constant_in_loop.ll
@@ -43,10 +43,9 @@ return:                                           ; preds = %bb3, %entry
   ret void
 }
 
-; CHECK: Stmt_bb1
-; CHECK:   Domain :=
-; CHECK:     [M, N] -> { Stmt_bb1[i0] : i0 >= 0 and i0 <= -1 + M };
 ; CHECK: Stmt_bb2
 ; CHECK:   Domain :=
 ; CHECK:     [M, N] -> { Stmt_bb2[i0] : 1 = 0 };
-
+; CHECK: Stmt_bb1
+; CHECK:   Domain :=
+; CHECK:     [M, N] -> { Stmt_bb1[i0] : i0 >= 0 and i0 <= -1 + M };
diff --git a/polly/test/ScopInfo/isl_trip_count_multiple_exiting_blocks.ll b/polly/test/ScopInfo/isl_trip_count_multiple_exiting_blocks.ll
new file mode 100644
index 00000000000..7e75ce10ad7
--- /dev/null
+++ b/polly/test/ScopInfo/isl_trip_count_multiple_exiting_blocks.ll
@@ -0,0 +1,46 @@
+; RUN: opt %loadPolly -polly-scops -polly-detect-unprofitable -analyze < %s | FileCheck %s
+;
+; CHECK: Domain :=
+; CHECK:   { Stmt_if_end[i0] : i0 <= 1024 and i0 >= 0 };
+;
+;    void f(int *A) {
+;      int i = 0;
+;      do {
+;        if (i > 1024)
+;          break;
+;        A[i] = i;
+;        i++;
+;      } while (i > 0);
+;    }
+;
+target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
+
+define void @f(i32* %A) {
+entry:
+  br label %do.body
+
+do.body:                                          ; preds = %do.cond, %entry
+  %indvars.iv = phi i64 [ %indvars.iv.next, %do.cond ], [ 0, %entry ]
+  %cmp = icmp sgt i64 %indvars.iv, 1024
+  br i1 %cmp, label %if.then, label %if.end
+
+if.then:                                          ; preds = %do.body
+  br label %do.end
+
+if.end:                                           ; preds = %do.body
+  %arrayidx = getelementptr inbounds i32, i32* %A, i64 %indvars.iv
+  %tmp = trunc i64 %indvars.iv to i32
+  store i32 %tmp, i32* %arrayidx, align 4
+  br label %do.cond
+
+do.cond:                                          ; preds = %if.end
+  %indvars.iv.next = add nuw nsw i64 %indvars.iv, 1
+  %cmp2 = icmp sgt i64 %indvars.iv.next, 0
+  br i1 %cmp2, label %do.body, label %do.end.loopexit
+
+do.end.loopexit:                                  ; preds = %do.cond
+  br label %do.end
+
+do.end:                                           ; preds = %do.end.loopexit, %if.then
+  ret void
+}
diff --git a/polly/test/ScopInfo/multiple_exiting_blocks.ll b/polly/test/ScopInfo/multiple_exiting_blocks.ll
new file mode 100644
index 00000000000..13a74d743dd
--- /dev/null
+++ b/polly/test/ScopInfo/multiple_exiting_blocks.ll
@@ -0,0 +1,60 @@
+; RUN: opt %loadPolly -polly-scops -polly-detect-unprofitable -analyze < %s | FileCheck %s
+;
+; CHECK: Domain :=
+; CHECK:   [N, P, Q] -> { Stmt_if_end[i0] : (i0 >= 2 + P and i0 >= 1 and i0 <= 1 + Q and i0 <= -1 + N) or (i0 >= 1 and i0 <= 1 + Q and i0 <= -1 + P and i0 <= -1 + N); Stmt_if_end[0] : (N >= 1 and P <= -1) or (N >= 1 and P >= 1) };
+;
+;    void f(int *A, int N, int P, int Q) {
+;      for (int i = 0; i < N; i++) {
+;        if (i == P)
+;          break;
+;        A[i]++;
+;        if (i > Q)
+;          break;
+;      }
+;    }
+;
+target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
+
+define void @f(i32* %A, i32 %N, i32 %P, i32 %Q) {
+entry:
+  %tmp = sext i32 %N to i64
+  %tmp1 = sext i32 %Q to i64
+  br label %for.cond
+
+for.cond:                                         ; preds = %for.inc, %entry
+  %indvars.iv = phi i64 [ %indvars.iv.next, %for.inc ], [ 0, %entry ]
+  %cmp = icmp slt i64 %indvars.iv, %tmp
+  br i1 %cmp, label %for.body, label %for.end.loopexit
+
+for.body:                                         ; preds = %for.cond
+  %tmp2 = trunc i64 %indvars.iv to i32
+  %cmp1 = icmp eq i32 %tmp2, %P
+  br i1 %cmp1, label %if.then, label %if.end
+
+if.then:                                          ; preds = %for.body
+  br label %for.end
+
+if.end:                                           ; preds = %for.body
+  %arrayidx = getelementptr inbounds i32, i32* %A, i64 %indvars.iv
+  %tmp3 = load i32, i32* %arrayidx, align 4
+  %inc = add nsw i32 %tmp3, 1
+  store i32 %inc, i32* %arrayidx, align 4
+  %cmp2 = icmp sgt i64 %indvars.iv, %tmp1
+  br i1 %cmp2, label %if.then.3, label %if.end.4
+
+if.then.3:                                        ; preds = %if.end
+  br label %for.end
+
+if.end.4:                                         ; preds = %if.end
+  br label %for.inc
+
+for.inc:                                          ; preds = %if.end.4
+  %indvars.iv.next = add nuw nsw i64 %indvars.iv, 1
+  br label %for.cond
+
+for.end.loopexit:                                 ; preds = %for.cond
+  br label %for.end
+
+for.end:                                          ; preds = %for.end.loopexit, %if.then.3, %if.then
+  ret void
+}
diff --git a/polly/test/ScopInfo/non_affine_region_1.ll b/polly/test/ScopInfo/non_affine_region_1.ll
index 89585107145..f3b9cdbece1 100644
--- a/polly/test/ScopInfo/non_affine_region_1.ll
+++ b/polly/test/ScopInfo/non_affine_region_1.ll
@@ -19,15 +19,15 @@
 ;    }
 ;
 ; CHECK:       Region: %bb1---%bb21
-; CHECK:       Stmt_bb3
+; CHECK:       Stmt_bb8
 ; CHECK:             MustWriteAccess :=  [Reduction Type: NONE] [Scalar: 1]
-; CHECK:                 [b] -> { Stmt_bb3[i0] -> MemRef_x_1__phi[] };
+; CHECK:                 [b] -> { Stmt_bb8[i0] -> MemRef_x_1__phi[] };
 ; CHECK:       Stmt_bb7
 ; CHECK:             MustWriteAccess :=  [Reduction Type: NONE] [Scalar: 1]
 ; CHECK:                 [b] -> { Stmt_bb7[i0] -> MemRef_x_1__phi[] };
-; CHECK:       Stmt_bb8
+; CHECK:       Stmt_bb3
 ; CHECK:             MustWriteAccess :=  [Reduction Type: NONE] [Scalar: 1]
-; CHECK:                 [b] -> { Stmt_bb8[i0] -> MemRef_x_1__phi[] };
+; CHECK:                 [b] -> { Stmt_bb3[i0] -> MemRef_x_1__phi[] };
 ; CHECK:       Stmt_bb10__TO__bb18
 ; CHECK-NEXT:        Domain :=
 ; CHECK-NEXT:            [b] -> { Stmt_bb10__TO__bb18[i0] :
diff --git a/polly/test/ScopInfo/phi_condition_modeling_1.ll b/polly/test/ScopInfo/phi_condition_modeling_1.ll
index 980e878bb98..2062a800c95 100644
--- a/polly/test/ScopInfo/phi_condition_modeling_1.ll
+++ b/polly/test/ScopInfo/phi_condition_modeling_1.ll
@@ -12,15 +12,15 @@
 ;    }
 ;
 ; CHECK:    Statements {
-; CHECK-LABEL:      Stmt_bb6
+; CHECK-LABEL:      Stmt_bb7
 ; CHECK-NOT: Access
 ; CHECK:            MustWriteAccess :=  [Reduction Type: NONE] [Scalar: 1]
-; CHECK:                [N, c] -> { Stmt_bb6[i0] -> MemRef_tmp_0__phi[] };
+; CHECK:                [N, c] -> { Stmt_bb7[i0] -> MemRef_tmp_0__phi[] };
 ; CHECK-NOT: Access
-; CHECK-LABEL:      Stmt_bb7
+; CHECK-LABEL:      Stmt_bb6
 ; CHECK-NOT: Access
 ; CHECK:            MustWriteAccess :=  [Reduction Type: NONE] [Scalar: 1]
-; CHECK:                [N, c] -> { Stmt_bb7[i0] -> MemRef_tmp_0__phi[] };
+; CHECK:                [N, c] -> { Stmt_bb6[i0] -> MemRef_tmp_0__phi[] };
 ; CHECK-NOT: Access
 ; CHECK-LABEL:      Stmt_bb8
 ; CHECK-NOT: Access
diff --git a/polly/test/ScopInfo/phi_condition_modeling_2.ll b/polly/test/ScopInfo/phi_condition_modeling_2.ll
index f283858b02f..e5624eeb1dd 100644
--- a/polly/test/ScopInfo/phi_condition_modeling_2.ll
+++ b/polly/test/ScopInfo/phi_condition_modeling_2.ll
@@ -12,15 +12,15 @@
 ;    }
 ;
 ; CHECK:    Statements {
-; CHECK-LABEL:      Stmt_bb6
+; CHECK-LABEL:      Stmt_bb7
 ; CHECK-NOT: Access
 ; CHECK:            MustWriteAccess :=  [Reduction Type: NONE] [Scalar: 1]
-; CHECK:                [N, c] -> { Stmt_bb6[i0] -> MemRef_tmp_0__phi[] };
+; CHECK:                [N, c] -> { Stmt_bb7[i0] -> MemRef_tmp_0__phi[] };
 ; CHECK-NOT: Access
-; CHECK-LABEL:      Stmt_bb7
+; CHECK-LABEL:      Stmt_bb6
 ; CHECK-NOT: Access
 ; CHECK:            MustWriteAccess :=  [Reduction Type: NONE] [Scalar: 1]
-; CHECK:                [N, c] -> { Stmt_bb7[i0] -> MemRef_tmp_0__phi[] };
+; CHECK:                [N, c] -> { Stmt_bb6[i0] -> MemRef_tmp_0__phi[] };
 ; CHECK-NOT: Access
 ; CHECK-LABEL:      Stmt_bb8
 ; CHECK-NOT: Access
diff --git a/polly/test/ScopInfo/phi_conditional_simple_1.ll b/polly/test/ScopInfo/phi_conditional_simple_1.ll
index 50ed3217017..6e347c18c9f 100644
--- a/polly/test/ScopInfo/phi_conditional_simple_1.ll
+++ b/polly/test/ScopInfo/phi_conditional_simple_1.ll
@@ -10,15 +10,15 @@
 ;    }
 ;
 ; CHECK:    Statements {
-; CHECK-LABEL:      Stmt_if_else
+; CHECK-LABEL:      Stmt_if_then
 ; CHECK-NOT: Access
 ; CHECK:            MustWriteAccess :=  [Reduction Type: NONE] [Scalar: 1]
-; CHECK:                [c] -> { Stmt_if_else[i0] -> MemRef_phi__phi[] };
+; CHECK:                [c] -> { Stmt_if_then[i0] -> MemRef_phi__phi[] };
 ; CHECK-NOT: Access
-; CHECK-LABEL:      Stmt_if_then
+; CHECK-LABEL:      Stmt_if_else
 ; CHECK-NOT: Access
 ; CHECK:            MustWriteAccess :=  [Reduction Type: NONE] [Scalar: 1]
-; CHECK:                [c] -> { Stmt_if_then[i0] -> MemRef_phi__phi[] };
+; CHECK:                [c] -> { Stmt_if_else[i0] -> MemRef_phi__phi[] };
 ; CHECK-NOT: Access
 ; CHECK-LABEL:      Stmt_if_end
 ; CHECK-NOT: Access