[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

2934–2936

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

2934–2936

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

2935

This seems to originate from @jmolloy from rL237423.

llvm/lib/Transforms/Scalar/NewGVN.cpp

3179–3180

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

[ikulagin]

llvm/lib/CodeGen/SelectionDAG/SelectionDAGBuilder.cpp

2935

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

2935

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

2935

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

2935

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

2935

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

2935

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

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

llvm/include/llvm/ADT/STLExtras.h

 inline void sort(IteratorTy Start, IteratorTy End, Compare Comp) {
 #ifdef EXPENSIVE_CHECKS
   std::mt19937 Generator(std::random_device{}());
   std::shuffle(Start, End, Generator);
 #endif
   std::sort(Start, End, Comp);
 }
 
 //===----------------------------------------------------------------------===//
 //     Extra additions to <algorithm>
 //===----------------------------------------------------------------------===//
 
 /// For a container of pointers, deletes the pointers and then clears the
 /// container.
 template<typename Container>
 void DeleteContainerPointers(Container &C) {
   for (auto V : C)
     delete V;
   C.clear();
build_index_impl<
         std::tuple_size<typename std::decay<Tuple>::type>::value>{})) {
   using Indices = build_index_impl<
       std::tuple_size<typename std::decay<Tuple>::type>::value>;
 
   return detail::apply_tuple_impl(std::forward<F>(f), std::forward<Tuple>(t),
                                   Indices{});
 }
 
+/// 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)));
+}
+
 } // end namespace llvm
 
 #endif // LLVM_ADT_STLEXTRAS_H

llvm/lib/CodeGen/SelectionDAG/SelectionDAGBuilder.cpp

void SelectionDAGBuilder::visitSelect(const User &I) {
   SmallVector<SDValue, 4> Values(NumValues);
   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))
       VT = TLI.getTypeToTransformTo(Ctx, VT);

llvm/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/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