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.
(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);
+ 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))
+ (*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;
+}
+
/* 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;
+ if (free_loop_distances_lost_p (ddr, &free_loops, &varies)
+ && !add_free_loop_distances (ddr, free_loops, varies))
+ {
+ 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;
