summaryrefslogtreecommitdiffstats
diff options
context:
space:
mode:
Diffstat
-rw-r--r--polly/include/polly/ScopDetection.h16
-rw-r--r--polly/include/polly/ScopDetectionDiagnostic.h24
-rw-r--r--polly/lib/Analysis/ScopDetection.cpp73
-rw-r--r--polly/lib/Analysis/ScopDetectionDiagnostic.cpp17
-rw-r--r--polly/test/ScopDetectionDiagnostics/ReportIrreducibleRegion.ll120
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)
OpenPOWER on IntegriCloud