Hi Richard,
Thanks for the review. I looked into where the missed dependences
come from, and it is wider than the structure case.
1. It also happens with plain arrays and the same base. PR120254 is
wrong at -O3 on trunk (92a7b1230e6): for A[k+1][i][i] against
A[k][i][i] in an (i, j, k) nest the only distance vector is (0 0 1),
but (0 1 -1) is a real distance, and interchange swaps j and k.
2. The cause is in build_classic_dist_vector. Call a loop of the nest
free when none of the compared access functions evolves in it.
A free loop gets component 0 in every distance vector. Only when
it lies outside every constrained loop are vectors added with 1 in
its component (add_outer_distances, add_other_self_distances,
add_distance_for_zero_overlaps). So the vectors cover all
distances only when there is no free loop, or exactly one that
lies outside all the constrained loops.
3. In the structure case, full_seq = struct_seq drops the base
subscript, so the loop in which the objects move becomes a free
loop. That is PR115869 and PR105771.
4. Unroll-and-jam already guards against this using DR_ACCESS_FNS, but
the structure path defeats that check because it looks at the
reference's access functions rather than the compared ones. Loop
distribution has its own guard. Interchange has none. I found no
vectorizer miscompile.
5. On x[k].v vs x[k + d].v: giving it the same dependences as x[k] vs
x[k + d] would be right, but not enough on its own, since as in 1
plain arrays miss distances too in deeper nests. For x[k].v[j],
j invariant or in an outer loop behaves like x[k].v; with j in an
inner loop the vectors are conservative in a two-deep nest, but a
three-deep nest with the objects moving in the middle loop
miscompiles at -O3 -fno-loop-unroll-and-jam.
I have tried a fix in both places:
a) In the consumers: unroll-and-jam's existing guard uses the
compared access functions, and interchange refuses only a loop
pair whose swap a missing distance could reverse. 57 changed
lines.
b) In tree-data-ref.cc: give up on a relation whose vectors miss a
free loop. This also has to release the distance vectors
(unroll-and-jam reads them even on chrec_dont_know) and count a
loop as free only if it contains both references. 61 changed
lines.
Both fix every miscompile of this kind I have found, including
PR120254 and the PR109184 testcase. Compiling the C, C++ and Fortran
testsuites at -O3, and again with -fprefetch-loop-arrays, (a) changes
no vectorizer, distribution or prefetch decision. (b) changes no
issued prefetch either, but changes prefetch reuse-distance estimates
in 23 files and refuses more valid transforms. Either way, a few
interchanges that are only valid because the update commutes are
refused.
Testing so far, on aarch64-linux: both were built and run through the
same targeted tests (the new tests, vect.exp, the interchange,
unroll-and-jam and prefetch tests) and the testsuite comparison above.
(a) has also passed a three-stage bootstrap and full regression
testing against an unpatched baseline; (b) has not had a bootstrap or
a full regression run.
The v1 patch does not fix PR120254 and should be considered
superseded.
Which direction would you prefer? I will post (a) once the release
branch testing finishes, unless you would rather have (b), in which
case I will give it the same full testing first.
Thanks,
Rohith
