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 @@ -6,9 +6,66 @@ // //===----------------------------------------------------------------------===// /// \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. +/// 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. +/// +/// The `seq(A, B)` function produces a sequence of values from `A` to up to +/// (but not including) `B`, i.e., [`A`, `B`), that can be safely iterated over. +/// `seq` supports both integral (e.g., `int`, `char`, `uint32_t`) and enum +/// types. `seq_inclusive(A, B)` produces a sequence of values from `A` to `B`, +/// including `B`. +/// +/// Examples with integral types: +/// for (auto x : seq(0, 3)) +/// outs() << x << " "; +/// ``` +/// +/// Prints: `0 1 2`. +/// +/// ``` +/// for (auto x : seq_inclusive(0, 3)) +/// outs() << x << " "; +/// ``` +/// +/// Prints: `0 1 2 3`. +/// +/// To enable iteration with enum types, you need to either mark enums as safe +/// to iterate over using `DECLARE_ITERABLE_ENUM(MyEnum)`, or opt into +/// potentially unsafe iteration at every callsite with `forge_iterable_enum`. +/// These utilities work with both enums delcared in namespaces and inside +/// structs/classes. +/// +/// Examples with enum types: +/// ``` +/// namespace X { +/// enum class MyEnum : unsigned {A = 0, B, C}; +/// DECLARE_ITERABLE_ENUM(MyEnum) +/// } // namespace X +/// +/// class MyClass { +/// public: +/// enum Safe { D = 3, E, F }; +/// friend DECLARE_ITERABLE_ENUM(Safe); +/// +/// enum MaybeUnsafe { G = 1, H = 2, I = 4 }; +/// }; +/// ``` +/// +/// ``` +/// for (auto v : seq(MyClass::Safe::D, MyClass::Safe::F)) +/// outs() << int(v) << " "; +/// ``` +/// +/// Prints: `3 4`. +/// +/// ``` +/// for (auto v : seq(forge_iterable_enum(MyClass::MaybeUnsafe::H), +/// forge_iterable_enum(MyClass::MaybeUnsafe::I))) +/// outs() << int(v) << " "; +/// ``` +/// +/// Prints: `2 3`. /// //===----------------------------------------------------------------------===// @@ -18,12 +75,61 @@ #include // assert #include // std::random_access_iterator_tag #include // std::numeric_limits -#include // std::underlying_type, std::is_enum +#include // std::underlying_type, std::is_enum, std::false_type +#include "llvm/Support/Compiler.h" // LLVM_ATTRIBUTE_UNUSED #include "llvm/Support/MathExtras.h" // AddOverflow / SubOverflow namespace llvm { +// Enum traits that marks enums as safe to iterate over. Custom enum traits +// used with the utilities in this file (`seq`, `iota_range`) must provide +// `is_iterable`. +template struct iterable_enum_traits { + static constexpr bool is_iterable = true; +}; + +// Wrapper type to represent an enum value and its traits. +// We use this so that we can use ADL to get enum traits. Using traditional +// C++ traits specialized for user types is an alternative that we decided not +// to use, as this would require defining these traits in the same namespace +// and would complicate dealing with enums defined within classes. +template struct enum_with_traits { + Enum value; + static_assert(std::is_enum::value, "Not an enum type"); + using enum_type = Enum; + using underlying_type = std::underlying_type_t; + using traits_type = Traits; +}; + +namespace detail { +// We cannot use std::false directly because it would make a static_assert in a +// function template trigger even when not instanciated. This templated version +// only evaluates to false when actually instantiated in a function. +// FIXME: Move this to STLExtras.h and replace similar utilities in the +// codebase with it. +template struct always_false : std::false_type {}; +} // namespace detail + +// Generate a compilation error when add_enum_traits are not defined for this +// enum type. +template auto add_enum_traits(Enum value) = delete; + +// Wraps this enum value with traits. By default, we use `iterable_enum_traits`, +// so that it is marked as safe to iterate over. +template > +enum_with_traits forge_iterable_enum(Enum value) { + return {value}; +} + +// Use to declare ENUM as safe to iterate over. This can be used for enums +// declared in namespace scope and inside class/struct (as a friend function). +// We mark it as potentially unused to silence false positives. +#define DECLARE_ITERABLE_ENUM(ENUM) \ + inline auto LLVM_ATTRIBUTE_UNUSED add_enum_traits(ENUM value) { \ + return llvm::forge_iterable_enum(value); \ + } + namespace detail { // Returns whether a value of type U can be represented with type T. @@ -174,9 +280,7 @@ template friend struct SafeIntIterator; }; -} // namespace detail - -template struct iota_range { +template struct iota_range_impl { using value_type = T; using reference = T &; using const_reference = const T &; @@ -187,7 +291,7 @@ using difference_type = intmax_t; using size_type = std::size_t; - explicit iota_range(T Begin, T End, bool Inclusive) + explicit iota_range_impl(T Begin, T End, bool Inclusive) : BeginValue(Begin), PastEndValue(End) { assert(Begin <= End && "Begin must be less or equal to End."); if (Inclusive) @@ -213,27 +317,74 @@ iterator PastEndValue; }; +} // namespace detail + +template struct iota_range; + +// iota_range specialization for integral types. +template +struct iota_range::value>> + : detail::iota_range_impl { + using detail::iota_range_impl::iota_range_impl; +}; + +// iota_range specialization for enum types. The constructor checks +// the traits to make sure it is safe to iterate over this enum type. +template +struct iota_range::value>> + : detail::iota_range_impl { + explicit iota_range(Enum Begin, Enum End, bool Inclusive) + : detail::iota_range_impl(Begin, End, Inclusive) { + // Make sure that this enum is safe to iterate over. + using enum_traits = typename decltype(add_enum_traits(Begin))::traits_type; + static_assert( + enum_traits::is_iterable, + "Enum not iterable. Use DECLARE_ITERABLE_ENUM or override this " + "safety check with forge_iterable_enum."); + } +}; + +// iota_range specialization for enum_with_traits types. The constructor checks +// the traits to make sure it is safe to iterate over this enum type. +// This specialization serves as an escape hatch to iterate over enum types not +// marked with DECLARE_ITERABLE_ENUM, for example, by using forge_iterable_enum. +template +struct iota_range, + std::enable_if_t::value>> + : detail::iota_range_impl { + explicit iota_range(enum_with_traits Begin, + enum_with_traits End, bool Inclusive) + : detail::iota_range_impl(Begin.value, End.value, Inclusive) { + static_assert( + Traits::is_iterable, + "Enum not iterable. Use DECLARE_ITERABLE_ENUM or override this " + "safety check with forge_iterable_enum."); + }; +}; + /// Iterate over an integral/enum type from Begin up to - but not including - /// End. -/// Note on enum iteration: `seq` will generate each consecutive value, even if -/// no enumerator with that value exists. /// Note: Begin and End values have to be within [INTMAX_MIN, INTMAX_MAX] for /// forward iteration (resp. [INTMAX_MIN + 1, INTMAX_MAX] for reverse /// iteration). +/// Note on enum iteration: by default, `seq` treats enum types as non-iterable. +/// To mark an enum as safe for iteration, use `DECLARE_ITERABLE_ENUM`, or +/// implement `add_enum_traits`, or wrap enum values with `forge_iterable_enum`. template auto seq(T Begin, T End) { return iota_range(Begin, End, false); } /// Iterate over an integral/enum type from Begin to End inclusive. -/// Note on enum iteration: `seq_inclusive` will generate each consecutive -/// value, even if no enumerator with that value exists. /// Note: Begin and End values have to be within [INTMAX_MIN, INTMAX_MAX - 1] /// for forward iteration (resp. [INTMAX_MIN + 1, INTMAX_MAX - 1] for reverse /// iteration). +/// Note on enum iteration: by default, `seq_inclusive` treats enum types as +/// non-iterable. To mark an enum as safe for iteration, use +/// `DECLARE_ITERABLE_ENUM`, or implement `add_enum_traits`, or wrap enum values +/// with `forge_iterable_enum`. template auto seq_inclusive(T Begin, T End) { return iota_range(Begin, End, true); } - } // end namespace llvm #endif // LLVM_ADT_SEQUENCE_H diff --git a/llvm/include/llvm/IR/InstrTypes.h b/llvm/include/llvm/IR/InstrTypes.h --- a/llvm/include/llvm/IR/InstrTypes.h +++ b/llvm/include/llvm/IR/InstrTypes.h @@ -19,6 +19,7 @@ #include "llvm/ADT/None.h" #include "llvm/ADT/Optional.h" #include "llvm/ADT/STLExtras.h" +#include "llvm/ADT/Sequence.h" #include "llvm/ADT/StringMap.h" #include "llvm/ADT/StringRef.h" #include "llvm/ADT/Twine.h" @@ -2368,6 +2369,8 @@ DEFINE_TRANSPARENT_OPERAND_ACCESSORS(FuncletPadInst, Value) +DECLARE_ITERABLE_ENUM(CmpInst::Predicate) + } // end namespace llvm #endif // LLVM_IR_INSTRTYPES_H 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 @@ -1402,6 +1402,8 @@ static MVT getVT(Type *Ty, bool HandleUnknown = false); public: + friend DECLARE_ITERABLE_ENUM(MVT::SimpleValueType); + /// SimpleValueType Iteration /// @{ static auto all_valuetypes() { 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 @@ -919,7 +919,8 @@ case X86::OperandType::OPERAND_COND_CODE: { Exploration = true; auto CondCodes = - seq_inclusive(X86::CondCode::COND_O, X86::CondCode::LAST_VALID_COND); + seq_inclusive(forge_iterable_enum(X86::CondCode::COND_O), + forge_iterable_enum(X86::CondCode::LAST_VALID_COND)); Choices.reserve(CondCodes.size()); for (int CondCode : CondCodes) Choices.emplace_back(MCOperand::createImm(CondCode)); 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 @@ -16,6 +16,7 @@ using namespace llvm; using testing::ElementsAre; +using testing::IsEmpty; namespace { @@ -68,17 +69,6 @@ EXPECT_EQ(Actual - (Actual + 2), -2); } -TEST(StrongIntTest, Enums) { - enum UntypedEnum { A = 3 }; - EXPECT_EQ(CheckedInt::from(A).to(), A); - - enum TypedEnum : uint32_t { B = 3 }; - EXPECT_EQ(CheckedInt::from(B).to(), B); - - enum class ScopedEnum : uint16_t { C = 3 }; - EXPECT_EQ(CheckedInt::from(ScopedEnum::C).to(), ScopedEnum::C); -} - #if defined(GTEST_HAS_DEATH_TEST) && !defined(NDEBUG) TEST(StrongIntDeathTest, OutOfBounds) { // Values above 'INTMAX_MAX' are not representable. @@ -215,4 +205,72 @@ EXPECT_EQ(Backward[2], 7); } -} // anonymous namespace +enum UntypedEnum { A = 3 }; +enum TypedEnum : uint32_t { B = 3 }; + +DECLARE_ITERABLE_ENUM(UntypedEnum) +DECLARE_ITERABLE_ENUM(TypedEnum) + +namespace X { +enum class ScopedEnum : uint16_t { C = 3 }; +DECLARE_ITERABLE_ENUM(X::ScopedEnum) +} // namespace X + +TEST(StrongIntTest, Enums) { + EXPECT_EQ(CheckedInt::from(A).to(), A); + EXPECT_EQ(CheckedInt::from(B).to(), B); + EXPECT_EQ(CheckedInt::from(X::ScopedEnum::C).to(), + X::ScopedEnum::C); +} + +struct S { + enum NestedEnum { D = 4 }; + enum NestedEnum2 { E = 5 }; + + friend DECLARE_ITERABLE_ENUM(NestedEnum); +}; + +TEST(SequenceTest, IterableEnums) { + EXPECT_THAT( + llvm::iota_range(UntypedEnum::A, UntypedEnum::A, false), + IsEmpty()); + EXPECT_THAT( + llvm::iota_range(UntypedEnum::A, UntypedEnum::A, true), + ElementsAre(UntypedEnum::A)); + + EXPECT_THAT(llvm::iota_range(TypedEnum::B, TypedEnum::B, false), + IsEmpty()); + EXPECT_THAT(llvm::iota_range(TypedEnum::B, TypedEnum::B, true), + ElementsAre(TypedEnum::B)); + + EXPECT_THAT(llvm::iota_range(X::ScopedEnum::C, + X::ScopedEnum::C, false), + IsEmpty()); + EXPECT_THAT( + llvm::iota_range(X::ScopedEnum::C, X::ScopedEnum::C, true), + ElementsAre(X::ScopedEnum::C)); + + EXPECT_THAT(seq_inclusive(X::ScopedEnum::C, X::ScopedEnum::C), + ElementsAre(X::ScopedEnum::C)); + EXPECT_THAT(seq_inclusive(S::NestedEnum::D, S::NestedEnum::D), + ElementsAre(S::NestedEnum::D)); +} + +TEST(SequenceTest, ForgeIterableEnums) { + EXPECT_THAT(seq(forge_iterable_enum(S::NestedEnum2::E), + forge_iterable_enum(S::NestedEnum2::E)), + IsEmpty()); + EXPECT_THAT(seq_inclusive(forge_iterable_enum(S::NestedEnum2::E), + forge_iterable_enum(S::NestedEnum2::E)), + ElementsAre(S::NestedEnum2::E)); + + auto ValueWithTraits = forge_iterable_enum(S::NestedEnum2::E); + EXPECT_THAT(llvm::iota_range( + ValueWithTraits, ValueWithTraits, false), + IsEmpty()); + EXPECT_THAT(llvm::iota_range( + ValueWithTraits, ValueWithTraits, true), + ElementsAre(S::NestedEnum2::E)); +} + +} // namespace