[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.