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

[domada]

Summary

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 function to ScopHelper.
6. Moved getNumBlocksInLoop function to ScopHelper.
7. Moved getNumBlocksInRegionNode function to ScopHelper.
8. Moved getRegionNodeLoop function to ScopHelper.

[Meinersbur]

LGTM

polly/trunk/include/polly/ScopBuilder.h

class ScopBuilder {
   /// accesses that reference arrays that have base pointers that are known to
   /// be equal to the base pointer of such a canonical array to this canonical
   /// array.
   ///
   /// We currently do not canonicalize arrays for which certain memory accesses
   /// have been hoisted as loop invariant.
   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,
                        ScopDetection &SD, ScalarEvolution &SE,
                        OptimizationRemarkEmitter &ORE);
   ScopBuilder(const ScopBuilder &) = delete;
   ScopBuilder &operator=(const ScopBuilder &) = delete;
   ~ScopBuilder() = default;

polly/trunk/include/polly/ScopInfo.h

private:
 
   /// Removes @p Stmt from the StmtMap.
   void removeFromStmtMap(ScopStmt &Stmt);
 
   /// Removes all statements where the entry block of the statement does not
   /// 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
   ///                  of a given type.
   ///
   /// @returns The set of memory accesses in the scop that match the predicate.
   isl::union_map
   getAccessesOfType(std::function<bool(MemoryAccess &)> Predicate);

polly/trunk/include/polly/Support/ScopHelper.h

 class LoopInfo;
 class Loop;
 class ScalarEvolution;
 class SCEV;
 class Region;
 class Pass;
 class DominatorTree;
 class RegionInfo;
+class RegionNode;
 } // namespace llvm
 
 namespace polly {
 class Scop;
 class ScopStmt;
 
 /// Type to remap values.
 using ValueMapT = llvm::DenseMap<llvm::AssertingVH<llvm::Value>,

 ///
 /// For unconditional branches the "i1 true" condition will be returned.
 ///
 /// @param TI The terminator to get the condition from.
 ///
 /// @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.
 /// @param R     The analyzed region.
 /// @param LI    The loop info.
 /// @param SE    The scalar evolution analysis.
 /// @param DT    The dominator tree of the function.
 /// @param KnownInvariantLoads The invariant load set.

polly/trunk/lib/Analysis/ScopBuilder.cpp

 #include "polly/ScopInfo.h"
 #include "polly/Support/GICHelper.h"
 #include "polly/Support/ISLTools.h"
 #include "polly/Support/SCEVValidator.h"
 #include "polly/Support/ScopHelper.h"
 #include "polly/Support/VirtualInstruction.h"
 #include "llvm/ADT/ArrayRef.h"
 #include "llvm/ADT/EquivalenceClasses.h"
+#include "llvm/ADT/PostOrderIterator.h"
 #include "llvm/ADT/Statistic.h"
 #include "llvm/Analysis/AliasAnalysis.h"
 #include "llvm/Analysis/Loads.h"
 #include "llvm/Analysis/LoopInfo.h"
 #include "llvm/Analysis/OptimizationRemarkEmitter.h"
 #include "llvm/Analysis/RegionInfo.h"
 #include "llvm/Analysis/RegionIterator.h"
 #include "llvm/Analysis/ScalarEvolution.h"
void ScopBuilder::buildScalarDependences(ScopStmt *UserStmt,
                                          Instruction *Inst) {
   assert(!isa<PHINode>(Inst));
 
   // Pull-in required operands.
   for (Use &Op : Inst->operands())
     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
   // of a write, we must determine such use here.
   if (scop->isEscaping(Inst))
     ensureValueWrite(Inst);
 }
 
void ScopBuilder::buildScop(Region &R, AssumptionCache &AC) {
   // only the runtime context could become infeasible.
   if (!scop->isProfitable(UnprofitableScalarAccs)) {
     scop->invalidate(PROFITABLE, DebugLoc());
     LLVM_DEBUG(
         dbgs() << "Bailing-out because SCoP is not considered profitable\n");
     return;
   }
 
-  scop->buildSchedule(LI);
+  buildSchedule();
 
   finalizeAccesses();
 
   scop->realignParams();
   addUserContext();
 
   // After the context was fully constructed, thus all our knowledge about
   // the parameters is in there, we add all recorded assumptions to the

polly/trunk/lib/Analysis/ScopInfo.cpp

static cl::opt<bool, true> XUseInstructionNames(
     cl::ZeroOrMore, cl::cat(PollyCategory));
 
 static cl::opt<bool> PollyPrintInstructions(
     "polly-print-instructions", cl::desc("Output instructions per ScopStmt"),
     cl::Hidden, cl::Optional, cl::init(false), cl::cat(PollyCategory));
 
 //===----------------------------------------------------------------------===//
 
-// 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;
   isl::ctx Ctx = S.get_ctx();
 
   // The upper and lower bound for a parameter value is derived either from
   // the data type of the parameter or from the - possibly more restrictive -
   // range metadata.

 getRegionNodeSuccessor(RegionNode *RN, Instruction *TI, unsigned idx) {
   if (RN->isSubRegion()) {
     assert(idx == 0);
     return RN->getNodeAs<Region>()->getExit();
   }
   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())
     return isErrorBlock(*RN->getNodeAs<BasicBlock>(), R, LI, DT);
   for (BasicBlock *BB : RN->getNodeAs<Region>()->blocks())
     if (isErrorBlock(*BB, R, LI, DT))
       return true;
   return false;
if (Affinator.hasNSWAddRecForLoop(L))
     return true;
 
   isl::set UnboundedCtx = Parts.first.params();
   recordAssumption(INFINITELOOP, UnboundedCtx,
                    HeaderBB->getTerminator()->getDebugLoc(), AS_RESTRICTION);
   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;
 
 int Scop::getNextID(std::string ParentFunc) {
   if (ParentFunc != CurrentFunc) {
     CurrentFunc = ParentFunc;
     NextScopID = 0;
for (ScopStmt &Stmt : *this) {
     else
       Stmt.restrictDomain(isl::set(NewStmtDomain));
   }
   return Changed;
 }
 
 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!");
   Stmts.emplace_back(*this, *BB, Name, SurroundingLoop, Instructions);
   auto *Stmt = &Stmts.back();
   StmtMap[BB].push_back(Stmt);
   for (Instruction *Inst : Instructions) {
     assert(!InstStmtMap.count(Inst) &&
#ifndef NDEBUG
   assert(Domain.is_subset(SourceDomain) &&
          "Source access not defined for complete statement domain");
 #endif
   Stmts.emplace_back(*this, SourceRel, TargetRel, Domain);
   CopyStmtsNum++;
   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())
     return {};
   return StmtMapIt->second;
 }
 
 ScopStmt *Scop::getIncomingStmtFor(const Use &U) const {

polly/trunk/lib/Support/ScopHelper.cpp

Value *polly::getConditionFromTerminator(Instruction *TI) {
   }
 
   if (SwitchInst *SI = dyn_cast<SwitchInst>(TI))
     return SI->getCondition();
 
   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)) {
     const SCEV *PtrSCEV = SE.getSCEVAtScope(Val, L);
     Loop *OuterLoop = R.outermostLoopInRegion(L);
     if (!SE.isLoopInvariant(PtrSCEV, OuterLoop))
       return true;
   }