Allow general loops with one latch

[jdoerfert]

Summary

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.

[grosser]

Two small comments, otherwise this looks good to me.

Tobias

P.S: Please remember to add [Polly] as a tag to not confuse LLVM developers.

lib/Analysis/ScopDetection.cpp

706

typo: a valid exiting

lib/Analysis/ScopInfo.cpp

1708

Is it necessary to move this code around? This seems to unnecessarily complicate the diff

[Meinersbur]

include/polly/ScopInfo.h

654

This change looks unrelated

lib/Analysis/ScopInfo.cpp

981

Can we have an assert here to ensure that the id has been set before?

1494

Rename to setDomainDimId?
"add" made me think it would append another dimension.

1515

for (int LD = getRelativeLoopDepth(LI.getLoopFor(EntryBB)); LD >= 0; LD-=1)

2137

This may make sense to create an element, but looks wrong.

2139

Schedule = LoopSchedules.count(L) ? LoopSchedules[L].first : nullptr;

as alternative to line 2137

2547

isl_set *LDomain

2552

Loop *PL

lib/Support/ScopHelper.cpp

36

Really good this finally does away

[llvm-commits]

I agree with most comments but I am kinda busy right now. I will come
back to this though.

• msg-2386-361.dat219 BDownload
• msg-2386-362.txt162 BDownload

include/polly/ScopInfo.h

 public:
   /// @brief List to hold all (scalar) memory accesses mapped to an instruction.
   using MemoryAccessList = std::forward_list<MemoryAccess>;
 
   ScopStmt(const ScopStmt &) = delete;
   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
   //@{
 
   /// The Scop containing this ScopStmt
   Scop &Parent;
 
private:
   /// @brief The region represented by this statement (in the non-affine case).
   Region *R;
 
   ///}
 
   /// @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;
 
   /// Build the statement.
   //@{
   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.
   /// @param Block          The basic block for which accesses should be
   ///                       created.
   /// @param isApproximated Flag to indicate blocks that might not be executed,
   ///                       hence for which write accesses need to be modeled as
   ///                       may-write accesses.
private:
   /// @brief Create a new SCoP statement for either @p BB or @p R.
   ///
   /// Either @p BB or @p R should be non-null. A new statement for the non-null
   /// argument will be created and added to the statement vector and map.
   ///
   /// @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.
-  ///
-  /// @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.
+  /// @brief Build Schedule and ScopStmts from a given TempScop.
   ///
-  /// @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.
   ///
   ///{
   void printContext(raw_ostream &OS) const;
   void printArrayInfo(raw_ostream &OS) const;
   void printStatements(raw_ostream &OS) const;
   void printAliasAssumptions(raw_ostream &OS) const;

lib/Analysis/ScopDetection.cpp

if (!isAffineExpr(&CurRegion, LHS, *SE) ||
         !isAffineExpr(&CurRegion, RHS, *SE)) {
       if (!AllowNonAffineSubRegions ||
           !addOverApproximatedRegion(RI->getRegionFor(&BB), Context))
         return invalid<ReportNonAffBranch>(Context, /*Assert=*/true, &BB, LHS,
                                            RHS, ICmp);
     }
   }
 
