Hi Michael,
Thanks. I agree: tree-data-ref's output has to be right, and the passes
shouldn't need guards, so I've dropped that version.
Corrections first. The (b) I described lost foo11's unroll-and-jam in
gcc.dg/unroll-and-jam.c, and I didn't say so; the version below keeps
it. And point 2 wasn't enough: its condition is necessary but not
sufficient. One free loop outside the constrained loops isn't always
covered: add_multivariate_self_dist adds its outer distances in one
direction only. Interchange swaps this nest and gets it wrong at -O3
(the arrays are unsigned):
for (int f = 0; f < nf; f++)
for (int i = 0; i < ni; i++)
for (int j = 0; j < nj; j++)
a[i - j + 8] = a[i - j + 8] * 3 + B[i][f];
Also, a self dependence that can't be represented (more than two varying
loops, or a non-constant step or initial value) only clears
DDR_AFFINE_P. The zero vector stays, and the passes trust it. This one
goes wrong at -O3 through the outer-loop vectorizer, so my "no
vectorizer miscompile" doesn't hold any more:
for (int i0 = 0; i0 < n0; i0++)
for (int i1 = 0; i1 < n1; i1++)
for (int i2 = 0; i2 < n2; i2++)
for (int i3 = 0; i3 < n3; i3++)
A0[i1 + i2 + i3]
= A0[i1 + i2 + i3] * 3u + B[i0][i1] + (unsigned) i3;
Richard B.: no_evolution_in_loop_p finds the same free loops as
evolution_part_in_loop_num, which is what I used, on the testsuite
corpus and my probes. Happy to switch.
Richard S.: yes, that's a latent bug. Only the early-out in
add_other_self_distances leaves vectors on a chrec_dont_know relation,
and with a write, unroll-and-jam gives up there anyway: the write's own
self dependence hits the same early-out. The patch releases the vectors
of every relation it marks unknown, so unroll-and-jam is unchanged. I
can also add the check in adjust_unroll_factor if you prefer. As for
examples: in my own probe set, each built with several flag sets, it
refuses transforms that trunk applies in 63 nests. 45 would miscompile,
10 reverse a dependence whose value gets overwritten later, and 6 are
only right because the update commutes. The other 2 are too
conservative. Here's one:
for (int i0 = 0; i0 < n0; i0++)
for (int i1 = 0; i1 + 1 < n1; i1++)
for (int i2 = 0; i2 < n2; i2++)
A[i0][i1 + 1] = A[i0][i1] * 3 + (unsigned) B[i1][i0][i2];
The inner pair can't be swapped ((0, 1, -1) is a real distance), and
interchange stops at the first pair it can't swap, so it never reaches
the outer pair trunk swaps. At -O3 the testsuite corpus loses two
decisions: unroll-and-jam in pr102087.c, and an interchange in libgomp's
task_dep-5.f90 that looks legal by hand. Its self dependence has three
varying loops, so part 1 makes it unknown. With -fprefetch-loop-arrays
no prefetch is issued or dropped; reuse estimates change in 171 files.
The proposal is tree-data-ref.cc only, about 150 lines, with no pass
changes. Part 1 makes a self dependence with no distance-vector
representation unknown and releases its vectors. Part 2 handles free
loops, where the distance can be anything: when the vectors agree up to
sign in the constrained loops, I add -1, 0 and +1 in each free loop's
component (Richard S.'s case B). Otherwise it gives up, as it always
does in case A. For correctness, the users need only the signs and the
smallest distance there. Loop distribution counts vectors, but extra
ones only make it more conservative.
It fixes PR115869, PR105771, PR120254 and the PR109184 testcase
(-O2 -floop-interchange -fno-move-loop-stores). I've left one case
alone: a single free inner loop with zero distance in every other loop,
where only vectors positive in that loop are missing. Loop distribution
has worked around it since PR115347, and completing it belongs with a
real '*'. That's the cleaner answer; I'd gladly look at it later.
Targeted tests (vect.exp, interchange, unroll-and-jam, prefetch) show no
new failures on aarch64, and randomized loop nests turn up no wrong code
of this kind. Next I will run bootstrap and full testsuite runs on
aarch64 and x86_64, and post both patches when they are clean. Does
this direction look right to you?
Thanks,
Rohith
