[Polly] Implement an iterator for isl maps, basic_maps, sets, basic_sets

[philip.pfaffe]

Summary

Provide an iterator to simplify iteration over some isl collections.
Since these types do not natively support iteration, they have to be converted
to an list first by the caller, but can then be used in a ranged for loop:

isl::set S;
for (auto SubSet : S.get_basic_set_list ()) {
  // ...
}

[Meinersbur]

For reference: This is an alternative to D47604

[suggestion] Add unit tests for iterating over isl sets.

include/polly/Support/ISLTools.h

28 ↗

(On Diff #151197)

Why not const List &?

50 ↗

(On Diff #151197)

Should this hold a reference to the list? That is, the underlying object is not freed until all iterators are destroyed.

90 ↗

(On Diff #151197)

[suggestion] Make it take const isl::map_list &M, so we safe a reference counting cycle.

[serious] Without having looked further into it, does the map_iterator store a pointer to M, which does goes out-of-scope after leaving this function?

[philip.pfaffe]

include/polly/Support/ISLTools.h

28 ↗

(On Diff #151197)

I guess technically it could be const, since in isl everything is by-value.

50 ↗

(On Diff #151197)

It needs a reference to do the iteration.

90 ↗

(On Diff #151197)

You're right, this should take a reference to the list.

[philip.pfaffe]

Add a unittest and address comments

[philip.pfaffe]

Looks like I forgot to add pollydev as a subscriber. Shall I resubmit the patch?

[Meinersbur]

Thanks for the test case

In D48136#1132114, @philip.pfaffe wrote:

Looks like I forgot to add pollydev as a subscriber. Shall I resubmit the patch?

Don't think it's necessary.

include/polly/Support/ISLTools.h

50 ↗

(On Diff #151197)

What I mean is that the iterator could increase isl's ref counter to ensure that it is not free'd as long as one iterator exists. That is, is the following code valid?

basic_set_iterator I, E;
{
  auto List = S.get_basic_set_list();
  I = begin(List); E = end(List);
} // List out-of-scope here
for (; I != E; ++I) { ... }

unittests/Support/ISLTools.cpp

12 ↗

(On Diff #151311)

Ctx no free'd?

[grosser]

Thank you Philip. This clearly looks a lot better than my patch. From my perspective this looks good after Michael's comments are addressed. Thanks a lot.

[philip.pfaffe]

Free the context in the unittest.

[philip.pfaffe]

include/polly/Support/ISLTools.h

50 ↗

(On Diff #151197)

Well, if you destroy the container you obtained iterators for and then use the iterators, that's on you ;)

[Meinersbur]

include/polly/Support/ISLTools.h

50 ↗

(On Diff #151197)

Using reference counting would allow us to not invalidate the iterators.

It's not just destroying the container, but also modifying it while iterating. Isl objects are reference counted, so the underlying object might be shared by other references as well.

At least it should be documented when iterators are invalidated.

unittests/Support/ISLTools.cpp

24 ↗

(On Diff #151674)

[suggestion] I quite like using RAII to free the isl_ctx as done in IslTest.cpp:

std::unique_ptr<isl_ctx, decltype(&isl_ctx_free)> Ctx(isl_ctx_alloc(), &isl_ctx_free);

[philip.pfaffe]

include/polly/Support/ISLTools.h

50 ↗

(On Diff #151197)

If I capture the List by value, how do I compare iterators? I'll have to compare the lists by value then, and that's quite expensive.

I can certainly document iterator invalidation, but it behaves just as you'd expect: destruction or modification of the list invalidate.

unittests/Support/ISLTools.cpp

24 ↗

(On Diff #151674)

Why doesn't the C++ wrapper do this already?

[philip.pfaffe]

RAII management of the isl_ctx

[Meinersbur]

include/polly/Support/ISLTools.h

50 ↗

(On Diff #151197)

Comparison of iterators from different containers is undefined (except: value-initialized iterators). You can also compare their pointers: List.get() == O.get(). However, since isl list objects use copy-on-write as an implementation detail, it pointer-equality of two list references (as in: two variables of lists that may or may not contain the same elements) was never well-defined.

IMHO the interesting question is whether the additional definedness/safety (accidentally invalidating an iterator is one of my least favorite kinds of bugs) is worth the potential overhead of reference counter increment/decrement.

unittests/Support/ISLTools.cpp

24 ↗

(On Diff #151674)

We could not decide what the right approach is. Freeing the isl_ctx would mean that isl::ctx owns the reference. But in most cases, you are not owning it: E.g. if returned by a get_ctx function to do something else.

[philip.pfaffe]

include/polly/Support/ISLTools.h

50 ↗

(On Diff #151197)

I'll buy the comparison point, but I'm not comfortable relying on copy semantics of isl lists:

• the iterator is a template. I can instantiate it for std::vector.
• it'd mean depending on internal implementation details of isl lists.
• iterator use-after-invalidation is a bug everywhere in the code, and is easily checkable. Valgrind will detect this immediately.

[philip.pfaffe]

unittests/Support/ISLTools.cpp

24 ↗

(On Diff #151674)

Then why not just return the C object? Or decide ownership based on how the object is constructed?

[bollu]

include/polly/Support/ISLTools.h

50 ↗

(On Diff #151197)

So, I now understand what you mean when you said that the copy-on-write is part of the implementation, not the interface.

If I understood correctly, you mean that:

1. If we use const ListT List, and then ISL decides to use std::vector (at which point, ISL's interface changes, since it has abandoned COW semantics), our code will need to change.

2. However, if we use const ListT* List, then if ISL decides to use std::vector, out code will not need to change.

Hence, 2 is better than 1 since it makes less assumptions about ISL's semantics, and leads to less code churn.

Please correct me if I am mis-representing your position.

Is this implementation morally correct _today_?

While I agree with this position from a software engineering perspective, I disagree with it when it comes to the semantics of your code.

By holding a const ListT *List, with respect to ISL's _current_ interface, you are holding a pointer-to-pointer (so, something like a weak reference). Hence, I feel that this implementation violates ISL's _current_ interface, to prevent code churn in the _future_ (which is unlikely, BTW) that ISL changes its COW semantics.

Keeping a const ListT List is in line with ISL's _current_ interface of COW semantics, and is thus the correct choice.

UB with respect to iterators if ISL decides to clone objects

Another argument put forth was that if ISL changes the implementation of COW to actually clone the underlying object, then something like:

isl_list l1 = ...;
auto begin1 = l1.begin();

isl_list l2 = l1;
auto end2 = l2.end();

// UB, since we are comparing iterators across different objects,
// since ISL cloned L2 into L1.
if (begin1 != end2) {
    ...
}

I don't believe this triggers UB according to iterator semantics.

1. Definition of input iterator

An input iterator is one that satisfies the iterator laws (de-referncible, existence of ++, along with a == operator.

By this definition, yes the example given would be UB, since I'm performing == between two iterators in different domains. However, there are two important caveats that make this argument incorrect:

a. [EqualityComparable == is an equivalence relation](http://eel.is/c++draft/utility.arg.requirements#tab:equalitycomparable)

is an equivalence relation, that is, it has the following properties:

...

b. Domain of an iterator can change over time

term the domain of == is used in the ordinary mathematical sense to denote the set of values over which == is (required to be) defined. This set can change over time.

So, _as the iterator implementor_, I can say that when

l2 = l1;

occurs, then __the domain of == on begin1 expands to contain all valid iterators of l2, and vice versa for `end2.

This way, begin1 == end2 is perfectly well defined and the compiler cannot optimise this away.

Practically, is const ListT List nicer or const ListT* List

From a usability perspective, assuming that ISL does not change its COW semantics (and therefore we pay no code churn), I much prefer const ListT List, since not only does it respect the current interface semantics, but it also makes debugging easier as Michael pointed out.

Hence, I vote for const ListT List :)

[philip.pfaffe]

include/polly/Support/ISLTools.h

50 ↗

(On Diff #151197)

So I'm not going to make this a value instead of a reference:

While the moral issue is indisputable per se, this is purely a software engineering issue, and morals don't count if they don't help. We can debate whether COW semantics is public or private implementation, but the fact is that with a List value I'd depend on an implementation detail that I do not have to depend on. Every SE book and lecture on the planet agrees that's a bad idea.

Having an iterator own a copy of the container it iterates is just insane. Nobody can read the code without stumbling over this, and nobody can understand it without in-depth knowledge of isl. A reference is absolutely clear in the intent and behaviour of this implementation.

I disagree with Micheal's argument for debuggability. In the current implementation of the iterator and isl, the only possible kind of invalidation is if the container goes out of scope, because it is immutable. That's a dangling reference error and is easily debuggable.

[Meinersbur]

A follow-up to last week's phone call:

C++ compilers cannot optimize iterators based on what the equality operator's domain is because the compiler has no understanding of what a iterator is. It is a library concept.

Previous drafts for C++ contained axioms, which could be used by the compiler for optimization (I think they were mostly meant for correctness checking, not optimization, as concepts were also mostly about improving compiler error messages), if such axiom was added to the iterator concept. This is speculative, but I'd assume such a axiom could at most be added to iterator implementations, not iterators in general. Most iterators don't even store a reference/pointer/etc to the container object they are iterating over.

The most recent draft for concepts does not contain axiom or mention that these could be used for compiler optimizations.

unittests/Support/ISLTools.cpp

24 ↗

(On Diff #151674)

@grosser used this for Polly's isl-noexceptions.h since get_ctx() had to return something. The isl version of it never generated something using isl_ctx as parameter or return value. I don't know why he chose to not use isl_ctx directly, but I had no objections.

[bollu]

@Meinersbur even assuming that such a concept exists (since one could argue such a concept does exist for a range-based for loop to work), I still don't think it allows the compiler to optimise away iterators based on the interpretation of the spec I outlined (== is an equivalence relation whose domain is mutable).

[bollu]

Sorry, I meant to accept this last week. I accept this as an acceptable "software engineering" compromise, while I still hold the philosophical reservations I have mentioned.

[bollu]

@Meinersbur If you are opposed to merging this, please request changes.

[Meinersbur]

Committing is ok, I merely disagree with @philip.pfaffe's arguments, not with the patch itself.

polly/trunk/include/polly/Support/ISLTools.h

 // Integer Set Library (isl).
 //
 //===----------------------------------------------------------------------===//
 
 #ifndef POLLY_ISLTOOLS_H
 #define POLLY_ISLTOOLS_H
 
 #include "polly/Support/GICHelper.h"
+#include "llvm/ADT/iterator_range.h"
+
+namespace isl {
+inline namespace noexceptions {
+
+template <typename DerivedT, typename ElementT, typename ListT>
+struct iterator_base : public llvm::iterator_facade_base<
+                           iterator_base<DerivedT, ElementT, ListT>,
+                           std::forward_iterator_tag, ElementT> {
+  explicit iterator_base(const ListT &List) : List(&List) {
+    Position = static_cast<DerivedT *>(this)->list_size();
+  }
+  iterator_base(const ListT &List, int Position) : List(&List), Position(Position) {}
+  iterator_base &operator=(const iterator_base &R) = default;
+
+  bool operator==(const iterator_base &O) const {
+    return List == O.List && Position == O.Position;
+  }
+
+  DerivedT &operator++() {
+    ++Position;
+    return *static_cast<DerivedT *>(this);
+  }
+
+  DerivedT operator++(int) {
+    DerivedT Copy{static_cast<DerivedT *>(this)};
+    ++Position;
+    return Copy;
+  }
+
+protected:
+  const ListT *List;
+  int Position = 0;
+};
+
+struct map_iterator : iterator_base<map_iterator, isl::map, isl::map_list> {
+  using BaseT = iterator_base<map_iterator, isl::map, isl::map_list>;
+  using BaseT::BaseT;
+  isl::map operator*() const { return List->get_map(this->Position); }
+  int list_size() const { return this->List->n_map(); }
+};
+
+struct basic_map_iterator
+    : iterator_base<basic_map_iterator, isl::basic_map, isl::basic_map_list> {
+  using BaseT =
+      iterator_base<basic_map_iterator, isl::basic_map, isl::basic_map_list>;
+  using BaseT::BaseT;
+  isl::basic_map operator*() const {
+    return List->get_basic_map(this->Position);
+  }
+  int list_size() const { return this->List->n_basic_map(); }
+};
+
+struct set_iterator : iterator_base<set_iterator, isl::set, isl::set_list> {
+  using BaseT = iterator_base<set_iterator, isl::set, isl::set_list>;
+  using BaseT::BaseT;
+  isl::set operator*() const { return List->get_set(this->Position); }
+  int list_size() const { return this->List->n_set(); }
+};
+
+struct basic_set_iterator
+    : iterator_base<basic_set_iterator, isl::basic_set, isl::basic_set_list> {
+  using BaseT =
+      iterator_base<basic_set_iterator, isl::basic_set, isl::basic_set_list>;
+  using BaseT::BaseT;
+  isl::basic_set operator*() const {
+    return List->get_basic_set(this->Position);
+  }
+  int list_size() const { return this->List->n_basic_set(); }
+};
+
+inline map_iterator begin(const isl::map_list &M) { return map_iterator(M, 0); }
+inline map_iterator end(const isl::map_list &M) { return map_iterator(M); }
+inline set_iterator begin(const isl::set_list &M) { return set_iterator(M, 0); }
+inline set_iterator end(const isl::set_list &M) { return set_iterator(M); }
+inline basic_map_iterator begin(const isl::basic_map_list &M) {
+  return basic_map_iterator(M, 0);
+}
+inline basic_map_iterator end(const isl::basic_map_list &M) {
+  return basic_map_iterator(M);
+}
+inline basic_set_iterator begin(const isl::basic_set_list &M) {
+  return basic_set_iterator(M, 0);
+}
+inline basic_set_iterator end(const isl::basic_set_list &M) {
+  return basic_set_iterator(M);
+}
+
+} // namespace noexceptions
+} // namespace isl
 
 namespace polly {
 
 /// 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).

polly/trunk/unittests/CMakeLists.txt

function(add_polly_unittest test_name)
   target_link_libraries(${test_name} PRIVATE Polly)
 endfunction()
 
 add_subdirectory(Isl)
 add_subdirectory(Flatten)
 add_subdirectory(DeLICM)
 add_subdirectory(ScopPassManager)
 add_subdirectory(ScheduleOptimizer)
+add_subdirectory(Support)

polly/trunk/unittests/Support/CMakeLists.txt

+add_polly_unittest(ISLToolsTests
+  ISLTools.cpp
+  )

polly/trunk/unittests/Support/ISLTools.cpp

+#include "polly/Support/ISLTools.h"
+#include "gmock/gmock.h"
+#include "gtest/gtest.h"
+
+namespace isl {
+static bool operator==(const isl::basic_set &A, const isl::basic_set &B) {
+  return A.is_equal(B);
+}
+}
+
+TEST(Support, isl_iterator) {
+  std::unique_ptr<isl_ctx, decltype(&isl_ctx_free)> RawCtx(isl_ctx_alloc(),
+                                                           &isl_ctx_free);
+  isl::ctx Ctx(RawCtx.get());
+
+  isl::basic_set A(
+      Ctx, "{ [x, y] : 0 <= x <= 5 and y >= 0 and x > 0 and 0 < y <= 5 }");
+  isl::basic_set B(
+      Ctx, "{ [x, y] : 0 <= x <= 5 and y >= 0 and x <= 4 and y <= 3 + x }");
+  isl::set S = A.unite(B);
+
+  ASSERT_EQ(S.n_basic_set(), 2);
+  std::vector<isl::basic_set> Sets;
+  for (auto BS : S.get_basic_set_list())
+    Sets.push_back(BS);
+  EXPECT_THAT(Sets, testing::UnorderedElementsAre(A, B));
+}