-  // 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;
 }
 
 bool ScopDetection::isValidCallInst(CallInst &CI) {
   if (CI.doesNotReturn())
     return false;
 
   if (CI.doesNotAccessMemory())
bool ScopDetection::isValidInstruction(Instruction &Inst,
   }
 
   // We do not know this instruction, therefore we assume it is invalid.
   return invalid<ReportUnknownInst>(Context, /*Assert=*/true, &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 a 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);
 }
 
 bool ScopDetection::hasMoreThanOneLoop(Region *R) const {
   auto LoopNum = 0;
 
   auto L = LI->getLoopFor(R->getEntry());
   L = L ? R->outermostLoopInRegion(L) : nullptr;

lib/Analysis/ScopInfo.cpp

 #include "polly/Support/ScopHelper.h"
 #include "polly/CodeGen/BlockGenerators.h"
 #include "llvm/ADT/MapVector.h"
 #include "llvm/ADT/SetVector.h"
 #include "llvm/ADT/Statistic.h"
 #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"
 #include "llvm/Analysis/ScalarEvolutionExpressions.h"
 #include "llvm/Support/Debug.h"
 #include "isl/aff.h"
 #include "isl/constraint.h"
 #include "isl/local_space.h"
if (auto *CCond = dyn_cast<ConstantInt>(Condition)) {
     assert(ICond &&
            "Condition of exiting branch was neither constant nor ICmp!");
 
     ScalarEvolution &SE = *S.getSE();
     isl_pw_aff *LHS, *RHS;
     LHS = S.getPwAff(SE.getSCEVAtScope(ICond->getOperand(0), L), Domain);
     RHS = S.getPwAff(SE.getSCEVAtScope(ICond->getOperand(1), L), Domain);
     ConsequenceCondSet = buildConditionSet(ICond->getPredicate(), LHS, RHS);
+
+    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);
   isl_set *AlternativeCondSet =
       isl_set_complement(isl_set_copy(ConsequenceCondSet));
 
   ConditionSets.push_back(isl_set_coalesce(
       isl_set_intersect(ConsequenceCondSet, isl_set_copy(Domain))));

 }
 
 void ScopStmt::deriveAssumptions(BasicBlock *Block) {
   for (Instruction &Inst : *Block)
     if (auto *GEP = dyn_cast<GetElementPtrInst>(&Inst))
       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()) {
     buildAccesses(tempScop, Block, Block != EntryBB);
     deriveAssumptions(Block);
   }
   if (DetectReductions)
     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)
     checkForReductions();
 }
 
 /// @brief Collect loads which might form a reduction chain with @p StoreMA
 ///
static inline Loop *getRegionNodeLoop(RegionNode *RN, LoopInfo &LI) {
 
   Region *NonAffineSubRegion = RN->getNodeAs<Region>();
   Loop *L = LI.getLoopFor(NonAffineSubRegion->getEntry());
   while (L && NonAffineSubRegion->contains(L))
     L = L->getParentLoop();
   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();
   return isl_set_copy(DomainMap[BB]);
 }
 
 void Scop::buildDomains(Region *R, LoopInfo &LI, ScopDetection &SD,
                         DominatorTree &DT) {
 
   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);
   addLoopBoundsToHeaderDomains(LI, SD, DT);
   propagateDomainConstraints(R, LI, SD, DT);
 }
 
 void Scop::buildDomainsWithBranchConstraints(Region *R, LoopInfo &LI,
for (unsigned u = 0, e = ConditionSets.size(); u < e; u++) {
         // adjust the dimensionality accordingly. Lastly, if we leave a loop
         // and enter a new one we need to drop the old constraints.
         int SuccBBLoopDepth = getRelativeLoopDepth(SuccBBLoop);
         assert(std::abs(BBLoopDepth - SuccBBLoopDepth) <= 1);
         if (BBLoopDepth > SuccBBLoopDepth) {
           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);
         }
       }
 
       // Set the domain for the successor or merge it with an existing domain in
       // case there are multiple paths (without loop back edges) to the
       // successor block.
       isl_set *&SuccDomain = DomainMap[SuccBB];
       if (!SuccDomain)
if (DIt != DomainMap.end())
     return isl_set_copy(DIt->getSecond());
 
   Region *R = RI.getRegionFor(BB);
   while (R->getEntry() == BB)
     R = R->getParent();
   return getDomainForBlock(R->getEntry(), DomainMap, RI);
 }
 
