diff --git a/llvm/include/llvm/ADT/Sequence.h b/llvm/include/llvm/ADT/Sequence.h --- a/llvm/include/llvm/ADT/Sequence.h +++ b/llvm/include/llvm/ADT/Sequence.h @@ -15,13 +15,18 @@ #ifndef LLVM_ADT_SEQUENCE_H #define LLVM_ADT_SEQUENCE_H -#include //std::ptrdiff_t -#include //std::random_access_iterator_tag +#include // assert +#include // std::ptrdiff_t +#include // std::random_access_iterator_tag +#include // std::underlying_type, std::is_enum namespace llvm { namespace detail { +// Providing std::type_identity for C++14. +template struct type_identity { using type = T; }; + template struct iota_range_iterator { using iterator_category = std::random_access_iterator_tag; using value_type = T; @@ -30,20 +35,27 @@ using reference = T &; private: + using U = typename std::conditional_t< + std::is_enum::value, std::underlying_type, type_identity>::type; + struct Forward { - static void increment(T &V) { ++V; } - static void decrement(T &V) { --V; } - static void offset(T &V, difference_type Offset) { V += Offset; } - static T add(const T &V, difference_type Offset) { return V + Offset; } - static difference_type difference(const T &A, const T &B) { return A - B; } + static void increment(U &V) { ++V; } + static void decrement(U &V) { --V; } + static void offset(U &V, difference_type Offset) { V += Offset; } + static U add(const U &V, difference_type Offset) { return V + Offset; } + static difference_type difference(const U &A, const U &B) { + return difference_type(A) - difference_type(B); + } }; struct Reverse { - static void increment(T &V) { --V; } - static void decrement(T &V) { ++V; } - static void offset(T &V, difference_type Offset) { V -= Offset; } - static T add(const T &V, difference_type Offset) { return V - Offset; } - static difference_type difference(const T &A, const T &B) { return B - A; } + static void increment(U &V) { --V; } + static void decrement(U &V) { ++V; } + static void offset(U &V, difference_type Offset) { V -= Offset; } + static U add(const U &V, difference_type Offset) { return V - Offset; } + static difference_type difference(const U &A, const U &B) { + return difference_type(B) - difference_type(A); + } }; using Op = std::conditional_t; @@ -54,7 +66,7 @@ // copy-constructible iota_range_iterator(const iota_range_iterator &) = default; // value constructor - explicit iota_range_iterator(T Value) : Value(Value) {} + explicit iota_range_iterator(T Value) : Value(static_cast(Value)) {} // copy-assignable iota_range_iterator &operator=(const iota_range_iterator &) = default; // destructible @@ -83,8 +95,10 @@ } // Dereference - T operator*() const { return Value; } - T operator[](difference_type Offset) const { return Op::add(Value, Offset); } + T operator*() const { return static_cast(Value); } + T operator[](difference_type Offset) const { + return static_cast(Op::add(Value, Offset)); + } // Arithmetic iota_range_iterator operator+(difference_type Offset) const { @@ -132,18 +146,15 @@ } private: - T Value; + U Value; }; } // namespace detail -template struct iota_range { - static_assert(std::is_integral::value, - "ValueT must be an integral type"); - - using value_type = ValueT; - using reference = ValueT &; - using const_reference = const ValueT &; +template struct iota_range { + using value_type = T; + using reference = T &; + using const_reference = const T &; using iterator = detail::iota_range_iterator; using const_iterator = iterator; using reverse_iterator = detail::iota_range_iterator; @@ -151,27 +162,57 @@ using difference_type = std::ptrdiff_t; using size_type = std::size_t; - value_type Begin; - value_type End; - - explicit iota_range(ValueT Begin, ValueT End) : Begin(Begin), End(End) {} + value_type BeginValue; + value_type PastEndValue; + + explicit iota_range(T Begin, T End, bool Inclusive) + : BeginValue(Begin), PastEndValue(Inclusive ? NextValue(End) : End) { + // We only check relative order of input values here (i.e. `Begin`/`End`). + assert(Begin <= End); + // When `Inclusive && End == std::numeric_limits::max()` + // NextValue(End) wraps around and PastEndValue is 0. This is not a problem + // for iteration as for-loop stopping condition relies on equality + // comparison and same wrap around mechanism occurs. + // + // That said in this particular case iterator difference and comparison is + // broken: + // auto sequence = seq_inclusive(255, 255); + // assert(sequence.begin() <= sequence.end()); // broken + } - size_t size() const { return End - Begin; } - bool empty() const { return Begin == End; } + size_t size() const { return PastEndValue - BeginValue; } + bool empty() const { return BeginValue == PastEndValue; } - auto begin() const { return const_iterator(Begin); } - auto end() const { return const_iterator(End); } + auto begin() const { return const_iterator(BeginValue); } + auto end() const { return const_iterator(PastEndValue); } - auto rbegin() const { return const_reverse_iterator(End - 1); } - auto rend() const { return const_reverse_iterator(Begin - 1); } + // Implementation note for rbegin/rend: + // `--begin()` is usually undefined behavior for normal iterators. + // Here it works because iota_range_iterator is generative, self-contained and + // does not refer to external memory. + auto rbegin() const { return const_reverse_iterator(*--end()); } + auto rend() const { return const_reverse_iterator(*--begin()); } private: - static_assert(std::is_same>::value, - "ValueT must not be const nor volatile"); + static_assert(std::is_integral::value || std::is_enum::value, + "T must be an integral or enum type"); + static_assert(std::is_same>::value, + "T must not be const nor volatile"); + + static T NextValue(T value) { return *++const_iterator(value); } }; -template auto seq(ValueT Begin, ValueT End) { - return iota_range(Begin, End); +/// Iterate over an integral/enum type from Begin up to - but not including - +/// End. +template auto seq(T Begin, T End) { + return iota_range(Begin, End, false); +} + +/// Iterate over an integral/enum type from Begin to End inclusive. +/// Beware that iterator difference and comparison are broken when +/// `End == std::numeric_limits::max()`. Iteration works fine though. +template auto seq_inclusive(T Begin, T End) { + return iota_range(Begin, End, true); } } // end namespace llvm diff --git a/llvm/include/llvm/Support/MachineValueType.h b/llvm/include/llvm/Support/MachineValueType.h --- a/llvm/include/llvm/Support/MachineValueType.h +++ b/llvm/include/llvm/Support/MachineValueType.h @@ -14,6 +14,7 @@ #ifndef LLVM_SUPPORT_MACHINEVALUETYPE_H #define LLVM_SUPPORT_MACHINEVALUETYPE_H +#include "llvm/ADT/Sequence.h" #include "llvm/ADT/iterator_range.h" #include "llvm/Support/ErrorHandling.h" #include "llvm/Support/MathExtras.h" @@ -1388,84 +1389,55 @@ /// returned as Other, otherwise they are invalid. static MVT getVT(Type *Ty, bool HandleUnknown = false); - private: - /// A simple iterator over the MVT::SimpleValueType enum. - struct mvt_iterator { - SimpleValueType VT; - - mvt_iterator(SimpleValueType VT) : VT(VT) {} - - MVT operator*() const { return VT; } - bool operator!=(const mvt_iterator &LHS) const { return VT != LHS.VT; } - - mvt_iterator& operator++() { - VT = (MVT::SimpleValueType)((int)VT + 1); - assert((int)VT <= MVT::MAX_ALLOWED_VALUETYPE && - "MVT iterator overflowed."); - return *this; - } - }; - - /// A range of the MVT::SimpleValueType enum. - using mvt_range = iterator_range; - public: /// SimpleValueType Iteration /// @{ - static mvt_range all_valuetypes() { - return mvt_range(MVT::FIRST_VALUETYPE, - (MVT::SimpleValueType)(MVT::LAST_VALUETYPE + 1)); + static auto all_valuetypes() { + return seq_inclusive(MVT::FIRST_VALUETYPE, MVT::LAST_VALUETYPE); } - static mvt_range integer_valuetypes() { - return mvt_range(MVT::FIRST_INTEGER_VALUETYPE, - (MVT::SimpleValueType)(MVT::LAST_INTEGER_VALUETYPE + 1)); + static auto integer_valuetypes() { + return seq_inclusive(MVT::FIRST_INTEGER_VALUETYPE, + MVT::LAST_INTEGER_VALUETYPE); } - static mvt_range fp_valuetypes() { - return mvt_range(MVT::FIRST_FP_VALUETYPE, - (MVT::SimpleValueType)(MVT::LAST_FP_VALUETYPE + 1)); + static auto fp_valuetypes() { + return seq_inclusive(MVT::FIRST_FP_VALUETYPE, MVT::LAST_FP_VALUETYPE); } - static mvt_range vector_valuetypes() { - return mvt_range(MVT::FIRST_VECTOR_VALUETYPE, - (MVT::SimpleValueType)(MVT::LAST_VECTOR_VALUETYPE + 1)); + static auto vector_valuetypes() { + return seq_inclusive(MVT::FIRST_VECTOR_VALUETYPE, + MVT::LAST_VECTOR_VALUETYPE); } - static mvt_range fixedlen_vector_valuetypes() { - return mvt_range( - MVT::FIRST_FIXEDLEN_VECTOR_VALUETYPE, - (MVT::SimpleValueType)(MVT::LAST_FIXEDLEN_VECTOR_VALUETYPE + 1)); + static auto fixedlen_vector_valuetypes() { + return seq_inclusive(MVT::FIRST_FIXEDLEN_VECTOR_VALUETYPE, + MVT::LAST_FIXEDLEN_VECTOR_VALUETYPE); } - static mvt_range scalable_vector_valuetypes() { - return mvt_range( - MVT::FIRST_SCALABLE_VECTOR_VALUETYPE, - (MVT::SimpleValueType)(MVT::LAST_SCALABLE_VECTOR_VALUETYPE + 1)); + static auto scalable_vector_valuetypes() { + return seq_inclusive(MVT::FIRST_SCALABLE_VECTOR_VALUETYPE, + MVT::LAST_SCALABLE_VECTOR_VALUETYPE); } - static mvt_range integer_fixedlen_vector_valuetypes() { - return mvt_range( - MVT::FIRST_INTEGER_FIXEDLEN_VECTOR_VALUETYPE, - (MVT::SimpleValueType)(MVT::LAST_INTEGER_FIXEDLEN_VECTOR_VALUETYPE + 1)); + static auto integer_fixedlen_vector_valuetypes() { + return seq_inclusive(MVT::FIRST_INTEGER_FIXEDLEN_VECTOR_VALUETYPE, + MVT::LAST_INTEGER_FIXEDLEN_VECTOR_VALUETYPE); } - static mvt_range fp_fixedlen_vector_valuetypes() { - return mvt_range( - MVT::FIRST_FP_FIXEDLEN_VECTOR_VALUETYPE, - (MVT::SimpleValueType)(MVT::LAST_FP_FIXEDLEN_VECTOR_VALUETYPE + 1)); + static auto fp_fixedlen_vector_valuetypes() { + return seq_inclusive(MVT::FIRST_FP_FIXEDLEN_VECTOR_VALUETYPE, + MVT::LAST_FP_FIXEDLEN_VECTOR_VALUETYPE); } - static mvt_range integer_scalable_vector_valuetypes() { - return mvt_range( - MVT::FIRST_INTEGER_SCALABLE_VECTOR_VALUETYPE, - (MVT::SimpleValueType)(MVT::LAST_INTEGER_SCALABLE_VECTOR_VALUETYPE + 1)); + static auto integer_scalable_vector_valuetypes() { + return seq_inclusive(MVT::FIRST_INTEGER_SCALABLE_VECTOR_VALUETYPE, + MVT::LAST_INTEGER_SCALABLE_VECTOR_VALUETYPE); } - static mvt_range fp_scalable_vector_valuetypes() { - return mvt_range( - MVT::FIRST_FP_SCALABLE_VECTOR_VALUETYPE, - (MVT::SimpleValueType)(MVT::LAST_FP_SCALABLE_VECTOR_VALUETYPE + 1)); + static auto fp_scalable_vector_valuetypes() { + return seq_inclusive(MVT::FIRST_FP_SCALABLE_VECTOR_VALUETYPE, + MVT::LAST_FP_SCALABLE_VECTOR_VALUETYPE); } /// @} }; diff --git a/llvm/lib/CodeGen/SelectionDAG/LegalizeVectorTypes.cpp b/llvm/lib/CodeGen/SelectionDAG/LegalizeVectorTypes.cpp --- a/llvm/lib/CodeGen/SelectionDAG/LegalizeVectorTypes.cpp +++ b/llvm/lib/CodeGen/SelectionDAG/LegalizeVectorTypes.cpp @@ -4629,8 +4629,7 @@ EVT InVT = InOp.getValueType(); if (InVT.getSizeInBits() != VT.getSizeInBits()) { EVT InEltVT = InVT.getVectorElementType(); - for (int i = MVT::FIRST_VECTOR_VALUETYPE, e = MVT::LAST_VECTOR_VALUETYPE; i < e; ++i) { - EVT FixedVT = (MVT::SimpleValueType)i; + for (EVT FixedVT : MVT::vector_valuetypes()) { EVT FixedEltVT = FixedVT.getVectorElementType(); if (TLI.isTypeLegal(FixedVT) && FixedVT.getSizeInBits() == VT.getSizeInBits() && @@ -5157,14 +5156,11 @@ if (!Scalable && Width == WidenEltWidth) return RetVT; - // See if there is larger legal integer than the element type to load/store. - unsigned VT; // Don't bother looking for an integer type if the vector is scalable, skip // to vector types. if (!Scalable) { - for (VT = (unsigned)MVT::LAST_INTEGER_VALUETYPE; - VT >= (unsigned)MVT::FIRST_INTEGER_VALUETYPE; --VT) { - EVT MemVT((MVT::SimpleValueType) VT); + // See if there is larger legal integer than the element type to load/store. + for (EVT MemVT : reverse(MVT::integer_valuetypes())) { unsigned MemVTWidth = MemVT.getSizeInBits(); if (MemVT.getSizeInBits() <= WidenEltWidth) break; @@ -5185,9 +5181,7 @@ // See if there is a larger vector type to load/store that has the same vector // element type and is evenly divisible with the WidenVT. - for (VT = (unsigned)MVT::LAST_VECTOR_VALUETYPE; - VT >= (unsigned)MVT::FIRST_VECTOR_VALUETYPE; --VT) { - EVT MemVT = (MVT::SimpleValueType) VT; + for (EVT MemVT : reverse(MVT::vector_valuetypes())) { // Skip vector MVTs which don't match the scalable property of WidenVT. if (Scalable != MemVT.isScalableVector()) continue; diff --git a/llvm/tools/llvm-exegesis/lib/X86/Target.cpp b/llvm/tools/llvm-exegesis/lib/X86/Target.cpp --- a/llvm/tools/llvm-exegesis/lib/X86/Target.cpp +++ b/llvm/tools/llvm-exegesis/lib/X86/Target.cpp @@ -918,9 +918,9 @@ continue; case X86::OperandType::OPERAND_COND_CODE: { Exploration = true; - auto CondCodes = seq((int)X86::CondCode::COND_O, - 1 + (int)X86::CondCode::LAST_VALID_COND); - Choices.reserve(std::distance(CondCodes.begin(), CondCodes.end())); + auto CondCodes = + seq_inclusive(X86::CondCode::COND_O, X86::CondCode::LAST_VALID_COND); + Choices.reserve(CondCodes.size()); for (int CondCode : CondCodes) Choices.emplace_back(MCOperand::createImm(CondCode)); break; diff --git a/llvm/unittests/ADT/SequenceTest.cpp b/llvm/unittests/ADT/SequenceTest.cpp --- a/llvm/unittests/ADT/SequenceTest.cpp +++ b/llvm/unittests/ADT/SequenceTest.cpp @@ -7,12 +7,15 @@ //===----------------------------------------------------------------------===// #include "llvm/ADT/Sequence.h" +#include "gmock/gmock.h" #include "gtest/gtest.h" #include using namespace llvm; +using testing::ElementsAre; + namespace { TEST(SequenceTest, Forward) { @@ -48,4 +51,69 @@ EXPECT_EQ(Backward[2], 7); } +enum class CharEnum : char { A = 1, B, C, D, E, LAST = E }; + +TEST(SequenceTest, ForwardIteration) { + EXPECT_THAT(seq_inclusive(CharEnum::C, CharEnum::LAST), + ElementsAre(CharEnum::C, CharEnum::D, CharEnum::E)); +} + +TEST(SequenceTest, BackwardIteration) { + EXPECT_THAT(reverse(seq_inclusive(CharEnum::B, CharEnum::D)), + ElementsAre(CharEnum::D, CharEnum::C, CharEnum::B)); +} + +template class SequenceTest : public testing::Test { + const T min = std::numeric_limits::min(); + const T after_min = min + 1; + const T max = std::numeric_limits::max(); + const T before_max = max - 1; + +protected: + void CheckIteration() const { + // Forward + EXPECT_THAT(seq(min, min), ElementsAre()); + EXPECT_THAT(seq(min, after_min), ElementsAre(min)); + EXPECT_THAT(seq(before_max, max), ElementsAre(before_max)); + EXPECT_THAT(seq(max, max), ElementsAre()); + // Reverse + EXPECT_THAT(reverse(seq(min, min)), ElementsAre()); + EXPECT_THAT(reverse(seq(min, after_min)), ElementsAre(min)); + EXPECT_THAT(reverse(seq(before_max, max)), ElementsAre(before_max)); + EXPECT_THAT(reverse(seq(max, max)), ElementsAre()); + // Inclusive + EXPECT_THAT(seq_inclusive(min, min), ElementsAre(min)); + EXPECT_THAT(seq_inclusive(min, after_min), ElementsAre(min, after_min)); + EXPECT_THAT(seq_inclusive(before_max, max), ElementsAre(before_max, max)); + EXPECT_THAT(seq_inclusive(max, max), ElementsAre(max)); + // Inclusive Reverse + EXPECT_THAT(reverse(seq_inclusive(min, min)), ElementsAre(min)); + EXPECT_THAT(reverse(seq_inclusive(min, after_min)), + ElementsAre(after_min, min)); + EXPECT_THAT(reverse(seq_inclusive(before_max, max)), + ElementsAre(max, before_max)); + EXPECT_THAT(reverse(seq_inclusive(max, max)), ElementsAre(max)); + } + + void CheckIteratorEquality() const { + auto check = [](auto sequence) { + EXPECT_LE(sequence.begin(), sequence.end()); + }; + check(seq(min, min)); + check(seq(max, max)); + check(seq_inclusive(min, min)); + // seq_inclusive(max, max) currently breaks iterator ordering invariant. + } +}; + +using IntegralTypes = testing::Types; + +TYPED_TEST_SUITE(SequenceTest, IntegralTypes); + +TYPED_TEST(SequenceTest, Boundaries) { + this->CheckIteration(); + this->CheckIteratorEquality(); +} + } // anonymous namespace diff --git a/llvm/unittests/CodeGen/ScalableVectorMVTsTest.cpp b/llvm/unittests/CodeGen/ScalableVectorMVTsTest.cpp --- a/llvm/unittests/CodeGen/ScalableVectorMVTsTest.cpp +++ b/llvm/unittests/CodeGen/ScalableVectorMVTsTest.cpp @@ -18,7 +18,7 @@ namespace { TEST(ScalableVectorMVTsTest, IntegerMVTs) { - for (auto VecTy : MVT::integer_scalable_vector_valuetypes()) { + for (MVT VecTy : MVT::integer_scalable_vector_valuetypes()) { ASSERT_TRUE(VecTy.isValid()); ASSERT_TRUE(VecTy.isInteger()); ASSERT_TRUE(VecTy.isVector()); @@ -30,7 +30,7 @@ } TEST(ScalableVectorMVTsTest, FloatMVTs) { - for (auto VecTy : MVT::fp_scalable_vector_valuetypes()) { + for (MVT VecTy : MVT::fp_scalable_vector_valuetypes()) { ASSERT_TRUE(VecTy.isValid()); ASSERT_TRUE(VecTy.isFloatingPoint()); ASSERT_TRUE(VecTy.isVector()); diff --git a/llvm/unittests/IR/ConstantRangeTest.cpp b/llvm/unittests/IR/ConstantRangeTest.cpp --- a/llvm/unittests/IR/ConstantRangeTest.cpp +++ b/llvm/unittests/IR/ConstantRangeTest.cpp @@ -1551,9 +1551,9 @@ } TEST(ConstantRange, ICmp) { - for (auto Pred : seq(CmpInst::Predicate::FIRST_ICMP_PREDICATE, - 1 + CmpInst::Predicate::LAST_ICMP_PREDICATE)) - ICmpTestImpl((CmpInst::Predicate)Pred); + for (auto Pred : seq_inclusive(CmpInst::Predicate::FIRST_ICMP_PREDICATE, + CmpInst::Predicate::LAST_ICMP_PREDICATE)) + ICmpTestImpl(Pred); } TEST(ConstantRange, MakeGuaranteedNoWrapRegion) { diff --git a/mlir/lib/Dialect/Linalg/IR/LinalgOps.cpp b/mlir/lib/Dialect/Linalg/IR/LinalgOps.cpp --- a/mlir/lib/Dialect/Linalg/IR/LinalgOps.cpp +++ b/mlir/lib/Dialect/Linalg/IR/LinalgOps.cpp @@ -1695,7 +1695,7 @@ unsigned endPos = map.getResults().back().cast().getPosition(); AffineExpr expr; SmallVector dynamicDims; - for (auto dim : llvm::seq(startPos, endPos + 1)) { + for (auto dim : llvm::seq_inclusive(startPos, endPos)) { dynamicDims.push_back(builder.createOrFold(loc, src, dim)); AffineExpr currExpr = builder.getAffineSymbolExpr(dim - startPos); expr = (expr ? expr * currExpr : currExpr); @@ -1728,7 +1728,7 @@ map.value().getResults().front().cast().getPosition(); unsigned endPos = map.value().getResults().back().cast().getPosition(); - for (auto dim : llvm::seq(startPos, endPos + 1)) { + for (auto dim : llvm::seq_inclusive(startPos, endPos)) { expandedDimToCollapsedDim[dim] = map.index(); } }