Rohith Kapelli <[email protected]> writes:
> For references with different bases, dependence analysis compares only
> the structure-rooted access functions and sets DDR_COULD_BE_INDEPENDENT_P.
> The distance vectors are then only valid for one fixed pair of objects,
> which is the case when DDR_OBJECT_A is set because both objects are
> invariant in the loop nest. In PR115869 res[k].v and res[k + d].v move
> with k, so the vectors (0 0), (1 0) and (0 1) miss the (1, -d) dependence
> and loop interchange wrongly swaps the nest. PR105771 is the same problem
> in unroll-and-jam.
>
> The vectorizer and prefetching handle such relations, but interchange and
> unroll-and-jam use the vectors as they are and cannot check the objects at
> runtime. The following makes both passes give up when DDR_OBJECT_A is not
> set.
>
> PR tree-optimization/115869
> PR tree-optimization/105771
>
> gcc/ChangeLog:
>
> * gimple-loop-interchange.cc (tree_loop_interchange_compute_ddrs):
> Give up if DDR_COULD_BE_INDEPENDENT_P is set and DDR_OBJECT_A is not.
> * gimple-loop-jam.cc (adjust_unroll_factor): Likewise.
>
> gcc/testsuite/ChangeLog:
>
> * gcc.dg/torture/pr105771.c: New test.
> * gcc.dg/torture/pr115869.c: New test.
>
> Signed-off-by: Rohith Kapelli <[email protected]>
> ---
> Bootstrapped and regression tested on aarch64-unknown-linux-gnu, and on
> the gcc-14, gcc-15 and gcc-16 branches. An attempt to fix this in
> tree-data-ref.cc instead regressed gcc.dg/vect/vect-alias-check-3.c.
>
> OK for trunk and the branches?
I think the problem is instead in tree-data-ref.cc itself. As the comments
say, the dependence distances are supposed to be conservatively correct even
when DDR_COULD_BE_INDEPEDENT_P is true. (Thus the check in the prefetcher
should be unnecessary.)
The else in:
if (same_base_p)
{
if (indices_a->unconstrained_base)
full_seq.length += 1;
}
else
full_seq = struct_seq;
was intended mostly to handle cases where an array access is a
subaccess of a structure access, such as in:
x->foo[k] vs. y->foo[k + 1]
In this case we can compute a conservative dependence distance for a
single-nested k loop even if x and y are not invariant, since aliasing
rules don't allow x->foo and y->foo to partially overlap.
But "x[k].v" vs. "x[k + d].v" provides no more information than
"x[k]" vs. "x[k + d]" and so the dependencies should be the same.
Similarly for "x[k].v[j]" vs. "x[k + d].v[j]" where "j" is indepedent
of "k".
I'll need to think more about where in the compute_affine_dependence
this should be handled. I just wanted to say something now rather than
leave the patch unreviewed.
Thanks,
Richard
>
> gcc/gimple-loop-interchange.cc | 7 +++++
> gcc/gimple-loop-jam.cc | 5 +++-
> gcc/testsuite/gcc.dg/torture/pr105771.c | 36 +++++++++++++++++++++++++
> gcc/testsuite/gcc.dg/torture/pr115869.c | 25 +++++++++++++++++
> 4 files changed, 72 insertions(+), 1 deletion(-)
> create mode 100644 gcc/testsuite/gcc.dg/torture/pr105771.c
> create mode 100644 gcc/testsuite/gcc.dg/torture/pr115869.c
>
> diff --git a/gcc/gimple-loop-interchange.cc b/gcc/gimple-loop-interchange.cc
> index 7f8ca2f9d57b..4091d1916ed1 100644
> --- a/gcc/gimple-loop-interchange.cc
> +++ b/gcc/gimple-loop-interchange.cc
> @@ -1883,6 +1883,13 @@ tree_loop_interchange_compute_ddrs (vec<loop_p>
> loop_nest,
> && DDR_NUM_DIR_VECTS (ddr) == 0))
> return false;
>
> + /* The vectors describe one fixed pair of objects only when
> + DDR_OBJECT_A is set; this pass cannot check them at runtime. */
> + if (DDR_ARE_DEPENDENT (ddr) == NULL_TREE
> + && DDR_COULD_BE_INDEPENDENT_P (ddr)
> + && !DDR_OBJECT_A (ddr))
> + return false;
> +
> /* If either data references is in outer loop of nest, we require
> no dependence here because the data reference need to be moved
> into inner loop during interchange. */
> diff --git a/gcc/gimple-loop-jam.cc b/gcc/gimple-loop-jam.cc
> index 2c4162d17a2a..7b39f40f229a 100644
> --- a/gcc/gimple-loop-jam.cc
> +++ b/gcc/gimple-loop-jam.cc
> @@ -407,7 +407,10 @@ adjust_unroll_factor (class loop *inner, struct
> data_dependence_relation *ddr,
> bool ret = false;
> if (DDR_ARE_DEPENDENT (ddr) != chrec_known)
> {
> - if (DDR_NUM_DIST_VECTS (ddr) == 0)
> + /* The vectors describe one fixed pair of objects only when
> + DDR_OBJECT_A is set; this pass cannot check them at runtime. */
> + if (DDR_NUM_DIST_VECTS (ddr) == 0
> + || (DDR_COULD_BE_INDEPENDENT_P (ddr) && !DDR_OBJECT_A (ddr)))
> return false;
> unsigned i;
> lambda_vector dist_v;
> diff --git a/gcc/testsuite/gcc.dg/torture/pr105771.c
> b/gcc/testsuite/gcc.dg/torture/pr105771.c
> new file mode 100644
> index 000000000000..dc862f7e7cae
> --- /dev/null
> +++ b/gcc/testsuite/gcc.dg/torture/pr105771.c
> @@ -0,0 +1,36 @@
> +/* PR tree-optimization/105771 */
> +/* { dg-do run } */
> +/* { dg-additional-options "-floop-unroll-and-jam" } */
> +
> +struct st { unsigned v; };
> +
> +__attribute__((noipa)) void
> +f (struct st *p, int m, int n, int d)
> +{
> + for (int i = 0; i < m; i++)
> + for (int k = 0; k + d < n; k++)
> + p[k + d].v = p[k + d].v * 3 + p[k].v + (unsigned) i;
> +}
> +
> +__attribute__((noipa)) void
> +g (volatile unsigned *q, int m, int n, int d)
> +{
> + for (int i = 0; i < m; i++)
> + for (int k = 0; k + d < n; k++)
> + q[k + d] = q[k + d] * 3 + q[k] + (unsigned) i;
> +}
> +
> +int
> +main ()
> +{
> + struct st p[16];
> + unsigned q[16];
> + for (int j = 0; j < 16; j++)
> + p[j].v = q[j] = (unsigned) j + 1;
> + f (p, 8, 16, 1);
> + g (q, 8, 16, 1);
> + for (int j = 0; j < 16; j++)
> + if (p[j].v != q[j])
> + __builtin_abort ();
> + return 0;
> +}
> diff --git a/gcc/testsuite/gcc.dg/torture/pr115869.c
> b/gcc/testsuite/gcc.dg/torture/pr115869.c
> new file mode 100644
> index 000000000000..083a6180cc30
> --- /dev/null
> +++ b/gcc/testsuite/gcc.dg/torture/pr115869.c
> @@ -0,0 +1,25 @@
> +/* PR tree-optimization/115869 */
> +/* { dg-do run } */
> +/* { dg-additional-options "-floop-interchange" } */
> +
> +struct st { int v; };
> +
> +__attribute__((noipa)) int
> +f (struct st *res)
> +{
> + res[0].v = 1;
> + for (int d = 1; d < 3; d++)
> + for (int i = 0; i < 2; i++)
> + for (int k = 0; k + d < 3; k++)
> + res[k + d].v += res[k].v;
> + return res[2].v;
> +}
> +
> +int
> +main ()
> +{
> + struct st res[3] = { { 0 }, { 0 }, { 0 } };
> + if (f (res) != 5)
> + __builtin_abort ();
> + return 0;
> +}
