[ScopDetection] Do not detect scops that exit to an unreachable

Scops that exit with an unreachable are today still permitted, but make little
sense to optimize. We therefore can already skip them during scop detection.
This speeds up scop detection in certain cases and also ensures that bugpoint
does not introduce unreachables when reducing test cases.

In practice this change should have little impact, as the performance of
unreachable code is unlikely to matter.

This commit is part of a series that makes Polly more robust in the presence
of unreachables.

llvm-svn: 297151

4 files changed, 82 insertions, 1 deletions

diff --git a/polly/include/polly/ScopDetectionDiagnostic.h b/polly/include/polly/ScopDetectionDiagnostic.h
index f53855c50a7..226ed9e9993 100644
--- a/polly/include/polly/ScopDetectionDiagnostic.h
+++ b/polly/include/polly/ScopDetectionDiagnostic.h
@@ -67,6 +67,7 @@ enum class RejectReasonKind {
   CFG,
   InvalidTerminator,
   IrreducibleRegion,
+  UnreachableInExit,
   LastCFG,
 
   // Non-Affinity
@@ -230,6 +231,30 @@ public:
 };
 
 //===----------------------------------------------------------------------===//
+/// Captures regions with an unreachable in the exit block.
+class ReportUnreachableInExit : public ReportCFG {
+  BasicBlock *BB;
+  DebugLoc DbgLoc;
+
+public:
+  ReportUnreachableInExit(BasicBlock *BB, DebugLoc DbgLoc)
+      : ReportCFG(RejectReasonKind::UnreachableInExit), BB(BB), DbgLoc(DbgLoc) {
+  }
+
+  /// @name LLVM-RTTI interface
+  //@{
+  static bool classof(const RejectReason *RR);
+  //@}
+
+  /// @name RejectReason interface
+  //@{
+  virtual std::string getMessage() const override;
+  virtual std::string getEndUserMessage() const override;
+  virtual const DebugLoc &getDebugLoc() const override;
+  //@}
+};
+
+//===----------------------------------------------------------------------===//
 /// Base class for non-affine reject reasons.
 ///
 /// Scop candidates that violate restrictions to affinity are reported under
diff --git a/polly/lib/Analysis/ScopDetection.cpp b/polly/lib/Analysis/ScopDetection.cpp
index a637afa5a41..690655201a1 100644
--- a/polly/lib/Analysis/ScopDetection.cpp
+++ b/polly/lib/Analysis/ScopDetection.cpp
@@ -1428,6 +1428,13 @@ bool ScopDetection::isValidRegion(DetectionContext &Context) const {
     return false;
   }
 
+  DebugLoc DbgLoc;
+  if (isa<UnreachableInst>(CurRegion.getExit()->getTerminator())) {
+    DEBUG(dbgs() << "Unreachable in exit\n");
+    return invalid<ReportUnreachableInExit>(Context, /*Assert=*/true,
+                                            CurRegion.getExit(), DbgLoc);
+  }
+
   if (!CurRegion.getEntry()->getName().count(OnlyRegion)) {
     DEBUG({
       dbgs() << "Region entry does not match -polly-region-only";
@@ -1445,7 +1452,6 @@ bool ScopDetection::isValidRegion(DetectionContext &Context) const {
   if (!allBlocksValid(Context))
     return false;
 
-  DebugLoc DbgLoc;
   if (!isReducibleRegion(CurRegion, DbgLoc))
     return invalid<ReportIrreducibleRegion>(Context, /*Assert=*/true,
                                             &CurRegion, DbgLoc);
diff --git a/polly/lib/Analysis/ScopDetectionDiagnostic.cpp b/polly/lib/Analysis/ScopDetectionDiagnostic.cpp
index b2b566bdffd..ca70018e8fb 100644
--- a/polly/lib/Analysis/ScopDetectionDiagnostic.cpp
+++ b/polly/lib/Analysis/ScopDetectionDiagnostic.cpp
@@ -44,6 +44,7 @@ using namespace llvm;
 llvm::Statistic RejectStatistics[] = {
     SCOP_STAT(CFG, ""),
     SCOP_STAT(InvalidTerminator, "Unsupported terminator instruction"),
+    SCOP_STAT(UnreachableInExit, "Unreachable in exit block"),
     SCOP_STAT(IrreducibleRegion, "Irreducible loops"),
     SCOP_STAT(LastCFG, ""),
     SCOP_STAT(AffFunc, ""),
@@ -190,6 +191,24 @@ bool ReportInvalidTerminator::classof(const RejectReason *RR) {
 }
 
 //===----------------------------------------------------------------------===//
+// UnreachableInExit.
+
+std::string ReportUnreachableInExit::getMessage() const {
+  std::string BBName = BB->getName();
+  return "Unreachable in exit block" + BBName;
+}
+
+const DebugLoc &ReportUnreachableInExit::getDebugLoc() const { return DbgLoc; }
+
+std::string ReportUnreachableInExit::getEndUserMessage() const {
+  return "Unreachable in exit block.";
+}
+
+bool ReportUnreachableInExit::classof(const RejectReason *RR) {
+  return RR->getKind() == RejectReasonKind::UnreachableInExit;
+}
+
+//===----------------------------------------------------------------------===//
 // ReportIrreducibleRegion.
 
 std::string ReportIrreducibleRegion::getMessage() const {
diff --git a/polly/test/ScopDetectionDiagnostics/ReportUnreachableInExit.ll b/polly/test/ScopDetectionDiagnostics/ReportUnreachableInExit.ll
new file mode 100644
index 00000000000..b775d2886f1
--- /dev/null
+++ b/polly/test/ScopDetectionDiagnostics/ReportUnreachableInExit.ll
@@ -0,0 +1,31 @@
+; RUN: opt %loadPolly -polly-detect -analyze < %s \
+; RUN:     -pass-remarks-missed="polly-detect" 2>&1 | FileCheck %s
+
+; void f(long A[], long N) {
+;   long i;
+;   for (i = 0; i < N; ++i)
+;     A[i] = i;
+;   unreachable()
+; }
+
+target datalayout = "e-p:64:64:64-i1:8:8-i8:8:8-i16:16:16-i32:32:32-i64:64:64-f32:32:32-f64:64:64-v64:64:64-v128:128:128-a0:0:64-s0:64:64-f80:128:128"
+
+define void @f(i64* %A, i64 %N) nounwind {
+entry:
+  fence seq_cst
+  br label %for.i
+
+for.i:
+  %indvar = phi i64 [ 0, %entry ], [ %indvar.next, %for.i ]
+  %scevgep = getelementptr i64, i64* %A, i64 %indvar
+  store i64 %indvar, i64* %scevgep
+  %indvar.next = add nsw i64 %indvar, 1
+  %exitcond = icmp eq i64 %indvar.next, %N
+  br i1 %exitcond, label %return, label %for.i
+
+return:
+  fence seq_cst
+  unreachable
+}
+
+; CHECK: Unreachable in exit block