[ScopDetection] Remove redundant checks for endless loops

Summary:
Both `canUseISLTripCount()` and `addOverApproximatedRegion()` contained checks
to reject endless loops which are now removed and replaced by a single check
in `isValidLoop()`.

For reporting such loops the `ReportLoopOverlapWithNonAffineSubRegion` is
renamed to `ReportLoopHasNoExit`. The test case
`ReportLoopOverlapWithNonAffineSubRegion.ll` is adapted and renamed as well.

The schedule generation in `buildSchedule()` is based on the following
assumption:

Given some block B that is contained in a loop L and a SESE region R,
we assume that L is contained in R or the other way around.

However, this assumption is broken in the presence of endless loops that are
nested inside other loops. Therefore, in order to prevent erroneous behavior
in `buildSchedule()`, r265280 introduced a corresponding check in
`canUseISLTripCount()` to reject endless loops. Unfortunately, it was possible
to bypass this check with -polly-allow-nonaffine-loops which was fixed by adding
another check to reject endless loops in `allowOverApproximatedRegion()` in
r273905. Hence there existed two separate locations that handled this case.

Thank you Johannes Doerfert for helping to provide the above background
information.

Reviewers: Meinersbur, grosser

Subscribers: _jdoerfert, pollydev

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

Contributed-by: Matthias Reisinger <d412vv1n@gmail.com>
llvm-svn: 281987

4 files changed, 62 insertions, 98 deletions

diff --git a/polly/include/polly/ScopDetectionDiagnostic.h b/polly/include/polly/ScopDetectionDiagnostic.h
index 2bdad7dc1ca..125e031d99d 100644
--- a/polly/include/polly/ScopDetectionDiagnostic.h
+++ b/polly/include/polly/ScopDetectionDiagnostic.h
@@ -84,7 +84,7 @@ enum RejectReasonKind {
   rrkLastAffFunc,
 
   rrkLoopBound,
-  rrkLoopOverlapWithNonAffineSubRegion,
+  rrkLoopHasNoExit,
 
   rrkFuncCall,
   rrkNonSimpleMemoryAccess,
@@ -511,22 +511,18 @@ public:
 };
 
 //===----------------------------------------------------------------------===//
