https://gcc.gnu.org/bugzilla/show_bug.cgi?id=49782
--- Comment #4 from Michael Matz <matz at gcc dot gnu.org> ---
(In reply to Michael Matz from comment #3)
> (In reply to Richard Biener from comment #2)
> > The vectorizer just does not try to ask - it only analyzes dependences of
> > the innermost loop where a[j] has invariant address.
>
> Nit: a[i] is the invariant one in the inner loop.
>
> > loop distribution does, and there we hit
> >
> > (compute_affine_dependence
> > ref_a: a[i_17], stmt_a: _1 = a[i_17];
> > ref_b: a[j_16], stmt_b: a[j_16] = _2;
> > (analyze_overlapping_iterations
> > (chrec_a = {0, +, 1}<nw>_1)
> > (chrec_b = {0, +, 1}_2)
> > (analyze_miv_subscript
> > (analyze_subscript_affine_affine
> > (overlaps_a = [0 + 1 * x_1])
> > (overlaps_b = [0 + 1 * x_1]))
> > )
> > (overlap_iterations_a = [0 + 1 * x_1])
> > (overlap_iterations_b = [0 + 1 * x_1]))
> > (Dependence relation cannot be represented by distance vector.)
> > )
> > consider run-time aliasing test between a[i_17] and a[j_16]
>
> Well, that's correct. There's no distance vector that describes this
> dependence. For instance for the read-after-write dependences (from a[j] to
> a[i]), we have dependences at iterations (i,j) = (0,0) to (1,0)
> (in fact to (*,0)), and from (1,1) to (0,1) (again, actually to (*,1)).
Bah, sorry. The second example dependence would be the write-after-read dep
from iteration (0,1) (read of a[0]) to (1,0) (write of a[0]), which comes
out as distance (1,-1), incompatible as distance with the (1,0). As direction
vector it would still be fine between those two (coming out as (>,*)), but
eventually there are still more that also make the first direction be back and
forward, so the rest applies.
> I'm not quite sure what this bug is about, which optimization is missed?
> (do note that the return value a[0] does depend on all other a[*] eventually)
As per our discussion I now understand that the missed optimization is
actually rather a useless-addition: the vectorizer adds a runtime aliasing
check to vectorize (because, as it correctly determines, and as the above
shows,
the dependence really can't be expressed in a closed classic form).
But the problem is that that check is in fact always false at runtime, and
hence the vectorized variant is never taken.
Generally such cannot be solved: if we could somehow prove that an aliasing
runtime check (after we deem it necessary because no closed form of the
dependence exists) is always true (or false) we could have solved the
dependence
direction calculation. So, it would always be special code that checks for
specific situation. In this case that would of course be possible and it
may be worthwhile, but it is outside of the dependence framework, but rather
in its client code.
