[llvm] Make Sequence reverse-iterable

[gchatelet]

Summary

This patch simplifies the implementation of Sequence and makes it compatible with llvm::reverse.
It exposes the reverse iterators through rbegin/rend which prevents a dangling reference in std::reverse_iterator::operator++().

[courbet]

llvm/include/llvm/ADT/Sequence.h

90

why is this no longer a random access iterator ?

91

Let's keep the forwarnding reference ctor for when T is expensive:

template <typename U, typename Enabler = decltype(ValueT(std::declval<U>()))>
  value_sequence_iterator(U &&Value) : Value(std::forward<U>(Value)) {}

145

Does this need to be public ?

145

should this be value_range ?

163

template <typename U, typename Enabler = decltype(ValueT(std::declval<U>()))>
value_sequence(U &&Begin, U&& end);

or even:

template <typename U1,, typename U2, typename Enabler = decltype(ValueT(std::declval<U1>())),typename Enabler = decltype(ValueT(std::declval<U2>()))>
value_sequence(U1 &&Begin, U2&& end);

[gchatelet]

llvm/include/llvm/ADT/Sequence.h

90

forward_iterator ought to be enough for everyone : )
More seriously I first thought it would suffice and it does for all of llvm, except MLIR. It does something funky with its metadata and assumes that the underlying iterator is random access. I've implemented the random access iterator trait but it makes the code more complex.

163

This introduces some resolution issues and I'm not sure this brings much.
Iterators must be lightweight and copyable by definition.

edit: This one can actually be solved by the second version with two typename template parameters. It still feels a bit overkill to me but let me know it you think it's worth it.

In file included from /redacted/git/llvm-project/llvm/lib/Analysis/LoopCacheAnalysis.cpp:30:
/redacted/git/llvm-project/llvm/include/llvm/ADT/Sequence.h:86:41: error: no matching constructor for initialization of 'llvm::value_range<unsigned int>::const_iterator' (aka 'value_range_iterator<unsigned int, true>')
  const_iterator begin() const { return {Begin}; }
                                        ^~~~~~~
