ScopDetection: Do not detect regions with irreducible control as scops

Polly currently does not support irreducible control and it is probably not
worth supporting. This patch adds code that checks for irreducible control
and refuses regions containing irreducible control.

Polly traditionally had rather restrictive checks on the control flow structure
which would have refused irregular control, but within the last couple of months
most of the control flow restrictions have been removed. As part of this
generalization we accidentally allowed irregular control flow.

Contributed-by: Karthik Senthil and Ajith Pandel
llvm-svn: 258497

5 files changed, 250 insertions, 0 deletions

diff --git a/polly/include/polly/ScopDetection.h b/polly/include/polly/ScopDetection.h
index 5dadd31fa4b..7e76995fc1a 100644
--- a/polly/include/polly/ScopDetection.h
+++ b/polly/include/polly/ScopDetection.h
@@ -198,6 +198,13 @@ private:
   AliasAnalysis *AA;
   //@}
 
+  /// @brief Enum for coloring BBs in Region.
+  ///
+  /// WHITE - Unvisited BB in DFS walk.
+  /// GREY - BBs which are currently on the DFS stack for processing.
+  /// BLACK - Visited and completely processed BB.
+  enum Color { WHITE, GREY, BLACK };
+
   /// @brief Map to remember detection contexts for valid regions.
   using DetectionContextMapTy = DenseMap<const Region *, DetectionContext>;
   mutable DetectionContextMapTy DetectionContextMap;
@@ -452,6 +459,15 @@ private:
   /// @brief Print the locations of all detected scops.
   void printLocations(llvm::Function &F);
 
+  /// @brief Check if a region is reducible or not.
+  ///
+  /// @param Region The region to check.
+  /// @param DbgLoc Parameter to save the location of instruction that
+  ///               causes irregular control flow if the region is irreducible.
+  ///
+  /// @return True if R is reducible, false otherwise.
+  bool isReducibleRegion(Region &R, DebugLoc &DbgLoc) const;
+
   /// @brief Track diagnostics for invalid scops.
   ///
   /// @param Context The context of scop detection.
diff --git a/polly/include/polly/ScopDetectionDiagnostic.h b/polly/include/polly/ScopDetectionDiagnostic.h
index 9f77ac04552..4f16a1c7b52 100644
--- a/polly/include/polly/ScopDetectionDiagnostic.h
+++ b/polly/include/polly/ScopDetectionDiagnostic.h
@@ -62,6 +62,7 @@ enum RejectReasonKind {
   rrkInvalidTerminator,
   rrkCondition,
   rrkLastCFG,
+  rrkIrreducibleRegion,
 
   // Non-Affinity
   rrkAffFunc,
@@ -247,6 +248,29 @@ public:
 };
 
 //===----------------------------------------------------------------------===//
+/// @brief Captures irreducible regions in CFG.
+class ReportIrreducibleRegion : public ReportCFG {
+  Region *R;
+  DebugLoc DbgLoc;
+
+public:
+  ReportIrreducibleRegion(Region *R, DebugLoc DbgLoc)
+      : ReportCFG(rrkIrreducibleRegion), R(R), 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;
+  //@}
+};
+
+//===----------------------------------------------------------------------===//
 /// @brief 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 7e8075d8315..fb58a0bbcc0 100644
--- a/polly/lib/Analysis/ScopDetection.cpp
+++ b/polly/lib/Analysis/ScopDetection.cpp
@@ -65,6 +65,7 @@
 #include "llvm/IR/LLVMContext.h"
 #include "llvm/Support/Debug.h"
 #include <set>
+#include <stack>
 
 using namespace llvm;
 using namespace polly;
@@ -1215,6 +1216,11 @@ 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);
+
   if (!isProfitableRegion(Context))
     return false;
 
@@ -1267,6 +1273,73 @@ void ScopDetection::emitMissedRemarksForLeaves(const Function &F,
   }
 }
 
