[ADT] Teach reverse() about filter_iterator ranges

[vsk]

Summary

This makes it possible to reverse a filtered range. For example, here's
a way to visit memory accesses in a BasicBlock in reverse order:

auto MemInsts = reverse(make_filter_range(BB, [](Instruction &I) {
  return isa<StoreInst>(&I) || isa<LoadInst>(&I);
}));

for (auto &MI : MemInsts)
  ...

To implement this functionality, I added an overload of reverse() which
is enabled just for filter_iterator ranges. The overload invalidates the
original range and creates a new filter_iterator range using reverse
iterators.

I'd appreciate any comments about how to make this cleaner. The only
alternative approach I considered was to get filter_iterator to adopt
bidirectional_iterator_tag and define an operator-- conditionally, but I
couldn't get this to work out.

This was motivated by a problem we encountered in D45657: we'd like to
visit the non-debug-info instructions in a BasicBlock in reverse order.

Testing: check-llvm, check-clang

[vsk]

• Avoid some code movement.

[vsk]

• Add some more tests.

[zturner]

include/llvm/ADT/STLExtras.h

235

Can we use std::rbegin() and std::rend() instead of C.rbegin() and C.rend()? This way it works for arrays too.

236–247

Can we put these two functions in the detail namespace?

237

I'd rather overload make_reverse_iterator() instead of reverse(), then have one implementation of reverse()

238–239

Do we need the enable_if? Won't the non-existence of C.rbegin() trigger SFINAE and fall back to the second overload?

[aprantl]

include/llvm/ADT/STLExtras.h

290

///

323

///
there's more below...

[vsk]

• Simplify the is_filter_iterator predicate.
• Fix up some doxygen comments.
• Remove an unnecessary enable_if.

include/llvm/ADT/STLExtras.h

235

I think this overload already works with arrays. Do you have an example of a case that's not supported?

236–247

I can do that in a follow-up. Aside from make_reverse_iterator, which other function did you have in mind?

237

This doesn't seem to be possible. A filter_iterator pointing to the end of the sequence can't meaningfully be reversed, because the Payload would be missing.

238–239

Nope, nice catch, we don't need this enable_if. I'll get rid of it.

[timshen]

My understanding is that, the reason why reverse_iterator<filter_iterator<I, F>> doesn't "just work" is because filter_iterator<I> is only a forward_iterator, while reverse_iterator expects a bidirectional_iterator. Can we make filter_iterator bidirectional instead?

[zturner]

In D45792#1072601, @timshen wrote:

My understanding is that, the reason why reverse_iterator<filter_iterator<I, F>> doesn't "just work" is because filter_iterator<I> is only a forward_iterator, while reverse_iterator expects a bidirectional_iterator. Can we make filter_iterator bidirectional instead?

Yea it seems like filter_iterator should be bidirectional if and only if the underlying range is bidirectional.

[dblaikie]

+1 - I'd rather not have a special case for filter+reverse if we can help
it. If filter can be made bidi so it "just works" without reverse knowing
anything about it, that seems better.

[vsk]

In D45792#1072601, @timshen wrote:

My understanding is that, the reason why reverse_iterator<filter_iterator<I, F>> doesn't "just work" is because filter_iterator<I> is only a forward_iterator, while reverse_iterator expects a bidirectional_iterator. Can we make filter_iterator bidirectional instead?

I think it's possible. I've sketched a version of this which passes tests: https://reviews.llvm.org/D45853. I haven't got all of the enable_ifs finalized, but it should be simpler than this patch.

The downside is that it introduces copies of the wrapped begin/end iterators, as well as the predicate functor. That's why I'm leaning towards adding an overload of reverse(), but I'm open to either approach.

[vsk]

In D45792#1072947, @vsk wrote:

In D45792#1072601, @timshen wrote:

My understanding is that, the reason why reverse_iterator<filter_iterator<I, F>> doesn't "just work" is because filter_iterator<I> is only a forward_iterator, while reverse_iterator expects a bidirectional_iterator. Can we make filter_iterator bidirectional instead?

I think it's possible. I've sketched a version of this which passes tests: https://reviews.llvm.org/D45853. I haven't got all of the enable_ifs finalized, but it should be simpler than this patch.

