summaryrefslogtreecommitdiffstats
diff options
context:
space:
mode:
Diffstat
-rw-r--r--polly/include/polly/Support/ScopHelper.h14
-rw-r--r--polly/lib/Analysis/ScopDetection.cpp9
-rw-r--r--polly/lib/Analysis/ScopInfo.cpp20
-rw-r--r--polly/lib/Support/ScopHelper.cpp14
-rw-r--r--polly/test/ScopInfo/BoundChecks/single-loop.ll17
-rw-r--r--polly/test/ScopInfo/BoundChecks/two-loops.ll98
6 files changed, 164 insertions, 8 deletions
diff --git a/polly/include/polly/Support/ScopHelper.h b/polly/include/polly/Support/ScopHelper.h
index 05e866c28ee..83fa151e9b1 100644
--- a/polly/include/polly/Support/ScopHelper.h
+++ b/polly/include/polly/Support/ScopHelper.h
@@ -99,5 +99,19 @@ llvm::Value *expandCodeFor(Scop &S, llvm::ScalarEvolution &SE,
const llvm::DataLayout &DL, const char *Name,
const llvm::SCEV *E, llvm::Type *Ty,
llvm::Instruction *IP);
+
+/// @brief Check if the block is a error block.
+///
+/// A error block is currently any block that fullfills at least one of
+/// the following conditions:
+///
+/// - It is terminated by an unreachable instruction
+/// - It contains a call to a function named:
+/// + __ubsan_handle_out_of_bounds
+///
+/// @param BB The block to check.
+///
+/// @return True if the block is a error block, false otherwise.
+bool isErrorBlock(llvm::BasicBlock &BB);
}
#endif
diff --git a/polly/lib/Analysis/ScopDetection.cpp b/polly/lib/Analysis/ScopDetection.cpp
index 45a69cf09cf..3aa116b5a3c 100644
--- a/polly/lib/Analysis/ScopDetection.cpp
+++ b/polly/lib/Analysis/ScopDetection.cpp
@@ -896,14 +896,17 @@ bool ScopDetection::allBlocksValid(DetectionContext &Context) const {
return false;
}
- for (BasicBlock *BB : CurRegion.blocks())
+ for (BasicBlock *BB : CurRegion.blocks()) {
+ // Do not check exception blocks as we will never include them in the SCoP.
+ if (isErrorBlock(*BB))
+ continue;
+
if (!isValidCFG(*BB, Context) && !KeepGoing)
return false;
-
- for (BasicBlock *BB : CurRegion.blocks())
for (BasicBlock::iterator I = BB->begin(), E = --BB->end(); I != E; ++I)
if (!isValidInstruction(*I, Context) && !KeepGoing)
return false;
+ }
if (!hasAffineMemoryAccesses(Context))
return false;
diff --git a/polly/lib/Analysis/ScopInfo.cpp b/polly/lib/Analysis/ScopInfo.cpp
index 0fcde7d308e..dddef6689d1 100644
--- a/polly/lib/Analysis/ScopInfo.cpp
+++ b/polly/lib/Analysis/ScopInfo.cpp
@@ -1554,6 +1554,15 @@ void Scop::buildDomainsWithBranchConstraints(Region *R, LoopInfo &LI,
}
BasicBlock *BB = getRegionNodeBasicBlock(RN);
+ TerminatorInst *TI = BB->getTerminator();
+
+ // Unreachable instructions do not have successors so we can skip them.
+ if (isa<UnreachableInst>(TI)) {
+ // Assume unreachables only in error blocks.
+ assert(isErrorBlock(*BB));
+ continue;
+ }
+
isl_set *Domain = DomainMap[BB];
DEBUG(dbgs() << "\tVisit: " << BB->getName() << " : " << Domain << "\n");
assert(Domain && "Due to reverse post order traversal of the region all "
@@ -1569,7 +1578,7 @@ void Scop::buildDomainsWithBranchConstraints(Region *R, LoopInfo &LI,
// exit node, hence the single entry node domain is the condition set. For
// basic blocks we use the helper function buildConditionSets.
SmallVector<isl_set *, 2> ConditionSets;
- BranchInst *BI = cast<BranchInst>(BB->getTerminator());
+ BranchInst *BI = cast<BranchInst>(TI);
if (RN->isSubRegion())
ConditionSets.push_back(isl_set_copy(Domain));
else
@@ -1738,6 +1747,13 @@ void Scop::propagateDomainConstraints(Region *R, LoopInfo &LI,
// Under the union of all predecessor conditions we can reach this block.
Domain = isl_set_intersect(Domain, PredDom);
+
+ // Add assumptions for error blocks.
+ if (isErrorBlock(*BB)) {
+ IsOptimized = true;
+ isl_set *DomPar = isl_set_params(isl_set_copy(Domain));
+ addAssumption(isl_set_complement(DomPar));
+ }
}
}
@@ -2435,7 +2451,7 @@ bool Scop::restrictDomains(__isl_take isl_union_set *Domain) {
ScalarEvolution *Scop::getSE() const { return SE; }
bool Scop::isTrivialBB(BasicBlock *BB, TempScop &tempScop) {
- if (tempScop.getAccessFunctions(BB))
+ if (tempScop.getAccessFunctions(BB) && !isErrorBlock(*BB))
return false;
return true;
diff --git a/polly/lib/Support/ScopHelper.cpp b/polly/lib/Support/ScopHelper.cpp
index a535f98aa55..69904f0c241 100644
--- a/polly/lib/Support/ScopHelper.cpp
+++ b/polly/lib/Support/ScopHelper.cpp
@@ -331,3 +331,17 @@ Value *polly::expandCodeFor(Scop &S, ScalarEvolution &SE, const DataLayout &DL,
ScopExpander Expander(S.getRegion(), SE, DL, Name);
return Expander.expandCodeFor(E, Ty, IP);
}
+
+bool polly::isErrorBlock(BasicBlock &BB) {
+
+ for (Instruction &Inst : BB)
+ if (CallInst *CI = dyn_cast<CallInst>(&Inst))
+ if (Function *F = CI->getCalledFunction())
+ if (F->getName().equals("__ubsan_handle_out_of_bounds"))
+ return true;
+
+ if (isa<UnreachableInst>(BB.getTerminator()))
+ return true;
+
+ return false;
+}
diff --git a/polly/test/ScopInfo/BoundChecks/single-loop.ll b/polly/test/ScopInfo/BoundChecks/single-loop.ll
index 98c226eb343..3e4f55912b7 100644
--- a/polly/test/ScopInfo/BoundChecks/single-loop.ll
+++ b/polly/test/ScopInfo/BoundChecks/single-loop.ll
@@ -1,5 +1,5 @@
-; RUN: opt %loadPolly -polly-scops -analyze < %s | FileCheck %s
-; XFAIL: *
+; RUN: opt %loadPolly -polly-detect-unprofitable -polly-scops -analyze < %s | FileCheck %s
+; RUN: opt %loadPolly -polly-detect-unprofitable -polly-ast -analyze < %s | FileCheck %s --check-prefix=AST
;
; void exception() __attribute__((noreturn));
;
@@ -18,7 +18,18 @@
; We should detect this kernel as a SCoP and derive run-time conditions such
; that the bound-checked blocks are not part of the optimized SCoP.
-; CHECK: Assumed Context
+; CHECK: Assumed Context:
+; CHECK: [n] -> { : n <= 100 }
+
+; AST: if (n <= 100)
+; AST: for (int c0 = 0; c0 <= min(99, n - 1); c0 += 1)
+; AST: Stmt_if_end_4(c0);
+;
+; AST-NOT: for
+; AST-NOT: Stmt
+;
+; AST: else
+; AST: { /* original code */ }
target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
diff --git a/polly/test/ScopInfo/BoundChecks/two-loops.ll b/polly/test/ScopInfo/BoundChecks/two-loops.ll
new file mode 100644
index 00000000000..3689d51dde6
--- /dev/null
+++ b/polly/test/ScopInfo/BoundChecks/two-loops.ll
@@ -0,0 +1,98 @@
+; RUN: opt %loadPolly -polly-detect-unprofitable -polly-scops -analyze < %s | FileCheck %s
+; RUN: opt %loadPolly -polly-detect-unprofitable -polly-ast -analyze < %s | FileCheck %s --check-prefix=AST
+;
+; void exception() __attribute__((noreturn));
+;
+; void foo(long n, float A[100]) {
+; for (long j = 0; j < n; j++) {
+; for (long i = j; i < n; i++) {
+; if (i < 0)
+; exception();
+;
+; if (i >= 100)
+; exception();
+;
+; A[i] += i;
+; }
+; }
+; }
+;
+; CHECK: Assumed Context:
+; CHECK: [n] -> { : n <= 100 }
+
+; AST: if (n <= 100)
+; AST: for (int c0 = 0; c0 <= min(99, n - 1); c0 += 1)
+; AST: for (int c1 = 0; c1 <= min(n - c0 - 1, -c0 + 99); c1 += 1)
+; AST: Stmt_if_end_7(c0, c1);
+;
+; AST-NOT: for
+; AST-NOT: Stmt
+;
+; AST: else
+; AST: { /* original code */ }
+target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
+
+define void @foo(i64 %n, float* %A) #0 {
+entry:
+ br label %for.cond
+
+for.cond: ; preds = %for.inc.8, %entry
+ %j.0 = phi i64 [ 0, %entry ], [ %inc9, %for.inc.8 ]
+ %cmp = icmp slt i64 %j.0, %n
+ br i1 %cmp, label %for.body, label %for.end.10
+
+for.body: ; preds = %for.cond
+ br label %for.cond.1
+
+for.cond.1: ; preds = %for.inc, %for.body
+ %i.0 = phi i64 [ %j.0, %for.body ], [ %inc, %for.inc ]
+ %cmp2 = icmp slt i64 %i.0, %n
+ br i1 %cmp2, label %for.body.3, label %for.end
+
+for.body.3: ; preds = %for.cond.1
+ br i1 false, label %if.then, label %if.end
+
+if.then: ; preds = %for.body.3
+ call void (...) @exception() #2
+ unreachable
+
+if.end: ; preds = %for.body.3
+ %cmp5 = icmp sgt i64 %i.0, 99
+ br i1 %cmp5, label %if.then.6, label %if.end.7
+
+if.then.6: ; preds = %if.end
+ call void (...) @exception() #2
+ unreachable
+
+if.end.7: ; preds = %if.end
+ %conv = sitofp i64 %i.0 to float
+ %arrayidx = getelementptr inbounds float, float* %A, i64 %i.0
+ %tmp = load float, float* %arrayidx, align 4
+ %add = fadd float %tmp, %conv
+ store float %add, float* %arrayidx, align 4
+ br label %for.inc
+
+for.inc: ; preds = %if.end.7
+ %inc = add nuw nsw i64 %i.0, 1
+ br label %for.cond.1
+
+for.end: ; preds = %for.cond.1
+ br label %for.inc.8
+
+for.inc.8: ; preds = %for.end
+ %inc9 = add nuw nsw i64 %j.0, 1
+ br label %for.cond
+
+for.end.10: ; preds = %for.cond
+ ret void
+}
+
+declare void @exception(...) #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"="+sse,+sse2" "unsafe-fp-math"="false" "use-soft-float"="false" }
+attributes #1 = { noreturn "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"="+sse,+sse2" "unsafe-fp-math"="false" "use-soft-float"="false" }
+attributes #2 = { noreturn nounwind }
+
+!llvm.ident = !{!0}
+
+!0 = !{!"clang version 3.8.0 (trunk 246853)"}
OpenPOWER on IntegriCloud