On Fri, 16 Oct 2026, Rohith Kapelli wrote: > Call a loop of the nest free when it contains both references and no > compared access function evolves in it: the dependence can then have any > distance in that loop. build_classic_dist_vector gives a free loop a > distance of its own only when it is the only one and lies outside the > loops the subscripts constrain; otherwise its distance is taken as zero, > which misses the distances of opposite signs. Interchange and > unroll-and-jam then reverse dependences that exist, as for structure > accesses through objects that move in the nest (PR115869, PR105771) and > for plain arrays (PR120254, PR109184). > > When the vectors agree up to sign in the constrained loops, add every > lexicographically positive vector with -1, 0 or 1 in each free loop and > the first vector's distances, or their opposite, in the other loops. > For correctness the users need only the signs and the smallest distance > in such a loop. Give up instead when the bases differ and the objects > move in the nest, when the vectors disagree (as the vectors of > add_multivariate_self_dist do, whose outer distances go one way only), > when more than three loops are free, or when more than 32 vectors would > be needed.
This is technically sound, but see below > PR tree-optimization/115869 > PR tree-optimization/105771 > PR tree-optimization/120254 > PR tree-optimization/109184 > > gcc/ChangeLog: > > * tree-data-ref.cc (dist_vectors_agree_p): New function. > (free_loop_distances_lost_p): Likewise. > (add_free_loop_distances): Likewise. > (subscript_dependence_tester): Complete the distance vectors of > free loops, or give up. > > gcc/testsuite/ChangeLog: > > * gcc.dg/torture/pr105771.c: New test. > * gcc.dg/torture/pr109184.c: New test. > * gcc.dg/torture/pr115869.c: New test. > * gcc.dg/torture/pr115869-2.c: New test. > * gcc.dg/torture/pr115869-3.c: New test. > * gcc.dg/torture/pr115869-5.c: New test. > * gcc.dg/torture/pr120254.c: New test. > > Signed-off-by: Rohith Kapelli <[email protected]> > --- > gcc/testsuite/gcc.dg/torture/pr105771.c | 36 ++++++ > gcc/testsuite/gcc.dg/torture/pr109184.c | 29 +++++ > gcc/testsuite/gcc.dg/torture/pr115869-2.c | 40 ++++++ > gcc/testsuite/gcc.dg/torture/pr115869-3.c | 33 +++++ > gcc/testsuite/gcc.dg/torture/pr115869-5.c | 33 +++++ > gcc/testsuite/gcc.dg/torture/pr115869.c | 25 ++++ > gcc/testsuite/gcc.dg/torture/pr120254.c | 30 +++++ > gcc/tree-data-ref.cc | 141 ++++++++++++++++++++++ > 8 files changed, 367 insertions(+) > create mode 100644 gcc/testsuite/gcc.dg/torture/pr105771.c > create mode 100644 gcc/testsuite/gcc.dg/torture/pr109184.c > create mode 100644 gcc/testsuite/gcc.dg/torture/pr115869-2.c > create mode 100644 gcc/testsuite/gcc.dg/torture/pr115869-3.c > create mode 100644 gcc/testsuite/gcc.dg/torture/pr115869-5.c > create mode 100644 gcc/testsuite/gcc.dg/torture/pr115869.c > create mode 100644 gcc/testsuite/gcc.dg/torture/pr120254.c > > 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/pr109184.c > b/gcc/testsuite/gcc.dg/torture/pr109184.c > new file mode 100644 > index 000000000000..8c853626da8e > --- /dev/null > +++ b/gcc/testsuite/gcc.dg/torture/pr109184.c > @@ -0,0 +1,29 @@ > +/* PR tree-optimization/109184 */ > +/* { dg-do run } */ > +/* { dg-additional-options "-floop-interchange -fno-move-loop-stores" } */ > + > +static int g_1731[7] = { 42, 0, 0, 0, 0, 0, 42 }; > + > +void __attribute__((noipa)) > +foo () > +{ > + int l_1930[5] = { 0, }; > + > + for (int i = 0; i < 15; ++i) > + for (int j = 4; (j >= 1); j -= 1) > +#pragma GCC unroll 0 > + for (int k = 0; (k <= 4); k += 1) > + g_1731[(j + 1)] = --l_1930[k]; > +} > + > +int > +main () > +{ > + foo (); > + if (g_1731[0] != 42 > + || g_1731[1] != 0 || g_1731[2] != -60 || g_1731[3] != -59 > + || g_1731[4] != -58 || g_1731[5] != -57 > + || g_1731[6] != 42) > + __builtin_abort (); > + return 0; > +} > diff --git a/gcc/testsuite/gcc.dg/torture/pr115869-2.c > b/gcc/testsuite/gcc.dg/torture/pr115869-2.c > new file mode 100644 > index 000000000000..2f9d6b0b21d9 > --- /dev/null > +++ b/gcc/testsuite/gcc.dg/torture/pr115869-2.c > @@ -0,0 +1,40 @@ > +/* PR tree-optimization/115869 */ > +/* { dg-do run } */ > +/* { dg-additional-options "-floop-unroll-and-jam" } */ > + > +struct st { unsigned v[4]; }; > + > +__attribute__((noipa)) void > +f (struct st *p, int m, int n, int d, int j) > +{ > + for (int i = 0; i < m; i++) > + for (int k = 0; k + d < n; k++) > + p[k + d].v[j] = p[k + d].v[j] * 3 + p[k].v[j] + (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 k = 0; k < 16; k++) > + { > + for (int e = 0; e < 4; e++) > + p[k].v[e] = (unsigned) (k * 4 + e); > + q[k] = p[k].v[2]; > + } > + f (p, 8, 16, 1, 2); > + g (q, 8, 16, 1); > + for (int k = 0; k < 16; k++) > + if (p[k].v[2] != q[k]) > + __builtin_abort (); > + return 0; > +} > diff --git a/gcc/testsuite/gcc.dg/torture/pr115869-3.c > b/gcc/testsuite/gcc.dg/torture/pr115869-3.c > new file mode 100644 > index 000000000000..9f185c7083c1 > --- /dev/null > +++ b/gcc/testsuite/gcc.dg/torture/pr115869-3.c > @@ -0,0 +1,33 @@ > +/* PR tree-optimization/115869 */ > +/* { dg-do run } */ > +/* { dg-require-effective-target int32plus } */ > +/* { dg-additional-options "-floop-interchange" } */ > + > +unsigned a[16]; > +unsigned B[8][1024]; > + > +void __attribute__((noipa)) > +foo (int nf, int ni, int nj) > +{ > + 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]; > +} > + > +int > +main () > +{ > + for (int i = 0; i < 8; i++) > + for (int x = 0; x < 1024; x++) > + B[i][x] = x * 7 + i * 13 + 1; > + for (int x = 0; x < 16; x++) > + a[x] = x; > + foo (2, 2, 2); > + unsigned s = 0; > + for (int x = 0; x < 16; x++) > + s = s * 31 + a[x]; > + if (s != 2738069132u) > + __builtin_abort (); > + return 0; > +} > diff --git a/gcc/testsuite/gcc.dg/torture/pr115869-5.c > b/gcc/testsuite/gcc.dg/torture/pr115869-5.c > new file mode 100644 > index 000000000000..ac483c40ae9b > --- /dev/null > +++ b/gcc/testsuite/gcc.dg/torture/pr115869-5.c > @@ -0,0 +1,33 @@ > +/* PR tree-optimization/115869 */ > +/* { dg-do run } */ > +/* { dg-require-effective-target int32plus } */ > +/* { dg-additional-options "-floop-interchange -fno-loop-unroll-and-jam" } */ > + > +unsigned a[64]; > +unsigned B[64][64]; > + > +void __attribute__((noipa)) > +foo (int ni, int nj, int nk) > +{ > + for (int i = 0; i < ni; i++) > + for (int j = 0; j < nj; j++) > + for (int k = 0; k < nk; k++) > + a[i + k] = a[i + k] * 3 + B[j][i]; > +} > + > +int > +main () > +{ > + for (int j = 0; j < 64; j++) > + for (int i = 0; i < 64; i++) > + B[j][i] = i * 7 + j * 13 + 1; > + for (int x = 0; x < 64; x++) > + a[x] = x; > + foo (2, 2, 2); > + unsigned s = 0; > + for (int x = 0; x < 64; x++) > + s = s * 31 + a[x]; > + if (s != 3050518888u) > + __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; > +} > diff --git a/gcc/testsuite/gcc.dg/torture/pr120254.c > b/gcc/testsuite/gcc.dg/torture/pr120254.c > new file mode 100644 > index 000000000000..c6176ab34c7c > --- /dev/null > +++ b/gcc/testsuite/gcc.dg/torture/pr120254.c > @@ -0,0 +1,30 @@ > +/* PR tree-optimization/120254 */ > +/* { dg-do run } */ > +/* { dg-require-effective-target int32plus } */ > + > +#define N 30 > + > +unsigned A[N][N][N]; > + > +int > +main () > +{ > + for (int i = 0; i < N; i++) > + for (int j = 0; j < N; j++) > + for (int k = 0; k < N; k++) > + A[i][j][k] = i + j + k; > + > + for (int i = 0; i < N - 1; i++) > + for (int j = 0; j < N; j++) > + for (int k = 0; k < N - 1; k++) > + A[k + 1][i][i] += A[k + 1][i][i + 1] - A[k][i][i] - 6; > + > + unsigned sum = 0; > + for (int i = 0; i < N; i++) > + for (int j = 0; j < N; j++) > + for (int k = 0; k < N; k++) > + sum += A[i][j][k]; > + if (sum != 2337195900u) > + __builtin_abort (); > + return 0; > +} > diff --git a/gcc/tree-data-ref.cc b/gcc/tree-data-ref.cc > index 31d324cb3abd..9112b3469aef 100644 > --- a/gcc/tree-data-ref.cc > +++ b/gcc/tree-data-ref.cc > @@ -5698,6 +5698,136 @@ subscript_dependence_tester_1 (struct > data_dependence_relation *ddr, > return false; > } > > +/* Return true if every distance vector of DDR has, in the loops marked in > + VARIES, the distances of the first vector or all of them negated. */ > + > +static bool > +dist_vectors_agree_p (const struct data_dependence_relation *ddr, > + const vec<bool> &varies) > +{ > + if (DDR_NUM_DIST_VECTS (ddr) == 0) > + return true; > + lambda_vector first = DDR_DIST_VECT (ddr, 0); > + for (lambda_vector v : DDR_DIST_VECTS (ddr)) > + { > + bool same = true, opposite = true; > + for (unsigned i = 0; i < DDR_NB_LOOPS (ddr); i++) > + if (varies[i]) > + { > + same &= v[i] == first[i]; > + opposite &= v[i] == -first[i]; > + } > + if (!same && !opposite) > + return false; > + } > + return true; > +} > + > +/* Return true if the distance vectors of DDR miss distances because of a > + free loop, a loop of the nest that contains both references and in > + which no compared access function evolves, so that the dependence can > + have any distance in it. The vectors give a free loop a distance of > + its own only when it is the only free loop and lies outside every loop > + the subscripts constrain, and the vectors agree in the loops the > + subscripts constrain. Otherwise its distance is taken as zero, which > + misses the distances of opposite signs in it and in another free loop > + or in a loop with a nonzero distance. Set FREE_LOOPS[I] when loop I of > + the nest is free and VARIES[I] when a compared access function evolves > + in it. */ > + > +static bool > +free_loop_distances_lost_p (const struct data_dependence_relation *ddr, > + vec<bool> *free_loops, vec<bool> *varies) > +{ > + unsigned n = DDR_NB_LOOPS (ddr); > + if (n < 2) > + return false; > + free_loops->safe_grow_cleared (n); > + > + varies->safe_grow_cleared (n); I think we want to use quick_grow_cleared here and have the caller allocate it with (*) > + for (subscript *sub : DDR_SUBSCRIPTS (ddr)) > + for (unsigned k = 0; k < 2; k++) > + for (unsigned i = 0; i < n; i++) > + if (evolution_part_in_loop_num (SUB_ACCESS_FN (sub, k), > + DDR_LOOP_NEST (ddr)[i]->num)) This is a bit inefficient given we walk the whole CHREC N times via chrec_component_in_loop_num. We might want to expose the core walker in chrec_component_in_loop_num with a callback called on each (sub-)CHREC visited to avoid the quadraticness. > + (*varies)[i] = true; > + > + basic_block bb_a = gimple_bb (DR_STMT (DDR_A (ddr))); > + basic_block bb_b = gimple_bb (DR_STMT (DDR_B (ddr))); > + unsigned first_varying = n, nfree = 0, free_idx = 0; > + for (unsigned i = 0; i < n; i++) > + if ((*varies)[i]) > + first_varying = MIN (first_varying, i); > + else if (flow_bb_inside_loop_p (DDR_LOOP_NEST (ddr)[i], bb_a) > + && flow_bb_inside_loop_p (DDR_LOOP_NEST (ddr)[i], bb_b)) > + { > + nfree++; > + free_idx = i; > + (*free_loops)[i] = true; > + } > + if (nfree == 0) > + return false; > + if (!dist_vectors_agree_p (ddr, *varies)) > + return true; > + if (nfree == 1 && free_idx < first_varying) > + return false; > + if (nfree > 1) > + return true; > + > + unsigned j; > + lambda_vector v; > + FOR_EACH_VEC_ELT (DDR_DIST_VECTS (ddr), j, v) > + for (unsigned i = 0; i < n; i++) > + if ((*varies)[i] && v[i] != 0) > + return true; > + return false; > +} > + > +/* Add the distance vectors of DDR that its free loops FREE_LOOPS miss: > + every lexicographically positive vector with the distances of the first > + vector, or their opposite, in the other loops and -1, 0 or 1 in each > + free loop. That is not possible when the bases differ and the objects > + vary in the nest, or when the vectors do not agree in the loops VARIES > + marks; return false then, when there is no vector to start from, or when > + more than 32 vectors would be needed. */ > + > +static bool > +add_free_loop_distances (struct data_dependence_relation *ddr, > + const vec<bool> &free_loops, const vec<bool> &varies) > +{ > + if ((DDR_COULD_BE_INDEPENDENT_P (ddr) && !DDR_OBJECT_A (ddr)) > + || DDR_NUM_DIST_VECTS (ddr) == 0 > + || !dist_vectors_agree_p (ddr, varies)) > + return false; > + unsigned n = DDR_NB_LOOPS (ddr), nfree = 0, ncomb = 1; > + for (bool f : free_loops) > + if (f) > + { > + nfree++; > + ncomb *= 3; > + } > + if (nfree > 3) > + return false; > + > + lambda_vector first = DDR_DIST_VECT (ddr, 0); > + for (int sign = 1; sign >= -1; sign -= 2) > + for (unsigned c = 0; c < ncomb; c++) > + { > + lambda_vector v = lambda_vector_new (n); > + for (unsigned i = 0, rest = c; i < n; i++) > + if (free_loops[i]) > + { > + v[i] = (int) (rest % 3) - 1; > + rest /= 3; > + } > + else > + v[i] = sign * first[i]; > + if (lambda_vector_lexico_pos (v, n)) > + save_dist_v (ddr, v); > + } > + return DDR_NUM_DIST_VECTS (ddr) <= 32; Hmm, so why push them all when we are going to throw the result away? > +} > + > /* Computes the conflicting iterations in LOOP_NEST, and initialize DDR. */ > > static void > @@ -5710,6 +5840,17 @@ subscript_dependence_tester (struct > data_dependence_relation *ddr, > compute_subscript_distance (ddr); > if (build_classic_dist_vector (ddr, loop_nest)) > { > + auto_vec<bool, 8> free_loops, varies; (*) free_loops (n), varies (n) which should be more efficient. > + if (free_loop_distances_lost_p (ddr, &free_loops, &varies) > + && !add_free_loop_distances (ddr, free_loops, varies)) This ends up calling dist_vectors_agree_p twice, we might be able to improve on this by returning this from free_loop_distances_lost_p in some way (with a tri-state return?) Otherwise thanks for working on this. Richard. > + { > + if (dump_file && (dump_flags & TDF_DETAILS)) > + fprintf (dump_file, "(distance vectors miss a free loop)\n"); > + DDR_ARE_DEPENDENT (ddr) = chrec_dont_know; > + DDR_DIST_VECTS (ddr).release (); > + return; > + } > + > if (dump_file && (dump_flags & TDF_DETAILS)) > { > unsigned i; > -- Richard Biener <[email protected]> SUSE Software Solutions Germany GmbH, Frankenstrasse 146, 90461 Nuernberg, Germany; GF: Stefan Gaiser, Jochen Jaser, Abhinav Puri; (HRB 36809, AG Nuernberg)
