On Tue, 13 Oct 2026, Richard Sandiford wrote:
> 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?"?
no_evolution_in_loop_p can possibly be used?
> 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?
IIRC Michael Matz analyzed a latent data dependence issue that boils
down to the bad representation of distance/direction vectors which
do not encode the do-not-know (either direction) case leading to
downstream wrong answers exactly in the case where there are
loops without an evolution. Maybe he remembers and also the
associated PR.
Richard.
> 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
>
--
Richard Biener <[email protected]>
SUSE Software Solutions Germany GmbH,
Frankenstrasse 146, 90461 Nuernberg, Germany;
GF: Stefan Gaiser, Jochen Jaser, Abhinav Puri; (HRB 36809, AG Nuernberg)
