[ADT] Add all_equal predicate

[kuhar]

Summary

llvm::all_equal checks if all values in the given range are equal, i.e., there are no two elements that are not equal.
Similar to llvm::all_of, it returns true when the range is empty.

llvm::all_equal is intended to supersede llvm::is_splat, which will be deprecated and removed in future patches.
See the discussion thread for more details:
https://discourse.llvm.org/t/adt-is-splat-and-empty-ranges/64692.

[dblaikie]

Great (:

[shchenz]

LGTM. Thanks for fixing.

[dtzWill]

Small question about usage of std::equal here, if you don't mind? Thanks!

llvm/include/llvm/ADT/STLExtras.h

1770

Hi! Just wondering, why does this use std::equal-- which compares ranges (here, range of [2nd to last] vs [1st to (last-1)])-- instead of something like llvm::all_of(Range,[&](auto x)(return x == *Begin;)?

Does this have advantages? Seems slightly more expensive this way, is why I'm asking, but I haven't bounced through the generated code or such.

[kuhar]

llvm/include/llvm/ADT/STLExtras.h

1770

This is how is_splat used to be implemented. is_splat was in fact introduced in https://reviews.llvm.org/D49958 to fix previous misuses of std::equal that called it incorrectly.

I haven't looked at the generated code to see which implementation would be better either. Based on the existing uses in the code base, I don't think we ever use all_equal with a large enough number of elements for it to matter. But I'd be happy to know too, if you want to dig deeper.

FWIW, the implementation based on all_of performs one more comparison.

llvm/include/llvm/ADT/STLExtras.h

 
 /// Wrapper function around std::equal to detect if pair-wise elements between
 /// two ranges are the same.
 template <typename L, typename R> bool equal(L &&LRange, R &&RRange) {
   return std::equal(adl_begin(LRange), adl_end(LRange), adl_begin(RRange),
                     adl_end(RRange));
 }
 
-/// Wrapper function around std::equal to detect if all elements
-/// in a container are same.
-template <typename R>
-bool is_splat(R &&Range) {
-  size_t range_size = size(Range);
-  return range_size != 0 && (range_size == 1 ||
-         std::equal(adl_begin(Range) + 1, adl_end(Range), adl_begin(Range)));
+/// Returns true if all elements in Range are equal or when the Range is empty.
+template <typename R> bool all_equal(R &&Range) {
+  auto Begin = adl_begin(Range);
+  auto End = adl_end(Range);
+  return Begin == End || std::equal(Begin + 1, End, Begin);
+}
+
+/// Returns true if all Values in the initializer lists are equal or the list
+// is empty.
+template <typename T> bool all_equal(std::initializer_list<T> Values) {
+  return all_equal<std::initializer_list<T>>(std::move(Values));
+}
+
+/// Returns true if Range consists of the same value repeated multiple times.
+template <typename R> bool is_splat(R &&Range) {
+  return !llvm::empty(Range) && all_equal(Range);
 }
 
-/// Returns true iff all Values in the initializer lists are same.
+/// Returns true if Values consists of the same value repeated multiple times.
 template <typename T> bool is_splat(std::initializer_list<T> Values) {
   return is_splat<std::initializer_list<T>>(std::move(Values));
 }
 
 /// Provide a container algorithm similar to C++ Library Fundamentals v2's
 /// `erase_if` which is equivalent to:
 ///
 ///   C.erase(remove_if(C, pred), C.end());

llvm/unittests/ADT/STLExtrasTest.cpp

#endif
   // Erasing the front including the current doesn't break incrementing.
   L.erase(L.begin(), std::prev(L.end()));
   ++I;
   EXPECT_EQ(&*L.begin(), *I);
   ++I;
   EXPECT_EQ(EIR.end(), I);
 }
 
+TEST(STLExtrasTest, AllEqual) {
+  std::vector<int> V;
+  EXPECT_TRUE(all_equal(V));
+
+  V.push_back(1);
+  EXPECT_TRUE(all_equal(V));
+
+  V.push_back(1);
+  V.push_back(1);
+  EXPECT_TRUE(all_equal(V));
+
+  V.push_back(2);
+  EXPECT_FALSE(all_equal(V));
+}
+
+TEST(STLExtrasTest, AllEqualInitializerList) {
+  EXPECT_TRUE(all_equal({1}));
+  EXPECT_TRUE(all_equal({1, 1}));
+  EXPECT_FALSE(all_equal({1, 2}));
+  EXPECT_FALSE(all_equal({2, 1}));
+  EXPECT_TRUE(all_equal({1, 1, 1}));
+}
+
 TEST(STLExtrasTest, IsSplat) {
   std::vector<int> V;
   EXPECT_FALSE(is_splat(V));
 
   V.push_back(1);
   EXPECT_TRUE(is_splat(V));
 
   V.push_back(1);