/redacted/git/llvm-project/llvm/lib/Analysis/LoopCacheAnalysis.cpp:169:20: note: in instantiation of member function 'llvm::value_range<unsigned int>::begin' requested here
  for (auto SubNum : seq<unsigned>(0, NumSubscripts - 1)) {
                   ^
/redacted/git/llvm-project/llvm/include/llvm/ADT/Sequence.h:30:3: note: candidate constructor not viable: no known conversion from 'llvm::value_range<unsigned int>::value_type' (aka 'const unsigned int') to 'const llvm::detail::value_range_iterator<unsigned int, true>' for 1st argument
  value_range_iterator(const value_range_iterator &) = default;
  ^
/redacted/git/llvm-project/llvm/include/llvm/ADT/Sequence.h:33:3: note: candidate template ignored: substitution failure [with U = const unsigned int &]: use of undeclared identifier 'ValueT'
  value_range_iterator(U &&Value) : Value(std::forward<U>(Value)) {}
  ^
/redacted/git/llvm-project/llvm/include/llvm/ADT/Sequence.h:28:3: note: candidate constructor not viable: requires 0 arguments, but 1 was provided
  value_range_iterator() = default;
  ^

[gchatelet]

• Address comments

[gchatelet]

llvm/include/llvm/ADT/SmallVector.h

1

This one is not to be submitted but helps make tests D102760 is under review.

[courbet]

llvm/include/llvm/ADT/Sequence.h

35

style (here and below)

146

why const ? This makes value_range not movable.

163

Given that ValueT is a template parameter it is generally a good practice to not assume anything about the cost of copying.
We might have a cheaply movable but expensive to copy ValueT for example. A user might want to move the bounds into the value range.

(And BTW given that the iterator holds a member variable of type ValueT, the iterator is not necessarily cheap to copy, so we might as well try to avoid the copies).

that being said I only see seq currently being used with integers, so your call.

178

std::move(Begin), std::move(End) if you go with the forwarding reference ctors

[mehdi_amini]

llvm/include/llvm/ADT/Sequence.h

52

Why all the upper case for the method here?

[gchatelet]

• Addressing comments

llvm/include/llvm/ADT/Sequence.h

146

Indeed

[courbet]

llvm/include/llvm/ADT/Sequence.h

93

This is formally OK given that the return value T verifies __Referenceable<T>, but is there any reason not to return a const T& ?
(Again, this is mostly a theoretical argument, feel free to ignore.)

[gchatelet]

• remove unneeded container traits, simplify implementation

[gchatelet]

llvm/include/llvm/ADT/Sequence.h

93

Yes there is a reason.
A typical range or container holds all of its values and iterators refer to them, so it makes sense to return a reference because the value outlives the iterator.
In this particular case the iterator contains the value which might lead to dangling references.

In fact this is why I had to provide the reverse iterators in the first place. With the original Sequence code, the std::reverse_iterator's pre-increment operator generated from Sequence::iterator behaves like a post-increment operator and copies the iterator. Pseudo code:

reverse_iterator operator++(int) {
  reverse_iterator Tmp = *this;
  ++(*this);
  return Tmp;
}

In the following code, value ends up being a dangling reference.

auto sequence = std::reverse(llvm::Seq(0, 10));
const auto& value = *++sequence.begin();

Using a value type instead of a reference type should trigger an error from the compiler in such cases.

[courbet]

llvm/include/llvm/ADT/Sequence.h

93

Makes sense, thanks for the explanation.

[gchatelet]

• Remove dependency in SmallVector, use begin/end elsewhere

[gchatelet]

• Remove dependency in SmallVector, use begin/end elsewhere

[gchatelet]

@courbet do you mind having another look?
I reverted the changes in SmallVector as stated in D102760 and used begin/end instead.

[gchatelet]

• PDLToPDLInterp modification can now be simplified

[• Quuxplusone]

llvm/include/llvm/ADT/Sequence.h

26–28

Lines 26 and 28, please avoid std::iterator because it is deprecated in C++17 and I assume we anticipate compiling LLVM with -std=c++17 in the near future. Just write out the 5 public member typedefs by hand. (Actually you already write out difference_type, so there's only 4 typedefs left. ;))

48

Naming nit: When I saw Forward in an iterator context, I assumed you were talking about forward iterators versus bidirectional iterators, and was going to say "technically, bidirectional iterators are also forward iterators." But on second glance I see that by IsForward you really mean IsNotReversed. I suggest s/IsForward/!IsReversed/g and s/Backward/Reverse/g.

Orthogonally, I didn't realize until operator[] that by value_range you meant not just "operator* returns by value," but actually iota_range; and I wonder if that would be a good renaming.

62–64

I suspect this should be just

explicit value_range_iterator(T Value) : Value(Value) {}

All constructors (except copy and move) should always be explicit; and I don't think the templatey stuff is serving a purpose here.

163

explicit value_range(value_type Begin, value_type End)
    : Begin(Begin), End(End) {}

Based on @courbet's comment, I also suggest adding static_assert(std::is_integral<ValueT>::value, ""); into this code, as a speed bump for anyone who tries to use it with non-integral types (because that's not currently a supported nor tested use-case, and they ought to think about it before plowing ahead blindly).

[gchatelet]

• Revert "PDLToPDLInterp modification can now be simplified"

[gchatelet]

• Address comments

[gchatelet]

@Quuxplusone how about renaming seq into iota then?
In a second NFC patch possibly to keep it simple.

We may also provide an overloaded version that implicitly starts at 0 (e.g. iota(5) -> 0, 1, 2, 3, 4).
More than half of the call sites use 0 explicitly as a first parameter.

llvm/include/llvm/ADT/Sequence.h

163

SGTM I have a use case that is not a primitive scalar value but a thin wrapper around it. I'll update the static_assert accordingly then.

[• Quuxplusone]

llvm/include/llvm/ADT/Sequence.h

48

@gchatelet wrote:

how about renaming seq into iota then? In a second NFC patch possibly to keep it simple.

FWIW, I would oppose that. I mean, iota is established C++ jargon — that's why I used it above when I needed one word to explain my realization — but it's still jargon; I think seq captures the intent pretty nicely. It's like the shell utility [seq](https://en.wikipedia.org/wiki/Seq_(Unix)).

We may also provide an overloaded version that implicitly starts at 0 (e.g. iota(5) -> 0, 1, 2, 3, 4). More than half of the call sites use 0 explicitly as a first parameter.

I would extremely strongly oppose a one-argument overload, if the name were iota, because std::views::iota(5) is actually 5, 6, 7, .... (This is a huge pain point and I think there's a proposal to retroactively kill off the one-argument iota from the Standard.)

If the name is kept as seq, I would mildly oppose a one-argument overload.

If the name is changed to e.g. range or xrange (a la Python), then the one-argument overload might make sense — but it would still be unnecessary, so probably provide some-cost-and-no-benefit, so probably not worth doing.

[gchatelet]

Ok so let's leave it as is. I'll address the remaining clang-tidy shortly and submit after that.

[gchatelet]

• Rebase and address tests clang-tidy.

[mehdi_amini]

Reverted ; seems like gcc5 didn't like some constructs in this patch, see details here: https://buildkite.com/mlir/mlir-core/builds/14326#2cda617f-aeb8-49d2-833c-b5a734cba86a ; let me know if you can't reproduce.

mlir/lib/Dialect/Linalg/Transforms/Vectorization.cpp

321 ↗

(On Diff #350594)

Why did we lose this direct initialization pattern? Can we adjust something to keep this?

[• Quuxplusone]

mlir/lib/Dialect/Linalg/Transforms/Vectorization.cpp

321 ↗

(On Diff #350594)

FWIW, I don't think we want to keep this. A lazy llvm::seq object physically-is something very different from a SmallVector<int64_t>; I think it's very good that the new code separates them. It might be even better to just use the std::iota algorithm to initialize the vector's contents:

SmallVector<int64_t> transposition(linalgOp.getNumLoops());
std::iota(transposition.begin(), transposition.end(), 0);
std::swap(transposition.back(), transposition[indexOp.dim()]);

If we were to keep it a one-liner, I would argue in favor of a named method on seq:

SmallVector<int64_t> transposition =
    llvm::seq<int64_t>(0, linalgOp.getNumLoops()).asSmallVector();
std::swap(transposition.back(), transposition[indexOp.dim()]);

[mehdi_amini]

mlir/lib/Dialect/Linalg/Transforms/Vectorization.cpp

321 ↗

(On Diff #350594)

A lazy llvm::seq object physically-is something very different from a SmallVector<int64_t>

Yes of course, but I don't see the point you're making here? I'm getting a lazy-range thing and I want to materialize it in a vector. We wouldn't want an implicit conversion, but that's not a reason to disallow the explicit materialization.

The question is what is the most concise and readable code for this (one-liner if possible), an llvm::iota may be palatable (to avoid begin/end forced by the std:: version), but I still find it adding a cognitive load: it actually requires to initialize a vector of zeroes before overwriting it with iota.

Probably not enough of a common pattern to optimize for though...

llvm/include/llvm/ADT/Sequence.h

 //===- Sequence.h - Utility for producing sequences of values ---*- C++ -*-===//
 //
 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
 // See https://llvm.org/LICENSE.txt for license information.
 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
 //
 //===----------------------------------------------------------------------===//
 /// \file
 /// This routine provides some synthesis utilities to produce sequences of
 /// values. The names are intentionally kept very short as they tend to occur
 /// in common and widely used contexts.
 ///
 //===----------------------------------------------------------------------===//
 
-#ifndef LLVM_ADT_SEQUENCE_H
-#define LLVM_ADT_SEQUENCE_H
+#ifndef LLVM_LLVM_INCLUDE_LLVM_ADT_SEQUENCE_H
+#define LLVM_LLVM_INCLUDE_LLVM_ADT_SEQUENCE_H
 
-#include "llvm/ADT/iterator.h"
-#include "llvm/ADT/iterator_range.h"
-#include <algorithm>
 #include <iterator>
-#include <utility>
 
 namespace llvm {
 
 namespace detail {
 
-template <typename ValueT>
-class value_sequence_iterator
-    : public iterator_facade_base<value_sequence_iterator<ValueT>,
-                                  std::random_access_iterator_tag,
-                                  const ValueT> {
-  using BaseT = typename value_sequence_iterator::iterator_facade_base;
+template <typename T, bool IsForward>
+struct value_range_iterator
+    : public std::iterator<std::random_access_iterator_tag, const T> {
+private:
+  using Base = std::iterator<std::random_access_iterator_tag, const T>;
 
-  ValueT Value;
+public:
+  using difference_type = typename Base::difference_type;
+
+private:
+  struct Forward {
+    static void Inc(T &V) { ++V; }
+    static void Dec(T &V) { --V; }
+    static void PlusAssign(T &V, difference_type Offset) { V += Offset; }
+    static void MinusAssign(T &V, difference_type Offset) { V -= Offset; }
+    static T Plus(const T &V, difference_type Offset) { return V + Offset; }
+    static T Minus(const T &V, difference_type Offset) { return V - Offset; }
+    static T ItDiff(const T &A, const T &B) { return A - B; }
+    static difference_type Cmp(const T &It1, const T &It2) { return It1 - It2; }
+  };
+  struct Backward {
+    static void Inc(T &V) { --V; }
+    static void Dec(T &V) { ++V; }
+    static void PlusAssign(T &V, difference_type Offset) { V -= Offset; }
+    static void MinusAssign(T &V, difference_type Offset) { V += Offset; }
+    static T Plus(const T &V, difference_type Offset) { return V - Offset; }
+    static T Minus(const T &V, difference_type Offset) { return V + Offset; }
+    static T ItDiff(const T &A, const T &B) { return B - A; }
+    static difference_type Cmp(const T &It1, const T &It2) { return It2 - It1; }
+  };
+  using Op = std::conditional_t<IsForward, Forward, Backward>;
 
 public:
-  using difference_type = typename BaseT::difference_type;
-  using reference = typename BaseT::reference;
+  // default-constructible
+  value_range_iterator() = default;
+  // copy-constructible
+  value_range_iterator(const value_range_iterator &) = default;
+  // value constructor
+  value_range_iterator(T Value) : Value(Value) {}
+  // copy-assignable
+  value_range_iterator &operator=(const value_range_iterator &) = default;
+  // destructible
+  ~value_range_iterator() = default;
+
+  // Can be compared for equivalence using the equality/inequality operators,
+  bool operator!=(const value_range_iterator &RHS) const {
+    return Value != RHS.Value;
+  }
+  bool operator==(const value_range_iterator &RHS) const {
+    return Value == RHS.Value;
+  }
 
-  value_sequence_iterator() = default;
-  value_sequence_iterator(const value_sequence_iterator &) = default;
-  value_sequence_iterator(value_sequence_iterator &&Arg)
-      : Value(std::move(Arg.Value)) {}
-  value_sequence_iterator &operator=(const value_sequence_iterator &Arg) {
-    Value = Arg.Value;
-    return *this;
+  // Comparison
+  bool operator<(const value_range_iterator &Other) const {
+    return Op::Cmp(Value, Other.Value) < 0;
+  }
+  bool operator<=(const value_range_iterator &Other) const {
+    return Op::Cmp(Value, Other.Value) <= 0;
+  }
+  bool operator>(const value_range_iterator &Other) const {
+    return Op::Cmp(Value, Other.Value) > 0;
+  }
+  bool operator>=(const value_range_iterator &Other) const {
+    return Op::Cmp(Value, Other.Value) >= 0;
   }
 
-  template <typename U, typename Enabler = decltype(ValueT(std::declval<U>()))>
-  value_sequence_iterator(U &&Value) : Value(std::forward<U>(Value)) {}
+  // Dereference
+  T operator*() const { return Value; }
+  T operator[](difference_type Offset) const { return Op::Plus(Value, Offset); }
 
-  value_sequence_iterator &operator+=(difference_type N) {
-    Value += N;
+  // Arithmetic
+  value_range_iterator operator+(difference_type Offset) const {
+    return {Op::Plus(Value, Offset)};
+  }
+  value_range_iterator operator-(difference_type Offset) const {
+    return {Op::Minus(Value, Offset)};
+  }
+
+  // Iterator difference
+  difference_type operator-(const value_range_iterator &Other) const {
+    return Op::ItDiff(Value, Other.Value);
+  }
+
+  // Pre/Post Increment
+  value_range_iterator &operator++() {
+    Op::Inc(Value);
     return *this;
   }
-  value_sequence_iterator &operator-=(difference_type N) {
-    Value -= N;
+  value_range_iterator operator++(int) {
+    value_range_iterator Tmp = *this;
+    Op::Inc(Value);
+    return Tmp;
+  }
+
+  // Pre/Post Decrement
+  value_range_iterator &operator--() {
+    Op::Dec(Value);
     return *this;
   }
-  using BaseT::operator-;
-  difference_type operator-(const value_sequence_iterator &RHS) const {
-    return Value - RHS.Value;
+  value_range_iterator operator--(int) {
+    value_range_iterator Tmp = *this;
+    Op::Dec(Value);
+    return Tmp;
   }
 
-  bool operator==(const value_sequence_iterator &RHS) const {
-    return Value == RHS.Value;
+  // Compound assignment operators
+  value_range_iterator &operator+=(difference_type Offset) {
+    Op::PlusAssign(Value, Offset);
+    return *this;
   }
-  bool operator<(const value_sequence_iterator &RHS) const {
-    return Value < RHS.Value;
+  value_range_iterator &operator-=(difference_type Offset) {
+    Op::MinusAssign(Value, Offset);
+    return *this;
   }
 
-  reference operator*() const { return Value; }
+private:
+  T Value;
 };
 
-} // end namespace detail
+} // namespace detail
+
+template <typename ValueT> struct value_range {
+  using value_type = const ValueT;
+  using reference = ValueT &;
+  using const_reference = const ValueT &;
+  using pointer = ValueT *;
+  using const_pointer = const ValueT *;
+  using difference_type = std::ptrdiff_t;
+  using size_type = std::size_t;
+  using iterator = detail::value_range_iterator<ValueT, true>;
+  using const_iterator = detail::value_range_iterator<ValueT, true>;
+  using reverse_iterator = detail::value_range_iterator<ValueT, false>;
+  using const_reverse_iterator = detail::value_range_iterator<ValueT, false>;
+
+  value_type Begin;
+  value_type End;
+
+  value_range(ValueT Begin, ValueT End) : Begin(Begin), End(End) {}
+
+  size_t size() const { return End - Begin; }
+  bool empty() const { return Begin == End; }
+
+  const_iterator begin() const { return {Begin}; }
+  const_iterator end() const { return {End}; }
+
+  const_reverse_iterator rbegin() const { return {End - 1}; }
+  const_reverse_iterator rend() const { return {Begin - 1}; }
+
+private:
+  static_assert(std::is_same<ValueT, std::remove_cv_t<ValueT>>::value,
+                "ValueT must not be const nor volatile");
+};
 
-template <typename ValueT>
-iterator_range<detail::value_sequence_iterator<ValueT>> seq(ValueT Begin,
-                                                            ValueT End) {
-  return make_range(detail::value_sequence_iterator<ValueT>(Begin),
-                    detail::value_sequence_iterator<ValueT>(End));
+template <typename ValueT> auto seq(ValueT Begin, ValueT End) {
+  return value_range<ValueT>(Begin, End);
 }
 
 } // end namespace llvm
 
 #endif // LLVM_ADT_SEQUENCE_H

llvm/include/llvm/ADT/SmallVector.h

 //===- llvm/ADT/SmallVector.h - 'Normally small' vectors --------*- C++ -*-===//
 //
 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
 // See https://llvm.org/LICENSE.txt for license information.
 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
 //
 //===----------------------------------------------------------------------===//
 //
 // This file defines the SmallVector class.
 //
 //===----------------------------------------------------------------------===//
 
-#ifndef LLVM_ADT_SMALLVECTOR_H
-#define LLVM_ADT_SMALLVECTOR_H
+#ifndef LLVM_LLVM_INCLUDE_LLVM_ADT_SMALLVECTOR_H
+#define LLVM_LLVM_INCLUDE_LLVM_ADT_SMALLVECTOR_H
 
+#include "llvm/ADT/Sequence.h"
 #include "llvm/ADT/iterator_range.h"
 #include "llvm/Support/Compiler.h"
 #include "llvm/Support/ErrorHandling.h"
 #include "llvm/Support/MathExtras.h"
 #include "llvm/Support/MemAlloc.h"
 #include "llvm/Support/type_traits.h"
 #include <algorithm>
 #include <cassert>
public:
   }
 
   template <typename RangeTy>
   explicit SmallVector(const iterator_range<RangeTy> &R)
       : SmallVectorImpl<T>(N) {
     this->append(R.begin(), R.end());
   }
 
+  template <typename RangeTy>
+  explicit SmallVector(const value_range<RangeTy> &R) : SmallVectorImpl<T>(N) {
+    this->append(R.begin(), R.end());
+  }
+
   SmallVector(std::initializer_list<T> IL) : SmallVectorImpl<T>(N) {
     this->assign(IL);
   }
 
   SmallVector(const SmallVector &RHS) : SmallVectorImpl<T>(N) {
     if (!RHS.empty())
       SmallVectorImpl<T>::operator=(RHS);
   }

llvm/unittests/ADT/SequenceTest.cpp

 #include "gtest/gtest.h"
 
 #include <list>
 
 using namespace llvm;
 
 namespace {
 
-TEST(SequenceTest, Basic) {
-  int x = 0;
-  for (int i : seq(0, 10)) {
-    EXPECT_EQ(x, i);
-    x++;
-  }
-  EXPECT_EQ(10, x);
-
-  auto my_seq = seq(0, 4);
-  EXPECT_EQ(4, my_seq.end() - my_seq.begin());
-  for (int i : {0, 1, 2, 3})
-    EXPECT_EQ(i, (int)my_seq.begin()[i]);
-
-  EXPECT_TRUE(my_seq.begin() < my_seq.end());
-
-  auto adjusted_begin = my_seq.begin() + 2;
-  auto adjusted_end = my_seq.end() - 2;
-  EXPECT_TRUE(adjusted_begin == adjusted_end);
-  EXPECT_EQ(2, *adjusted_begin);
-  EXPECT_EQ(2, *adjusted_end);
+TEST(SequenceTest, Forward) {
+  int X = 0;
+  for (int I : seq(0, 10)) {
+    EXPECT_EQ(X, I);
+    ++X;
+  }
+  EXPECT_EQ(10, X);
+}
+
+TEST(SequenceTest, Backward) {
+  int X = 9;
+  for (int I : reverse(seq(0, 10))) {
+    EXPECT_EQ(X, I);
+    --X;
+  }
+  EXPECT_EQ(-1, X);
+}
+
+TEST(SequenceTest, Distance) {
+  const auto forward = seq(0, 10);
+  EXPECT_EQ(std::distance(forward.begin(), forward.end()), 10);
+  EXPECT_EQ(std::distance(forward.rbegin(), forward.rend()), 10);
+}
+
+TEST(SequenceTest, Dereferene) {
+  const auto forward = seq(0, 10).begin();
+  EXPECT_EQ(forward[0], 0);
+  EXPECT_EQ(forward[2], 2);
+  const auto backward = seq(0, 10).rbegin();
+  EXPECT_EQ(backward[0], 9);
+  EXPECT_EQ(backward[2], 7);
 }
 
 } // anonymous namespace

mlir/include/mlir/IR/BuiltinAttributes.td

AttrBuilderWithInferredContext<(ins "ShapedType":$type,
       assert(type.hasStaticShape() && "type must have static shape");
       return $_get(type.getContext(), type,
                    indices.cast<DenseIntElementsAttr>(), values);
     }]>,
   ];
   let extraClassDeclaration = [{
     template <typename T>
     using iterator =
-        llvm::mapped_iterator<llvm::detail::value_sequence_iterator<ptrdiff_t>,
+        llvm::mapped_iterator<decltype(llvm::seq<ptrdiff_t>(0, 0))::const_iterator,
                               std::function<T(ptrdiff_t)>>;
 
     /// Return the values of this attribute in the form of the given type 'T'.
     /// 'T'  may be any of Attribute, APInt, APFloat, c++ integer/float types,
     /// etc.
     template <typename T> llvm::iterator_range<iterator<T>> getValues() const;
 
     /// Return the value of the element at the given index. The 'index' is