[FIX] Do not create a SCoP in the presence of infinite loops

  If a loop has no exiting blocks the region covering we use during
  schedule genertion might not cover that loop properly. For now we bail
  out as we would not optimize these loops anyway.

llvm-svn: 265260

5 files changed, 103 insertions, 15 deletions

diff --git a/polly/lib/Analysis/ScopDetection.cpp b/polly/lib/Analysis/ScopDetection.cpp
index 594d656a284..c0dba128beb 100644
--- a/polly/lib/Analysis/ScopDetection.cpp
+++ b/polly/lib/Analysis/ScopDetection.cpp
@@ -1029,8 +1029,14 @@ bool ScopDetection::canUseISLTripCount(Loop *L,
   // 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->getLoopLatches(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))
       return false;
diff --git a/polly/lib/Analysis/ScopInfo.cpp b/polly/lib/Analysis/ScopInfo.cpp
index b61d9fa81d7..f3271c20334 100644
--- a/polly/lib/Analysis/ScopInfo.cpp
+++ b/polly/lib/Analysis/ScopInfo.cpp
@@ -3618,8 +3618,15 @@ void Scop::buildSchedule(ScopDetection &SD, LoopInfo &LI) {
   Loop *L = getLoopSurroundingRegion(getRegion(), LI);
   LoopStackTy LoopStack({LoopStackElementTy(L, nullptr, 0)});
   buildSchedule(getRegion().getNode(), LoopStack, SD, LI);
-  assert(LoopStack.size() == 1 && LoopStack.back().L == L);
-  Schedule = LoopStack[0].Schedule;
+  assert(!LoopStack.empty());
+  if (LoopStack.size() == 1 && LoopStack.back().L == L) {
+    Schedule = LoopStack[0].Schedule;
+  } else {
+    // If something went wrong we have to cleanup.
+    assert(!hasFeasibleRuntimeContext());
+    while (!LoopStack.empty())
+      isl_schedule_free(LoopStack.pop_back_val().Schedule);
+  }
 }
 
 /// To generate a schedule for the elements in a Region we traverse the Region
@@ -3662,9 +3669,22 @@ void Scop::buildSchedule(Region *R, LoopStackTy &LoopStack, ScopDetection &SD,
   // 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.
+  unsigned RemainingWork = WorkList.size() + DelayList.size() + 1;
   while (!WorkList.empty() || !DelayList.empty()) {
+    Loop *LastLoop = LoopStack.back().L;
     RegionNode *RN;
 
+    // FIXME: We will bail out if we cannot make progress. So far that is only
+    //        known to happen in the presence of infinite loops without an exit
+    //        edge. For such cases there is no region covering only the loop and
+    //        our reasoning fails.
+    if (WorkList.size() + DelayList.size() >= RemainingWork) {
+      invalidate(INFINITELOOP, R->getEntry()->getTerminator()->getDebugLoc());
+      LastLoop = nullptr;
+    }
+
+    RemainingWork = WorkList.size() + DelayList.size();
+
     if ((LastRNWaiting && !WorkList.empty()) || DelayList.size() == 0) {
       RN = WorkList.front();
       WorkList.pop_front();
@@ -3678,9 +3698,8 @@ void Scop::buildSchedule(Region *R, LoopStackTy &LoopStack, ScopDetection &SD,
     if (!getRegion().contains(L))
       L = OuterScopLoop;
 
-    Loop *LastLoop = LoopStack.back().L;
     if (LastLoop != L) {
-      if (!LastLoop->contains(L)) {
+      if (LastLoop && !LastLoop->contains(L)) {
         LastRNWaiting = true;
         DelayList.push_back(RN);
         continue;
diff --git a/polly/test/ScopInfo/schedule-constuction-endless-loop1.ll b/polly/test/ScopInfo/schedule-constuction-endless-loop1.ll
new file mode 100644
index 00000000000..50af71bb2fe
--- /dev/null
+++ b/polly/test/ScopInfo/schedule-constuction-endless-loop1.ll
@@ -0,0 +1,34 @@
+; RUN: opt %loadPolly -polly-scops -analyze < %s | FileCheck %s
+;
+; Check that we do not build a SCoP and do not crash.
+;
+; CHECK-NOT: Statements
+;
+target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
+
+; Function Attrs: nounwind uwtable
+define void @int_upsample(i32* %A) {
+entry:
+  %0 = load i8, i8* undef, align 1
+  %conv7 = zext i8 %0 to i32
+  br label %while.body.preheader
+
+while.body.preheader:                             ; preds = %entry
+  br label %while.body
+
+while.body:                                       ; preds = %if.end, %while.body.preheader
+  %outrow.036 = phi i32 [ %add23, %if.end ], [ 0, %while.body.preheader ]
+  br i1 true, label %if.end, label %while.body16
+
+while.body16:                                     ; preds = %while.body16, %while.body
+  br label %while.body16
+
+if.end:                                           ; preds = %while.body
+  store i32 0, i32* %A
+  %add23 = add nuw nsw i32 %outrow.036, 1
+  %cmp = icmp slt i32 %add23, 0
+  br i1 %cmp, label %while.body, label %while.end24
+
+while.end24:                                      ; preds = %if.end
+  ret void
+}
diff --git a/polly/test/ScopInfo/schedule-constuction-endless-loop2.ll b/polly/test/ScopInfo/schedule-constuction-endless-loop2.ll
new file mode 100644
index 00000000000..d190ddd6321
--- /dev/null
+++ b/polly/test/ScopInfo/schedule-constuction-endless-loop2.ll
@@ -0,0 +1,37 @@
+; RUN: opt %loadPolly -polly-scops -analyze < %s | FileCheck %s
+;
+; Check that we do not build a SCoP and do not crash.
+;
+; CHECK-NOT: Statements
+;
+target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
+
+; Function Attrs: nounwind uwtable
+define void @int_upsample(i32* %A) {
+entry:
+  %0 = load i8, i8* undef, align 1
+  %conv7 = zext i8 %0 to i32
+  br label %while.body.preheader
+
+while.body.preheader:                             ; preds = %entry
+  br label %while.body
+
+while.body:                                       ; preds = %if.end, %while.body.preheader
+  %outrow.036 = phi i32 [ %add23, %if.end ], [ 0, %while.body.preheader ]
+  br i1 true, label %if.end, label %while.body16
+
+while.body16:                                     ; preds = %while.body16, %while.body
+  br label %while.body16.split
+
+while.body16.split:
+  br label %while.body16
+
+if.end:                                           ; preds = %while.body
+  store i32 0, i32* %A
+  %add23 = add nuw nsw i32 %outrow.036, 1
+  %cmp = icmp slt i32 %add23, 0
+  br i1 %cmp, label %while.body, label %while.end24
+
+while.end24:                                      ; preds = %if.end
+  ret void
+}
diff --git a/polly/test/ScopInfo/two-loops-one-infinite.ll b/polly/test/ScopInfo/two-loops-one-infinite.ll
index 21a4f4ec413..974194f04ca 100644
--- a/polly/test/ScopInfo/two-loops-one-infinite.ll
+++ b/polly/test/ScopInfo/two-loops-one-infinite.ll
@@ -1,16 +1,8 @@
 ; RUN: opt %loadPolly -polly-scops -analyze < %s | FileCheck %s
 ;
-; Verify we detect and create the SCoP correctly
+; Verify we do not create a SCoP in the presence of infinite loops.
 ;
-; CHECK:      Statements {
-; CHECK-NEXT:   Stmt_while_body_us
-; CHECK-NEXT:     Domain :=
-; CHECK-NEXT:       [a13] -> { Stmt_while_body_us[] };
-; CHECK-NEXT:     Schedule :=
-; CHECK-NEXT:       [a13] -> { Stmt_while_body_us[] -> [] };
-; CHECK-NEXT:     MustWriteAccess := [Reduction Type: NONE] [Scalar: 1]
-; CHECK-NEXT:       [a13] -> { Stmt_while_body_us[] -> MemRef_uuu[] };
-; CHECK-NEXT: }
+; CHECK-NOT:      Statements
 ;
 target datalayout = "e-m:e-p:32:32-i64:64-v128:64:128-a:0:32-n8:16:32-S64"