Richard Biener <[email protected]> writes:
> 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?
Ah, yeah, thanks. Think I only searched the .cc.
>> 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.
Ah, ok. It wasn't explicit in what I said last time, but: the case
of varying but different bases (DDR_COULD_BE_INDEPENDENT_P &&
!DDR_OBJECT_A, "case A") is still different from the other cases
("case B"). For case B we do have the option of adding more vectors
(at the risk of explosion for deep nests). But for case A we have no
option but to give up. The analysis should be the same for both cases,
or at least be similar, but the end result could be different.
So I was wondering whether the missed transforms above indicated that
we should try harder to generate correct vectors for case B. It sounds
like that was the anticipated fix for the latent issue you mention.
Richard