+struct MapToDimensionDataTy {
+  int N;
+  isl_union_pw_multi_aff *Res;
+};
+
+// @brief Create a function that maps the elements of 'Set' to its N-th
+//        dimension.
+//
+// The result is added to 'User->Res'.
+//
+// @param Set The input set.
+// @param N   The dimension to map to.
+//
+// @returns   Zero if no error occurred, non-zero otherwise.
+static isl_stat mapToDimension_AddSet(__isl_take isl_set *Set, void *User) {
+  struct MapToDimensionDataTy *Data = (struct MapToDimensionDataTy *)User;
+  int Dim;
+  isl_space *Space;
+  isl_pw_multi_aff *PMA;
+
+  Dim = isl_set_dim(Set, isl_dim_set);
+  Space = isl_set_get_space(Set);
+  PMA = isl_pw_multi_aff_project_out_map(Space, isl_dim_set, Data->N,
+                                         Dim - Data->N);
+  if (Data->N > 1)
+    PMA = isl_pw_multi_aff_drop_dims(PMA, isl_dim_out, 0, Data->N - 1);
+  Data->Res = isl_union_pw_multi_aff_add_pw_multi_aff(Data->Res, PMA);
+
+  isl_set_free(Set);
+
+  return isl_stat_ok;
+}
+
+// @brief Create a function that maps the elements of Domain to their Nth
+//        dimension.
+//
+// @param Domain The set of elements to map.
+// @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;
+
+  Space = isl_union_set_get_space(Domain);
+  Data.N = N;
+  Data.Res = isl_union_pw_multi_aff_empty(Space);
+  if (isl_union_set_foreach_set(Domain, &mapToDimension_AddSet, &Data) < 0)
+    Data.Res = isl_union_pw_multi_aff_free(Data.Res);
+
+  isl_union_set_free(Domain);
+  return isl_multi_union_pw_aff_from_union_pw_multi_aff(Data.Res);
+}
+
 void Scop::propagateDomainConstraints(Region *R, LoopInfo &LI,
                                       ScopDetection &SD, DominatorTree &DT) {
   // Iterate over the region R and propagate the domain constrains from the
   // predecessors to the current node. In contrast to the
   // buildDomainsWithBranchConstraints function, this one will pull the domain
   // information from the predecessors instead of pushing it to the successors.
   // Additionally, we assume the domains to be already present in the domain
   // map here. However, we iterate again in reverse post order so we know all
for (AliasGroupTy &AG : AliasGroups) {
 
     if (!Valid)
       return false;
   }
 
   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) {
 
   const ScopDetection::BoxedLoopsSetTy *BoxedLoops = SD.getBoxedLoops(&R);
 
   unsigned MinLD = INT_MAX, MaxLD = 0;
   for (BasicBlock *BB : R.blocks()) {
     if (Loop *L = LI.getLoopFor(BB)) {
: DT(DT), SE(&ScalarEvolution), R(R), IsOptimized(false),
       IslCtx(Context), Affinator(this) {}
 
 void Scop::initFromTempScop(TempScop &TempScop, LoopInfo &LI, ScopDetection &SD,
                             AliasAnalysis &AA) {
   buildContext();
 
   buildDomains(&R, LI, SD, DT);
 
-  SmallVector<Loop *, 8> NestLoops;
+  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,
                                ScalarEvolution &SE, ScopDetection &SD,
                                AliasAnalysis &AA, DominatorTree &DT,
                                isl_ctx *ctx) {
   auto &R = TempScop.getMaxRegion();
   auto MaxLoopDepth = getMaxLoopDepthInRegion(R, LI, SD);

 
 bool Scop::isTrivialBB(BasicBlock *BB, TempScop &tempScop) {
   if (tempScop.getAccessFunctions(BB))
     return false;
 
   return true;
 }
 
-struct MapToDimensionDataTy {
-  int N;
-  isl_union_pw_multi_aff *Res;
-};
-
-// @brief Create a function that maps the elements of 'Set' to its N-th
-//        dimension.
-//
-// The result is added to 'User->Res'.
-//
-// @param Set The input set.
-// @param N   The dimension to map to.
-//
-// @returns   Zero if no error occurred, non-zero otherwise.
-static isl_stat mapToDimension_AddSet(__isl_take isl_set *Set, void *User) {
-  struct MapToDimensionDataTy *Data = (struct MapToDimensionDataTy *)User;
-  int Dim;
-  isl_space *Space;
-  isl_pw_multi_aff *PMA;
-
-  Dim = isl_set_dim(Set, isl_dim_set);
-  Space = isl_set_get_space(Set);
-  PMA = isl_pw_multi_aff_project_out_map(Space, isl_dim_set, Data->N,
-                                         Dim - Data->N);
-  if (Data->N > 1)
-    PMA = isl_pw_multi_aff_drop_dims(PMA, isl_dim_out, 0, Data->N - 1);
-  Data->Res = isl_union_pw_multi_aff_add_pw_multi_aff(Data->Res, PMA);
-
-  isl_set_free(Set);
-
-  return isl_stat_ok;
-}
-
-// @brief Create a function that maps the elements of Domain to their Nth
-//        dimension.
-//
-// @param Domain The set of elements to map.
-// @param N      The dimension to map to.
-static __isl_give isl_multi_union_pw_aff *
-mapToDimension(__isl_take isl_union_set *Domain, int N) {
-  struct MapToDimensionDataTy Data;
-  isl_space *Space;
-
-  Space = isl_union_set_get_space(Domain);
-  Data.N = N;
-  Data.Res = isl_union_pw_multi_aff_empty(Space);
-  if (isl_union_set_foreach_set(Domain, &mapToDimension_AddSet, &Data) < 0)
-    Data.Res = isl_union_pw_multi_aff_free(Data.Res);
-
-  isl_union_set_free(Domain);
-  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;
   }
   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));
-}
-
-__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));
-  }
-
-  Loop *L = castToLoop(CurRegion, LI);
-
-  if (L)
-    NestLoops.push_back(L);
-
-  unsigned loopDepth = NestLoops.size();
-  isl_schedule *Schedule = nullptr;
-
-  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);
+  ReversePostOrderTraversal<Region *> RTraversal(R);
+  for (auto *RN : RTraversal) {
+
+    if (RN->isSubRegion()) {
+      Region *SubRegion = RN->getNodeAs<Region>();
+      if (!SD.isNonAffineSubRegion(SubRegion, &getRegion())) {
+        buildSchedule(SubRegion, TS, LI, SD, LoopSchedules);
+        continue;
       }
-    Schedule = combineInSequence(Schedule, StmtSchedule);
     }
 
-  if (!L)
-    return Schedule;
+    Loop *L = getRegionNodeLoop(RN, LI);
+    int LD = getRelativeLoopDepth(L);
+    auto &LSchedulePair = LoopSchedules[L];
+    LSchedulePair.second += getNumBlocksInRegionNode(RN);
 
-  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);
-  }
-  isl_union_set_free(Domain);
+    BasicBlock *BB = getRegionNodeBasicBlock(RN);
+    if (RN->isSubRegion() || !isTrivialBB(BB, TS)) {
 
-  NestLoops.pop_back();
-  return Schedule;
+      ScopStmt *Stmt;
+      if (RN->isSubRegion())
+        Stmt = addScopStmt(nullptr, RN->getNodeAs<Region>(), TS);
+      else
+        Stmt = addScopStmt(BB, nullptr, TS);
+
+      auto *UDomain = isl_union_set_from_set(Stmt->getDomain());
+      auto *StmtSchedule = isl_schedule_from_domain(UDomain);
+      LSchedulePair.first =
+          combineInSequence(LSchedulePair.first, StmtSchedule);
+    }
+
+    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;
+    }
+  }
 }
 
 ScopStmt *Scop::getStmtForBasicBlock(BasicBlock *BB) const {
   auto StmtMapIt = StmtMap.find(BB);
   if (StmtMapIt == StmtMap.end())
     return nullptr;
   return StmtMapIt->second;
 }

