[FIX] Adjust execution context of hoisted loads wrt. error domains
If we build the domains for error blocks and later remove them we lose
the information that they are not executed. Thus, in the SCoP it looks
like the control will always reach the statement S:
for (i = 0 ... N)
if (*valid == 0)
doSth(&ptr);
S: A[i] = *ptr;
Consequently, we would have assumed "ptr" to be always accessed and
preloaded it unconditionally. However, only if "*valid != 0" we would
execute the optimized version of the SCoP. Nevertheless, we would have
hoisted and accessed "ptr"regardless of "*valid". This changes the
semantic of the program as the value of "*valid" can cause a change of
"ptr" and control if it is executed or not.
To fix this problem we adjust the execution context of hoisted loads
wrt. error domains. To this end we introduce an ErrorDomainCtxMap that
maps each basic block to the error context under which it might be
executed. Thus, to the context under which it is executed but an error
block would have been executed to. To fill this map one traversal of
the blocks in the SCoP suffices. During this traversal we do also
"remove" error statements and those that are only reachable via error
statements. This was previously done by the removeErrorBlockDomains
function which is therefor not needed anymore.
This fixes bug PR26683 and thereby several SPEC miscompiles.
Differential Revision: http://reviews.llvm.org/D18822
llvm-svn: 265778
diff --git a/polly/lib/Analysis/ScopInfo.cpp b/polly/lib/Analysis/ScopInfo.cpp
index a56318b..9c81b43 100644
--- a/polly/lib/Analysis/ScopInfo.cpp
+++ b/polly/lib/Analysis/ScopInfo.cpp
@@ -2118,39 +2118,6 @@
return isl_set_copy(DomainMap[BB]);
}
-void Scop::removeErrorBlockDomains(ScopDetection &SD, DominatorTree &DT,
- LoopInfo &LI) {
- auto removeDomains = [this, &DT](BasicBlock *Start) {
- auto *BBNode = DT.getNode(Start);
- for (auto *ErrorChild : depth_first(BBNode)) {
- auto *ErrorChildBlock = ErrorChild->getBlock();
- auto *CurrentDomain = DomainMap[ErrorChildBlock];
- auto *Empty = isl_set_empty(isl_set_get_space(CurrentDomain));
- DomainMap[ErrorChildBlock] = Empty;
- isl_set_free(CurrentDomain);
- }
- };
-
- SmallVector<Region *, 4> Todo = {&R};
-
- while (!Todo.empty()) {
- auto *SubRegion = Todo.back();
- Todo.pop_back();
-
- if (!SD.isNonAffineSubRegion(SubRegion, &getRegion())) {
- for (auto &Child : *SubRegion)
- Todo.push_back(Child.get());
- continue;
- }
- if (containsErrorBlock(SubRegion->getNode(), getRegion(), LI, DT))
- removeDomains(SubRegion->getEntry());
- }
-
- for (auto *BB : R.blocks())
- if (isErrorBlock(*BB, R, LI, DT))
- removeDomains(BB);
-}
-
bool Scop::buildDomains(Region *R, ScopDetection &SD, DominatorTree &DT,
LoopInfo &LI) {
@@ -2178,12 +2145,17 @@
// Error blocks and blocks dominated by them have been assumed to never be
// executed. Representing them in the Scop does not add any value. In fact,
// it is likely to cause issues during construction of the ScopStmts. The
- // contents of error blocks have not been verfied to be expressible and
+ // contents of error blocks have not been verified to be expressible and
// will cause problems when building up a ScopStmt for them.
// Furthermore, basic blocks dominated by error blocks may reference
// instructions in the error block which, if the error block is not modeled,
- // can themselves not be constructed properly.
- removeErrorBlockDomains(SD, DT, LI);
+ // can themselves not be constructed properly. To this end we will replace
+ // the domains of error blocks and those only reachable via error blocks
+ // with an empty set. Additionally, we will record for each block under which
+ // parameter combination it would be reached via an error block in the
+ // ErrorDomainCtxMap map. This information is needed during load hoisting.
+ propagateErrorConstraints(R, SD, DT, LI);
+
return true;
}
@@ -2246,6 +2218,65 @@
return Dom;
}
+void Scop::propagateErrorConstraints(Region *R, ScopDetection &SD,
+ DominatorTree &DT, LoopInfo &LI) {
+
+ ReversePostOrderTraversal<Region *> RTraversal(R);
+ for (auto *RN : RTraversal) {
+
+ // Recurse for affine subregions but go on for basic blocks and non-affine
+ // subregions.
+ if (RN->isSubRegion()) {
+ Region *SubRegion = RN->getNodeAs<Region>();
+ if (!SD.isNonAffineSubRegion(SubRegion, &getRegion())) {
+ propagateErrorConstraints(SubRegion, SD, DT, LI);
+ continue;
+ }
+ }
+
+ bool ContainsErrorBlock = containsErrorBlock(RN, getRegion(), LI, DT);
+ BasicBlock *BB = getRegionNodeBasicBlock(RN);
+ isl_set *&Domain = DomainMap[BB];
+ assert(Domain && "Cannot propagate a nullptr");
+
+ auto *&ErrorCtx = ErrorDomainCtxMap[BB];
+ auto *DomainCtx = isl_set_params(isl_set_copy(Domain));
+ bool IsErrorBlock = ContainsErrorBlock ||
+ (ErrorCtx && isl_set_is_subset(DomainCtx, ErrorCtx));
+
+ if (IsErrorBlock) {
+ ErrorCtx = ErrorCtx ? isl_set_union(ErrorCtx, DomainCtx) : DomainCtx;
+ auto *EmptyDom = isl_set_empty(isl_set_get_space(Domain));
+ isl_set_free(Domain);
+ Domain = EmptyDom;
+ } else {
+ isl_set_free(DomainCtx);
+ }
+
+ if (!ErrorCtx)
+ continue;
+
+ auto *TI = BB->getTerminator();
+ unsigned NumSuccs = RN->isSubRegion() ? 1 : TI->getNumSuccessors();
+ for (unsigned u = 0; u < NumSuccs; u++) {
+ auto *SuccBB = getRegionNodeSuccessor(RN, TI, u);
+ auto *&SuccErrorCtx = ErrorDomainCtxMap[SuccBB];
+ auto *CurErrorCtx = isl_set_copy(ErrorCtx);
+ SuccErrorCtx =
+ SuccErrorCtx ? isl_set_union(SuccErrorCtx, CurErrorCtx) : CurErrorCtx;
+ SuccErrorCtx = isl_set_coalesce(SuccErrorCtx);
+
+ // Check if the maximal number of domain conjuncts was reached.
+ // In case this happens we will bail.
+ if (isl_set_n_basic_set(SuccErrorCtx) < MaxConjunctsInDomain)
+ continue;
+
+ invalidate(COMPLEXITY, TI->getDebugLoc());
+ return;
+ }
+ }
+}
+
void Scop::propagateDomainConstraintsToRegionExit(
BasicBlock *BB, Loop *BBLoop,
SmallPtrSetImpl<BasicBlock *> &FinishedExitBlocks, ScopDetection &SD,
@@ -2932,6 +2963,8 @@
for (auto It : DomainMap)
isl_set_free(It.second);
+ for (auto It : ErrorDomainCtxMap)
+ isl_set_free(It.second);
// Free the alias groups
for (MinMaxVectorPairTy &MinMaxAccessPair : MinMaxAliasGroups) {
@@ -3044,10 +3077,18 @@
return nullptr;
}
+isl_set *Scop::getErrorCtxReachingStmt(ScopStmt &Stmt) {
+ auto *BB = Stmt.getEntryBlock();
+ return isl_set_copy(ErrorDomainCtxMap.lookup(BB));
+}
+
void Scop::addInvariantLoads(ScopStmt &Stmt, MemoryAccessList &InvMAs) {
- // Get the context under which the statement is executed.
+ // Get the context under which the statement is executed but remove the error
+ // context under which this statement is reached.
isl_set *DomainCtx = isl_set_params(Stmt.getDomain());
+ if (auto *ErrorCtx = getErrorCtxReachingStmt(Stmt))
+ DomainCtx = isl_set_subtract(DomainCtx, ErrorCtx);
DomainCtx = isl_set_remove_redundancies(DomainCtx);
DomainCtx = isl_set_detect_equalities(DomainCtx);
DomainCtx = isl_set_coalesce(DomainCtx);