-/// Captures errors when loop overlap with nonaffine subregion.
-class ReportLoopOverlapWithNonAffineSubRegion : public RejectReason {
+/// Captures errors when loop has no exit.
+class ReportLoopHasNoExit : public RejectReason {
   //===--------------------------------------------------------------------===//
 
-  /// If L and R are set then L and R overlap.
-
-  /// The loop contains stmt overlapping nonaffine subregion.
+  /// The loop that has no exit.
   Loop *L;
 
-  /// The nonaffine subregion that contains infinite loop.
-  Region *R;
-
   const DebugLoc Loc;
 
 public:
-  ReportLoopOverlapWithNonAffineSubRegion(Loop *L, Region *R);
+  ReportLoopHasNoExit(Loop *L)
+      : RejectReason(rrkLoopHasNoExit), L(L), Loc(L->getStartLoc()) {}
 
   /// @name LLVM-RTTI interface
   //@{
diff --git a/polly/lib/Analysis/ScopDetection.cpp b/polly/lib/Analysis/ScopDetection.cpp
index b891c020410..7df5179dc8d 100644
--- a/polly/lib/Analysis/ScopDetection.cpp
+++ b/polly/lib/Analysis/ScopDetection.cpp
@@ -297,56 +297,10 @@ bool ScopDetection::addOverApproximatedRegion(Region *AR,
   // All loops in the region have to be overapproximated too if there
   // are accesses that depend on the iteration count.
 
-  BoxedLoopsSetTy ARBoxedLoopsSet;
-
   for (BasicBlock *BB : AR->blocks()) {
     Loop *L = LI->getLoopFor(BB);
-    if (AR->contains(L)) {
+    if (AR->contains(L))
       Context.BoxedLoopsSet.insert(L);
-      ARBoxedLoopsSet.insert(L);
-    }
-  }
-
-  // Reject if the surrounding loop does not entirely contain the nonaffine
-  // subregion.
-  // This can happen because a region can contain BBs that have no path to the
-  // exit block (Infinite loops, UnreachableInst), but such blocks are never
-  // part of a loop.
-  //
-  // _______________
-  // | Loop Header | <-----------.
-  // ---------------             |
-  //        |                    |
-  // _______________       ______________
-  // | RegionEntry |-----> | RegionExit |----->
-  // ---------------       --------------
-  //        |
-  // _______________
-  // | EndlessLoop | <--.
-  // ---------------    |
-  //       |            |
-  //       \------------/
-  //
-  // In the example above, the loop (LoopHeader,RegionEntry,RegionExit) is
-  // neither entirely contained in the region RegionEntry->RegionExit
-  // (containing RegionEntry,EndlessLoop) nor is the region entirely contained
-  // in the loop.
-  // The block EndlessLoop is contained is in the region because
-  // Region::contains tests whether it is not dominated by RegionExit. This is
-  // probably to not having to query the PostdominatorTree.
-  // Instead of an endless loop, a dead end can also be formed by
-  // UnreachableInst. This case is already caught by isErrorBlock(). We hence
-  // only have to test whether there is an endless loop not contained in the
-  // surrounding loop.
-  BasicBlock *BBEntry = AR->getEntry();
-  Loop *L = LI->getLoopFor(BBEntry);
-  while (L && AR->contains(L))
-    L = L->getParentLoop();
-  if (L) {
-    for (const auto *ARBoxedLoop : ARBoxedLoopsSet)
-      if (!L->contains(ARBoxedLoop))
-        return invalid<ReportLoopOverlapWithNonAffineSubRegion>(
-            Context, /*Assert=*/true, L, AR);
   }
 
   return (AllowNonAffineSubLoops || Context.BoxedLoopsSet.empty());
@@ -1057,18 +1011,23 @@ bool ScopDetection::isValidInstruction(Instruction &Inst,
   return invalid<ReportUnknownInst>(Context, /*Assert=*/true, &Inst);
 }
 
+/// Check whether @p L has exiting blocks.
+///
+/// @param L The loop of interest
+///
+/// @return True if the loop has exiting blocks, false otherwise.
+static bool hasExitingBlocks(Loop *L) {
+  SmallVector<BasicBlock *, 4> ExitingBlocks;
+  L->getExitingBlocks(ExitingBlocks);
+  return !ExitingBlocks.empty();
+}
+
 bool ScopDetection::canUseISLTripCount(Loop *L,
                                        DetectionContext &Context) const {
   // Ensure the loop has valid exiting blocks as well as latches, otherwise we
   // need to overapproximate it as a boxed loop.
   SmallVector<BasicBlock *, 4> LoopControlBlocks;
   L->getExitingBlocks(LoopControlBlocks);
-
-  // Loops without exiting blocks cannot be handled by the schedule generation
-  // as it depends on a region covering that is not given.
-  if (LoopControlBlocks.empty())
-    return false;
-
   L->getLoopLatches(LoopControlBlocks);
   for (BasicBlock *ControlBB : LoopControlBlocks) {
     if (!isValidCFG(*ControlBB, true, false, Context))
@@ -1080,6 +1039,38 @@ bool ScopDetection::canUseISLTripCount(Loop *L,
 }
 
 bool ScopDetection::isValidLoop(Loop *L, DetectionContext &Context) const {
+  // Loops that contain part but not all of the blocks of a region cannot be
+  // handled by the schedule generation. Such loop constructs can happen
+  // because a region can contain BBs that have no path to the exit block
+  // (Infinite loops, UnreachableInst), but such blocks are never part of a
+  // loop.
+  //
+  // _______________
+  // | Loop Header | <-----------.
+  // ---------------             |
+  //        |                    |
+  // _______________       ______________
+  // | RegionEntry |-----> | RegionExit |----->
+  // ---------------       --------------
+  //        |
+  // _______________
+  // | EndlessLoop | <--.
+  // ---------------    |
+  //       |            |
+  //       \------------/
+  //
+  // In the example above, the loop (LoopHeader,RegionEntry,RegionExit) is
+  // neither entirely contained in the region RegionEntry->RegionExit
+  // (containing RegionEntry,EndlessLoop) nor is the region entirely contained
+  // in the loop.
+  // The block EndlessLoop is contained in the region because Region::contains
+  // tests whether it is not dominated by RegionExit. This is probably to not
+  // having to query the PostdominatorTree. Instead of an endless loop, a dead
+  // end can also be formed by an UnreachableInst. This case is already caught
+  // by isErrorBlock(). We hence only have to reject endless loops here.
+  if (!hasExitingBlocks(L))
+    return invalid<ReportLoopHasNoExit>(Context, /*Assert=*/true, L);
+
   if (canUseISLTripCount(L, Context))
     return true;
 
diff --git a/polly/lib/Analysis/ScopDetectionDiagnostic.cpp b/polly/lib/Analysis/ScopDetectionDiagnostic.cpp
index e74073cecba..eb65dc2c1bb 100644
--- a/polly/lib/Analysis/ScopDetectionDiagnostic.cpp
+++ b/polly/lib/Analysis/ScopDetectionDiagnostic.cpp
@@ -43,8 +43,6 @@ using namespace llvm;
 
 BADSCOP_STAT(CFG, "CFG too complex");
 BADSCOP_STAT(LoopBound, "Loop bounds can not be computed");
-BADSCOP_STAT(LoopOverlapWithNonAffineSubRegion,
-             "Loop overlap with nonaffine subregion");
 BADSCOP_STAT(FuncCall, "Function call with side effects appeared");
 BADSCOP_STAT(AffFunc, "Expression not affine");
 BADSCOP_STAT(Alias, "Found base address alias");
@@ -330,30 +328,20 @@ std::string ReportLoopBound::getEndUserMessage() const {
 }
 
 //===----------------------------------------------------------------------===//
-// ReportLoopOverlapWithNonAffineSubRegion.
+// ReportLoopHasNoExit.
 
-ReportLoopOverlapWithNonAffineSubRegion::
-    ReportLoopOverlapWithNonAffineSubRegion(Loop *L, Region *R)
-    : RejectReason(rrkLoopOverlapWithNonAffineSubRegion), L(L), R(R),
-      Loc(L->getStartLoc()) {
-  ++BadLoopOverlapWithNonAffineSubRegionForScop;
+std::string ReportLoopHasNoExit::getMessage() const {
+  return "Loop " + L->getHeader()->getName() + " has no exit.";
 }
 
-std::string ReportLoopOverlapWithNonAffineSubRegion::getMessage() const {
-  return "Non affine subregion: " + R->getNameStr() + " overlaps Loop " +
-         L->getHeader()->getName();
+bool ReportLoopHasNoExit::classof(const RejectReason *RR) {
+  return RR->getKind() == rrkLoopHasNoExit;
 }
 
-const DebugLoc &ReportLoopOverlapWithNonAffineSubRegion::getDebugLoc() const {
-  return Loc;
-}
-
-bool ReportLoopOverlapWithNonAffineSubRegion::classof(const RejectReason *RR) {
-  return RR->getKind() == rrkLoopOverlapWithNonAffineSubRegion;
-}
+const DebugLoc &ReportLoopHasNoExit::getDebugLoc() const { return Loc; }
 
-std::string ReportLoopOverlapWithNonAffineSubRegion::getEndUserMessage() const {
-  return "Loop overlaps with nonaffine subregion.";
+std::string ReportLoopHasNoExit::getEndUserMessage() const {
+  return "Loop cannot be handled because it has no exit.";
 }
 
 //===----------------------------------------------------------------------===//
diff --git a/polly/test/ScopDetectionDiagnostics/ReportLoopOverlapWithNonAffineSubRegion.ll b/polly/test/ScopDetectionDiagnostics/ReportLoopHasNoExit.ll
index 87b78a3867d..979c339658f 100644
--- a/polly/test/ScopDetectionDiagnostics/ReportLoopOverlapWithNonAffineSubRegion.ll
+++ b/polly/test/ScopDetectionDiagnostics/ReportLoopHasNoExit.ll
@@ -1,5 +1,5 @@
-; RUN: opt %loadPolly -pass-remarks-missed="polly-detect" -polly-allow-nonaffine-loops -analyze  -polly-detect < %s 2>&1 | FileCheck %s --check-prefix=REJECTLOOPOVERLAPREGION
-; RUN: opt %loadPolly -pass-remarks-missed="polly-detect" -polly-allow-nonaffine-loops=false -analyze  -polly-detect < %s 2>&1 | FileCheck %s --check-prefix=REJECTNONAFFINELOOPS
+; RUN: opt %loadPolly -pass-remarks-missed="polly-detect" -polly-allow-nonaffine-loops -analyze  -polly-detect < %s 2>&1 | FileCheck %s
+; RUN: opt %loadPolly -pass-remarks-missed="polly-detect" -polly-allow-nonaffine-loops=false -analyze  -polly-detect < %s 2>&1 | FileCheck %s
 
 ; void func (int param0, int N, int *A)
 ; {
@@ -11,18 +11,7 @@
 ;      A[i] = 2;
 ; }
 
-; If we reject non-affine region and loop will be reported:
-;
-; REJECTLOOPOVERLAPREGION: remark: ReportLoopOverlapWithNonAffineRegion.c:3:3: The following errors keep this region from being a Scop.
-; REJECTLOOPOVERLAPREGION: remark: ReportLoopOverlapWithNonAffineRegion.c:3:3: Loop overlaps with nonaffine subregion.
-; REJECTLOOPOVERLAPREGION: remark: ReportLoopOverlapWithNonAffineRegion.c:7:7: Failed to derive an affine function from the loop bounds.
-; REJECTLOOPOVERLAPREGION: remark: ReportLoopOverlapWithNonAffineRegion.c:7:7: Invalid Scop candidate ends here.
-;
-; If we reject non-affine loops the non-affine loop bound will be reported:
-;
-; REJECTNONAFFINELOOPS: remark: ReportLoopOverlapWithNonAffineRegion.c:7:7: The following errors keep this region from being a Scop.
-; REJECTNONAFFINELOOPS: remark: ReportLoopOverlapWithNonAffineRegion.c:7:7: Failed to derive an affine function from the loop bounds.
-; REJECTNONAFFINELOOPS: remark: ReportLoopOverlapWithNonAffineRegion.c:7:7: Invalid Scop candidate ends here.
+; CHECK: remark: ReportLoopHasNoExit.c:7:7: Loop cannot be handled because it has no exit.
 
 
 
@@ -95,7 +84,7 @@ attributes #1 = { nounwind readnone }
 !llvm.ident = !{!5}
 
 !0 = distinct !DICompileUnit(language: DW_LANG_C99, file: !1, producer: "clang version 3.9.0 ", isOptimized: false, runtimeVersion: 0, emissionKind: FullDebug, enums: !2)
-!1 = !DIFile(filename: "ReportLoopOverlapWithNonAffineRegion.c", directory: "test/ScopDetectionDiagnostics/")
+!1 = !DIFile(filename: "ReportLoopHasNoExit.c", directory: "test/ScopDetectionDiagnostics/")
 !2 = !{}
 !3 = !{i32 2, !"Dwarf Version", i32 4}
 !4 = !{i32 2, !"Debug Info Version", i32 3}