lib/Support/ScopHelper.cpp

 #include "llvm/Support/Debug.h"
 #include "llvm/Transforms/Utils/BasicBlockUtils.h"
 
 using namespace llvm;
 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();
   else if (StoreInst *store = dyn_cast<StoreInst>(&Inst))
     return store->getPointerOperand();
   else if (GetElementPtrInst *gep = dyn_cast<GetElementPtrInst>(&Inst))
     return gep->getPointerOperand();
 

test/ScopInfo/phi_condition_modeling_2.ll

 ; RUN: opt %loadPolly -polly-detect-unprofitable -analyze -polly-scops < %s | FileCheck %s
 ;
 ;    void f(int *A, int c, int N) {
 ;      int tmp;
 ;      for (int i = 0; i < N; i++) {
 ;        if (i > c)
 ;          tmp = 3;
 ;        else
 ;          tmp = 5;
 ;        A[i] = tmp;
 ;      }
 ;    }
 ;
 ; 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
 ; CHECK:            ReadAccess := [Reduction Type: NONE] [Scalar: 1]
 ; CHECK:                [N, c] -> { Stmt_bb8[i0] -> MemRef_tmp_0__phi[] };
 ; CHECK-NOT: Access
 ; CHECK:            MustWriteAccess :=  [Reduction Type: NONE] [Scalar: 1]
 ; CHECK:                [N, c] -> { Stmt_bb8[i0] -> MemRef_tmp_0[] };