[ADT] add initializer list specialization for is_contained

[beanz]

Summary

Adding an initializer list specialization for is_contained allows for compile-time evaluation when called with a constant or runtime evaluation for non-constant values.

This patch doesn't add any uses of this template, but that is coming in
a subsequent patch.

[pete]

llvm/include/llvm/ADT/EnumMatcher.h

10

Probably shouldn’t have DXIL in the comment. Otherwise LGTM

[arsenm]

llvm/include/llvm/ADT/EnumMatcher.h

1

Missing license header

llvm/unittests/ADT/EnumMatcherTests.cpp

28

EXPECT_TRUE

[kuhar]

A few thoughts:

1. Is the requirement for this to be constant folded by the optimizer?
2. This could be made constexpr if we wanted.
3. The function name suggests this handles enums only but it works with any copybale & comparable type. I think we should either restrict it to enum types or make the name more general.
4. Since this function is not constexpr now, how about we added an overload to is_contained accepting an initializer list as the second element, e.g.: is_constained(MyEnum::A, {MyEnum::A, MyEnum::B, MyEnum::C})?

[beanz]

In D122079#3396156, @kuhar wrote:

A few thoughts:

1. Is the requirement for this to be constant folded by the optimizer?

It isn't strictly a requirement. If the code is called with a non-constant value the optimizer will convert it to nice range checks.

2. This could be made constexpr if we wanted.

I had another place that I wanted to use this in clang where the input parameter isn't constant.

4. The function name suggests this handles enums only but it works with any copybale & comparable type. I think we should either restrict it to enum types or make the name more general.

That is totally reasonable. It's really a compile-time set matcher :).

5. Since this function is not constexpr now, how about we added an overload to is_contained accepting an initializer list as the second element, e.g.: is_constained(MyEnum::A, {MyEnum::A, MyEnum::B, MyEnum::C})?

I realize this is probably a bit overkill, but isInEnumSet<Numbers, One, Two, Three, Four, Five>(Val) will actually optimize down to roughly if( Val >= One && Val <= Five) (assuming sequential values), and that really only works reliably with the template parameter unrolling.

[MaskRay]

Does the template compile to efficient code? lld/ELF has a utility which seems pretty efficient https://reviews.llvm.org/D112385#3084969

[MaskRay]

This patch doesn't add any uses of this template, but that is coming in a subsequent patch.

Usage link is usually directly mentioned to justify an addition to ADT/ or Support/.

[beanz]

In D122079#3401411, @MaskRay wrote:

Does the template compile to efficient code? lld/ELF has a utility which seems pretty efficient https://reviews.llvm.org/D112385#3084969

With a constant value it will fold to true/false, with non-constant values it optimizes to minimal range checks.

In D122079#3401413, @MaskRay wrote:

Usage link is usually directly mentioned to justify an addition to ADT/ or Support/.

This is part of a commit stack. The next commit in the stack which uses it is https://reviews.llvm.org/D122081. :)

[kuhar]

In D122079#3401001, @beanz wrote:

In D122079#3396156, @kuhar wrote:

2. This could be made constexpr if we wanted.

I had another place that I wanted to use this in clang where the input parameter isn't constant.

constexpr works with both constant-evaluated contexts and runtime calls.

5. Since this function is not constexpr now, how about we added an overload to is_contained accepting an initializer list as the second element, e.g.: is_constained(MyEnum::A, {MyEnum::A, MyEnum::B, MyEnum::C})?

I realize this is probably a bit overkill, but isInEnumSet<Numbers, One, Two, Three, Four, Five>(Val) will actually optimize down to roughly if( Val >= One && Val <= Five) (assuming sequential values), and that really only works reliably with the template parameter unrolling.

I've checked and it seems to work just as well when passing in an array. With initializer_list, there are still some branches left. See https://godbolt.org/z/o7hKnKen5.

Overall, I'd lean towards the array or initializer_list version (either re-using is_contained or introducing a new name like is_in) to keep things more familiar and avoid recursion.

[beanz]

In D122079#3401426, @kuhar wrote:

constexpr works with both constant-evaluated contexts and runtime calls.

Fair point.

I've checked and it seems to work just as well when passing in an array. With initializer_list, there are still some branches left. See https://godbolt.org/z/o7hKnKen5.

Ah! I had tried using this with the existing is_contained definition, and it wasn’t folding. I think it was the std::find call, I can adjust.

Overall, I'd lean towards the array or initializer_list version (either re-using is_contained or introducing a new name like is_in to keep things more familiar and avoid recursion.

Makes sense to me. Will rework tomorrow.

Thank you!

[beanz]

Updating to be a specialization on is_contained rather than a standalone thing.

