[Polly] Make ScopInfo handle PHI nodes in exit block

[Meinersbur]

Summary

after iterating over all blocks of the region, also iterate over the exit block which normally does not belong to the region. The exit block may contain PHI nodes that will later be moved into the region.

Such PHI nodes cannot yet occur without changes upstream (TempScopInfo, ScopDetection) which will follow.

[jdoerfert]

I am unsure if I missed something but this looks to me like two code extractions into helper functions and hidden in line 1693ff some code that does create an extra statement. I do not mind the first part (extraction) but I have some comments regarding the second:

1. Please commit them separately
2. For the extra statement I think we need at least one test case as well as some motivation how this actually helps us.

[Meinersbur]

In D11869#219805, @jdoerfert wrote:

2. For the extra statement I think we need at least one test case as well as some motivation how this actually helps us.

This patch alone has no effect. See summary.

[Meinersbur]

Rebase to http://reviews.llvm.org/D11878

[grosser]

LGTM. Please merge with other changes to ensure we get test coverage at the first commit.

[Meinersbur]

Merged into D11869

[Meinersbur]

Merged into D11870, not D11869

include/polly/ScopInfo.h

private:
   /// @param R          The region we build the statement for (or null).
   /// @param tempScop   The temp SCoP we use as model.
   /// @param CurRegion  The SCoP region.
   /// @param NestLoops  A vector of all surrounding loops.
   ScopStmt *addScopStmt(BasicBlock *BB, Region *R, TempScop &tempScop,
                         const Region &CurRegion,
                         SmallVectorImpl<Loop *> &NestLoops);
 
+  /// @brief Create the ScopStmt for a BasicBlcok 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 CurRegion  The SCoP region.
+  /// @param NestLoops  A vector of all surrounding loops.
+  ///
+  /// @return The ScopStmt's schedule.
+  __isl_give isl_schedule *buildBBScopStmt(BasicBlock *BB, TempScop &tempScop,
+                                           const Region &CurRegion,
+                                           SmallVectorImpl<Loop *> &NestLoops);
+
+  /// @brief Create a sequence of two schedules.
+  ///
+  /// Either argument may be null and interpreted as the empty schedule.
+  ///
+  /// @param Prev Scheduled before Succ
+  /// @param Succ Scheduled after Prev.
+  ///
+  /// @return The sequence of both schedules or null if empty.
+  __isl_give isl_schedule *
+  ScheduleCombineSequence(__isl_take isl_schedule *Prev,
+                          __isl_take isl_schedule *Succ);
+
   /// @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.

lib/Analysis/ScopInfo.cpp

void Scop::initFromTempScop(TempScop &TempScop, LoopInfo &LI,
                             ScopDetection &SD) {
   buildContext();
 
   SmallVector<Loop *, 8> NestLoops;
 
   // Build the iteration domain, access functions and schedule functions
   // traversing the region tree.
   Schedule = buildScop(TempScop, getRegion(), NestLoops, LI, SD);
+
+  // Build the statement for PHIs in the exit block (never nested in a
+  // scopped-loop)
+  auto StmtSchedule =
+      buildBBScopStmt(getRegion().getExit(), TempScop, getRegion(), NestLoops);
+  Schedule = ScheduleCombineSequence(Schedule, StmtSchedule);
+
   if (!Schedule)
     Schedule = isl_schedule_empty(getParamSpace());
 
   realignParams();
   addParameterBounds();
   simplifyAssumedContext();
 
   assert(NestLoops.empty() && "NestLoops not empty at top level!");
if (BB) {
     Stmts.emplace_back(*this, tempScop, CurRegion, *R, NestLoops);
     Stmt = &Stmts.back();
     for (BasicBlock *BB : R->blocks())
       StmtMap[BB] = Stmt;
   }
   return Stmt;
 }
 
+__isl_give isl_schedule *
+Scop::buildBBScopStmt(BasicBlock *BB, TempScop &tempScop,
+                      const Region &CurRegion,
+                      SmallVectorImpl<Loop *> &NestLoops) {
+  if (isTrivialBB(BB, tempScop))
+    return nullptr;
+
+  auto *Stmt = addScopStmt(BB, nullptr, tempScop, CurRegion, NestLoops);
+  auto *Domain = Stmt->getDomain();
+  return isl_schedule_from_domain(isl_union_set_from_set(Domain));
+}
+
+__isl_give isl_schedule *
+Scop::ScheduleCombineSequence(__isl_take isl_schedule *Prev,
+                              __isl_take isl_schedule *Succ) {
+  if (!Prev)
+    return Succ;
+  if (!Succ)
+    return Prev;
+
+  return isl_schedule_sequence(Prev, Succ);
+}
+
 __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, CurRegion, NestLoops);
     auto *Domain = Stmt->getDomain();
__isl_give isl_schedule *Scop::buildScop(TempScop &tempScop,
   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 {
-      BasicBlock *BB = I->getNodeAs<BasicBlock>();
-
-      if (isTrivialBB(BB, tempScop)) {
-        continue;
-      } else {
-        auto *Stmt = addScopStmt(BB, nullptr, tempScop, CurRegion, NestLoops);
-        auto *Domain = Stmt->getDomain();
-        StmtSchedule = isl_schedule_from_domain(isl_union_set_from_set(Domain));
-      }
+      StmtSchedule = buildBBScopStmt(I->getNodeAs<BasicBlock>(), tempScop,
+                                     CurRegion, NestLoops);
     }
-
-    if (!Schedule)
-      Schedule = StmtSchedule;
-    else if (StmtSchedule)
-      Schedule = isl_schedule_sequence(Schedule, StmtSchedule);
+    Schedule = ScheduleCombineSequence(Schedule, StmtSchedule);
   }
 
   if (!L)
     return Schedule;
 
   auto *Domain = isl_schedule_get_domain(Schedule);
   if (!isl_union_set_is_empty(Domain)) {
     auto *MUPA = mapToDimension(isl_union_set_copy(Domain), loopDepth);