[Polly] Reject regions entered by an indirectbr/callbr.

SplitBlockPredecessors is unable to insert an additional BasicBlock
between an indirectbr/callbr terminator and the successor blocks.
This is needed by Polly to normalize the control flow before emitting
its optimzed code.

This patches rejects regions entered by an indirectbr/callbr to not fail
later at code generation.

This fixes llvm.org/PR51964

Recommit with "REQUIRES: asserts" in test that uses statistics.

4 files changed, 106 insertions, 1 deletions

diff --git a/polly/include/polly/ScopDetectionDiagnostic.h b/polly/include/polly/ScopDetectionDiagnostic.h
index 200fb8f47d37..f4c2ee466a39 100644
--- a/polly/include/polly/ScopDetectionDiagnostic.h
+++ b/polly/include/polly/ScopDetectionDiagnostic.h
@@ -73,6 +73,7 @@ enum class RejectReasonKind {
   InvalidTerminator,
   IrreducibleRegion,
   UnreachableInExit,
+  IndirectPredecessor,
   LastCFG,
 
   // Non-Affinity
@@ -276,6 +277,32 @@ public:
 };
 
 //===----------------------------------------------------------------------===//
+/// Captures regions with an IndirectBr predecessor.
+class ReportIndirectPredecessor : public ReportCFG {
+  Instruction *Inst;
+  DebugLoc DbgLoc;
+
+public:
+  ReportIndirectPredecessor(Instruction *Inst, DebugLoc DbgLoc)
+      : ReportCFG(RejectReasonKind::IndirectPredecessor), Inst(Inst),
+        DbgLoc(DbgLoc) {}
+
+  /// @name LLVM-RTTI interface
+  //@{
+  static bool classof(const RejectReason *RR);
+  //@}
+
+  /// @name RejectReason interface
+  //@{
+  std::string getRemarkName() const override;
+  const Value *getRemarkBB() const override;
+  std::string getMessage() const override;
+  std::string getEndUserMessage() const override;
+  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 bf9d7abbbcec..aab87415eb89 100644
--- a/polly/lib/Analysis/ScopDetection.cpp
+++ b/polly/lib/Analysis/ScopDetection.cpp
@@ -1757,6 +1757,13 @@ bool ScopDetection::isValidRegion(DetectionContext &Context) {
     return false;
   }
 
+  for (BasicBlock *Pred : predecessors(CurRegion.getEntry())) {
+    Instruction *PredTerm = Pred->getTerminator();
+    if (isa<IndirectBrInst>(PredTerm) || isa<CallBrInst>(PredTerm))
+      return invalid<ReportIndirectPredecessor>(
+          Context, /*Assert=*/true, PredTerm, PredTerm->getDebugLoc());
+  }
+
   // SCoP cannot contain the entry block of the function, because we need
   // to insert alloca instruction there when translate scalar to array.
   if (!PollyAllowFullFunction &&
diff --git a/polly/lib/Analysis/ScopDetectionDiagnostic.cpp b/polly/lib/Analysis/ScopDetectionDiagnostic.cpp
index a32428583c86..0bac2cfd1555 100644
--- a/polly/lib/Analysis/ScopDetectionDiagnostic.cpp
+++ b/polly/lib/Analysis/ScopDetectionDiagnostic.cpp
@@ -50,8 +50,9 @@ using namespace llvm;
 static 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(UnreachableInExit, "Unreachable in exit block"),
+    SCOP_STAT(IndirectPredecessor, "Branch from indirect terminator"),
     SCOP_STAT(LastCFG, ""),
     SCOP_STAT(AffFunc, ""),
     SCOP_STAT(UndefCond, "Undefined branch condition"),
@@ -240,6 +241,37 @@ bool ReportUnreachableInExit::classof(const RejectReason *RR) {
 }
 
 //===----------------------------------------------------------------------===//
+// IndirectPredecessor.
+
+std::string ReportIndirectPredecessor::getRemarkName() const {
+  return "IndirectPredecessor";
+}
+
+const Value *ReportIndirectPredecessor::getRemarkBB() const {
+  if (Inst)
+    return Inst->getParent();
+  return nullptr;
+}
+
+std::string ReportIndirectPredecessor::getMessage() const {
+  if (Inst)
+    return "Branch from indirect terminator: " + *Inst;
+  return getEndUserMessage();
+}
+
+const DebugLoc &ReportIndirectPredecessor::getDebugLoc() const {
+  return DbgLoc;
+}
+
+std::string ReportIndirectPredecessor::getEndUserMessage() const {
+  return "Branch from indirect terminator.";
+}
+
+bool ReportIndirectPredecessor::classof(const RejectReason *RR) {
+  return RR->getKind() == RejectReasonKind::IndirectPredecessor;
+}
+
+//===----------------------------------------------------------------------===//
 // ReportIrreducibleRegion.
 
 std::string ReportIrreducibleRegion::getRemarkName() const {
diff --git a/polly/test/ScopDetect/callbr.ll b/polly/test/ScopDetect/callbr.ll
new file mode 100644
index 000000000000..1981f0127e87
--- /dev/null
+++ b/polly/test/ScopDetect/callbr.ll
@@ -0,0 +1,39 @@
+; RUN: opt %loadPolly -polly-detect -polly-detect-track-failures -disable-output -pass-remarks-missed=polly-detect < %s 2>&1 | FileCheck %s --check-prefix=REMARK
+; RUN: opt %loadPolly -polly-detect -polly-detect-track-failures -disable-output -stats                            < %s 2>&1 | FileCheck %s --check-prefix=STAT
+; REQUIRES: asserts
+
+; REMARK: Branch from indirect terminator.
+
+; STAT: 1 polly-detect - Number of rejected regions: Branch from indirect terminator
+
+
+target datalayout = "e-m:e-p270:32:32-p271:32:32-p272:64:64-i64:64-f80:128-n8:16:32:64-S128"
+target triple = "x86_64-unknown-linux-gnu"
+
+define void @func(i32 %n, double* noalias nonnull %A) {
+entry:
+  callbr void asm sideeffect "", "X,~{dirflag},~{fpsr},~{flags}"(i8* blockaddress(@func, %for)) #1
+          to label %fallthrough [label %for]
+
+fallthrough:
+  br label %for
+
+for:
+  %j = phi i32 [0, %entry], [0, %fallthrough], [%j.inc, %inc]
+  %j.cmp = icmp slt i32 %j, %n
+  br i1 %j.cmp, label %body, label %exit
+
+    body:
+      store double 42.0, double* %A
+      br label %inc
+
+inc:
+  %j.inc = add nuw nsw i32 %j, 1
+  br label %for
+
+exit:
+  br label %return
+
+return:
+  ret void
+}