This is the mail archive of the
gcc-patches@gcc.gnu.org
mailing list for the GCC project.
Re: [PATCH]: Fix PR tree-optimization/18792
Actually, i got a chance to update it in between bootstraps.
Here ya go.
2004-12-07 Daniel Berlin <dberlin@dberlin.org>
* 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.
2004-12-07 Daniel Berlin <dberlin@dberlin.org>
* 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 13 Dec 2004 16:43:32 -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;
@@ -1819,19 +1819,18 @@ build_classic_dist_vector (struct data_d
if (TREE_CODE (access_fn_a) == POLYNOMIAL_CHREC
&& TREE_CODE (access_fn_b) == POLYNOMIAL_CHREC)
{
- int dist, loop_nb;
+ int dist, loop_nb, loop_depth;
int loop_nb_a = CHREC_VARIABLE (access_fn_a);
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,13 +1861,13 @@ 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_depth = 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,
something is borked. */
- gcc_assert (loop_nb >= 0);
- gcc_assert (loop_nb < nb_loops);
+ gcc_assert (loop_depth >= 0);
+ gcc_assert (loop_depth < nb_loops);
if (chrec_contains_undetermined (SUB_DISTANCE (subscript)))
{
non_affine_dependence_relation (ddr);
@@ -1883,15 +1882,15 @@ build_classic_dist_vector (struct data_d
| ... = T[i][i]
| endloop
There is no dependence. */
- if (init_v[loop_nb] != 0
- && dist_v[loop_nb] != dist)
+ if (init_v[loop_depth] != 0
+ && dist_v[loop_depth] != dist)
{
finalize_ddr_dependent (ddr, chrec_known);
return true;
}
- dist_v[loop_nb] = dist;
- init_v[loop_nb] = 1;
+ dist_v[loop_depth] = dist;
+ init_v[loop_depth] = 1;
}
}
@@ -1906,43 +1905,43 @@ build_classic_dist_vector (struct data_d
struct loop *lca, *loop_a, *loop_b;
struct data_reference *a = DDR_A (ddr);
struct data_reference *b = DDR_B (ddr);
- int lca_nb;
+ int lca_depth;
loop_a = loop_containing_stmt (DR_STMT (a));
loop_b = loop_containing_stmt (DR_STMT (b));
/* Get the common ancestor loop. */
lca = find_common_loop (loop_a, loop_b);
- lca_nb = lca->num;
- lca_nb -= first_loop;
- gcc_assert (lca_nb >= 0);
- gcc_assert (lca_nb < nb_loops);
+ lca_depth = lca->depth;
+ lca_depth -= first_loop_depth;
+ gcc_assert (lca_depth >= 0);
+ gcc_assert (lca_depth < nb_loops);
/* For each outer loop where init_v is not set, the accesses are
in dependence of distance 1 in the loop. */
if (lca != loop_a
&& lca != loop_b
- && init_v[lca_nb] == 0)
- dist_v[lca_nb] = 1;
+ && init_v[lca_depth] == 0)
+ dist_v[lca_depth] = 1;
lca = lca->outer;
if (lca)
{
- lca_nb = lca->num - first_loop;
+ lca_depth = lca->depth - first_loop_depth;
while (lca->depth != 0)
{
/* If we're considering just a sub-nest, then don't record
any information on the outer loops. */
- if (lca_nb < 0)
+ if (lca_depth < 0)
break;
- gcc_assert (lca_nb < nb_loops);
+ gcc_assert (lca_depth < nb_loops);
- if (init_v[lca_nb] == 0)
- dist_v[lca_nb] = 1;
+ if (init_v[lca_depth] == 0)
+ dist_v[lca_depth] = 1;
lca = lca->outer;
- lca_nb = lca->num - first_loop;
+ lca_depth = 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;
@@ -1994,20 +1993,19 @@ build_classic_dir_vector (struct data_de
if (TREE_CODE (access_fn_a) == POLYNOMIAL_CHREC
&& TREE_CODE (access_fn_b) == POLYNOMIAL_CHREC)
{
- int dist, loop_nb;
+ int dist, loop_nb, loop_depth;
enum data_dependence_direction dir = dir_star;
int loop_nb_a = CHREC_VARIABLE (access_fn_a);
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,13 +2036,13 @@ 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_depth = 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,
something is borked. */
- gcc_assert (loop_nb >= 0);
- gcc_assert (loop_nb < nb_loops);
+ gcc_assert (loop_depth >= 0);
+ gcc_assert (loop_depth < nb_loops);
if (chrec_contains_undetermined (SUB_DISTANCE (subscript)))
{
@@ -2067,17 +2065,17 @@ build_classic_dir_vector (struct data_de
| ... = T[i][i]
| endloop
There is no dependence. */
- if (init_v[loop_nb] != 0
+ if (init_v[loop_depth] != 0
&& dir != dir_star
- && (enum data_dependence_direction) dir_v[loop_nb] != dir
- && (enum data_dependence_direction) dir_v[loop_nb] != dir_star)
+ && (enum data_dependence_direction) dir_v[loop_depth] != dir
+ && (enum data_dependence_direction) dir_v[loop_depth] != dir_star)
{
finalize_ddr_dependent (ddr, chrec_known);
return true;
}
- dir_v[loop_nb] = dir;
- init_v[loop_nb] = 1;
+ dir_v[loop_depth] = dir;
+ init_v[loop_depth] = 1;
}
}
@@ -2092,41 +2090,41 @@ build_classic_dir_vector (struct data_de
struct loop *lca, *loop_a, *loop_b;
struct data_reference *a = DDR_A (ddr);
struct data_reference *b = DDR_B (ddr);
- int lca_nb;
+ int lca_depth;
loop_a = loop_containing_stmt (DR_STMT (a));
loop_b = loop_containing_stmt (DR_STMT (b));
/* Get the common ancestor loop. */
lca = find_common_loop (loop_a, loop_b);
- lca_nb = lca->num - first_loop;
+ lca_depth = lca->depth - first_loop_depth;
- gcc_assert (lca_nb >= 0);
- gcc_assert (lca_nb < nb_loops);
+ gcc_assert (lca_depth >= 0);
+ gcc_assert (lca_depth < nb_loops);
/* For each outer loop where init_v is not set, the accesses are
in dependence of distance 1 in the loop. */
if (lca != loop_a
&& lca != loop_b
- && init_v[lca_nb] == 0)
- dir_v[lca_nb] = dir_positive;
+ && init_v[lca_depth] == 0)
+ dir_v[lca_depth] = dir_positive;
lca = lca->outer;
if (lca)
{
- lca_nb = lca->num - first_loop;
+ lca_depth = lca->depth - first_loop_depth;
while (lca->depth != 0)
{
/* If we're considering just a sub-nest, then don't record
any information on the outer loops. */
- if (lca_nb < 0)
+ if (lca_depth < 0)
break;
- gcc_assert (lca_nb < nb_loops);
+ gcc_assert (lca_depth < nb_loops);
- if (init_v[lca_nb] == 0)
- dir_v[lca_nb] = dir_positive;
+ if (init_v[lca_depth] == 0)
+ dir_v[lca_depth] = dir_positive;
lca = lca->outer;
- lca_nb = lca->num - first_loop;
+ lca_depth = 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 13 Dec 2004 16:43:32 -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))
{