Hi,
this was still collecting dust on my disk, so here it is. See the
extensive comment in the patch for what happens, in short invariant IVs
are affine but still have to be handled more conservative than other
affine IVs in transformations that reorder instructions. Making our
dependence analysis more conservative instead would be too much, we
wouldn't be able to handle cases that we should handle anymore.
Regstrapped on x86-64-linux without regressions (all languages+Ada).
Ciao,
Michael.
PR middle-end/90796
* gimple-loop-jam.c (any_access_function_variant_p): New function.
(adjust_unroll_factor): Use it to constrain safety, new parameter.
(tree_loop_unroll_and_jam): Adjust call and profitable unroll factor.
testsuite/
* gcc.dg/unroll-and-jam.c: Add three invalid and one valid case.
diff --git a/gcc/gimple-loop-jam.c b/gcc/gimple-loop-jam.c
index 11153f5..899653b 100644
--- a/gcc/gimple-loop-jam.c
+++ b/gcc/gimple-loop-jam.c
@@ -360,16 +360,33 @@ fuse_loops (class loop *loop)
rewrite_into_loop_closed_ssa_1 (NULL, 0, SSA_OP_USE, loop);
}
+/* Return true if any of the access functions for dataref A
+ isn't invariant with respect to loop LOOP_NEST. */
+static bool
+any_access_function_variant_p (const struct data_reference *a,
+ const class loop *loop_nest)
+{
+ unsigned int i;
+ vec<tree> fns = DR_ACCESS_FNS (a);
+ tree t;
+
+ FOR_EACH_VEC_ELT (fns, i, t)
+ if (!evolution_function_is_invariant_p (t, loop_nest->num))
+ return true;
+
+ return false;
+}
+
/* Returns true if the distance in DDR can be determined and adjusts
the unroll factor in *UNROLL to make unrolling valid for that distance.
- Otherwise return false.
+ Otherwise return false. DDR is with respect to the outer loop of INNER.
If this data dep can lead to a removed memory reference, increment
*REMOVED and adjust *PROFIT_UNROLL to be the necessary unroll factor
for this to happen. */
static bool
-adjust_unroll_factor (struct data_dependence_relation *ddr,
+adjust_unroll_factor (class loop *inner, struct data_dependence_relation *ddr,
unsigned *unroll, unsigned *profit_unroll,
unsigned *removed)
{
@@ -392,9 +409,59 @@ adjust_unroll_factor (struct data_dependence_relation *ddr,
gcc_unreachable ();
else if ((unsigned)dist >= *unroll)
;
- else if (lambda_vector_lexico_pos (dist_v + 1, DDR_NB_LOOPS (ddr) - 1)
- || (lambda_vector_zerop (dist_v + 1, DDR_NB_LOOPS (ddr) - 1)
- && dist > 0))
+ else if (lambda_vector_zerop (dist_v + 1, DDR_NB_LOOPS (ddr) - 1))
+ {
+ /* We have (a,0) with a < N, so this will be transformed into
+ (0,0) after unrolling by N. This might potentially be a
+ problem, if it's not a read-read dependency. */
+ if (DR_IS_READ (DDR_A (ddr)) && DR_IS_READ (DDR_B (ddr)))
+ ;
+ else
+ {
+ /* So, at least one is a write, and we might reduce the
+ distance vector to (0,0). This is still no problem
+ if both data-refs are affine with respect to the inner
+ loops. But if one of them is invariant with respect
+ to an inner loop our reordering implicit in loop fusion
+ corrupts the program, as our data dependences don't
+ capture this. E.g. for:
+ for (0 <= i < n)
+ for (0 <= j < m)
+ a[i][0] = a[i+1][0] + 2; // (1)
+ b[i][j] = b[i+1][j] + 2; // (2)
+ the distance vector for both statements is (-1,0),
+ but exchanging the order for (2) is okay, while
+ for (1) it is not. To see this, write out the original
+ accesses (assume m is 2):
+ a i j original
+ 0 0 0 r a[1][0] b[1][0]
+ 1 0 0 w a[0][0] b[0][0]
+ 2 0 1 r a[1][0] b[1][1]
+ 3 0 1 w a[0][0] b[0][1]
+ 4 1 0 r a[2][0] b[2][0]
+ 5 1 0 w a[1][0] b[1][0]
+ after unroll-by-2 and fusion the accesses are done in
+ this order (from column a): 0,1, 4,5, 2,3, i.e. this:
+ a i j transformed
+ 0 0 0 r a[1][0] b[1][0]
+ 1 0 0 w a[0][0] b[0][0]
+ 4 1 0 r a[2][0] b[2][0]
+ 5 1 0 w a[1][0] b[1][0]
+ 2 0 1 r a[1][0] b[1][1]
+ 3 0 1 w a[0][0] b[0][1]
+ Note how access 2 accesses the same element as access 5
+ for array 'a' but not for array 'b'. */
+ if (any_access_function_variant_p (DDR_A (ddr), inner)
+ && any_access_function_variant_p (DDR_B (ddr), inner))
+ ;
+ else
+ /* And if any dataref of this pair is invariant with
+ respect to the inner loop, we have no chance than
+ to reduce the unroll factor. */
+ *unroll = dist;
+ }
+ }
+ else if (lambda_vector_lexico_pos (dist_v + 1, DDR_NB_LOOPS (ddr) -
1))
;
else
*unroll = dist;
@@ -486,7 +553,7 @@ tree_loop_unroll_and_jam (void)
/* Now check the distance vector, for determining a sensible
outer unroll factor, and for validity of merging the inner
loop copies. */
- if (!adjust_unroll_factor (ddr, &unroll_factor, &profit_unroll,
+ if (!adjust_unroll_factor (loop, ddr, &unroll_factor, &profit_unroll,
&removed))
{
/* Couldn't get the distance vector. For two reads that's
@@ -506,7 +573,7 @@ tree_loop_unroll_and_jam (void)
to ignore all profitability concerns and apply the transformation
always. */
if (!PARAM_VALUE (PARAM_UNROLL_JAM_MIN_PERCENT))
- profit_unroll = 2;
+ profit_unroll = MAX(2, profit_unroll);
else if (removed * 100 / datarefs.length ()
< (unsigned)PARAM_VALUE (PARAM_UNROLL_JAM_MIN_PERCENT))
profit_unroll = 1;
diff --git a/gcc/testsuite/gcc.dg/unroll-and-jam.c
b/gcc/testsuite/gcc.dg/unroll-and-jam.c
index 70910d3..bcfe1bd 100644
--- a/gcc/testsuite/gcc.dg/unroll-and-jam.c
+++ b/gcc/testsuite/gcc.dg/unroll-and-jam.c
@@ -31,10 +31,10 @@ void checkb(void)
//printf(" %d\n", sum);
}
+unsigned i, j;
#define TEST(name, body, test) \
static void __attribute__((noinline,noclone)) name (unsigned long n, unsigned
long m) \
{ \
- unsigned long i, j; \
for (i = 1; i < m; i++) { \
for (j = 1; j < n; j++) { \
body; \
@@ -58,9 +58,14 @@ TEST(foo3, aa[i+1][j-1]=aa[i][j] * aa[i][j] / 2, checkaa())
//notok, -1,1
TEST(foo4, aa[i][j] = aa[i-1][j+1] * aa[i-1][j+1] / 2, checkaa()) //notok, -1,1
TEST(foo5, aa[i][j] = aa[i+1][j+1] * aa[i+1][j+1] / 2, checkaa()) //ok, 1,1
TEST(foo6, aa[i][j] = aa[i+1][j] * aa[i+1][j] / 2, checkaa()) //ok, -1,0
+TEST(foo61, aa[i][0] = aa[i+1][0] * aa[i+1][0] / 2, checkaa()) //notok, -1,0
+TEST(foo62, aa[i][j/2] = aa[i+1][j/2] * aa[i+1][j/2] / 2, checkaa()) //notok,
not affine
+TEST(foo63, aa[i][j%2] = aa[i+1][j%2] * aa[i+1][j%2] / 2, checkaa()) //notok,
not affine
TEST(foo7, aa[i+1][j] = aa[i][j] * aa[i][j] / 2, checkaa()) //ok, 1,0
TEST(foo9, b[j] = 3*b[j+1] + 1, checkb()) //notok, 0,-1
TEST(foo10, b[j] = 3*b[j] + 1, checkb()) //ok, 0,0
+extern int f;
+TEST(foo11, f = b[i-1] = 1 + 3* b[i+1], checkb()) //ok, 2,0 but must reduce
unroll factor to 2, (it would be incorrect with unroll-by-3, which the
profitability would suggest)
/* foo8 should work as well, but currently doesn't because the distance
vectors we compute are too pessimistic. We compute
@@ -68,6 +73,7 @@ TEST(foo10, b[j] = 3*b[j] + 1, checkb()) //ok, 0,0
and the last one causes us to lose. */
TEST(foo8, b[j+1] = 3*b[j] + 1, checkb()) //ok, 0,1
+int f;
unsigned int a[1024];
unsigned int b[1024];
unsigned int aa[16][1024];
@@ -88,10 +94,12 @@ void init(void)
printf(" %s\n", #name); \
init();for(i=0;i<4;i++)name##noopt(32,8); checka = checksum; \
init();for(i=0;i<4;i++)name(32,8); \
+ if (checka != checksum) fail = 1; \
printf("%sok %s\n", checka != checksum ? "NOT " : "", #name);
int main()
{
+ int fail = 0;
int i;
unsigned checka;
RUN(foo1);
@@ -100,12 +108,18 @@ int main()
RUN(foo4);
RUN(foo5);
RUN(foo6);
+ RUN(foo61);
+ RUN(foo62);
+ RUN(foo63);
RUN(foo7);
RUN(foo8);
RUN(foo9);
RUN(foo10);
- return 0;
+ RUN(foo11);
+ if (fail)
+ __builtin_abort();
+ return fail;
}
-/* Five loops should be unroll-jammed (actually six, but see above). */
-/* { dg-final { scan-tree-dump-times "applying unroll and jam" 5 "unrolljam" }
} */
+/* Six loops should be unroll-jammed (actually seven, but see above). */
+/* { dg-final { scan-tree-dump-times "applying unroll and jam" 6 "unrolljam" }
} */
