[PATCH]: Fix PR tree-optimization/18792
Daniel Berlin
dberlin@dberlin.org
Thu Dec 9 00:00:00 GMT 2004
It turns out we can't depend on loop index numbers being in any particular
order.
When it didn't happen, like the testcase in 18792,
This fixes it to use loop depth as the index into the distance and
direction vectors when building them, as well as fixing the parts of
tree-loop-linear that indexed into those arrays
This should work, as the function already assumes there are no sibling
loops in the nest, etc.
Bootstrapped and regtested on i686-pc-linux-gnu.
Okay for mainline?
2004-12-07 Daniel Berlin <dberlin@dberlin.org>
Fix PR tree-optimization/18792
* tree-data-ref.c (build_classic_dist_vector): Change first_loop
to first_loop_depth, and use loop depth instead of loop number.
(build_classic_dir_vector): Ditto.
(compute_data_dependences_for_loop): Use depth, not loop number.
* tree-loop-linear.c (try_interchange_loops): Use loop depth, not loop
number. Pass in loops, instead of loop numbers.
(gather_interchange_stats): Ditto.
(linear_transform_loops): Ditto.
Index: tree-data-ref.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/tree-data-ref.c,v
retrieving revision 2.17
diff -u -p -r2.17 tree-data-ref.c
--- tree-data-ref.c 12 Nov 2004 00:13:06 -0000 2.17
+++ tree-data-ref.c 8 Dec 2004 23:54:05 -0000
@@ -1781,15 +1781,15 @@ subscript_dependence_tester (struct data
DDR is the data dependence relation to build a vector from.
NB_LOOPS is the total number of loops we are considering.
- FIRST_LOOP is the loop->num of the first loop in the analyzed
+ FIRST_LOOP_DEPTH is the loop->depth of the first loop in the analyzed
loop nest.
Return FALSE if the dependence relation is outside of the loop nest
- starting with FIRST_LOOP.
+ starting at FIRST_LOOP_DEPTH.
Return TRUE otherwise. */
static bool
build_classic_dist_vector (struct data_dependence_relation *ddr,
- int nb_loops, unsigned int first_loop)
+ int nb_loops, int first_loop_depth)
{
unsigned i;
lambda_vector dist_v, init_v;
@@ -1824,14 +1824,13 @@ build_classic_dist_vector (struct data_d
int loop_nb_b = CHREC_VARIABLE (access_fn_b);
struct loop *loop_a = current_loops->parray[loop_nb_a];
struct loop *loop_b = current_loops->parray[loop_nb_b];
- struct loop *loop_first = current_loops->parray[first_loop];
/* If the loop for either variable is at a lower depth than
the first_loop's depth, then we can't possibly have a
dependency at this level of the loop. */
- if (loop_a->depth < loop_first->depth
- || loop_b->depth < loop_first->depth)
+ if (loop_a->depth < first_loop_depth
+ || loop_b->depth < first_loop_depth)
return false;
if (loop_nb_a != loop_nb_b
@@ -1862,7 +1861,7 @@ build_classic_dist_vector (struct data_d
| endloop_1
In this case, the dependence is carried by loop_1. */
loop_nb = loop_nb_a < loop_nb_b ? loop_nb_a : loop_nb_b;
- loop_nb -= first_loop;
+ loop_nb = current_loops->parray[loop_nb]->depth - first_loop_depth;
/* If the loop number is still greater than the number of
loops we've been asked to analyze, or negative,
@@ -1913,8 +1912,8 @@ build_classic_dist_vector (struct data_d
/* Get the common ancestor loop. */
lca = find_common_loop (loop_a, loop_b);
- lca_nb = lca->num;
- lca_nb -= first_loop;
+ lca_nb = lca->depth;
+ lca_nb -= first_loop_depth;
gcc_assert (lca_nb >= 0);
gcc_assert (lca_nb < nb_loops);
@@ -1929,7 +1928,7 @@ build_classic_dist_vector (struct data_d
if (lca)
{
- lca_nb = lca->num - first_loop;
+ lca_nb = lca->depth - first_loop_depth;
while (lca->depth != 0)
{
/* If we're considering just a sub-nest, then don't record
@@ -1942,7 +1941,7 @@ build_classic_dist_vector (struct data_d
if (init_v[lca_nb] == 0)
dist_v[lca_nb] = 1;
lca = lca->outer;
- lca_nb = lca->num - first_loop;
+ lca_nb = lca->depth - first_loop_depth;
}
}
@@ -1957,15 +1956,15 @@ build_classic_dist_vector (struct data_d
DDR is the data dependence relation to build a vector from.
NB_LOOPS is the total number of loops we are considering.
- FIRST_LOOP is the loop->num of the first loop in the analyzed
+ FIRST_LOOP_DEPTH is the loop->depth of the first loop in the analyzed
loop nest.
Return FALSE if the dependence relation is outside of the loop nest
- starting with FIRST_LOOP.
+ at FIRST_LOOP_DEPTH.
Return TRUE otherwise. */
static bool
build_classic_dir_vector (struct data_dependence_relation *ddr,
- int nb_loops, unsigned int first_loop)
+ int nb_loops, int first_loop_depth)
{
unsigned i;
lambda_vector dir_v, init_v;
@@ -2000,14 +1999,13 @@ build_classic_dir_vector (struct data_de
int loop_nb_b = CHREC_VARIABLE (access_fn_b);
struct loop *loop_a = current_loops->parray[loop_nb_a];
struct loop *loop_b = current_loops->parray[loop_nb_b];
- struct loop *loop_first = current_loops->parray[first_loop];
/* If the loop for either variable is at a lower depth than
the first_loop's depth, then we can't possibly have a
dependency at this level of the loop. */
- if (loop_a->depth < loop_first->depth
- || loop_b->depth < loop_first->depth)
+ if (loop_a->depth < first_loop_depth
+ || loop_b->depth < first_loop_depth)
return false;
if (loop_nb_a != loop_nb_b
@@ -2038,7 +2036,7 @@ build_classic_dir_vector (struct data_de
| endloop_1
In this case, the dependence is carried by loop_1. */
loop_nb = loop_nb_a < loop_nb_b ? loop_nb_a : loop_nb_b;
- loop_nb -= first_loop;
+ loop_nb = current_loops->parray[loop_nb]->depth - first_loop_depth;
/* If the loop number is still greater than the number of
loops we've been asked to analyze, or negative,
@@ -2098,7 +2096,7 @@ build_classic_dir_vector (struct data_de
/* Get the common ancestor loop. */
lca = find_common_loop (loop_a, loop_b);
- lca_nb = lca->num - first_loop;
+ lca_nb = lca->depth - first_loop_depth;
gcc_assert (lca_nb >= 0);
gcc_assert (lca_nb < nb_loops);
@@ -2113,7 +2111,7 @@ build_classic_dir_vector (struct data_de
lca = lca->outer;
if (lca)
{
- lca_nb = lca->num - first_loop;
+ lca_nb = lca->depth - first_loop_depth;
while (lca->depth != 0)
{
/* If we're considering just a sub-nest, then don't record
@@ -2126,7 +2124,7 @@ build_classic_dir_vector (struct data_de
if (init_v[lca_nb] == 0)
dir_v[lca_nb] = dir_positive;
lca = lca->outer;
- lca_nb = lca->num - first_loop;
+ lca_nb = lca->depth - first_loop_depth;
}
}
@@ -2330,8 +2328,8 @@ compute_data_dependences_for_loop (unsig
chrec_dont_know. */
ddr = initialize_data_dependence_relation (NULL, NULL);
VARRAY_PUSH_GENERIC_PTR (*dependence_relations, ddr);
- build_classic_dist_vector (ddr, nb_loops, loop->num);
- build_classic_dir_vector (ddr, nb_loops, loop->num);
+ build_classic_dist_vector (ddr, nb_loops, loop->depth);
+ build_classic_dir_vector (ddr, nb_loops, loop->depth);
return;
}
@@ -2342,10 +2340,10 @@ compute_data_dependences_for_loop (unsig
{
struct data_dependence_relation *ddr;
ddr = VARRAY_GENERIC_PTR (allrelations, i);
- if (build_classic_dist_vector (ddr, nb_loops, loop->num))
+ if (build_classic_dist_vector (ddr, nb_loops, loop->depth))
{
VARRAY_PUSH_GENERIC_PTR (*dependence_relations, ddr);
- build_classic_dir_vector (ddr, nb_loops, loop->num);
+ build_classic_dir_vector (ddr, nb_loops, loop->depth);
}
}
}
Index: tree-loop-linear.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/tree-loop-linear.c,v
retrieving revision 2.4
diff -u -p -r2.4 tree-loop-linear.c
--- tree-loop-linear.c 3 Nov 2004 17:32:34 -0000 2.4
+++ tree-loop-linear.c 8 Dec 2004 23:54:05 -0000
@@ -55,19 +55,19 @@ Software Foundation, 59 Temple Place - S
transform matrix for locality purposes.
TODO: Completion of partial transforms. */
-/* Gather statistics for loop interchange. LOOP_NUMBER is a relative
- index in the considered loop nest. The first loop in the
- considered loop nest is FIRST_LOOP, and consequently the index of
- the considered loop is obtained by FIRST_LOOP + LOOP_NUMBER.
+/* Gather statistics for loop interchange. LOOP is the loop being
+ considered. The first loop in the considered loop nest is
+ FIRST_LOOP, and consequently, the index of the considered loop is
+ obtained by LOOP->DEPTH - FIRST_LOOP->DEPTH
Initializes:
- DEPENDENCE_STEPS the sum of all the data dependence distances
- carried by loop LOOP_NUMBER,
+ carried by loop LOOP,
- NB_DEPS_NOT_CARRIED_BY_LOOP the number of dependence relations
- for which the loop LOOP_NUMBER is not carrying any dependence,
+ for which the loop LOOP is not carrying any dependence,
- - ACCESS_STRIDES the sum of all the strides in LOOP_NUMBER.
+ - ACCESS_STRIDES the sum of all the strides in LOOP.
Example: for the following loop,
@@ -93,8 +93,8 @@ Software Foundation, 59 Temple Place - S
static void
gather_interchange_stats (varray_type dependence_relations,
varray_type datarefs,
- unsigned int loop_number,
- unsigned int first_loop,
+ struct loop *loop,
+ struct loop *first_loop,
unsigned int *dependence_steps,
unsigned int *nb_deps_not_carried_by_loop,
unsigned int *access_strides)
@@ -123,7 +123,7 @@ gather_interchange_stats (varray_type de
- dist = DDR_DIST_VECT (ddr)[loop_number];
+ dist = DDR_DIST_VECT (ddr)[loop->depth - first_loop->depth];
if (dist == 0)
(*nb_deps_not_carried_by_loop) += 1;
else if (dist < 0)
@@ -139,17 +139,16 @@ gather_interchange_stats (varray_type de
struct data_reference *dr = VARRAY_GENERIC_PTR (datarefs, i);
tree stmt = DR_STMT (dr);
struct loop *stmt_loop = loop_containing_stmt (stmt);
- struct loop *inner_loop = current_loops->parray[first_loop + 1];
-
- if (!flow_loop_nested_p (inner_loop, stmt_loop)
- && inner_loop->num != stmt_loop->num)
+ struct loop *inner_loop = first_loop->inner;
+
+ if (inner_loop != stmt_loop
+ && !flow_loop_nested_p (inner_loop, stmt_loop))
continue;
-
for (it = 0; it < DR_NUM_DIMENSIONS (dr); it++)
{
tree chrec = DR_ACCESS_FN (dr, it);
tree tstride = evolution_part_in_loop_num
- (chrec, first_loop + loop_number);
+ (chrec, loop->num);
if (tstride == NULL_TREE
|| TREE_CODE (tstride) != INTEGER_CST)
@@ -173,9 +172,10 @@ try_interchange_loops (lambda_trans_matr
unsigned int depth,
varray_type dependence_relations,
varray_type datarefs,
- unsigned int first_loop)
+ struct loop *first_loop)
{
- unsigned int loop_i, loop_j;
+ struct loop *loop_i;
+ struct loop *loop_j;
unsigned int dependence_steps_i, dependence_steps_j;
unsigned int access_strides_i, access_strides_j;
unsigned int nb_deps_not_carried_by_i, nb_deps_not_carried_by_j;
@@ -189,8 +189,12 @@ try_interchange_loops (lambda_trans_matr
return trans;
/* LOOP_I is always the outer loop. */
- for (loop_j = 1; loop_j < depth; loop_j++)
- for (loop_i = 0; loop_i < loop_j; loop_i++)
+ for (loop_j = first_loop->inner;
+ loop_j;
+ loop_j = loop_j->inner)
+ for (loop_i = first_loop;
+ loop_i->depth < loop_j->depth;
+ loop_i = loop_i->inner)
{
gather_interchange_stats (dependence_relations, datarefs,
loop_i, first_loop,
@@ -218,11 +222,15 @@ try_interchange_loops (lambda_trans_matr
|| nb_deps_not_carried_by_i > nb_deps_not_carried_by_j
|| access_strides_i < access_strides_j)
{
- lambda_matrix_row_exchange (LTM_MATRIX (trans), loop_i, loop_j);
+ lambda_matrix_row_exchange (LTM_MATRIX (trans),
+ loop_i->depth - first_loop->depth,
+ loop_j->depth - first_loop->depth);
/* Validate the resulting matrix. When the transformation
is not valid, reverse to the previous transformation. */
if (!lambda_transform_legal_p (trans, depth, dependence_relations))
- lambda_matrix_row_exchange (LTM_MATRIX (trans), loop_i, loop_j);
+ lambda_matrix_row_exchange (LTM_MATRIX (trans),
+ loop_i->depth - first_loop->depth,
+ loop_j->depth - first_loop->depth);
}
}
@@ -318,7 +326,7 @@ linear_transform_loops (struct loops *lo
lambda_matrix_id (LTM_MATRIX (trans), depth);
trans = try_interchange_loops (trans, depth, dependence_relations,
- datarefs, loop_nest->num);
+ datarefs, loop_nest);
if (lambda_trans_matrix_id_p (trans))
{
Index: testsuite/gcc.dg/pr18792.c
===================================================================
RCS file: testsuite/gcc.dg/pr18792.c
diff -N testsuite/gcc.dg/pr18792.c
--- /dev/null 1 Jan 1970 00:00:00 -0000
+++ testsuite/gcc.dg/pr18792.c 8 Dec 2004 23:57:35 -0000
@@ -0,0 +1,19 @@
+/* PR tree-optimization/18792 */
+/* { dg-do compile } */
+/* { dg-options "-O1 -ftree-loop-linear" } */
+void put_atoms_in_triclinic_unitcell(float x[][3])
+{
+ int i=0,d;
+
+ while (x[i][3] < 0)
+ for (d=0; d<=3; d++)
+ x[i][d] = 0;
+
+ while (x[i][3] >= 0)
+ for (d=0; d<=3; d++)
+ x[i][d] = 0;
+
+}
+
+
+
More information about the Gcc-patches
mailing list