[islpp] Do not abuse isl::stat::error as early-abort

[grosser]

Summary

isl::stat::error indicates a run-time error. We should not abuse it to
enforce an early abort of the foreach call. We should soon see a new
isl_*_every function family, which allows for specific return values to
abort early. When these are available, we should introduce these
deliberately to indicate early aborts.

In same cases we also abused these return values to indicate if a
certain value has been found or not. To avoid this abuse an extra
boolean is introduced to track this state.

[grosser]

Convert two more functions

[philip.pfaffe]

I think this makes sense, with some inline nits.

lib/Analysis/ScopInfo.cpp

2357–2360

Shouldn't this still be an error?

2377–2378

This is now superfluous.

2409

In case of isl_error_quota, this should also return false in that case.

lib/Transform/FlattenAlgo.cpp

61

You could check this condition before testing the BMap's out-dimension to save a little bit of compute.

[grosser]

lib/Analysis/ScopInfo.cpp

2357–2360

I don't think this is needed. Isl's global error state is already set to 'error'. I don't see which benefit it has to pass this fact _again_ to isl. Also, we check for this fact again at:

for (AliasGroupTy &AG : AliasGroups) {                                         
  if (!hasFeasibleRuntimeContext())                                            
    return false;                                                              
                                                                               
  {                                                                            
    IslMaxOperationsGuard MaxOpGuard(getIslCtx().get(), OptComputeOut);        
    bool Valid = buildAliasGroup(AG, HasWriteAccess);                          
    if (!Valid)                                                                
      return false;                                                            
  }                                                                            
  if (isl_ctx_last_error(getIslCtx().get()) == isl_error_quota) {              
    invalidate(COMPLEXITY, DebugLoc());                                        
    return false;                                                              
  }

In fact, I feel we should probably just drop this condition entirely. Not sure why it even has been left here.

@Meinersbur, any idea?

2377–2378

Dropped.

2396

Why? We don't do this today either.

As the global quota state is already set to quota-error anything we will compute inside the quota guard will anyhow discarded. There is no need to communicate on any other pass that things are invalid and we should probably not even try as otherwise we would need to check for compute out's all over the place, if we would like to be consistent. As this is not possible, the intend is always that there is a final check that drops everything, if there was a compute-out error.

lib/Transform/FlattenAlgo.cpp

61

I don't get what you have in mind here. Could you provide a mini code snippet?

[grosser]

Address some of Philips comments

• Remove unneeded return

[philip.pfaffe]

lib/Analysis/ScopInfo.cpp

2396

We do it today, courtesy of buildMinMaxAccess propagating the error.

But if we're dropping that propagation alltogether, then this is ceretainly fine.

lib/Transform/FlattenAlgo.cpp

61

[&](isl::basic_map BMap) -> isl::stat {
    if (IsVariableDim)
        return isl::stat::ok;

    ...
}

[grosser]

Thanks @philip.pfaffe . Is this fine from your side, otherwise?

I am still waiting for feedback from Michael Kruse regarding dropping the compute-out stuff. Please feel free to comment on this as well.

lib/Analysis/ScopInfo.cpp

2396

I see. Seems we agree.

lib/Transform/FlattenAlgo.cpp

61

I understand. I feel this adds just noise. I doubt we will save anything measurable. Would prefer to add it only if we can measure a perf difference.

[Meinersbur]

Why not just waiting until isl_*_every is available? When it comes, do we need to undo the changes here again?

Did you consider adding a wrapper foreach that sets/checks the Aborted flag itself?

lib/Analysis/ScopInfo.cpp

2357–2360

There is a clean-up of this in D45066.

2393

buildMinMaxAccess returning isl::stat::error is an error: The access bounds could not be computed. It's no abuse.

2404

Instead of making buildMinMaxAccess handle the "break;" of a loop that is called in, I'd prefer if it is handled directly in the lambda.

lib/Support/ISLTools.cpp

478–479

If UMap is NULL (or cannot be iterated over), this now returns an empty map instead of nullptr.

lib/Transform/ForwardOpTree.cpp

271

The // break comment should be moved to the line above.

lib/Transform/Simplify.cpp

100–102

bool Aborted = false;

105–106

Consistency: if (Aborted) added to this foreach, but not the following.

116

Resetting Aborted to false is unnecessary: Once Result has exceeded SimplifyMaxDisjuncts, no more disjuncts will be added.

lib/Transform/ZoneAlgo.cpp

260–261

There's a difference in semantics here: If UMap is NULL (or cannot be iterated over), this function would return nullptr, instead of an empty map.

870

Like above, if UMap is NULL, this now returns true instead of false

[philip.pfaffe]

I'm generally fine with this, just one more nit: I don't like for the argument to be called Aborted, for that suggests an error condition. What about BreakIteration instead?

[Meinersbur]

Scop::containsExtensionNode is missing

[grosser]

Thanks. I am currently upstreaming a set of functions to isl which allow us to get basic_map_lists from a map and map_lists from a union_map. For isl_*_list types it should be easy to write an iterator that allows foreach loops. I plan to write such iterators and will then use these to simplify this code.

[grosser]

Dropping this in favor of D47604. Thanks for the suggestions!

lib/Analysis/ScopInfo.cpp

void Scop::simplifyContexts() {
   //   we assume that the condition m <= 0 or (m >= 1 and p >= 0) holds as
   //   otherwise we would access out of bound data. Now, knowing that code is
   //   only executed for the case m >= 0, it is sufficient to assume p >= 0.
   AssumedContext = simplifyAssumptionContext(AssumedContext, *this);
   InvalidContext = InvalidContext.align_params(getParamSpace());
 }
 
 /// Add the minimal/maximal access in @p Set to @p User.
-static isl::stat
-buildMinMaxAccess(isl::set Set, Scop::MinMaxVectorTy &MinMaxAccesses, Scop &S) {
+static void buildMinMaxAccess(isl::set Set,
+                              Scop::MinMaxVectorTy &MinMaxAccesses, Scop &S,
+                              bool &Aborted) {
   isl::pw_multi_aff MinPMA, MaxPMA;
   isl::pw_aff LastDimAff;
   isl::aff OneAff;
   unsigned Pos;
   isl::ctx Ctx = Set.get_ctx();
 
+  if (Aborted)
+    return;
+
   Set = Set.remove_divs();
 
-  if (isl_set_n_basic_set(Set.get()) >= MaxDisjunctsInDomain)
-    return isl::stat::error;
+  if (isl_set_n_basic_set(Set.get()) >= MaxDisjunctsInDomain) {
+    Aborted = true;
+    return;
+  }
 
   // Restrict the number of parameters involved in the access as the lexmin/
   // lexmax computation will take too long if this number is high.
   //
   // Experiments with a simple test case using an i7 4800MQ:
   //
   //  #Parameters involved | Time (in sec)
   //            6          |     0.01
   //            7          |     0.04
   //            8          |     0.12
   //            9          |     0.40
   //           10          |     1.54
   //           11          |     6.78
   //           12          |    30.38
   //
   if (isl_set_n_param(Set.get()) > RunTimeChecksMaxParameters) {
     unsigned InvolvedParams = 0;
     for (unsigned u = 0, e = isl_set_n_param(Set.get()); u < e; u++)
       if (Set.involves_dims(isl::dim::param, u, 1))
         InvolvedParams++;
 
-    if (InvolvedParams > RunTimeChecksMaxParameters)
-      return isl::stat::error;
+    if (InvolvedParams > RunTimeChecksMaxParameters) {
+      Aborted = true;
+      return;
+    }
   }
 
-  if (isl_set_n_basic_set(Set.get()) > RunTimeChecksMaxAccessDisjuncts)
-    return isl::stat::error;
+  if (isl_set_n_basic_set(Set.get()) > RunTimeChecksMaxAccessDisjuncts) {
+    Aborted = true;
+    return;
+  }
 
   MinPMA = Set.lexmin_pw_multi_aff();
   MaxPMA = Set.lexmax_pw_multi_aff();
 
-  if (isl_ctx_last_error(Ctx.get()) == isl_error_quota)
-    return isl::stat::error;
+  if (isl_ctx_last_error(Ctx.get()) == isl_error_quota) {
+    Aborted = true;
+    return;
+  }
 
   MinPMA = MinPMA.coalesce();
   MaxPMA = MaxPMA.coalesce();
 
   // Adjust the last dimension of the maximal access by one as we want to
   // enclose the accessed memory region by MinPMA and MaxPMA. The pointer
   // we test during code generation might now point after the end of the
   // allocated array but we will never dereference it anyway.
   assert(MaxPMA.dim(isl::dim::out) && "Assumed at least one output dimension");
   Pos = MaxPMA.dim(isl::dim::out) - 1;
   LastDimAff = MaxPMA.get_pw_aff(Pos);
   OneAff = isl::aff(isl::local_space(LastDimAff.get_domain_space()));
   OneAff = OneAff.add_constant_si(1);
   LastDimAff = LastDimAff.add(OneAff);
   MaxPMA = MaxPMA.set_pw_aff(Pos, LastDimAff);
 
   MinMaxAccesses.push_back(std::make_pair(MinPMA, MaxPMA));
-
-  return isl::stat::ok;
 }
 
 static __isl_give isl_set *getAccessDomain(MemoryAccess *MA) {
   isl_set *Domain = MA->getStatement()->getDomain().release();
   Domain = isl_set_project_out(Domain, isl_dim_set, 0, isl_set_n_dim(Domain));
   return isl_set_reset_tuple_id(Domain);
 }
 
 /// Wrapper function to calculate minimal/maximal accesses to each array.
 static bool calculateMinMaxAccess(Scop::AliasGroupTy AliasGroup, Scop &S,
                                   Scop::MinMaxVectorTy &MinMaxAccesses) {
   MinMaxAccesses.reserve(AliasGroup.size());
 
   isl::union_set Domains = S.getDomains();
   isl::union_map Accesses = isl::union_map::empty(S.getParamSpace());
 
   for (MemoryAccess *MA : AliasGroup)
     Accesses = Accesses.add_map(MA->getAccessRelation());
 
   Accesses = Accesses.intersect_domain(Domains);
   isl::union_set Locations = Accesses.range();
   Locations = Locations.coalesce();
   Locations = Locations.detect_equalities();
 
-  auto Lambda = [&MinMaxAccesses, &S](isl::set Set) -> isl::stat {
-    return buildMinMaxAccess(Set, MinMaxAccesses, S);
+  bool Aborted = false;
+  auto Lambda = [&MinMaxAccesses, &S, &Aborted](isl::set Set) -> isl::stat {
+    buildMinMaxAccess(Set, MinMaxAccesses, S, Aborted);
+    return isl::stat::ok;
   };
-  return Locations.foreach_set(Lambda) == isl::stat::ok;
+  Locations.foreach_set(Lambda);
+
+  return !Aborted;
 }
 
 /// Helper to treat non-affine regions and basic blocks the same.
 ///
 ///{
 
 /// Return the block that is the representing block for @p RN.
 static inline BasicBlock *getRegionNodeBasicBlock(RegionNode *RN) {
   return RN->isSubRegion() ? RN->getNodeAs<Region>()->getEntry()
auto PMA = isl::pw_multi_aff::project_out_map(S.get_space(), isl::dim::set,
                                                   N, Dim - N);
     if (N > 1)
       PMA = PMA.drop_dims(isl::dim::out, 0, N - 1);
 
     Result = Result.add_pw_multi_aff(PMA);
     return isl::stat::ok;
   };
 
-  isl::stat Res = USet.foreach_set(Lambda);
-  (void)Res;
-
-  assert(Res == isl::stat::ok);
+  USet.foreach_set(Lambda);
 
   return isl::multi_union_pw_aff(isl::union_pw_multi_aff(Result));
 }
 
 void Scop::addScopStmt(BasicBlock *BB, StringRef Name, Loop *SurroundingLoop,
                        std::vector<Instruction *> Instructions) {
   assert(BB && "Unexpected nullptr!");
   Stmts.emplace_back(*this, *BB, Name, SurroundingLoop, Instructions);

lib/Support/ISLTools.cpp

Translator = Translator.equate(isl::dim::in, DomainDims + Range1Dims + i,
                                    isl::dim::out,
                                    DomainDims + Range1Dims + DomainDims + i);
 
   return Map.wrap().apply(Translator).unwrap();
 }
 
 isl::union_map polly::distributeDomain(isl::union_map UMap) {
   isl::union_map Result = isl::union_map::empty(UMap.get_space());
-  isl::stat Success = UMap.foreach_map([=, &Result](isl::map Map) {
+  UMap.foreach_map([=, &Result](isl::map Map) {
     auto Distributed = distributeDomain(Map);
     Result = Result.add_map(Distributed);
     return isl::stat::ok;
   });
-  if (Success != isl::stat::ok)
-    return {};
   return Result;
 }
 
 isl::union_map polly::liftDomains(isl::union_map UMap, isl::union_set Factor) {
 
   // { Factor[] -> Factor[] }
   isl::union_map Factors = makeIdentityMap(Factor, true);
 
isl::val polly::getConstant(isl::pw_aff PwAff, bool Max, bool Min) {
   PwAff.foreach_piece([=, &Result](isl::set Set, isl::aff Aff) -> isl::stat {
     if (Result && Result.is_nan())
       return isl::stat::ok;
 
     // TODO: If Min/Max, we can also determine a minimum/maximum value if
     // Set is constant-bounded.
     if (!Aff.is_cst()) {
       Result = isl::val::nan(Aff.get_ctx());
-      return isl::stat::error;
+      return isl::stat::ok;
     }
 
     isl::val ThisVal = Aff.get_constant_val();
     if (!Result) {
       Result = ThisVal;
       return isl::stat::ok;
     }
 
     if (Result.eq(ThisVal))
       return isl::stat::ok;
 
     if (Max && ThisVal.gt(Result)) {
       Result = ThisVal;
       return isl::stat::ok;
     }
 
     if (Min && ThisVal.lt(Result)) {
       Result = ThisVal;
       return isl::stat::ok;
     }
 
     // Not compatible
     Result = isl::val::nan(Aff.get_ctx());
-    return isl::stat::error;
+    return isl::stat::ok;
   });
   return Result;
 }
 
 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
 static void foreachPoint(const isl::set &Set,
                          const std::function<void(isl::point P)> &F) {
   Set.foreach_point([&](isl::point P) -> isl::stat {

lib/Transform/FlattenAlgo.cpp

 /// Whether BMap's first out-dimension is not a constant.
 bool isVariableDim(const isl::basic_map &BMap) {
   auto FixedVal = BMap.plain_get_val_if_fixed(isl::dim::out, 0);
   return !FixedVal || FixedVal.is_nan();
 }
 
 /// Whether Map's first out dimension is no constant nor piecewise constant.
 bool isVariableDim(const isl::map &Map) {
-  return Map.foreach_basic_map([](isl::basic_map BMap) -> isl::stat {
+  bool IsVariableDim = false;
+
+  Map.foreach_basic_map([&](isl::basic_map BMap) -> isl::stat {
     if (isVariableDim(BMap))
-      return isl::stat::error;
+      IsVariableDim = true;
     return isl::stat::ok;
-  }) == isl::stat::ok;
+  });
+
+  return IsVariableDim;
 }
 
 /// Whether UMap's first out dimension is no (piecewise) constant.
 bool isVariableDim(const isl::union_map &UMap) {
-  return UMap.foreach_map([](isl::map Map) -> isl::stat {
+  bool IsVariableDim = false;
+
+  UMap.foreach_map([&](isl::map Map) {
     if (isVariableDim(Map))
-      return isl::stat::error;
+      IsVariableDim = true;
     return isl::stat::ok;
-  }) == isl::stat::ok;
+  });
+
+  return IsVariableDim;
 }
 
 /// Compute @p UPwAff - @p Val.
 isl::union_pw_aff subtract(isl::union_pw_aff UPwAff, isl::val Val) {
   if (Val.is_zero())
     return UPwAff;
 
   auto Result = isl::union_pw_aff::empty(UPwAff.get_space());

lib/Transform/ForwardOpTree.cpp

private:
   isl::map singleLocation(isl::union_map MustKnown, isl::set Domain) {
     // { Domain[] -> Element[] }
     isl::map Result;
 
     // MemoryAccesses can read only elements from a single array
     // (i.e. not: { Dom[0] -> A[0]; Dom[1] -> B[1] }).
     // Look through all spaces until we find one that contains at least the
     // wanted statement instance.s
+    bool Aborted = false;
     MustKnown.foreach_map([&](isl::map Map) -> isl::stat {
       // Get the array this is accessing.
+      if (Aborted)
+        return isl::stat::ok;
+
       isl::id ArrayId = Map.get_tuple_id(isl::dim::out);
       ScopArrayInfo *SAI = static_cast<ScopArrayInfo *>(ArrayId.get_user());
 
       // No support for generation of indirect array accesses.
       if (SAI->getBasePtrOriginSAI())
         return isl::stat::ok; // continue
 
       // Determine whether this map contains all wanted values.
       isl::set MapDom = Map.domain();
       if (!Domain.is_subset(MapDom).is_true())
         return isl::stat::ok; // continue
 
       // There might be multiple array elements that contain the same value, but
       // choose only one of them. lexmin is used because it returns a one-value
       // mapping, we do not care about which one.
       // TODO: Get the simplest access function.
       Result = Map.lexmin();
-      return isl::stat::error; // break
+
+      Aborted = true;
+      return isl::stat::ok; // break
     });
 
     return Result;
   }
 
 public:
   ForwardOpTreeImpl(Scop *S, LoopInfo *LI, IslMaxOperationsGuard &MaxOpGuard)
       : ZoneAlgorithm("polly-optree", S, LI), MaxOpGuard(MaxOpGuard) {}

lib/Transform/Simplify.cpp

static isl::union_map underapproximatedAddMap(isl::union_map UMap,
 
   // Fast path: If known that we cannot exceed the disjunct limit, just add
   // them.
   if (isl_map_n_basic_map(PrevMap.get()) + isl_map_n_basic_map(Map.get()) <=
       SimplifyMaxDisjuncts)
     return UMap.add_map(Map);
 
   isl::map Result = isl::map::empty(PrevMap.get_space());
-  PrevMap.foreach_basic_map([&Result](isl::basic_map BMap) -> isl::stat {
-    if (isl_map_n_basic_map(Result.get()) > SimplifyMaxDisjuncts)
-      return isl::stat::error;
+  bool Aborted;
+
+  Aborted = false;
+  PrevMap.foreach_basic_map(
+      [&Result, &Aborted](isl::basic_map BMap) -> isl::stat {
+        if (Aborted)
+          return isl::stat::ok;
+
+        if (isl_map_n_basic_map(Result.get()) > SimplifyMaxDisjuncts) {
+          Aborted = true;
+          return isl::stat::ok;
+        }
         Result = Result.unite(BMap);
         return isl::stat::ok;
       });
-  Map.foreach_basic_map([&Result](isl::basic_map BMap) -> isl::stat {
-    if (isl_map_n_basic_map(Result.get()) > SimplifyMaxDisjuncts)
-      return isl::stat::error;
+
+  Aborted = false;
+  Map.foreach_basic_map([&Result, &Aborted](isl::basic_map BMap) -> isl::stat {
+    if (isl_map_n_basic_map(Result.get()) > SimplifyMaxDisjuncts) {
+      Aborted = true;
+      return isl::stat::ok;
+    }
     Result = Result.unite(BMap);
     return isl::stat::ok;
   });
 
   isl::union_map UResult =
       UMap.subtract(isl::map::universe(PrevMap.get_space()));
   UResult.add_map(Result);
 
for (auto &Stmt : *S) {
               isl::map::from_domain_and_range(AllowedAccesses.wrap(), ValSet);
 
           // Lookup future write that fulfills these conditions.
           // { [[Domain[] -> Element[]] -> Value[]] -> MemoryAccess[] }
           isl::union_map Filtered =
               FutureWrites.uncurry().intersect_domain(Filter.wrap());
 
           // Iterate through the candidates.
+          bool Aborted = false;
           Filtered.foreach_map([&, this](isl::map Map) -> isl::stat {
+            if (Aborted)
+              return isl::stat::ok;
             MemoryAccess *OtherMA = (MemoryAccess *)Map.get_space()
                                         .get_tuple_id(isl::dim::out)
                                         .get_user();
 
             isl::map OtherAccRel =
                 OtherMA->getLatestAccessRelation().intersect_domain(Domain);
 
             // The filter only guaranteed that some of OtherMA's accessed
for (auto &Stmt : *S) {
 
             // We removed MA, OtherMA takes its role.
             MA = OtherMA;
 
             TotalWritesCoalesced[CallNo]++;
             WritesCoalesced++;
 
             // Don't look for more candidates.
-            return isl::stat::error;
+            Aborted = true;
+            return isl::stat::ok;
           });
         }
 
         // Two writes cannot be coalesced if there is another access (to some of
         // the written elements) between them. Remove all visited write accesses
         // from the list of eligible writes. Don't just remove the accessed
         // elements, but any MemoryAccess that touches any of the invalidated
         // elements.

lib/Transform/ZoneAlgo.cpp

 static bool isMapToUnknown(const isl::map &Map) {
   isl::space Space = Map.get_space().range();
   return Space.has_tuple_id(isl::dim::set).is_false() &&
          Space.is_wrapping().is_false() && Space.dim(isl::dim::set) == 0;
 }
 
 isl::union_map polly::filterKnownValInst(const isl::union_map &UMap) {
   isl::union_map Result = isl::union_map::empty(UMap.get_space());
-  isl::stat Success = UMap.foreach_map([=, &Result](isl::map Map) -> isl::stat {
+  UMap.foreach_map([=, &Result](isl::map Map) -> isl::stat {
     if (!isMapToUnknown(Map))
       Result = Result.add_map(Map);
     return isl::stat::ok;
   });
-  if (Success != isl::stat::ok)
-    return {};
   return Result;
 }
 
 ZoneAlgorithm::ZoneAlgorithm(const char *PassName, Scop *S, LoopInfo *LI)
     : PassName(PassName), IslCtx(S->getSharedIslCtx()), S(S), LI(LI),
       Schedule(S->getSchedule()) {
   auto Domains = S->getDomains();
 
bool ZoneAlgorithm::isNormalized(isl::map Map) {
   MemoryAccess *PHIRead = IncomingStmt->lookupPHIReadOf(PHI);
   if (!isNormalizable(PHIRead))
     return true;
 
   return false;
 }
 
 bool ZoneAlgorithm::isNormalized(isl::union_map UMap) {
-  auto Result = UMap.foreach_map([this](isl::map Map) -> isl::stat {
-    if (isNormalized(Map))
-      return isl::stat::ok;
-    return isl::stat::error;
+  bool IsNormalized = true;
+  UMap.foreach_map([&](isl::map Map) -> isl::stat {
+    if (!isNormalized(Map))
+      IsNormalized = false;
   });
-  return Result == isl::stat::ok;
+  return IsNormalized;
 }
 
 void ZoneAlgorithm::computeCommon() {
   AllReads = makeEmptyUnionMap();
   AllMayWrites = makeEmptyUnionMap();
   AllMustWrites = makeEmptyUnionMap();
   AllWriteValInst = makeEmptyUnionMap();
   AllReadValInst = makeEmptyUnionMap();