[ScopDetection] If a loop is not part of a scop, none of it backedges can be

This patch makes sure that in case a loop is not fully contained within a region
that later forms a SCoP, none of the loop backedges are allowed to be part of
the region. We currently do not support the situation where only some of a loops
backedges are part of a scop. Today, this can break both scop modeling and code
generation. One such breaking test case is for example
test/ScopDetectionDiagnostics/loop_partially_in_scop-2.ll, where we totally
forgot to code generate some of the backedges. Fortunately, it is commonly not
necessary to support these partial loops, it is way more common that either
no backedge is included in a region or all loop backedge are included.

This fixes a recent miscompile in
MultiSource/Benchmarks/MiBench/consumer-typeset which was exposed after
r306477.

llvm-svn: 308113

2 files changed, 33 insertions, 3 deletions

diff --git a/polly/lib/Analysis/ScopDetection.cpp b/polly/lib/Analysis/ScopDetection.cpp
index c56d2cc..27dfc93 100644
--- a/polly/lib/Analysis/ScopDetection.cpp
+++ b/polly/lib/Analysis/ScopDetection.cpp
@@ -1402,9 +1402,19 @@ bool ScopDetection::allBlocksValid(DetectionContext &Context) const {
 
   for (const BasicBlock *BB : CurRegion.blocks()) {
     Loop *L = LI.getLoopFor(BB);
-    if (L && L->getHeader() == BB && CurRegion.contains(L) &&
-        (!isValidLoop(L, Context) && !KeepGoing))
-      return false;
+    if (L && L->getHeader() == BB) {
+      if (CurRegion.contains(L)) {
+        if (!isValidLoop(L, Context) && !KeepGoing)
+          return false;
+      } else {
+        SmallVector<BasicBlock *, 1> Latches;
+        L->getLoopLatches(Latches);
+        for (BasicBlock *Latch : Latches)
+          if (CurRegion.contains(Latch))
+            return invalid<ReportLoopOnlySomeLatches>(Context, /*Assert=*/true,
+                                                      L);
+      }
+    }
   }
 
   for (BasicBlock *BB : CurRegion.blocks()) {
diff --git a/polly/lib/Analysis/ScopDetectionDiagnostic.cpp b/polly/lib/Analysis/ScopDetectionDiagnostic.cpp
index ca70018..ffc259f 100644
--- a/polly/lib/Analysis/ScopDetectionDiagnostic.cpp
+++ b/polly/lib/Analysis/ScopDetectionDiagnostic.cpp
@@ -60,6 +60,7 @@ llvm::Statistic RejectStatistics[] = {
     SCOP_STAT(LastAffFunc, ""),
     SCOP_STAT(LoopBound, "Uncomputable loop bounds"),
     SCOP_STAT(LoopHasNoExit, "Loop without exit"),
+    SCOP_STAT(LoopOnlySomeLatches, "Not all loop latches in scop"),
     SCOP_STAT(FuncCall, "Function call with side effects"),
     SCOP_STAT(NonSimpleMemoryAccess,
               "Compilated access semantics (volatile or atomic)"),
@@ -393,6 +394,25 @@ std::string ReportLoopHasNoExit::getEndUserMessage() const {
 }
 
 //===----------------------------------------------------------------------===//
+// ReportLoopOnlySomeLatches
+
+std::string ReportLoopOnlySomeLatches::getMessage() const {
+  return "Not all latches of loop " + L->getHeader()->getName() +
+         " part of scop.";
+}
+
+bool ReportLoopOnlySomeLatches::classof(const RejectReason *RR) {
+  return RR->getKind() == RejectReasonKind::LoopHasNoExit;
+}
+
+const DebugLoc &ReportLoopOnlySomeLatches::getDebugLoc() const { return Loc; }
+
+std::string ReportLoopOnlySomeLatches::getEndUserMessage() const {
+  return "Loop cannot be handled because not all latches are part of loop "
+         "region.";
+}
+
+//===----------------------------------------------------------------------===//
 // ReportFuncCall.
 
 ReportFuncCall::ReportFuncCall(Instruction *Inst)