[kuhar]

Could you also add some tests that make sure this can be constant-evaluated? (e.g., with static_assert)

Also, would be good to have a couple of tests with non-enum types (e.g., some trivial type like int and some class with a copy constructor etc.)

llvm/unittests/ADT/STLExtrasTest.cpp

976 ↗

(On Diff #418714)

Can you add an extra test case with an empty set of things to match against?

979 ↗

(On Diff #418714)

These should be EXPECT_TRUE.

ASSERT_TRUE are for when you can't continue executing a test after a failure

979 ↗

(On Diff #418714)

Also, put the call directly inside the check: EXPECT_TRUE(is_contained(...)).

[kuhar]

llvm/include/llvm/ADT/STLExtras.h

1661 ↗

(On Diff #418714)

This function arguments are backwards compared to the other overloads. Could we keep it consistent?

[beanz]

Updating based on feedback from @kuhar. Thank you!

[kuhar]

LGTM, thanks for the fixes.

[kuhar]

llvm/unittests/ADT/STLExtrasTest.cpp

985–989 ↗

(On Diff #418919)

nit: make sure to run this through clang-format if you haven't already. It looks to me like some spaces might be missing.

[kuhar]

llvm/include/llvm/ADT/STLExtras.h

1661 ↗

(On Diff #418919)

nit: variable names should be capitalized in this function

llvm/include/llvm/ADT/EnumMatcher.h

+#ifndef LLVM_ADT_ENUMMATCHER_H
+#define LLVM_ADT_ENUMMATCHER_H
+
+#include "llvm/Support/Compiler.h"
+
+namespace llvm {
+
+namespace detail {
+// This magic blob of code here looks awful, but it is actually pretty clever.
+// If you call isValidForDXIL with a constant value, this should generate an
+// insane AST that will all constant fold down to true or false.
+// If you call it with a non-constant value, it should turn into a nasty switch,
+// which is as good as you're going to do anyways...
+template <typename T>
+LLVM_ATTRIBUTE_ALWAYS_INLINE bool unrollCompare(T Left, T Right) {
+  return Left == Right;
+}
+
+template <typename T, typename... V>
+LLVM_ATTRIBUTE_ALWAYS_INLINE bool unrollCompare(T Left, T Right, V... Vals) {
+  if (Left == Right)
+    return true;
+  return unrollCompare(Left, Vals...);
+}
+} // namespace detail
+
+// TODO: When we update to C++17 we can use auto here to avoid needing to
+// specify the type of the enum.
+template <typename T, T Val, T... Vals>
+LLVM_ATTRIBUTE_ALWAYS_INLINE bool isInEnumSet(T InVal) {
+  return detail::unrollCompare(InVal, Val, Vals...);
+}
+
+} // namespace llvm
+
+#endif // LLVM_ADT_ENUMMATCHER_H

llvm/unittests/ADT/CMakeLists.txt

add_llvm_unittest(ADTTests
   CombinationGeneratorTest.cpp
   DAGDeltaAlgorithmTest.cpp
   DeltaAlgorithmTest.cpp
   DenseMapTest.cpp
   DenseSetTest.cpp
   DepthFirstIteratorTest.cpp
   DirectedGraphTest.cpp
   EnumeratedArrayTest.cpp
+  EnumMatcherTests.cpp
   EquivalenceClassesTest.cpp
   FallibleIteratorTest.cpp
   FloatingPointMode.cpp
   FoldingSet.cpp
   FunctionExtrasTest.cpp
   FunctionRefTest.cpp
   HashingTest.cpp
   IListBaseTest.cpp

llvm/unittests/ADT/EnumMatcherTests.cpp

+//===- llvm/unittest/ADT/EnumMatcherTests.cpp -------------------*- 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
+//
+//===----------------------------------------------------------------------===//
+//
+//===----------------------------------------------------------------------===//
+
+#include "llvm/ADT/EnumMatcher.h"
+#include "gtest/gtest.h"
+
+using namespace llvm;
+
+enum Doggos {
+  Floofer,
+  Woofer,
+  SubWoofer,
+  Pupper,
+  Pupperino,
+  Longboi,
+};
+
+TEST(EnumMatcher, MatchCase) {
+  {
+    bool Val = isInEnumSet<Doggos, Woofer, SubWoofer>(Woofer);
+    ASSERT_TRUE(Val);
+  }
+  {
+    bool Val = isInEnumSet<Doggos, Woofer, SubWoofer>(SubWoofer);
+    ASSERT_TRUE(Val);
+  }
+  {
+    bool Val = isInEnumSet<Doggos, Woofer, SubWoofer>(Pupper);
+    ASSERT_FALSE(Val);
+  }
+}