[Polly] Add isl C++ list iterators

[grosser]

Summary

These iterators allow to use C++ range-based for loops to enumerate the
elements in an isl list. They can be used to enumerate e.g. the sets in
a union set:

for (isl::set Set : USet.get_set_list()) {
  Set.dump();
}

Use this implementation to replace the use of foreach + lambda with
easier readable range-based for loops.

[Meinersbur]

Nice one, at least for lists.

Don't forget to add [Polly] into the title for reviews.

include/polly/Support/ISLTools.h

22–42

[suggestion] These are not meant to be used outside of struct list_iterator, correct? Hence you could put them into an anonymous namespace.

24

[serious] basic_set_list::get_basic_set etc. use the type int for indices, not long.

[suggestion] Pass by const & could safe a reference counter increment and decrement.

[style] This does not look like LLVM's naming style.

45

[suggestion] did you check whether you could derive from llvm::iterator_adaptor_base? It adds some common iterator boilerplate methods.

52

[suggestion] Could you add assertions to check that list is not null and position is within the expected range?

56

[style] usually the operator* returns a value.

58

[serious] No operator==? Should be added for consistency.

63–64

[concern] The template is very general and can be instantiated for any type. Could you check that when C++ foreach looks for overloads for begin, end it does not try to use these functions in case of non-intended type. I fear we could get strange error message for something non-iteratable like "no overload list_size(isl::id)";

64

[suggestion] Should this be const list_type &?

[Meinersbur]

[suggestion] unit tests?

include/polly/Support/ISLTools.h

22–42

or polly::detail subnamespace

[Meinersbur]

[serious] Could you document what you expect to happen in out-of-quote situations? I just noticed that eg. USet.get_set_list will allocate a new list, thus may fail in IslQuotaScopes.

I am a bit concerned about allocating a heavy-weight heap object just for iterating over something. That is, the iterators over list object are great, but in the long term maybe we could find a way to avoid creating such lists to iterate over sets/maps.

[philip.pfaffe]

I love the gist of this, but there are a couple of implementation issues, some of which @Meinersbur pointed out already.

list_iterator is not an InputIterator, not even an Iterator. You're lacking various parts required by the concepts:

• It's not Swappable
• It's not CopyAssignable
• There's no std::iterator_traits
• There's no operator->
• There's no post-increment operator.

I very much don't like implementation as a template class, while outlining the specialized behavior. A much nicer way to build this would be to have an index_iterator CRTP iterator base for iteration via index, implemented on to of llvm::iterator_facade_base and scoped to an isl namespace (names subject to bikeshedding). Derive iterators from that to specialize the accessors. Similarly, have explicit overloads for {basic_,}{set,map} lists' begin() and end() functions. A low-tech solution is required for this, anything else will just come back to bite us.

[bollu]

This might be too much to ask for, but is it possible to report_fatal_error() at the earliest when accessing out of bounds using the iterator? If ISL performs inbounds checks, then disregard this.

Also, I was probably out of the loop for the API discussion. When did we settle on getting a list out of a set, map, etc. and then iterating over the list?

I thought the eventual API was trying to settle into something like:

for (isl::set Set : USet) {...}

rather than

for (isl::set Set : USet.get_set_list()) {...}

[bollu]

This might be too much to ask for, but is it possible to report_fatal_error() at the earliest when accessing out of bounds using the iterator? If ISL performs inbounds checks, then disregard this.

Also, I was probably out of the loop for the API discussion. When did we settle on getting a list out of a set, map, etc. and then iterating over the list?

I thought the eventual API was trying to settle into something like:

for (isl::set Set : USet) {...}

rather than

for (isl::set Set : USet.get_set_list()) {...}

[philip.pfaffe]

In D47604#1120577, @bollu wrote:

This might be too much to ask for, but is it possible to report_fatal_error() at the earliest when accessing out of bounds using the iterator? If ISL performs inbounds checks, then disregard this.

