[MISC]Fix wrong usage of std::equal()

[shchenz]

Summary

This is a small patch to fix std::equal() wrong usage.

Firstly find this issue in function visitSelect() of file SelectionDAGBuilder.cpp:

// Min/max matching is only viable if all output VTs are the same.
if (std::equal(ValueVTs.begin(), ValueVTs.end(), ValueVTs.begin())) {

This is obviously wrong. "std::equal(ValueVTs.begin(), ValueVTs.end(), ValueVTs.begin())" is always true.

Then I go through all llvm codes, find another two wrong places.

Since this is a very obviously mistake and related to c++ language not to compiler area, I do not add some cases for this. Hope it is ok.

[lebedev.ri]

llvm/lib/CodeGen/SelectionDAG/SelectionDAGBuilder.cpp

2918–2920 ↗

(On Diff #157854)

I don't understand what this code is doing at all.
All three arguments point to the same array.
This is (1) in https://en.cppreference.com/w/cpp/algorithm/equal:

1,3) Returns true if the range [first1, last1) is equal to the range [first2, first2 + (last1 - first1)), and false otherwise

So it will equality-compare the ValueVTs[i] with ValueVTs[i] for all i?
But that is always true (well, except weird floats, etc)
Or am i completely misreading this?

Assuming the comment is the correct one, shouldn't this be

if (llvm::all_of(ValueVTs, [FirstVT = ValueVTs.front()](EVT VT) -> bool {
      return VT == FirstVT;
    })) {

?

[craig.topper]

llvm/lib/CodeGen/SelectionDAG/SelectionDAGBuilder.cpp

2918–2920 ↗

(On Diff #157854)

The original code does just compare each element to itself and is always true.

The code in the patch compares each element to the one before it. This will only be true if they are all the same. And is an valid idiom for this. It’s one of the comments here https://stackoverflow.com/questions/20287095/checking-if-all-elements-of-a-vector-are-equal-in-c

The lambda you wrote would also work.

[lebedev.ri]

But yes, i think the LHS of the diff looks at least strange..

llvm/lib/CodeGen/SelectionDAG/SelectionDAGBuilder.cpp

2919 ↗

(On Diff #157854)

This seems to originate from @jmolloy from rL237423.

llvm/lib/Transforms/Scalar/NewGVN.cpp

3179–3180 ↗

(On Diff #157854)

This seems to originate from @dberlin from rL299298 / rL291698.

[ikulagin]

llvm/lib/CodeGen/SelectionDAG/SelectionDAGBuilder.cpp

2919 ↗

(On Diff #157854)

maybe it was supposed like this:

if (std::equal(ValueVTs.begin(), ValueVTs.end(), ValueVTs.rbegin())) {

iterate from both ends

[inouehrs]

llvm/lib/CodeGen/SelectionDAG/SelectionDAGBuilder.cpp

2919 ↗

(On Diff #157854)

Comparing from both side may return true for sequences like 1, 2, 1 or 1, 2, 2, 1, although they are not all the same.

[shchenz]

Thanks all for your comments.

llvm/lib/CodeGen/SelectionDAG/SelectionDAGBuilder.cpp

2919 ↗

(On Diff #157854)

Yes, iterating from both ends can only get a palindrome pattern like {1,2,3,4,5,4,3,2,1}. Here we need to check all values in container are the same I think.

[shchenz]

ping? ^_^

[jedilyn]

llvm/lib/CodeGen/SelectionDAG/SelectionDAGBuilder.cpp

2919 ↗

(On Diff #157854)

It looks "ValueVTs.size() == 1" is redundant, even if the input vector only holds 1-element, the std::equal can still work and return true, what is this special size checking expects. Please feel free to correct me if I missed something we have to specify that here.

[jedilyn]

llvm/lib/CodeGen/SelectionDAG/SelectionDAGBuilder.cpp

2919 ↗

(On Diff #157854)

OK, it looks due to empty range related operation is an undefined behavior https://stackoverflow.com/questions/2270138/does-passing-an-empty-range-identical-iterators-to-an-stl-algorithm-result-in. Please ignore my above comment.

[shchenz]

Ping?

[shchenz]

llvm/lib/CodeGen/SelectionDAG/SelectionDAGBuilder.cpp

2919 ↗

(On Diff #157854)

thanks for looking into this issue.

[lebedev.ri]

This looks good to me in principle. A few thoughts:

1. Would be great to have test coverage for [at least some of] this. If it is possible and reasonably easy of course.
2. I wonder if we should instead create a llvm::is_splat() helper and use it here?

[shchenz]

In D49958#1202169, @lebedev.ri wrote:

This looks good to me in principle. A few thoughts:

1. Would be great to have test coverage for [at least some of] this. If it is possible and reasonably easy of course.
2. I wonder if we should instead create a llvm::is_splat() helper and use it here?

@lebedev.ri Hi Roman, thanks very much for your comments.
For 1, when I created this patch, I tried to add some testcase to expose the bug, but unfortunately failed. Since this is a obviously mistake of std::equal() and not related to compiler area, I leave it without test cases.
For 2, yes, it is a good idea to wrap it into a helper function. I have done it in new patch.

Could you help to have another look? Thanks again.

[lebedev.ri]

LG, thanks!

llvm/include/llvm/ADT/STLExtras.h

986–988 ↗

(On Diff #161170)

You want to add it in this section, somewhere closer to the end.

llvm/trunk/include/llvm/ADT/STLExtras.h

 /// deletes the second elements and then clears the container.
 template<typename Container>
 void DeleteContainerSeconds(Container &C) {
   for (auto &V : C)
     delete V.second;
   C.clear();
 }
 
+/// Get the size of a range. This is a wrapper function around std::distance
+/// which is only enabled when the operation is O(1).
+template <typename R>
+auto size(R &&Range, typename std::enable_if<
+                         std::is_same<typename std::iterator_traits<decltype(
+                                          Range.begin())>::iterator_category,
+                                      std::random_access_iterator_tag>::value,
+                         void>::type * = nullptr)
+    -> decltype(std::distance(Range.begin(), Range.end())) {
+  return std::distance(Range.begin(), Range.end());
+}
+
 /// Provide wrappers to std::for_each which take ranges instead of having to
 /// pass begin/end explicitly.
 template <typename R, typename UnaryPredicate>
 UnaryPredicate for_each(R &&Range, UnaryPredicate P) {
   return std::for_each(adl_begin(Range), adl_end(Range), P);
 }
 
 /// Provide wrappers to std::all_of which take ranges instead of having to pass

 
 /// Provide wrappers to std::lower_bound which take ranges instead of having to
 /// pass begin/end explicitly.
 template <typename R, typename ForwardIt>
 auto lower_bound(R &&Range, ForwardIt I) -> decltype(adl_begin(Range)) {
   return std::lower_bound(adl_begin(Range), adl_end(Range), I);
 }
 
+/// 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)));
+}
+
 /// Given a range of type R, iterate the entire range and return a
 /// SmallVector with elements of the vector.  This is useful, for example,
 /// when you want to iterate a range and then sort the results.
 template <unsigned Size, typename R>
 SmallVector<typename std::remove_const<detail::ValueOfRange<R>>::type, Size>
 to_vector(R &&Range) {
   return {adl_begin(Range), adl_end(Range)};
 }
 
 /// 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());
 ///
 /// This version works for any container with an erase method call accepting
 /// two iterators.
 template <typename Container, typename UnaryPredicate>
 void erase_if(Container &C, UnaryPredicate P) {
   C.erase(remove_if(C, P), C.end());
 }
 
-/// Get the size of a range. This is a wrapper function around std::distance
-/// which is only enabled when the operation is O(1).
-template <typename R>
-auto size(R &&Range, typename std::enable_if<
-                         std::is_same<typename std::iterator_traits<decltype(
-                                          Range.begin())>::iterator_category,
-                                      std::random_access_iterator_tag>::value,
-                         void>::type * = nullptr)
-    -> decltype(std::distance(Range.begin(), Range.end())) {
-  return std::distance(Range.begin(), Range.end());
-}
-
 //===----------------------------------------------------------------------===//
 //     Extra additions to <memory>
 //===----------------------------------------------------------------------===//
 
 // Implement make_unique according to N3656.
 
 /// Constructs a `new T()` with the given args and returns a
 ///        `unique_ptr<T>` which owns the object.

llvm/trunk/lib/CodeGen/SelectionDAG/SelectionDAGBuilder.cpp

void SelectionDAGBuilder::visitSelect(const User &I) {
   SDValue Cond     = getValue(I.getOperand(0));
   SDValue LHSVal   = getValue(I.getOperand(1));
   SDValue RHSVal   = getValue(I.getOperand(2));
   auto BaseOps = {Cond};
   ISD::NodeType OpCode = Cond.getValueType().isVector() ?
     ISD::VSELECT : ISD::SELECT;
 
   // Min/max matching is only viable if all output VTs are the same.
-  if (std::equal(ValueVTs.begin(), ValueVTs.end(), ValueVTs.begin())) {
+  if (is_splat(ValueVTs)) {
     EVT VT = ValueVTs[0];
     LLVMContext &Ctx = *DAG.getContext();
     auto &TLI = DAG.getTargetLoweringInfo();
 
     // We care about the legality of the operation after it has been type
     // legalized.
     while (TLI.getTypeAction(Ctx, VT) != TargetLoweringBase::TypeLegal &&
            VT != TLI.getTypeToTransformTo(Ctx, VT))

llvm/trunk/lib/Transforms/Scalar/NewGVN.cpp

bool NewGVN::singleReachablePHIPath(
   auto ReachableOperandPred = [&](const Use &U) {
     return ReachableEdges.count({MP->getIncomingBlock(U), MP->getBlock()});
   };
   auto FilteredPhiArgs =
       make_filter_range(MP->operands(), ReachableOperandPred);
   SmallVector<const Value *, 32> OperandList;
   std::copy(FilteredPhiArgs.begin(), FilteredPhiArgs.end(),
             std::back_inserter(OperandList));
-  bool Okay = OperandList.size() == 1;
-  if (!Okay)
-    Okay =
-        std::equal(OperandList.begin(), OperandList.end(), OperandList.begin());
+  bool Okay = is_splat(OperandList);
   if (Okay)
     return singleReachablePHIPath(Visited, cast<MemoryAccess>(OperandList[0]),
                                   Second);
   return false;
 }
 
 // Verify the that the memory equivalence table makes sense relative to the
 // congruence classes.  Note that this checking is not perfect, and is currently
if (auto *FirstMUD = dyn_cast<MemoryUseOrDef>(KV.first)) {
       auto FilteredPhiArgs =
           make_filter_range(FirstMP->operands(), ReachableOperandPred);
       SmallVector<const CongruenceClass *, 16> PhiOpClasses;
       std::transform(FilteredPhiArgs.begin(), FilteredPhiArgs.end(),
                      std::back_inserter(PhiOpClasses), [&](const Use &U) {
                        const MemoryDef *MD = cast<MemoryDef>(U);
                        return ValueToClass.lookup(MD->getMemoryInst());
                      });
-      assert(std::equal(PhiOpClasses.begin(), PhiOpClasses.end(),
-                        PhiOpClasses.begin()) &&
+      assert(is_splat(PhiOpClasses) &&
              "All MemoryPhi arguments should be in the same class");
     }
   }
 #endif
 }
 
 // Verify that the sparse propagation we did actually found the maximal fixpoint
 // We do this by storing the value to class mapping, touching all instructions,

llvm/trunk/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(4, *I);
   ++I;
   EXPECT_EQ(EIR.end(), I);
 }
 
+TEST(STLExtrasTest, splat) {
+  std::vector<int> V;
+  EXPECT_FALSE(is_splat(V));
+
+  V.push_back(1);
+  EXPECT_TRUE(is_splat(V));
+
+  V.push_back(1);
+  V.push_back(1);
+  EXPECT_TRUE(is_splat(V));
+
+  V.push_back(2);
+  EXPECT_FALSE(is_splat(V));
+}
+
 } // namespace