Introduce an invalid context for each statement

  Collect the error domain contexts (formerly in the ErrorDomainCtxMap)
  for each statement in the new InvalidContext member variable. While
  this commit is basically a [NFC] it is a first step to make hoisting
  sound by allowing a more fine grained record of invalid contexts,
  e.g., here on statement level.

llvm-svn: 266053

3 files changed, 68 insertions, 50 deletions

diff --git a/polly/include/polly/ScopInfo.h b/polly/include/polly/ScopInfo.h
index 9a29e6c41a2..f0f078f1173 100644
--- a/polly/include/polly/ScopInfo.h
+++ b/polly/include/polly/ScopInfo.h
@@ -932,6 +932,14 @@ private:
   /// The Scop containing this ScopStmt
   Scop &Parent;
 
+  /// @brief The context under which this statement is not modeled precisely.
+  ///
+  /// The invalid context for a statement describes all parameter combinations
+  /// under which the statement looks to be executed but is in fact not because
+  /// some assumption/restriction makes the statement/scop invalid. Currently
+  /// it is build only using error block domain contexts.
+  isl_set *InvalidContext;
+
   /// The iteration domain describes the set of iterations for which this
   /// statement is executed.
   ///
@@ -1086,6 +1094,14 @@ public:
   /// @brief Get an isl string representing this schedule.
   std::string getScheduleStr() const;
 
+  /// @brief Get the invalid context for this statement.
+  __isl_give isl_set *getInvalidContext() const {
+    return isl_set_copy(InvalidContext);
+  }
+
+  /// @brief Set the invalid context for this statement to @p IC.
+  void setInvalidContext(__isl_take isl_set *IC);
+
   /// @brief Get the BasicBlock represented by this ScopStmt (if any).
   ///
   /// @return The BasicBlock represented by this ScopStmt, or null if the
@@ -1332,14 +1348,6 @@ private:
   /// @brief A map from basic blocks to their domains.
   DenseMap<BasicBlock *, isl_set *> DomainMap;
 
-  /// @brief A map from basic blocks to the error context reaching them.
-  ///
-  /// The error context describes all parameter configurations under which
-  /// the block would be executed but the control would pass an error block.
-  /// This information is not contained in the domain and only implicit in the
-  /// AssumedContext/InvalidContext.
-  DenseMap<BasicBlock *, isl_set *> ErrorDomainCtxMap;
-
   /// Constraints on parameters.
   isl_set *Context;
 
@@ -1517,20 +1525,19 @@ private:
   void propagateDomainConstraints(Region *R, ScopDetection &SD,
                                   DominatorTree &DT, LoopInfo &LI);
 
-  /// @brief Propagate of error block domain contexts through @p R.
+  /// @brief Propagate invalid contexts of statements through @p R.
   ///
-  /// This method will propagate error block domain contexts through @p R
-  /// and thereby fill the ErrorDomainCtxMap map. Additionally, the domains
-  /// of error statements and those only reachable via error statements will
-  /// be replaced by an empty set. Later those will be removed completely from
-  /// the SCoP.
+  /// This method will propagate invalid statement contexts through @p R and at
+  /// the same time add error block domain context to them. Additionally, the
+  /// domains of error statements and those only reachable via error statements
+  /// will be replaced by an empty set. Later those will be removed completely.
   ///
   /// @param R  The currently traversed region.
   /// @param SD The ScopDetection analysis for the current function.
   /// @param DT The DominatorTree for the current function.
   /// @param LI The LoopInfo for the current function.
-  void propagateErrorConstraints(Region *R, ScopDetection &SD,
-                                 DominatorTree &DT, LoopInfo &LI);
+  void propagateInvalidStmtContexts(Region *R, ScopDetection &SD,
+                                    DominatorTree &DT, LoopInfo &LI);
 
   /// @brief Compute the domain for each basic block in @p R.
   ///
@@ -1566,9 +1573,6 @@ private:
   /// @see isIgnored()
   void simplifySCoP(bool RemoveIgnoredStmts, DominatorTree &DT, LoopInfo &LI);
 
-  /// @brief Return the error context under which @p Stmt is reached.
-  __isl_give isl_set *getErrorCtxReachingStmt(ScopStmt &Stmt);
-
   /// @brief Create equivalence classes for required invariant accesses.
   ///
   /// These classes will consolidate multiple required invariant loads from the