Actually I'd prefer not to report an error here at all, at least not outside of LLVM_DEBUG. Dereferencing a past-the-end iterator is UB.

When did we settle on getting a list out of a set, map, etc. and then iterating over the list?

This is not as simple as it looks, since a union_set doesn't allow you to enumerate or access the individual sets. So you can choose between USet.get_set_list() or something like range(USet) which returns an appropriate iterator range that holds the list.

[grosser]

This has become obsolete, after Philip Pfaffe committed a better variant of this feature.

include/polly/Support/ISLTools.h

 
 #ifndef POLLY_ISLTOOLS_H
 #define POLLY_ISLTOOLS_H
 
 #include "polly/Support/GICHelper.h"
 
 namespace polly {
 
+/// A set of list accessors which make the subsequent iterator implementation
+/// easier.
+inline isl::basic_set list_get(isl::basic_set_list list, long idx) {
+  return list.get_basic_set(idx);
+}
+inline isl::set list_get(isl::set_list list, long idx) {
+  return list.get_set(idx);
+}
+inline isl::basic_map list_get(isl::basic_map_list list, long idx) {
+  return list.get_basic_map(idx);
+}
+inline isl::map list_get(isl::map_list list, long idx) {
+  return list.get_map(idx);
+}
+
+/// A set of list size functions which make the subsequent iterator
+/// implementation easier.
+inline int list_size(isl::basic_set_list list) { return list.n_basic_set(); }
+inline int list_size(isl::set_list list) { return list.n_set(); }
+inline int list_size(isl::basic_map_list list) { return list.n_basic_map(); }
+inline int list_size(isl::map_list list) { return list.n_map(); }
+
+/// An iterator for isl lists, which enables e.g. C++ foreach loops.
+template <typename list_type, typename element_type> struct list_iterator {
+private:
+  list_type &list;
+  int position;
+
+public:
+  list_iterator(list_type &list, int position)
+      : list(list), position(position) {}
+
+  element_type operator*() { return list_get(list, position); }
+
+  void operator++() { position++; }
+
+  bool operator!=(const list_iterator &that) {
+    return that.position != position;
+  }
+};
+
+template <typename list_type>
+auto begin(list_type &list)
+    -> list_iterator<list_type, decltype(list_get(list, 0))> {
+  return list_iterator<list_type, decltype(list_get(list, 0))>(list, 0);
+}
+
+template <typename list_type>
+auto end(list_type &list)
+    -> list_iterator<list_type, decltype(list_get(list, 0))> {
+  return list_iterator<list_type, decltype(list_get(list, 0))>(list,
+                                                               list_size(list));
+}
+
 /// Return the range elements that are lexicographically smaller.
 ///
 /// @param Map    { Space[] -> Scatter[] }
 /// @param Strict True for strictly lexicographically smaller elements (exclude
 ///               same timepoints from the result).
 ///
 /// @return { Space[] -> Scatter[] }
 ///         A map to all timepoints that happen before the timepoints the input

lib/Support/ISLTools.cpp

isl::map polly::beforeScatter(isl::map Map, bool Strict) {
   isl::space RangeSpace = Map.get_space().range();
   isl::map ScatterRel =
       Strict ? isl::map::lex_gt(RangeSpace) : isl::map::lex_ge(RangeSpace);
   return Map.apply_range(ScatterRel);
 }
 
 isl::union_map polly::beforeScatter(isl::union_map UMap, bool Strict) {
   isl::union_map Result = isl::union_map::empty(UMap.get_space());
-  UMap.foreach_map([=, &Result](isl::map Map) -> isl::stat {
+
+  for (isl::map Map : UMap.get_map_list()) {
     isl::map After = beforeScatter(Map, Strict);
     Result = Result.add_map(After);
-    return isl::stat::ok;
-  });
+  }
+
   return Result;
 }
 
 isl::map polly::afterScatter(isl::map Map, bool Strict) {
   isl::space RangeSpace = Map.get_space().range();
   isl::map ScatterRel =
       Strict ? isl::map::lex_lt(RangeSpace) : isl::map::lex_le(RangeSpace);
   return Map.apply_range(ScatterRel);
 }
 
 isl::union_map polly::afterScatter(const isl::union_map &UMap, bool Strict) {
   isl::union_map Result = isl::union_map::empty(UMap.get_space());
-  UMap.foreach_map([=, &Result](isl::map Map) -> isl::stat {
+  for (isl::map Map : UMap.get_map_list()) {
     isl::map After = afterScatter(Map, Strict);
     Result = Result.add_map(After);
-    return isl::stat::ok;
-  });
+  }
   return Result;
 }
 
 isl::map polly::betweenScatter(isl::map From, isl::map To, bool InclFrom,
                                bool InclTo) {
   isl::map AfterFrom = afterScatter(From, !InclFrom);
   isl::map BeforeTo = beforeScatter(To, !InclTo);
 
isl::set polly::singleton(isl::union_set USet, isl::space ExpectedSpace) {
   isl::set Result(USet);
   assert(!Result || Result.get_space().has_equal_tuples(ExpectedSpace));
 
   return Result;
 }
 
 unsigned polly::getNumScatterDims(const isl::union_map &Schedule) {
   unsigned Dims = 0;
-  Schedule.foreach_map([&Dims](isl::map Map) -> isl::stat {
+  for (isl::map Map : Schedule.get_map_list())
     Dims = std::max(Dims, Map.dim(isl::dim::out));
-    return isl::stat::ok;
-  });
   return Dims;
 }
 
 isl::space polly::getScatterSpace(const isl::union_map &Schedule) {
   if (!Schedule)
     return nullptr;
   unsigned Dims = getNumScatterDims(Schedule);
   isl::space ScatterSpace = Schedule.get_space().set_from_params();
   return ScatterSpace.add_dims(isl::dim::set, Dims);
 }
 
 isl::union_map polly::makeIdentityMap(const isl::union_set &USet,
                                       bool RestrictDomain) {
   isl::union_map Result = isl::union_map::empty(USet.get_space());
-  USet.foreach_set([=, &Result](isl::set Set) -> isl::stat {
+  for (isl::set Set : USet.get_set_list()) {
     isl::map IdentityMap = isl::map::identity(Set.get_space().map_from_set());
     if (RestrictDomain)
       IdentityMap = IdentityMap.intersect_domain(Set);
     Result = Result.add_map(IdentityMap);
-    return isl::stat::ok;
-  });
+  }
   return Result;
 }
 
 isl::map polly::reverseDomain(isl::map Map) {
   isl::space DomSpace = Map.get_space().domain().unwrap();
   isl::space Space1 = DomSpace.domain();
   isl::space Space2 = DomSpace.range();
   isl::map Swap = makeTupleSwapMap(Space1, Space2);
   return Map.apply_domain(Swap);
 }
 
 isl::union_map polly::reverseDomain(const isl::union_map &UMap) {
   isl::union_map Result = isl::union_map::empty(UMap.get_space());
-  UMap.foreach_map([=, &Result](isl::map Map) -> isl::stat {
+  for (isl::map Map : UMap.get_map_list()) {
     auto Reversed = reverseDomain(std::move(Map));
     Result = Result.add_map(Reversed);
-    return isl::stat::ok;
-  });
+  }
   return Result;
 }
 
 isl::set polly::shiftDim(isl::set Set, int Pos, int Amount) {
   int NumDims = Set.dim(isl::dim::set);
   if (Pos < 0)
     Pos = NumDims + Pos;
   assert(Pos < NumDims && "Dimension index must be in range");
   isl::space Space = Set.get_space();
   Space = Space.map_from_domain_and_range(Space);
   isl::multi_aff Translator = makeShiftDimAff(Space, Pos, Amount);
   isl::map TranslatorMap = isl::map::from_multi_aff(Translator);
   return Set.apply(TranslatorMap);
 }
 
 isl::union_set polly::shiftDim(isl::union_set USet, int Pos, int Amount) {
   isl::union_set Result = isl::union_set::empty(USet.get_space());
-  USet.foreach_set([=, &Result](isl::set Set) -> isl::stat {
+  for (isl::set Set : USet.get_set_list()) {
     isl::set Shifted = shiftDim(Set, Pos, Amount);
     Result = Result.add_set(Shifted);
-    return isl::stat::ok;
-  });
+  }
   return Result;
 }
 
 isl::map polly::shiftDim(isl::map Map, isl::dim Dim, int Pos, int Amount) {
   int NumDims = Map.dim(Dim);
   if (Pos < 0)
     Pos = NumDims + Pos;
   assert(Pos < NumDims && "Dimension index must be in range");
default:
     llvm_unreachable("Unsupported value for 'dim'");
   }
 }
 
 isl::union_map polly::shiftDim(isl::union_map UMap, isl::dim Dim, int Pos,
                                int Amount) {
   isl::union_map Result = isl::union_map::empty(UMap.get_space());
 
-  UMap.foreach_map([=, &Result](isl::map Map) -> isl::stat {
+  for (isl::map Map : UMap.get_map_list()) {
     isl::map Shifted = shiftDim(Map, Dim, Pos, Amount);
     Result = Result.add_map(Shifted);
-    return isl::stat::ok;
-  });
+  }
   return Result;
 }
 
 void polly::simplify(isl::set &Set) {
   Set = isl::manage(isl_set_compute_divs(Set.copy()));
   Set = Set.detect_equalities();
   Set = Set.coalesce();
 }
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) {
+  for (isl::map Map : UMap.get_map_list()) {
     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);
 
if (!USet) {
     return;
   }
 
   if (Simplify)
     simplify(USet);
 
   // Get all the polyhedra.
   std::vector<isl::basic_set> BSets;
-  USet.foreach_set([&BSets](isl::set Set) -> isl::stat {
-    Set.foreach_basic_set([&BSets](isl::basic_set BSet) -> isl::stat {
+
+  for (isl::set Set : USet.get_set_list()) {
+    for (isl::basic_set BSet : Set.get_basic_set_list()) {
       BSets.push_back(BSet);
-      return isl::stat::ok;
-    });
-    return isl::stat::ok;
-  });
+    }
+  }
 
   if (BSets.empty()) {
     OS << "{\n}\n";
     return;
   }
 
   // Sort the polyhedra.
   llvm::sort(BSets.begin(), BSets.end(), orderComparer);

 /// a set of singleton polyhedra. Unbounded dimensions are not expanded.
 ///
 /// Example:
 ///   { [i] : 0 <= i < 2 }
 /// is expanded to:
 ///   { [0]; [1] }
 static isl::set expand(const isl::set &Set) {
   isl::set Expanded = isl::set::empty(Set.get_space());
-  Set.foreach_basic_set([&](isl::basic_set BSet) -> isl::stat {
+  for (isl::basic_set BSet : Set.get_basic_set_list())
     recursiveExpand(BSet, 0, Expanded);
-    return isl::stat::ok;
-  });
   return Expanded;
 }
 
 /// Expand all points of a union set explicit.
 ///
 /// @see expand(const isl::set)
 static isl::union_set expand(const isl::union_set &USet) {
   isl::union_set Expanded = isl::union_set::empty(USet.get_space());
-  USet.foreach_set([&](isl::set Set) -> isl::stat {
+  for (isl::set Set : USet.get_set_list()) {
     isl::set SetExpanded = expand(Set);
     Expanded = Expanded.add_set(SetExpanded);
-    return isl::stat::ok;
-  });
+  }
   return Expanded;
 }
 
 LLVM_DUMP_METHOD void polly::dumpPw(const isl::set &Set) {
   printSortedPolyhedra(Set, llvm::errs(), true, false);
 }
 
 LLVM_DUMP_METHOD void polly::dumpPw(const isl::map &Map) {