Rohith Kapelli <[email protected]> writes:
> 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.
When doing the original review, I was thinking along the lines of (b).
But it looked like it might be cumbersome to calculate. Is there an
off-the-self way of asking "does this value vary only in subloops and
superloops?"?
So I was hoping there might be a simpler way. However, the same-base
examples above suggest that (b) really is the right thing after all.
Isn't it a bug that unroll-and-jam's adjust_unroll_factor doesn't check
whether DDR_ARE_DEPENDENT (ddr) is chrec_dont_know? The dump functions
in tree-data-ref.cc suggest that the distance vectors shouldn't be read
in that case. And there is an existing early-out in
add_other_self_distances:
if (DDR_NUM_SUBSCRIPTS (ddr) != 1)
{
DDR_ARE_DEPENDENT (ddr) = chrec_dont_know;
return;
}
where (AIUI) the code is explicitly dropping a case that would matter
to consumers of the distance vectors.
> 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.
Do you have examples of the refused prefetch and interchange transforms?
Are they being refused for the "right" reasons, or are we being too
conservative?
Thanks,
Richard
> 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
