https://gcc.gnu.org/g:99126c684223cabab03e41e806616160b4058f73
commit r17-5774-g99126c684223cabab03e41e806616160b4058f73 Author: Rohith Kapelli <[email protected]> Date: Fri Oct 16 00:58:52 2026 +0530 tree-optimization/115869 - complete or drop the distance vectors of free loops 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. 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. (mark_evolving_loops): Likewise. (enum free_loop_distances): New. (check_free_loop_distances): New function. (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]> Diff: --- 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 | 181 ++++++++++++++++++++++++++++++ 8 files changed, 407 insertions(+) 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 c1614420c87d..edcc146c07de 100644 --- a/gcc/tree-data-ref.cc +++ b/gcc/tree-data-ref.cc @@ -5744,6 +5744,172 @@ 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; +} + +/* Set VARIES[I] for each loop I of the nest of DDR in which CHREC has an + evolution part, as evolution_part_in_loop_num finds it, walking CHREC + once. The nest is a chain of loops at consecutive depths, as + find_loop_nest builds it, so loop I is at the depth of loop 0 plus I. */ + +static void +mark_evolving_loops (const struct data_dependence_relation *ddr, tree chrec, + vec<bool> *varies) +{ + unsigned n = DDR_NB_LOOPS (ddr); + if (automatically_generated_chrec_p (chrec)) + for (unsigned i = 0; i < n; i++) + (*varies)[i] = true; + unsigned depth0 = loop_depth (DDR_LOOP_NEST (ddr)[0]); + for (; TREE_CODE (chrec) == POLYNOMIAL_CHREC; chrec = CHREC_LEFT (chrec)) + { + class loop *loop = get_chrec_loop (chrec); + unsigned i = loop_depth (loop) - depth0; + if (i < n && DDR_LOOP_NEST (ddr)[i] == loop) + (*varies)[i] = true; + } +} + +/* What the distance vectors of a dependence miss in its free loops. */ + +enum free_loop_distances +{ + /* They miss nothing. */ + FREE_LOOP_DISTANCES_KEPT, + /* They miss distances, and agree in the loops the subscripts constrain, + so they can be completed. */ + FREE_LOOP_DISTANCES_LOST, + /* They miss distances and do not agree there. */ + FREE_LOOP_DISTANCES_DISAGREE +}; + +/* Return whether 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; both have room for DDR_NB_LOOPS (DDR) elements. */ + +static enum free_loop_distances +check_free_loop_distances (const struct data_dependence_relation *ddr, + vec<bool> *free_loops, vec<bool> *varies) +{ + unsigned n = DDR_NB_LOOPS (ddr); + if (n < 2) + return FREE_LOOP_DISTANCES_KEPT; + free_loops->quick_grow_cleared (n); + + varies->quick_grow_cleared (n); + for (subscript *sub : DDR_SUBSCRIPTS (ddr)) + for (unsigned k = 0; k < 2; k++) + mark_evolving_loops (ddr, SUB_ACCESS_FN (sub, k), varies); + + 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 FREE_LOOP_DISTANCES_KEPT; + if (!dist_vectors_agree_p (ddr, *varies)) + return FREE_LOOP_DISTANCES_DISAGREE; + if (nfree == 1 && free_idx < first_varying) + return FREE_LOOP_DISTANCES_KEPT; + if (nfree > 1) + return FREE_LOOP_DISTANCES_LOST; + + 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 FREE_LOOP_DISTANCES_LOST; + return FREE_LOOP_DISTANCES_KEPT; +} + +/* Add the distance vectors of DDR that its free loops FREE_LOOPS miss, + when its vectors agree in the loops the subscripts constrain: 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; return false then, when there is no vector to start + from, or as soon as more than 32 vectors would be needed. */ + +static bool +add_free_loop_distances (struct data_dependence_relation *ddr, + const vec<bool> &free_loops) +{ + if ((DDR_COULD_BE_INDEPENDENT_P (ddr) && !DDR_OBJECT_A (ddr)) + || DDR_NUM_DIST_VECTS (ddr) == 0) + 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); + if (DDR_NUM_DIST_VECTS (ddr) > 32) + return false; + } + } + return true; +} + /* Computes the conflicting iterations in LOOP_NEST, and initialize DDR. */ static void @@ -5756,6 +5922,21 @@ subscript_dependence_tester (struct data_dependence_relation *ddr, compute_subscript_distance (ddr); if (build_classic_dist_vector (ddr, loop_nest)) { + unsigned n = DDR_NB_LOOPS (ddr); + auto_vec<bool, 8> free_loops (n), varies (n); + enum free_loop_distances lost + = check_free_loop_distances (ddr, &free_loops, &varies); + if (lost == FREE_LOOP_DISTANCES_DISAGREE + || (lost == FREE_LOOP_DISTANCES_LOST + && !add_free_loop_distances (ddr, free_loops))) + { + 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;
