Erroneous loop optimization with -O2, accessing to wrong std::vector element

[Quuxplusone]

Bugzilla Link	PR38786
Status	RESOLVED FIXED
Importance	P release blocker
Reported by	Sylvestre Ledru (sylvestre@debian.org)
Reported on	2018-08-31 00:56:12 -0700
Last modified on	2018-09-11 03:11:42 -0700
Version	6.0
Hardware	PC Linux
CC	anna@azul.com, ayal.zaks@intel.com, hans@chromium.org, hfinkel@anl.gov, llvm-bugs@lists.llvm.org, mssimpso@codeaurora.org, orivej@gmx.fr, silviu.baranga@arm.com
Fixed by commit(s)
Attachments	bug-38786.c (326 bytes, text/x-csrc) bug-38786.c (322 bytes, text/x-csrc) reproducer.ll (1302 bytes, text/plain) PR38786.patch (679 bytes, text/plain)
Blocks	PR38406
Blocked by
See also	http://bugs.debian.org/907649

Reported initially here http://bugs.debian.org/907649

Clang 5.0 doesn't have the issue.
I can reproduce the issue from Clang 6 => 8
----
#include <iostream>
#include <vector>

class Foo {
private:
    std::vector<double> _a;
    std::vector<double> _d;

public:
    Foo(const std::vector<double> &x, const std::vector<double> &y)
        : _a(x.size()), _d(x.size()) {

        for (unsigned int i = 0; i < x.size() - 1; i++) {
            _a[i] = x[i + 1] - x[i];
            _d[i] = (y[i + 1] - y[i]) / _a[i];
        }
    }

    const std::vector<double> &a() const noexcept { return _a; }
};

int main() {

    // Read input file
    std::vector<double> x, y;
    while (std::cin) {
        double xi, yi;
        if (std::cin >> xi >> yi) {
            x.push_back(xi);
            y.push_back(yi);
        }
    }

    // Create Foo instance
    Foo foo(x, y);

    // Print computed data
    for (auto a : foo.a()) std::cout << a << '\n';

    return 0;
}
----

$> clang++-6.0 -std=c++11 -O2 -o bug  bug.cpp
$> paste <(seq 1 5) <(seq 1 5) | ./bug

the expected result is:
1
1
1
1
0

But one gets:
1
2
2
0
0

Works with -O1

[Quuxplusone]

Hans, I am marking it blocking as release 7 to bring that to your attention. However, as we already shipped 6.0 with this issue, maybe you might not want to take it (but this is a pain for users to debug such issue, you might want to take a patch :)

[Quuxplusone]

Bisect shows that this was introduced in https://reviews.llvm.org/rL313012

[Quuxplusone]

r313012 allows versioning of the loop for vectorisation.

In the example, the code is vectorizable and the vectorised version of the loop should be executed. So it seems that the change exposed some hidden bug.

FWIW I can reproduce this on AArch64 as well, so the problem is somewhere in the mid-end optimizers.

[Quuxplusone]

Pretty interesting, the problem also disappears when compiling with -
fsanitize=undefined, e.g.:

$ clang++ -O2 pr38786-2.cpp -o pr38786-2 && paste <(seq 1 5) <(seq 1 5) |
./pr38786-2
1
2
2
0
0

$ clang++ -fsanitize=undefined -O2 pr38786-2.cpp -o pr38786-2 && paste <(seq 1
5) <(seq 1 5) | ./pr38786-2
1
1
1
1
0

As far as I can see, the program isn't doing anything that is undefined, though.

[Quuxplusone]

Attached bug-38786.c (326 bytes, text/x-csrc): Reduced testcase

[Quuxplusone]

Attached bug-38786.c (322 bytes, text/x-csrc): Reduced testcase

[Quuxplusone]

Attached reproducer.ll (1302 bytes, text/plain): vectorizer IR input

[Quuxplusone]

It seems that the problem is somewhere in fixFirstOrderRecurrence.

@Matthew, Anna: any idea what going on here? My analysis above would suggest that first order recurrences are broken at the moment, but maybe I've missed something obvious?

[Quuxplusone]

Attached PR38786.patch (679 bytes, text/plain): Tentative fix

[Quuxplusone]

Thanks! Your patch fixes the issue.

[Quuxplusone]

(In reply to Orivej Desh from comment #10)
> Thanks! Your patch fixes the issue.

Are you working on a patch with test case that can be send for review? It would
be nice to get this fixed for the 7.0.0 release, but then it has to happen very
soon.

[Quuxplusone]

I have created https://reviews.llvm.org/D51639

[Quuxplusone]

For my notes: the patch landed in r341416. Let's have that bake in trunk a little bit before merging.

[Quuxplusone]

Merged in r341523.

[Quuxplusone]

This section of the patch doesn't apply to the 6.0 branch.

What should it be it?

--- lib/Transforms/Vectorize/LoopVectorize.cpp
+++ lib/Transforms/Vectorize/LoopVectorize.cpp
@@ -4529,6 +4529,11 @@
       // isOutOfScope operands cannot be uniform instructions.
       if (isOutOfScope(OV))
         continue;
+      // First order recurrence Phi's should typically be considered
+      // non-uniform.
+      auto *OP = dyn_cast<PHINode>(OV);
+      if (OP && Legal->isFirstOrderRecurrence(OP))
+        continue;
       // If all the users of the operand are uniform, then add the
       // operand into the uniform worklist.
       auto *OI = cast<Instruction>(OV);

[Quuxplusone]

LoopVectorize.cpp in release_60 and release_70 do not have surrounding comments. You can apply the diff from release_70: svn diff http://llvm.org/svn/llvm-project/llvm/branches/release_70/{lib,test} -c341523