The downside is that it introduces copies of the wrapped begin/end iterators, as well as the predicate functor. That's why I'm leaning towards adding an overload of reverse(), but I'm open to either approach.

I've realized that the current version of filter_iterator doesn't support predicates which capture move-only types, so I no longer have reservations about just making filter_iterator bidirectional.

I'll abandon this in favor of https://reviews.llvm.org/D45853.

include/llvm/ADT/STLExtras.h

public:
   static const bool value = sizeof(test<Ty>(nullptr)) == sizeof(yes);
 };
 
 /// Metafunction to determine if T& or T has a member called rbegin().
 template <typename Ty>
 struct has_rbegin : has_rbegin_impl<typename std::remove_reference<Ty>::type> {
 };
 
-// Returns an iterator_range over the given container which iterates in reverse.
-// Note that the container must have rbegin()/rend() methods for this to work.
-template <typename ContainerTy>
-auto reverse(ContainerTy &&C,
-             typename std::enable_if<has_rbegin<ContainerTy>::value>::type * =
-                 nullptr) -> decltype(make_range(C.rbegin(), C.rend())) {
-  return make_range(C.rbegin(), C.rend());
-}
-
-// Returns a std::reverse_iterator wrapped around the given iterator.
-template <typename IteratorTy>
-std::reverse_iterator<IteratorTy> make_reverse_iterator(IteratorTy It) {
-  return std::reverse_iterator<IteratorTy>(It);
-}
-
-// Returns an iterator_range over the given container which iterates in reverse.
-// Note that the container must have begin()/end() methods which return
-// bidirectional iterators for this to work.
-template <typename ContainerTy>
-auto reverse(
-    ContainerTy &&C,
-    typename std::enable_if<!has_rbegin<ContainerTy>::value>::type * = nullptr)
-    -> decltype(make_range(llvm::make_reverse_iterator(std::end(C)),
-                           llvm::make_reverse_iterator(std::begin(C)))) {
-  return make_range(llvm::make_reverse_iterator(std::end(C)),
-                    llvm::make_reverse_iterator(std::begin(C)));
-}
+/// An empty base class used to identify filter iterators in metaprograms.
+class filter_iterator_base {};
 
 /// An iterator adaptor that filters the elements of given inner iterators.
 ///
 /// The predicate parameter should be a callable object that accepts the wrapped
 /// iterator's reference type and returns a bool. When incrementing or
 /// decrementing the iterator, it will call the predicate on each element and
 /// skip any where it returns false.
 ///
 /// \code
 ///   int A[] = { 1, 2, 3, 4 };
 ///   auto R = make_filter_range(A, [](int N) { return N % 2 == 1; });
 ///   // R contains { 1, 3 }.
 /// \endcode
 template <typename WrappedIteratorT, typename PredicateT>
 class filter_iterator
     : public iterator_adaptor_base<
           filter_iterator<WrappedIteratorT, PredicateT>, WrappedIteratorT,
           typename std::common_type<
               std::forward_iterator_tag,
               typename std::iterator_traits<
