This is an archive of the discontinued LLVM Phabricator instance.

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

Authored by shchenz on Jul 28 2018, 7:03 AM.

Details

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.

Diff Detail

Event Timeline

shchenz created this revision.Jul 28 2018, 7:03 AM
lebedev.ri added inline comments.Jul 28 2018, 9:14 AM
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 added inline comments.
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 added subscribers: dberlin, jmolloy.

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.

shchenz edited the summary of this revision. (Show Details)Jul 28 2018, 5:16 PM
ikulagin added inline comments.
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 added inline comments.
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.

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.

jedilyn added inline comments.
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 added inline comments.Aug 13 2018, 7:51 PM
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 added inline comments.Aug 13 2018, 7:55 PM
llvm/lib/CodeGen/SelectionDAG/SelectionDAGBuilder.cpp
2935

thanks for looking into this issue.

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 updated this revision to Diff 161170.Aug 16 2018, 11:45 PM

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 accepted this revision.Aug 16 2018, 11:57 PM

LG, thanks!

llvm/include/llvm/ADT/STLExtras.h
986–988

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

This revision is now accepted and ready to land.Aug 16 2018, 11:57 PM
This revision was automatically updated to reflect the committed changes.