+bool ScopDetection::isReducibleRegion(Region &R, DebugLoc &DbgLoc) const {
+  BasicBlock *REntry = R.getEntry();
+  BasicBlock *RExit = R.getExit();
+  // Map to match the color of a BasicBlock during the DFS walk.
+  DenseMap<const BasicBlock *, Color> BBColorMap;
+  // Stack keeping track of current BB and index of next child to be processed.
+  std::stack<std::pair<BasicBlock *, unsigned>> DFSStack;
+
+  unsigned AdjacentBlockIndex = 0;
+  BasicBlock *CurrBB, *SuccBB;
+  CurrBB = REntry;
+
+  // Initialize the map for all BB with WHITE color.
+  for (auto *BB : R.blocks())
+    BBColorMap[BB] = ScopDetection::WHITE;
+
+  // Process the entry block of the Region.
+  BBColorMap[CurrBB] = ScopDetection::GREY;
+  DFSStack.push(std::make_pair(CurrBB, 0));
+
+  while (!DFSStack.empty()) {
+    // Get next BB on stack to be processed.
+    CurrBB = DFSStack.top().first;
+    AdjacentBlockIndex = DFSStack.top().second;
+    DFSStack.pop();
+
+    // Loop to iterate over the successors of current BB.
+    const TerminatorInst *TInst = CurrBB->getTerminator();
+    unsigned NSucc = TInst->getNumSuccessors();
+    for (unsigned I = AdjacentBlockIndex; I < NSucc;
+         ++I, ++AdjacentBlockIndex) {
+      SuccBB = TInst->getSuccessor(I);
+
+      // Checks for region exit block and self-loops in BB.
+      if (SuccBB == RExit || SuccBB == CurrBB)
+        continue;
+
+      // WHITE indicates an unvisited BB in DFS walk.
+      if (BBColorMap[SuccBB] == ScopDetection::WHITE) {
+        // Push the current BB and the index of the next child to be visited.
+        DFSStack.push(std::make_pair(CurrBB, I + 1));
+        // Push the next BB to be processed.
+        DFSStack.push(std::make_pair(SuccBB, 0));
+        // First time the BB is being processed.
+        BBColorMap[SuccBB] = ScopDetection::GREY;
+        break;
+      } else if (BBColorMap[SuccBB] == ScopDetection::GREY) {
+        // GREY indicates a loop in the control flow.
+        // If the destination dominates the source, it is a natural loop
+        // else, an irreducible control flow in the region is detected.
+        if (!DT->dominates(SuccBB, CurrBB)) {
+          // Get debug info of instruction which causes irregular control flow.
+          DbgLoc = TInst->getDebugLoc();
+          return false;
+        }
+      }
+    }
+
+    // If all children of current BB have been processed,
+    // then mark that BB as fully processed.
+    if (AdjacentBlockIndex == NSucc)
+      BBColorMap[CurrBB] = ScopDetection::BLACK;
+  }
+
+  return true;
+}
+
 bool ScopDetection::runOnFunction(llvm::Function &F) {
   LI = &getAnalysis<LoopInfoWrapperPass>().getLoopInfo();
   RI = &getAnalysis<RegionInfoPass>().getRegionInfo();
diff --git a/polly/lib/Analysis/ScopDetectionDiagnostic.cpp b/polly/lib/Analysis/ScopDetectionDiagnostic.cpp
index 9b6673c911e..5d5a1a43f8e 100644
--- a/polly/lib/Analysis/ScopDetectionDiagnostic.cpp
+++ b/polly/lib/Analysis/ScopDetectionDiagnostic.cpp
@@ -144,6 +144,23 @@ bool ReportInvalidTerminator::classof(const RejectReason *RR) {
 }
 
 //===----------------------------------------------------------------------===//
+// ReportIrreducibleRegion.
+
+std::string ReportIrreducibleRegion::getMessage() const {
+  return "Irreducible region encountered: " + R->getNameStr();
+}
+
+const DebugLoc &ReportIrreducibleRegion::getDebugLoc() const { return DbgLoc; }
+
+std::string ReportIrreducibleRegion::getEndUserMessage() const {
+  return "Irreducible region encountered in control flow.";
+}
+
+bool ReportIrreducibleRegion::classof(const RejectReason *RR) {
+  return RR->getKind() == rrkIrreducibleRegion;
+}
+
+//===----------------------------------------------------------------------===//
 // ReportAffFunc.
 
 ReportAffFunc::ReportAffFunc(const RejectReasonKind K, const Instruction *Inst)
diff --git a/polly/test/ScopDetectionDiagnostics/ReportIrreducibleRegion.ll b/polly/test/ScopDetectionDiagnostics/ReportIrreducibleRegion.ll
new file mode 100644
index 00000000000..87f8a91dbba
--- /dev/null
+++ b/polly/test/ScopDetectionDiagnostics/ReportIrreducibleRegion.ll
@@ -0,0 +1,120 @@
+; RUN: opt %loadPolly -analyze -polly-detect \
+; RUN:     -pass-remarks-missed="polly-detect" \
+; RUN:     < %s 2>&1| FileCheck %s
+target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
+
+;void foo(int a, int b) {
+;  if(b == 42) {
+;    if (a > 0) {
+;      LABEL1:
+;      a--;
+;    }
+;
+;    if (a > 0) {
+;      goto LABEL1;
+;    }
+;    b = b + 42;
+;  }
+;}
+
+; CHECK: remark: ReportIrreducibleRegion.c:3:7: The following errors keep this region from being a Scop.
+; CHECK-NEXT: remark: ReportIrreducibleRegion.c:9:4: Irreducible region encountered in control flow.
+; CHECK-NEXT: remark: ReportIrreducibleRegion.c:9:4: Invalid Scop candidate ends here.
+
+
+; Function Attrs: nounwind uwtable
+define void @foo(i32 %a, i32 %b) #0 !dbg !4 {
+entry:
+  %a.addr = alloca i32, align 4
+  %b.addr = alloca i32, align 4
+  store i32 %a, i32* %a.addr, align 4
+  call void @llvm.dbg.declare(metadata i32* %a.addr, metadata !11, metadata !12), !dbg !13
+  store i32 %b, i32* %b.addr, align 4
+  call void @llvm.dbg.declare(metadata i32* %b.addr, metadata !14, metadata !12), !dbg !15
+  %0 = load i32, i32* %b.addr, align 4, !dbg !16
+  %cmp = icmp eq i32 %0, 42, !dbg !18
+  br i1 %cmp, label %if.then, label %if.end6, !dbg !19
+
+if.then:                                          ; preds = %entry
+  %1 = load i32, i32* %a.addr, align 4, !dbg !20
+  %cmp1 = icmp sgt i32 %1, 0, !dbg !23
+  br i1 %cmp1, label %if.then2, label %if.end, !dbg !24
+
+if.then2:                                         ; preds = %if.then
+  br label %LABEL1, !dbg !25
+
+LABEL1:                                           ; preds = %if.then4, %if.then2
+  %2 = load i32, i32* %a.addr, align 4, !dbg !27
+  %dec = add nsw i32 %2, -1, !dbg !27
+  store i32 %dec, i32* %a.addr, align 4, !dbg !27
+  br label %if.end, !dbg !29
+
+if.end:                                           ; preds = %LABEL1, %if.then
+  %3 = load i32, i32* %a.addr, align 4, !dbg !30
+  %cmp3 = icmp sgt i32 %3, 0, !dbg !32
+  br i1 %cmp3, label %if.then4, label %if.end5, !dbg !33
+
+if.then4:                                         ; preds = %if.end
+  br label %LABEL1, !dbg !34
+
+if.end5:                                          ; preds = %if.end
+  %4 = load i32, i32* %b.addr, align 4, !dbg !36
+  %add = add nsw i32 %4, 42, !dbg !37
+  store i32 %add, i32* %b.addr, align 4, !dbg !38
+  br label %if.end6, !dbg !39
+
+if.end6:                                          ; preds = %if.end5, %entry
+  ret void, !dbg !40
+}
+
+; Function Attrs: nounwind readnone
+declare void @llvm.dbg.declare(metadata, metadata, metadata) #1
+
+attributes #0 = { nounwind uwtable "disable-tail-calls"="false" "less-precise-fpmad"="false" "no-frame-pointer-elim"="true" "no-frame-pointer-elim-non-leaf" "no-infs-fp-math"="false" "no-nans-fp-math"="false" "stack-protector-buffer-size"="8" "target-cpu"="x86-64" "target-features"="+fxsr,+mmx,+sse,+sse2" "unsafe-fp-math"="false" "use-soft-float"="false" }
+attributes #1 = { nounwind readnone }
+
+!llvm.dbg.cu = !{!0}
+!llvm.module.flags = !{!8, !9}
+!llvm.ident = !{!10}
+
+!0 = distinct !DICompileUnit(language: DW_LANG_C99, file: !1, producer: "clang version 3.8.0 (http://llvm.org/git/clang.git a9b56346a9fa49b176872a2068b479d4ff759ae4) (http://llvm.org/git/llvm.git 82a04b17aeffdf31b7665f927ac42d81e80c07f0)", isOptimized: false, runtimeVersion: 0, emissionKind: 1, enums: !2, subprograms: !3)
+!1 = !DIFile(filename: "ReportIrreducibleRegion.c", directory: "llvm/tools/polly/test/ScopDetectionDiagnostics")
+!2 = !{}
+!3 = !{!4}
+!4 = distinct !DISubprogram(name: "foo", scope: !1, file: !1, line: 1, type: !5, isLocal: false, isDefinition: true, scopeLine: 1, flags: DIFlagPrototyped, isOptimized: false, variables: !2)
+!5 = !DISubroutineType(types: !6)
+!6 = !{null, !7, !7}
+!7 = !DIBasicType(name: "int", size: 32, align: 32, encoding: DW_ATE_signed)
+!8 = !{i32 2, !"Dwarf Version", i32 4}
+!9 = !{i32 2, !"Debug Info Version", i32 3}
+!10 = !{!"clang version 3.8.0 (http://llvm.org/git/clang.git a9b56346a9fa49b176872a2068b479d4ff759ae4) (http://llvm.org/git/llvm.git 82a04b17aeffdf31b7665f927ac42d81e80c07f0)"}
+!11 = !DILocalVariable(name: "a", arg: 1, scope: !4, file: !1, line: 1, type: !7)
+!12 = !DIExpression()
+!13 = !DILocation(line: 1, column: 14, scope: !4)
+!14 = !DILocalVariable(name: "b", arg: 2, scope: !4, file: !1, line: 1, type: !7)
+!15 = !DILocation(line: 1, column: 21, scope: !4)
+!16 = !DILocation(line: 2, column: 5, scope: !17)
+!17 = distinct !DILexicalBlock(scope: !4, file: !1, line: 2, column: 5)
+!18 = !DILocation(line: 2, column: 7, scope: !17)
+!19 = !DILocation(line: 2, column: 5, scope: !4)
+!20 = !DILocation(line: 3, column: 7, scope: !21)
+!21 = distinct !DILexicalBlock(scope: !22, file: !1, line: 3, column: 7)
+!22 = distinct !DILexicalBlock(scope: !17, file: !1, line: 2, column: 14)
+!23 = !DILocation(line: 3, column: 9, scope: !21)
+!24 = !DILocation(line: 3, column: 7, scope: !22)
+!25 = !DILocation(line: 3, column: 14, scope: !26)
+!26 = !DILexicalBlockFile(scope: !21, file: !1, discriminator: 1)
+!27 = !DILocation(line: 5, column: 5, scope: !28)
+!28 = distinct !DILexicalBlock(scope: !21, file: !1, line: 3, column: 14)
+!29 = !DILocation(line: 6, column: 3, scope: !28)
+!30 = !DILocation(line: 8, column: 7, scope: !31)
+!31 = distinct !DILexicalBlock(scope: !22, file: !1, line: 8, column: 7)
+!32 = !DILocation(line: 8, column: 9, scope: !31)
+!33 = !DILocation(line: 8, column: 7, scope: !22)
+!34 = !DILocation(line: 9, column: 4, scope: !35)
+!35 = distinct !DILexicalBlock(scope: !31, file: !1, line: 8, column: 14)
+!36 = !DILocation(line: 11, column: 7, scope: !22)
+!37 = !DILocation(line: 11, column: 9, scope: !22)
+!38 = !DILocation(line: 11, column: 5, scope: !22)
+!39 = !DILocation(line: 12, column: 2, scope: !22)
+!40 = !DILocation(line: 13, column: 1, scope: !4)