[NFC][ScopBuilder] Move buildSchedule and its callees to ScopBuilder or ScopHelper

Scope of changes:
1. Moved buildSchedule functions to ScopBuilder.
2. Moved combineInSequence function to ScopBuilder.
3. Moved mapToDimension function to ScopBuilder.
4. Moved LoopStackTy to ScopBuilder.
5. Moved getLoopSurroundingScop to ScopHelper.
6. Moved getNumBlocksInLoop to ScopHelper.
7. Moved getNumBlocksInRegionNode to ScopHelper.
8. Moved getRegionNodeLoop to ScopHelper.

Differential Revision: https://reviews.llvm.org/D64223

llvm-svn: 366377

6 files changed, 327 insertions, 320 deletions

diff --git a/polly/include/polly/ScopBuilder.h b/polly/include/polly/ScopBuilder.h
index a6c8c0e..415190b 100644
--- a/polly/include/polly/ScopBuilder.h
+++ b/polly/include/polly/ScopBuilder.h
@@ -584,6 +584,62 @@ class ScopBuilder {
   /// have been hoisted as loop invariant.
   void canonicalizeDynamicBasePtrs();
 
+  /// Construct the schedule of this SCoP.
+  void buildSchedule();
+
+  /// A loop stack element to keep track of per-loop information during
+  ///        schedule construction.
+  using LoopStackElementTy = struct LoopStackElement {
+    // The loop for which we keep information.
+    Loop *L;
+
+    // The (possibly incomplete) schedule for this loop.
+    isl::schedule Schedule;
+
+    // The number of basic blocks in the current loop, for which a schedule has
+    // already been constructed.
+    unsigned NumBlocksProcessed;
+
+    LoopStackElement(Loop *L, isl::schedule S, unsigned NumBlocksProcessed)
+        : L(L), Schedule(S), NumBlocksProcessed(NumBlocksProcessed) {}
+  };
+
+  /// The loop stack used for schedule construction.
+  ///
+  /// The loop stack keeps track of schedule information for a set of nested
+  /// loops as well as an (optional) 'nullptr' loop that models the outermost
+  /// schedule dimension. The loops in a loop stack always have a parent-child
+  /// relation where the loop at position n is the parent of the loop at
+  /// position n + 1.
+  using LoopStackTy = SmallVector<LoopStackElementTy, 4>;
+
+  /// Construct schedule information for a given Region and add the
+  ///        derived information to @p LoopStack.
+  ///
+  /// Given a Region we derive schedule information for all RegionNodes
+  /// contained in this region ensuring that the assigned execution times
+  /// correctly model the existing control flow relations.
+  ///
+  /// @param R              The region which to process.
+  /// @param LoopStack      A stack of loops that are currently under
+  ///                       construction.
+  void buildSchedule(Region *R, LoopStackTy &LoopStack);
+
+  /// Build Schedule for the region node @p RN and add the derived
+  ///        information to @p LoopStack.
+  ///
+  /// In case @p RN is a BasicBlock or a non-affine Region, we construct the
+  /// schedule for this @p RN and also finalize loop schedules in case the
+  /// current @p RN completes the loop.
+  ///
+  /// In case @p RN is a not-non-affine Region, we delegate the construction to
+  /// buildSchedule(Region *R, ...).
+  ///
+  /// @param RN             The RegionNode region traversed.
+  /// @param LoopStack      A stack of loops that are currently under
+  ///                       construction.
+  void buildSchedule(RegionNode *RN, LoopStackTy &LoopStack);
+
 public:
   explicit ScopBuilder(Region *R, AssumptionCache &AC, AliasAnalysis &AA,
                        const DataLayout &DL, DominatorTree &DT, LoopInfo &LI,
diff --git a/polly/include/polly/ScopInfo.h b/polly/include/polly/ScopInfo.h
index 0e523bc..9405d8c 100644
--- a/polly/include/polly/ScopInfo.h
+++ b/polly/include/polly/ScopInfo.h
@@ -2109,66 +2109,6 @@ private:
   /// have a corresponding domain in the domain map (or it is empty).
   void removeStmtNotInDomainMap();
 
-  /// Construct the schedule of this SCoP.
-  ///
-  /// @param LI The LoopInfo for the current function.
-  void buildSchedule(LoopInfo &LI);
-
-  /// A loop stack element to keep track of per-loop information during
-  ///        schedule construction.
-  using LoopStackElementTy = struct LoopStackElement {
-    // The loop for which we keep information.
-    Loop *L;
-
-    // The (possibly incomplete) schedule for this loop.
-    isl::schedule Schedule;
-
-    // The number of basic blocks in the current loop, for which a schedule has
-    // already been constructed.
-    unsigned NumBlocksProcessed;
-
-    LoopStackElement(Loop *L, isl::schedule S, unsigned NumBlocksProcessed)
-        : L(L), Schedule(S), NumBlocksProcessed(NumBlocksProcessed) {}
-  };
-
-  /// The loop stack used for schedule construction.
-  ///
-  /// The loop stack keeps track of schedule information for a set of nested
-  /// loops as well as an (optional) 'nullptr' loop that models the outermost
-  /// schedule dimension. The loops in a loop stack always have a parent-child
-  /// relation where the loop at position n is the parent of the loop at
-  /// position n + 1.
-  using LoopStackTy = SmallVector<LoopStackElementTy, 4>;
-
-  /// Construct schedule information for a given Region and add the
-  ///        derived information to @p LoopStack.
-  ///
-  /// Given a Region we derive schedule information for all RegionNodes
-  /// contained in this region ensuring that the assigned execution times
-  /// correctly model the existing control flow relations.
-  ///
-  /// @param R              The region which to process.
-  /// @param LoopStack      A stack of loops that are currently under
-  ///                       construction.
-  /// @param LI The LoopInfo for the current function.
-  void buildSchedule(Region *R, LoopStackTy &LoopStack, LoopInfo &LI);
-
-  /// Build Schedule for the region node @p RN and add the derived
-  ///        information to @p LoopStack.
-  ///
-  /// In case @p RN is a BasicBlock or a non-affine Region, we construct the
-  /// schedule for this @p RN and also finalize loop schedules in case the
-  /// current @p RN completes the loop.
-  ///
-  /// In case @p RN is a not-non-affine Region, we delegate the construction to
-  /// buildSchedule(Region *R, ...).
-  ///
-  /// @param RN             The RegionNode region traversed.
-  /// @param LoopStack      A stack of loops that are currently under
-  ///                       construction.
-  /// @param LI The LoopInfo for the current function.
-  void buildSchedule(RegionNode *RN, LoopStackTy &LoopStack, LoopInfo &LI);
-
   /// Collect all memory access relations of a given type.
   ///
   /// @param Predicate A predicate function that returns true if an access is
diff --git a/polly/include/polly/Support/ScopHelper.h b/polly/include/polly/Support/ScopHelper.h
index 02c669a..8d794e0 100644
--- a/polly/include/polly/Support/ScopHelper.h
+++ b/polly/include/polly/Support/ScopHelper.h
@@ -27,6 +27,7 @@ class Region;
 class Pass;
 class DominatorTree;
 class RegionInfo;
+class RegionNode;
 } // namespace llvm
 
 namespace polly {
@@ -379,6 +380,27 @@ bool isErrorBlock(llvm::BasicBlock &BB, const llvm::Region &R,
 /// @return The condition of @p TI and nullptr if none could be extracted.
 llvm::Value *getConditionFromTerminator(llvm::Instruction *TI);
 
+/// Get the smallest loop that contains @p S but is not in @p S.
+llvm::Loop *getLoopSurroundingScop(Scop &S, llvm::LoopInfo &LI);
+
+/// Get the number of blocks in @p L.
+///
+/// The number of blocks in a loop are the number of basic blocks actually
+/// belonging to the loop, as well as all single basic blocks that the loop
+/// exits to and which terminate in an unreachable instruction. We do not
+/// allow such basic blocks in the exit of a scop, hence they belong to the
+/// scop and represent run-time conditions which we want to model and
+/// subsequently speculate away.
+///
+/// @see getRegionNodeLoop for additional details.
+unsigned getNumBlocksInLoop(llvm::Loop *L);
+
+/// Get the number of blocks in @p RN.
+unsigned getNumBlocksInRegionNode(llvm::RegionNode *RN);
+
+/// Return the smallest loop surrounding @p RN.
+llvm::Loop *getRegionNodeLoop(llvm::RegionNode *RN, llvm::LoopInfo &LI);
+
 /// Check if @p LInst can be hoisted in @p R.
 ///
 /// @param LInst The load to check.
diff --git a/polly/lib/Analysis/ScopBuilder.cpp b/polly/lib/Analysis/ScopBuilder.cpp
index b2fdd07..d301cfe 100644
--- a/polly/lib/Analysis/ScopBuilder.cpp
+++ b/polly/lib/Analysis/ScopBuilder.cpp
@@ -24,6 +24,7 @@
 #include "polly/Support/VirtualInstruction.h"
 #include "llvm/ADT/ArrayRef.h"
 #include "llvm/ADT/EquivalenceClasses.h"
+#include "llvm/ADT/PostOrderIterator.h"
 #include "llvm/ADT/Statistic.h"
 #include "llvm/Analysis/AliasAnalysis.h"
 #include "llvm/Analysis/Loads.h"
@@ -222,6 +223,179 @@ void ScopBuilder::buildScalarDependences(ScopStmt *UserStmt,
     ensureValueRead(Op.get(), UserStmt);
 }
 
+// Create a sequence of two schedules. Either argument may be null and is
+// interpreted as the empty schedule. Can also return null if both schedules are
+// empty.
+static isl::schedule combineInSequence(isl::schedule Prev, isl::schedule Succ) {
+  if (!Prev)
+    return Succ;
+  if (!Succ)
+    return Prev;
+
+  return Prev.sequence(Succ);
+}
+
+// Create an isl_multi_union_aff that defines an identity mapping from the
+// elements of USet to their N-th dimension.
+//
+// # Example:
+//
+//            Domain: { A[i,j]; B[i,j,k] }
+//                 N: 1
+//
+// Resulting Mapping: { {A[i,j] -> [(j)]; B[i,j,k] -> [(j)] }
+//
+// @param USet   A union set describing the elements for which to generate a
+//               mapping.
+// @param N      The dimension to map to.
+// @returns      A mapping from USet to its N-th dimension.
+static isl::multi_union_pw_aff mapToDimension(isl::union_set USet, int N) {
+  assert(N >= 0);
+  assert(USet);
+  assert(!USet.is_empty());
+
+  auto Result = isl::union_pw_multi_aff::empty(USet.get_space());
+
+  for (isl::set S : USet.get_set_list()) {
+    int Dim = S.dim(isl::dim::set);
+    auto PMA = isl::pw_multi_aff::project_out_map(S.get_space(), isl::dim::set,
+                                                  N, Dim - N);
+    if (N > 1)
+      PMA = PMA.drop_dims(isl::dim::out, 0, N - 1);
+
+    Result = Result.add_pw_multi_aff(PMA);
+  }
+
+  return isl::multi_union_pw_aff(isl::union_pw_multi_aff(Result));
+}
+
+void ScopBuilder::buildSchedule() {
+  Loop *L = getLoopSurroundingScop(*scop, LI);
+  LoopStackTy LoopStack({LoopStackElementTy(L, nullptr, 0)});
+  buildSchedule(scop->getRegion().getNode(), LoopStack);
+  assert(LoopStack.size() == 1 && LoopStack.back().L == L);
+  scop->setScheduleTree(LoopStack[0].Schedule);
+}
+
+/// To generate a schedule for the elements in a Region we traverse the Region
+/// in reverse-post-order and add the contained RegionNodes in traversal order
+/// to the schedule of the loop that is currently at the top of the LoopStack.
+/// For loop-free codes, this results in a correct sequential ordering.
+///
+/// Example:
+///           bb1(0)
+///         /     \.
+///      bb2(1)   bb3(2)
+///         \    /  \.
+///          bb4(3)  bb5(4)
+///             \   /
+///              bb6(5)
+///
+/// Including loops requires additional processing. Whenever a loop header is
+/// encountered, the corresponding loop is added to the @p LoopStack. Starting
+/// from an empty schedule, we first process all RegionNodes that are within
+/// this loop and complete the sequential schedule at this loop-level before
+/// processing about any other nodes. To implement this
+/// loop-nodes-first-processing, the reverse post-order traversal is
+/// insufficient. Hence, we additionally check if the traversal yields
+/// sub-regions or blocks that are outside the last loop on the @p LoopStack.
+/// These region-nodes are then queue and only traverse after the all nodes
+/// within the current loop have been processed.
+void ScopBuilder::buildSchedule(Region *R, LoopStackTy &LoopStack) {
+  Loop *OuterScopLoop = getLoopSurroundingScop(*scop, LI);
+
+  ReversePostOrderTraversal<Region *> RTraversal(R);
+  std::deque<RegionNode *> WorkList(RTraversal.begin(), RTraversal.end());
+  std::deque<RegionNode *> DelayList;
+  bool LastRNWaiting = false;
+
+  // Iterate over the region @p R in reverse post-order but queue
+  // sub-regions/blocks iff they are not part of the last encountered but not
+  // completely traversed loop. The variable LastRNWaiting is a flag to indicate
+  // that we queued the last sub-region/block from the reverse post-order
+  // iterator. If it is set we have to explore the next sub-region/block from
+  // the iterator (if any) to guarantee progress. If it is not set we first try
+  // the next queued sub-region/blocks.
+  while (!WorkList.empty() || !DelayList.empty()) {
+    RegionNode *RN;
+
+    if ((LastRNWaiting && !WorkList.empty()) || DelayList.empty()) {
+      RN = WorkList.front();
+      WorkList.pop_front();
+      LastRNWaiting = false;
+    } else {
+      RN = DelayList.front();
+      DelayList.pop_front();
+    }
+
+    Loop *L = getRegionNodeLoop(RN, LI);
+    if (!scop->contains(L))
+      L = OuterScopLoop;
+
+    Loop *LastLoop = LoopStack.back().L;
+    if (LastLoop != L) {
+      if (LastLoop && !LastLoop->contains(L)) {
+        LastRNWaiting = true;
+        DelayList.push_back(RN);
+        continue;
+      }
+      LoopStack.push_back({L, nullptr, 0});
+    }
+    buildSchedule(RN, LoopStack);
+  }
+}
+
+void ScopBuilder::buildSchedule(RegionNode *RN, LoopStackTy &LoopStack) {
+  if (RN->isSubRegion()) {
+    auto *LocalRegion = RN->getNodeAs<Region>();
+    if (!scop->isNonAffineSubRegion(LocalRegion)) {
+      buildSchedule(LocalRegion, LoopStack);
+      return;
+    }
+  }
+
+  assert(LoopStack.rbegin() != LoopStack.rend());
+  auto LoopData = LoopStack.rbegin();
+  LoopData->NumBlocksProcessed += getNumBlocksInRegionNode(RN);
+
+  for (auto *Stmt : scop->getStmtListFor(RN)) {
+    isl::union_set UDomain{Stmt->getDomain()};
+    auto StmtSchedule = isl::schedule::from_domain(UDomain);
+    LoopData->Schedule = combineInSequence(LoopData->Schedule, StmtSchedule);
+  }
+
+  // Check if we just processed the last node in this loop. If we did, finalize
+  // the loop by:
+  //
+  //   - adding new schedule dimensions
+  //   - folding the resulting schedule into the parent loop schedule
+  //   - dropping the loop schedule from the LoopStack.
+  //
+  // Then continue to check surrounding loops, which might also have been
+  // completed by this node.
+  size_t Dimension = LoopStack.size();
+  while (LoopData->L &&
+         LoopData->NumBlocksProcessed == getNumBlocksInLoop(LoopData->L)) {
+    isl::schedule Schedule = LoopData->Schedule;
+    auto NumBlocksProcessed = LoopData->NumBlocksProcessed;
+
+    assert(std::next(LoopData) != LoopStack.rend());
+    ++LoopData;
+    --Dimension;
+
+    if (Schedule) {
+      isl::union_set Domain = Schedule.get_domain();
+      isl::multi_union_pw_aff MUPA = mapToDimension(Domain, Dimension);
+      Schedule = Schedule.insert_partial_schedule(MUPA);
+      LoopData->Schedule = combineInSequence(LoopData->Schedule, Schedule);
+    }
+
+    LoopData->NumBlocksProcessed += NumBlocksProcessed;
+  }
+  // Now pop all loops processed up there from the LoopStack
+  LoopStack.erase(LoopStack.begin() + Dimension, LoopStack.end());
+}
+
 void ScopBuilder::buildEscapingDependences(Instruction *Inst) {
   // Check for uses of this instruction outside the scop. Because we do not
   // iterate over such instructions and therefore did not "ensure" the existence
@@ -2554,7 +2728,7 @@ void ScopBuilder::buildScop(Region &R, AssumptionCache &AC) {
     return;
   }
 
-  scop->buildSchedule(LI);
+  buildSchedule();
 
   finalizeAccesses();
 
diff --git a/polly/lib/Analysis/ScopInfo.cpp b/polly/lib/Analysis/ScopInfo.cpp
index c9a780a..199729e 100644
--- a/polly/lib/Analysis/ScopInfo.cpp
+++ b/polly/lib/Analysis/ScopInfo.cpp
@@ -163,18 +163,6 @@ static cl::opt<bool> PollyPrintInstructions(
 
 //===----------------------------------------------------------------------===//
 
-// Create a sequence of two schedules. Either argument may be null and is
-// interpreted as the empty schedule. Can also return null if both schedules are
-// empty.
-static isl::schedule combineInSequence(isl::schedule Prev, isl::schedule Succ) {
-  if (!Prev)
-    return Succ;
-  if (!Succ)
-    return Prev;
-
-  return Prev.sequence(Succ);
-}
-
 static isl::set addRangeBoundsToSet(isl::set S, const ConstantRange &Range,
                                     int dim, isl::dim type) {
   isl::val V;
@@ -2125,72 +2113,6 @@ getRegionNodeSuccessor(RegionNode *RN, Instruction *TI, unsigned idx) {
   return TI->getSuccessor(idx);
 }
 
-/// Return the smallest loop surrounding @p RN.
-static inline Loop *getRegionNodeLoop(RegionNode *RN, LoopInfo &LI) {
-  if (!RN->isSubRegion()) {
-    BasicBlock *BB = RN->getNodeAs<BasicBlock>();
-    Loop *L = LI.getLoopFor(BB);
-
-    // Unreachable statements are not considered to belong to a LLVM loop, as
-    // they are not part of an actual loop in the control flow graph.
-    // Nevertheless, we handle certain unreachable statements that are common
-    // when modeling run-time bounds checks as being part of the loop to be
-    // able to model them and to later eliminate the run-time bounds checks.
-    //
-    // Specifically, for basic blocks that terminate in an unreachable and
-    // where the immediate predecessor is part of a loop, we assume these
-    // basic blocks belong to the loop the predecessor belongs to. This
-    // allows us to model the following code.
-    //
-    // for (i = 0; i < N; i++) {
-    //   if (i > 1024)
-    //     abort();            <- this abort might be translated to an
-    //                            unreachable
-    //
-    //   A[i] = ...
-    // }
-    if (!L && isa<UnreachableInst>(BB->getTerminator()) && BB->getPrevNode())
-      L = LI.getLoopFor(BB->getPrevNode());
-    return L;
-  }
-
-  Region *NonAffineSubRegion = RN->getNodeAs<Region>();
-  Loop *L = LI.getLoopFor(NonAffineSubRegion->getEntry());
-  while (L && NonAffineSubRegion->contains(L))
-    L = L->getParentLoop();
-  return L;
-}
-
-/// Get the number of blocks in @p L.
-///
-/// The number of blocks in a loop are the number of basic blocks actually
-/// belonging to the loop, as well as all single basic blocks that the loop
-/// exits to and which terminate in an unreachable instruction. We do not
-/// allow such basic blocks in the exit of a scop, hence they belong to the
-/// scop and represent run-time conditions which we want to model and
-/// subsequently speculate away.
-///
-/// @see getRegionNodeLoop for additional details.
-unsigned getNumBlocksInLoop(Loop *L) {
-  unsigned NumBlocks = L->getNumBlocks();
-  SmallVector<BasicBlock *, 4> ExitBlocks;
-  L->getExitBlocks(ExitBlocks);
-
-  for (auto ExitBlock : ExitBlocks) {
-    if (isa<UnreachableInst>(ExitBlock->getTerminator()))
-      NumBlocks++;
-  }
-  return NumBlocks;
-}
-
-static inline unsigned getNumBlocksInRegionNode(RegionNode *RN) {
-  if (!RN->isSubRegion())
-    return 1;
-
-  Region *R = RN->getNodeAs<Region>();
-  return std::distance(R->block_begin(), R->block_end());
-}
-
 static bool containsErrorBlock(RegionNode *RN, const Region &R, LoopInfo &LI,
                                const DominatorTree &DT) {
   if (!RN->isSubRegion())
@@ -2761,26 +2683,6 @@ bool Scop::addLoopBoundsToHeaderDomain(
   return true;
 }
 
-/// Get the smallest loop that contains @p S but is not in @p S.
-static Loop *getLoopSurroundingScop(Scop &S, LoopInfo &LI) {
-  // Start with the smallest loop containing the entry and expand that
-  // loop until it contains all blocks in the region. If there is a loop
-  // containing all blocks in the region check if it is itself contained
-  // and if so take the parent loop as it will be the smallest containing
-  // the region but not contained by it.
-  Loop *L = LI.getLoopFor(S.getEntry());
-  while (L) {
-    bool AllContained = true;
-    for (auto *BB : S.blocks())
-      AllContained &= L->contains(BB);
-    if (AllContained)
-      break;
-    L = L->getParentLoop();
-  }
-
-  return L ? (S.contains(L) ? L->getParentLoop() : L) : nullptr;
-}
-
 int Scop::NextScopID = 0;
 
 std::string Scop::CurrentFunc;
@@ -3463,40 +3365,6 @@ bool Scop::restrictDomains(isl::union_set Domain) {
 
 ScalarEvolution *Scop::getSE() const { return SE; }
 
-// Create an isl_multi_union_aff that defines an identity mapping from the
-// elements of USet to their N-th dimension.
-//
-// # Example:
-//
-//            Domain: { A[i,j]; B[i,j,k] }
-//                 N: 1
-//
-// Resulting Mapping: { {A[i,j] -> [(j)]; B[i,j,k] -> [(j)] }
-//
-// @param USet   A union set describing the elements for which to generate a
-//               mapping.
-// @param N      The dimension to map to.
-// @returns      A mapping from USet to its N-th dimension.
-static isl::multi_union_pw_aff mapToDimension(isl::union_set USet, int N) {
-  assert(N >= 0);
-  assert(USet);
-  assert(!USet.is_empty());
-
-  auto Result = isl::union_pw_multi_aff::empty(USet.get_space());
-
-  for (isl::set S : USet.get_set_list()) {
-    int Dim = S.dim(isl::dim::set);
-    auto PMA = isl::pw_multi_aff::project_out_map(S.get_space(), isl::dim::set,
-                                                  N, Dim - N);
-    if (N > 1)
-      PMA = PMA.drop_dims(isl::dim::out, 0, N - 1);
-
-    Result = Result.add_pw_multi_aff(PMA);
-  }
-
-  return isl::multi_union_pw_aff(isl::union_pw_multi_aff(Result));
-}
-
 void Scop::addScopStmt(BasicBlock *BB, StringRef Name, Loop *SurroundingLoop,
                        std::vector<Instruction *> Instructions) {
   assert(BB && "Unexpected nullptr!");
@@ -3549,133 +3417,6 @@ ScopStmt *Scop::addScopStmt(isl::map SourceRel, isl::map TargetRel,
   return &(Stmts.back());
 }
 
-void Scop::buildSchedule(LoopInfo &LI) {
-  Loop *L = getLoopSurroundingScop(*this, LI);
-  LoopStackTy LoopStack({LoopStackElementTy(L, nullptr, 0)});
-  buildSchedule(getRegion().getNode(), LoopStack, LI);
-  assert(LoopStack.size() == 1 && LoopStack.back().L == L);
-  Schedule = LoopStack[0].Schedule;
-}
-
-/// To generate a schedule for the elements in a Region we traverse the Region
-/// in reverse-post-order and add the contained RegionNodes in traversal order
-/// to the schedule of the loop that is currently at the top of the LoopStack.
-/// For loop-free codes, this results in a correct sequential ordering.
-///
-/// Example:
-///           bb1(0)
-///         /     \.
-///      bb2(1)   bb3(2)
-///         \    /  \.
-///          bb4(3)  bb5(4)
-///             \   /
-///              bb6(5)
-///
-/// Including loops requires additional processing. Whenever a loop header is
-/// encountered, the corresponding loop is added to the @p LoopStack. Starting
-/// from an empty schedule, we first process all RegionNodes that are within
-/// this loop and complete the sequential schedule at this loop-level before
-/// processing about any other nodes. To implement this
-/// loop-nodes-first-processing, the reverse post-order traversal is
-/// insufficient. Hence, we additionally check if the traversal yields
-/// sub-regions or blocks that are outside the last loop on the @p LoopStack.
-/// These region-nodes are then queue and only traverse after the all nodes
-/// within the current loop have been processed.
-void Scop::buildSchedule(Region *R, LoopStackTy &LoopStack, LoopInfo &LI) {
-  Loop *OuterScopLoop = getLoopSurroundingScop(*this, LI);
-
-  ReversePostOrderTraversal<Region *> RTraversal(R);
-  std::deque<RegionNode *> WorkList(RTraversal.begin(), RTraversal.end());
-  std::deque<RegionNode *> DelayList;
-  bool LastRNWaiting = false;
-
-  // Iterate over the region @p R in reverse post-order but queue
-  // sub-regions/blocks iff they are not part of the last encountered but not
-  // completely traversed loop. The variable LastRNWaiting is a flag to indicate
-  // that we queued the last sub-region/block from the reverse post-order
-  // iterator. If it is set we have to explore the next sub-region/block from
-  // the iterator (if any) to guarantee progress. If it is not set we first try
-  // the next queued sub-region/blocks.
-  while (!WorkList.empty() || !DelayList.empty()) {
-    RegionNode *RN;
-
-    if ((LastRNWaiting && !WorkList.empty()) || DelayList.empty()) {
-      RN = WorkList.front();
-      WorkList.pop_front();
-      LastRNWaiting = false;
-    } else {
-      RN = DelayList.front();
-      DelayList.pop_front();
-    }
-
-    Loop *L = getRegionNodeLoop(RN, LI);
-    if (!contains(L))
-      L = OuterScopLoop;
-
-    Loop *LastLoop = LoopStack.back().L;
-    if (LastLoop != L) {
-      if (LastLoop && !LastLoop->contains(L)) {
-        LastRNWaiting = true;
-        DelayList.push_back(RN);
-        continue;
-      }
-      LoopStack.push_back({L, nullptr, 0});
-    }
-    buildSchedule(RN, LoopStack, LI);
-  }
-}
-
-void Scop::buildSchedule(RegionNode *RN, LoopStackTy &LoopStack, LoopInfo &LI) {
-  if (RN->isSubRegion()) {
-    auto *LocalRegion = RN->getNodeAs<Region>();
-    if (!isNonAffineSubRegion(LocalRegion)) {
-      buildSchedule(LocalRegion, LoopStack, LI);
-      return;
-    }
-  }
-
-  assert(LoopStack.rbegin() != LoopStack.rend());
-  auto LoopData = LoopStack.rbegin();
-  LoopData->NumBlocksProcessed += getNumBlocksInRegionNode(RN);
-
-  for (auto *Stmt : getStmtListFor(RN)) {
-    isl::union_set UDomain{Stmt->getDomain()};
-    auto StmtSchedule = isl::schedule::from_domain(UDomain);
-    LoopData->Schedule = combineInSequence(LoopData->Schedule, StmtSchedule);
-  }
-
-  // Check if we just processed the last node in this loop. If we did, finalize
-  // the loop by:
-  //
-  //   - adding new schedule dimensions
-  //   - folding the resulting schedule into the parent loop schedule
-  //   - dropping the loop schedule from the LoopStack.
-  //
-  // Then continue to check surrounding loops, which might also have been
-  // completed by this node.
-  size_t Dimension = LoopStack.size();
-  while (LoopData->L &&
-         LoopData->NumBlocksProcessed == getNumBlocksInLoop(LoopData->L)) {
-    isl::schedule Schedule = LoopData->Schedule;
-    auto NumBlocksProcessed = LoopData->NumBlocksProcessed;
-
-    assert(std::next(LoopData) != LoopStack.rend());
-    ++LoopData;
-    --Dimension;
-
-    if (Schedule) {
-      isl::union_set Domain = Schedule.get_domain();
-      isl::multi_union_pw_aff MUPA = mapToDimension(Domain, Dimension);
-      Schedule = Schedule.insert_partial_schedule(MUPA);
-      LoopData->Schedule = combineInSequence(LoopData->Schedule, Schedule);
-    }
-
-    LoopData->NumBlocksProcessed += NumBlocksProcessed;
-  }
-  // Now pop all loops processed up there from the LoopStack
-  LoopStack.erase(LoopStack.begin() + Dimension, LoopStack.end());
-}
-
 ArrayRef<ScopStmt *> Scop::getStmtListFor(BasicBlock *BB) const {
   auto StmtMapIt = StmtMap.find(BB);
   if (StmtMapIt == StmtMap.end())
diff --git a/polly/lib/Support/ScopHelper.cpp b/polly/lib/Support/ScopHelper.cpp
index e65c472..5f80afd 100644
--- a/polly/lib/Support/ScopHelper.cpp
+++ b/polly/lib/Support/ScopHelper.cpp
@@ -461,6 +461,80 @@ Value *polly::getConditionFromTerminator(Instruction *TI) {
   return nullptr;
 }
 
+Loop *polly::getLoopSurroundingScop(Scop &S, LoopInfo &LI) {
+  // Start with the smallest loop containing the entry and expand that
+  // loop until it contains all blocks in the region. If there is a loop
+  // containing all blocks in the region check if it is itself contained
+  // and if so take the parent loop as it will be the smallest containing
+  // the region but not contained by it.
+  Loop *L = LI.getLoopFor(S.getEntry());
+  while (L) {
+    bool AllContained = true;
+    for (auto *BB : S.blocks())
+      AllContained &= L->contains(BB);
+    if (AllContained)
+      break;
+    L = L->getParentLoop();
+  }
+
+  return L ? (S.contains(L) ? L->getParentLoop() : L) : nullptr;
+}
+
+unsigned polly::getNumBlocksInLoop(Loop *L) {
+  unsigned NumBlocks = L->getNumBlocks();
+  SmallVector<BasicBlock *, 4> ExitBlocks;
+  L->getExitBlocks(ExitBlocks);
+
+  for (auto ExitBlock : ExitBlocks) {
+    if (isa<UnreachableInst>(ExitBlock->getTerminator()))
+      NumBlocks++;
+  }
+  return NumBlocks;
+}
+
+unsigned polly::getNumBlocksInRegionNode(RegionNode *RN) {
+  if (!RN->isSubRegion())
+    return 1;
+
+  Region *R = RN->getNodeAs<Region>();
+  return std::distance(R->block_begin(), R->block_end());
+}
+
+Loop *polly::getRegionNodeLoop(RegionNode *RN, LoopInfo &LI) {
+  if (!RN->isSubRegion()) {
+    BasicBlock *BB = RN->getNodeAs<BasicBlock>();
+    Loop *L = LI.getLoopFor(BB);
+
+    // Unreachable statements are not considered to belong to a LLVM loop, as
+    // they are not part of an actual loop in the control flow graph.
+    // Nevertheless, we handle certain unreachable statements that are common
+    // when modeling run-time bounds checks as being part of the loop to be
+    // able to model them and to later eliminate the run-time bounds checks.
+    //
+    // Specifically, for basic blocks that terminate in an unreachable and
+    // where the immediate predecessor is part of a loop, we assume these
+    // basic blocks belong to the loop the predecessor belongs to. This
+    // allows us to model the following code.
+    //
+    // for (i = 0; i < N; i++) {
+    //   if (i > 1024)
+    //     abort();            <- this abort might be translated to an
+    //                            unreachable
+    //
+    //   A[i] = ...
+    // }
+    if (!L && isa<UnreachableInst>(BB->getTerminator()) && BB->getPrevNode())
+      L = LI.getLoopFor(BB->getPrevNode());
+    return L;
+  }
+
+  Region *NonAffineSubRegion = RN->getNodeAs<Region>();
+  Loop *L = LI.getLoopFor(NonAffineSubRegion->getEntry());
+  while (L && NonAffineSubRegion->contains(L))
+    L = L->getParentLoop();
+  return L;
+}
+
 static bool hasVariantIndex(GetElementPtrInst *Gep, Loop *L, Region &R,
                             ScalarEvolution &SE) {
   for (const Use &Val : llvm::drop_begin(Gep->operands(), 1)) {