summaryrefslogtreecommitdiffstats
diff options
context:
space:
mode:
Diffstat
-rw-r--r--polly/include/polly/ScopInfo.h12
-rw-r--r--polly/lib/Analysis/ScopInfo.cpp103
-rw-r--r--polly/test/ScopInfo/user-defined-error-causes-dead-blocks.ll139
3 files changed, 215 insertions, 39 deletions
diff --git a/polly/include/polly/ScopInfo.h b/polly/include/polly/ScopInfo.h
index 8b3c56adde2..5d8614d2967 100644
--- a/polly/include/polly/ScopInfo.h
+++ b/polly/include/polly/ScopInfo.h
@@ -1192,15 +1192,15 @@ private:
void buildDomains(Region *R, LoopInfo &LI, ScopDetection &SD,
DominatorTree &DT);
- /// @brief Check if a basic block is trivial.
+ /// @brief Check if a region part should be represented in the SCoP or not.
///
- /// A trivial basic block does not contain any useful calculation. Therefore,
- /// it does not need to be represented as a polyhedral statement.
+ /// If @p RN does not contain any useful calculation or is only reachable
+ /// via error blocks we do not model it in the polyhedral representation.
///
- /// @param BB The basic block to check
+ /// @param RN The region part to check.
///
- /// @return True if the basic block is trivial, otherwise false.
- bool isTrivialBB(BasicBlock *BB);
+ /// @return True if the part should be ignored, otherwise false.
+ bool isIgnored(RegionNode *RN);
/// @brief Add parameter constraints to @p C that imply a non-empty domain.
__isl_give isl_set *addNonEmptyDomainConstraints(__isl_take isl_set *C) const;
diff --git a/polly/lib/Analysis/ScopInfo.cpp b/polly/lib/Analysis/ScopInfo.cpp
index eb9bff873cd..31c85f6a19e 100644
--- a/polly/lib/Analysis/ScopInfo.cpp
+++ b/polly/lib/Analysis/ScopInfo.cpp
@@ -1693,6 +1693,15 @@ static inline unsigned getNumBlocksInRegionNode(RegionNode *RN) {
return NumBlocks;
}
+static bool containsErrorBlock(RegionNode *RN) {
+ if (!RN->isSubRegion())
+ return isErrorBlock(*RN->getNodeAs<BasicBlock>());
+ for (BasicBlock *BB : RN->getNodeAs<Region>()->blocks())
+ if (isErrorBlock(*BB))
+ return true;
+ return false;
+}
+
///}
static inline __isl_give isl_set *addDomainDimId(__isl_take isl_set *Domain,
@@ -1765,22 +1774,29 @@ void Scop::buildDomainsWithBranchConstraints(Region *R, LoopInfo &LI,
}
}
+ // Error blocks are assumed not to be executed. Therefor they are not
+ // checked properly in the ScopDetection. Any attempt to generate control
+ // conditions from them might result in a crash. However, this is only true
+ // for the first step of the domain generation (this function) where we
+ // push the control conditions of a block to the successors. In the second
+ // step (propagateDomainConstraints) we only receive domain constraints from
+ // the predecessors and can therefor look at the domain of a error block.
+ // That allows us to generate the assumptions needed for them not to be
+ // executed at runtime.
+ if (containsErrorBlock(RN))
+ continue;
+
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));
+ isl_set *Domain = DomainMap.lookup(BB);
+ if (!Domain) {
+ DEBUG(dbgs() << "\tSkip: " << BB->getName()
+ << ", it is only reachable from error blocks.\n");
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 "
- "predecessor of the current region node should have been "
- "visited and a domain for this region node should have "
- "been set.");
Loop *BBLoop = getRegionNodeLoop(RN, LI);
int BBLoopDepth = getRelativeLoopDepth(BBLoop);
@@ -1873,15 +1889,6 @@ getDomainForBlock(BasicBlock *BB, DenseMap<BasicBlock *, isl_set *> &DomainMap,
return getDomainForBlock(R->getEntry(), DomainMap, RI);
}
-static bool containsErrorBlock(RegionNode *RN) {
- if (!RN->isSubRegion())
- return isErrorBlock(*RN->getNodeAs<BasicBlock>());
- for (BasicBlock *BB : RN->getNodeAs<Region>()->blocks())
- if (isErrorBlock(*BB))
- return true;
- return false;
-}
-
void Scop::propagateDomainConstraints(Region *R, LoopInfo &LI,
ScopDetection &SD, DominatorTree &DT) {
// Iterate over the region R and propagate the domain constrains from the
@@ -1909,16 +1916,26 @@ void Scop::propagateDomainConstraints(Region *R, LoopInfo &LI,
}
}
+ // Get the domain for the current block and check if it was initialized or
+ // not. The only way it was not is if this block is only reachable via error
+ // blocks, thus will not be executed under the assumptions we make. Such
+ // blocks have to be skipped as their predecessors might not have domains
+ // either. It would not benefit us to compute the domain anyway, only the
+ // domains of the error blocks that are reachable from non-error blocks
+ // are needed to generate assumptions.
BasicBlock *BB = getRegionNodeBasicBlock(RN);
+ isl_set *&Domain = DomainMap[BB];
+ if (!Domain) {
+ DEBUG(dbgs() << "\tSkip: " << BB->getName()
+ << ", it is only reachable from error blocks.\n");
+ DomainMap.erase(BB);
+ continue;
+ }
+ DEBUG(dbgs() << "\tVisit: " << BB->getName() << " : " << Domain << "\n");
+
Loop *BBLoop = getRegionNodeLoop(RN, LI);
int BBLoopDepth = getRelativeLoopDepth(BBLoop);
- isl_set *&Domain = DomainMap[BB];
- assert(Domain && "Due to reverse post order traversal of the region all "
- "predecessor of the current region node should have been "
- "visited and a domain for this region node should have "
- "been set.");
-
isl_set *PredDom = isl_set_empty(isl_set_get_space(Domain));
for (auto *PredBB : predecessors(BB)) {
@@ -2019,8 +2036,12 @@ void Scop::addLoopBoundsToHeaderDomain(Loop *L, LoopInfo &LI) {
L->getLoopLatches(LatchBlocks);
for (BasicBlock *LatchBB : LatchBlocks) {
- assert(DomainMap.count(LatchBB));
- isl_set *LatchBBDom = DomainMap[LatchBB];
+
+ // If the latch is only reachable via error statements we skip it.
+ isl_set *LatchBBDom = DomainMap.lookup(LatchBB);
+ if (!LatchBBDom)
+ continue;
+
isl_set *BackedgeCondition = nullptr;
TerminatorInst *TI = LatchBB->getTerminator();
@@ -2752,11 +2773,28 @@ bool Scop::restrictDomains(__isl_take isl_union_set *Domain) {
ScalarEvolution *Scop::getSE() const { return SE; }
-bool Scop::isTrivialBB(BasicBlock *BB) {
- if (getAccessFunctions(BB) && !isErrorBlock(*BB))
- return false;
+bool Scop::isIgnored(RegionNode *RN) {
+ BasicBlock *BB = getRegionNodeBasicBlock(RN);
- return true;
+ // Check if there are accesses contained.
+ bool ContainsAccesses = false;
+ if (!RN->isSubRegion())
+ ContainsAccesses = getAccessFunctions(BB);
+ else
+ for (BasicBlock *RBB : RN->getNodeAs<Region>()->blocks())
+ ContainsAccesses |= (getAccessFunctions(RBB) != nullptr);
+ if (!ContainsAccesses)
+ return true;
+
+ // Check for reachability via non-error blocks.
+ if (!DomainMap.count(BB))
+ return true;
+
+ // Check if error blocks are contained.
+ if (containsErrorBlock(RN))
+ return true;
+
+ return false;
}
struct MapToDimensionDataTy {
@@ -2863,14 +2901,13 @@ void Scop::buildSchedule(
auto &LSchedulePair = LoopSchedules[L];
LSchedulePair.second += getNumBlocksInRegionNode(RN);
- BasicBlock *BB = getRegionNodeBasicBlock(RN);
- if (RN->isSubRegion() || !isTrivialBB(BB)) {
+ if (!isIgnored(RN)) {
ScopStmt *Stmt;
if (RN->isSubRegion())
Stmt = addScopStmt(nullptr, RN->getNodeAs<Region>());
else
- Stmt = addScopStmt(BB, nullptr);
+ Stmt = addScopStmt(RN->getNodeAs<BasicBlock>(), nullptr);
auto *UDomain = isl_union_set_from_set(Stmt->getDomain());
auto *StmtSchedule = isl_schedule_from_domain(UDomain);
diff --git a/polly/test/ScopInfo/user-defined-error-causes-dead-blocks.ll b/polly/test/ScopInfo/user-defined-error-causes-dead-blocks.ll
new file mode 100644
index 00000000000..a0ee192620b
--- /dev/null
+++ b/polly/test/ScopInfo/user-defined-error-causes-dead-blocks.ll
@@ -0,0 +1,139 @@
+; RUN: opt %loadPolly -polly-scops -polly-detect-unprofitable -polly-error-functions=timer_start,timer_stop -analyze < %s | FileCheck %s
+;
+; Error blocks are skipped during SCoP detection. Hence, we have to skip
+; them during SCoP too as they might contain accesses or branches we cannot
+; handle. Additionally, some blocks might be only reachable via error blocks.
+; Such blocks should not be considered to be valid and therefor ignored.
+;
+; void timer_start(void);
+; void timer_stop(void);
+; void kernel(int *A, int *B, int timeit, int N) {
+;
+; if (timeit) {
+; timer_start();
+; // split BB
+; A[0] = 0; // Do not create a statement for this block
+; }
+;
+; for (int i = 0; i < N; i++)
+; A[i] += B[i];
+;
+; if (timeit) {
+; timer_stop();
+; if (invalid float branch) // Do not crash on the float branch
+; timer_start();
+; }
+;
+; for (int i = 0; i < N; i++)
+; A[i] += B[i];
+;
+; if (timeit)
+; timer_stop();
+; }
+;
+; The assumed context is empty because all statements are executed only
+; if timeit != 0. This is due to the fact that they are not "reached"
+; by the error blocks that are executed for timeit == 0.
+;
+; CHECK: Region: %entry.split---%if.end.20
+; CHECK: Assumed Context:
+; CHECK-NEXT: [timeit, N] -> { : }
+; CHECK: Statements {
+; CHECK-NOT: Stmt_if_then_split
+; CHECK: Stmt_for_body
+; CHECK-NOT: Stmt_if_then_split
+; CHECK: Stmt_for_body_9
+; CHECK-NOT: Stmt_if_then_split
+; CHECK: }
+;
+target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
+
+define void @kernel(i32* %A, i32* %B, i32 %timeit, i32 %N) {
+entry:
+ br label %entry.split
+
+entry.split:
+ %tobool = icmp eq i32 %timeit, 0
+ br i1 %tobool, label %for.cond.pre, label %if.then
+
+if.then: ; preds = %entry
+ call void @timer_start()
+ br label %if.then.split
+
+; Dead block if we assume if.then not to be executed because of the call
+if.then.split: ; preds = %if.then
+ %A0 = getelementptr inbounds i32, i32* %A, i64 0
+ store i32 0, i32* %A0, align 4
+ br label %for.cond.pre
+
+for.cond.pre:
+ %tmp = sext i32 %N to i64
+ br label %for.cond
+
+for.cond: ; preds = %for.inc, %if.end
+ %indvars.iv1 = phi i64 [ %indvars.iv.next2, %for.inc ], [ 0, %for.cond.pre ]
+ %cmp = icmp slt i64 %indvars.iv1, %tmp
+ br i1 %cmp, label %for.body, label %for.end
+
+for.body: ; preds = %for.cond
+ %arrayidx = getelementptr inbounds i32, i32* %B, i64 %indvars.iv1
+ %tmp3 = load i32, i32* %arrayidx, align 4
+ %arrayidx2 = getelementptr inbounds i32, i32* %A, i64 %indvars.iv1
+ %tmp4 = load i32, i32* %arrayidx2, align 4
+ %add = add nsw i32 %tmp4, %tmp3
+ store i32 %add, i32* %arrayidx2, align 4
+ br label %for.inc
+
+for.inc: ; preds = %for.body
+ %indvars.iv.next2 = add nuw nsw i64 %indvars.iv1, 1
+ br label %for.cond
+
+for.end: ; preds = %for.cond
+ %tobool3 = icmp eq i32 %timeit, 0
+ br i1 %tobool3, label %if.end.5, label %if.then.4
+
+if.then.4: ; preds = %for.end
+ call void @timer_stop()
+ %na = fcmp one float 4.0, 5.0
+ br i1 %na, label %if.end.5, label %if.then.4.rem
+
+if.then.4.rem: ; preds = %for.end
+ call void @timer_start()
+ br label %if.end.5
+
+if.end.5: ; preds = %for.end, %if.then.4
+ %tmp5 = sext i32 %N to i64
+ br label %for.cond.7
+
+for.cond.7: ; preds = %for.inc.15, %if.end.5
+ %indvars.iv = phi i64 [ %indvars.iv.next, %for.inc.15 ], [ 0, %if.end.5 ]
+ %cmp8 = icmp slt i64 %indvars.iv, %tmp5
+ br i1 %cmp8, label %for.body.9, label %for.end.17
+
+for.body.9: ; preds = %for.cond.7
+ %arrayidx11 = getelementptr inbounds i32, i32* %B, i64 %indvars.iv
+ %tmp6 = load i32, i32* %arrayidx11, align 4
+ %arrayidx13 = getelementptr inbounds i32, i32* %A, i64 %indvars.iv
+ %tmp7 = load i32, i32* %arrayidx13, align 4
+ %add14 = add nsw i32 %tmp7, %tmp6
+ store i32 %add14, i32* %arrayidx13, align 4
+ br label %for.inc.15
+
+for.inc.15: ; preds = %for.body.9
+ %indvars.iv.next = add nuw nsw i64 %indvars.iv, 1
+ br label %for.cond.7
+
+for.end.17: ; preds = %for.cond.7
+ %tobool18 = icmp eq i32 %timeit, 0
+ br i1 %tobool18, label %if.end.20, label %if.then.19
+
+if.then.19: ; preds = %for.end.17
+ call void @timer_stop()
+ br label %if.end.20
+
+if.end.20: ; preds = %for.end.17, %if.then.19
+ ret void
+}
+
+declare void @timer_start()
+declare void @timer_stop()
OpenPOWER on IntegriCloud