1 files changed, 78 insertions, 37 deletions

diff --git a/polly/lib/Analysis/ScopInfo.cpp b/polly/lib/Analysis/ScopInfo.cpp
index a56318bf7a3..9c81b432b9f 100644
--- a/polly/lib/Analysis/ScopInfo.cpp
+++ b/polly/lib/Analysis/ScopInfo.cpp
@@ -2118,39 +2118,6 @@ isl_set *Scop::getDomainConditions(BasicBlock *BB) {
   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 @@ bool Scop::buildDomains(Region *R, ScopDetection &SD, DominatorTree &DT,
   // 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 @@ static __isl_give isl_set *adjustDomainDimensions(Scop &S,
   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 @@ Scop::~Scop() {
 
   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 @@ const InvariantEquivClassTy *Scop::lookupInvariantEquivClass(Value *Val) const {
   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);