[Polly][FIX] Adjust execution context of hoisted loads wrt. error domains

[jdoerfert]

Summary

      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.

[Meinersbur]

The summary does not mention this is supposed to fix PR26683 or what was wrong with hoisted loads before.
There's a typo: s/therefor/therefore

include/polly/ScopInfo.h

1320 ↗

(On Diff #52778)

Could you explain somewhere what an 'error context' is?

1427–1441 ↗

(On Diff #52778)

Maybe this and the implementation could be moved to where removeErrorBlockDomains was to make clear it's a replacement.

lib/Analysis/ScopInfo.cpp

2178–2185 ↗

(On Diff #52778)

The comment still applies for the most part, doesn't it?

2212–2223 ↗

(On Diff #52778)

I have not better immediate solution but would like to remark the following:

• This pattern occurs multiple times (buildDomainsWithBranchConstraints, propagateDomainConstraints, propagateErrorConstraints) so it might make sense to wrap it.
• The comment of ReversePostOrderTraversal mentions it is expensive to create
• Why does it need to be recursive over nested regions, instead non-recursive over BB reverse post-order?

2242 ↗

(On Diff #52778)

else

3070–3071 ↗

(On Diff #52778)

Isn't it enough just use the union of all error domains (or the context) instead per-stmt?

That domain could contain the hoisted value itself, but which could be just outprojected.

test/ScopInfo/error-blocks-1.ll

10–20 ↗

(On Diff #52778)

Because there is no load hoisting, what dos this patch change in this test case?

test/ScopInfo/error-blocks-2.ll

9 ↗

(On Diff #52778)

Are the invariant accesses ordered? Is the previous invariant access for MemRef_valid guaranteed to be executed before this and to use valid_val ?

[jdoerfert]

In D18822#393262, @Meinersbur wrote:

The summary does not mention this is supposed to fix PR26683 or what was wrong with hoisted loads before.

It does and the code shown there is a test case here. I can mention it.

There's a typo: s/therefor/therefore

Thx.

include/polly/ScopInfo.h

1320 ↗

(On Diff #52778)

Sure.

1427–1441 ↗

(On Diff #52778)

If you think that is better, sure.

lib/Analysis/ScopInfo.cpp

2178–2185 ↗

(On Diff #52778)

I will recycle some parts.

2212–2223 ↗

(On Diff #52778)

All good points which I partially addresses a while ago but should have mentioned somehwere more prominent when we introduced the new domain generation. Here is my take but we might want to put that somehwere [either as comment or code]:

1. To wrap the pattern is something I would like to see but I do not have a good solution for (different recursive functions and signatures). I will gladly review and support that though.

2. I saw the comment early on and my take was that we could change the implementation of that algorithm if it was actually "slow". So far I did not (look for or) observe any slowdown due to the RPO and the first way to counter it would be to share/reuse/cache the same RTraversal for the different regions. Though, due to the little number of regions this might not change much.

3. We can either build a RPO traversal for the whole CFG or a Region which can contain SubRegions as nodes. There was an initial assumption that a SCoP does not span enough of the CFG to make it worthwile to build a traversal for the whole thing, thus we went with the latter. Since it operates on the RegionTree not on the CFG we should not pay more due to the recursive nature of the traversal. In fact we should pay only for what we need. That said, I do not know if it will make sense to go with a function RPO traversal at some point (if we have a function pass maybe) or not.

2242 ↗

(On Diff #52778)

I did this on purpose but I can do else too.

3070–3071 ↗

(On Diff #52778)

Isn't it enough just use the union of all error domains (or the context) instead per-stmt?

That would be an overapproximation that would basically make error statements and invariant loads "exclusive" again. Thus, the domain of a error-block could not depend on an invariant load, now it can.

That domain could contain the hoisted value itself, but which could be just outprojected.

I do not get this, sorry.

test/ScopInfo/error-blocks-1.ll

10–20 ↗

(On Diff #52778)

This is a test for the removal of error statements that was poorly covered before.

test/ScopInfo/error-blocks-2.ll

9 ↗

(On Diff #52778)

Are the invariant accesses ordered?

Not anymore. That did not work out well ... The code generation will "order" them on demand.

[grosser]

Hi Johannes,

thanks for this patch. It seems you guys already discussed this topic a lot and you seem to converge on the technical review. This is great. I will look at the updated version than once again.

Regarding this patch, it would be good to describe briefly in the commit message the original issue (at best with an example), the solution, and the reason alternatives have not been chosen. With this information one can understand this patch without having to dig through the previous discussion. Most likely you can just take some of the text that was in the bug report to discuss this.

One alternative that I learned about in the bug report was to revert an earlier patch (which svn id?). This would have fixed this bug here, but would have caused unnecessarily complicated domains. Right? Can we give a motivation why this would not be the case with the current approach?

s/priviously/previously/g

lib/Analysis/ScopInfo.cpp

3060 ↗

(On Diff #52778)

Add __isl_give here as well.

test/ScopInfo/error-blocks-1.ll

10–20 ↗

(On Diff #52778)

If this test case is not changed / affected by this commit, I would suggest to commit it ahead of time.

[llvm-commits]

• signature.asc219 BDownload
• msg-30043-152.txt162 BDownload

[jdoerfert]

Changed according to comments

[Meinersbur]

lib/Analysis/ScopInfo.cpp

2242 ↗

(On Diff #52778)

Please do; I was looking for a leak for the case IsErrorBlock == true when I noticed that it's the negated condition.

3070–3071 ↗

(On Diff #52778)

That would be an overapproximation that would basically make error statements and invariant loads "exclusive"
again. Thus, the domain of a error-block could not depend on an invariant load, now it can.

OK, I see. Any ErrorDomainCtxMap is not only valid in the scop context, but even required for checking the context.

But in case of "union of all error domains", the validity check is a conjunction of all error domains. If one of them is is true, the other ones can be just undef and not influence the outcome.

At a second though, I think we'd have a problem with the evaluation order. One error domain needs to be checked first and might be only allowed to be dereferenced depending on another error domain.

[grosser]

Thanks Johannes for the improved commit message. This LGTM now.

[grosser]

Ah, and please reference the bug report id in your commit message.

polly/trunk/include/polly/ScopInfo.h

private:
   std::shared_ptr<isl_ctx> IslCtx;
 
   /// @brief A map from basic blocks to SCoP statements.
   DenseMap<BasicBlock *, ScopStmt *> StmtMap;
 
   /// @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;
 
   /// @brief The affinator used to translate SCEVs to isl expressions.
   SCEVAffinator Affinator;
 
   typedef MapVector<std::pair<AssertingVH<const Value>, int>,
                     std::unique_ptr<ScopArrayInfo>>
private:
   ///
   /// @param R  The region we currently build branching conditions for.
   /// @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 propagateDomainConstraints(Region *R, ScopDetection &SD,
                                   DominatorTree &DT, LoopInfo &LI);
 
-  /// @brief Remove domains of error blocks/regions (and blocks dominated by
-  ///        them).
+  /// @brief Propagate of error block domain contexts 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.
   ///
+  /// @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 removeErrorBlockDomains(ScopDetection &SD, DominatorTree &DT,
-                               LoopInfo &LI);
+  void propagateErrorConstraints(Region *R, ScopDetection &SD,
+                                 DominatorTree &DT, LoopInfo &LI);
 
   /// @brief Compute the domain for each basic block in @p R.
   ///
   /// @param R  The region we currently traverse.
   /// @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.
   ///
private:
   /// @brief Simplify the SCoP representation
   ///
   /// At the moment we perform the following simplifications:
   ///   - removal of no-op statements
   /// @param RemoveIgnoredStmts If true, also removed ignored statments.
   /// @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
   /// same address in order to keep the number of dimensions in the SCoP
   /// description small. For each such class equivalence class only one
   /// representing element, hence one required invariant load, will be chosen
   /// and modeled as parameter. The method
   /// Scop::getRepresentingInvariantLoadSCEV() will replace each element from an

polly/trunk/lib/Analysis/ScopInfo.cpp

isl_set *Scop::getDomainConditions(ScopStmt *Stmt) {
   return getDomainConditions(Stmt->getEntryBlock());
 }
 
 isl_set *Scop::getDomainConditions(BasicBlock *BB) {
   assert(DomainMap.count(BB) && "Requested BB did not have a domain");
   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) {
 
   bool IsOnlyNonAffineRegion = SD.isNonAffineSubRegion(R, R);
   auto *EntryBB = R->getEntry();
   auto *L = IsOnlyNonAffineRegion ? nullptr : LI.getLoopFor(EntryBB);
   int LD = getRelativeLoopDepth(L);
   auto *S = isl_set_universe(isl_space_set_alloc(getIslCtx(), 0, LD + 1));
bool Scop::buildDomains(Region *R, ScopDetection &SD, DominatorTree &DT,
   if (!buildDomainsWithBranchConstraints(R, SD, DT, LI))
     return false;
 
   propagateDomainConstraints(R, SD, DT, LI);
 
   // 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;
 }
 
 static Loop *
 getFirstNonBoxedLoopFor(BasicBlock *BB, LoopInfo &LI,
                         const ScopDetection::BoxedLoopsSetTy &BoxedLoops) {
   auto *L = LI.getLoopFor(BB);
   while (BoxedLoops.count(L))
if (OldDepth == NewDepth) {
     int NumDim = isl_set_n_dim(Dom);
     assert(NumDim >= Diff);
     Dom = isl_set_project_out(Dom, isl_dim_set, NumDim - Diff, Diff);
   }
 
   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,
     LoopInfo &LI) {
 
   // Check if the block @p BB is the entry of a region. If so we propagate it's
   // domain to the exit block of the region. Otherwise we are done.
   auto *RI = R.getRegionInfo();

 Scop::~Scop() {
   isl_set_free(Context);
   isl_set_free(AssumedContext);
   isl_set_free(InvalidContext);
   isl_schedule_free(Schedule);
 
   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) {
     for (MinMaxAccessTy &MMA : MinMaxAccessPair.first) {
       isl_pw_multi_aff_free(MMA.first);
       isl_pw_multi_aff_free(MMA.second);
     }
     for (MinMaxAccessTy &MMA : MinMaxAccessPair.second) {
for (auto &IAClass : InvariantEquivClasses) {
     for (auto *MA : MAs)
       if (MA->getAccessInstruction() == Val)
         return &IAClass;
   }
 
   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);
 
   // Project out all parameters that relate to loads in the statement. Otherwise
   // we could have cyclic dependences on the constraints under which the
   // hoisted loads are executed and we could not determine an order in which to
   // pre-load them. This happens because not only lower bounds are part of the

polly/trunk/test/ScopInfo/error-blocks-2.ll

+; RUN: opt %loadPolly -polly-scops -analyze < %s | FileCheck %s
+;
+; CHECK:         Invariant Accesses: {
+; CHECK-NEXT:            ReadAccess :=  [Reduction Type: NONE] [Scalar: 0]
+; CHECK-NEXT:                [N, valid_val] -> { Stmt_for_body[i0] -> MemRef_valid[0] };
+; CHECK-NEXT:            Execution Context: [N, valid_val] -> {  : N > 0 }
+; CHECK-NEXT:            ReadAccess :=  [Reduction Type: NONE] [Scalar: 0]
+; CHECK-NEXT:                [N, valid_val] -> { Stmt_S[i0] -> MemRef_ptr_addr[0] };
+; CHECK-NEXT:            Execution Context: [N, valid_val] -> {  : N > 0 and (valid_val < 0 or valid_val > 0) }
+; CHECK-NEXT:            ReadAccess :=  [Reduction Type: NONE] [Scalar: 0]
+; CHECK-NEXT:                [N, valid_val] -> { Stmt_S[i0] -> MemRef_tmp2[0] };
+; CHECK-NEXT:            Execution Context: [N, valid_val] -> {  : N > 0 and (valid_val < 0 or valid_val > 0) }
+; CHECK-NEXT:    }
+; CHECK-NEXT:    Context:
+; CHECK-NEXT:    [N, valid_val] -> {  : -2147483648 <= N <= 2147483647 and -2147483648 <= valid_val <= 2147483647 }
+; CHECK-NEXT:    Assumed Context:
+; CHECK-NEXT:    [N, valid_val] -> {  :  }
+; CHECK-NEXT:    Invalid Context:
+; CHECK-NEXT:    [N, valid_val] -> {  : valid_val = 0 and N > 0 }
+;
+; CHECK:         Statements {
+; CHECK-NEXT:       Stmt_S
+; CHECK-NEXT:            Domain :=
+; CHECK-NEXT:                [N, valid_val] -> { Stmt_S[i0] : 0 <= i0 < N };
+; CHECK-NEXT:            Schedule :=
+; CHECK-NEXT:                [N, valid_val] -> { Stmt_S[i0] -> [i0] };
+; CHECK-NEXT:            MustWriteAccess := [Reduction Type: NONE] [Scalar: 0]
+; CHECK-NEXT:                [N, valid_val] -> { Stmt_S[i0] -> MemRef_A[i0] };
+; CHECK-NEXT:    }
+;
+target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
+
+define void @f(i32 %N, i32* noalias %valid, i32* noalias %ptr, i32* noalias %A) {
+entry:
+  %ptr.addr = alloca i32*, align 8
+  store i32* %ptr, i32** %ptr.addr, align 8
+  %tmp = sext i32 %N to i64
+  br label %for.cond
+
+for.cond:                                         ; preds = %for.inc, %entry
+  %indvars.iv = phi i64 [ %indvars.iv.next, %for.inc ], [ 0, %entry ]
+  %cmp = icmp slt i64 %indvars.iv, %tmp
+  br i1 %cmp, label %for.body, label %for.end
+
+for.body:                                         ; preds = %for.cond
+  %valid_val = load i32, i32* %valid, align 4
+  %cmp1 = icmp eq i32 %valid_val, 0
+  br i1 %cmp1, label %if.then, label %if.end
+
+if.then:                                          ; preds = %for.body
+  call void @doSth(i32** nonnull %ptr.addr)
+  br label %if.end
+
+if.end:                                           ; preds = %if.then, %for.body
+  br label %S
+
+S:                                                ; preds = %if.end
+  %tmp2 = load i32*, i32** %ptr.addr, align 8
+  %tmp3 = load i32, i32* %tmp2, align 4
+  %arrayidx = getelementptr inbounds i32, i32* %A, i64 %indvars.iv
+  store i32 %tmp3, i32* %arrayidx, align 4
+  br label %for.inc
+
+for.inc:                                          ; preds = %S
+  %indvars.iv.next = add nuw nsw i64 %indvars.iv, 1
+  br label %for.cond
+
+for.end:                                          ; preds = %for.cond
+  ret void
+}
+
+declare void @doSth(i32**)