diff --git a/polly/lib/Analysis/ScopInfo.cpp b/polly/lib/Analysis/ScopInfo.cpp
index ed9479dda40..4c97cce9afd 100644
--- a/polly/lib/Analysis/ScopInfo.cpp
+++ b/polly/lib/Analysis/ScopInfo.cpp
@@ -1091,6 +1091,7 @@ void ScopStmt::realignParams() {
   for (MemoryAccess *MA : *this)
     MA->realignParams();
 
+  InvalidContext = isl_set_align_params(InvalidContext, Parent.getParamSpace());
   Domain = isl_set_align_params(Domain, Parent.getParamSpace());
 }
 
@@ -1437,13 +1438,15 @@ void ScopStmt::collectSurroundingLoops() {
 }
 
 ScopStmt::ScopStmt(Scop &parent, Region &R)
-    : Parent(parent), Domain(nullptr), BB(nullptr), R(&R), Build(nullptr) {
+    : Parent(parent), InvalidContext(isl_set_empty(Parent.getParamSpace())),
+      Domain(nullptr), BB(nullptr), R(&R), Build(nullptr) {
 
   BaseName = getIslCompatibleName("Stmt_", R.getNameStr(), "");
 }
 
 ScopStmt::ScopStmt(Scop &parent, BasicBlock &bb)
-    : Parent(parent), Domain(nullptr), BB(&bb), R(nullptr), Build(nullptr) {
+    : Parent(parent), InvalidContext(isl_set_empty(Parent.getParamSpace())),
+      Domain(nullptr), BB(&bb), R(nullptr), Build(nullptr) {
 
   BaseName = getIslCompatibleName("Stmt_", &bb, "");
 }
@@ -1605,6 +1608,11 @@ std::string ScopStmt::getScheduleStr() const {
   return Str;
 }
 
+void ScopStmt::setInvalidContext(__isl_take isl_set *IC) {
+  isl_set_free(InvalidContext);
+  InvalidContext = IC;
+}
+
 BasicBlock *ScopStmt::getEntryBlock() const {
   if (isBlockStmt())
     return getBasicBlock();
@@ -1639,7 +1647,10 @@ __isl_give isl_id *ScopStmt::getDomainId() const {
   return isl_set_get_tuple_id(Domain);
 }
 
-ScopStmt::~ScopStmt() { isl_set_free(Domain); }
+ScopStmt::~ScopStmt() {
+  isl_set_free(Domain);
+  isl_set_free(InvalidContext);
+}
 
 void ScopStmt::print(raw_ostream &OS) const {
   OS << "\t" << getBaseName() << "\n";
@@ -2222,9 +2233,9 @@ bool Scop::buildDomains(Region *R, ScopDetection &SD, DominatorTree &DT,
   // 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);
+  // parameter combination it would be reached via an error block in its
+  // InvalidContext. This information is needed during load hoisting.
+  propagateInvalidStmtContexts(R, SD, DT, LI);
 
   return true;
 }
@@ -2288,8 +2299,8 @@ static __isl_give isl_set *adjustDomainDimensions(Scop &S,
   return Dom;
 }
 
-void Scop::propagateErrorConstraints(Region *R, ScopDetection &SD,
-                                     DominatorTree &DT, LoopInfo &LI) {
+void Scop::propagateInvalidStmtContexts(Region *R, ScopDetection &SD,
+                                        DominatorTree &DT, LoopInfo &LI) {
 
   ReversePostOrderTraversal<Region *> RTraversal(R);
   for (auto *RN : RTraversal) {
@@ -2299,23 +2310,24 @@ void Scop::propagateErrorConstraints(Region *R, ScopDetection &SD,
     if (RN->isSubRegion()) {
       Region *SubRegion = RN->getNodeAs<Region>();
       if (!SD.isNonAffineSubRegion(SubRegion, &getRegion())) {
-        propagateErrorConstraints(SubRegion, SD, DT, LI);
+        propagateInvalidStmtContexts(SubRegion, SD, DT, LI);
         continue;
       }
     }
 
     bool ContainsErrorBlock = containsErrorBlock(RN, getRegion(), LI, DT);
     BasicBlock *BB = getRegionNodeBasicBlock(RN);
+    ScopStmt *Stmt = getStmtFor(BB);
     isl_set *&Domain = DomainMap[BB];
     assert(Domain && "Cannot propagate a nullptr");
 
-    auto *&ErrorCtx = ErrorDomainCtxMap[BB];
+    auto *InvalidCtx = Stmt->getInvalidContext();
     auto *DomainCtx = isl_set_params(isl_set_copy(Domain));
-    bool IsErrorBlock = ContainsErrorBlock ||
-                        (ErrorCtx && isl_set_is_subset(DomainCtx, ErrorCtx));
+    bool IsInvalidBlock =
+        ContainsErrorBlock || isl_set_is_subset(DomainCtx, InvalidCtx);
 
-    if (IsErrorBlock) {
-      ErrorCtx = ErrorCtx ? isl_set_union(ErrorCtx, DomainCtx) : DomainCtx;
+    if (IsInvalidBlock) {
+      InvalidCtx = isl_set_coalesce(isl_set_union(InvalidCtx, DomainCtx));
       auto *EmptyDom = isl_set_empty(isl_set_get_space(Domain));
       isl_set_free(Domain);
       Domain = EmptyDom;
@@ -2323,22 +2335,32 @@ void Scop::propagateErrorConstraints(Region *R, ScopDetection &SD,
       isl_set_free(DomainCtx);
     }
 
-    if (!ErrorCtx)
+    if (isl_set_is_empty(InvalidCtx)) {
+      isl_set_free(InvalidCtx);
       continue;
+    }
+
+    Stmt->setInvalidContext(InvalidCtx);
 
     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);
+      auto *SuccStmt = getStmtFor(SuccBB);
+
+      // Skip successors outside the SCoP.
+      if (!SuccStmt)
+        continue;
+
+      auto *SuccInvalidCtx = SuccStmt->getInvalidContext();
+      SuccInvalidCtx = isl_set_union(SuccInvalidCtx, Stmt->getInvalidContext());
+      SuccInvalidCtx = isl_set_coalesce(SuccInvalidCtx);
+      unsigned NumConjucts = isl_set_n_basic_set(SuccInvalidCtx);
+      SuccStmt->setInvalidContext(SuccInvalidCtx);
 
       // 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)
+      if (NumConjucts < MaxConjunctsInDomain)
         continue;
 
       invalidate(COMPLEXITY, TI->getDebugLoc());
@@ -3016,8 +3038,6 @@ 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) {
@@ -3130,18 +3150,12 @@ const InvariantEquivClassTy *Scop::lookupInvariantEquivClass(Value *Val) const {
   return nullptr;
 }
 
-__isl_give 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 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_subtract(DomainCtx, Stmt.getInvalidContext());
   DomainCtx = isl_set_remove_redundancies(DomainCtx);
   DomainCtx = isl_set_detect_equalities(DomainCtx);
   DomainCtx = isl_set_coalesce(DomainCtx);
diff --git a/polly/test/ScopInfo/invariant_loads_complicated_dependences.ll b/polly/test/ScopInfo/invariant_loads_complicated_dependences.ll
index fe88b63d5ec..99cb35c9b3f 100644
--- a/polly/test/ScopInfo/invariant_loads_complicated_dependences.ll
+++ b/polly/test/ScopInfo/invariant_loads_complicated_dependences.ll
@@ -9,7 +9,7 @@
 ; CHECK-NEXT:         Execution Context: [LB, UB] -> {  :  }
 ; CHECK-NEXT:         ReadAccess :=    [Reduction Type: NONE] [Scalar: 0]
 ; CHECK-NEXT:             [LB, UB] -> { Stmt_if_then[i0, i1] -> MemRef_V[0] };
-; CHECK-NEXT:         Execution Context: [LB, UB] -> {  : (UB > LB and UB >= 6) or LB >= 6 }
+; CHECK-NEXT:         Execution Context: [LB, UB] -> {  : LB >= 6 or (UB > LB and UB >= 6) }
 ; CHECK-NEXT:         ReadAccess :=    [Reduction Type: NONE] [Scalar: 0]
 ; CHECK-NEXT:             [LB, UB] -> { Stmt_if_else[i0, i1] -> MemRef_U[0] };
 ; CHECK-NEXT:         Execution Context: [LB, UB] -> {  : LB <= 5 }