-                  WrappedIteratorT>::iterator_category>::type> {
+                  WrappedIteratorT>::iterator_category>::type>,
+      filter_iterator_base {
   using BaseT = iterator_adaptor_base<
       filter_iterator<WrappedIteratorT, PredicateT>, WrappedIteratorT,
       typename std::common_type<
           std::forward_iterator_tag,
           typename std::iterator_traits<WrappedIteratorT>::iterator_category>::
           type>;
 
   struct PayloadType {
filter_iterator(WrappedIteratorT Begin, WrappedIteratorT End, PredicateT Pred)
         Payload(PayloadType{std::move(End), std::move(Pred)}) {
     findNextValid();
   }
 
   // Construct the end iterator. It's not incrementable, so Payload doesn't
   // have to be engaged.
   filter_iterator(WrappedIteratorT End) : BaseT(End) {}
 
+  // Used to implement a predicate to check if an object is a filter_iterator.
+  template<typename Ty>
+  friend struct is_filter_iterator;
+
 public:
   using BaseT::operator++;
+  using BaseT::wrapped;
 
   filter_iterator &operator++() {
     BaseT::operator++();
     findNextValid();
     return *this;
   }
 
   template <typename RT, typename PT>
   friend iterator_range<filter_iterator<detail::IterOfRange<RT>, PT>>
   make_filter_range(RT &&, PT);
+
+  /// Move the predicate out of the iterator. This invalidates the iterator.
+  PredicateT takePredicate() {
+    assert(Payload && "Cannot find the predicate");
+    PredicateT P = std::move(Payload->Pred);
+    Payload = None;
+    return std::move(P);
+  }
+};
+
+/// Metafunction to determine if T is a filter iterator.
+template <typename Ty> struct is_filter_iterator {
+  static const bool value = std::is_base_of<filter_iterator_base, Ty>::value;
 };
 
+/// Returns an iterator_range over the given container which iterates in
+/// reverse. Note that the container must have rbegin()/rend() methods for this
+/// overload to be selected.
+template <typename ContainerTy>
+auto reverse(ContainerTy &&C) -> decltype(make_range(C.rbegin(), C.rend())) {
+  return make_range(C.rbegin(), C.rend());
+}
+
 /// Convenience function that takes a range of elements and a predicate,
 /// and return a new filter_iterator range.
 ///
 /// FIXME: Currently if RangeT && is a rvalue reference to a temporary, the
 /// lifetime of that temporary is not kept by the returned range object, and the
 /// temporary is going to be dropped on the floor after the make_iterator_range
 /// full expression that contains this function call.
 template <typename RangeT, typename PredicateT>
 iterator_range<filter_iterator<detail::IterOfRange<RangeT>, PredicateT>>
 make_filter_range(RangeT &&Range, PredicateT Pred) {
   using FilterIteratorT =
       filter_iterator<detail::IterOfRange<RangeT>, PredicateT>;
   return make_range(FilterIteratorT(std::begin(std::forward<RangeT>(Range)),
                                     std::end(std::forward<RangeT>(Range)),
                                     std::move(Pred)),
                     FilterIteratorT(std::end(std::forward<RangeT>(Range))));
 }
 
+/// Returns a std::reverse_iterator wrapped around the given iterator.
+template <typename IteratorTy>
+std::reverse_iterator<IteratorTy> make_reverse_iterator(IteratorTy It) {
+  return std::reverse_iterator<IteratorTy>(It);
+}
+
+/// Returns an iterator_range over the given container which iterates in
+/// reverse. Note that the container must have begin()/end() methods which
+/// return bidirectional iterators for overload to be selected.
+template <typename ContainerTy>
+auto reverse(
+    ContainerTy &&C,
+    typename std::enable_if<
+        !has_rbegin<ContainerTy>::value &&
+        !is_filter_iterator<decltype(std::begin(C))>::value>::type * = nullptr)
+    -> decltype(make_range(llvm::make_reverse_iterator(std::end(C)),
+                           llvm::make_reverse_iterator(std::begin(C)))) {
+  return make_range(llvm::make_reverse_iterator(std::end(C)),
+                    llvm::make_reverse_iterator(std::begin(C)));
+}
+
+/// Returns an iterator_range over the given filtered range which iterates in
+/// reverse. Note that this invalidates the input filtered range.
+template <typename FilteredRangeT>
+auto reverse(
+    FilteredRangeT &&R,
+    typename std::enable_if<
+        is_filter_iterator<decltype(R.begin())>::value>::type * = nullptr)
+    -> decltype(make_filter_range(
+        make_range(llvm::make_reverse_iterator(R.end().wrapped()),
+                   llvm::make_reverse_iterator(R.begin().wrapped())),
+        R.begin().takePredicate())) {
+  return make_filter_range(
+      make_range(llvm::make_reverse_iterator(R.end().wrapped()),
+                 llvm::make_reverse_iterator(R.begin().wrapped())),
+      R.begin().takePredicate());
+}
+
 // forward declarations required by zip_shortest/zip_first
 template <typename R, typename UnaryPredicate>
 bool all_of(R &&range, UnaryPredicate P);
 
 template <size_t... I> struct index_sequence;
 
 template <class... Ts> struct index_sequence_for;
 

unittests/ADT/IteratorTest.cpp

 //===- IteratorTest.cpp - Unit tests for iterator utilities ---------------===//
 //
 //                     The LLVM Compiler Infrastructure
 //
 // This file is distributed under the University of Illinois Open Source
 // License. See LICENSE.TXT for details.
 //
 //===----------------------------------------------------------------------===//
 
 #include "llvm/ADT/iterator.h"
+#include "llvm/ADT/ArrayRef.h"
 #include "llvm/ADT/STLExtras.h"
 #include "llvm/ADT/SmallVector.h"
 #include "gtest/gtest.h"
 
 using namespace llvm;
 
 namespace {
 
TEST(FilterIteratorTest, InputIterator) {
   int A[] = {0, 1, 2, 3, 4, 5, 6};
   auto Range = make_filter_range(
       make_range(InputIterator(std::begin(A)), InputIterator(std::end(A))),
       IsOdd);
   SmallVector<int, 3> Actual(Range.begin(), Range.end());
   EXPECT_EQ((SmallVector<int, 3>{1, 3, 5}), Actual);
 }
 
+TEST(FilterIteratorTest, ReverseFilterRange) {
+  auto IsOdd = [](int N) { return N % 2 == 1; };
+  int A[] = {0, 1, 2, 3, 4, 5, 6};
+
+  // Check basic reversal.
+  auto Range = reverse(make_filter_range(A, IsOdd));
+  SmallVector<int, 3> Actual(Range.begin(), Range.end());
+  EXPECT_EQ((SmallVector<int, 3>{5, 3, 1}), Actual);
+
+  // Check that the reverse of the reverse is the original.
+  auto Range2 = reverse(reverse(make_filter_range(A, IsOdd)));
+  SmallVector<int, 3> Actual2(Range2.begin(), Range2.end());
+  EXPECT_EQ((SmallVector<int, 3>{1, 3, 5}), Actual2);
+
+  // Check empty ranges.
+  auto Range3 = reverse(make_filter_range(ArrayRef<int>(), IsOdd));
+  SmallVector<int, 0> Actual3(Range3.begin(), Range3.end());
+  EXPECT_EQ((SmallVector<int, 0>{}), Actual3);
+
+  // Check that we don't skip the first element, provided it isn't filtered
+  // away.
+  auto IsEven = [](int N) { return N % 2 == 0; };
+  auto Range4 = reverse(make_filter_range(A, IsEven));
+  SmallVector<int, 4> Actual4(Range4.begin(), Range4.end());
+  EXPECT_EQ((SmallVector<int, 4>{6, 4, 2, 0}), Actual4);
+}
+
 TEST(PointerIterator, Basic) {
   int A[] = {1, 2, 3, 4};
   pointer_iterator<int *> Begin(std::begin(A)), End(std::end(A));
   EXPECT_EQ(A, *Begin);
   ++Begin;
   EXPECT_EQ(A + 1, *Begin);
   ++Begin;
   EXPECT_EQ(A + 2, *Begin);

unittests/IR/BasicBlockTest.cpp

TEST(BasicBlockTest, PhiRange) {
   }
 
   // Test that we can use const iterators and generally that the iterators
   // behave like iterators.
   BasicBlock::const_phi_iterator CI;
   CI = BB->phis().begin();
   EXPECT_NE(CI, BB->phis().end());
 
+  // Test that filtering iterators work with basic blocks.
+  auto isPhi = [](Instruction &I) { return isa<PHINode>(&I); };
+  auto Phis = make_filter_range(*BB, isPhi);
+  auto ReversedPhis = reverse(make_filter_range(*BB, isPhi));
+  EXPECT_EQ(std::distance(Phis.begin(), Phis.end()), 3);
+  EXPECT_EQ(&*Phis.begin(), P1);
+  EXPECT_EQ(std::distance(ReversedPhis.begin(), ReversedPhis.end()), 3);
+  EXPECT_EQ(&*ReversedPhis.begin(), P3);
+
   // And iterate a const range.
   for (const auto &PN : const_cast<const BasicBlock *>(BB.get())->phis()) {
     EXPECT_EQ(BB.get(), PN.getIncomingBlock(0));
     EXPECT_EQ(BB1.get(), PN.getIncomingBlock(1));
     EXPECT_EQ(BB2.get(), PN.getIncomingBlock(2));
   }
 }
 
 } // End anonymous namespace.
 } // End llvm namespace.