Hello,
On Tue, 13 Oct 2026, Richard Biener wrote:
> > > 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.
...
> > 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.
>
> 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.
I don't and I can't seem to find my notes about that. I think my last two
comments at https://gcc.gnu.org/bugzilla/show_bug.cgi?id=49782#c3 are
remnants of what was the cause that ultimately lead me to investigate the
current representation of distance and direction vectors in tree-data-ref,
whatever that cause really was :)
I think the observations (1) to (5) are correct, though I seem to remember
that also the fact that if there are multiple directions (+1 and -1) in
one dimension that the resulting dimension isn't correctly collapsing to
'*' (i.e. not necessarily only in cases where the dimension is such
because of invariantness in its respective iteration dimension). In fact
we have no notion of '*' at all, and hence variously either give up
totally or create wrong or incomplete distance vectors.
There certainly were confusing interactions between the manipulation of
nr-of-dimensions and sometimes ignoring or not ignoring the such-changed
dimensions and building the classic distance vectors out of that: for
client code the number of components in these vectors must match the
nest-depth of the analyzed loop nest and the manipulation above shuffles
components around in non-obvious ways ultimately leading to comparing
dimensions that really stem from different loops, and hence needing
strange-looking workaround in several of the client code that currently
exists in GCC. That all usually only starts to matter when a real nest,
i.e. at least two loops, are involved.
The fact that unroll-and-jam doesn't test DDR_ARE_DEPENDEND for
chrec_dont_know may be an artifact of such client-code work-arounds, I
don't remember. I also may have just missed to add it and the other
necessary work-arounds were hiding the fact.
Another wart was that the direction vector is calculation from the
distance vector(s), which is always optimal: the direction vector may
exist when the distance vectors aren't representable, which we don't
handle.
Either way, I think just adding various additional guards to the existing
passes is the wrong way. The output of tree-data-ref (and in particular
the dependence relation pairs) simply needs to be correct. For that I
think we need a representation of '*' in a component, and we need to stop
adding fake dimensions that aren't directly related to a loop (certainly
such fake dimensions must at least not be used when considering a pair of
datarefs), and then the component of a relation between two datarefs where
one is invariant and the other affine will naturally come out as '*', as
it should be.
I'm sorry if this sounds like unstructured rambling, I really don't
remember the details or find my notes :-(
Ciao,
Michael.
>
> 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
> >
>
>
